Programación Lineal
Tema
Yamil Huais
Docente
Proyectos, dirección de obras y valuaciones
Programación Lineal
Definición: Técnica matemática utilizada para resolver una clase
amplia de problemas de optimización.
Problemas a resolver:
• Formulación de mezclas (ej: alimentación, fabricación, etc)
• Control de inventario y planeación de producción.
• Distribución y logística.
• Asignación de personal.
Programación Lineal
Objetivo: Maximizar o minimizar una función lineal de n variables
reales, sujeta a m restricciones. Generalmente se requiere
maximizar el ingreso o la ganancia o minimizar los costos.
Métodos:
• Simplex
• Excel
• Gráfico
Problema
Office Company fabrica muebles de oficina. El Dpto producción
produce 2 escritorios, el estándar y el premium. Un escritorio
estándar requiere 10 𝑝𝑖𝑒𝑠 2 de pino, 4 de cedro y 15 de ombú. Para
un escritorio Premium se requieren 20 𝑝𝑖𝑒𝑠 2 de pino, 15 de cedro y
10 de ombú. Los escritorios producen ganancias de 90 U$D y 110
U$D respectivamente. En la actualidad la empresa dispone de 200
𝑝𝑖𝑒𝑠 2 de pino, 128 de cedro y 220 de ombú. Han recibido pedidos
de ambos escritorios y le gustaría producir la cantidad de ambos
que maximice su ganancia. ¿Cuántas debe producir de cada uno?
Problema - Datos
Pino Cedro Ombú
Estándar 10 4 15
Premium 20 15 10
Disponibilidad 200 128 220
Ganancia
Estándar 90
Premium 115
Formulación del problema - Planteo
¿Cuál es la decisión?
Decidir que valores deben tomar las variables de decisión para optimizar o
minimizar dichas variable.
¿Cuándo una decisión está tomada?
Una decisión esta tomada cuando se le asigna un valor a cada variable.
¿Cuál es la mejor decisión?
Una decisión será mejor que otra si cumple con un criterio dado. Es el
objetivo el que decide. Por ejemplo: algunos criterios serían minimizar los
costos, o usar la menor cantidad de horas hombre posible, o minimizar el
tiempo, etc.
Formulación del problema - Planteo
En el caso del ejemplo:
¿Cuál es la decisión?
Decidir qué cantidades de escritorios estándares y Premium se deben
producir para maximizar la ganancia.
¿Cuándo una decisión está tomada?
La decisión estará tomada cuando definamos las cantidades de escritorios de
cada tipo que se van a producir.
¿Cuál es la mejor decisión?
Nuestra mejor decisión será aquella en la que las cantidades producidas de
cada escritorio maximice la ganancia.
Formulación del problema – Pasos para el planteo
1° Paso
Identificar variables de decisión
𝑋1 = 𝐶𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑒𝑠𝑐𝑟𝑖𝑡𝑜𝑟𝑖𝑜𝑠 𝑒𝑠𝑡𝑎𝑛𝑑𝑎𝑟
𝑋2 = 𝐶𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑒𝑠𝑐𝑟𝑖𝑡𝑜𝑟𝑖𝑜𝑠 𝑝𝑟𝑒𝑚𝑖𝑢𝑚
2° Paso
Identificar función objetivo
Definición: Cantidad que se desea maximizar o minimizar
En el ejemplo el objetivo es maximizar la ganancia total cuando se
producen X1 escritorios estándares y X2 escritorios Premium.
Formulación del problema – Pasos para el planteo
Función Objetivo
Ganancia
Estándar 90 𝑍 = 90 𝑋1 + 115 𝑋2
Premium 115
Formulación del problema – Pasos para el planteo
3° Paso
Identificar las restricciones
Pino Cedro Ombú
Estándar 10 4 15 10𝑋1 + 20𝑋2 ≤ 200 (𝑃𝐼𝑁𝑂)
Premium 20 15 10 4𝑋1 + 16𝑋2 ≤ 128 (𝐶𝐸𝐷𝑅𝑂)
15𝑋1 + 10𝑋2 ≤ 220 (𝑂𝑀𝐵Ú)
Disponibilidad 200 128 220
𝑋1 ≥ 0
Restricciones de no negatividad 𝑋2 ≥ 0
Formulación del problema – Pasos para el planteo
Problema planteado
Variables
𝑋1 = 𝐶𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑒𝑠𝑐𝑟𝑖𝑡𝑜𝑟𝑖𝑜𝑠 𝑒𝑠𝑡𝑎𝑛𝑑𝑎𝑟
𝑋2 = 𝐶𝑎𝑛𝑡𝑖𝑑𝑎𝑑 𝑑𝑒 𝑒𝑠𝑐𝑟𝑖𝑡𝑜𝑟𝑖𝑜𝑠 𝑝𝑟𝑒𝑚𝑖𝑢𝑚
Función Objetivo
𝑍 = 90 𝑋1 + 115 𝑋2
Restricciones
10𝑋1 + 20𝑋2 ≤ 200
4𝑋1 + 16𝑋2 ≤ 128
15𝑋1 + 10𝑋2 ≤ 220
𝑋1 ≥ 0
𝑋2 ≥ 0
Formulación general del problema
𝑆𝑒𝑎𝑛 𝑋1 , 𝑋2 , … 𝑋𝑛 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑠 𝑑𝑒 𝑑𝑒𝑐𝑖𝑠𝑖ó𝑛 𝑦 𝑚 𝑟𝑒𝑠𝑡𝑟𝑖𝑐𝑐𝑖𝑜𝑛𝑒𝑠 𝑑𝑒 𝑟𝑒𝑐𝑢𝑟𝑠𝑜𝑠
𝐹𝑢𝑛𝑐𝑖ó𝑛 𝑜𝑏𝑗𝑒𝑡𝑖𝑣𝑜
𝑍 = 𝐶1 𝑋1 + 𝐶2 𝑋2 + ⋯ + 𝐶𝑛 𝑋𝑛
𝑅𝑒𝑠𝑟𝑖𝑐𝑐𝑖𝑜𝑛𝑒𝑠
𝑎11 𝑋1 + 𝑎12 𝑋2 + ⋯ + 𝑎1𝑛 𝑋𝑛 ≤ 𝑏1
𝑎21 𝑋1 + 𝑎22 𝑋2 + ⋯ + 𝑎2𝑛 𝑋𝑛 ≤ 𝑏2
𝑎𝑚1 𝑋1 + 𝑎𝑚2 𝑋2 + ⋯ + 𝑎𝑚𝑛 𝑋𝑛 ≤ 𝑏𝑚
𝑋1 , 𝑋2 , 𝑋𝑛 ≥ 0
Condiciones de la programación lineal
• Proporcionalidad: Incrementos de una unidad en las variables de decisión provocan cambios
proporcionales en la función objetivo y en las restricciones. Las cantidades cambian en
proporciones fijas. Por ejemplo, si cuesta $10 producir una unidad, debe costar $20 producir dos
y $100 producir cien unidades.
• Divisibilidad: La suposición de divisibilidad requiere que cada variable pueda tomar valores
fraccionarios.
• No negatividad: Todas las variables de decisión serán no negativa.
• Determinista: Se asume que, una vez determinados los coeficientes que intervienen, no admiten
variaciones. Por ejemplo: se estima que el costo de producir una unidad es de 5 $/un. Es una
aseveración determinista.
Método gráfico
Graficar en un sistema de ejes cartesianos las desigualdades lineales
representadas por las restricciones.
10𝑋1 + 20𝑋2 ≤ 200
4𝑋1 + 16𝑋2 ≤ 128
15𝑋1 + 10𝑋2 ≤ 220
𝑋1 ≥ 0
𝑋2 ≥ 0
Método gráfico
𝑹𝒆𝒔𝒕𝒓𝒊𝒄𝒄𝒊ó𝒏 1
10𝑋1 + 20𝑋2 ≤ 200
Método gráfico
𝑹𝒆𝒔𝒕𝒓𝒊𝒄𝒄𝒊ó𝒏 2
4𝑋1 + 16𝑋2 ≤ 128
Método gráfico
𝑹𝒆𝒔𝒕𝒓𝒊𝒄𝒄𝒊ó𝒏 𝟑
15𝑋1 + 10𝑋2 ≤ 220
Método gráfico
𝑹𝒆𝒔𝒕𝒓𝒊𝒄𝒄𝒊𝒐𝒏𝒆𝒔 𝒅𝒆 𝒏𝒐 𝒏𝒆𝒈𝒂𝒕𝒊𝒗𝒊𝒅𝒂𝒅
𝑋1 ≥ 0
𝑋2 ≥ 0
Método gráfico
Región factible
• La región factible es un conjunto
convexo.
• Las cotas de la región son rectas.
• Estas rectas se intersecan en los
llamados puntos extremos.
• Todos los puntos de la región son
soluciones factibles.
Método gráfico
Función Objetivo
La función objetivo es una familia de rectas.
𝑍 = 90 𝑋1 + 115 𝑋2
𝑍 90
𝑋2 = + 𝑋
115 115 1
Infinitas rectas paralelas se forman, dando infinitos valores a Z
Dando un valor arbitrario a Z, por ejemplo 𝑍 = 3105, se puede graficar una
recta Z, que será la recta 𝑍 = 3105
Las demás Z, serán rectas paralelas y con Z diferentes.
Método gráfico
Función Objetivo
Método gráfico
Una propiedad importante de los problemas de programación lineal es que la solución
óptima siempre se presenta en un punto extremo de la región factible (sin importar la
fución objetivo)
Si en el caso del ejemplo reemplazamos (𝑋1 , 𝑋2 ) correspondiente a cada uno de los
cinco puntos extremos, obtendremos el 𝑋𝑚𝑎𝑥 .
El método grafico consiste en dibujar la función objetivo, dándole un valor cualquiera,
y comenzar a desplazar la recta con una regla hasta que toque el primer punto
extremos. Dicho punto (𝑋1 , 𝑋2 ) es el que maximiza la función.
Método gráfico
Resolución gráfica
Moviendo Z, se llega al punto extremo
donde dos restricciones se igualan,
10𝑋1 + 20𝑋2 ≤ 200
15𝑋1 + 10𝑋2 ≤ 220
Dichas rectas se igualan en el punto:
𝑋1 , 𝑋2 = (12,4)
Casos especiales
Múltiples soluciones
Casos especiales
Problemas sin soluciones
Casos especiales
Problemas no acotados
Programación Lineal
Casos prácticos
Tema
Yamil Huais
Docente
Proyectos, dirección de obras y valuaciones
Formulación de mezclas
Alimentación
Un granjero cría cerdos para la venta y desea
determinar la cantidad de los distintos tipos de
alimento debe dar a cada cerdo para cumplir
requisitos nutricionales a un costo mínimo. En la
siguiente tabla se dan las unidades de cada clase de
ingredientes nutritivos básicos contenido en un
kilogramos de cada tipo de alimento, junto con los
requisitos nutricionales diarios y los costos de los
alimentos.
Formulación de mezclas
Alimentación
Ing. Kg de Mínimo
Kg de maíz Kg de grasa
Nutricional alfalfa diario
Carbohidra
90 20 40 200
tos
Proteínas 30 80 60 180
Vitaminas 10 20 60 150
Costos 42 36 30
Formulación de mezclas
Alimentación
El problema de transporte
Una empresa energética dispone de cuatro plantas de
generación para satisfacer la demanda diaria de 4 ciudades. La
planta 1 puede dar hasta 80 mKW/día, la planta 2 hasta 30
mKW/día, la planta 3 hasta 60 mKW/día, la planta 4 hasta 45
mKW/día. La ciudad 1 tiene una demanda de 70 mKW/día, la
ciudad 2 de 40 mKW/día, la ciudad 3 de 70 mKW/día, la ciudad
4 de 35 mKW/día.
El problema de transporte
Los costos asociados al envío de suministro energético por cada
millón de KW entre cada planta y ciudad son:
CIUDAD
1 2 3 4
1 5 2 7 3
PLANTA
2 3 6 6 1
3 6 1 2 4
4 4 3 6 6
Formular el modelo de programación lineal que satisfaga las
necesidades de todas las ciudades al tiempo que minimice los
costos de transporte
El problema de transporte
El problema de transporte
Programación de turnos
Un hospital enfrenta problemas con el horario de trabajo de sus
enfermeros. Se desea minimizar el número total de trabajadores
sujetos a un número específico de enfermeras durante cada
período del día.
Número
Período Turno del Día requerido de
enfermeros
1 8:00 a 10:00 10
2 10:00 a 12:00 8
3 12:00 a 14:00 9
4 14:00 a 16:00 11
5 16:00 a 18:00 13
6 18:00 a 20:00 8
7 20:00 a 22:00 5
8 22:00 a 24:00 3
Programación de turnos
Dado que cada enfermero trabaja jornadas de 8 hs diarias,
pueden comenzar a trabajar al comienzo de cualquieras de los
primeros cinco periodos: 8:00, 10:00, 12:00, 14:00, 16:00.
Adicionalmente, no se necesita ningun enfermero que
comience a trabajar después de las 16, dado que su horario se
extenderá hasta después de la media noche cuando no son
necesarias. ¿Cuántas enfermeras se deben reportar de forma
tal de cumplir con los requerimientos en la tabla anterior?
Programación de turnos
Programación de turnos
SOLVER
Programación Lineal en Excel
Pasos a seguir para habilitar el Solver
Ejemplo de aplicación - Solver
Inversión: Disponemos de 210.000 pesos para invertir
en bolsa. Nos recomiendan dos tipos de acciones. Las
del tipo A, que rinden el 10% y las del tipo B, que
rinden el 8%. Decidimos invertir un máximo de
130.000 pesos en las del tipo A y como mínimo 60.000
en las del tipo B. Además queremos que la inversión
en las del tipo A sea menor que el doble de la inversión
en B. ¿Cuál tiene que ser la distribución de la inversión
para obtener el máximo interés anual?
Ejemplo de aplicación - Solver
Ejemplo de aplicación - Solver
Armado del modelo
Ejemplo de aplicación - Solver
Ejemplo de aplicación - Solver
Ejemplo de aplicación - Solver
Ejemplo de aplicación - Solver
Ejemplo de aplicación - Solver
Ejemplo de aplicación - Solver
Ejemplo de aplicación - Solver
Ejemplo de aplicación - Solver
Ejemplo de aplicación - Solver
Error de traducción!!
Es “REDUCCION”
Error de traducción!!
Es “REDUCCION”