Modelos de programación lineal

UNIDAD II: Formulación y Aplicación de Modelos

MODELOS LINEALES. PROGRAMACIÓN LINEAL: CONCEPTOS FUNDAMENTALES. FORMULACIÓN DE PROBLEMAS, MÉTODO GRÁFICO, MÉTODO SIMPLEX

Modelos de programación lineal

Características de los problemas de programación lineal:

Una función objetivo que se va a Maximizar o a Minimizar.

Restricciones que pueden ser de limitaciones o Exigencias.

Proporcionalidad: la función objetivo y las restricciones deben ser proporcionales a nivel de fabricación de cada producto.

Divisibilidad: Significa que son posibles asignaciones fraccionarias de productos.

Aditividad: las contribuciones de los productos individuales son aditivos.

No negatividad de los productos: No es posible fabricar cantidades negativas de ellos.

SECCIÓN A. Teoría General de Programación Lineal y Fase de Formulación y Construcción de Modelos

Programación Lineal es una técnica cuantitativa ampliamente aplicada en sistemas que presenten relaciones lineales, para utilizar los recursos escasos de la mejor manera posible.

La mejor manera de usar los recursos escasos se logra utilizando un modelo del sistema llamado Modelo de Programación Lineal.

El Modelo de Programación Lineal es un modelo matemático con variables de decisión, coeficientes y/o parámetros, restricciones y una Función Objetivo.

Es determinístico porque todos los datos relevantes utilizados, son conocidos. Es lineal porque las restricciones y el objetivo son funciones lineales. La contribución de cada variable al valor total del objetivo y al lado derecho de cada restricción es proporcional al valor de la variable. Es aditivo porque los términos de sus restricciones y objetivo pueden sumarse (o restarse). La contribución de cada variable es independiente del valor de las otras variables. Es divisible porque las variables de decisión pueden aceptar valores fraccionales. En caso de no aceptar valores fraccionales, sería preferible usar Programación Lineal Entera.

La Formulación y Construcción del Modelo Lineal implica:

Definir claramente las variables de decisión y expresarlas simbólicamente o convencionalmente.

Definir claramente la Función Objetivo y las restricciones y expresarlas matemáticamente como funciones lineales.

Variables de decisión (VD): X1, X2, ……., Xn

Debe cuidarse que los elementos componentes del modelo sean expresados para el mismo período de tiempo.

Se debe estipular que las variables de decisión sean mayores o iguales a cero. Esto acerca el modelo a la realidad. En los programas de computadora para resolver modelos lineales, ya está incluida esta condición y no hace falta incorporarla manualmente.

La Función Objetivo del Modelo Lineal es la formulación matemática de una meta establecida y por lo tanto su valor final mide la efectividad lograda. Es una función lineal a ser maximizada o minimizada y tiene la siguiente forma general:

FO (Max. O Min.) Optimizar Z = C1X1 + C2X2 + C3X3 + C4X4 +...................+ CnXn

Xj, simboliza matemáticamente a las variables de decisión. Son los valores numéricos que se determinan con la solución del modelo y representan o están relacionadas con una actividad o acción a tomar. Son los únicos valores desconocidos en el modelo y pueden existir en cualquier cantidad, desde 1 hasta n variables. Es decir, j varía desde 1 hasta n.

Cj, matemáticamente, simboliza el coeficiente de la variable j en la Función Objetivo. Son datos relevantes, insumos incontrolables ya conocidos. En la Función Objetivo representan la cantidad con la cual contribuye cada unidad de la variable j, al valor total deseado en el objetivo.

Las restricciones, desde el punto de vista matemático, son funciones lineales expresadas como igualdades o desigualdades, que limitan el valor de las variables de decisión a valores permisibles. Representan recursos, condiciones o requerimientos establecidos. Las restricciones del Modelo Lineal general tienen la forma siguiente:

a11 X1 + a 12 X 2 + a 13 X 3 + a14 X 4 + .................. + a1n Xn ≥≤ = b1

a21 X1 + a 22 X 2 + a 23 X 3 + a24 X 4 + .................. + a2n Xn ≥≤ = b2

a31 X1 + a 32 X 2 + a 33 X 3 + a34 X 4 + .................. + a3n Xn ≥≤ = b3

. . . . . .

am1 X1 + a m2 X 2 + a m3 X 3 + am4 X 4 +...............+ amn Xn ≥≤ = bm

aij, matemáticamente simboliza el coeficiente, en la restricción i, de las variable j.

El subíndice i indica el recurso, requerimiento o condición cuya limitación se está expresando; j indica la variable correspondiente. Cuando la limitación es de un recurso i, estos coeficientes representan la cantidad del recurso total limitado i, que es utilizada en cada unidad de la variable j. Cuando la limitación es de un requerimiento o condición i, representan la cantidad del requerimiento o condición i limitada, que aporta cada unidad de la variable j, al requerimiento o condición total establecida. Son, por ello, valores unitarios, al igual que los coeficientes de las variables en la Función Objetivo.

bi, matemáticamente constituye el lado derecho de la restricción i. Representa la cantidad total disponible del recurso limitado i, o la cantidad total de un requerimiento o condición i establecida. Puede existir cualquier cantidad de restricciones por lo tanto i puede variar desde 1 hasta m.

Xj ³ 0 es una restricción de no negatividad de las j variables, la cual se le considera siempre presente como una condición natural en el Modelo Lineal General.

Donde:

X1 , X2,......,Xn Representan las variables de decisión sobre las cuales hay que decidir.

a11 a12....a1n

a21 a22....a2n

...........................

am1 am2....amn Representan los requisitos unitarios para cada variable de decisión.

c1, c2 ....cn Representan las contribuciones marginales (aporte que da a la función objetiva (FO), cada unidad de los elementos representados por las variables de decisión).

b1, b2 ......bn Representan las disponibilidades o las exigencias

Cada una de las desigualdades y/o ecuaciones representa una restricción del problema.

Tienen su origen en las limitaciones de recursos (insumos) o en las exigencias mínimas a cumplir (normas).

Para una restricción de limitación usamos  y para una de exigencia se usa .

Los valores bj, donde j = 1, 2,3..., m representan, o el límite máximo de disponibilidad del i-ésimo recurso o el mínimo exigido para una cierta norma a cumplir.

Cada uno de los coeficientes aij, se llama requerimiento técnico del artículo representado por la variable Xi, y forman la matriz principal del sistema.

El otro conjunto de restricciones (Xi  0), limitan a los valores de las variables de decisiones (VD) a ser no negativas.

Planteamiento de modelos

Lo primero que tenemos que hacer al tener un problema es construir el modelo de PL

Resumamos los pasos para la construcción de un modelo de PL

Definición de las variables de decisión (VD).

Definición del objetivo o meta en términos de sus variables de decisión.

FO: Maximizar o Minimizar.

Definición de las restricciones: De limitaciones o de exigencias.

Restringir todas las variables de decisión para que no sean negativas.

Ejemplo 1: (Problema de producción de la FMM)

La fábrica de muebles Masaya (FMM) es especialista en la producción de dos clases de comedores muy de moda en Centro América: Virginiano y Masaya.

La FMM logra una utilidad (precio neto de venta - costos variables de fabricación) de $200 y $240 de cada tipo respectivamente

La FMM ha experimentado una alta demanda de ambos comedores, en consecuencia, el gerente cree que puede vender todos los comedores que produzca

Los comedores requieren tiempo de procesamiento en los departamentos de construcción y de pintura. Los requerimientos y capacidades en horas diarios están resumidos en la siguiente tabla:

Departamento Tipo de comedor

Virginiano Masaya Capacidad (horas)

Construcción 6 12 120

Pintura 8 4 64

Utilidad unitaria 200 240

El modelo será entonces

VD: Sean X1 = número de comedores tipo Virginiano a producir

X2 = número de comedores tipo Masaya a producir

FO: (Max.) Z = 200X1 + 240 X2 (Utilidad)

s.a.

6 X1 + 12 X2  120 (Disponibilidad (h / Dpto. Construcción)

8 X1 + 4 X2  64 (Disponibilidad (h / Dpto. Pintura)

X1, X2  0

Ejemplo 2 (TIR):

Una empresa estatal tiene $12.000.000 para invertir en tales proyectos y desea saber cuánto invertir en cada uno de ellos con el objetivo lógico de maximizar la utilidad generada por la TIR global.

Por razones de riesgo no se debe invertir más del 30% del total en los proyectos I y II. Por razones de carácter social se debe invertir por lo menos el 40% en los proyectos I y III en conjunto.

Proyecto TIR

I 17%

II 18%

III 12%

IV 14%

Solución

VD: Sean X1: Cantidad de $ a invertir en el proyecto I

X2: Cantidad de $ a invertir en el proyecto II

X3: Cantidad de $ a invertir en el proyecto III

X4: Cantidad de $ a invertir en el proyecto IV

FO: (Max) Z = 17 X1 + 18 X2 + 12 X3 + 14 X4 (ganancia

s.a.

X1 + X2 + X3 +

...