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

...