APLICACIONES Y ALGORITMOS CAPITULO 4
Enviado por Maria Lesiw • 17 de Abril de 2018 • Trabajos • 3.215 Palabras (13 Páginas) • 126 Visitas
INVESTIGACION DE OPERACIONES
APLICACIONES Y ALGORITMOS
CAPITULO 4
Wayne L. Winston
Capítulo 4
Introducción al Algoritmo Simplex
4.1 PL en la forma estándar : SISTEMA DE ECUACIONES
Se agregan variables de holgura y exceso para transformar en la forma estándar
INECUACIONES --------------⬄ ECUACIONES
Max / Min Z = c1 x1 + c2 x2 + c3 x3 + .... + cn xn
s.a
a11 x1 + a12 x2 + a13 x3 + .... + a1n xn = b1
a21 x1 + a22 x2 + a23 x3 + .... + a2n xn = b2
a31 x1 + a32 x2 + a33 x3 + .... + a3n xn = b3
.
.
.
am1 x1 + am2 x2 + am3 x3 + .... + amn xn = bn
C = c1 c2 c3 .........cn
A=
.
a11 . ... a12 a13 .. a1n
a21 ..... a22. .. a23 ....... a2n
a31 ..... a32. ... a33. ...... a3n
.
.
am1. ...am2 ..am3 ....... amn .
X=
X1
X2
X3
.
.
Xn
b=
b1
b2
b3
.
.
bm
Definición
Como son no iguales las cantidades de variables y ecuaciones existentes es necesario obtener un sistema de ecuaciones lineales con solución única
Solución Básica A x = b haciendo (n – m ) variables = 0
Variables Básicas (VB)
Variables NO Básicas (VNB)
SOLUCIÓN FACTIBLE : Es una solución donde todas las VB son no negativas
En cualquier problema de PROGRAMACION LINEAL la región factible es un conjunto convexo. Si un PL tiene una SOLUCIÓN ÓPTIMA , TENDRÁ QUE EXISTIR UN PUNTO EXTREMO DE LA REGION FACTIBLE QUE ES ÓPTIMO
Para cualquier PL, existe un punto extremo único de la región factible del PL que corresponde a cada solución básica factible . También existe por lo menos una SOLUCION BASICA FACTIBLE (sbf) que corresponde a cada punto extremo de la región factible
Max z = 4 x1 + 3 x2
s.a.
x1 + x2 <= 40
2x1 + x2 <= 60
x1, x2 =>0
Llevando a ecuaciones :
Max z = 4 x1 + 3 x2
s.a.
x1 + x2 + s1 = 40
2x1 + x2 + s2 = 60
Calculo de los valores de las variables [pic 1]
X1 | x2 | s1 | s2 | Ld | MINVERSA | MMULT = b | ||||
1 | 1 | 1 | 0 | 40 | 0 | 0 | 1 | 0 | 0 | |
2 | 1 | 0 | 1 | 60 | 0 | 0 | 0 | 1 | 0 | |
1 | 0 | 0 | 0 | 0 | 1 | 0 | -1 | -1 | 40 | |
0 | 1 | 0 | 0 | 0 | 0 | 1 | -2 | -1 | 60 |
1 | 1 | 1 | 0 | 40 | 0 | 0 | 1 | 0 | 0 |
2 | 1 | 0 | 1 | 60 | 1 | 0 | -1 | -1 | 40 |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
0 | 0 | 1 | 0 | 0 | -1 | 1 | -1 | 1 | 20 |
1 | 1 | 1 | 0 | 40 | 0 | 0 | 1 | 0 | 0 |
2 | 1 | 0 | 1 | 60 | 0 | 1 | -2 | -1 | 60 |
1 | 0 | 0 | 0 | 0 | 1 | -1 | 1 | 1 | -20 |
0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
1 | 1 | 1 | 0 | 40 | 1 | 0 | -1 | -1 | 40 |
2 | 1 | 0 | 1 | 60 | 0 | 0 | 1 | 0 | 0 |
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
0 | 0 | 1 | 0 | 0 | -2 | 1 | 1 | 2 | -20 |
1 | 1 | 1 | 0 | 40 | 0 | 0,5 | -0,5 | -0,5 | 30 |
2 | 1 | 0 | 1 | 60 | 0 | 0 | 1 | 0 | 0 |
0 | 1 | 0 | 0 | 0 | 1 | -0,5 | -0,5 | 0,5 | 10 |
0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
1 | 1 | 1 | 0 | 40 | -1 | 1 | 1 | -1 | 20 |
2 | 1 | 0 | 1 | 60 | 2 | -1 | -2 | 1 | 20 |
0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
Para cualquier PL con m restricciones se dice que dos soluciones factibles son adyacentes si sus conjuntos de variables básicas tienen m – 1 variables básicas comunes
Si un PL en la forma estándar tiene m ecuaciones y n variables , se deben construir :
...