programacion lineal

PROGRAMACIÓN LINEAL







FABIAN LEANDRO ROJAS DUEÑAS
CC.74377018








UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
INGENIERIA INDUSTRIAL
MAYO 2012METODO DUAL



Este método se aplica a problemas óptimos pero infactibles. En este caso, las restricciones se expresan en forma canónica.
La función objetivo puede estar en la forma de maximizacióno de minimizació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, elproblema puede resolverse por el método dual simplex.

Función objetivo
Min. Z = 4X1 + 12X2 + 18X3
Sujeto a: X1 + 3X3 ≥ 3
2X2 + 2X3 ≥ 5X1, X2, X3 ≥ 0

Para convertir el problema de minimización en maximización se multiplica por -1 la función objetivo

Luego multiplicamos las restricciones por -1y así quedan negativas pero también cambia el ≥ y ahora queda ≤

- X1 - 3X3 ≤ -3
- 2X2 - 2X3 ≤ -5
X1, X2, X3 ≥ 0



Convertimos las inecuaciones en ecuaciones


Z + 4X1 + 12X2+ 18X3 = 0
- X1 - 3X3 + S1 = -3
– 2X2 - 2X3 + S2 = -5

Elaboramos la tabla

X1
X2
X3
S1
S2
solucion
S1 -1
0
-3
1
0
-3
S2 0
-2
-2
0
1
-5
Z 4
12
18
00
0


Z 4
12
18
0
0
0
P 0
-2
-2
0
1
-5
Resultado -
-6
-9
-
0
0

Halamos o seleccionamos la variable que sale la fila pivote es la variable saliente menor en este casoes la fila del -5
luego hallamos el valor entrante para esto dividimos la fila de z para así hallar los coeficientes de la fila pivote se divide la fila del z con la fila -5 así hallamos elotro coeficiente:
4/0= -, 12/-2=-6, 18/-2=-9, 0/0=-, 0/1=-, 0/-5=0,
así escogemos la columna menos negativa y es la columna que va entrar.

Luego de la primera tabla construimos otra tabla...