Trabajo De Investigación De Operaciones

Profesor: Manuel Campuzano

Integrantes: Carlos Andrés Cuevas y

Carlos Mario Fontalvo

Tema: Metodo De Las 2 Fases y

Metodo De La Gran M

Fecha: 31/03/2020

Universidad Antonio Nariño

Santa Marta
D.T.C.H.
 Tabla De Contenido

Contents
Introducción.......................................................................................................................................3
Objetivos............................................................................................................................................4
Metodo de las 2 fases........................................................................................................................5
Pasos para resolver un problema de programación lineal:................................................................6
Otras aplicaciones del metodo de dos fases:.....................................................................................7
Ejemplo:.............................................................................................................................................8
Conclusión:.......................................................................................................................................18
Web-Grafía.......................................................................................................................................19
Introducción

Este método trata de buscar la solución de la manera más fácil, tratando de eludir la
constante M, aquella que definimos como un número muy grande, teniendo como objetivo
llegar a la conclusión más óptima, este método lo implementamos en 2 partes, la primera
es donde agregamos las variables auxiliares a las restricciones del problema, de modo de
obtener la solución más básica y la segunda resolver por Simplex el problema original a
partir de la solución básica factible hallada en fase
Objetivos

Conocer la decisión del método de Dos fases, los pasos para resolver el problema de
programación lineal por medio de dos fases y comprender cuando es más efectivo
utilizarlo.
1. Definir si el método de Dos fases es una manera más compacta de resolver el método
simplex.
2. Comprender si es el uso de este método requiere de una previa comprensión de la
técnica M para solucionar problemas de programación lineal.
3. Conocer la manera convertir las inecuaciones para dar solución por medio de la técnica
de Dos fases.
4. Conocer las variables matemáticas que permiten dar solución al problema de
programación lineal por medio de la técnica de Dos fases
Metodo de las 2 fases

Es una técnica utilizada en la solución de problemas de programación lineal, el método de

las dos fases es una variante del algoritmo simple que es usado como alternativa al
método de la gran M, dónde se evita el uso de la constante M para variables artificiales.

¿Qué requerimientos debe cumplir?

1. Modificar las restricciones para el lado no sea negativo
2. Convertir las desigualdades en su forma estándar
3. Añadir una variable artificial no negativa (a) a las restricciones que en el paso 1 fuera =
0.

El método de las dos fases como su nombre lo indica, trabajar por medio de dos fases o
procedimientos, con el objetivo de encontrar primeramente una solución factible inicial y
después pasar resolver el modelo a través del modelo simplex. Para utilizar este método
de debe tener el modelo en su forma ampliada, las variables de decisión deben ser reales
y mayor a cero.

[ CITATION Byr13 \l 2058 ]

Pasos para resolver un problema de programación
lineal:

Paso 1:

 Se fórmula el problema inicial reemplazando Xo por la suma de las variables

artificiales únicamente (R1, R2, ETC)
 Las restricciones quedan igual que las del problema original
 Si el problema tiene un espacio factible, el valor mínimo de la nueva función
objetivo (Ro), lo cual indica que todas las variables artificiales son cero.
 Si lo anterior no se cumple, el problema termina concluyendo que no existe
solución factible

Paso 2:

 Si el valor mínimo fue cero en la anterior (Ro=0) ser utiliza la solución final como
inicio de esta fase colocando únicamente la Xo del problema original con valor de
solución cero.
 A partir de aquí se sustituyen los valores de las casillas de Xo correspondientes a
las columnas pivotes considerando, además, el tipo de objetivo que este (PL)
tenga.

[ CITATION And12 \l 2058 ]

Otras aplicaciones del metodo de dos fases:

 Resolver un problema LP cuya función objetivo (W) sea minimizar la suma de las
variables artificiales (Fase 1)
 Si el valor óptimo W es positivo el problema original no tiene solución factible
 Si el valor óptimo W es 0 no hay variables artificiales en la solución básica se
eliminan las columnas de la tabla óptima de la fase 1 que corresponden a las
variables artificiales y se combinan la función objetivo original con las restricciones
de dicha tabla fase 2
Ejemplo:
Hay que recordar que con este método en la primera fase se debe de minimizar (ya sea
un problema de maximización o minimización), y en la segunda fase hay que hacer lo que
dice inicialmente el problema.
Aplicamos el método de las dos fases para resolver el siguiente problema:

Min z= 4x + x 1 2

S.a 3x +x =3 1 2

4x +x ≥ 6
1 2

X +2x ≤4
1 2

X , x ≥0
1 2

Estandarizamos:

Min z= 4x +x 1 2
s.a: 3x +x +A =3
1 2 1

4x +3x -E +A =6
1 2 1 2

X +2x +H =4
1 2 1

x, x≥ 0
1 2

Dónde: A= variable artificial

E= variable de exceso
H= variable de holgura

El objetivo de la fase uno es encontrar una solución básica factible (SBF) inicial.
Fase 1:
* añadir variables artificiales no negativas a las restricciones, como el método de la gran
M.
* El objetivo de fase uno es minimizar la suma de variables artificiales.
* resolver problemas de la fase 1 con las variables artificiales.
* formular un nuevo problema reemplazando la función objetivo por la suma de las
variables artificiales.
* La nueva función objetivo se minimiza sujeta a las restricciones del problema original.
* La fase 1 termina cuando no hay variables artificiales en la base y se encuentran la SBF
inicial.
* Si el problema tiene un espacio factible el valor mínimo de la función objetivo óptimo
será cero, lo cual indica que todas las variables artificiales son ceros. En este momento
pasamos a la fase 2.
* Si el valor de la función objetivo optima es mayor que cero, el problema no tiene solución
y termina notándose que no existen soluciones factibles.

Entonces:
Min z= A +A 1 2

s.a 3x +x +A =3 1 2 1

4x +3x -E +A =6
1 2 1 2

X +2X +H =4
1 2 1

X1, X ≥0 2

La función z la igualamos a 0

Queda de la siguiente forma:

Min z-0x -0x -0H -0E -A -A =0

1 2 1 1 1 2

s.a: 3x +x +A =3 1 2 1

4X +3X -E +A =6
1 2 1 2

X +2X +H =4
1 2 1

X , X ≥01 2

Los datos quedarían de la siguiente forma mostrados en esta tabla.

Para formar SB inicial el coeficiente de A1 Y A2 en la fila cero deben ser 0.
Iteración Variables Variables agregadas
originales
Ecuación Variables Lado
X1 X2 H1 E1 A1 A2 derecho
Básicas
0 Z 0 0 0 0 -1 -1 0
 1 A1 3 1 0 0 1 0 3
0
2 A2 4 3 0 -1 0 1 6

3 H1 1 2 1 0 0 0 4

Para quitar los valores de -1 en A1 y A 2 vamos a realizar dos operaciones:

A la fila 0 le sumamos la fila 1 y a esa misma fila 0 le sumaremos la fila 2

(Fila 0  fila 0 + fila 1) y (fila 0  fila 0 + fila 2)

Una vez realizada las operaciones anteriores la tabla quedaría como se muestra:

La SB inicial es no factible porque contiene 2 variables artificiales que no forman parte de la

solución del problema.

Variables originales Variables agregadas

Iteración Ecuación Variables Lado

derecho
Básicas
X1 X2 H1 E1 A1 A2

0 Z 7 4 0 -1 0 0 9

1 A1 3 1 0 0 1 0 3
1
2 A2 4 3 0 -1 0 1 6

3 H1 1 2 1 0 0 0 4

Columna pivote:

Entra el coeficiente mas positivo en el reglon z = x 1

3/3= 1 → menor sale A 1

6/4=3/2

4/1=4

Variables originales Variables agregadas

Variables Lado
 Iteración Ecuación Básicas derecho
X1 X2 H1 E1 A1 A2

0 Z 0 5/3 0 -1 -7/3 0 2

1 X1 1 1/3 0 0 1/3 0 1
2
2 A2 0 5/3 0 -1 -4/3 1 2

3 H1 0 5/3 1 0 -1/3 0 3

Columna pivote:

Entra el coeficiente mas positivo en el reglon z = x 2

1/1/3=3
2/5/3=6/5→ menor sale A2
3/5/3=9/5

Aplicamos gauss jordan sobre la columna entrante y obtenemos esta nueva tabla:

Variables originales Variables agregadas

Iteración Ecuación Variables Lado

derecho
Básicas
X1 X2 H1 E1 A1 A2

0 Z 0 0 0 -1 -1 -1 0

1 X1 1 0 0 3/5 3/5 -1/5 3/5

3
2 x2 0 0 0 -4/5 -4/5 3/5 6/5

3 H1 0 1 1 1 1 -1 1

Podemos observar que en la base ya no se encuentra ninguna variable artificial solamente nos
quedan x1, x2 y H 1.

En el renglon z podemos ver que ya no hay ningun valor positivo y en el lado derecho el valor de z
es de 0.
Una vez obtenido esto hemos conseguido la solucion basica factible(SBF) inicial para
empezar a desarrollar la fase 2.
La solucion basica factible actual es de:

Z= 0

X1= 3/5

X2= 6/5

H1= 1

Aquí terminaria la fase 1.

Pasamos a la fase 2 por que la solucion basica factible (SBF) actual es obtima porque z no puede
mejorarse.

*la SB actual es factible en el problema original porque no contiene las variables artificiales A 1 Y A2.

*la SB actual es la SB inical de la fase 2.

Fase 2
Objetivo original
* utilizar la solucion optima de la fase 1 como solucion de incio para el problema original. En este
caso, la funcion objetivo original se expresa en terminos de las variables no basicas utilizando las
eliminaciones usuales gauss jordan.

Min z = 4x1+x2 +0H1+0E1

Igualamos la funcion a 0:

Min z-4x1-x2-0H1-0E1=0

En la tabla se muestra los datos que obtuvimos en la fase 1 mas los datos de la funcion

z-4x1-x2-0H1-0E1=0 y como se puede observar ya no estan las variables artificiales A 1 Y A2.

Para formar la SBF inicial el coeficiente de x1 y x2 en la fila cero deben ser 0.

Variables Variables
originales agregadas
Iteración Ecuación Variables Lado
X1 X2 H1 E1
 Básicas derecho
0 Z -4 -1 0 0 0

1 x1 1 0 0 1/5 3/5
0
2 x2 0 1 0 -3/5 6/5

3 H1 0 0 1 1 1

Para obtener cero en el renglon z de las variables x1 y x2 procedemos a realizar estas operaciones:

Fila 0 ←(fila 0 +4 (fila 1)) y fila 0 ←(fila 0+ fila 2)

Luego de realizar esto obtenemos la siguiente tabla:

Variables Variables
originales agregadas
Iteración Ecuación Variables Lado
X1 X2 H1 E1
Básicas derecho
0 Z 0 0 0 1/5 18/5

1 x1 1 0 0 1/5 3/5
1
2 x2 0 1 0 -3/5 6/5

3 H1 0 0 1 1 1

Columna pivote:

Entra la variable que va entrar seria E 1.

3/5/1/5= 3

6/5/-3/5= no es validad

1/1= 1 → menor sale H1

Aplicamos gauss jordan sobre la variable entrante y obtenemos esta nueva tabla:

Variables Variables
originales agregadas
Iteración Ecuación Variables Lado
X1 X2 H1 E1
 Básicas derecho
0 Z 0 0 -1/5 0 17/5

1 x1 1 0 -1/5 0 2/5
2
2 x2 0 1 3/5 0 9/5

3 E1 0 0 1 1 1

Podemos ver que en el renglon z ya no hay ningun valor positivo por lo tanto ya hemos terminado
de iterar entonces esta seria nuestra solucion basica factible (SBF) optima.

Solucion optima:

Z= 17/5

X1= 2/5

X2= 9/5

[ CITATION Sim13 \l 2058 ]

Ejercicio 2:
Conclusión:

El método de Dos fases, se conforma efectivamente de dos fases, de un modelo de

programa lineal a solucionar por la minimización de la suma de las variables artificiales
encontradas en la normalización del modelo.
Decir de una manera más compacta al momento y resolver el método simplex, incluye dos
fases que describe la pronta solución de unas formas más prácticas y efectivas.
* El método de dos fases, se usa ante la presencia de variables artificiales en el modelo a
solucionar y después eludir el uso de la constante M.
Web-Grafía

Byron Garcia (14/Junio/2013), Metodo de dos Fases

https://prezi.com/9x8khb976yqb/metodo-de-las-dos-fases/

Andrés Eduardo Ortuño Rodríguez (1/Febrero/2012), Metodo De Dos Fases

https://es.slideshare.net/limker/mtodo-de-dos-fases

Canal De Youtube SimplexBorre (22/Febrero/2013)

https://www.youtube.com/watch?v=H6HSW1WcRN8