PROGRAMACION LINEAL
Tarea 1. Métodos simplex primal y simplex dual
PRESENTADO POR: CARMEN YOLANDA LANDAZABAL MONSALVE
PRESENTADO AL TUTOR: ALBERTO MARIO PERNETT
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
ESCUELA DE CIENCIAS ADMINISTRATIVAS, CONTABLES, ECONÓMICAS
Y DE NEGOCIOS “ECACEN”
MARZO DE 2019
1
Introducción
El curso de programación Lineal es un área de las matemáticas que tiene aplicabilidad en
varios campos y el profesional de hoy, necesita desarrollar habilidades de pensamiento
superior en la abstracción, el análisis, la síntesis, la inducción, la deducción, etc.
En el presente trabajo encontraremos el desarrollo a los puntos propuestos en la unidad 1
tarea 1 los métodos de programación lineal como el Simplex dual de maximización; el
método simplex de las dos fases con el fin de comprender todos los temas propuestos y así
cumplir con los objetivos propuestos para dicha unidad.
2
Objetivos
Objetivo General
Comprender y aplicar en forma clara los fundamentos conceptuales y teóricos de la
asignatura de programación lineal.
Objetivos Específicos
Realizar de forma individual cada uno de los ejercicios propuestos en la guía de trabajo
Interpretar y aplicar los principios de la programación lineal como el método simplex
dual y de las dos fases para la resolución de problemas relacionados en nuestra
profesión
Desarrollar las capacidades analíticas y de interpretación de datos para solucionar
problemas en contextos del desarrollo profesional
3
Ejercicio 1.
Una empresa de jugos naturales produce tres tipos de bebidas que se venden en los
supermercados de cadena y que cuyas compradoras potenciales son las madres para poner en
las loncheras de sus hijos (Jugo 1 de pera, Jugo 2 de manzana y Jugo 3 tropical). El jugo 1
está compuesto por 20 mililitros el componente A, 30 mililitros el componente B y 20
mililitros el componente C. El jugo 2 está compuesto por 30 mililitros el componente A, 20
mililitros el componente B y 20 mililitros vez el componente C y finalmente el jugo 3 está
compuesto por 20 mililitros el componente A, 10 mililitros el componente B y 20 mililitros
el componente C. Se deben gastar como minino 1500 mililitros del componente A, máximo
1700 mililitros del B y máximo 1300 mililitros del C por producción al día. La utilidad de
los jugos 1, 2 y 3, es respectivamente de 600, 400 y 500 pesos. El componente A, hace
relación al agua usada, el B al saborizante que incluye concentración de azúcar y el C al
conservante.
Formule el problema expuesto en la situación 1 y resuélvalo por el método simplex por los
algoritmos simplex algebraico y simplex de las dos fases. Responda:
Identificar y definir variables
Jugo 1(PERA) = 20A+30B+20C
Jugo 2 (MANZANA) = 30A+20B+20C
Jugo 3 (TROPICAL) = 20A+10B+20C
MODELO CANÓNICO (Con signos < y >)
Función objetivo:
Maximizar
𝑍 = 600𝑋1 + 400𝑋2 + 500𝑋3
Restricciones
20𝑋1 + 30𝑋2 + 20𝑋3 ≥ 1500
30𝑋1 + 20𝑋2 + 20𝑋3 ≤ 1700
20𝑋1 + 10𝑋2 + 20𝑋𝑥3 ≤ 1300
Condiciones de no negatividad 𝑋1 , 𝑋2 , 𝑋3 ≥ 0
4
MODELO ESTANDAR (Convertir los signos < y > en signos de tipo =)
Función objetivo:
Maximizar
𝑍 − 600𝑥1 − 400𝑥2 − 500𝑥3 = 0
Restricciones
20𝑥1 + 30𝑥2 + 20𝑥3 − 1𝑠1 ≥ 1500
30𝑥1 + 20𝑥2 + 20𝑥3 + 1𝑠2 ≤ 1700
20𝑥1 + 10𝑥2 + 20𝑥3 + 1𝑠3 ≤ 1300
Condiciones de no negatividad 𝑋1 , 𝑋2 , 𝑋3 ≥ 0
Desarrollo en el software PHP simplex y adjuntar capturas de pantalla al trabajo incluyendo
resultados.
X1 X2 X3 S1 S2 S3 RESULTADO
Z -600 -400 -500 0 0 0 0
S1 20 30 20 1 0 0 1.500
S2 30 20 20 0 1 0 1.700
5
S3 20 10 20 0 0 1 1.300
A > 1500 ml
B≤ 1700 ml
C≤1300 ml
Utilidad:
Jugo1 = 600
Jugo 2 = 400
Jugo 3 = 500
¿Qué cantidad de cada uno de los jugos debe fabricarse, según el método algebraico del
simplex primal?
Jugo pera = 15
Jugo manzana = 17
Jugo Tropical =13
¿Qué cantidad de cada uno de los jugos debe fabricarse, según el método de las dos fases del
simplex primal?
Jugo pera = 42.5
Jugo manzana = 20
Jugo Tropical =2.5
¿Cuál es la utilidad del problema?
La utilidad seria: $34.750
¿Las respuestas de producción según las condiciones varían de acuerdo a cada método usado?
Cada método arroja resultados diferentes.
PLANTEMOS LA MATRIZ:
A B C
Jugo 1 20 30 20
6
Jugo 2 30 20 20
Jugo 3 20 10 20
Restricciones:
A > 1500 ml
B≤ 1700 ml
C≤1300 ml
Función objetivo:
Umax = 600Jugo1+400Jugo2+500Jugo3
EN SEGUIDA SE FORMA LA MATRIZ DE IDENTIDAD:
20Jugo1+20Jugo2+20Jugo3 + 1s1+0s2+0s3= 1500
30Jugo1+20jugo2+10jugo3 +0s1+1s2+0s3= 1700
20jugo1+20jugo2+20jugo3+0s1+0s2+1s3 = 1300
Definimos la tabla Simplex inicial:
Cb | V. Solución | Solución | A |B |C | S1 | S2 | S3|
0 S1 15 20 30 20 1 0 0
0 S2 17 30 20 10 0 1 0
0 S3 13 20 20 20 0 0 1
7
PROBLEMA 2: Construya un planteamiento de acuerdo con el siguiente problema:
Función objetivo
Maximizar Z = 6X1 + 7X2 + 5X3 + 3X4
MODELO CANONICO
Sujeto a las restricciones:
3X1 + 3X2 + 2X3 + X4 ≤ 75
3X1 + 2X2 + 3X3 + 2X4 ≤ 100
2X1 + 2X2 + 4X3 + 3X4 ≥ 30 Condición de no negatividad
2X1 + 2X2 + 1X3 + 2X4 ≤ 68
X1, X2, X3, X4 ≥ 0
MODELO ESTANDAR
Z-6x1-7x2-5x3-3x4=0
Sujeto a las restricciones:
3X1 + 3X2 + 2X3 + X4 +S1 = 75
3X1 + 2X2 + 3X3 + 2X4 +S2 = 100
2X1 + 2X2 + 4X3 + 3X4 +S3 = 30
2X1 + 2X2 + 1X3 + 2X4 +S4 = 68
METODO SIMPLEX DUAL
Función objetivo
Maximizar Z = 6X1 + 7X2 + 5X3 + 3X4
MODELO CANONICO
8
Sujeto a las restricciones:
3X1 + 3X2 + 2X3 + X4 ≤ 75
3X1 + 2X2 + 3X3 + 2X4 ≤ 100
2X1 + 2X2 + 4X3 + 3X4 ≥ 30 Condición de no negatividad
2X1 + 2X2 + 1X3 + 2X4 ≤ 68
X1, X2, X3, X4 ≥ 0
MODELO ESTANDAR
Z-6x1-7x2-5x3-3x4=0
Sujeto a las restricciones:
3X1 + 3X2 + 2X3 + X4 -S1 = 75
3X1 + 2X2 + 3X3 + 2X4 -S2 = 100
2X1 + 2X2 + 4X3 + 3X4 -S3 = 30
2X1 + 2X2 + 1X3 + 2X4 -S4 = 68
9
EJERCICIO 3:
Raúl García es el heredero de un taller de carpintería que le ha dejado su padre como parte
de tradición familiar. Raúl es un comerciante de vehículos importados que nunca se
interesó por el negocio con el que su padre le crió y le pagó sus estudios universitarios.
Ahora con la muerte de su padre Raúl debe hacerse cargo del negocio, el cual heredará
algún día a uno de sus hijos. Cuando Raúl visita el taller para hacerse cargo, encuentra que
el producto que mayor atención merece por ser el de mayor venta es el de escritorios tipo
deko que su padre diseñó y que se fabrican según especificaciones de los clientes, tipo 1
para hogar, tipo 2 para oficinas y tipo 3 para colegios. Cada escritorio pasa por 3 procesos
básicos el corte de la madera, el ensamblado y la pintura del producto terminado que se
miden en horas de trabajo.
Raúl seguirá la política de contratación de personal de su padre, los turnos rotativos, por lo
cual el tiempo de trabajo es variable entre una y otra semana, las horas mínimas a contratar
por semana se muestran en la tabla 1. A partir de los datos siguientes que se consignan en la
tabla 1, formule el problema de programación lineal y resuélvalo a partir del método
simplex primal de las dos fases para ayudar a Rubén a minimizar los costos del proceso.
Corte Ensamble Pintura Costos por
Tipo de
producto
escritorio X1 X2 X3 semanales
1 2 3 2 US 17
2 2 2 3 US 17
3 3 1 1 US 23
Horas 33 31 35
FUNCION OBJETIVO
Z=17X1+17X2+23X3
Restricciones
2X1+2X2+3X3 ≤ 33
3X1+2X2+1X3 ≤ 31
2X1+3X2+1X3 ≤ 35
10
X1,X2,X3 > 0
MINIMIZAR
Z=17X1+17X2+23X3
Sujeto a:
2X1+2X2+3X3 = 33
3X1+2X2+1X3 = 31
2X1+3X2+1X3 = 35
X1,X2,X3 ≥ 0
MAXIMIZAR
Z = -17 X1 -17 X2 -23 X3 + 0 X4 + 0 X5 + 0 X6
Sujeto a:
2X1+2X2+3X3+1X6 = 33
3X1+2X2+1X3 +1X5 = 31
2X1+3X2+1X3 + 1X4 = 35
X1, X2, X3, X4, X5, X6 ≥ 0
11
Pasamos a construir la primera tabla de la Fase I del método de las Dos Fases..
TABLA No. 1
0 0 0 -1 -1 -1
Base Cb P0 P1 P2 P3 P4 P5 P6
P6 -1 33 2 2 3 0 0 1
P5 -1 31 3 2 1 0 1 0
P4 -1 35 2 3 1 1 0 0
Z -99 -7 -7 -5 0 0 0
La variable que sale de la base es P5 y la que entra es P1.
TABLA No. 2
0 0 0 -1 -1 -1
Base Cb P0 P1 P2 P3 P4 P5 P6
-
P6 -1 12.333333333333 0 0.66666666666667 2.3333333333333 0 1
0.66666666666667
P1 0 10.333333333333 1 0.66666666666667 0.33333333333333 0 0.33333333333333 0
-
P4 -1 14.333333333333 0 1.6666666666667 0.33333333333333 1 0
0.66666666666667
-
Z 0 -2.3333333333333 -2.6666666666667 0 2.3333333333333 0
26.666666666667
La variable que sale de la base es P6 y la que entra es P3.
TABLA No. 3
12
0 0 0 -1 -1 -1
Base Cb P0 P1 P2 P3 P4 P5 P6
-
P3 0 5.2857142857143 0 0.28571428571429 1 0 0.42857142857143
0.28571428571429
-
P1 0 8.5714285714286 1 0.57142857142857 0 0 0.42857142857143
0.14285714285714
- -
P4 -1 12.571428571429 0 1.5714285714286 0 1
0.57142857142857 0.14285714285714
-
Z 0 -1.5714285714286 0 0 1.5714285714286 1.1428571428571
12.571428571429
TABLA No. 4
0 0 0 -1 -1 -1
Base Cb P0 P1 P2 P3 P4 P5 P6
P3 0 3 0 0 1 -0.18181818181818 -0.18181818181818 0.45454545454545
P1 0 4 1 0 0 -0.36363636363636 0.63636363636364 -0.090909090909091
P2 0 8 0 1 0 0.63636363636364 -0.36363636363636 -0.090909090909091
Z 1.0E-14 0 0 0 1 1 1
Existe alguna solución posible para el problema, por lo que podemos pasar a la Fase II para
calcularla.
TABLA No.1
-17 -17 -23
Base Cb P0 P1 P2 P3
P3 -23 3 0 0 1
P1 -17 4 1 0 0
P2 -17 8 0 1 0
Z -273 0 0 0
La solución óptima es Z = 273
13
X1 = 4 X2 = 8 X3 = 3
PROBLEMA 4: De acuerdo a las siguientes condiciones de un problema productivo, donde
se han tomado los datos de costos y restricciones, según ciertas condiciones y necesidades,
determine:
Cantidad de cada uno de las variables a fabricarse, según el método de las dos fases del
simplex primal.
Valor de la función objetivo del problema.
Función objetivo Minimizar Z = 720X1 + 215X2 + 120X3 + 70X4
Sujeto a las restricciones:
30X1 + 5X2 + 3X3 + 7X4 ≥ 510
17X1 + 7X2 + 3X3 + 5X4 ≥ 320
11X1 + 5X2 + 4X3 + 2X4 ≥ 280
7X1 + 6X2 + 5X3 + 1X4 ≥ 170
X1, X2, X3, X4 ≥ 0
Pasamos el problema a la forma estándar, añadiendo variables de exceso, holgura, y
artificiales según corresponda.
Como la restricción 1 es del tipo '≥' se agrega la variable de exceso X5 y la variable
artificial X9.
Como la restricción 2 es del tipo '≥' se agrega la variable de exceso X6 y la variable
artificial X10.
Como la restricción 3 es del tipo '≥' se agrega la variable de exceso X7 y la variable
artificial X11.
Como la restricción 4 es del tipo '≥' se agrega la variable de exceso X8 y la variable
artificial X12.
14
MAXIMIZAR: Z = -720 X1 -215 X2 -120 X3
MINIMIZAR: Z = 720 X1 + 215 X2 +
-70 X4 + 0 X5 + 0 X6 + 0 X7 + 0 X8 + 0 X9
120 X3 + 70 X4
+ 0 X10 + 0 X11 + 0 X12
sujeto a
sujeto a 30 X1 + 5 X2 + 3 X3 + 7 X4 -1 X5 + 1 X9 =
510
30 X1 + 5 X2 + 3 X3 + 7 X4 ≥ 510 17 X1 + 7 X2 + 3 X3 + 5 X4 -1 X6 + 1 X10 =
17 X1 + 7 X2 + 3 X3 + 5 X4 ≥ 320 320
11 X1 + 5 X2 + 4 X3 + 2 X4 ≥ 280 11 X1 + 5 X2 + 4 X3 + 2 X4 -1 X7 + 1 X11 =
7 X1 + 6 X2 + 5 X3 + 1 X4 ≥ 170 280
7 X1 + 6 X2 + 5 X3 + 1 X4 -1 X8 + 1 X12 =
170
X1, X2, X3, X4, X5, X6, X7, X8, X9, X10,
X1, X2, X3, X4 ≥ 0
X11, X12 ≥ 0
Pasamos a construir la primera tabla de la Fase I del método de las Dos Fases.
TABLA No. 1
0 0 0 0 0 0 0 0 -1 -1 -1 -1
Base Cb P0 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12
P9 -1 510 30 5 3 7 -1 0 0 0 1 0 0 0
P10 -1 320 17 7 3 5 0 -1 0 0 0 1 0 0
P11 -1 280 11 5 4 2 0 0 -1 0 0 0 1 0
P12 -1 170 7 6 5 1 0 0 0 -1 0 0 0 1
-
Z -65 -23 -15 -15 1 1 1 1 0 0 0 0
1280
La variable que sale de la base es P9 y la que entra es P1.
TABLA No.2
0 0 0 0 0 0 0 0 -1 -1 -1 -1
Bas C P0 P P2 P P4 P5 P P P P9 P P P
e b 1 3 6 7 8 10 11 12
P1 0 17 1 0.16666666 0. 0.23333333 - 0 0 0 0.033333333 0 0 0
666667 1 333333 0.033333333 333333
333333
P1 - 31 0 4.16666666 1. 1.03333333 0.566666666 - 0 0 - 1 0 0
0 1 66667 3 33333 66667 1 0.566666666
66667
15
P1 - 93 0 3.16666666 2. - 0.366666666 0 - 0 - 0 1 0
1 1 66667 9 0.56666666 66667 1 0.366666666
666667 66667
P1 - 51 0 4.83333333 4. - 0.233333333 0 0 - - 0 0 1
2 1 33333 3 0.63333333 33333 1 0.233333333
333333 33333
Z - 0 - - 0.16666666 - 1 1 1 2.166666666 0 0 0
17 12.1666666 8. 666667 1.166666666 6667
5 66667 5 6667
La variable que sale de la base es P10 y la que entra es P2.
TABLA No. 3
0 0 0 0 0 0 0 0 -1 -1 -1 -1
Bas P1 P1
Cb P0 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10
e 1 2
-
0.04 0.19 0.0 -
P1 0 15.76 1 0 0.05 0 0 0.056 0 0
8 2 4 0.04
6
-
0.31 0.24 0.13 -
P2 0 7.44 0 1 0.2 0 0 0.24 0 0
2 8 6 0.136
4
- -
1.91 0.7 -
P11 -1 69.44 0 0 1.35 0.06 -1 0 0.064 1 0
2 6 0.76
2 4
- -
2.79 1.1 -
P12 -1 15.04 0 0 1.83 0.42 0 -1 0.424 0 1
2 6 1.16
2 4
- -
- 3.18 0.48
Z 0 0 4.70 1.9 1 1 0.512 2.92 0 0
84.48 4 8
4 2
TABLA No. 4
16
- -
-720 -215 12 7 0 0 0 0
0 0
Bas C P P P
P0 P1 P2 P3 P5 P7
e b 4 6 8
-
- 54.5454545 3.954545454 0.227272727 0.136363636
P4 0 1 0.181818181 0 0
70 45455 5455 27273 36364
81818
- -
98.1818181 0.818181818 0.272727272
P8 0 0.090909090 0 0 0 1.454545454 1
81818 18182 72727
909092 5455
- - -
80.9090909 5.090909090
P6 0 2.454545454 0 0 0.636363636 1 0.272727272 0
09091 9091
5455 36364 72727
- -
42.7272727 0.772727272 1.136363636 0.090909090
P3 12 1 0 0 0.318181818 0
27273 72727 3636 909091
0 18182
-
350.4545454 62.72727272 1.818181818 28.63636363
Z 8945.45454 0 0 0 0
5455 7273 1818 6364
54545
La solución óptima es Z = 8945.4545454545
X1 = 0
X2 = 0
X3 = 42.727272727273
X4 = 54.545454545455
17
BIBLIOGRAFIA
Martínez, S. (2014). Investigación de operaciones. (1a. ed.) (pp. 44-67), México: Grupo
Editorial Patria. Disponible en el entorno de conocimiento del curso.
18
