– Monografias.com
Problema I
Dado el programa lineal.
Se ha obtenido como tabla final solución del
Simplex la siguiente
x1 | x2 | x3 | s1 | s2 | Sol | |
Max z | 0 | 2 | 0 | 2 | 1 | 19 |
x1 | 1 | 5 | 0 | 3 | -1 | 1 |
x3 | 0 | -7 | 1 | -5 | 2 | 2 |
Se pide en tal caso describir independientemente para
cada eventualidad las consecuencias producidas, y en su caso la
nueva solución, si ocurre que:
a) (Un punto). Se añade una nueva
restricción de la forma
b) (Un punto). El coeficiente de x3 en la
segunda restricción pasa de valer 3 a valer 4.
c) (Un punto). Se añade una nueva
variable de decisión x4 con coeficientes 2 y 3 en la
primera y segunda restricción respectivamente y con
coeficiente 1 en la función
objetivo.
Solución al problema I
a) La solución x1 = 1, x2 = 0, x3 = 2 no verifica
la nueva restricción (1+0+3.2 = 7 > 4) y por tanto esta
no será redundante. En efecto añadiéndola a
la tabla original, tendremos la tabla
x1 | x2 | x3 | s1 | s2 | s3 | SOL | |
Max z | 0 | 2 | 0 | 2 | 1 | 0 | 19 |
x1 | 1 | 5 | 0 | 3 | -1 | 0 | 1 |
x3 | 0 | -7 | 1 | -5 | 2 | 0 | 2 |
s3 | 1 | 1 | 3 | 0 | 0 | 1 | 4 |
Esta tabla no está dispuesta de acuerdo con los
requisitos del Simplex puesto que dos variables básicas
(x1 y x2) no tienen asociados vectores de la base
canónica, lo cual corregimos restándole a la
última fila la primera y también la segunda
multiplicada por 3. Obtenemos en consecuencia:
x1 | x2 | x3 | s1 | s2 | s3 | SOL | |
Max z | 0 | 2 | 0 | 2 | 1 | 0 | 19 |
x1 | 1 | 5 | 0 | 3 | -1 | 0 | 1 |
x3 | 0 | -7 | 1 | -5 | 2 | 0 | 2 |
s3 | 0 | 17 | 0 | 12 | -5 | 1 | -3 |
Resulta inmediato constatar que la solución es
obviamente sobreoptimal pero no factible (lo que era de esperar
al no ser la nueva restricción redundante con las
previamente establecidas). Por tanto podremos aplicar el
algoritmo dual. Sus reglas de actuación señalan que
el primer pivote a elegir es el señalado en negrita y
cursiva en la tabla anterior. Pivotando obtenemos
x1 | x2 | x3 | s1 | s2 | s3 | SOL | |
Max z | 0 | 27/5 | 0 | 22/5 | 0 | 1/5 | 92/5 |
x1 | 1 | 8/5 | 0 | 3/5 | 0 | -1/5 | 8/5 |
x3 | 0 | -1/5 | 1 | -1/5 | 0 | 2/5 | 4/5 |
s2 | 0 | -17/5 | 0 | -12/5 | 1 | -1/5 | 3/5 |
Solución que resulta ser factible y, en
consecuencia la solución final buscada.
b) Como x3 es una variable básica va a
cambiar la matriz que en nuestra nomenclatura denominamos Ab. En
consecuencia variará su inversa lo que afecta
simultáneamente a la fila de multiplicadores
(optimalidad), a los lados derechos (factibilidad) y al valor de
la solución. Por tanto tendremos:
Para que la nueva solución sea factible
tendrá que verificarse que
Y en efecto no hay cambios en la factibilidad, aunque si
en el valor de la función objetivo como es
natural.
Pero además la fila de multiplicadores
valdrá:
Como son todos positivos permaneceremos en la
optimalidad. En consecuencia la nueva solución
será
x1 = 5/3
x2 = 0
x3 = 2/3
s1 = 0
s2 = 0
z = 55/3
c) Para obtener la nueva variable decisión
tendremos que considerar
y el valor del multiplicador que se obtiene por medio
de
Por tanto, al ser positivo, permanecemos en la
optimalidad y la nueva variable resulta irrelevante.
Problema II
Dado el programa lineal:
Se pide:
a) Determinar su programa dual.
b) Representar este último
gráficamente, una vez efectuado el conveniente cambio de
variable necesario para conseguir que todas las variables de
decisión sean positivas.
c) A la vista de esta representación, y ante
la inexistencia de una solución básica factible
inicial, efectuar las operaciones de pivotado necesarias, que no
tienen por que seguir las reglas del Simplex, para alcanzar la
solución del programa. Señalar en el gráfico
el camino seguido para alcanzar el óptimo.
d) Determinar la solución del programa
original mediante las relaciones de holgura
complementaria.
Solución al problema
II
a) Utilizando las reglas de determinación
del programa dual obtenemos directamente como expresión
del programa dual el siguiente:
En efecto, el problema ha de ser Min pues el primal es
Max; las ecuaciones segunda y tercera son con signo ( pues las
variables asociadas son negativas; mientras que la variable y1 es
negativa porque la restricción asociada lleva el signo ( y
el problema es de Max.
b) Para representar este último
gráficamente y para atenernos a la costumbre de considerar
todas las variables de decisión positivas efectuamos el
cambio de variable y1 = -v1, y, para mantener la homogeneidad en
la escritura, y2 = v2.
Entonces el programa quedará:
La representación gráfica
será:
c) A la vista de esta representación, y ante
la inexistencia de una solución básica factible
inicial, veamos la tabla correspondiente introduciendo las
variables de holgura:
v1 | v2 | s1 | s2 | s3 | s4 | Sol | |
Min w | 1 | -2 | 0 | 0 | 0 | 0 | 0 |
s1 | 1 | 1 | -1 | 0 | 0 | 0 | 10 |
s2 | -1 | 1 | 0 | 1 | 0 | 0 | 4 |
s3 | -1 | 2 | 0 | 0 | 1 | 0 | 14 |
s4 | 2 | -1 | 0 | 0 | 0 | 1 | 8 |
Como resulta evidente la solución no es factible.
Pero si realizamos el trayecto marcado por la flecha horizontal
(que entre en la base v1 y que salga de ella s1) y después
hacemos el ascendente (que entre en la base v2 y que salga de
ella s4) hallaremos la solución. Resulta evidente que
podemos realizar otros muchos trayectos con el mismo resultado.
Así pues, pivotando sucesivamente alrededor de los
elementos marcados en cursiva y negrita, obtenemos:
v1 | v2 | s1 | s2 | s3 | s4 | Sol | |
Min w | 0 | -3 | 1 | 0 | 0 | 0 | -10 |
v1 | 1 | 1 | -1 | 0 | 0 | 0 | 10 |
s2 | 0 | 2 | -1 | 1 | 0 | 0 | 14 |
s3 | 0 | 3 | -1 | 0 | 1 | 0 | 24 |
s4 | 0 | -3 | 2 | 0 | 0 | 1 | -12 |
v1 | v2 | s1 | s2 | s3 | s4 | Sol | |
Min w | 0 | 0 | -1 | 0 | 0 | -1 | 2 |
v1 | 1 | 0 | -1/3 | 0 | 0 | 1/3 | 6 |
s2 | 0 | 0 | 1/3 | 1 | 0 | 2/3 | 6 |
s3 | 0 | 0 | 1 | 0 | 1 | 1 | 12 |
v2 | 0 | 1 | -2/3 | 0 | 0 | -1/3 | 4 |
d) Si h1 y h2 son las holguras del programa
original, entonces se ha de verificar que
Por tanto de las restricciones originales y de lo anterior
deducimos que
Sistema que tiene como solución x1 = x4 = 1,
siendo z = 2.
Problema III
Dado el programa lineal:
Se pide:
a) Resolverlo utilizando el método del
Simplex.
b) Alcanzada la solución, constatar la
existencia de soluciones múltiples mostrando las tablas
representativas de los vértices que las
definen.
c) Escribir una expresión general que resuma
el conjunto de las soluciones.
Solución al
problema III
a) La tabla inicial del simplex, en la que se constata
la existencia de una solución factible básica
inicial es:
x1 | x2 | s1 | s2 | s3 | SOL | |
Max z | 1 | -2 | 0 | 0 | 0 | 0 |
s1 | 1 | 0 | 1 | 0 | 0 | 8 |
s2 | -1 | 1 | 0 | 1 | 0 | 4 |
s3 | -3 | 6 | 0 | 0 | 1 | 42 |
Pivotando según las reglas del simplex alrededor
de los elementos marcados en negrita y cursiva obtenemos
sucesivamente:
x1 | x2 | s1 | s2 | s3 | SOL | |
Max z | -1 | 0 | 0 | 2 | 0 | 8 |
s1 | 1 | 0 | 1 | 0 | 0 | 8 |
x2 | -1 | 1 | 0 | 1 | 0 | 4 |
s3 | 3 | 0 | 0 | -6 | 1 | 18 |
x1 | x2 | s1 | s2 | s3 | SOL | |
Max z | 0 | 0 | 0 | 0 | 1/3 | 14 |
s1 | 0 | 0 | 1 | 2 | -1/3 | 2 |
x2 | 0 | 1 | 0 | -1 | 1/3 | 10 |
x1 | 1 | 0 | 0 | -2 | 1/3 | 6 |
Que es un óptimo.
b) Sin embargo, el multiplicador correspondiente a
la variable no básica s2 es nulo, lo que implica la
existencia de soluciones múltiples. Partiendo de la tabla
anterior
x1 | x2 | s1 | s2 | s3 | SOL | |
Max z | 0 | 0 | 0 | 0 | 1/3 | 14 |
s1 | 0 | 0 | 1 | 2 | -1/3 | 2 |
x2 | 0 | 1 | 0 | -1 | 1/3 | 10 |
x1 | 1 | 0 | 0 | -2 | 1/3 | 6 |
si forzamos la entrada en la base de s2, obtendremos la
nueva tabla solución
x1 | x2 | s1 | s2 | s3 | SOL | |
Max z | 0 | 0 | 0 | 0 | 1/3 | 14 |
s2 | 0 | 0 | 1/2 | 1 | -1/6 | 1 |
x2 | 0 | 1 | 1 | 0 | -1/6 | 11 |
x1 | 1 | 0 | 1 | 0 | 0 | 8 |
Resulta claro que no hay más soluciones factibles
básicas óptimas pues lo único que podemos
hacer a partir de esta solución es forzar la entrada de s1
en la base, lo que trae aparejado la entrada forzosa en ella de
s2 volviendo a obtener la solución original.
c) Las soluciones anteriores son, para un valor de
la función objetivo 14, las
siguientes:
La solución general será de la forma (A +
(1-()B y en consecuencia se expresará como:
Autor:
Iván José Pablo Turmero Astros