Metodo simplex

Gestión de Investigación de Operaciones

Profesor: Pedro Peña Carter Ingeniero Comercial UTFSM MBA IEDE ESPAÑA

Departamento de Industrias

Universidad Técnica Federico Santa Maria

Método Simplex
En lo que sigue consideremos el siguiente problema de programación lineal en su forma estándar. Min sa C1 x1 + C2 x2 + ... + Cn xn A11 x1 + A12 x2 + ... + A1n xn = b1 A21 x1 + A22 x2 + ... +A2n xn = b2 ... ... ... Am1 x1 + Am2 x2 + ... + Amn xn = bm xi  0, i = 1, 2, ..., n
Departamento de Industrias

y

mn
Universidad Técnica Federico Santa Maria

Método Simplex
Matricialmente escrito como:

Min cTx s.a. A x = b x0
No existe pérdida de la generalidad al suponer que un problema viene dado en la forma estándar. En efecto, si tuviésemos el siguiente problema:Departamento de Industrias Universidad Técnica Federico Santa Maria

Método Simplex
P) Max s.a. 9X1 + 2X2 + 5X3 4X1 + 3X2 + 6X3  50 X1 + 2X2 - 3X3  8 2X1 – 4X2 + X3 = 5 X1 , X2 , X3  0

Es posible reformular de manera equivalente el problema anterior usando que:
Departamento de Industrias Universidad Técnica Federico Santa Maria

Método Simplex
Siempre es posible llevar un problema demaximización a uno de minimización. Cada restricción del tipo



puede ser llevada a una

ecuación de igualdad usando una (nueva) variable de

holgura no negativa, con un coeficiente nulo en la función
objetivo. De igual modo, cada restricción del tipo  puede ser llevada a una ecuación de igualdad usando una (nueva) variable de exceso no negativa. En el caso de igualdades asumir variable librepositiva.

Departamento de Industrias

Universidad Técnica Federico Santa Maria

Método Simplex
El problema P) puede ser escrito de manera equivalente como (Formato Estándar): Min - 9x1 - 2x2 - 5x3 + 0S4 + 0S5 + 0S6 sa: 4x1 + 3x2 + 6x3 +S4 = 50 x1 + 2x2 - 3x3 + S5 = 8 2x1 - 4x2 + x3 +S6 = 5 xi  0,
Departamento de Industrias

i=1,2,3,4,5,6.
Universidad Técnica Federico Santa MariaMétodo Simplex
La búsqueda de la solución óptima se restringe a encontrar un vértice óptimo. Cada vértice del conjunto de las restricciones del problema, esto es del conjunto

{ x / A x = b, x  0 }, corresponde en
términos algebraicos a una solución básica factible del sistema Ax = b.
Departamento de Industrias Universidad Técnica Federico Santa Maria

Método Simplex
Esta solución básicafactible, corresponde a su vez a aquellas soluciones que resultan de resolver el sistema para exactamente m variables, fijando las restantes n - m en cero, llamadas respectivamente variables básicas y no-básicas, que además deben satisfacer condiciones de no-negatividad.
Departamento de Industrias Universidad Técnica Federico Santa Maria

Método Simplex
Teorema Fundamental de la ProgramaciónLineal:
Cada problema de PL en su forma estándar cumple con las siguientes tres propiedades: Si el problema no tiene solución óptima entonces es no-acotado o infactible. Si tiene una solución factible, tiene una solución básica factible. Si el problema tiene solución óptima, tiene una solución básica factible óptima.
Departamento de Industrias Universidad Técnica Federico Santa Maria

MétodoSimplex
En lo que sigue suponemos que Ran(A) = m y que por lo tanto existe una matriz invertible B de m x m, que sin pérdida de la generalidad asumimos corresponde a aquella que definen las m primeras columnas de A Lo anterior induce una partición de las variables y parámetros del modelo como lo muestra la siguiente diapositiva:
Departamento de Industrias Universidad Técnica Federico Santa Marian

Método Simplex
XB : Variables básicas. XD : Variables no básicas. CB : Costos básicos. CD : Costos no básicos.

A= B
m
X1

D
n-m
XB
m

m

B : Es llamada una matriz de base

CB

m

X=
Xn

=
XD
n-m

C=
CD
n-m

Método Simplex
De este modo, el sistema AX = b equivale a:

BxB  D xD  b BxB  b  D xD xB  B b  B D xD
Donde esta última expresión da el...