Fundamentos del método simplex

INSTITUTO TECNOLOGICO DE MAZATLAN

INVESTIGACION DE OPERACIONES

Programación Lineal

UNIDAD I

CARLOS ABRAHAM MORALES PORTILLO

ING. SISTEMAS COMPUTACIONALES IV

Gilberto Niebla Lizárraga

Fundamentos del método simplex

La mayoría de los problemas realesde programación lineal tienen mas de dos variables y son por ende demasiado grandes para su solución grafica. Un procedimiento llamado método simplex desarrollado en 1947 por el norteamericano George B. Dantzia puede ser utilizado para encontrar la solución óptica de los problemas con multivariables. El Método Simplex es en realidad un algoritmo ( ó un conjunto de instrucciones) con el que seexaminan los puntos vértices (esquinas) de una manera metódica hasta conseguir la mejor solución: la máxima utilidad ó el mínimo costo, por ejemplo.

TIPOS DE SOLUCIÓN:

Solución Factible: Es un valor del conjunto de variables (vector solución) para el cual todas las restricciones se cumplen, incluyendo las de no-negatividad.

Solución Optima: Es una solución factible que optimiza lafunción objetivo “z”.

Solución Básica: En un sistema de ecuaciones con n variables (n , m). Una solución es aquella se obtiene de fijar (n , m) variables del sistema iguales a cero y resolver el sistema en función de las “m” restantes, a estas variables se les llaman Variables Básicas.

Solución Básica Factible: Es aquella solución básica en que todas las variables básicas son no-negativo.TIPOS DE VARIABLES:

Variables de Decisión: Son aquellas variables que determinan la solución del problema y se denotan por Xj.

Variables Base: Son aquellas variables que se agregan al sistema de restricciones como de holgura y artificiales y pertenecen a la columna Vb.

Variables de Holgura: La variable de holgura se denota por Hi y Hj, cuya ecuación es:
1)Al introducirla a larestricción, la convierte en ecuación.
2)Forma parte de la matriz identidad y su costo es cero.
3)En la tabla simplex, en renglón representa el sobrante del recurso y en la
columna representa el sobrante de la contribución.

Variable Artificial: Esta variable se denota por Ai y Aj, cuya función es:

1)Sirve como variable basica inicial, carece de sentido en elproblema, solo en un
artificio.
2)Forma parte de la matriz identidad y su costo es M, tan grande cuando Z se
minimiza y tan pequeña cuando Z se maximiza, para garantizar valore negativos y
positivos, respectivamente
3)Tiene preferencias de entrar a la tabla simplex inicial.

PROPIEDADES:
1)El conjunto de soluciones factibles es un conjunto convexo.
2)Si existe unasolución factible, existirá una solución básica factible,
correspondiente a un punto vértice del conjunto de soluciones factibles (conjunto
convexo).
3)Existe un número finito de soluciones básicas factibles (puntos vértices del
conjunto convexo).
4)Si la función objetivo posee un óptimo finito. Entonces dicho óptimo estará dado
por una ó mas soluciones básicasfactibles.

PROCEDIMIENTO DE CALCULO:

I)Formación del problema (fase I).
II)Construccion del modelo del problema (fase II).
III)Convertir el sistema de restricciones en un sistema de ecuaciones; agregando variables de holgura y artificiales, según sea el tipo de restricción:

| TIPO DE | SE AGREGA | FUNCION OBJETIVO|
|RESTRINCCION | | |
| [pic] | Hi |Max ó Min Z= 0 Hj |
| = | Ai |Max Z = -MAj ó Min...