Optimización I

Semana 5, clase sincrónica:

Modelo de programación lineal
Resultados de aprendizaje

Aplicar los supuestos de la programación lineal y problemas clásicos facilitando el

análisis de situaciones operativas de una empresa.
Contenido

Álgebra de los métodos de programación lineal: método gráfico, método simplex.

Introducción: Álgebra de la PL

En general, usaremos un modelo matemático de

optimización que tiene la siguiente estructura.

La función objetivo corresponde a la que se pretende

optimizar, es decir, minimizar o maximizar. Esta función
objetivo está restringida a lo que conocemos como
restricciones. La sigla s.a significa “sujeto a” y define las
restricciones del modelo.

Estas restricciones podrían relacionarse con el tiempo o los

materiales, como madera, aluminio, etc. Típicamente,
también están las restricciones de no negatividad, que
establecen que las soluciones serán positivas o cero, ya
que, en general, estas soluciones representan elementos
tangibles como producción de mesas, sillas, etc. Por último,
definimos la naturaleza de las variables. En este caso, serían
cantidades positivas.
Método gráfico

Pasos de aplicación:

1. Graficar cada una de las restricciones correspondientes al problema en un eje de coordenadas (X1, X2).

2. Definir la región factible de soluciones del problema.

3. Encontrar los puntos extremos del polígono que se forma con las intersecciones.

4. Evaluar la función objetivo con los puntos encontrados y elegir de acuerdo con el objetivo (maximizar o minimizar).
Ejemplo aplicación método gráfico

Máx Z = 3X1 + 5X2

sujeto a:
X1 <= 4
2X2 <= 12
3X1 + 2X2 <= 18
X1, X2 >= 0
Ejemplo aplicación método gráfico

Primero, graficamos las restricciones. Como nos encontramos en el cuadrante positivo del plano cartesiano, dado por las
restricciones de no negatividad, la solución factible debería encontrarse en este cuadrante. La restricción uno indica que la
variable X1≤4. Si despejamos la variable X2 de la ecuación número 2, encontraremos que X2 <= 6.

Finalmente, graficando la tercera restricción en el eje de coordinadas equis uno, equis dos, encontramos que la tercera restricción
corta al eje equis dos en nueve y al eje equis uno en seis. Luego, se evalúan los puntos de intersección de las restricciones y
encontramos lo siguiente:
Ejemplo aplicación método gráfico

Después, se evalúan los puntos de intersección de las restricciones. Al evaluar cada punto encontramos lo siguiente:
Método simplex
Método simplex

El simplex, diseñado por George Dantzing en la década del 40 para resolver problemas lineales, es el algoritmo más famoso para
este tipo de problemas.

En palabras sencillas, dado que el óptimo del problema se puede encontrar en un punto extremo, lo que hace el algoritmo es
moverse de extremo a extremo siempre que mejore la función objetivo.

El método simplex se utiliza cuando existen más de dos variables, el procedimiento no es tan sencillo y se resuelve mediante
operaciones matriciales.
Método simplex

Función objetivo:
Máx o mín Z= c1 x1 + c2 x2 + c3 x3 + ...+ cn xn
Sujeto a:
a11 x1 + a12 x2 +...+ a1n xn £ b1
a21 x1 + a22 x2 +...+ a2n xn £ b2
. . .
am 1 x1 + am2 x2 +...+ amn xn £ bm
xj ³ 0 ; j=1..n

Modelo general de PL con “m” restricciones y “n” variables de decisión.

Método simplex: formato estándar

Función objetivo:
Máx o mín Z= c1 x1 + c2 x2 + c3 x3 + ...+ cn xn
Sujeto a:
a11 x1 + a12 x2 +...+ a1n xn + h1 = b1
a21 x1 + a22 x2 +...+ a2n xn + h2 = b2
. . .
am 1 x1 + am2 x2 +...+ amn xn + hm = bm
xj ³ 0 ; j=1…n
Pasos método simplex

1. Igualar la función objetivo a cero.

2. Convertir las desigualdades de las restricciones en igualdades (<= a = ) agregando una variable de holgura hi.

3. Confeccionar el tableau con solución básica inicial igual a cero con sus respectivos coeficientes.

4. Elegir la variable que entra en la base (de las Xi), que corresponde a la que menos contribuye a la función objetivo (criterio
de elección de la columna pivote).
Pasos método simplex

5. Elegir la variable básica que sale de la base de acuerdo con el criterio de mínimo cociente entre el LD y su coeficiente
correspondiente de la columna pivote (criterio de elección de la fila pivote).

6. Dejar un 1 en la intersección entre la columna y la fila pivote y dejar 0 en el resto de la columna pivote aplicando
operaciones elementales (pivoteando con la fila pivote).

7. Repetir el proceso hasta que la primera fila (Zj-Cj) sean todos positivos o ceros (caso de máximo) o sean todos negativos
o ceros (caso de mínimo).
Ejemplo método simplex

Resuelve el siguiente problema de programación lineal mediante método simplex:

max Z = 2 x1 + x2 + 3 x3
s.a.
x1 + x2 + x3 ≤ 100
5 x1 + 5 x2 + 5 x3 ≤ 500
x1 + x3 ≥ 50
x1 , x2 , x3 ≥ 0
Ejemplo método simplex

Para resolver este problema de forma manual, aplicando el método simplex, seguimos los pasos del algoritmo. Primero se iguala la
función objetivo a cero, pasando hacia la izquierda las variables de decisión con sus coeficientes, cambiando su signo. Luego, se
traspasa el modelo del formato canónico al estándar, agregando las variables de holgura hi respectivas. Para realizar esta
transformación en la tercera restricción, se multiplica por menos uno toda esa restricción y después se transforma al formato
estándar. Una vez aplicado el formato estándar se construye el tableau con los respectivos coeficientes.

Formato estándar:
Z - 2X1 - X2 - 3X3 = 0
X1+ X2 + X3 + h1 = 100
5X1 + 5X2 + 5X3 +h2 =500
-X1- X3 + h3 = -50
 Problema primal-dual

Cada modelo de optimización de un sistema, que llamaremos el PRIMAL, tiene asociado modelo DUAL.

El modelo PRIMAL representa el sistema que se desea optimizar.

El modelo DUAL calcula los precios sombra de las restricciones de un primal.

Función óptima modelo primal: Z.

Variables de decisión modelo primal: Xj.

Función óptima modelo dual: W.

Variables de decisión modelo dual: Yi.
 Problema primal-dual

a. Modelos primales simétricos o normales

Se dice que un modelo primal de maximización es simétrico o normal cuando todas sus restricciones son limitaciones menor o
igual y todas sus variables de decisión son no negativas.
Se dice que un modelo primal de minimización es simétrico o normal cuando todas sus restricciones son requerimientos del tipo
menor que y todas sus variables de decisión son no negativas.
Problema primal-dual

b. Modelo dual de modelos primales no normales

1. Si existen variables sin restricción de signo, reemplaza en el modelo la(s) variable(s) por una diferencia entre dos variables
auxiliares.

2. Si existen requerimientos del tipo igualdad reemplaza esa(s) restricciones por dos restricciones, una del tipo (≥) y otra del tipo
(≤).

3. Si el problema es de maximización, transforma todas las restricciones en limitaciones (≤) y, si el problema es de minimización,
transforma todas las restricciones en requerimientos, multiplicando por (-1) las restricciones (≥). Si el problema es de
minimización, transforma todas las restricciones en requerimientos, multiplicando por (-1) las restricciones (≤).
 Problema primal-dual

Teorema de las holguras complementarias

Sea Xj el valor de las variables de decisión que da origen a una solución factible de un problema PRIMAL y sea Yi el valor de las
variables de decisión que da origen a una solución factible de su problema DUAL. Entonces , ambas soluciones serán óptimas. Si, al
reemplazar las variables de una restricción primal por su valor óptimo la restricción se cumple en su sentido estricto mayor o menor
que, observar la ecuación primera ecuación a.

La ecuación b, en forma similar, se concluye con esta segunda parte del teorema que, cuando una variable primal básica óptima es
distinta de cero, la holgura de la restricción dual, valorizada en el óptimo, debe ser necesariamente igual a cero.
Resumen

La programación lineal corresponde a un caso particular de los modelos de optimización paramétrica en el que se cumplen todos los
supuestos.

El modelo general de programación lineal está compuesto por la función objetivo y restricciones y corresponde a un modelo
algebraico de tipo matricial.

Un modelo de programación lineal en su forma más simple puede resolverse con el método gráfico, esto es, cuando el modelo posee
dos variables de decisión.

El método simplex es el programado en los softwares, dado que la operación de encontrar el óptimo de un problema de
programación lineal no es más que aplicar operaciones matriciales.

El modelo dual de un dual es el modelo primal.

Referencias bibliográficas

Hillier, F. y Lieberman, G. (2010). Introducción a la investigación de operaciones. (9ª ed.). McGraw-Hill.

Taha, H. A. (2012). Investigación de operaciones. (9ª ed.). Pearson.