Investigacion Operativa

Trabajo 3




Fecha: 29 / 06 / 2012Integrantes: Javier Albornoz
Enrique Keim
Profesor: Jorge MelladoÍndice

Resumen ejecutivo………………………………………………………………3
Introducción………………………………………………………………………3
Capítulos de contenido metodológico…………………………………………4
Método Dual simplex………………………………………………………..4Ejemplo y método simplex…………………………………………………..6
Conclusión………………………………………………………………………..11
Anexo……………………………………………………………………………..11
Referencias………………………………………………………………………12
Tabla de Control…………………………………………………………………12

Resumen ejecutivo
En este trabajo definiremos el método dual simplex como tal. Pondremos en practica el método dual simplex en un ejemplo para poder obtener las solucionesrespectivas al ejemplo y compararemos el método dual simplex con el método normal simplex y evaluaremos sus diferencias y alcances.

Introducción
En este trabajo utilizaremos el método dual simplex , utilizando sus propiedades para
encontrar solución o conjuntos soluciones junto con sus restricciones considerando que la
función objetivo puede estar en la forma de maximización ominimización.
Después de agregar las variables de holgura y de poner el problema en la tabla, si
algún elemento de la parte derecha es negativo y si la condición de optimidad está
satisfecha, el problema puede resolverse por el método dual simplex. Note que un
elemento negativo en el lado derecho significa que el problema comienza óptimo
pero infactible como se requiere en el método dualsimplex. En la iteración donde
la solución básica llega a ser factible esta será la solución óptima del problema.

Capítulos de contenido:

El método dual simplex
Como sabemos, el método simplex es un algoritmo iterativo que iniciando en una solución básica factible pero no óptima, genera soluciones básicas factibles cada vez mejores hasta encontrar la solución óptima (sí esta existe). Nóteseque la base de su lógica es mantener la factibilidad, mientras busca la optimalidad. Pero surge la posibilidad de usar otro esquema igualmente iterativo, que como contraparte del simplex, comienza en una solución básica óptima, pero no factible y mantiene la inmejorabilidad mientras busca la factibilidad. Con este procedimiento se llega igualmente a la solución óptima.
El nuevo algoritmo fuedesarrollo en 1954 por C. E. Lemke y se conoce con el nombre de Método Dual-Simplex. A continuación se presenta su estructura y un ejemplo para ilustrar su aplicación.
 
Algoritmo Dual-Simplex para un modelo de maximización
Primero se debe expresar el modelo en formato estándar, agregando las variables de holgura y de exceso que se requieran.
Enseguida, en las ecuaciones que tengan variables deexceso (resultantes de restricciones de tipo >), se debe multiplicar por (-1) en ambos lados , para hacer positivo el coeficiente de la variable de exceso, y formar así un vector unitario que nos permita tomar esta variable de exceso como una variable básica inicial. sin necesidad de agregar una variable artificial en esa restricción.

Al hacer lo anterior se logra que debajo de las variables...