Solución de problemas en programación lineal

Ejercicios que deberán ser resueltos por los métodos llamados de la M y de las Dos fases

1. ValorCreativo.blogspot.com
Facilitador: Ing. Román Humberto Garma Manzanilla.
Alumno: ARLO ENRIQUE SOLIS VILLA
Matricula: 10530393
2017

2. -Investigación de Operaciones -
2

Investigación de
Operaciones




EVIDENCIA DEL
APRENDIZAJE
UNIDAD 1


Solución a problemas de
programación lineal

3. -Investigación de Operaciones -
3

Introducción
Como actividad final de la unidad, aplicarás lo aprendido en dos ejercicios que deberán ser
resueltos por los métodos llamados de la M y de las Dos fases. Recuerda que para
resolverlos debidamente es necesario estudiar todo el material de apoyo propuesto en la
unidad, el cual se encuentra especificado como Fuentes de Consulta al final de este
documento y realizar las actividades anteriores.

Propósito

Analizar las alternativas, criterios objetivos y restricciones de un problema determinado.


Instrucciones

1. Lee detenidamente los siguientes ejercicios.

Ejercicio 1

Considera el siguiente problema.

Maximizar Z = 2x1 + 5x2 + 3x3

Sujeto a: x1 - 2x2 + x3 ≥ 20

2x1 + 4x2 + x3 = 50

y x1, x2, x3 ≥ 0


Ejercicio 2

Considera el siguiente problema.

Minimizar Z = 3X1 + 2X2 + 4X3

Sujeto a: 2X1 + X2 + 3X3 = 60

3X1 + 3X2 + 5X3 ≥ 120


y X1, X2, X3 ≥ 0

4. -Investigación de Operaciones -
4
2. Utiliza el método de la gran M y construye la primera tabla simplex completa
para el método simplex e identifica la solución BF inicial (artificial) correspondiente.
También identifica la variable básica entrante inicial y la variable básica que sale.

3. Aplica el método simplex paso a paso para resolver el problema.

4. Utiliza el método de las dos fases para construir la primera tabla simplex
completa para la fase 1 e identifica la solución BF inicial (artificial) correspondiente.
También, identifica la variable básica entrante inicial y la variable básica que sale.

5. Aplica la fase 1 paso a paso.

6. Construye la primera tabla simplex completa de la fase 2.

7. Aplica la fase 2 paso a paso para resolver el problema.

8. Compara la secuencia de soluciones BF que obtuvo en el paso 2 con los pasos

4 y 6. Contesta la pregunta: ¿Cuáles de estas soluciones son factibles solo para el
problema artificial obtenido al introducir las variables artificiales y cuáles son
factibles para el problema real?

9. Utiliza un paquete de software basado en el método simplex (phpsimplex,
jsimplex, herramienta método simplex) para comparar sus resultados con los
hechos a mano. En el contenido de la unidad 1 y en la bibliografía encontrarás
sugerencias de sitios en Internet para usar el programa.

10. Guarda los dos ejercicios con la nomenclatura
DIOP_U1_EA_XXYZ. Sustituye las XX por las dos primeras letras del primer
nombre, la Y por la inicial del apellido paterno y la Z por la inicial del apellido
materno.

11. Revisa la escala de evaluación de la Evidencia de aprendizaje para considerar
los criterios a evaluar.

12. Envía el archivo a tu Docente en línea mediante la sección
de Tareas para recibir retroalimentación. Espera y atiende la retroalimentación
correspondiente.

5. -Investigación de Operaciones -
5

Recomendaciones: Ingresa a los siguientes enlaces para utilizar los programas de
solución y comparación de resultados obtenidos:

 www.phpsimplex.com
 http://soft.ingenieria-industrial.net/programacion_lineal.php
 http://www.zweigmedia.com/MundoReal/simplex.html


SOLUCION METODO DE LA M

Ejercicio 1

Considera el siguiente problema.

Maximizar Z = 2x1 + 5x2 + 3x3

Sujeto a: x1 - 2x2 + x3 ≥ 20

2x1 + 4x2 + x3 = 50

y x1, x2, x3 ≥ 0



RESTRICCION VARIABLE
≥ +R -S
≤ +S
= +R

6. -Investigación de Operaciones -
6

Sumando variables artificiales y variables de holgura

??????
� − �??????
�+??????
�+�
�−�
�= ��

�??????
� + �??????
�+??????
�+ �
� = ��

??????
�,??????
�, ??????
� ≥ �

MAXIMIZAR ?????? = �??????
� + �??????
�+ �??????
�− ??????�
� − ??????�
�+��
�

SUJETO A
??????
� − �??????
�+??????
�+�
�−�
�= ��

�??????
� + �??????
�+??????
�+ �
� = ��

??????
�,??????
�, ??????
� ≥ �

Igualando ecuación a cero

?????? −�??????
� − �??????
�− �??????
�+ ??????�
� + ??????�
�−��
�=�

Se realiza la tabla con las variables
Z X₁ X₂ X₃ �
� R₁ R₂ Sol

y con las variables artificiales
Z
R₁
R₂

7. -Investigación de Operaciones -
7

TABLA 1
Base Z X₁ X₂ X₃ �
� R₁ R₂ Sol
Z 1 -2 -5 -3 0 M M 0
R₁ 0 1 -2 1 -1 1 0 20
R₂ 0 2 4 1 0 0 1 50


Con la primera tabla se obtiene la primera solución básica de inicio donde:

R1=20
R2=50
Z=0

Para eliminar los coeficientes M de la variable artificial Z a cero.
Tomamos como pivote a la fila 2, debemos multiplicar –M por el renglón 2 más el renglón 1,
y se obtienen los valores de Z y se forma esta tabla



TABLA 2
Base Z X₁ X₂ X₃ �
� R₁ R₂ Sol
Z 1 -2-M -5+2M -3-M M 0 M -20M
R₁ 0 1 -2 1 -1 1 0 20
R₂ 0 2 4 1 0 0 1 50


Ahora vamos a realizar lo mismo con la segunda M, tomamos como pivote a la fila 3,
debemos multiplicar –M por el renglón 3 más el renglón 1, y se obtienen los valores de Z y
se forma esta tabla


TABLA 3

8. -Investigación de Operaciones -
8
Base Z X₁ X₂ X₃ �
� R₁ R₂ Sol
Z 1 -2-3M -5-2M -3-2M M 0 0 -70M
R₁ 0 1 -2 1 -1 1 0 20
R₂ 0 2 4 1 0 0 1 50

Se obtiene la solución factible pero no optima

�
�=��
�
�=��
�
�=�
??????
�=�
??????
�=�
??????
�=�

Se aplica método simplex para solución básica pero no optima, realizamos las interacciones
ubicando la función pivot en las filas y columnas, nos vamos a la función objetivo (Z) y como
es un problema de maximización escogemos el coeficiente más negativo en los coeficientes
de variable de decisión

La variable de entrada es X1 y la de salida es la variable R1 con pivote igual a 1

TABLA 4
Base X₁ X₂ X₃ �
� R₁ R₂ Sol Razón
Z -2-3M -5-2M -3-2M M 0 0 -70M
R₁ 1 -2 1 -1 1 0 20 20
R₂ 2 4 1 0 0 1 50 25


Se Multiplica 3M+2 para volver cero en columna pivote.

3�+2 (1)= 3� +2 +(−3�−2)= 0

9. -Investigación de Operaciones -
9

3�+2 (−2)= −6�−4 +(−2�−5)= −8�−9

3�+2 (1)= 3� +2 +(−2�−3)= �−1

3�+2(−1)= −3�−2 +(�)= −2�−2

3�+2(1)= 3�+2 +(0)= 3� +2

3�+2(0)= 0 +(0)= 0

3�+2 (20)=60�+40 +(−70�)= −10�+40

Se Multiplica -2 para volver cero en columna pivote

1(−2)=−2+2=0

−2(−2)=4+4=8

1(−2)=−2+1=−1

−1(−2)=−2+1=−1

1(−2)=−2+0=−2

0(−2)=0+1=1

20(−2)=−40+50=10

10. -Investigación de Operaciones -
10

Se obtiene la siguiente tabla.
Entra X2 y sale R2 con pivote numero 8

TABLA 5
Base X₁ X₂ X₃ �
� R₁ R₂ Sol
Z 0 -9+8M M1 2+2M 2+3M 0 40 + 10M
R₁ 1 -2 1 -1 1 0 20
R₂ 0 8 -1 2 2 1 10

Se multiplica el renglón pivote por 1/8 para hacerlo 1
Se realiza operación 8M+9 por R3 y se suma a R1

8�+9(0)=0+0=0

8�+9(1)=8�+9 + (−8�−9)=0

8�+9(−.12)= −�−1.08 + (�−1)=−2.08

8�+9(.25)=2�+2.25 + (−2�−2)=.25

8�+9(−.25)=2�−2.25+ (3�+2)=�−.25

8�+9(.12)=.96�+1.08+ (0)=.96�+1.08

11. -Investigación de Operaciones -
11
8�+9(1.25)=10�+1.25+(−10�+40)=51.25

Se multiplica 2 por R3 y se suma a R2
2(0)=0+1=1

2(1)=2+(−2)=0

2(−.12)=−.24+1=.75

2(.25)=.5+(−1)=−.

2(−.25)=−.5+1=.5

2(.12)=.24+0=.25

2(1.25)=2.5+20=22.5

Con los resultados se obtiene la siguiente tabla
Entra ??????
3 y sale ??????
1

12. -Investigación de Operaciones -
12
TABLA 6
Base X₁ X₂ X₃ �
� R₁ R₂ Sol
Z 0 0 -2.08 .25 M-.25 1.08 51.25
X₁ 1 0 .75 -.5 .5 .25 22.5
X₂ 0 1 -.12 .25 -.25 .13 1.25

TABLA 7
Base X₁ X₂ X₃ �
� R₁ R₂ Sol
Z 2.83 0 0 -1.17 M+1.17 M+1.83 115
X₃ 1.33 0 1 .67 .67 .33 30
X₂ 0 1 -.12 .25 -.25 .12 5

TABLA 8
Base X₁ X₂ X₃ �
� R₁ R₂ Sol
Z 4 7 0 0 M M+3 150
X₃ 2 4 1 .0 .0 .1 50
S₁ 1 6 0 1 -.1 1 30


Solución Óptima por método de la gran M:
Z= 150 X1=0 X2=0 X3=50

13. -Investigación de Operaciones -
13

METODO DE LAS DOS FASES
TABLA 1
Base X₁ X₂ X₃ S₁ R₁ R₂ Sol
Z 0 0 0 0 -1 -1 0
R₁ 1 -2 1 -1 .1 .0 20
R₂ 2 4 1 0 0 1 50

Sumamos : ?????? + [ �??????�
� + �??????�
�] para obtener el nuevo valor de ??????
Obtenemos la siguiente tabla

TABLA 2
Base X₁ X₂ X₃ S₁ R₁ R₂ Sol
Z 3 2 2 -1 0 0 70
R₁ 1 -2 1 -1 1 .0 20
R₂ 2 4 1 0 0 1 50

De la tabla anterior nuestra variable de entrada es ??????
�y la de salida será ??????
�

TABLA 3
Base X₁ X₂ X₃ S₁ R₁ R₂ Sol
Z 3 2 2 -1 0 0 70
R₁ 1 -2 1 -1 1 .0 20
R₂ 2 4 1 0 0 1 50

14. -Investigación de Operaciones -
14
Se volverán cero los valores que están en la columna pivote (3 y 2) con las siguientes
operaciones.

�?????? = ??????
1∗ −3 + ??????
�??????
2 = ??????
1 ∗ −2 + ??????
2
Obteniendo la siguiente tabla

TABLA 4
Base X₁ X₂ X₃ S₁ R₁ R₂ Sol
Z 0 8 1 2 3 0 10
X₁ 1 -2 1 1 1 .0 20
R₂ 0 8 1 2 2 1 10

De la tabla anterior nuestra columna pivote es ??????
2 por lo que ??????
2 será a variable de entrada y
R2 la de salida.

Se hace el pivote igual a 1 multiplicándolo por 1/8.
Se harán cero los números (8 � −2)
Con las operaciones:
�?????? = ??????
2∗ −8 + ??????
�??????
1= ??????
2 ∗2 + ??????
1
y obtenemos la tabla siguiente:

15. -Investigación de Operaciones -
15
TABLA 5
Base X₁ X₂ X₃ S₁ R₁ R₂ Sol
Z 0 0 0 0 1 1 0
X₁ 1 0 ¾ 1/2 ½ ¼ 45/2
X₂ 0 1 -1/8 ¼ 1/4 1/8 5/4

Con la tabla anterior podemos ver que ya no existen las variables artificiales y la solución es
cero por lo que terminamos la Fase 1 y esa tabla se convierte en nuestra BF inicial

Fase 2: Usamos la solución factible de la fase anterior con la función objetivo original.
Se eliminan las columnas pertenecientes a las variables artificiales ya que ellas ya no existen
y queda la siguiente tabla.

TABLA 6
Base X₁ X₂ X₃ S₁ Sol
Z -2 -5 -3 0 0
X₁ 1 0 ¾ 1/2 45/2
X₂ 0 1 -1/8 ¼ 5/4

Con esta tabla empezamos la maximización.
La variable entrante es ??????
2 y la de la salida es ??????
2
Hacemos la operación.
�?????? = ??????
3 ∗5 + ??????
Y obtenemos la tabla

16. -Investigación de Operaciones -
16

TABLA 7
Base X₁ X₂ X₃ S₁ Sol
Z -2 0 -29/8 5/4 25/4
X₁ 1 0 ¾ -1/2 45/2
X₂ 0 1 -1/8 ¼ 5/4

La variable entrante es ??????
3 y la que sale es??????
1.
Realizamos las siguientes operaciones pivote ∗ 4/3

�?????? = ??????
1∗29/8 + ??????
�??????
2 = ??????
1 ∗1/8 +??????
2

Obteniendo la siguiente tabla

TABLA 8
Base X₁ X₂ X₃ S₁ Sol
Z 17/6 0 0 7/6 115
??????
� 4/3 0 1 -2/3 30
??????
� 1/6 1 0
1
6
⁄ 5

La variable entrante es ??????
3 y la que sale es??????
1.
Realizamos las siguientes operaciones pivote * 6
�??????= ?????? + ??????
2∗ 7/6
�??????
3 = ??????
3 + ??????
2 ∗ 2/3

17. -Investigación de Operaciones -
17

Obteniendo la siguiente tabla:

TABLA 9
Base X₁ X₂ X₃ S₁ Sol
Z 4 7/6 0 0 150
??????
� 2 2/3 1 0 50
??????
� 1 1 0 1 30


En la anterior tabla podemos observar que ya no existen valores negativos Z por lo que
terminan las iteraciones y obtenemos el resultado.
Solución optima:
??????= ��� ??????�=� ??????�=� ??????�= ��

Compara la secuencia de soluciones BF que obtuvo en el paso 2 con los pasos 4 y 6.
Contesta la pregunta. ¿Cuáles de estas soluciones son factibles sólo para el problema
artificial obtenido al introducir las variables artificiales y cuáles son factibles para el problema
real?
Las soluciones de los pasos 2 y 6 son factibles solamente para el problema real mientras
que el del paso 4 solo es factible para el problema artificial

18. -Investigación de Operaciones -
18

Verificación con Software PHP Simplex

19. -Investigación de Operaciones -
19

Ejercicio 2

Considera el siguiente problema.

Minimizar Z = 3X1 + 2X2 + 4X3

Sujeto a: 2X1 + X2 + 3X3 = 60

3X1 + 3X2 + 5X3 ≥ 120

y X1, X2, X3 ≥ 0

Par empezar maximizaremos y aplicaremos los métodos expuestos en el anterior ejercicio
como ya se explicaron ahora con el método de minimizar ocuparemos el mismo método, con
la misma tabla pero como es minimizar haremos los cambios a las restricciones, para este
ejercicio me apoye de un video de youtube realizándolo en Excel por lo que pondré solo las
tablas
RESTRICCION VARIABLE
≥ +R -S
≤ +S
= +R

(1) Maximizar −?????? = −3�
1−2�
2−4�
3

(2) 2�
1+�
2+3�
3+�4=60

(3) 3�
1+3�
2+5�
3−�
5+�
6=120

??????
1,??????
2,??????
3,??????
4,??????
5,??????
6 >=0

20. -Investigación de Operaciones -
20

Tabla 1
??????
� ??????
� ??????
� ??????
� ??????
� ??????
� −?????? ??????.??????
2 1 3 1 0 0 0 60
3 3 5 0 -1 0 0 120
2 1 3 0 0 -1 0 60
3 2 4 0 0 0 1 0



Tabla 2
??????
� ??????
� ??????
� ??????
� ??????
� ??????
� −?????? ??????.??????
0 0 0 1 0 0 0 0
-1/3 4/3 0 0 -1 5/3 0 20
2/3 1/3 1 0 0 -1/3 0 20
1/3 2/3 0 0 0 4/3 1 -80



Tabla 3
??????
1 ??????
� ??????
� ??????
� ??????
� ??????
� −?????? ??????.??????
0 0 0 1 0 1 0 0
-1/3 4/3 0 -5/3 -1 0 0 20
2/3 1/3 1 1/3 0 0 0 20
1/3 2/3 0 -4/3 0 1 1 -80

21. -Investigación de Operaciones -
21


Tabla 4
??????
1 ??????
� ??????
� ??????
� ??????
� ??????
� −?????? ??????.??????
0 0 0 1 0 1 0 0
-1/4 1 0 -5/4 -3/4 0 0 15
3/4 0 1 3/4 1/4 0 0 15
1/2 0 0 -1/2 1/2 0 1 -90



Tabla 5
??????
1 ??????
� ??????
� ??????
� ??????
� ??????
� −?????? ??????.??????
0 0 0 1 0 1 0 0
-1/4 1 0 0 -3/4 5/4 0 20
3/4 0 1 0 1/4 -3/4 0 20
1/2 0 0 0 1/2 1/2 1 -90

POR LO TANTO LA SOLUCION MÁS ÓPTIMA QUE ME SATISFACE EL EJERCIO A
MINIMIZAR ES:

Z = 90

X1 = 0

X2 = 15

X3 = 15

22. -Investigación de Operaciones -
22
METODO DE LAS DOS FASES

????????????????????????????????????????????????�: −� ??????� −� ??????� −� ??????� + � ??????� + � ??????� + � ??????�

� ??????� + � ??????� + � ??????� + � ??????� = ��

� ??????� + � ??????� + � ??????� −� ??????� + � ??????� = ���

??????�,??????�,??????�,??????�,??????�,??????� ≥ �

 Como la restricción 1 es del tipo '=' se agrega la variable artificial X5.
 Como la restricción 2 es del tipo '≥' se agrega la variable de exceso X4 y la variable
artificial X6.

Tabla 1
Base Cb X₁ X₂ X₃ ??????
� ??????
� ??????
� Sol
Z 0 -5 -4 -8 1 0 0 -180
??????
� -1 2 1 3 0 1 0 120
??????
� -1 3 3 5 -1 0 1 50

Sale la variable ??????
� y entra ??????
�

23. -Investigación de Operaciones -
23
Tabla 2
Base Cb X₁ X₂ X₃ ??????
� ??????
� ??????
� Sol
Z 0 1 / 3 -4 / 3 0 1 8 / 3 0 -20
??????
� 0 2 / 3 1 / 3 1 0 1 / 3 0 20
??????
� -1 -1 / 3 4 / 3 0 -1 -5 / 3 1 20

Sale la variable ??????
� y entra ??????
�
Tabla 3
Base Cb X₁ X₂ X₃ ??????
� ??????
� ??????
� Sol
Z 0 0 0 0 0 1 1 0
??????
� 0 3 / 4 0 1 1 / 4 3 / 4 -1 / 4 15
??????
� -2 -1 / 4 1 0 -3 / 4 -5 / 4 3 / 4 15

Pasamos a la fase 2
Tabla 4
Base Cb X₁ X₂ X₃ ??????
� Sol
Z 0 0 0 0 0 -90
??????
� -4 3 / 4 0 1 1 / 4 15
??????
� -2 -1 / 4 1 0 -3 / 4 15

La solución óptima es: ?????? = 90
??????1 = 0
??????2 = 15
??????3 = 15

24. -Investigación de Operaciones -
24

Comprobación con el Software PHP Simplex

25. -Investigación de Operaciones -
25

Compara la serie de soluciones BF de los pasos 1 y 2. Contesta la pregunta. ¿Cuáles de
esta soluciones son factibles sólo para el problema artificial que se obtuvo al introducir las
variables artificiales y cuáles son factibles para el problema real?
Las soluciones de los pasos 1 son factibles para el problema real, mientras que el del paso
2 la primera fase solo es factible para la solución artificial y la fase dos si es factible para el
problema real.

Fuentes consultadas:

Método simplex ejemplo básico a mano, para maximizar [Simplex method to
maximize]
https://www.youtube.com/watch?v=hVjBn14xdMQ
Programación Lineal Maximización
https://www.youtube.com/watch?v=dHTFI-wAPUg
http://www.phpsimplex.com/simplex/solucion2.php?l=es
https://www.youtube.com/watch?v=S-eeFSL0Hrg
https://www.youtube.com/watch?v=AFm-N7WbDxI