Unidad 2.
Programación lineal (PL)
Investigación de operaciones
1
Unidad 2. Programación lineal (PL)
Investigación de operaciones
Instrucciones
Construye el modelo de programación lineal asociado a cada uno de los siguientes problemas. Considera
lo siguiente:
• Determina las variables.
• Determina la función objetivo.
• Construye las restricciones mediante desigualdades.
• No olvides las restricciones de no negatividad.
Puedes resolver tus ejercicios a mano, con letra legible y escanearlos o tomar una fotografía, que deberás
pegar en un documento de word. Otra opción es que utilices el editor de ecuaciones de word para capturar
los ejercicios con sus soluciones.
Modelos de programación lineal
[Link] una granja agrícola se desea criar conejos y pollos como complemento en su economía, de
forma que no se superen en conjunto las 180 horas mensuales destinadas a esta actividad. Su
almacén sólo puede albergar un máximo de 1000 kilogramos de alimento para conejos y pollos. Si se
supone que un conejo necesita 20 kilogramos de este alimento al mes y un pollo 10 kilogramos al
mes, que las horas mensuales de cuidados requeridos por un conejo son 3 y por un pollo son 2 y que
los beneficios que reportaría su venta ascienden a 500 y 300 pesos por cabeza respectivamente,
hallar el número de animales que deben criarse para que el beneficio sea máximo.
2
Unidad 2. Programación lineal (PL)
Investigación de operaciones
Programación Lineal para la Ingeniería Técnica
Solución:
Definimos las variables originales como:
x1 = número de conejos.
x2 = número de pollos.
La función a maximizar, beneficio obtenido, será:
f (x1 , x2 ) = 500x1 + 300x2
Las restricciones lineales del problema se formulas como:
20x1 + 10x2 1000 (para la disponibilidad del pienso)
3x1 + 2x2 180 (para la disponibilidad de horas)
Finalmente, tenemos las restricciones de no negatividad de las variables:
x1 , x2 0
3
115
Unidad 2. Programación lineal (PL)
Investigación de operaciones
El planteamiento del problema queda, por tanto, de la siguiente manera:
max f (x1 , x2 ) = 500x1 + 300x2
s.a.: 20x1 + 10x2 1000
3x1 + 2x2 180
x1 , x2 0
El siguiente paso consistirá en pasar a la forma estándar, esto es,
introducimos variables de holgura en las dos restricciones verdaderas,
obteniendo, una vez realizadas las simplificaciones oportunas:
max 500x1 + 300x2
s.a.: 2x1 + x2 + x H = 100
3
3x1 + 2x2 + xH = 180
4
x , x , x H , xH 0
1 2 3 4
La solución factible básica inicial es:
x1 = x2 = 0 , x H = 100 , x H = 180
3 4
Así, obtenemos la tabla inicial del algoritmo del Simplex:
x3H 100 2 3 1 0
x4H 180 3 2 0 1
500 300 0 0
Continuamos con las siguientes iteraciones:
4
Unidad 2. Programación lineal (PL)
Investigación de operaciones
x1 50 1 1/2 1/2 0
x4H 30 0 1/2 -3/2 1
0 50 -250 0
x1 20 1 0 2 -1
x2 60 0 1 -3 2
0 0 -100 -100
Obtenemos, por tanto, la solución óptima cuyo valor es:
x1* = 20 conejos, x2* = 60 pollos, Z * = 28000 pesetas.
Este problema puede ser resuelto también gráficamente:
500x + 300y = 0 20x + 10y = 1000
Ahora, calculamos los vértices y el valor que toma en ellos la función objetivo:
A = (0,0), B = (50,0), C = (20,60), D = (0,90)
f (A) = 0, f(B) = 25000, f(C) = 28000, f(D) = 27000
5
Unidad 2. Programación lineal (PL)
Investigación de operaciones
Por tanto, obtenemos la misma solución: 20 conejos y 60 pollos, con un beneficio máximo de 28000
pesos
[Link] fabricante produce sillas y mesas para las que requiere la utilización de dos secciones de
producción: la sección de montaje y la sección de pintura. La producción de una silla requiere 1 hora
de trabajo en la sección de montaje y de 2 horas en la de pintura. Por su parte, la fabricación de una
mesa precisa de 3 horas en la sección de montaje y de 1 hora en la de pintura. La sección de
montaje sólo puede estar 9 horas diarias en funcionamiento, mientras que la de pintura sólo 8 horas.
El beneficio produciendo mesas es doble que el de sillas. ¿Cuál ha de ser la producción diaria de
mesas y sillas para que el beneficio sea máximo?.
6
Unidad 2. Programación lineal (PL)
Investigación de operaciones
Solución:
Definimos las variables originales como:
x1 = número de sillas.
x2 = número de mesas.
La función a maximizar, beneficio obtenido, será:
f (x1 , x2 ) = x1 + 2x2
Las restricciones lineales del problema se formulan como:
x1 + 3x2 9 (disponibilidad de horas en la sección de montaje)
2x1 + x2 8 (disponibilidad de horas en la sección de pintura)
Finalmente, tenemos las restricciones de no negatividad de las variables:
x1 , x2 0
El planteamiento del problema queda, por tanto, de la siguiente manera:
max f (x1 , x2 ) = x1 + 2x2
s.a.: x1 + 3x2 9
2x1 + x2 8
x1 , x2 0
Obtenemos la forma estándar al introducir las correspondientes variables de
holgura:
max x1 + 2x2
s.a.: x1 + 3x2 + x H = 9
3
2x1 + x2 + x H = 8
7
Unidad 2. Programación lineal (PL)
Investigación de operaciones
max x1 + 2x2
s.a.: x1 + 3x2 + x H = 9
3
2x1 + x2 + x H = 8
4
x , x , x H , xH 0
La solución factible básica inicial es:
x1 = x2 = 0 , xH = 9 , xH = 8
3 4
Así, obtenemos la tabla inicial del algoritmo del Simplex:
X1 x2 x3H x4H
x3H 9 1 3 1 0
H
x 4 8 2 1 0 1
1 2 0 0
Continuamos con las siguientes iteraciones:
X1 x2 x3H x4H
x2 3 1/3 1 1/3 0
x4H 5 5/3 0 -1/3 1
1/3 0 -2/3 0
X1 x2 x3H x4H
x2 2 0 1 2/5 -1/5
x1 3 1 0 -1/5 3/5
0 0 -3/5 -1/5
8
Unidad 2. Programación lineal (PL)
Investigación de operaciones
Obtenemos, por tanto, la solución óptima cuyo valor es:
x1* = 3 sillas, x2* = 2 mesas, Z * = 7 veces el valor de venta de una silla.
Notamos que de nuevo este problema puede ser resuelto aplicando el método
gráfico, donde idenficamos las variables por comodidad como x e y (número
de sillas y de mesas respectivamente). Asi pues, obtenemos:
C
x + 3y = 9
A
B
2x + y = 8
x + 2y = 0
Ahora, calculamos los vértices y el valor que toma en ellos la función
objetivo:
A = (0,0), B = (4,0), C = (3,2), D = (0,3)
f (A) = 0, f(B) = 4, f(C) = 7, f(D) = 6
Por tanto, obtenemos la misma solución: 3 sillas y 2 mesas, con un beneficio
máximo de 7 veces el valor de una silla.
9
Unidad 2. Programación lineal (PL)
Investigación de operaciones
3. Sobre dos alimentos diferentes tenemos la siguiente información por kilogramo:
Alimento Calorías Proteínas (gr) Precio
(pesos)
A 1000 25 60
B 2000 100 210
Hallar el costo mínimo de una dieta formada sólo por este tipo de alimentos y que al menos aporte
3000 calorías y 100 gramos de proteínas.
Solución:
Definimos las variables originales como:
x1 = kilogramos de alimento A.
x2 = kilogramos de alimento B.
La función a minimizar, coste de la dieta, será:
f (x1 , x2 ) = 60x1 + 210x2
10
Unidad 2. Programación lineal (PL)
Investigación de operaciones
Las restricciones lineales del problema se formulan como:
1000x1 + 2000x2 3000 (aportación mínima de calorías)
25x1 + 100x2 100 (aportación mínima de proteínas)
Finalmente, por su definición, tenemos las restricciones de no negatividad
de las variables:
x1 , x2 0
El planteamiento del problema queda, por tanto, de la siguiente manera:
min f (x1 , x2 ) = 60x1 + 210x2
s.a.: 1000x1 + 2000x2 3000
25x1 + 100x2 100
x1 , x2 0
Cambiando de signo a la función objetivo, simplificando en las restricciones,
e introduciendo variables de holgura y artificiales obtenemos la forma
estándar:
max −60x − 210x − Mx A − Mx A
1 2 5 6
s.a.: x1 + 2x2 − x3 + x5 = 3
H A
x1 + 4x2 − x4H + x6A = 4
x , x , x H , xH , x A, x A 0
1 2 3 4 5 6
La solución factible básica inicial es:
x1 = x2 = xH3 = x H = 0 , xA = 3 , xA = 4
4 5 6
Así, obtenemos la tabla inicial del algoritmo del Simplex:
11
Unidad 2. Programación lineal (PL)
Investigación de operaciones
x 5A 3 1 2 -1 0 1 0 -M
A
x 4 -M
6 1 4 0 -1 0 1
-60 -210 0 0 -M -M
2M - 60 6M - 210 -M -M 0 0
Continuamos con las siguientes iteraciones:
x 5A 1 1/2 0 -1 1/2 1 -M
x2 1 1/4 1 0 -1/4 0 -210
-60 -210 0 0 -M
M 15 M 105
− 0 -M − 0
2 2 2 2
x1 2 1 0 -2 1 -60
x2 1/2 0 1 1/2 -1/2 -210
-60 -210 0 0
0 0 -15 -45
Obtenemos, por tanto, la solución óptima cuyo valor es:
x1* = 2 kilos de alimento A, x2* = 0.5 kilos de alimento B
Z * = 225 pesetas de coste mínimo
Este problema puede ser resuelto aplicando el método gráfico, sin más que
identificar a las variables x e y como las cantidades (kilogramos) de los
alimentos A y B respectivamente. Así pues, obtenemos el siguiente dibujo:
12
Unidad 2. Programación lineal (PL)
Investigación de operaciones
Ahora, calculamos los vértices y el valor que toma en ellos la función
objetivo:
A = (4,0), B = (2,0.5), C = (0,1.5)
f (A) = 240, f(B) = 225, f(C) = 315
Por tanto, obtenemos la misma solución: 2 kilogramos del alimento A y 0.5
del B, con un mínimo de 225 pesetas. Notamos que al movernos por los ejes
de coordenadas que limitan la región de factibilidad, la función objetivo crece
hacia infinito, por lo que en dichos puntos no puede alcanzarse el mínimo
buscado.
13
