Asdsad

“Año de la Integración Nacional y el Reconocimiento de Nuestra Diversidad”

Facultad de Ingeniería Y Arquitectura
Escuela Académico Profesional de Ingeniería de Sistemas e Informática
Programación Lineal
Ing. CARLOS HUARHUA
TRABAJO DE INVESTIGACIÓN:
HISTORIA DE LA INVESTIGACIÓN DE OPERACIONES Y DE LA PROGRAMACION LINEAL
INTEGRANTES:
* DELGADO PAJARES , Diego Fabricio
* RAMOSVILCAPOMA , Benji

IV CICLO - 2012

Chosica, 26 de setiembre 2012

INTRODUCCION
El método de dos fases como su mismo nombre lo dice consiste en dos fases, es utilizado de forma alterna al método de la Gran M, consiste en Minimizar el Modelo ,

Definición

¿Porque Usamos El Método de Dos Fases?

Debido al impacto potencial adverso del error de redondeo sobre la exactitud del método M,donde se manipulan en forma simultánea coeficientes grandes y pequeños, el método de dos fases reduce el problema eliminando por completo la constante M. Como su nombre indica, el método resuelve la programación lineal en dos fases: la fase I trata de determinar una solución básica factible de inicio y, si se encuentra, se invoca la fase II para resolver el problema original.

FASE l

Elproblema se pone en forma de ecuación y se agregan a las restricciones las variables artificiales necesarias, para asegurar una solución básica de inicio. A continuación se determina una solución básica de las ecuaciones resultantes, que minimice la suma de las variables artificiales. Si el valor mínimo de la suma es positivo, el problema de programación lineal no tiene solución factible, y termina elproceso (recuerde que una variable artificial positiva significa que no se satisface una restricción original). En caso contrario, se prosigue la fase II.

FASE ll
Se usa la solución factible de la fase I como solución básica factible de inicio para el problema original.

Pasos para resolver con el Método de dos Fases
Fase 1
1) Añadimos una submatriz identidad a la matriz A añadiendo mfilas mediante variables artificiales, o sea, la matriz A queda ahora con las dimensiones (n+m) x m. Esto hace que podamos iniciar el algoritmo.
2) Cambiamos la función objetivo original por una que tiene todo ceros excepto en las últmas m componentes que tienen el valor 1 (es decir, el vector C=(0, .., n-veces ..., 0, 1, .., m-veces ..., 1)
3) Iniciamos el algoritmo con este problema puedendarse estos casos:
3a) Llegamos al caso de solución óptima cero: esto quiere decir que las las variables artificiales han salido de la base, en este caso podemos pasar a la fase 2 del método.
3b) Llegamos al caso de solución óptima finita distinta de cero: El problema original no tiene solución.
3c) Llegamos al caso de restricciones incompatibles: Entonces el problemaoriginal no tiene solución.
3d) Llegamos al caso de solución no acotada: Mismo caso que el anterior, el problema no tiene solución y las restricciones son incompatibles.
Fase 2
Eliminamos las variables artificiales y continuamos el algoritmo, para ello:
1) tomamos la función objetivo original Z
2) Tomamos las m-primeras columnas de la primera matriz
3) Continuamos el algoritmo conestos cambios hasta llegar a una de las 4 posibles salidas del problema.

NOTA
La idea de la fase 1 es eliminar las variables artificiales de la base y obtener la solución trivial para ella
Veremos en esta sección un ejemplo del método de las dos fases y cómo manejar las variables artificiales y de holgura. Un ejemplo aún más completo está aquí.
Ya vimos que todo problema deprogramación lineal puede transformarse en uno de la forma estándar, por ejemplo si tenemos
EJEMPLO:

La Constructora Independent S.A elabora 2 productos en dos máquinas diferentes para ello invierte 2000$ para el mantenimiento de la maquina A y 500$, la empresa busca reducir costos en las maquinas, la maquina 1 utiliza 2 horas para elaborar el producto 1 y 3 horas para el producto 2 , la maquina...