Marzo 2021

www.utec.edu.uy

Instituto Tecnológico Regional

Norte

8cto. Semestre

Investigación Operativa
ITR Norte – Avda. Guido Machado km 496 – Ruta 5
ITRN 2022

Formulación general y modelado de

problemas con PL
Investigación Operativa
 Objetivos

 Comprender como se realiza la estructuración matemática de

problemas
 Realizar el modelado de algunos problemas de programación
lineal clásicos
 Historia de la Programación Lineal

 En 1939 Kantorovich formula rigurosamente

un problema de programación lineal en el
trabajo “Métodos Matemáticos de
Organización y planificación de la producción
” pero no presenta un algoritmo de resolución
 Historia de la Programación Lineal

 Dantzig trabajo en el Pentágono como

consejero matemático donde era
frecuentemente llamado para resolver
problemas de planificación
 Propone el Método Simplex que permitió la
solución de problemas de optimización de
diversos tipos
 Naturaleza de la programación lineal

“Asignar de forma óptima, recursos limitados a actividades

que compiten entre sí, es decir, elegir el nivel de ciertas
actividades que compiten por recursos escasos necesarios
para realizarlas”
 Problema 1-Mix de Producción

En un taller metalúrgico se fabrican dos tipos de piezas A y B, que

deben seguir los siguientes procesos:
1. Estampado en hojas metálicas
2. Soldado
3. Pintado
La operación de estampado consiste en preparar partes idénticas
que luego serán soldadas de a pares, formando la pieza A. El
mismo proceso se realiza para la pieza B.
 Problema 1-Mix de Producción

Los insumos de equipos son los siguientes, para la realización de

cada una de las operaciones (expresados en segundos por pieza)

La utilidad unitaria es de $ 4 para la pieza A y $ 3 para la pieza B.

Se desea establecer el programa semanal de producción que
maximice la utilidad del taller con respecto a las piezas consideradas.
 Modelando problemas por medio de la Programación lineal

 Definición de las actividades

 Definición de los recursos
 Calculo de los coeficientes de insumo/producción
 Determinación de las condiciones externas
 Formalización del modelo
 Modelando problemas por medio de la Programación lineal

 Definición de las actividades

Luego del análisis del problema, las actividades que lo componen

son definidas. A cada actividad se asocia una unidad de medida
 Modelando problemas por medio de la Programación lineal

 Definición de los recursos

Considerando los insumos disponibles dentro de cada actividad se
determina los recursos que están siendo usados y producidos en
cada una.
 Modelando problemas por medio de la Programación lineal

 Cálculo de los coeficientes de insumo/producción

Se establece como las actividades y los recursos están relacionados
en términos de los recursos necesarios por unidad de actividad
producida
 Modelando problemas por medio de la Programación lineal

 Determinación de las condiciones externas

Considerando que los recursos son limitados, se determina la
cantidad de recursos disponibles para el proceso de modelado. Son
las llamadas condiciones externas del modelo
 Modelando problemas por medio de la Programación lineal

 Formalización del modelo

Consiste en asociar cantidades no negativas 𝑥1 , 𝑥2 , ⋯ , 𝑥𝑛 a cada
una de las actividades , escribir las ecuaciones de equilibrio e
indicar el uso de cada recurso
 Secuencia de pasos para modelar un problema de programación lineal

1. Identificar las variables del problema 𝑥1 , 𝑥2 , ⋯ , 𝑥𝑛

2. Identificar las constantes del problema 𝑐1 , 𝑐2 , ⋯ , 𝑐𝑛
3. Identificar los valores de los factores limitantes del problema 𝒃𝒊
4. Determinar la función objetivo
5. Establecer restricciones
6. No olvidar que las variables tienen que ser no negativas: 𝑥𝑛 ≥ 0
 Modelado- Problema 1

1. Elección de las variables de decisión:

𝑥𝑖 ≡ cantidad de piezas fabricadas del tipo A (𝑖 = 1) y
cantidad de piezas fabricadas del tipo B (𝑖 = 2)
 Modelado- Problema 1

2. Elaboración de la función Objetivo

𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑧 = 4𝑥1 + 3𝑥2

Utilidad de la producción del taller en función de las piezas

fabricadas del tipo A y del tipo B.
 Modelado- Problema 1
3. Formulación de las Restricciones
1) Restricción asociada al proceso de Estampado
3𝑥1 + 8𝑥2 ≤ 48000
2) Restricción asociada al proceso de Soldado
12𝑥1 + 6𝑥2 ≤ 42000

3) Restricción asociada al proceso de Pintado

9𝑥1 + 9𝑥2 ≤ 36000
4) Restricción de no negatividad
𝑥1 ≥ 0 , 𝑥2 ≥ 0
 Modelado- Problema 1

𝑀𝑎𝑥𝑖𝑚𝑖𝑧𝑎𝑟 𝑧 = 4𝑥1 + 3𝑥2

Sujeto a:
3𝑥1 + 8𝑥2 ≤ 48000
12𝑥1 + 6𝑥2 ≤ 42000
9𝑥1 + 9𝑥2 ≤ 36000
𝑥1 ≥ 0 , 𝑥2 ≥ 0
 Modelos de Programación Lineal

Ejemplo modelo Problema General

Tiempo de las tres etapas del 𝑚 recursos
proceso

Fabricación de 2 piezas 𝑛 actividades

Tasa de producción de la piezas Nivel de actividad 𝑗, 𝑥𝑗

Ganancia Medida global de desempeño 𝑍

 Modelos de Programación Lineal

Programación lineal

 Las variables de decisión son continuas

 Maximización (o minimización) de una función Objetivo lineal
con relación a las variables de decisión del modelo
 Se tiene en cuenta las restricciones del problema expresadas
por un sistema de ecuaciones o inecuaciones lineales asociadas
a las variables de decisión
 Problema 2

 Plan de asignación de un producto desde 3 proveedores

a 4 consumidores
 Representación de un problema de programación matemática

Maximizar :
𝑓(𝑥1 , 𝑥2 ) 𝑓 : función objetivo

Sujeto a : 𝑥1 , 𝑥2 : variables de decisión

ℎ(𝑥1 , 𝑥2 ) ≤ 0 ℎ: restricción
𝑥1 ≥ 0
𝑥2 ≥ 0

El problema es encontrar valores reales 𝑥1 𝑦 𝑥2 que satisfagan las restricciones, los cuales
hagan que 𝑓 tome un valor no menor que para cualquier otro par 𝑥1 𝑦 𝑥2
 𝑓 𝑥1 , 𝑥2 = 4

𝑋෠ = 0, 1 es la solución
0, 1 𝑓 𝑥1 , 𝑥2 = 0.5 del problema

ℎ 𝑥1 , 𝑥2 = 0

𝑓 𝑥1 , 𝑥2 = −2
𝑆

0, 0 1, 0
 Representación de un problema de programación matemática

Maximizar : Solución óptima maximal :

𝑓(𝑥1 , 𝑥2 ) Cuando la solución 𝑋෠ verifica 𝑓 𝑋෠ ≥ 𝑓 𝑋 ∀ 𝑋 ∈ 𝑆
Sujeto a : Solución óptima minimal :
ℎ(𝑥1 , 𝑥2 ) ≤ 0 cuando la solución 𝑋෠ verifica 𝑓 𝑋෠ ≤ 𝑓 𝑋 ∀ 𝑋 ∈ 𝑆
𝑥1 ≥ 0
𝑥2 ≥ 0 Región factible :
𝑆= 𝑥1 , 𝑥2 : ℎ 𝑥1 , 𝑥2 ≤ 0 , 𝑥1 ≥ 0, 𝑥2 ≥ 0
Solución factible: Una solución 𝑋 tal que 𝑋 ∈ 𝑆
 𝑛
En un problema general de PL:
𝑀𝑖𝑛 𝑧 = ෍ 𝑐𝑗 ∙ 𝑥𝑗
𝑗 Función objetivo y restricciones
𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 ∶ son lineales
𝑛

෍ 𝑎𝑖𝑗 ∙ 𝑥𝑗 = 𝑏𝑖 , 𝑖 = 1, ⋯ , 𝑘
𝑗
𝑛

෍ 𝑎𝑖𝑗 ∙ 𝑥𝑗 ≥ 𝑏𝑖 , 𝑖 = 𝑘 + 1, ⋯ , 𝑚
𝑗
𝑥𝑗 ≥ 0 𝑗 = 1, . . . , 𝑙
El problema es encontrar valores reales 𝑥1 𝑦 𝑥2 que satisfagan las restricciones, los cuales
hagan que 𝑓 tome un valor no menor que para cualquier otro par 𝑥1 𝑦 𝑥2
 Región factible de un PL

La región factible de un problema de PL es un

conjunto poliédrico

En un espacio tridimensional: 3 variables de decisión

 𝑛 Restricciones de igualdad
෍ 𝑎𝑖𝑗 ∙ 𝑥𝑗 = 𝑏𝑖 , 𝑖 = 1, ⋯ , 𝑘
𝑗

෍ 𝑎𝑖𝑗 ∙ 𝑥𝑗 ≥ 𝑏𝑖 , 𝑖 = 𝑘 + 1, ⋯ , 𝑚
𝑗 Restricciones de desigualdad ≥
 PL en forma canónica

𝑀𝑖𝑛 𝑧 = ෍ 𝑐𝑗 ∙ 𝑥𝑗
Todas las restricciones están
𝑗
𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 ∶ expresadas como una desigualdad ≥
𝑃𝐿𝑐 𝑛

෍ 𝑎𝑖𝑗 ∙ 𝑥𝑗 ≥ 𝑏𝑖 , 𝑖 = 1, ⋯ , 𝑚
𝑗
𝑥𝑗 ≥ 0 𝑗 = 1, . . . , 𝑙
 PL en forma standard

𝑀𝑖𝑛 𝑧 = ෍ 𝑐𝑗 ∙ 𝑥𝑗
Todas las restricciones están
𝑗
𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 ∶ expresadas como una igualdad=
𝑃𝐿𝑐 𝑛

෍ 𝑎𝑖𝑗 ∙ 𝑥𝑗 = 𝑏𝑖 , 𝑖 = 1, ⋯ , 𝑚
𝑗
𝑥𝑗 ≥ 0 𝑗 = 1, . . . , 𝑙
 PL en notación vectorial

𝑥1 Variables de decisión
𝑥2
𝑥= ⋮
𝑥𝑛
𝑐 𝑇 = 𝑐1 , 𝑐2 , ⋯ , 𝑐𝑛
Coeficientes de la función objetivo
𝑏1
𝑏2
𝑏=
⋮
𝑏𝑚 Coeficientes de las restricciones
𝑎11 ⋯ 𝑎1𝑛
𝐴= ⋮ ⋱ ⋮
𝑎𝑚1 ⋯ 𝑎𝑚𝑛
 PL en notación vectorial

𝑀𝑖𝑛 𝑧 = 𝑐 𝑇 𝑥 𝑀𝑖𝑛 𝑧 = 𝑐 𝑇 𝑥
𝑠𝑢𝑗𝑒𝑡𝑜 𝑎 𝑠𝑢𝑗𝑒𝑡𝑜 𝑎
𝑃𝐿𝑐 𝑃𝐿𝑠 )
𝐴𝑥 ≥ 𝑏 𝐴𝑥 = 𝑏 𝑏 ≥ 0
𝑥≥0 𝑥≥0
 Transformación de un PL de minimización a un PL de maximización

Un problema de PL standard de minimización puede ser

transformado en un problema de maximización de PL:

𝑀𝑖𝑛 𝑧 = 𝑐 𝑇 𝑥 es equivalente a 𝑀á𝑥 − 𝑧 = −𝑐 𝑇 𝑥

Se multiplica la función objetivo por (-1)

 Transformación de restricciones ( ≤) a restricciones de ( =)

Una desigualdad puede llevarse a una igualdad introduciendo una

nueva variable no negativa, llamada variable de holgura

σ𝑛𝑗=1 𝑎𝑖𝑗 ∙ 𝑥𝑗 +𝑦 = 𝑏𝑖
σ𝑛𝑗 𝑎𝑖𝑗 ∙ 𝑥𝑗 ≤ 𝑏𝑖 se transforma ൝
𝑦≥0

La variable 𝑦 se llama variable de holgura

 Transformación de restricciones ( ≥) a restricciones de ( =)

Una desigualdad puede llevarse a una igualdad introduciendo

una nueva variable no negativa, llamada variable de exceso .

σ𝑛
𝑛 𝑗=1 𝑎𝑖𝑗 ∙ 𝑥𝑗 −𝑦 = 𝑏𝑖
La restricción σ𝑗=1 𝑎𝑖𝑗 ∙ 𝑥𝑗 ≥ 𝑏𝑖 se transforma en ൝
𝑦≥0
 Transformación de restricciones de ( ≥) a restricciones de ( ≤)

Una restricción del tipo ≥ puede ser transformada en otro del

tipo ≤ por medio de la multiplicación de ambos lados por (−1)
 De restricciones de igualdad a restricciones de desigualdad

El sistema de ecuaciones 𝐴𝑥 = 𝑏 puede ser fácilmente

transformado en dos desigualdades
𝐴𝑥 ≤ 𝑏
ቊ
𝐴𝑥 ≥ 𝑏
 Transformación de variables libres a variables con restricción de signo

Una variable libre puede, de todas formas, ser transformada en

una variable con restricción de signo si se la escribe como
diferencia entre dos variables positivas

𝑥 = 𝑥 + − 𝑥 − , 𝑥 + , −𝑥 − ≥ 0
 Ejemplo prototípico / optimización con PL

Planificación de la producción de equipos de una empresa para el

sector forestal

• Problema especifico: determinar la cantidad a producir de dos

equipos
( nombrados E y F)

• Objetivo es maximizar las ganancias.

• El proceso tiene dos requerimientos fundamentales

1. Tratamiento en dos departamentos de la planta A y B
2. Testeo
 Ejemplo/ optimización con PL

Datos generales sobre el proceso

Equipo Ganancia ($) Total ( Total de horas Total de testeo Independencia
equipos) de tratamiento (hr) entre los
equipos
E 5000 156 en Dep A y Por lo menos
10 160 en Dep B 135
F 4000 1F a cada 5E

Datos específicos sobre los equipos

Tratamientos Testeo
Equipo Dep. A (hr) Dep. B( hr) Testeo ( hr)
E 10 20 30
F 15 10 10