Departamento de Matemáticas

IES “Giner de los Ríos”

La programación lineal es un conjunto de técnicas racionales de análisis y de resolución de problemas que tiene por objeto ayudar a los responsables en las decisiones sobre asuntos en los que interviene un gran número de variables.

El nombre de programación lineal no procede de la creación de programas de ordenador, sino de un término militar, programar, que significa 'realizar planes o propuestas de tiempo para el entrenamiento, la logística o el despliegue de las unidades de combate'.

Aunque parece ser que la programación lineal fue utilizada por G. Monge en 1776, se considera a L. V. Kantoróvich uno de sus creadores. La presentó en su libro Métodos matemáticos para la organización y la producción (1939) y la desarrolló en su trabajo sobre la transferencia de masas (1942). Kantoróvich recibió el premio Nóbel de economía en 1975 por sus aportaciones al problema de la asignación óptima de recursos humanos.

La investigación de operaciones en general y la programación lineal en particular recibieron un gran impulso gracias a los ordenadores. Uno de momentos más importantes fue la aparición del método del  simplex. Este método, desarrollado por G. B. Dantzig en 1947, consiste en la utilización de un algoritmo para optimizar el valor de la función objetivo teniendo en cuenta las restricciones planteadas.

La programación lineal hace historia:

El puente aéreo de Berlín

En 1946 comienza el largo período de la guerra fría entre la antigua Unión Soviética (URSS) y las potencias aliadas (principalmente Inglaterra y Estados Unidos). Uno de los episodios más llamativos de esa guerra fría se produjo a mediados de 1948, cuando la URSS bloqueó las comunicaciones terrestres desde las zonas alemanas en poder de los aliados con la ciudad de Berlín, iniciando el bloqueo de Berlín. A los aliados se les plantearon dos posibilidades: o romper el bloqueo terrestre por la fuerza, o llegar a Berlín por el aire. Se adoptó la decisión de programar una demostración técnica del poder aéreo norteamericano; a tal efecto, se organizó un gigantesco puente aéreo para abastecer la ciudad: en diciembre de 1948 se estaban transportando 4500 toneladas diarias; en marzo de 1949, se llegó a las 8000 toneladas, tanto como se transportaba por carretera y ferrocarril antes del corte de las comunicaciones. En la planificación de los suministros se utilizó la programación lineal. (El 12 de mayo de 1949, los soviéticos levantaron el bloqueo)

Las 10 chicos y los 20 chicas de una clase de 2º de bachillerato organizan un viaje para el cual necesitan dinero. Deciden pedir trabajo por las tardes en una compañía encuestadora que contrata a equipos de jóvenes de dos tipos:

• Tipo A _ PAREJAS: 1 chico y 1 chica.

• Tipo B _ EQUIPOS: 1 chico y 3 chicas.

Se paga a 30 € la tarde a la pareja y 50 € la tarde al equipo.

¿Cómo les conviene distribuirse para sacar la mayor cantidad posible de dinero?

X+3YX+YTOTAL

3YYYEQUIPOS

XXXPAREJAS

CHICASCHICOSNÚMERO

Las 10 chicos y los 20 chicas de una clase de 2º de bachillerato organizan un viaje para el cual necesitan dinero. Deciden pedir trabajo por las tardes en una compañía encuestadora que contrata a equipos de jóvenes de dos tipos:

• Tipo A _ PAREJAS: 1 chico y 1 chica.

• Tipo B _ EQUIPOS: 1 chico y 3 chicas.

Se paga a 30 € la tarde a la pareja y 50 € la tarde al equipo.

¿Cómo les conviene distribuirse para sacar la mayor cantidad posible de dinero?

Las 10 chicos y los 20 chicas de una clase de 2º de bachillerato organizan un viaje para el cual necesitan dinero. Deciden pedir trabajo por las tardes en una compañía encuestadora que contrata a equipos de jóvenes de dos tipos:

• Tipo A _ PAREJAS: 1 chico y 1 chica.

• Tipo B _ EQUIPOS: 1 chico y 3 chicas.

Se paga a 30 € la tarde a la pareja y 50 € la tarde al equipo.

¿Cómo les conviene distribuirse para sacar la mayor cantidad posible de dinero?

X+3YX+YTOTAL

3YYYEQUIPOS

XXXPAREJAS

CHICASCHICOSNÚMERO

≤+≤+≥≥

203yx

10yx

0y

0xNúmeros enteros positivos

Número máximo de chicos

Número máximo de chicas

Las 10 chicos y los 20 chicas de una clase de 2º de bachillerato organizan un viaje para el cual necesitan dinero. Deciden pedir trabajo por las tardes en una compañía encuestadora que contrata a equipos de jóvenes de dos tipos:

• Tipo A _ PAREJAS: 1 chico y 1 chica.

• Tipo B _ EQUIPOS: 1 chico y 3 chicas.

Se paga a 30 € la tarde a la pareja y 50 € la tarde al equipo.

¿Cómo les conviene distribuirse para sacar la mayor cantidad posible de dinero ?

≤+≤+≥≥

203yx

10yx

0y

0x

Los puntos que cumplan todas las restricciones se llaman FACTIBLES y dan lugar a la REGIÓN FACTIBLE.

La ganancia total diaria, en euros, es G(x,y)= 30x + 50y

Debemos, por tanto, MAXIMIZAR la FUNCIÓN OBJETIVO G(x,y)= 30x + 50y

≤+≤+≥≥

203yx

10yx

0y

0x

0≥x

0≥y

≤+≤+≥≥

203yx

10yx

0y

0x

10≤+ yx

x y

0 10

2 8

102

8

≤+≤+≥≥

203yx

10yx

0y

0x

203 ≤+ yx

x y

5 5

2 6

52

6

5

203 ≤+ yx

10≤+ yx

0≥x0≥y

203 ≤+ yx

10≤+ yx

0≥x0≥y

Las posibles soluciones (x,y) han de ser números enteros positivos. ¿Por qué?. ¿Siempre es así?.

Las posibles soluciones (x,y) han de pertenecer a la región factible. ¿Por qué?. ¿Puede ser (2,7) una solución?. ¿Por qué?

Toma la función OBJETIVO:

G(x,y)= 30x+50y

y calcula diversas ganancias:

G(2,2) = 60+ 100 = 160 €

G(2,4) = 60 + 200 = 260 €

G(9,1) = 270 + 50 = 320 €

G(5,5) = 150 + 250 = 400 €

.......

¿CÓMO AVERIGUAR EN CUÁL DE LOS PUNTOS SE OBTIENE LA GANANCIA MÁXIMA?

05030 =+ yx

x y

0 0

5

G(0,0)= 0

G(6,0) = 180G(1,5) = 180

G(10,0)= 300

G(5,5)= 400-3

Se localiza la recta que esté lo más arriba posible y que pase por algún punto de la región factible.

Este punto resulta ser el (5,5)

G(0,0) = 0 €

G(6,0) = 180 €

G(1,5) = 180 €

G(10,0) = 300 €

G(5,5) = 400 € VALOR MÁXIMO

04010 =+ yx

x y

0 0

4

G(0,0)= 0

G(6,0) =G(2,1)= 60

G(10,0)= 100

G(2,6)= 260

-1

Se localiza la recta que esté lo más arriba posible y que pase por algún punto de la región factible.

Este punto resulta ser el (2,6)

G(0,0) = 0 €

G(6,0) = 60 €

G(10,0) = 100 €

G(5,5) = 250 €

G(2,6) = 260 € VALOR MÁXIMO

G(5,5)= 250

1º Representa la recta 20x + 40y = 0

06020 =+ yx

x y

0 0

3 -1

2º Comprueba que la función objetivo es paralela a uno de los lados de la región factible.

3º Comprueba que existen dos soluciones, que se localizan en la frontera de la región factible.

G(2,6)= 400G(5,5)= 400