Programacion lineal

Optimización y Programación Lineal
Programación Lineal
Departamento de Matemáticas

ITESM

Programación Lineal

TC3001 - p. 1/16

Introducción
s

s

s

Programación Lineal es una herramienta para resolver problemas de optimización. Fue desarrollada en 1947 por George Dantzig (1914-2005). Es una herramienta utilizada por las grandes compañías.

´ Introduccion Ejemplo 1 ´Modelacion Suposiciones Conceptos LP Ejemplo 2 Ejemplo 3 Ejemplo 4

Programación Lineal

TC3001 - p. 2/16

Ejemplo
Una compañía fabrica dos tipos de productos, el tipo A y el tipo B. Un producto A se vende en $27 y requiere materia prima por un costo de $10. El costo de mano de obra de cada producto A es de $14. Por otro lado, un producto B se vende en $21 y requiere materia prima por un costode $9. El costo de mano de obra de cada producto B es de $10. La manufactura de los productos A y B requiere dos tipos de labor: carpintería y acabado. Cada producto A requiere 2 horas de acabado y 1 de carpintería, mientras que un producto B requiere 1 hora de acabado y 1 hora de carpintería. Cada semana la campañía dispone de 100 horas para acabado y 80 horas para carpintería. Mientras que lademanda de productos B es ilimitada, se estima que la compañía vende a lo más 40 productos A por semana. La compañía desea hacer un plan de producción semanal que maximice la ganancia semanal.
´ Introduccion Ejemplo 1 ´ Modelacion Suposiciones Conceptos LP Ejemplo 2 Ejemplo 3 Ejemplo 4

Programación Lineal

TC3001 - p. 3/16

Modelación
´ ´ 1. Determinacion de las variables de decision
´Introduccion Ejemplo 1 ´ Modelacion Suposiciones Conceptos LP Ejemplo 2 Ejemplo 3 Ejemplo 4

Programación Lineal

TC3001 - p. 4/16

Modelación
´ ´ 1. Determinacion de las variables de decision
s s
´ Introduccion Ejemplo 1 ´ Modelacion Suposiciones Conceptos LP Ejemplo 2 Ejemplo 3 Ejemplo 4

x1 = Cuántos productos A por semana deben producirse y x2 = cuántos productos B

´ ´ 2.Determinacion de la funcion Objetivo

Programación Lineal

TC3001 - p. 4/16

Modelación
´ ´ 1. Determinacion de las variables de decision
s s
´ Introduccion Ejemplo 1 ´ Modelacion Suposiciones Conceptos LP Ejemplo 2 Ejemplo 3 Ejemplo 4

x1 = Cuántos productos A por semana deben producirse y x2 = cuántos productos B Maximizar la ganancia = Venta - Costo = z = 3 x1 + 2 x2

´ ´ 2. Determinacionde la funcion Objetivo

3. Uso de Restricciones

Programación Lineal

TC3001 - p. 4/16

Modelación
´ ´ 1. Determinacion de las variables de decision
s s
´ Introduccion Ejemplo 1 ´ Modelacion Suposiciones Conceptos LP Ejemplo 2 Ejemplo 3 Ejemplo 4

x1 = Cuántos productos A por semana deben producirse y x2 = cuántos productos B Maximizar la ganancia = Venta - Costo = z = 3 x1 + 2 x2´ ´ 2. Determinacion de la funcion Objetivo

3. Uso de Restricciones
s s s

Carpintería: 2 x1 + x2 ≤ 100 Acabado: x1 + x2 ≤ 80 Demanda: x1 ≤ 40

4. Uso de Restricciones de Signo

Programación Lineal

TC3001 - p. 4/16

Modelación
´ ´ 1. Determinacion de las variables de decision
s s
´ Introduccion Ejemplo 1 ´ Modelacion Suposiciones Conceptos LP Ejemplo 2 Ejemplo 3 Ejemplo 4

x1= Cuántos productos A por semana deben producirse y x2 = cuántos productos B Maximizar la ganancia = Venta - Costo = z = 3 x1 + 2 x2

´ ´ 2. Determinacion de la funcion Objetivo

3. Uso de Restricciones
s s s

Carpintería: 2 x1 + x2 ≤ 100 Acabado: x1 + x2 ≤ 80 Demanda: x1 ≤ 40 x1 ≥ 0 x2 ≥ 0

4. Uso de Restricciones de Signo
s s

Programación Lineal

TC3001 - p. 4/16

deProporcionalidad y de Aditividad
1. La contribución en la función objetivo de cada variable de decisión es proporcional a su valor. 2. La contribución en la función objetivo de cada variable es independiente de los valores de las otras variables de decisión. 3. La contribución en cada restricción de cada variable de decisión es proporcional a su valor. 4. La contribución en cada restricción de cada...