Simplex

UNIVERSIDAD CARLOS III DEPARTAMENTO DE
FACULTAD DE CIENCIAS ESTADÍSTICA Y SOCIALES Y POLÍTICAS ECONOMETRÍA












DIPLOMATURA DE ESTADÍSTICA
2º CURSO - INVESTIGACIÓN OPERATIVA I

EXAMEN DE 7 DE FEBRERO DE 2004


ENUNCIADO DE LOS PROBLEMAS















Prof. José Carlos Ayuso Elvira
UNIVERSIDAD CARLOS III DEPARTAMENTO DE
FACULTAD DE CIENCIASESTADÍSTICA Y SOCIALES Y POLÍTICAS ECONOMETRÍA












DIPLOMATURA DE ESTADÍSTICA
2º CURSO - INVESTIGACIÓN OPERATIVA I

EXAMEN DE 7 DE FEBRERO DE 2004


SOLUCIÓN DE LOS PROBLEMAS















Prof. José Carlos Ayuso Elvira
EXAMEN DE PROGRAMACIÓN LINEAL

FEBRERO DE 2004



PROBLEMA I .- Dado el programa lineal


Se ha obtenido como tabla finalsolució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

x1 + x2 + 3x3  4

b) (Un punto). El coeficiente de x3 en la segundarestricció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 efectoañ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 segundamultiplicada 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 deactuació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 acambiar 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 lafactibilidad, 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 considerary 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.

EXAMEN DE PROGRAMACIÓN LINEAL

FEBRERO DE 2004



PROBLEMA II.- Dado el programa lineal:

Max z = 10x1 + 4x2 + 14x3 - 8x4
s.a. - x1 + x2 + x3 + 2x4  1
x1 + x2 + 2x3 + x4  2
x1...