Problemas Clase 5

Problema 1: Póngase en forma estándar el siguiente programa:
MAXIMIZAR Z = X1 + X2
Sujeto a: X1 + 5X2 ≤ 5
2X1 + X2 ≤ 4
X1 , X2 ≥ 0
Agregando las variables de holgura X3 y X4, respectivamente, a los lados izquierdos de las restricciones e incluyendo en el objetivo estas nuevas variables con coeficientes de costo cero, se tiene:

MAXIMIZAR Z = X1 + X2 + 0X3 + 0X4
Sujeto a: X1 + 5X2 + X3 =5
2X1 + X2 + X4 = 4
X1 , X2 , X3 , X4 ≥ 0
Ya que cada ecuación de restricción contiene una variable de holgura, no se necesitan variables artificiales; una solución factible inicial es X3 = 5, X4 = 4, X1 = X2 = 0.































Problema 2: Exprese el siguiente problema de PL en forma estándar y encuentre su solución:
MAXIMIZAR P = 6X1 + 7X2
Sujeto a: 2X1 + 3X2 ≤ 24
2X1 +X2 ≤ 16
X1 , X2 ≥ 0
El primer paso del procedimiento es convertir las desigualdades en igualdades. Esto se hace agregando dos nuevas variables, X3 y X4, llamadas variables de holgura. Las variables de holgura representan la capacidad no utilizada en las respectivas restricciones. Así X3 es el número de horas de capacidad de la máquina 1 que no se usan y X4 es el número de horas no utilizadas dela máquina 2. Siempre es posible convertir desigualdades en igualdades puesto que debe haber alguna cantidad de capacidad no utilizada (X3) que, cuando se agrega a (2X1 + 3X2) será igual a 24 (X3 debe ser mayor o igual a cero).

Las restricciones del problema pueden escribirse como:
2X1 + 3X2 + X3 = 24
2X1 + X2 + X4 = 16
X1 , X2 , X3 , X4 ≥ 0
La función objetivo se convierte en:
MAXIMIZAR P= 6X1 + 7X2 + 0X3 + 0X4
Las variables de holgura no producen utilidad, por lo que sus coeficientes en las ecuaciones de utilidad son cero.

Cualquier valor de X1 , X2 , X3 y X4 que satisfagan las ecuaciones de restricción son soluciones factibles del problema de programación lineal. En la siguiente figura se muestran todas las soluciones factibles del problema (referida a las variables dedecisión únicamente):

En el problema general de programación lineal, hay m ecuaciones de restricción. Después de agregar las variables de holgura, hay más de m variables. Por los cursos de álgebra se sabe que puede hallarse la solución única de un grupo de m ecuaciones lineales, si hay exactamente m variables. Pero con más de m variables, como en el caso de la programación lineal, no hay una soluciónúnica.
Sin embargo, supóngase que arbitrariamente se eligen m variables cualesquiera y el resto se igualan a cero, entonces se resuelven las m ecuaciones para las m variables elegidas para obtener la solución. Dicha solución se llama solución básica. Las variables elegidas reciben el nombre de variables básicas y en su conjunto se denominan la base. El resto de las variables (igualadas a cero) son lasvariables no básicas.

En este ejemplo hay 4 variables desconocidas y 2 ecuaciones de restricción. Para encontrar la solución básica, se eligen dos variables cualesquiera y las restantes se igualan a cero.

Supóngase que arbitrariamente se eligen X1 y X3 como variables básicas y en consecuencia se hacen X2 = X4 = 0. Las ecuaciones resultantes son:

2X1 + 3(0) + X3 = 24 ; 2X1 + X3 = 24
2X1 + 1(0)+ 1(0) = 16 ; 2X1 = 16
La solución es X1 = 8, X3 = 8, X2 = X4 = 0. Esta es una solución básica del problema de programación lineal. El resto e las soluciones básicas se calculan de manera similar, tomando en cuenta que deben ser:

soluciones básicas factibles.
La siguiente tabla muestra todas las soluciones básicas:

Variables no básicas
(igualadas a cero)
Variables básicas
Utilidad
Marca en
lafigura
X1 y X2
X3 = 24
X4 = 16
0
A
X1 y X3
X2 = 8
X4 = 8
56
E
X1 y X4
X2 = 16
X3 = -24
No factible
F
X2 y X3
X1 = 12
X4 = -8
No factible
B
X2 y X4
X1 = 8
X3 = 8
48
C
X3 y X4
X1 = 6
X2 = 4
64
D

Nótese que algunas soluciones tienen valores negativos en algunas de las variables. Esta solución básica es no factible, puesto que el problema de programación lineal no permite valores negativos para...