Universidad Tecnológica de Pereira – Colombia
Posgrado en Ingeniería – Maestría/Doctorado
Programación Lineal Entera
Antonio H. Escobar Z.
2013
En el problema Dual simplex canalizado se deben tener en cuenta las siguientes
consideraciones:
1. Una variable básica asume normalmente un valor entre su límite inferior y su
límite superior.
2. Una variable no básica se encuentra en su límite inferior o se encuentra en su
límite superior. Se definen dos subconjuntos de índices de variables no
básicas:
Condiciones iniciales que debe cumplir el cuadro:
óptimo
-
Un límite violado
óptimo
R1
R2
+
Cuadro inicial con estilo Garfinkel:
Caso 1:
La variable no básica
que entra a la base
debe disminuir su valor
+
Por ejemplo, en el cuadro óptimo actual la variable básica tiene el valor
y se adiciona la restricción:
En este caso, para el nuevo problema,
tiene su límite superior violado.
= 2.75
variable no básica
que entra a la base y
debe disminuir su valor
Forma general de
las variables básicas
Nuevo valor de las
variables básicas
Cambio en las
variables básicas
-
+
variable básica que
sale de la base
La variable no básica
que entra a la base
debe disminuir su valor
variables básicas que
continúan en la base
variables básicas que
continúan en la base
+
Costos relativos
de las variables
no básicas que
están en R2
+
-
Para que el cuadro sea óptimo
los coeficientes de costo
reducido deben ser positivos si
las variables no básicas están
en el LS (R2)
Para que el cuadro sea óptimo
los coeficientes de costo
reducido deben ser positivos si
las variables no básicas están
en el LS (R2)
+
-
-
Garantiza que el cuadro
continua siendo óptimo
Caso 2:
La variable no básica
que entra a la base
debe aumentar su valor
+
Forma general de
las variables básicas
Nuevo valor de las
variables básicas
Cambio en las
variables básicas
+
+
variable básica que
sale de la base
Cambio en la variable no básica
que entra a la base
La variable no básica
que entra a la base
aumenta su valor
variables básicas que
continúan en la base
variables básicas que
continúan en la base
+
+
+
En general:
+
+
-
-
+
+
Caso 3:
La variable no básica
que entra a la base
debe disminuir su valor
+
Por ejemplo, en el cuadro óptimo actual la variable básica tiene el valor
y se adiciona la restricción:
En este caso, para el nuevo problema,
tiene su límite inferior violado.
= 2.75
variable básica que
sale de la base y
debe aumentar su valor
Cambio en la variable no básica
que entra a la base
La variable no básica
que entra a la base
disminuye su valor
variables básicas que
continúan en la base
variables básicas que
continúan en la base
Caso 4:
variable básica que
sale de la base y
debe aumentar su valor
Cambio en la variable no básica
que entra a la base
La variable no básica
que entra a la base
aumenta su valor
variables básicas que
continúan en la base
variables básicas que
continúan en la base
Cuadro
óptimo
En el cuadro óptimo actual la variable básica
= 2.75
y se adiciona la restricción:
En este caso, para el nuevo problema,
tiene su límite superior violado.
Las variables no básicas
se encuentran en su
límite inferior
La variable básica
viola su límite superior
La variable no básica
x5 que entra a la base
aumenta de valor desde
su límite inferior
La variable básica
x1 sale de la base y
pasa a ser no básica
en su límite superior
El cuadro primal es óptimo pero infactible (dual factible y no óptimo)
primal óptimo
primal infactible
La variable básica
viola su límite inferior
x1
x3
La variable no básica
x3 que entra a la base
aumenta de valor desde
su límite inferior
La variable básica
x4 sale de la base y
pasa a ser no básica
en su límite inferior
primal óptimo
primal factible
El cuadro primal es óptimo y factible
Descargar

PLE clase: Dual Simplex Canalizado, Pos