Programacion Lineal

APUNTES Y PROBLEMAS DE INVESTIGACION OPERATIVA

1. PROGRAMACIÓN LINEAL
Representación de modelos de programación lineal:

a). Forma condensada
c). Forma Canónica

b). Forma matriciald). Forma Estándar




1.1 Ejemplo 1 (Rafael Terrazas)

Las tablas del método simplex serán:

Iteración 0 :
Z x1 x2 s1 s2 s3 L.S. 
z 1 -3 -5 0 0 0 0
s1
0 1 0 1 0 0 4 
s2
0 02 0 1 0 12 6
s3 0 3 2 0 0 1 18 9

Iteración 1 :
Z x1 x2 s1 s2 s3 L.S. 
z 1 -3 0 0 5/2 0 -30
s1 0 1 0 1 0 0 4 4
x2
0 0 1 0 1/2 0 6 
s3 0 3 0 0 -1 1 6 2


Iteración 2 :
Z x1 x2 s1s2 s3 L.S. 
z 1 0 0 0 3/2 1 36
s1 0 0 0 1 1/3 -1/3 2 4
x2 0 0 1 0 1/2 0 6 
x1 0 1 0 0 -1/3 1/3 2 2



1.2 Ejemplo 2: (Rafael Terrazas)- archivo “io-1.doc”
Dado el siguiente problema:Max Z = 7x1 + 14x2 + 6x3 + 10x4 - 3x5
S.A.
x5  4000
3x2 + 2x4 + x5  6000
x1 + x2 - 3x5 = 0
x3 + x4 - 4x5 = 0
x1, x2, x3, x4, x5  0

Resolver por el método Simplex
Paso 1: Llevar el problemaa la forma estándar:
Al tratarse de dos restricciones de igualdad se añade a cada una variable artificial (S1 y S2) (Taha p 84, ver también Gould p 221)
Max Z = 7x1 + 14x2 + 6x3 + 10x4 - 3x5 + 0x6+ 0x7 - Ms1 - Ms2
S.A.
x5 + x6 = 4000 (R1)
3x2 + 2x4 + x5 + x7 = 6000 (R2)
x1 + x2 - 3x5 +s1 = 0 (R3)
x3 + x4 - 4x5+s2 = 0 (R4)
x1, x2, x3, x4, x5, x6, x7, s1, s2  0

Paso 2: Obtener la tabla Simplex inicial (llevando a la forma Max Z-cx =0)
entonces la función objetivo será:Max Z - 7x1 - 14x2 - 6x3 - 10x4 + 3x5 - 0x6 - 0x7 + Ms1 + Ms2
Hacer operaciones si es necesario en la función objetivo si se da el caso de que se tengan menos variables básicas que el número derestricciones. (Terrazas p. 36). obteniendo los vectores de los coeficientes tanto de la función objetivo como de las restricciones, procurando que las variables básicas iniciales sean las artificiales,...