Programación lineal

1.1 Introducción

• La programación matemática es una potente técnica de modelado usada en el proceso de toma de decisiones. Cuando se trata de resolver un problema de este tipo, la primera etapa consiste en identificar las posibles decisiones que pueden tomarse; esto lleva a identificar las variables del problema concreto. Normalmente, las variables son de carácter cuantitativo y se buscan los valores que optimizan el objetivo. La segunda etapa supone determinar que decisiones resultan admisibles; esto conduce a un conjunto de restricciones que se determinan teniendo presente la naturaleza del problema en cuestión. En la tercera etapa, se calcula el coste/beneficio asociado a cada decisión admisible; esto supone determinar una función objetivo que asigna, a cada conjunto posible de valores para las variables que determinan una decisión, un valor de coste/beneficio. El conjunto de todos estos elementos define el problema de optimización.

• La programación lineal (PL), que trata exclusivamente con funciones objetivos y restricciones lineales, es una parte de la programación matemática, y una de las áreas más importantes de la matemática aplicada. Se utiliza en campos como la ingeniería, la economía, la gestión, y muchas otras ´áreas de la ciencia, la técnica y la industria.• En este capitulo se introduce la programación lineal por medio de

varios ejemplos seleccionados. Para empezar nuestra exposición se hace notar que cualquier problema de programación lineal requiere identificar cuatro componentes básicos:

• 1. El conjunto de datos.• 2. El conjunto de variables involucradas en el problema, junto con sus

dominios respectivos de definición.• 3. El conjunto de restricciones lineales del problema que definen el

conjunto de soluciones admisibles.• 4. La función lineal que debe ser optimizada (minimizada o

maximizada).

• En las secciones que siguen se da una lista de ejemplos, prestando especial atención en cada caso a estos cuatro elementos.• La lista seleccionada no es sino una muestra de la gran cantidad de

problemas de programación lineal (PPL) disponibles en las referencias. El objetivo en dicha selección es poder ilustrar de manera clara el alcance de la programación lineal y ayudar a nuestros lectores a familiarizarse con los cuatro elementos descritos.

1.2 El problema del transporte

• En esta sección se presenta y se describe el problema del transporte.

• Imagínese que un cierto producto debe enviarse en determinadas cantidades u1, . . . , um, desde cada uno de m orígenes, y recibirse en cantidades v1, . . . , vn, en cada uno de n destinos. El problema consiste en determinar las cantidades xij , que deben enviarse desde el origen i al destino j, para conseguir minimizar el coste del envió.

• Los cuatro elementos principales de este problema son:• 1. Datos

• 2. Variables

• 3. Restricciones.

• 4. Objetivo que debe optimizarse.

• 1. Datos• m: el numero de orígenes• n: el numero de destinos• ui: la cantidad que debe enviarse desde el origen i• vj : la cantidad que debe ser recibida en el destino j• cij : el coste de envió de una unidad de producto desde el origen i al

destino j

• 2. Variables• xij : la cantidad que se envía desde el origen i al destino j.• Se supone que las variables deben ser no negativas:• xij ≥ 0; i = 1, . . . , m; j = 1, . . . , n (1.1)• Esto implica que la dirección de envió del producto esta prefijada

desde los distintos orígenes hasta los destinos. No obstante, otras hipótesis podrían tenerse en cuenta. Por ejemplo, podría no limitarse el signo de las variables xij ∈ IR, si no se quiere predeterminar cuáles son los puntos de partida y llegada.

• 3. Restricciones. • Las restricciones de este problema son:

• (1.2)

njvx

miux

i

m

i ij

i

n

j ij

,....,1;

,....,1;

1

1

Figura 1.1: Esquema del problema del transporte.

• El primer conjunto de condiciones indica que la cantidad del producto que parte del origen i debe coincidir con la suma de las cantidades que parten de ese origen hasta los distintos destinos j = 1, . . . , n.• El segundo conjunto de condiciones asegura que el total recibido en

el destino j debe corresponder a la suma de todas las cantidades que llegan a ese destino y parten de los distintos orígenes i = 1, . . . , m.

• 4. Objetivo que debe optimizarse. • En el problema del transporte nos interesa normalmente minimizar los

costes de envió (suma de los costes de envió por unidad de producto multiplicado por las cantidades enviadas); es decir, se debe minimizar

• (1.3)

• Una vez que se han identificado estos cuatro elementos, se esta preparado para resolver el problema.

n

j ijij

m

ixcZ

11

EJEMPLO

• La empresa Gal elabora cerveza, como uno de sus productos, en tres plantas localizadas en tres ciudades del país, A, B y C. Este producto se transporta a cuatro almacenes localizados en cuatro ciudades del país, 1, 2, 3 y 4 para su posterior distribución. Los costos de transporte (en miles de bolívares) por camión de cerveza, se indican en la matriz de costos que se le presenta. Cada camión puede transportar 1000 cajas de cerveza. La cantidad de cajas de cerveza, disponible en las plantas, para transportar es la siguiente: A: 90.000; B: 40.000; C: 80.000. Las cajas de cerveza que requiere cada almacén son las siguientes: 1: 40.000; 2: 60.000; 3: 50.000; 4: 60.000

1 2 3 4

A 10 20 5 9

B 2 10 8 30

C 1 20 7 10

• Variables de Decisión:• Xij: camiones de cerveza a transportar desde la Planta de la ciudad i

hasta el almacén de la ciudad j• i = A,B,C j = 1,2,3,4• Las variables son 12 en total: (mxn) (3x4). Pueden ser definidas una

por una, pero es suficiente hacerlo con una cualquiera de ellas para expresar lo que representan. Por ejemplo:• XA3: camiones de cerveza a transportar desde la planta en la Ciudad A

hasta el almacén de la Ciudad 3.

• Nota: Para ayudarse en la definición conceptual de las variables imagine que el valor de ella ya lo ha encontrado y es un número cualquiera. Por ejemplo 8. Coloque ese 8 antes de la definición dada a la variable y compruebe que puede leerlo con coherencia. Así, en este caso, Usted puede leer: 8 camiones de cerveza a transportar desde la planta de la ciudad A hasta el almacén de la ciudad 3.

• Restricciones de Oferta: Disponibilidades limitadas de cajas de cerveza en las plantas de las 3 ciudades:• XA1 + XA2 + XA3 + XA4 ≤ 90• XB1 + XB2 + XB3 + XB4 ≤ 40• XC1 + XC2 + XC3 + XC4 ≤ 80• La cantidad del lado derecho de la restricción es el resultado de transformar

la cantidad de cajas de cerveza disponibles, en camiones. Esto es así porque la variable Xij se ha definido en “camiones” y no se puede sumar camiones y obtener un total de cajas de cerveza. Se debe ser coherente y lo que se suma debe ser lo que se obtiene, recuerde la Aditividad de los modelos lineales.

• Definición conceptual de una específica restricción de Oferta. La tercera, por ejemplo:• Representa la suma de camiones de cerveza transportados desde la

planta de la ciudad C hasta el almacén de la ciudad 1 (XC1), más los transportados desde esa misma planta hasta el almacén 2 (XC2), más los transportados hasta el almacén 3 (XC3), mas los transportados hasta el almacén 4 (XC4). Esta suma debe ser menor o igual a la cantidad de camiones disponibles en la planta de la ciudad C. En este caso 80, ya que dispone de 80.000 cajas de cerveza equivalente a 80 camiones.

• Restricciones de Demanda: Requerimientos de cajas de cerveza en los almacenes de las 4 ciudades:• XA1 + XB1 + XC1 ≥ 40• XA2 + XB2 + XC2 ≥ 60• XA3 + XB3 + XC3 ≥ 50• XA4 + XB4 + XC4 ≥ 60• De nuevo la cantidad del lado derecho es el resultado de transformar la

cantidad de cajas de cerveza disponibles, en camiones. Cada ecuación del modelo debe ser coherente. Lo que se suma son camiones y eso es lo que debe obtenerse.

• Definición conceptual de una específica restricción de demanda: La primera, por ejemplo:• Representa la suma de camiones de cerveza transportados hasta el

almacén de la ciudad 1 desde las plantas de la ciudad A(XA1) más los transportados desde la planta de la ciudad B (XB1), más los transportados desde la planta de la ciudad C (XC1), para satisfacer la demanda de ese almacén de la ciudad 1. Esta suma debe ser mayor o igual a la cantidad de camiones demandados en el almacén de la ciudad 1. En este caso 40, ya que demanda 40.000 cajas de cerveza equivalente a 40 camiones.

• Restricciones de no-negatividad de las variables:• Las variables están restringidas a ser no-negativas. No se pueden

transportar cantidades negativas, no existentes, de cerveza. Por eso, esta restricción acerca el modelo a la realidad.

• Función Objetivo: Se define como Minimizar los costos totales de transporte de los camiones de cerveza desde las 3 plantas hasta los cuatro almacenes..• Min 10 XA1 + 20 XA2 + 5 XA3 + 9 XA4 + 2 XB1 + 10 XB2 + 8 XB3 + 30

XB4 + 1XC1 + 20 XC2 + 7 XC3 + 10 XC4• Esta expresión matemática representa la suma de los costos totales

de transporte desde todas las plantas hasta todos los almacenes.

• Así por ejemplo, 20 XC2 representa los costos totales de los camiones de cerveza transportados desde la planta de la ciudad C hasta el almacén de la ciudad 2. Donde 20 es el costo unitario de transporte; es decir, el costo de transporte de un camión de cerveza desde la planta de la ciudad C hasta el almacén de la ciudad 2; XC2 es la cantidad transportada.• Resumiendo el modelo y colocando las variables en la posición de las

variables similares, se puede observar más claramente la característica esencial que hace especial al Modelo Lineal de Transporte: “Los coeficientes de las variables en las restricciones son 1 o cero”.

• Analizando la variable XA3 se observa que tiene coeficiente 1 en la primera restricción, cero en la• segunda; es decir, no existe en esa restricción. Tiene coeficiente cero

en la tercera, cero en la cuarta,• cero en la quinta, uno en la sexta y cero en la séptima. Igual

característica se observa en las demás• variables. El resumen del modelo formulado y construido es el

siguiente:

• Un fabricante tiene tres centros de distribución en: Bogotá, Medellín y Cali. Estos centros tienen disponibilidades de: 20, 40 y 40 unidades respectivamente. Sus detallistas requieren los siguientes cantidades: Pereira 25, Tulúa 10, Anserma 20, Ibagué 30 y Armenia 15. El costo de transporte por unidad en pesos entre cada centro de distribución y las localidades de los detallistas se dan en la siguiente tabla:• Cuanto unidades debe mandar el fabricante desde cada centro de

distribución a cada detallista, de manera que los costos totales de transporte sean mínimos ?

• Formulación• 1. Definición de las variables:• Xij = Cantidad de unidades a enviar desde el centro de distribución i-ésimo (i = 1 =

Bogotá, i = 2 = Medellín, i = 3 = Cali), al detallista j-ésimo (j = 1 = Pereira, j = 2 = Tulúa, j = 3 = Anserma, j = 4 = Ibagué,• j = 5 = Armenia).• • 2. Función objetivo:• Minimizar Z = 55X11 + 30X12 + 40X13 + 50X14 + 40X15 + 35X21 + 30X22 + 100X23 +

45X24 + 60X25 + 40X31 + 60X32 + 95X33 + 35X34 + 30X35 Sujeto a las siguientes restricciones:

• 3. Restricciones:

• 4. Condición de no negatividad:• Xij ≥ 0 ; i = 1, 2 y 3 ; j = 1, 2, 3, 4 y 5

• Una empresa energética dispone de tres plantas de generación para satisfacer la demanda eléctrica de cuatro ciudades. Las plantas 1, 2 y 3 pueden satisfacer 35, 50 y 40 millones de [kWh] respectivamente. El valor máximo de consumo ocurre a las 2 PM y es de 45, 20, 30 y 30 millones de [kWh] en las ciudades 1, 2, 3 y 4 respectivamente. El costo de enviar 1 [kWh] depende de la distancia que deba recorrer la energía. La siguiente tabla muestra los costos de envío unitario desde cada planta a cada ciudad. Formule un modelo de programcion lineal que permita minimizar los costos de satisfaccion de la demanda maxima en todas las ciudades.

• En primer lugar debemos definir las variables de decisión necesarias para representar las posibles decisiones que puede tomar la empresa energética. En este caso, corresponde a la cantidad de energía que se debe enviar desde cada planta a cada ciudad, luego para i = 1 . . . 3 y j = 1 . . . 4 :• xij = número de millones de [kWh] producidos en la planta i enviadas a

ciudad j (1.1)• En términos de estas variables, el costo total de entregar energía a todas

las ciudades es:• (1.2)

• El problema tiene dos tipos de restricciones. En primer lugar, la energía total suministrada por cada planta no puede exceder su capacidad. En este caso se habla de restricciones de oferta o suministro. Como existen tres puntos de oferta o sumistro, existen tres restricciones:• (1.3)

• En segundo lugar, se deben plantear las restricciones que permitan asegurar que se satisfaga la demanda en las cuatro ciudades. Así, las restricciones de demanda para cada punto de demanda quedan:• (1.4)

• Evidentemente, cada xij debe ser no negativo, por lo tanto se agregan las restricciones xij ≥ 0 donde i = 1 . . . 3 y j = 1 . . . 4.• Más adelante demostraremos que la solución de este problema

es z = 1020, x12 = 10, x13 = 25, x21 = 45, x23 = 5, x32 = 10 y x34 = 30. El resto de las variables vale cero.• Por otro lado, es posible construir una representación gráfica del

problema (figura 1.1).