Programacion Lineal Tarea 1.docx
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Programacion Lineal Tarea 1.docx as PDF for free.
More details
- Words: 3,333
- Pages: 14
PROGRAMACION LINEAL 100404 TAREA 1. MÉTODOS SIMPLEX PRIMAL Y SIMPLEX DUAL
Presentado a: JOSE MARTIN DIAZ
UNIVERSIDAD NACIONAL ABIERTA Y DISTANCIA 28 marzo de 2019 BOGOTA D.C INTRODUCCION
El método Simplex es un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso. El proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima (el mayor o menor valor posible, según el caso, para el que se satisfacen todas las restricciones). Partiendo del valor de la función objetivo en un punto cualquiera, el procedimiento consiste en buscar otro punto que mejore el valor anterior.
Pasos, fases o etapas de la estrategia de aprendizaje a desarrollar:
El estudiante debe desarrollar individualmente cada uno de los ejercicios planteados de la siguiente manera:
Paso 1. Los ejercicios 1 y 2 del tipo maximizar deben plantearse de manera que se pueda aplicar la solución del modelo de programación lineal, identificando correctamente las condiciones del problema, función objetivo y restricciones. Resuélvalos por los métodos que se proponen en la unidad, métodos simplex primal algebraico y el método simplex primal de las dos fases. JUGO 1: 20 A + 30 B + 20 C JUGO 2: 30 A + 20B +20C JUGO 3 : 20 A + 10 B + 20 C Se debe gastar 𝐴 ≥ 1500 𝐵 ≤ 1700 𝐶 ≤ 1300 UTILIDAD J1=600 J2= 400 J3=500 Z= 600 J1 + 400 J2 + 500 J3 Sujeto A
20 𝐽1 + 30 𝐽2 + 20 𝐽2 ≥ 1500
30 𝐽1 + 20 𝐽2 +10 𝐽3 ≤ 1700 20 𝐽1 + 20 𝐽2 + 20 𝐽3 ≤ 1300 𝐽1 + 𝐽 2 + 𝐽 3 ≥ 0
Maximizar 𝑧 = 600 𝐽1 + 400 𝐽2 + 500 𝐽3 + 0 𝑥4 + 0 𝑥5 + 0 𝑥6 + 0𝑥7 Sujeto A 20 𝐽1 + 30 𝐽2 + 20 𝐽2 + 1 𝐽4 + 1 𝐽7 = 1500 30 𝐽1 + 20 𝐽2 + 10 𝐽2 + 1 𝐽5 = 1700 20𝐽1 + 20 𝐽2 + 20 𝐽2 + 1 𝑗6 = 1300 𝐽1 + 𝐽 2 + 𝐽 3 + 𝐽4 + 𝐽 5 + 𝐽 6 + 𝐽 7 ≥ 0 La variable que sale de la base es p7 y la que entra es p2 Tabla 1 𝑝7 𝑝5 𝑝6 Z
Cb
𝑝0
-1 0 0
1500 1700 1300 -1500
Tabla 1 𝑝2
Cb
𝑝0
0
50
𝑝5
0
700
𝑝6
0
300
Z Tabla 1 𝑝2
0 Cb
𝑝0
400
20 85⁄ 2 5⁄ 2 34750
𝑝1
600
𝑝3
500
Z
Solución óptima Z = 34750
𝑝1 20 30 20 -20
𝑝2
20 20 -30
𝑝1 2⁄ 3 50⁄ 3 20⁄ 3 0
𝑝3 20 10 20 -20
𝑝2 1 0 0 0
𝑝1
𝑝4 -1 0 0 1
𝑝5 0 1 1 0
𝑝6 0 0 0 0
1 0 0 0
𝑝3
𝑝4
2⁄ 3 −10⁄ 3 20⁄ 3 0
−1⁄ 30 2⁄ 3 2⁄ 3 0
𝑝3
𝑝4
𝑝5
𝑝6
−1⁄ 10 1⁄ 20 1⁄ 20 15
0 1⁄ 20 −1⁄ 20 5
−1⁄ 10 1⁄ 40 1⁄ 10 75⁄ 2
𝑝2
0
1
0
1
0
0
0
0
1
0
0
0
𝑝5
𝑝6
0
0
1
0
0
1
0
0
𝑝7
𝑝7 1⁄ 30 −2⁄ 3 −2⁄ 3 1
𝐽1 = 85⁄2 𝐽 2 = 20 𝐽 3 = 5⁄2
Paso 2. Los ejercicios 3 y 4 del tipo minimizar deben plantearse de manera que se pueda aplicar la solución del modelo de programación lineal identificando correctamente las condiciones del problema, función objetivo y restricciones. Resuélvalos por el método simplex primal de las dos fases. Maximizar z = 6x1 + 7x2 +5x3 + 3x4 Sujeto 3𝑥1 + 3𝑥2 + 2𝑥3 + 𝑥4 ≤ 75 3𝑥1 + 2𝑥2 + 3𝑥3 + 2𝑥4 ≤ 100 2𝑥1 + 2𝑥2 + 4𝑥3 + 3𝑥4 ≥30 2𝑥1 + 2𝑥2 + 1𝑥3 + 2𝑥4 ≤ 68
𝑥1 𝑥 2 𝑥3 𝑥4 ≥ 0
MAXIMIZAR Z= 6𝑥1+ 7 𝑥 2 + 5𝑥3 + 3 𝑥4 + 0𝑥5 + 0𝑥 6 + 0𝑥7 + 0 𝑥8 SUJETO 1 3𝑥1 + 3𝑥2 + 2𝑥3 + 𝑥4 + 𝑥5 = 75 3𝑥1 + 2𝑥2 + 3𝑥3 + 2𝑥4 + 𝑥6 = 100 2𝑥1 + 2𝑥2 + 4𝑥3 + 3𝑥4 − 𝑥7 + 𝑥9 = 30 2𝑥1 + 2𝑥2 + 𝑥3 + 2𝑥4 + 𝑥8 = 68 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5, 𝑥6 , 𝑥7 , 𝑥8 , 𝑥9 ≥ 0
Variable que sale de la base es p9 y el que entra es p3 Tabla 1 𝑝5 𝑝6 𝑝9 𝑝8 Z
Cb
𝑝0
𝑝1
𝑝2
𝑝3
𝑝4
𝑝5
𝑝6
𝑝7
𝑝8
𝑝7
0 0 -1 0
75 100 30 68 -30
3 3 2 2 -2
3 2 2 2 -2
2 3
1 2 3 2 -3
1 0 0 0 0
0 1 0 0 0
0 0 -1 0 1
0 0 0 1 0
0 0 1 0 0
Tabla 1 𝑝5
Cb
𝑝0
0
𝑝6
0
𝑝9
0
𝑝8
0
Z
1 -4
𝑝1
𝑝3
𝑝4
𝑝5
𝑝6
𝑝7
𝑝8
𝑝7
60 2 2 1⁄ 155⁄ 3⁄ 2 2 2 1⁄ 1⁄ 15⁄ 2 2 2 3⁄ 121⁄ 3⁄ 2 2 2
0
−1⁄ 2 −1⁄ 4 3⁄ 4 5⁄ 4
1
0
0
0
1
0
0
0
0
1⁄ 2 3⁄ 4 −1⁄ 4 1⁄ 4
−1⁄ 2 −3⁄ 4 1⁄ 4 −1⁄ 4
0
0
0
0
0
0
0
0
𝑝2
0 1 0
0
0 0 1
1
Metodo simplex
La variable que sale de la base es P5 y la que entra es P7. Tabla 1 Base P7 P6 P2 P8 Z
Cb 7 6 7 8
P0 20 50 25 18 759
6
7
5
3
0
0
0
0
P1 0 1 1 0 7
P2 0 0 1 0 0
P3 -8 / 3 5/3 2/3 -1 / 3 -35 / 3
P4 -7 / 3 4/3 1/3 4/3 5/3
P5 2/3 -2 / 3 1/3 -2 / 3 -7 / 3
P6 0 1 0 0 6
P7 1 0 0 0 7
P8 0 0 0 1 8
La variable que sale de la base es P2 y la que entra es P5. Tabla 2 Base P7 P3 P2 P8 Z
Cb 7 5 7 8
P0 100 30 5 28 1109
6
7
5
3
0
0
0
0
P1 8/5 3/5 3/5 1/5 14
P2 0 0 1 0 0
P3 0 1 0 0 0
P4 -1 / 5 4/5 -1 / 5 8/5 11
P5 -2 / 5 -2 / 5 3/5 -4 / 5 -7
P6 8/5 3/5 -2 / 5 1/5 13
P7 1 0 0 0 7
P8 0 0 0 1 8
Tabla 3 Base P7 P3 P5 P8 Z
Cb 7 5 0 8
P0 310 / 3 100 / 3 25 / 3 104 / 3 3502 / 3
6
7
5
3
0
0
0
0
P1 2 1 1 1 21
P2 2/3 2/3 5/3 4/3 35 / 3
P3 0 1 0 0 0
P4 -1 / 3 2/3 -1 / 3 4/3 26 / 3
P5 0 0 1 0 0
P6 4/3 1/3 -2 / 3 -1 / 3 25 / 3
P7 1 0 0 0 7
P8 0 0 0 1 8
La solución óptima es Z = 3502 / 3 X1 = 0 X2 = 0 X3 = 100 / 3 X4 = 0 Paso 3. Resuelva el ejercicio 1 de maximización por el método simplex dual, recuerde que en este método la solución comienza siendo infactible y óptima en comparación con el método simplex primal que comienza siendo factible, pero no óptimo. 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=-17x1-17x2-23x3+0x4+0x5+0x6 Sujeto a 2x1+2x2+3x3+1x4 =33 3x1+2x2+1x3+1x5 =31 2x1+3x2+1x3+1x6 =35 X1,x2,x3,x4,x5,x6 ≥0
Tabla 1 Base P4 P5 P6 Z
Cb 0 0 0
P0 33 31 35 0
-17
-17
-23
0
0
0
P1 2 3 2 17
P2 2 2 3 17
P3 3 1 1 23
P4 1 0 0 0
P5 0 1 0 0
P6 0 0 1 0
La solución óptima es Z = 0 X1 = 0 X2 = 0 X3 = 0 Para maximizar La variable que sale de la base es P4 y la que entra es P3 Tabla 1 Base P4 P5 P6 Z Tabla 2 Base P3 P5 P6 Z Tabla 3 Base P3 P1 P6 Z Tabla 4 Base P3
Cb 0 0 0
P0 33 31 35 0
17
17
23
0
0
0
P1 2 3 2 -17
P2 2 2 3 -17
P3 3 1 1 -23
P4 1 0 0 0
P5 0 1 0 0
P6 0 0 1 0
17
17
23
0
0
0
Cb 23 0 0
P0 11 20 24 253
P1 2/3 7/3 4/3 -5 / 3
P2 2/3 4/3 7/3 -5 / 3
P3 1 0 0 0
P4 1/3 -1 / 3 -1 / 3 23 / 3
P5 0 1 0 0
P6 0 0 1 0
Cb 23 17 0
P0 37 / 7 60 / 7 88 / 7 1871 / 7
17 P1 0 1 0 0
17 P2 2/7 4/7 11 / 7 -5 / 7
23 P3 1 0 0 0
0 P4 3/7 -1 / 7 -1 / 7 52 / 7
0 P5 -2 / 7 3/7 -4 / 7 5/7
0 P6 0 0 1 0
P0 3
17 P1 0
17 P2 0
23 P3 1
0 P4 5 / 11
0 P5 -2 / 11
0 P6 -2 / 11
Cb 23
P1 P2 Z
17 17
4 8 273
1 0 0
0 1 0
0 0 0
-1 / 11 -1 / 11 81 / 11
7 / 11 -4 / 11 5 / 11
-4 / 11 7 / 11 5 / 11
La solución óptima es Z = 273 X1 = 4 X2 = 8 X3 = 3 Paso 4. Resuelva el ejercicio 3 de minimización por el método simplex dual, recuerde que en este método la solución comienza siendo infactible y óptima en comparación con el método simplex primal que comienza siendo factible, pero no óptimo. Minimizar Z = 720X1 + 215X2 + 120X3 + 70X4 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 Maximizar Z=-720X1 - 215X2 - 120X3 - 70X4 +0X5 +0X6 + 0X7 +0X8 +0X9 +0X10 +0X11+0X12 30X1 + 5X2 + 3X3 + 7X4 -1X5 +1X9 =510 17X1 + 7X2 + 3X3 + 5X4 -1X6 +1X10 = 320 11X1 + 5X2 + 4X3 + 2X4 –X7 +1X11 = 280 7X1 + 6X2 + 5X3 + 1X4 -1X8 +1X12 = 170 X1, X2, X3, X4, X5, X6, X7, X8, X9, X10,X11,X12 ≥ 0 Tabla 1 Base P9 P10 P11
Cb -1 -1 -1
P0 510 320 280
0
0
0
0
0
0
0
0
-1
-1
-1
-1
P1 30 17 11
P2 5 7 5
P3 3 3 4
P4 7 5 2
P5 -1 0 0
P6 0 -1 0
P7 0 0 -1
P8 0 0 0
P9 1 0 0
P10 0 1 0
P11 0 0 1
P12 0 0 0
P12 Z
-1
170 7 -65 1280
6 -23
5 -15
1 -15
0 1
0 1
0 1
-1 1
0 0
0 0
0 0
1 0
La variable que sale de la base es P9 y la que entra es P1. Tabla 2 Base Cb P0 P1 0 17
0
0
0
0
0
0
0
0
-1
-1
-1
-1
P1 1
P11 0
P12 0
-1
0
0
1
0
0
P11
-1
93
0
0
-1
0
0
1
0
P12
-1
51
0
0
0
-1
0
0
1
-175
0
1
1
1
P9 1/ 30 -17 / 30 -11 / 30 -7 / 30 13 / 6
P10 0
0
P5 -1 / 30 17 / 30 11 / 30 7/ 30 -7 / 6
P8 0
31
P4 7/ 30 31 / 30 -17 / 30 -19 / 30 1/ 6
P7 0
-1
P3 1/ 10 13 / 10 29 / 10 43 / 10 -17 /2
P6 0
P10
P2 1/ 6 25 / 6 19 / 6 29 / 6 -73 /6
0
0
0
Z
La variable que sale de la base es P10 y la que entra es P2. Tabla 3 Base Cb P0
0
0
0
0
0
0
0
0
-1
-1
-1
-1
P1
P3
P4
P5
P6
P7
P8
P9
P10
P11
P12
P1
0
1
1/ 25 -6 / 25
0
0
-1 / 25 6/ 25
0
0
P11
-1
1736 / 25
0
0
239 / 125
-8 / 125
0
-19 / 25
1
0
-1
376 / 25
0
0
349 / 125
0
-1
53 / 125
-29 / 25
0
1
-2112 / 25
0
0
-588 / 125
19 / 25 29 / 25 -48 / 25
-1
P12
-169 / 125 -229 / 125 398 / 125
7/ 125 -17 / 125 8/ 125
0
1
-7 / 125 17 / 125
0
0
24 / 125 31 / 125
0
0
6/ 125 39 / 125
0
P2
394 / 25 186 / 25
P 2 0
1
1
64 / 125
73 / 25
0
0
Z
-53 / 125 61 / 125
La variable que sale de la base es P12 y la que entra es P3.
Tabla 4 Base Cb
P0
0
0
0
P1
P2 P3
0
0
0
0
0
-1
-1
-1
-1
P4
P5
P6
P7
P8
P9
P10
P11
P12
P1
0
5410 / 349
1
0
0
78 / 349
P2
0
2010 / 349
0
1
0
158 / 349
P11
-1
20640 0 / 349
0
0
-34 / 349
P3
0
1880 / 349
0
0
1
0 20640 / 349
0
0
Z
-17 / 349 64 / 349
7/ 349
0
6/ 349
17 / -7 / 349 349
0
-6 / 349
129 / 349 79 / -12 349 / 349
0
39 / -64 349 / 349
129 / 349
0
-39 / 349
-1
239 / 349
-79 / 349
12 / 1 349
239 / 349 125 / 349
-229 / 349
-53 / 349
145 / 349
0
-79 / 349
12 / 1 349
53 / 349 145 / 349 428 337 / / 349 349
0
34 / 349
125 / 349 239 / 349
0
588 / 349
La variable que sale de la base es P2 y la que entra es P8. Tabla 5 Base Cb P1 0 P8
0
P11
-1
P3
0
Z
0
0
0
0
0
0
0
0
-1
-1
-1
-1
P0 190 / 13 670 / 13 310 / 13
P1 1
P3 0
P6 1/ 13 -43 / 13 29 / 13
P7 0
P8 0
P12 0
1
0
-1
-1
0
P10 -1 / 13 43 / 13 -29 / 13
P11 0
0
P9 1/ 13 -64 / 39 35 / 39
1
0
0
P4 2/ 13 158 / 39 112 / 39 31 / 39 112 / 39
P5 -1 / 13 64 / 39 -35 / 39
310 / 13 310 / 13
P2 -2 / 13 349 / 39 239 / 39 125 / 39 239 / 39
17 / 39 35 / 39
-10 0 / 13 -29 1 / 13
-17 / 39 4/ 39
10 / 13 42 / 13
0
0
0
1
0 0
0
0 0
1 0
0 0
La variable que sale de la base es P11 y la que entra es P6. Tabla 6 Base Cb P1 0 P8
0
0 P0 P1 400 1 / 29 2520 0 / 29
0
0
0
0
0
0
0
-1
-1
-1
-1
P2 5/ 87 -4 / 29
P3 0
P4 22 / 87 -6 / 29
P5 -4 / 87 9/ 29
P6 0
P7 1/ 29 -43 / 29
P8 0
P9 4/ 87 -9 / 29
P10 0
P11 -1 / 29 43 / 29
P12 0
0
0
1
0
-1
P6
0
310 / 29
0
P3
0
930 / 29
0
-1 / 45
0
Z
239 / 87 95 / 87
0
0
0
112 / 87 -17 / 87
1
-35 / 87 11 / 87 0
0
1
0
0
-13 / 29 -10 / 29 0
0
0
0
35 / 87 -11 / 87 1
-1
13 / 29
0
0
10 / 29
0
1
1
1
Existe alguna solución posible para el problema, por lo que podemos pasar a la Fase II para calcularla. METODO SIMPLEX Tabla 1 Base P1
Cb -720
P8
0
P6
0
P3
-120
Z
P0 400 / 29 2520 / 29 310 / 29 930 / 29 399600 / 29
-720
-215
-120
-70
0
0
0
0
P1 1
P2 5 / 87
P3 0
P7 1 / 29
P8 0
-4 / 29 -239 / 87 95 / 87 1235 / 29
0
P5 -4 / 87 9 / 29
P6 0
0
P4 22 / 87 -6 / 29 -112 / 87 -17 / 87 -2570 / 29
0
1
-35 / 87 11 / 87 520 / 29
1
-43 / 29 -13 / 29 -10 / 29 480 / 29
0
0 P8 0
0 0 0
0 1 0
0 0
0 0 0
La variable que sale de la base es P1 y la que entra es P4. Tabla 2 Base P4
Cb -70
P8
0
P6
0
P3
-120
Z
P0 600 / 11 1080 / 11 890 / 11 470 / 11 98400 / 11
-720
-215
-120
-70
0
P1 87 / 22 9 / 11
P2 5 / 22
P3 0
P4 1
P5 P6 -2 / 11 0
P7 3 / 22
0
0
3 / 11
0
0
-7 / 11 1
-16 / 1 11 -3 / 11 0
1
0
1 / 11
0
-7 / 22 0
0
0
20 / 11
0
315 / 11
-1 / 11 56 / -27 / 11 11 17 / 25 / 22 22 3855 / 690 / 11 11
La solución óptima es Z = 98400 / 11 X1 = 0
0
0
0
X2 = 0 X3 = 470 / 11 X4 = 600 / 11
Paso 5. En grupo harán uso del complemento Solver de Excel para discutir si coinciden las respuestas obtenidas por los métodos manuales descritos anteriormente y además si resulta complejo o favorable el uso de herramientas tecno pedagógicas para solucionar problemas de la investigación de operaciones.
ONCLUCIONES El método simplex Es una herramienta algebraica que permite localizar de manera eficiente el óptimo entre los puntos extremos de una solución a un problema de programación lineal. Este método utiliza el álgebra de matrices, en el cual se forma la inversa de una matriz para resolver una serie de ecuaciones simultaneas. El método simplex se emplea con un proceso interactivo o sea que se usa sucesivamente la misma rutina básica de cálculo, lo que da por resultado una serie de soluciones sucesivas hasta que se encuentra la mejor. Una característica básica del método Simplex es que la última solución produce una contribución tan grande o mayor que la solución previa en un problema de maximización, lo que da la seguridad de llegar finalmente a la respuesta óptima.
Presentado a: JOSE MARTIN DIAZ
UNIVERSIDAD NACIONAL ABIERTA Y DISTANCIA 28 marzo de 2019 BOGOTA D.C INTRODUCCION
El método Simplex es un procedimiento iterativo que permite mejorar la solución de la función objetivo en cada paso. El proceso concluye cuando no es posible continuar mejorando dicho valor, es decir, se ha alcanzado la solución óptima (el mayor o menor valor posible, según el caso, para el que se satisfacen todas las restricciones). Partiendo del valor de la función objetivo en un punto cualquiera, el procedimiento consiste en buscar otro punto que mejore el valor anterior.
Pasos, fases o etapas de la estrategia de aprendizaje a desarrollar:
El estudiante debe desarrollar individualmente cada uno de los ejercicios planteados de la siguiente manera:
Paso 1. Los ejercicios 1 y 2 del tipo maximizar deben plantearse de manera que se pueda aplicar la solución del modelo de programación lineal, identificando correctamente las condiciones del problema, función objetivo y restricciones. Resuélvalos por los métodos que se proponen en la unidad, métodos simplex primal algebraico y el método simplex primal de las dos fases. JUGO 1: 20 A + 30 B + 20 C JUGO 2: 30 A + 20B +20C JUGO 3 : 20 A + 10 B + 20 C Se debe gastar 𝐴 ≥ 1500 𝐵 ≤ 1700 𝐶 ≤ 1300 UTILIDAD J1=600 J2= 400 J3=500 Z= 600 J1 + 400 J2 + 500 J3 Sujeto A
20 𝐽1 + 30 𝐽2 + 20 𝐽2 ≥ 1500
30 𝐽1 + 20 𝐽2 +10 𝐽3 ≤ 1700 20 𝐽1 + 20 𝐽2 + 20 𝐽3 ≤ 1300 𝐽1 + 𝐽 2 + 𝐽 3 ≥ 0
Maximizar 𝑧 = 600 𝐽1 + 400 𝐽2 + 500 𝐽3 + 0 𝑥4 + 0 𝑥5 + 0 𝑥6 + 0𝑥7 Sujeto A 20 𝐽1 + 30 𝐽2 + 20 𝐽2 + 1 𝐽4 + 1 𝐽7 = 1500 30 𝐽1 + 20 𝐽2 + 10 𝐽2 + 1 𝐽5 = 1700 20𝐽1 + 20 𝐽2 + 20 𝐽2 + 1 𝑗6 = 1300 𝐽1 + 𝐽 2 + 𝐽 3 + 𝐽4 + 𝐽 5 + 𝐽 6 + 𝐽 7 ≥ 0 La variable que sale de la base es p7 y la que entra es p2 Tabla 1 𝑝7 𝑝5 𝑝6 Z
Cb
𝑝0
-1 0 0
1500 1700 1300 -1500
Tabla 1 𝑝2
Cb
𝑝0
0
50
𝑝5
0
700
𝑝6
0
300
Z Tabla 1 𝑝2
0 Cb
𝑝0
400
20 85⁄ 2 5⁄ 2 34750
𝑝1
600
𝑝3
500
Z
Solución óptima Z = 34750
𝑝1 20 30 20 -20
𝑝2
20 20 -30
𝑝1 2⁄ 3 50⁄ 3 20⁄ 3 0
𝑝3 20 10 20 -20
𝑝2 1 0 0 0
𝑝1
𝑝4 -1 0 0 1
𝑝5 0 1 1 0
𝑝6 0 0 0 0
1 0 0 0
𝑝3
𝑝4
2⁄ 3 −10⁄ 3 20⁄ 3 0
−1⁄ 30 2⁄ 3 2⁄ 3 0
𝑝3
𝑝4
𝑝5
𝑝6
−1⁄ 10 1⁄ 20 1⁄ 20 15
0 1⁄ 20 −1⁄ 20 5
−1⁄ 10 1⁄ 40 1⁄ 10 75⁄ 2
𝑝2
0
1
0
1
0
0
0
0
1
0
0
0
𝑝5
𝑝6
0
0
1
0
0
1
0
0
𝑝7
𝑝7 1⁄ 30 −2⁄ 3 −2⁄ 3 1
𝐽1 = 85⁄2 𝐽 2 = 20 𝐽 3 = 5⁄2
Paso 2. Los ejercicios 3 y 4 del tipo minimizar deben plantearse de manera que se pueda aplicar la solución del modelo de programación lineal identificando correctamente las condiciones del problema, función objetivo y restricciones. Resuélvalos por el método simplex primal de las dos fases. Maximizar z = 6x1 + 7x2 +5x3 + 3x4 Sujeto 3𝑥1 + 3𝑥2 + 2𝑥3 + 𝑥4 ≤ 75 3𝑥1 + 2𝑥2 + 3𝑥3 + 2𝑥4 ≤ 100 2𝑥1 + 2𝑥2 + 4𝑥3 + 3𝑥4 ≥30 2𝑥1 + 2𝑥2 + 1𝑥3 + 2𝑥4 ≤ 68
𝑥1 𝑥 2 𝑥3 𝑥4 ≥ 0
MAXIMIZAR Z= 6𝑥1+ 7 𝑥 2 + 5𝑥3 + 3 𝑥4 + 0𝑥5 + 0𝑥 6 + 0𝑥7 + 0 𝑥8 SUJETO 1 3𝑥1 + 3𝑥2 + 2𝑥3 + 𝑥4 + 𝑥5 = 75 3𝑥1 + 2𝑥2 + 3𝑥3 + 2𝑥4 + 𝑥6 = 100 2𝑥1 + 2𝑥2 + 4𝑥3 + 3𝑥4 − 𝑥7 + 𝑥9 = 30 2𝑥1 + 2𝑥2 + 𝑥3 + 2𝑥4 + 𝑥8 = 68 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5, 𝑥6 , 𝑥7 , 𝑥8 , 𝑥9 ≥ 0
Variable que sale de la base es p9 y el que entra es p3 Tabla 1 𝑝5 𝑝6 𝑝9 𝑝8 Z
Cb
𝑝0
𝑝1
𝑝2
𝑝3
𝑝4
𝑝5
𝑝6
𝑝7
𝑝8
𝑝7
0 0 -1 0
75 100 30 68 -30
3 3 2 2 -2
3 2 2 2 -2
2 3
1 2 3 2 -3
1 0 0 0 0
0 1 0 0 0
0 0 -1 0 1
0 0 0 1 0
0 0 1 0 0
Tabla 1 𝑝5
Cb
𝑝0
0
𝑝6
0
𝑝9
0
𝑝8
0
Z
1 -4
𝑝1
𝑝3
𝑝4
𝑝5
𝑝6
𝑝7
𝑝8
𝑝7
60 2 2 1⁄ 155⁄ 3⁄ 2 2 2 1⁄ 1⁄ 15⁄ 2 2 2 3⁄ 121⁄ 3⁄ 2 2 2
0
−1⁄ 2 −1⁄ 4 3⁄ 4 5⁄ 4
1
0
0
0
1
0
0
0
0
1⁄ 2 3⁄ 4 −1⁄ 4 1⁄ 4
−1⁄ 2 −3⁄ 4 1⁄ 4 −1⁄ 4
0
0
0
0
0
0
0
0
𝑝2
0 1 0
0
0 0 1
1
Metodo simplex
La variable que sale de la base es P5 y la que entra es P7. Tabla 1 Base P7 P6 P2 P8 Z
Cb 7 6 7 8
P0 20 50 25 18 759
6
7
5
3
0
0
0
0
P1 0 1 1 0 7
P2 0 0 1 0 0
P3 -8 / 3 5/3 2/3 -1 / 3 -35 / 3
P4 -7 / 3 4/3 1/3 4/3 5/3
P5 2/3 -2 / 3 1/3 -2 / 3 -7 / 3
P6 0 1 0 0 6
P7 1 0 0 0 7
P8 0 0 0 1 8
La variable que sale de la base es P2 y la que entra es P5. Tabla 2 Base P7 P3 P2 P8 Z
Cb 7 5 7 8
P0 100 30 5 28 1109
6
7
5
3
0
0
0
0
P1 8/5 3/5 3/5 1/5 14
P2 0 0 1 0 0
P3 0 1 0 0 0
P4 -1 / 5 4/5 -1 / 5 8/5 11
P5 -2 / 5 -2 / 5 3/5 -4 / 5 -7
P6 8/5 3/5 -2 / 5 1/5 13
P7 1 0 0 0 7
P8 0 0 0 1 8
Tabla 3 Base P7 P3 P5 P8 Z
Cb 7 5 0 8
P0 310 / 3 100 / 3 25 / 3 104 / 3 3502 / 3
6
7
5
3
0
0
0
0
P1 2 1 1 1 21
P2 2/3 2/3 5/3 4/3 35 / 3
P3 0 1 0 0 0
P4 -1 / 3 2/3 -1 / 3 4/3 26 / 3
P5 0 0 1 0 0
P6 4/3 1/3 -2 / 3 -1 / 3 25 / 3
P7 1 0 0 0 7
P8 0 0 0 1 8
La solución óptima es Z = 3502 / 3 X1 = 0 X2 = 0 X3 = 100 / 3 X4 = 0 Paso 3. Resuelva el ejercicio 1 de maximización por el método simplex dual, recuerde que en este método la solución comienza siendo infactible y óptima en comparación con el método simplex primal que comienza siendo factible, pero no óptimo. 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=-17x1-17x2-23x3+0x4+0x5+0x6 Sujeto a 2x1+2x2+3x3+1x4 =33 3x1+2x2+1x3+1x5 =31 2x1+3x2+1x3+1x6 =35 X1,x2,x3,x4,x5,x6 ≥0
Tabla 1 Base P4 P5 P6 Z
Cb 0 0 0
P0 33 31 35 0
-17
-17
-23
0
0
0
P1 2 3 2 17
P2 2 2 3 17
P3 3 1 1 23
P4 1 0 0 0
P5 0 1 0 0
P6 0 0 1 0
La solución óptima es Z = 0 X1 = 0 X2 = 0 X3 = 0 Para maximizar La variable que sale de la base es P4 y la que entra es P3 Tabla 1 Base P4 P5 P6 Z Tabla 2 Base P3 P5 P6 Z Tabla 3 Base P3 P1 P6 Z Tabla 4 Base P3
Cb 0 0 0
P0 33 31 35 0
17
17
23
0
0
0
P1 2 3 2 -17
P2 2 2 3 -17
P3 3 1 1 -23
P4 1 0 0 0
P5 0 1 0 0
P6 0 0 1 0
17
17
23
0
0
0
Cb 23 0 0
P0 11 20 24 253
P1 2/3 7/3 4/3 -5 / 3
P2 2/3 4/3 7/3 -5 / 3
P3 1 0 0 0
P4 1/3 -1 / 3 -1 / 3 23 / 3
P5 0 1 0 0
P6 0 0 1 0
Cb 23 17 0
P0 37 / 7 60 / 7 88 / 7 1871 / 7
17 P1 0 1 0 0
17 P2 2/7 4/7 11 / 7 -5 / 7
23 P3 1 0 0 0
0 P4 3/7 -1 / 7 -1 / 7 52 / 7
0 P5 -2 / 7 3/7 -4 / 7 5/7
0 P6 0 0 1 0
P0 3
17 P1 0
17 P2 0
23 P3 1
0 P4 5 / 11
0 P5 -2 / 11
0 P6 -2 / 11
Cb 23
P1 P2 Z
17 17
4 8 273
1 0 0
0 1 0
0 0 0
-1 / 11 -1 / 11 81 / 11
7 / 11 -4 / 11 5 / 11
-4 / 11 7 / 11 5 / 11
La solución óptima es Z = 273 X1 = 4 X2 = 8 X3 = 3 Paso 4. Resuelva el ejercicio 3 de minimización por el método simplex dual, recuerde que en este método la solución comienza siendo infactible y óptima en comparación con el método simplex primal que comienza siendo factible, pero no óptimo. Minimizar Z = 720X1 + 215X2 + 120X3 + 70X4 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 Maximizar Z=-720X1 - 215X2 - 120X3 - 70X4 +0X5 +0X6 + 0X7 +0X8 +0X9 +0X10 +0X11+0X12 30X1 + 5X2 + 3X3 + 7X4 -1X5 +1X9 =510 17X1 + 7X2 + 3X3 + 5X4 -1X6 +1X10 = 320 11X1 + 5X2 + 4X3 + 2X4 –X7 +1X11 = 280 7X1 + 6X2 + 5X3 + 1X4 -1X8 +1X12 = 170 X1, X2, X3, X4, X5, X6, X7, X8, X9, X10,X11,X12 ≥ 0 Tabla 1 Base P9 P10 P11
Cb -1 -1 -1
P0 510 320 280
0
0
0
0
0
0
0
0
-1
-1
-1
-1
P1 30 17 11
P2 5 7 5
P3 3 3 4
P4 7 5 2
P5 -1 0 0
P6 0 -1 0
P7 0 0 -1
P8 0 0 0
P9 1 0 0
P10 0 1 0
P11 0 0 1
P12 0 0 0
P12 Z
-1
170 7 -65 1280
6 -23
5 -15
1 -15
0 1
0 1
0 1
-1 1
0 0
0 0
0 0
1 0
La variable que sale de la base es P9 y la que entra es P1. Tabla 2 Base Cb P0 P1 0 17
0
0
0
0
0
0
0
0
-1
-1
-1
-1
P1 1
P11 0
P12 0
-1
0
0
1
0
0
P11
-1
93
0
0
-1
0
0
1
0
P12
-1
51
0
0
0
-1
0
0
1
-175
0
1
1
1
P9 1/ 30 -17 / 30 -11 / 30 -7 / 30 13 / 6
P10 0
0
P5 -1 / 30 17 / 30 11 / 30 7/ 30 -7 / 6
P8 0
31
P4 7/ 30 31 / 30 -17 / 30 -19 / 30 1/ 6
P7 0
-1
P3 1/ 10 13 / 10 29 / 10 43 / 10 -17 /2
P6 0
P10
P2 1/ 6 25 / 6 19 / 6 29 / 6 -73 /6
0
0
0
Z
La variable que sale de la base es P10 y la que entra es P2. Tabla 3 Base Cb P0
0
0
0
0
0
0
0
0
-1
-1
-1
-1
P1
P3
P4
P5
P6
P7
P8
P9
P10
P11
P12
P1
0
1
1/ 25 -6 / 25
0
0
-1 / 25 6/ 25
0
0
P11
-1
1736 / 25
0
0
239 / 125
-8 / 125
0
-19 / 25
1
0
-1
376 / 25
0
0
349 / 125
0
-1
53 / 125
-29 / 25
0
1
-2112 / 25
0
0
-588 / 125
19 / 25 29 / 25 -48 / 25
-1
P12
-169 / 125 -229 / 125 398 / 125
7/ 125 -17 / 125 8/ 125
0
1
-7 / 125 17 / 125
0
0
24 / 125 31 / 125
0
0
6/ 125 39 / 125
0
P2
394 / 25 186 / 25
P 2 0
1
1
64 / 125
73 / 25
0
0
Z
-53 / 125 61 / 125
La variable que sale de la base es P12 y la que entra es P3.
Tabla 4 Base Cb
P0
0
0
0
P1
P2 P3
0
0
0
0
0
-1
-1
-1
-1
P4
P5
P6
P7
P8
P9
P10
P11
P12
P1
0
5410 / 349
1
0
0
78 / 349
P2
0
2010 / 349
0
1
0
158 / 349
P11
-1
20640 0 / 349
0
0
-34 / 349
P3
0
1880 / 349
0
0
1
0 20640 / 349
0
0
Z
-17 / 349 64 / 349
7/ 349
0
6/ 349
17 / -7 / 349 349
0
-6 / 349
129 / 349 79 / -12 349 / 349
0
39 / -64 349 / 349
129 / 349
0
-39 / 349
-1
239 / 349
-79 / 349
12 / 1 349
239 / 349 125 / 349
-229 / 349
-53 / 349
145 / 349
0
-79 / 349
12 / 1 349
53 / 349 145 / 349 428 337 / / 349 349
0
34 / 349
125 / 349 239 / 349
0
588 / 349
La variable que sale de la base es P2 y la que entra es P8. Tabla 5 Base Cb P1 0 P8
0
P11
-1
P3
0
Z
0
0
0
0
0
0
0
0
-1
-1
-1
-1
P0 190 / 13 670 / 13 310 / 13
P1 1
P3 0
P6 1/ 13 -43 / 13 29 / 13
P7 0
P8 0
P12 0
1
0
-1
-1
0
P10 -1 / 13 43 / 13 -29 / 13
P11 0
0
P9 1/ 13 -64 / 39 35 / 39
1
0
0
P4 2/ 13 158 / 39 112 / 39 31 / 39 112 / 39
P5 -1 / 13 64 / 39 -35 / 39
310 / 13 310 / 13
P2 -2 / 13 349 / 39 239 / 39 125 / 39 239 / 39
17 / 39 35 / 39
-10 0 / 13 -29 1 / 13
-17 / 39 4/ 39
10 / 13 42 / 13
0
0
0
1
0 0
0
0 0
1 0
0 0
La variable que sale de la base es P11 y la que entra es P6. Tabla 6 Base Cb P1 0 P8
0
0 P0 P1 400 1 / 29 2520 0 / 29
0
0
0
0
0
0
0
-1
-1
-1
-1
P2 5/ 87 -4 / 29
P3 0
P4 22 / 87 -6 / 29
P5 -4 / 87 9/ 29
P6 0
P7 1/ 29 -43 / 29
P8 0
P9 4/ 87 -9 / 29
P10 0
P11 -1 / 29 43 / 29
P12 0
0
0
1
0
-1
P6
0
310 / 29
0
P3
0
930 / 29
0
-1 / 45
0
Z
239 / 87 95 / 87
0
0
0
112 / 87 -17 / 87
1
-35 / 87 11 / 87 0
0
1
0
0
-13 / 29 -10 / 29 0
0
0
0
35 / 87 -11 / 87 1
-1
13 / 29
0
0
10 / 29
0
1
1
1
Existe alguna solución posible para el problema, por lo que podemos pasar a la Fase II para calcularla. METODO SIMPLEX Tabla 1 Base P1
Cb -720
P8
0
P6
0
P3
-120
Z
P0 400 / 29 2520 / 29 310 / 29 930 / 29 399600 / 29
-720
-215
-120
-70
0
0
0
0
P1 1
P2 5 / 87
P3 0
P7 1 / 29
P8 0
-4 / 29 -239 / 87 95 / 87 1235 / 29
0
P5 -4 / 87 9 / 29
P6 0
0
P4 22 / 87 -6 / 29 -112 / 87 -17 / 87 -2570 / 29
0
1
-35 / 87 11 / 87 520 / 29
1
-43 / 29 -13 / 29 -10 / 29 480 / 29
0
0 P8 0
0 0 0
0 1 0
0 0
0 0 0
La variable que sale de la base es P1 y la que entra es P4. Tabla 2 Base P4
Cb -70
P8
0
P6
0
P3
-120
Z
P0 600 / 11 1080 / 11 890 / 11 470 / 11 98400 / 11
-720
-215
-120
-70
0
P1 87 / 22 9 / 11
P2 5 / 22
P3 0
P4 1
P5 P6 -2 / 11 0
P7 3 / 22
0
0
3 / 11
0
0
-7 / 11 1
-16 / 1 11 -3 / 11 0
1
0
1 / 11
0
-7 / 22 0
0
0
20 / 11
0
315 / 11
-1 / 11 56 / -27 / 11 11 17 / 25 / 22 22 3855 / 690 / 11 11
La solución óptima es Z = 98400 / 11 X1 = 0
0
0
0
X2 = 0 X3 = 470 / 11 X4 = 600 / 11
Paso 5. En grupo harán uso del complemento Solver de Excel para discutir si coinciden las respuestas obtenidas por los métodos manuales descritos anteriormente y además si resulta complejo o favorable el uso de herramientas tecno pedagógicas para solucionar problemas de la investigación de operaciones.
ONCLUCIONES El método simplex Es una herramienta algebraica que permite localizar de manera eficiente el óptimo entre los puntos extremos de una solución a un problema de programación lineal. Este método utiliza el álgebra de matrices, en el cual se forma la inversa de una matriz para resolver una serie de ecuaciones simultaneas. El método simplex se emplea con un proceso interactivo o sea que se usa sucesivamente la misma rutina básica de cálculo, lo que da por resultado una serie de soluciones sucesivas hasta que se encuentra la mejor. Una característica básica del método Simplex es que la última solución produce una contribución tan grande o mayor que la solución previa en un problema de maximización, lo que da la seguridad de llegar finalmente a la respuesta óptima.
Related Documents
Programacion Lineal Tarea 1.docx
October 2019 49
Optimizacion Programacion Lineal
June 2020 14
Programacion Lineal Defininiones
June 2020 9
Programacion Lineal Entera.docx
June 2020 6
Programacion Lineal 1
November 2019 8
Taller Programacion Lineal
October 2019 26More Documents from "JENNIFER"
Intariri.docx
June 2020 63
Metoda Cubului.docx
August 2019 96
Sistemas De Inocuidad Y Seguridad De Los Alimentos
April 2020 12
Tarea 1 Estructura Molecular.docx
October 2019 26