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