Programación lineal

UNIDAD II
PROGRAMACIÓN LINEAL

Objetivo de la unidad
El alumno conocerá los fundamentos de la programación lineal y los aplicará en la resolución de problemas de optimización.

Introducción
Lineal:
Significa que todas las funciones matemáticas del modelo deben ser funciones lineales.

Programación Lineal : Trata la planeación de las actividades para obtener un resultado óptimo, estoes el resultado que mejor alcance la meta especificada (según el modelo matemático) entre todas las alternativas de solución.

¿Qué es Programación Lineal?
• Es un método de resolución de problemas desarrollado para situaciones que implican la maximización o minimización de una función lineal, sujeta a restricciones lineales que limitan el grado al cual se puede buscar un objetivo. • Dentro desus aplicaciones está el de asignar recursos limitados entre actividades competitivas de la mejor manera posible (es decir, en forma óptima).

¿Qué es optimización?
• Por técnica de optimización se entiende como una estrategia de que trata de maximizar las utilidades o minimizar los costos. • Por lo tanto, el propósito de la PL es el de utilizar en forma eficiente los recursos con que secuenta para el logro de metas establecidas. • La PL pertenece a un área más grande denominada “Programación Matemática”.

Terminología común para programación lineal
Ejemplo prototipo
Capacidad de producción de las plantas: 3 plantas Fabricación de productos: 2 productos Taza de producción del producto j, xj Ganancia Z

Problema general
Recursos m recursos Actividades n actividades Nivel de laactividad j, xj Medida global de efectividad Z

Símbolos que se usan para denotar los distintos componentes de un modelo de programación lineal
Z = valor de la medida global de efectividad.
Xj = nivel de la actividad j (para j= 1,2,…,n). Cj = incremento en Z obtenido al aumentar una unidad en el nivel de la actividad j. Bi = cantidad de recurso i disponible para asignar a las actividades(para i=1,2,…,m). Aij= cantidad del recurso i consumido por cada unidad de la actividad j.

Forma estándar del modelo
Maximizar Z=c1x1+c2x2+…+cnxn,

Sujeta
a las restricciones

a11x1+a12x2+…+a1nxn < b1 a21x1+a22x2+…+a2nxn < b2
.

.

am1x1+am2x2+…+amnxn

< bm,

.

Datos necesarios para un modelo de programación lineal que maneja la asignación de recursos a actividades
Consumo derecursos por unidad de actividad Actividad Recurso Cantidad de recursos

1 a11 a21 … am1

2 a12 a22 … am2 c2

… … … … … …

n a1n a2n … amn cn

disponibles

b1 b2 . . . bm

Contribución a Z por unidad de actividad

c1

y

x1>0, x2>0, …, xn>0.

La función que desea maximizar, c1x1+c2x2+…+cnxn, se llama función objetivo. De manera parecida, las restricciones xj>0 se conocen comorestricciones de no negatividad.

• Utilidad • Eficiencia Maximización • Beneficios. • Producción. • Calidad • Materia prima Función objetivo Restricciones – limitaciones o requerimientos • Costos • Tiempo

• Dinero
• Recursos humanos

Minimización

• Desperdicios. • Inversión.

Terminología para las soluciones del modelo
Una solución factible es aquella para la que todas lasrestricciones se satisfacen.

Una solución no factible es un solución para la que al menos una restricción se viola.
La región factible es la colección de todas las soluciones factibles.

Una solución óptima es una solución factible que proporciona el valor mas favorable de la función objetivo.

Ejemplo prototipo
Debido a la reducción en las ganancias, la alta administración de WYNDOR GLASS CO.Descontinuará varios productos no rentables y se dejará libre una parte de la capacidad de producción para emprender la fabricación de 2 productos nuevos que tienen ventas potenciales grandes:

Producto 1: una puerta de vidrio de 8ft con marco de aluminio
Producto 2: una ventana de resbalón con marco de madera de 4x6ft El producto 1 requiere parte de la capacidad de producción en las plantas...