iontroduccion al I. D. O.

CUARTO SEMESTRE















Contenido





2.1 TEORÍA DEL MÉTODO SIMPLEX

El método Simplex es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución.
Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamenteotro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono . Cómo el número de vértices es finito, siempre se podrá encontrar la solución.
El método Simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.
Deberá tenerse encuenta que este método sólo trabaja para restricciones que tengan un tipo de desigualdad "≤" y coeficientes independientes mayores o iguales a 0, y habrá que estandarizar las mismas para el algoritmo. En caso de que después de éste proceso, aparezcan (o no varíen) restricciones del tipo "≥" o "=" habrá que emplear otros métodos, siendo el más común el método de las Dos Fases.

Lo común es que estealgoritmo se trabaje en una computadora que solo pueda seguir instrucciones algebraicas. Por lo tanto es necesario traducir el procedimiento geométrico conceptual que se acaba de describir en un procedimiento algebraico que se pueda usar. El procedimiento algebraico se basa en resolver sistemas de ecuaciones. Entonces el primer paso para preparar el método Simplex es convertir las restriccionesfuncionales de desigualdad en restricciones de igualdad equivalentes. (Las restricciones de no negatividad se dejan como desigualdades porque se manejan por separado). La conversión en igualdades se logra con la introducción de variables de holgura.
El método Simplex es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguirmejorando más dicha solución.
Partiendo del valor de la función objetivo en un vértice cualquiera, el método consiste en buscar sucesivamente otro vértice que mejore al anterior. La búsqueda se hace siempre a través de los lados del polígono (o de las aristas del poliedro, si el número de variables es mayor). Cómo el número de vértices (y de aristas) es finito, siempre se podrá encontrar la solución.El método Simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta.
Deberá tenerse en cuenta que este método sólo trabaja para restricciones que tengan un tipo de desigualdad "≤" y coeficientes independientes mayores o iguales a 0, y habrá que estandarizar las mismas parael algoritmo. En caso de que después de éste proceso, aparezcan (o no varíen) restricciones del tipo "≥" o "=" habrá que emplear otros métodos, siendo el más común el método de las Dos Fases
2.2 FORMA TABULAR DEL MÉTODO SIMPLEX

Este método busca la solución, en cada paso, de forma mejorada hasta que no pueda seguir mejorando dicha solución. Al comienzo el vértice principal es un vérticecualquiera, hasta que va mejorando, comparándolo con el vértice anterior, en los pasos de la ecuación.
El método Simplex se basa en la siguiente propiedad: si la función objetivo, f, no toma su valor máximo en el vértice A, entonces hay una arista que parte de A, a lo largo de la cual f aumenta. Deberá tenerse en cuenta que este método sólo trabaja para restricciones que tengan un tipo dedesigualdad "≤" y coeficientes independientes mayores o iguales a 0, y habrá que estandarizar las mismas para el algoritmo. En caso de que después de éste proceso, aparezcan (o no varíen) restricciones del tipo "≥" o "=" habrá que emplear otros métodos, siendo el más común el método de las Dos Fases.
Pasos para formular un método simplex

Paso 1 Convertir el LP a suma forma estándar.
Paso 2...