Programación Lineal

Dentro del ámbito de la investigación operativa existen técnicas de modelado de problemas. La más básica de ellas es la programación lineal; la cual consiste en el modelado matemático generado a partir de un problema físico que busca optimizar un objetivo, para lo que han de existir recursos limitados o escasos (llámese capital, mano de obra, tiempo, materiales o insumos, etc.)

Se empezó a desarrollar en el siglo XX, basándose en métodos de teoría de números y técnicas de cálculo integral y geometría analítica. Matemáticos como Von Neumann, Leonid Kantorovich y George Dantzig fueron los que desarrollaron desde el planteamiento hasta los métodos de resolución de modelos lineales.

Un problema de programación lineal es un problema de optimización, en el cual:

• Se intenta maximizar o minimizar una función LINEAL de las variables de decisión; llamada F.O.
• Los valores de las variables de decisión deben satisfacer restricciones (ecuaciones o desigualdades lineales).
• Se relaciona una restricción de signo con cada variable. Para cualquier variable x, la restricción de signo especifica que xi no debe ser negativa (xi>=0) o no tener restricciones de signo (nrs).

Todo problema de programación lineal; para ser considerado tal; debe cumplir con las siguientes suposiciones:

SUPOSICIONES DE PROPORCIONALIDAD Y ADITIVIDAD

El hecho de que la función objetivo para una PL deba ser función lineal de las variables de decisión genera que:

• La contribución de la F.O. para cada variable de decisión (VD) es proporcional al valor de ésta. Por ejemplo, la contribución a la F.O. por hacer cuatro soldados (ej. 4x$3 = $12) es exactamente 4 veces la contribución por hacer un soldado ($3).
• La contribución a la F.O. para cualquier variable, es independiente de los valores de las otras variables de decisión. Es decir, no importa cuál sea el valor de X2, pero la manufactura de x1 soldados siempre contribuirá con 3×1 dólares a la F.O.

Igualmente, el hecho de que cada restricción de PL debe ser una ecuación/desigualdad lineal, tiene dos consecuencias:

• La contribución de cada variable al primer miembro de cada restricción, es proporcional al valor de la variable. Por ejemplo, se requieren exactamente 3 veces más horas de acabado (2×3 = 6 horas de acabado) para manufacturar 3 soldados, que para fabricar un soldado (2 horas de acabado).
• La contribución de una variable al primer miembro de cada restricción, es independiente de los valores de la variable. Por ejemplo, no importa cuál sea el valor de x1, pero la manufactura de x2 trenes requiere x2 horas de acabado y x2 horas de carpintería.

La primera consecuencia de cada lista se denomina suposición de proporcionalidad de la programación lineal. La consecuencia 2 de la primera lista implica que el valor de la F.O. es la suma de las contribuciones de cada una de las variables; y la consecuencia 2 de la segunda lista es que el primer miembro de cada restricción es la suma de las contribuciones de cada variable. Por esta razón, la segunda consecuencia de cada lista se denomina suposición de aditividad de la programación lineal.

Para que una programación lineal represente en forma adecuada una situación de la vida cotidiana, las variables de decisión deben satisfacer ambas suposiciones. También han de cumplir con otras dos suposiciones antes de que una PL represente adecuadamente una situación real: las suposiciones de divisibilidad y de certidumbre:

SUPOSICIÓN DE DIVISIBILIDAD

Requiere que todas las variables de decisión puedan asumir valores fraccionarios. En caso contrario, estamos hablando de un problema de PROGRAMACIÓN ENTERA. En muchas situaciones donde la divisibilidad no está presente, el redondeo de las variables a un entero en la solución óptima sería razonable. Por otro lado, en los casos en que sea imperativo no redondear; o sea imposible hacerlo, se deben utilizar los métodos de programación entera.

SUPOSICIÓN DE CERTIDUMBRE

Para esta suposición, se requiere conocer con certeza todos los parámetros (coeficiente de la F.O., segundo miembro y coeficientes tecnológicos (los que acompañan a las variables de decisión)). Si hay incertidumbre en la cantidad exacta de horas de carpintería y acabado para fabricar un tren, se incurriría en una violación a esta suposición.

Consta de tres pasos generales: Identificar, formular y resolver; los cuales ampliaremos en el ejemplo (el paso de resolver lo veremos más adelante en Método Gráfico, Método Simplex). Ahora vamos con un ejemplo de la estructuración de un programa lineal para ilustrar lo expuesto hasta el momento:

ESTRUCTURA EJEMPLO

La empresa Coca-Cola requiere vender sus productos estrella: Coca-Cola, Powerade y Frugos. Dado que es físicamente imposible vender una cantidad infinita de cada uno; desea saber en qué cantidad debe vender cada producto para maximizar sus ganancias; teniendo en cuenta que para producir cada bebida se requieren diferentes cantidades de insumos y mano de obra; y que la planta de producción no puede superar a su capacidad instalada.

PASO 1: IDENTIFICAR:

• Debe existir un objetivo único bien definido. (ej. Maximizar ganancias)
• Deben existir cursos de acción alternos (ej. Vender Powerade, Coca-Cola o Frugos)
• Deben existir limitaciones o restricciones. (ej. Tiempo, capacidad, etc.)
• Poder expresar la función objetivo y las restricciones en forma matemática.

PASO 2: FORMULAR:

• Definir el objetivo: (Maximizar o Minimizar): En este caso, maximizar las ganancias.
• Definir variables: Para el ejemplo;
  • X1: Cantidad de Powerade a vender.
  • X2: Cantidad de Frugos a vender.
  • X3: Cantidad de Coca-Cola a vender.
• Escribir la Función Objetivo:
  • MAX Z= C1X1+C2X2+C3X3+…CnXn
• Escribir cada una de las restricciones:
  • A. (sujeto a):
  • X1+A12.X2+A13.X3+…+A1N.XN <=,=,>= B1 (restricción de tiempos de prod.)
  • X1+A22.X2+A23.X3+…+A2N.XN <=,=,>= B2 (restricción de mano de obra)
  • X1+A32.X2+A33.X3+…+ANN.XN <=,=,>= BN (restricción de capacidad)
  • X1,X2,X3,…,XN >= 0.

PASO 3: RESOLVER

Una vez que el modelo lineal está planteado; se procede a resolverlo mediante: Método Gráfico o el Método Simplex.