1. INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL

La Programación Lineal es una de las principales ramas de la Investigación Operativa. En esta categoría se consideran todos aquellos modelos de optimización donde las funciones que lo componen, es decir, función objetivo y restricciones, son funciones lineales en las variables de decisión. Dicho en otras palabras, la programación lineal es una técnica de la Investigación de Operaciones que se encarga de buscar la mejor forma de utilizar los recursos limitados, mediante modelos de simulación conocidos como modelos de programación lineal. Se llega a una solución óptima después de la experimentación con dichos modelos. Una de las principales características de los problemas en donde se va a utilizar la programación lineal, es que los recursos deben ser limitados. El siguiente diagrama ilustra lo anterior.

3

RECURSOS

Cómo Optimizarlos

Encontrar la Solución Óptima

Se disponen de forma limitada

Técnicas para decidir cómo usarlos en forma óptima

Limitación en la disponibilidad de Recursos

Disponer de una cantidad Máxima de Recursos (< o =).

Disponer de una cantidad Mínima de Recursos (> o =).

Disponer de una cantidad Exacta de Recursos. (=)

INVESTIGACION DE OPERACIONES(TÉCNICAS)

Programación Lineal. Inventarios. Evaluación de Proyectos. Transporte y Asignación. Teoría de Redes. Etc.

EMPRESA

Los elementos que debe contener un modelo de programación lineal, son los siguientes:

Expresiones matemáticas

En tales expresiones encontramos a las Ecuaciones

Ejemplo: A+B=C

Las InecuacionesEjemplo: 2A+3B ≥ C

Las Variables de decisión, las cuales deben existir por lo menos dos variables y la mejor forma de representarlas es con Xn, donde n puede tomar infinitos valores.

Las relaciones permitidas con las variables son las siguientes: =, +, -, ≤, ≥, exponente 1 en las variables, producto entre el coeficiente y la variable.Por otro lado, las relaciones no permitidas son las siguientes: ≠, <, >, división y producto entre variables, exponente distinto (mayor) de uno, raíz cuadrada.

RestriccionesDe estas, debe haber dos o más.

Restricciones de No negatividad, significa que los valores de variables no deben ser negativos. Esto es: Xn ≥ 0

ObjetivoEs la meta o logro que la empresa quiere alcanzar cuando determine cómo utilizará sus recursos limitados. El objetivo será básicamente de dos tipos:

Maximizar.- Incrementar utilidades, rendimientos, contribuciones, etc. (MAX).Minimizar.- Reducir Costo, tiempo (MIN).

De lo anterior se desprende lo que conocemos como FUNCIÓN OBJETIVO, que no es otra cosa más que una expresión matemática que nos debe decir qué objetivo se persigue. Se representa con:-ZMAX ó MaxZ-ZMIN ó MinZ

MODELO DE PROGRAMACIÓN LINEAL

La estructura que debe presentar un modelo de programación lineal, es más o menos como sigue: Primero, que existan recursos limitados. Determinar variables de decisión (X1=, X2=,)

4

El siguiente paso es escribir SÓLO UNA Función ObjetivoEjemplo:ZMAX = 3X1+2X2

Al escribir la función objetivo, se deben tomar en cuenta las siguientes consideraciones:

Una función objetivo siempre es una ecuación (igualdad) La relación entre las variables siempre es de suma. La función objetivo está sujeta a las restricciones (s.a. “sujeto a”)

Estructura de las restricciones de recursos.Las restricciones de recursos deben ser dos o más y tendrán la siguiente estructura.

Las restricciones generalmente son desigualdades y en muy raras ocasiones son una igualdad. Debe existir una restricción por tipo de recurso. Las variables no deben ser negativas (restricción de no negatividad: X1, X2 ≥ 0).

Tipos de modelos de programación lineal.

Existen por lo menos cuatro tipos distintos de programación lineal:

1) Modelo de Maximizar Homogéneo: En este tipo de modelo, las restricciones son del mismo tipo.Ejemplo:

5

X1 + 3X2 ≤ 50

2X1 – X2 ≤ 20

RESTRICCIÓN 1

RESTRICCIÓN 2

Relaciones entre variables

Recursos limitados

ZMAX= 3X1 + 2X2

s.a. X1 + 3X2 ≤ 50

2X1 – X2 ≤ 20

X1, X2 ≥ 0

ZMIN= 4X1 + 2X2

s.a. 2X1 + X2 ≥ 10

X1 + 3X2 ≥ 15

3 X1 - X2 ≥ 8

X1, X2 ≥ 0

ZMIN= X1 + X2

s.a. 3X1 + 4X2 ≥ 10

X1 + X2 ≤ 5

X1, X2 ≥ 0

2) Modelo de Maximizar Heterogéneo: Restricciones de recursos son distintas.

Ejemplo:

3) Modelo de Minimizar HomogéneoEjemplo:

4) Modelo de Minimizar Heterogéneo.Ejemplo:

Cuándo usar reglas generales para determinar el tipo de restricción.

Las reglas generales se aplican cuando el problema no especifique las restricciones de recursos y sólo se aplica a los modelos heterogéneos.

Las reglas generales son las siguientes:

En un modelo de maximizar heterogéneo tiene las restricciones del tipo ≤

En un modelo de minimizar heterogéneo tiene las restricciones del tipo ≥

6

ZMAX= 4X1 + X2

s.a. 3X1 + X2 ≤ 25

X1 – X2 ≤ 8

X2 ≥ 4

X1, X2 ≥ 0

Coeficientes

2. FORMULACIÓN DE MODELOS DE PROGRAMACIÓN LINEAL.

El paso inicial es que exista un problema, luego contar con la información necesaria (recursos limitados, variables de decisión, objetivo, recursos para cada variable) y si el problema no nos aporta más información, recurrimos a las reglas generales.

El siguiente paso es construir una tabla como la siguiente.

RecursosVariables de Decisión

DisponibilidadX1 X2

Recurso1

Recurso2

Utilidad o Costos

Ejemplo con datos de un problema real.

Mesa SillaMadera

0.75 0.5≤ 100 M3

Clavos 1/4 1/8≤ 10 Kg

Mano de obra 5 4≤ 80 Hrs

Utilidad 50 45

Construcción del Modelo de Programación Lineal

7

X1 X2

Recu

rsos

Función Objetivo

ZMAX= 50X1 + 45X2

s.a. 0.75X1 + 0.5X2 ≤ 100

1/4X1 + 1/8X2 ≤ 10

5X1 + 4X2 ≤ 80

X1, X2 ≥ 0

* El resultado es un Modelo de Maximizar Homogéneo o Estándar de Maximizar

RESOLUCIÓN DE MODELOS DE PROGRAMACIÓN LINEAL

Para la resolución de los modelos de programación lineal, se consideran dos métodos.

3. MÉTODO GRÁFICO

Es considerado como el método más sencillo, pero tiene que satisfacer los siguientes criterios:

Solo es aplicable para modelos de 2 variables de decisión. Para 2 o más restricciones de recursos. Sólo proporciona información de las variables de decisión y Z. No proporciona información directa de la utilización de los recursos (solo indirectamente). Requiere el uso de escalas lineales.

Otras consideraciones:

El número de líneas rectas estará dado por el número de restricciones de recursos. Para los modelos homogéneos se espera que las áreas de análisis aparezcan del mismo

lado. La orientación de la línea, dependerá del número de variables.

Ejemplo:Para 2 variables se espera,

Para 1 Variable se espera

Pasos a seguir para resolución mediante el método gráfico.

Considere el siguiente ejemplo para ayudarnos a comprender mejor los pasos a seguir.

1. Identificar el modelo a resolver. Esto significa que vamos a determinar si buscamos el valor máximo de Z (ZMAX) o el valor mínimo de Z (ZMIN). Cuando existen áreas del mismo lado (modelos homogéneos) significa que por lo menos hay una solución óptima. En el ejemplo nos interesa obtener el valor máximo de Z.

8

ó

ó

ZMAX= 16XA + 12XB

s.a. 8XA + 15XB ≤ 112

20XA + 10XB ≤ 170

XA, XB ≥ 0

2. Establecer las fronteras de cada restricción. Las fronteras son las igualdades de las restricciones. Para hallarlas, solamente convertimos las desigualdades (inecuaciones) en igualdades (ecuaciones).

Esto es:

Una vez hecho lo anterior, podremos graficar las líneas rectas.

3. Graficar las líneas rectas.

Obtención de los puntos.

Le asignamos el valor 0 a una de las variables, para hallar el punto donde la línea hace intersección con el eje de las Y (XB). Empezamos con XA

1.- 8XA + 15XB = 112

Si XA = 0Entonces diremos que:0+15XB = 112XB = 112/15Por lo tanto, el punto 1 sería:P1 (0 , 112/15)

2.- 20XA + 10XB = 170

El siguiente paso sería graficar los puntos en el plano.

La gráfica de la solución del modelo anterior la incluimos en la página siguiente.

9

8XA + 15XB ≤ 112

20XA + 10XB ≤ 170

8XA + 15XB = 112

20XA + 10XB = 170

Si XB = 0Entonces diremos que:8XA + 0 = 112XA = 112/8XA = 14Por lo tanto, el punto 2 sería:P1 (14 , 0)

Si XA = 0Entonces diremos que:0 + 10XB = 170XB = 170/10XB = 17Por lo tanto, el punto 1 sería:P1 (0 , 17)

Si XB = 0Entonces diremos que:20XA + 0 = 170XA = 170/20XA = 17/2Por lo tanto, el punto 2 sería:P2 (17/2 , 0)

Gráfica del ejemplo anterior.

4. Identificación del área de solución factible para cada restricción.

Esta área contiene los valores de las variables que satisfacen la restricción (recurso limitado) que se analiza. En la gráfica anterior se puede identificar claramente el área de solución factible para cada una de las líneas rectas.

5. Identificar el área de Optimalidad

Esta área es la que contiene los valores de las variables que satisfacen a todas las restricciones del modelo y que además en uno o más vértices que la delimitan, llamados “vértices de optimalidad”, se encontrará la solución óptima del modelo. En la gráfica anterior identificamos al área de optimalidad por ser la región marcada con líneas color rojo en forma de rejilla delimitada por cuatro vértices de optimalidad señalados por flechas punteadas color amarillo.

10

Área de solución factible

Área de solución factible

Área de optimalidad

Vértices de Optimalidad

20XA + 10XB = 170

V

V

V

V

6. Construir una tabla donde se ubiquen los vértices de optimalidad, los valores de las variables en esos vértices y el valor de la función objetivo para cada vértice.

La tabla quedaría más o menos como sigue.

Vértice XA XB ZMAX= 16 XA + 12XB1 0 0 0

2 0 112/15

448/5 (89.6 aprox)

3 6.5 4 1524 8.5 0 136

7. Encontrar la solución óptima.

Esto lo haremos al seleccionar el vértice que satisfaga de mejor manera el objetivo que se persigue. Para el ejemplo que estamos analizando, el objetivo que perseguimos es de maximizar utilidades, por lo tanto nos interesa el valor más alto que es 152 y se encuentra en el vértice 3.

8. A partir de la solución óptima, interpretar dicha solución para encontrar la solución al problema que se está resolviendo.

POR LO TANTO,

La solución óptima es:

4. EL MÉTODO SIMPLEX

Es un procedimiento iterativo que permite ir mejorando la solución a cada paso. El proceso concluye cuando no es posible seguir mejorando más dicha solución. Fue creado en 1947 por el matemático George Dantzig .

El método del simplex se utiliza, sobre todo, para resolver problemas de programación lineal en los que intervienen tres o más variables.

Para construirlo se siguen los siguientes pasos.

1 Modelo original o modelo de desigualdades.

El objetivo que se persigue es lo que nos marcará las reglas a seguir.

11

Hallar el valor de XA, XB en los vértices 1, 2, y 4 no supone ningún problema, puesto que sabemos que en cualquiera de esos tres casos los vértices hacen contacto con los ejes XA y XB. Para encontrar los valores de XA y XB en el vértice 3, recurrimos a un sistema de ecuaciones simultáneo. Al resolverlo obtenemos los valores para XA= 6.5 y XB= 4

XA= 6.5

XB= 4

Con ZMAX = 152

Supongamos que tenemos el siguiente modelo original.

2. Relaciones aumentadas.

Se construye un modelo equivalente de programación lineal y se incorporan variables adicionales para encontrar la frontera. Al modelo equivalente también se le conoce como modelo de igualdad.

Si un momento dado se quiere volver de un modelo equivalente al modelo original, lo único que se tiene que hacer es eliminar las variables de holgura.

3. Construir Solución Inicial.

Las variables de decisión siempre serán 0. (XA = 0, XB = 0. En este punto se conocen como variables no básicas) ZMAX = 0

Las variables de holgura serán igual a los valores de los recursos.

S1=112, S2= 170 (Variables básicas)

4. Tabla Simplex Inicial.

Cj 16 12 0 0VB XA XB S1 S2 VS

0 S1 8 15 1 0 112

0 S2 20 10 0 1 170

Zj 0 0 0 0 016 12 0 0

12

ZMAX= 16XA + 12XB

s.a. 8XA + 15XB ≤ 112

20XA + 10XB ≤ 170

XA, XB ≥ 0

A las restricciones de recursos, dependiendo de qué tipo sean, se incorporará una variable adicional (+S en este caso)

El número de restricciones nos determinará el total de variables adicionales.

ZMAX= 16XA + 12XB + 0S1 + 0S2

s.a. 8XA + 15XB + S1 + 0S2 = 112

20XA + 10XB + 0S1 + S2 = 170

XA, XB, S1, S2 ≥ 0

Donde:

XA, XB son Variables de Decisión

S1, S2 son variables de Holgura

Cj- Zj

Columna Pivote

Renglón Pivote

ZMAX= 0 XA= 0 XB= 0

Zj = ∑ Cij aij

5. Cambio de Bases.

Consiste en cambiar una variable no básica a una básica y viceversa. La terminología para este tipo de variables es Variable Básica Entrante (VBE) y Variable Básica Saliente (VBS).

VBE= XA Columna Pivote

VBS= S2 Renglón Pivote

Para S1 = 1128

=14 Para S2= 17020

=172

=8.5

A la intersección entre la columna pivote y el renglón pivote se le llama número pivote. En este caso es 20.

Construcción de la primera tabla simplex revisada.

Cj 16 12 0 0VB XA XB S1 S2 VS

0 S1

16 XA 112

0120

172

Zj

13

Cj- Zj

Nueva Solución:S1= 44

XA= 17/2ZMAX= 135S2=0, XB=0

Primero se divide todo el renglón (ahora saliente entre el número pivote (20) y escribimos el resultado.

Luego, calculamos el valor de S2 con la siguiente operación:8 (1 ½ 0 1/20 = 17/2) Se efectúa el producto. 8 15 1 0 = 112 (Renglón pivote anterior) -8 -4 0 -2/5 = -68 (Producto resultante)

0 11 1 -2/5= 44 El resultado se escribe en S1Luego calculamos el valor de Zj

Cj 16 12 0 0VB XA XB S1 S2 VS

0 S1 0 11 1 −25

44

16 XA 112

0120

172

Zj 16 8 0 45

136

0 4 0 −45

Cj- Zj

Podemos ver que aún quedan valores positivos en Cj - Zj, por lo tanto aunque la solución parezca más optima que la anterior, todavía podemos hacer otra iteración. Entonces procedemos.

En este punto tendremos que repetir la operación anterior, es decir dividir todo el renglón pivote anterior entre el número pivote. Posteriormente buscar nuevos valores para el renglón XA, calcular los valores de Zj, y finalmente Cj-Zj. El resultado final queda como sigue.

Nos damos cuenta de que hemos llegado a la solución óptima porque en el renglón del criterio simplex (Cj – Zj) solo encontramos valores 0 y negativos.

Pudimos darnos cuenta que llegamos al mismo resultado que con el método gráfico, pero de distinta manera.

14

Columna Pivote

Determinamos un nuevo renglón y columna pivotes.

Nueva Solución:XA= 6.5 XB= 4

ZMAX= 152S2=0, S2=0

Cj 16 12 0 0VB XA XB S1 S2 VS

0 S1 0 11 1 −25

44

16 XA 112

0120

172

Zj 16 8 0 45

136

0 4 0 −45

Cj- Zj

Renglón Pivote

Cj 16 12 0 0VB XA XB S1 S2 VS

12 XB 0 1 1/11 -2/55 4

16 XA 1 0 -1/22 3/44 13/2

Zj 16 12 4/11 36/55 1520 0 -4/11 -36/55

Cj- Zj