PROBLEMAS DE PROGRAMACIÓN LINEAL METODO SIMPLEX
Ejercicio 1
En un centro de nutrición se desea obtener la dieta de coste máximo con unos
determinados requisitos vitamínicos para un grupo de niños que van a asistir a
campamentos de verano. El especialista estima que la dieta debe contener entre 18 %
unidades de vitamina A, al menos 24 % de vitamina B.
Las variables primalas son, denominados 1, 2, 3, 4, así como su coste por unidad.
El problema contiene 2 restricciones.
Dado el problema de programación lineal
Primal:
Sujeto a
Método Simplex
Tabla de Iteración #1
x y z w s1 s2 p
2 1 1 2 1 0 0 18
3 4 2 1 0 1 0 24
-2 1 -1 -1 0 0 1 0
Tabla de Iteración #2
x y z w s1 s2 p
0 -1.66667 -0.333333 1.33333 1 -0.666667 0 2
1 1.33333 0.666667 0.333333 0 0.333333 0 8
Página 1
0 3.66667 0.333333 -0.333333 0 0.666667 1 16
Tabla de Iteración #3
x y z w s1 s2 p
0 -1.25 -0.25 1 0.75 -0.5 0 1.5
1 1.75 0.75 0 -0.25 0.5 0 7.5
0 3.25 0.25 0 0.25 0.5 1 16.5
Solución Óptima:
p = 16.5;
x = 7.5,
y = 0,
z = 0,
w = 1.5
Ejercicio 2
Empresa dedicada a elaboración de artículos de carpintería (escritorios, mesas y sillas)
que se hacen en 3 etapas diferentes.
Etapa Madera
1
Etapa Carpintería
2
Etapa Acabado
3
Se desea maximizar la producción actual de cada producto dentro de los cuales se tiene
60 escritorios fabricados, 30 mesas fabricadas y 20 sillas fabricadas de los cales se
invierten 48 horas en el corte de la madera 20 horas en el acabado y 8 horas en la
carpintería.
Dado el problema de programación lineal
Primal:
Sujeto a
Página 2
(Restricción de madera)
4 (Restricción de acabado)
2 (Restricción de carpintería)
Donde:
X1 = cantidad de escritorios fabricados
X2 = cantidad de mesas fabricadas
X3 = cantidad de sillas fabricadas
Método Simplex
Tabla de Iteración #1
x y z s1 s2 s3 p
8 6 1 1 0 0 0 48
4 2 1.5 0 1 0 0 20
2 1.5 0.5 0 0 1 0 8
-60 -30 -20 0 0 0 1 0
Tabla de Iteración #2
x y z s1 s2 s3 p
0 0 -1 1 0 -4 0 16
0 -1 0.5 0 1 -2 0 4
1 0.75 0.25 0 0 0.5 0 4
0 15 -5 0 0 30 1 240
Tabla de Iteración #3
x y z s1 s2 s3 p
0 -2 0 1 2 -8 0 24
0 -2 1 0 2 -4 0 8
1 1.25 0 0 -0.5 1.5 0 2
0 5 0 0 10 10 1 280
Solución Óptima:
p = 280;
x = 2,
y = 0,
z=8
Página 3
Ejercicio 3
Una compañía de Ingenieros auditores se especializa en preparar liquidaciones y
auditorías de obras pequeñas de construcción de puentes. Tienen interés en saber
cuántas auditorías y liquidaciones pueden realizar mensualmente para maximizar sus
ingresos. Se dispone de 800 horas de trabajo directo y 320 horas para revisión. Una
auditoría en promedio requiere de 40 horas de trabajo directo y 10 horas de revisión,
además aporta un ingreso de 300 dls. Una liquidación de impuesto requiere de 8 horas de
trabajo directo y de 5 horas de revisión, produce un ingreso de 100 dls. El máximo de
liquidaciones mensuales disponibles es de 60.
OBJETIVO : Maximizar el ingreso total.
VARIABLE DE DECISION: Cantidad de auditorías (X1).
Cantidad de liquidaciones (X2).
RESTRICCIONES : Tiempo disponible de trabajo directo
Tiempo disponible de revisión
Número máximo de liquidaciones.
Maximizar
Sujeto a:
Método Simplex
Tabla de Iteración #1
x y s1 s2 s3 p
40 8 1 0 0 0 800
10 5 0 1 0 0 320
0 1 0 0 1 0 60
-300 -100 0 0 0 1 0
Página 4
Tabla de Iteración #2
x y s1 s2 s3 p
1 0.2 0.025 0 0 0 20
0 3 -0.25 1 0 0 120
0 1 0 0 1 0 60
0 -40 7.5 0 0 1 6000
Tabla de Iteración #3
x y s1 s2 s3 p
1 0 0.0416667 -0.0666667 0 0 12
0 1 -0.0833333 0.333333 0 0 40
0 0 0.0833333 -0.333333 1 0 20
0 0 4.16667 13.3333 0 1 7600
Solución Óptima:
p = 7600;
x = 12,
y = 40
Ejercicio 4
Una refinería de petróleo tiene dos fuentes de petróleo crudo: crudo ligero, que cuesta 35
dólares por barril y crudo pesado a 30 dólares el barril. Con cada barril de crudo ligero, la
refinería produce 0,3 barriles de gasolina (G), 0,2 barriles de combustible para calefacción
(C) y 0,3 barriles de combustible para turbinas (T), mientras que con cada barril de crudo
pesado produce 0,3 barriles de G, 0,4 barriles de C y 0,2 barriles de T. La refinería ha
contratado el suministro de 900000 barriles de G, 800000 barriles de C y 500000 barriles
de T. Hallar las cantidades de crudo ligero y pesado que debe comprar para poder cubrir
sus necesidades al costo mínimo.
Sean las variables de decisión:
X= número de barriles comprados de crudo ligero.
Y= número de barriles comprados de crudo pesado.
La tabla de producción de cada producto con arreglo al tipo de crudo es:
G C T
Ligero 0,3 0,2 0,3
Pesado 0,3 0,4 0,2
Página 5
La función objetivo que hay que minimizar es:
F = 35x + 30y
Las restricciones:
Método Simplex
Tabla de Iteración #1
x y s1 s2 s3 p
0.3 0.3 1 0 0 0 900000
0.2 0.4 0 1 0 0 800000
0.3 0.2 0 0 1 0 500000
-35 -30 0 0 0 1 0
Tabla de Iteración #2
x y s1 s2 s3 p
0 0.1 1 0 -1 0 400000
0 0.266667 0 1 -0.666667 0 466667
1 0.666667 0 0 3.33333 0 1666670
0 -6.66667 0 0 116.667 1 58333300
Tabla de Iteración #3
x y s1 s2 s3 p
0 0 1 -0.375 -0.75 0 225000
0 1 0 3.75 -2.5 0 1750000
1 0 0 -2.5 5 0 500000
0 0 0 25 100 1 70000000
Solución Óptima:
p = 70000000;
x = 500000,
y = 1750000
Ejercicio 5
Página 6
En un centro de nutrición se desea obtener la dieta de coste mínimo con unos
determinados requisitos vitamínicos para un grupo de niños que van a asistir a
campamentos de verano. El especialista estima que la dieta debe contener entre 26 y 32
unidades de vitamina A, al menos 25 unidades de vitamina B y 30 de C, y a lo sumo 14 de
vitamina D. La tabla nos da el número de unidades de las distintas vitaminas por unidad
de alimento consumido para seis alimentos elegidos, denominados 1, 2, 3, 4, 5 y 6, así
como su coste por unidad.
Se desea construir un modelo de PL para conocer la cantidad de cada alimento que hay
que preparar y que satisfaga los requisitos propuestos con coste mínimo.
• Variable de decisión:
xi = cantidad de alimento i =1,2,...,6 que se utiliza para la dieta.
• Conjunto de restricciones:
Método Simplex
Tabla de Iteración #1
x y z w t r s1 s2 s3 s4 -p
26 1 0 3 2 1 -1 0 0 0 0 32
1 2 1 2 1 0 0 -1 0 0 0 25
0 1 2 0 2 2 0 0 -1 0 0 32
1 0 0 1 0 1 0 0 0 -1 0 14
10 14 12 18 20 16 0 0 0 0 1 0
Página 7
Tabla de Iteración #2
x y z w t r s1 s2 s3 s4 -p
1 0.03 0 0.118 0.0769 0.035 -0.03 0 0 0 0 1.23077
0 1.96 1 1.884 0.923 -0.03 0.03 -1 0 0 0 23.7692
0 1 2 0 2 2 0 0 -1 0 0 32
0 -0.038 0 0.84 -0.076 0.96 0.035 0 0 -1 0 12.7692
0 13.61 12 16.82 19.28 15.61 0.384 0 0 0 1 -12.3077
Tabla de Iteración #3
x y z w t r s1 s2 s3 s4 -p
1 0 -0.019 0.07 0.05 0.03 -0.03 0.01 0 0 0 0.76
0 1 0.509 0.960 0.470 -0.01 0.01 -0.50 0 0 0 12.1
0 0 1.49 -0.964 1.52 2.01 -0.019 0.50 -1 0 0 19.8
0 0 0.019 0.921 -0.058 0.960 0.039 -0.019 0 -1 0 13.2
0 0 5.05 3.76 12.8 15.88 0.117 6.94 0 0 1 -177.29
Tabla de Iteración #4
x y z w t r s1 s2 s3 s4 -p
1 0 -0.04 0.09 0.02 0 -0.038 0.009 0.019 0 0 0.378
0 1 0.524 0.951 0.485 0 0.019 -0.504 -0.009 0 0 12.31
0 0 0.737 -0.475 0.757 1 -0.009 0.252 -0.49 0 0 9.84
0 0 -0.689 1.378 -0.786 0 0.04 -0.262 0.475 -1 0 3.77
0 0 -6.66 11.34 0.79 0 0.27 2.93 7.8 0 1 -333.65
Tabla de Iteración #5
x y z w t r s1 s2 s3 s4 -p
1 0 0 0 0.08 0 -0.04 0.02 -0.01 0.075 0 0.11
0 1 1 0 1.02 0 -0.01 -0.32 -0.33 0.69 0 9.70
0 0 0.5 0 0.48 1 0.007 0.161 -0.33 -0.34 0 11.14
0 0 -0.5 1 -0.57 0 0.03 -0.19 0.345 -0.72 0 2.73
0 0 -1 0 7.25 0 -0.12 5.08 3.95 8.21 1 -364.66
Tabla de Iteración #6
x y z w t r s1 s2 s3 s4 -p
1 0 0 0 0.08 0 -0.04 0.02 -0.01 0.07 0 0.112
0 1 1 0 1.02 0 -0.014 -0.323 -0.338 0.69 0 9.70
0 -0.5 0 0 -0.028 1 0.014 0.323 -0.161 -0.691 0 6.29
0 0.5 0 1 -0.05 0 0.028 -0.352 0.176 -0.38 0 7.59
0 1 0 0 8.28 0 -0.14 4.76 3.61 8.90 1 -354.95
Tabla de Iteración #7
x y z w t r s1 s2 s3 s4 -p
Página 8
1 0.75 0 1.5 0 0 0 -0.5 0.25 -0.5 0 11.5
0 1.25 1 0.5 1 0 0 -0.5 -0.25 0.5 0 13.5
0 -0.75 0 -0.5 0 1 0 0.5 -0.25 -0.5 0 2.5
0 17.75 0 35.5 -2 0 1 -12.5 6.25 -13.5 0 269.5
0 3.5 0 5 8 0 0 3 4.5 7 1 -317
Ejercicio 6
El Señor agricultor tiene 480 hectáreas en majes en la que se puede sembrar ya sea trigo
o maíz. El calcula que tiene 800 horas de trabajo disponible durante la estación crucial del
verano. Dados márgenes de utilidad y los requerimientos laborales mostrados a la
derecha, ¿Cuántas hectáreas de cada uno debe plantar para maximizar su utilidad?¿Cuál
es ésta utilidad máxima?
Maiz:
Utilidad: $40 por has.
Trabajo: 2hs por has.
Trigo:
Utilidad: $30 por has.
Trabajo: 1hs por has.
Solución: Como primer paso para la formulación matemática de este problema, se tabula
la información dada (Tabla 1). Si llamamos x a las hectáreas de maíz e y a las hectáreas de
trigo. Entonces la ganancia total P, en dólares, está dada por:
P=40x+30y
Que es la función objetivo por maximizar.
Elementos
Maíz Trigo
disponibles
Horas 2 1 800
Hectáreas 1 1 480
Utilidad por unidad $40 $30
Si consideremos el problema del granjero López, es decir, de maximizar P = 40x+ 30y
sujeta a.
2 x + y <= 800
X + y <= 480
X > 0, y > 0
Página 9
Método Simplex
Tabla de Iteración #1
x y s1 s2 p
2 1 1 0 0 800
1 1 0 1 0 480
-40 -30 0 0 1 0
Tabla de Iteración #2
x y s1 s2 p
1 0.5 0.5 0 0 400
0 0.5 -0.5 1 0 80
0 -10 20 0 1 16000
Tabla de Iteración #3
x y s1 s2 p
1 0 1 -1 0 320
0 1 -1 2 0 160
0 0 10 20 1 17600
Solución Óptima:
p = 17600;
x = 320,
y = 160
Página 10
