Solución de problemas de programación lineal

Método Gráfico
El método grafico es una forma de resolver problemas de programación lineal con 2 (o a lo mucho 3)
variables de decisión.

Supongamos que tenemos el siguiente problema de programación lineal (en forma matricial compacta)

max 𝑍 = 𝑐𝑇𝑥
𝑥
sujeto a 𝐴𝑥 ≤ 𝑏
𝑥≥0
El método consiste en lo siguiente:

1. Graficar todas las restricciones del problema 𝐴𝑥 ≤ 𝑏 y de no negatividad 𝑥 ≥ 0.

2. Identificar la región factible del problema.
3. Graficar la función objetivo sustituyendo 𝑍 = 0, es decir, graficar 𝑐 𝑇 𝑥 = 0.
4. Graficar el gradiente de la función objetivo 𝑐.
5. Mover la función objetivo de forma paralela en dirección del gradiente.
6. El último punto de la región factible que toque la función objetivo es el óptimo (o los óptimos)
del problema.

Nota: Si el problema es de minimización, entonces, hay que mover la función objetivo en la dirección
opuesta al gradiente.

Ejemplo:

Graficar la región factible, la Mover la función objetivo de El último punto de la región

función objetivo y su forma paralela en dirección factible que toque la función
gradiente. del gradiente. objetivo es el óptimo, en
este caso, el punto (2,6).

Ver metodo_grafico.ggb
Método Simplex
El método simplex es un algoritmo iterativo para resolver problemas de programación lineal con la
siguiente estructura:

- Todas las restricciones del problema (exceptuando las restricciones de no negatividad) son de
menor o igual.
- Todas las restricciones del problema (exceptuando las restricciones de no negatividad) tienen
lados derechos no negativos.
- Todas las variables de decisión tienen la restricción de no negatividad.
- La región factible cumple una propiedad de regularidad (por ejemplo, no hay restricciones
redundantes, entre otras propiedades más complejas).

De las condiciones anteriores, la única que no es necesario comprobar es la última ya que es muy difícil,
sin embargo, si no se cumple esta condición, el método simplex puede entrar en un bucle.

Algoritmo del método simplex

Consideremos el siguiente problema de programación lineal:

max 3𝑥1 + 5𝑥2
𝑥1 ,𝑥2
sujeto a 𝑥1 ≤ 4
2𝑥2 ≤ 12 (1)
3𝑥1 + 2𝑥2 ≤ 18
𝑥1 , 𝑥2 ≥ 0
Pasos iniciales del método simplex:

a. Escribir el problema de programación lineal en su forma estándar (maximización) y verificar que

cumpla con la estructura mencionada antes.
El problema (1) ya se encuentra en forma estándar para maximización y podemos comprobar
que todas las restricciones son de menor o igual con lados derechos no negativos y cada variable
tiene restricción de no negatividad. En este caso, sólo vamos a igualar la función objetivo a 𝑍 y
alinear las variables para visualizar mejor los siguientes pasos

max 𝑍 = 3𝑥1 + 5𝑥2

𝑥1 ,𝑥2
sujeto a 𝑥1 ≤ 4
2𝑥2 ≤ 12 (2)
3𝑥1 + 2𝑥2 ≤ 18
𝑥1 , 𝑥2 ≥ 0
b. Escribir la forma aumentada del problema.
En este paso debemos sumar una nueva variable no negativa a cada una de las restricciones
para convertirlas en igualdades, además de igualar la función objetivo a cero, dejando el
coeficiente de 𝑍 positivo. En este caso el problema (2) queda de la siguiente manera
 max 𝑍 − 3𝑥1 − 5𝑥2 = 0
𝑥1 ,𝑥2 ,𝑥3 ,𝑥4 ,𝑥5
sujeto a 𝑥1 + 𝑥3 = 4
2𝑥2 + 𝑥4 = 12 (3)
3𝑥1 + 2𝑥2 + 𝑥5
= 18
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0
Las variables introducidas para convertir las restricciones de menor o igual por restricciones de
igualdad (en este caso 𝑥3 , 𝑥4 , y 𝑥5 ) se llaman variables de holgura y una solución (no
necesariamente óptima o factible) para el problema (3) se llama solución aumentada.
c. Escribir la tabla del método simplex.
Ahora que tenemos sólo restricciones de igualdad (exceptuando las restricciones de no
negatividad) debemos vaciar las igualdades en una tabla de la siguiente manera (esto es análogo
a escribir la matriz aumentada de un sistema de ecuaciones lineales)
𝑉𝐵 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝐿𝐷
𝑍 −3 −5 0 0 0 0
𝑥3 1 0 1 0 0 4
𝑥4 0 2 0 1 0 12
𝑥5 3 2 0 0 1 18
o La primera fila representa las etiquetas de las columnas (𝑉𝐵 significa variables básicas y
𝐿𝐷 significa lados derechos), mientras que el resto de las filas corresponden a cada una
de las igualdades del problema en la forma aumentada (3).
o La primera columna representa las variables básicas, las cuales son la variable 𝑍 de la
función objetivo junto con las variables que forman la base canónica para el conjunto de
soluciones aumentadas, en este caso 𝑥3 , 𝑥4 , y 𝑥5 .
o El resto de las variables se llaman variables no básicas. En este caso 𝑥1 y 𝑥2 .
o Cada variable básica está relacionada con una de las igualdades. En este caso, 𝑍 está
relacionada con la función objetivo, mientras que 𝑥3 , 𝑥4 , y 𝑥5 , están relacionadas con
cada una de las restricciones en las que fueron introducidas como variables de holgura.
o Las columnas de en medio son los coeficientes de las variables como aparecen en las
igualdades del problema (3).
o La última coluna corresponde a los lados derechos de las igualdades del problema (3).
o La tabla anterior siempre genera una solución aumentada que cae en un vértice de la
región factible para el problema (3), llamada solución básica.
o Para la solución básica, los valores de las variables básicas están dado por el valor
correspondiente en la columna de lados derechos, mientras que las variables no básicas
toman el valor de cero. En este caso, la solución básica dada por la tabla anterior es
(𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ) = (0,0,4,12,18) con un valor para la función objetivo de 𝑍 = 0.
Pasos iterativos:

1. Prueba de optimalidad: Si los coeficientes de las variables en la fila de la función objetivo tienen
valores no negativos, la tabla genera una solución básica óptima y termia el algoritmo.
En la tabla del problema (3)
𝑉𝐵 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝐿𝐷
𝑍 −3 −5 0 0 0 0
𝑥3 1 0 1 0 0 4
𝑥4 0 2 0 1 0 12
𝑥5 3 2 0 0 1 18
vemos que esta no genera una solución óptima ya que las variables 𝑥1 y 𝑥2 tienen coeficientes
negativos en la función objetivo, por lo que seguimos con el siguiente paso.
2. Variable de entrada: En este paso vamos a seleccionar la variable que tenga el coeficiente más
pequeño en la función objetivo para entrar como nueva variable básica. Esta variable siempre
será no básica.
En la tabla del problema (3) vemos que la variable de entrada es 𝑥2
𝑉𝐵 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝐿𝐷
𝑍 −3 −5 0 0 0 0
𝑥3 1 0 1 0 0 4
𝑥4 0 2 0 1 0 12
𝑥5 3 2 0 0 1 18

3. Prueba del cociente mínimo: Para cada una de las filas de las restricciones que tengan un
coeficiente estrictamente positivo para la variable de entrada, calculamos el resultado de
dividir el lado derecho de esta restricción entre el coeficiente de la variable de entrada. Si no se
puede realizar esta prueba, el problema no está acotado y termia el algoritmo.
Para la tabla del problema (3) la prueba del cociente mínimo (PCM) nos da los siguientes
valores
𝑉𝐵 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝐿𝐷 PCM
𝑍 −3 −5 0 0 0 0
𝑥3 1 0 1 0 0 4 N/A
𝑥4 0 2 0 1 0 12 6
𝑥5 3 2 0 0 1 18 9
4. Variable de salida: Después de realizar la prueba del cociente mínimo vamos a seleccionar la
variable básica correspondiente a la restricción que haya obtenido el coeficiente más pequeño.
Esta variable vamos a sacarla de las variables básicas y reemplazarla por la variable de entrada.
Para la tabla del problema (3) la variable de salida es 𝑥4
𝑉𝐵 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝐿𝐷 PCM
𝑍 −3 −5 0 0 0 0
𝑥3 1 0 1 0 0 4 N/A
𝑥4 0 2 0 1 0 12 6
𝑥5 3 2 0 0 1 18 9
5. Convertir la variable de entrada en una variable básica transformando la columna
correspondiente a la variable de entrada en el vector canónico correspondiente a la variable de
salida utilizando operaciones de filas únicamente con la fila de la variable de salida.
6. Para la tabla del problema (3) debemos convertir la columna de la variable de entrada 𝑥2 en el
mismo vector canónico que aparece para la variable de salida 𝑥4
𝑉𝐵 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝐿𝐷
𝑍 −3 −5 0 0 0 0
𝑥3 1 0 1 0 0 4
𝑥4 0 2 0 1 0 12
𝑥5 3 2 0 0 1 18
Después de hacer las operaciones de filas (únicamente con la fila de la variable de salida)
obtenemos la nueva tabla
𝑉𝐵 𝑥1 𝑥2 𝑥3 𝑥4 𝑥5 𝐿𝐷
𝑍 −3 0 0 5⁄2 0 30
𝑥3 1 0 1 0 0 4
𝑥2 0 1 0 1⁄2 0 6
𝑥5 3 0 0 −1 1 6
Nótese que en la primera columna de la tabla cambiamos la variable de salida 𝑥4 por la variable
de entrada 𝑥2 .
7. Volver al paso 1.