I.E.S. CASTILLO DE LUNA

Programación lineal

En un problema de programación lineal con dos variables x; y, se trata de optimizar (hacer máximo o mínimo,según los casos) una función, llamada función objetivo de la forma F = px+ qy sujeta a una serie de restriccionesdadas mediante un sistrema de desigualdades lineales de tipo8>><>>:

a1x+ b1y � c1a2x+ b2y � c2

:::amx+ bmy � cm

Las variables x; y se llaman variables de decisión.Los puntos del plano que cumplen todas las restricciones (el sistema de desigualdades lineal) están en un recinto

convexo �nito (poligonal) o in�nito, llamado región factible o región de validez del problema.Los puntos de la región factible cumplen todas las restricciones y se llaman soluciones factibles.La solución factible que haga óptima la función objetivo, se llama solución óptima.Para resolver usaremos las siguientes propiedades:

� Si existe una única solución que optimice la función objetivo, ésta se encuentra en un vértice de la regiónfactible acotada, nunca en el interior de la misma. (Principio de las esquinas).

� Si la función objetivo toma el mismo valor óptimo en dos vértices, también toma idéntico valor en los puntosdel segmento que determinan esos vértices. En este caso el problema tiene solución múltiple.

� Si la región es no acotada, el problema puede carecer de solución, pero de existir se encuentra en losvértices de la región factible.

Sistemas de inecuaciones lineales con dos incógnitas:8>><>>:a1x+ b1y � c1a2x+ b2y � c2

:::amx+ bmy � cm

Para resolver se procede:

1. Resolver cada inecuación grá�camente por separado indicando mediante �echas o sombreando, el semiplanosolución.

2. La región factible está formado por las soluciones comunes a todas las inecuaciones.

Puede tener o no solución. La solución puede estar o no acotada. Si la solución es acotada, sus puntos estánencerrados en un polígono convexo.

Ejemplo: Representar la región factible asociada al sistema

8>><>>:x+ 3y � 20x+ y � 10x � 0y � 0

� Representemos la recta x+ 3y = 20; y = 20� x3

x y2 620 0Localizemos el semiplano x+ 3y < 20: Para ello comprobamos que el punto (0; 0) pertenece a dicho semiplano,

pues 0 + 3 � 0 < 20

1

� Representemos la recta x+ y = 10; y = 10� x

x y0 1010 0Localizemos el semiplano x + y < 10: Para ello comprobamos que el punto (0; 0) pertenece a dicho semiplano,

pues 0 + 0 < 20

� Reprersentemos los semiplanos x > 0; y > 0

� Resumiendo toda la información obtenemos la región factible, en la cual es importante tener calculado lospuntos de corte

�x+ 3y � 20x+ y � 10 =) x = 5 = y; (5; 5)

�x+ 3y = 20x = 0

=) x = 0; y =20

3;

�0;20

3

�Los otros dos puntos de corte son evidentes (0; 0) y (10; 0)

2

Ejemplo 2: Región acotada. Solución única. Maximizar la función F (x; y) = 10x + 4y sujeta a las restric-

ciones

8>><>>:x+ 3y � 20x+ y � 10x � 0y � 0

:

La región factible la hemos calculado en el ejemplo anterior. Pero, ¿cómo saber en que punto de dicho recintose maximiza la función objetivo?Trazaremos la recta 10x+ 4y = 0; recta en la que la función objetivo se anula. Recorreremos la región factible

con las paralelas a la anterior 10x+ 4y = z. De todas estas líneas buscaremos aquella en la que se alcanza el valoróptimo de la función objetivo, que pasará por un vértice de la región factible. En este caso, la que pasa por el

vértice�0;20

3

�; donde F

�0;20

3

�= 40 � 20

3=800

3= 266: 67:

Vértices F (x; y) = 10x+ 40y(0; 0) F (0; 0) = 10 � 0 + 40 � 0 = 0�0;20

3

�F

�0;20

3

�= 40 � 20

3=800

3= 266: 67

(5; 5) F (5; 5) = 10 � 5 + 40 � 5 = 250(10; 0) F (10; 0) = 10 � 10 + 40 � 0 = 100

Por tanto el máximo se alcanza en�0;20

3

�y la función toma el valor de

800

3:

Ejemplo 3: Región acotada. Solución múltiple. Maximizar la función F (x; y) = �4x + y + 9 sujeta a las

restricciones

8<: �4x+ y � 0�3x+ 10y � 05x+ 8y � 74

3

Vértices F (x; y) = �4x+ y + 9(0; 0) F (0; 0) = 9

(2; 8) F (2; 8) = 9

(10; 3) F (10; 3) = �28La solución se alcanza en todos los puntos del segmento de extremos B(0; 0) y A(2; 8), y el valor máximo es 9.

Ejemplo 3: Región no acotada. Solución única. Minimizar y maximizar la función F (x; y) = 2x+ 3y sujeta

a las restricciones

8>>>><>>>>:x+ y � 5x+ 3y � 94x+ y � 8x � 0y � 0

Vértices F (x; y) = 2x+ 3y(0; 8) F ((0; 8) = 24(3; 2) F (3; 2) = 12(1; 4) F (1; 4) = 14(9; 0) F (9; 0) = 18Por tanto, si tiene mínimo que se alcanza en (3,2) con valor 12, pero no tiene máximo, pues crece inde�nidamente.

Ejemplo 4: Región no acotada. Sin solución. Minimizar y maximizar la función F (x; y) = x+ y+1 sujeta a

las restricciones

8<: 3x+ 4y � 132x� 3y � 35x� y � 27

4

En este caso, no alcanza ni el máximo ni el mínimo.

Ejemplo 5: Problema del transporte. El objetivo del problema de transporte es determinar cuántas unidadesde producto deben enviarse desde cada origen hasta cada destino de forma que se minimicen los costes totalesde distribución, se satisfaga la demanda de cada destino y no se exceda la capacidad de oferta de cada unode los orígenes.

Destino 1 Destinoo 2 Destino n OfertasOrigen 1Origen 2

Origen mDemandasDesde dos almacenes, A y B, se tiene que distribuir fruta a tres mercados de la ciudad. El almacén A dispone

de 10 toneladas de fruta diarias y el B de 15 toneladas, que se reparten en su totalidad. Los dos primeros mercados,necesitan, diariamente, 8 toneladas de fruta, mientras que el tercero necesita de 9 toneladas diarias. El coste deltransporte desde cada almacén a cada mercado viene dado por los datos del cuadro. Plani�ca el transporte paraque el coste sea mínimo.

Mercado 1 Mercado 2 Mercado 3Almacén A 10 15 20Almacén B 15 10 10Llamemos x a la cantidad de mercancía que entrega el almacén A al mercado 1,e y a la mercancía que entrega

el almacén A al mercado 2, el resto de la mercancía se distribuye de la forma que se recoge en la tabla.Envíos al mercado 1 al mercado 2 al mercado 3 Ofertasdesde el almacén A x y 10� x� y 10desde el almacén B 8� x 8� y �1 + x+ y 15Demandas 8 8 9

Todas los envíos deben ser números positivos.

x � 0y � 0

10� x� y � 08� y � 08� x � 0

�1 + x+ y � 0

9>>>>>>=>>>>>>;La función coste es 10 �x+15 �y+20 � (10� x� y)+15 � (8� x)+10 (8� y)+10 � (�1 + x+ y) = 390�5y�15x

Minimizar C(x; y) = 390� 15x� 5y sujeto a

x � 0y � 0

10� x� y � 08� y � 08� x � 0

�1 + x+ y � 0

9>>>>>>=>>>>>>;

5

C(x; y) = 390� 15x� 5yC(1; 0) = 375C(0; 1) = 385C(8; 0) = 270C(0; 8) = 350C(8; 2) = 260; alcanza el valor mínimoC(2; 8) = 320Por tanto las cantidades a transportar son

Envíos al mercado 1 al mercado 2 al mercado 3 Ofertasdesde el almacén A 8 2 0 10desde el almacén B 0 6 9 15Demandas 8 8 9

Ejemplo 6: Problema de la dieta. Se trata de hallar la manera más económica de alimentar al ejercito peroasegurando al mismo tiempo unos determinados niveles nutricionales. Este tipo de problema se puede plantearen distintas formas tales como minimizar los gastos de la compra, dieta para el ganado, una dieta adelgazanteque cumpla unos determinados niveles de calorías, proteínas, hidratos de carbono, .

Imaginemos que las necesidades semanales mínimas de una persona en proteínas, hidratos de carbono y grasasson 8, 12, 9 unidades respectivamente. Supongamos que debemos obtener un preparado con esa composición mínimamezclando los productos A y B cuyos contenidos por kilogramo son los que se indican en la siguiente tabla:

Producto A Producto BProteínas 2 1Hidratos 6 1Grasas 1 3Coste(kg) 600 400¿Cuántos kilogramos de cada producto deberán comprarse semanalmente para que el costo de preparar la dieta

sea mínimo?De�namos x kg de producto A e y kg de producto B y completemos la información de la tabla.

Producto A Producto BProteínas 2 1 8Hidratos 6 1 12Grasas 1 3 9Coste(kg) 600 400Cantidad x y

La función coste es C(x; y) = 600x+ 400y sujeto a

2x+ y � 86x+ y � 12x+ 3y � 9x � 0y � 0

9>>>>=>>>>;6

C(x; y) = 600x+ 400yC (0; 12) = 4800C (1; 6) = 3000C (3; 2) = 2600C (9; 0) = 5400Por tanto la solución es 3 kg del producto A y 2 kg del producto B.Programación lineal entera.Vamos a proponer dos problemas de similar formulación, pero que nos sirve para introducir la programación

lineal entera.

Ejercicio 1: Una fábrica de tableros de madera pintados, produce 2 tipos de tableros:

� Normales, con una mano de imprimación y una de pintura.

� Extras, con una mano de imprimación y tres de pintura.

Disponen de 10 mil m2 de imprimación y 20 mil m2 de pintura y tableros sin pintar en cantidad ilimitada. Susganancias netas son 10 euros por m2 de tablero normal y 40 euros por m2 de tablero extra.¿Qué cantidad de tableros de cada tipo les conviene fabricar para maximizar ganacias?x = miles de m2 de tableros normalesy = miles de m2 de tableros extrax+ 3y � 20 (pintura)x+ y � 10 (imprimación)x � 0y � 0

Función a maximizar G(x; y) = 10x+ 40y; sujeta a

8>><>>:x+ 3y � 20x+ y � 10x � 0y � 0

:

Este problema está resuelto en el ejemplo 1. Por tanto la ganancia máxima se alcanza fabricando 0 m2 de

tablero normal y20

3miles de m2 de tablero extra, consiguiendo un bene�cio de

800000

3= 266666; 67 euros.

Ejercicio 2: Las 20 chicas y los 10 chicos de una clase organizan un viaje. Para sacar dinero trabajan en unacompañía que contrata a 2 tipos de equipos:

� Tipo A, formadonpor un chico y una chica.

� Tipo B, formado por 3 chicas y un chico.

Paga a 10 euros la tarde al tipo A y 40 euros la tarde al tipo B.¿Como les conviene distribuirse para conseguir la mayor cantidad de dinero?

7

x = número de equipos de Ay = número de equipos de Bx+ 3y � 20 (número de chicas disponibles)x+ y � 10 (número de chicos disponibles)x � 0y � 0

Función a maximizar F (x; y) = 10x+ 40y; sujeta a

8>><>>:x+ 3y � 20x+ y � 10x � 0y � 0

Pero una restricción a tener en cuenta y que los distingue del problema anterior, es que tanto x; ydeben ser números enteros. Observando el dibujo, sólo hay 54 puntos factibles.

La solución x = 0; y =20

3no nos vale, pues x e y deben ser números enteros. Si analizamos el valor de la función

objetivo en los 54 puntos factibles, el máximo se alcanza para (2; 6) ; donde F (2; 6) = 10 � 2 + 40 � 6 = 260 euros.

Ejemplo 7: Una empresa elabora dos productos, cada una de ellas en una cantidad que es múltiplo de 1000.Conoce que la demanda, de ambos productos conjuntamente, es mayor que 3000 unidades y menor que 6000unidades. Asimismo, sabe que la cantidad que se demanda de un producto es mayor que la mitad y menorque el doble de la de otro. Si la empresa desea vender toda la producción:

¿De cuántos modos puede organizar la producción?Para obtener bene�cios máximos, ¿de cuánto ha de ser la producción de cada uno de ellos si uno se vende a un

precio que es el triple que el del otro?x cantidad elaborada del producto 1 (expresadas en miles) e y cantidad elaborada del producto 2 (expresadas

en miles).x+ y > 3x+ y < 6

x >y

2x < 2y

x � 0; enteroy � 0; entero

9>>>>>>>=>>>>>>>;

8

Las soluciones facibles sólo son tres: (2; 3) ; (3; 2) ; (2; 2) : Luego la producción sólo se puede organizar de 3 maneraProducto 1 (unidades) Producto 2 (unidades)

2000 30003000 20002000 2000

La función bene�cio es B(x; y) = k(x+ 3y)B(2; 2) = 8kB(2; 3) = 11kB(3; 2) = 9kLuego debe fabricar 2000 unidades del primer producto y 3000 undidades del segundo producto para maximizar bene�cios.

9