Optimización de Operaciones
Aplicadas
Dirección Sectorial Energía &
Sustentabilidad
Área Construcción
Sede Ñuñoa
U2 Problemas de programación lineal.
Consideraciones Generales
• La Programación Lineal resuelve un tipo muy especial de problema, en el cual todas las relaciones
entre las variables son lineales, tanto en las restricciones como en la Función Objetivo.
• Dado un conjunto de m inecuaciones lineales ó ecuaciones lineales, con n variables, se requiere
hallar valores no negativos de estas variables que satisfagan las restricciones y maximicen o
minimicen alguna función lineal de las variables llamada Función Objetivo.
Matematicamente:
Hallar Xj, j = 1, 2,. . . . . n tal que:
Maximice o Minimice Z = C1X1 + C2X2 +. . . + CjXj +. . .+ CnXn Función Objetivo
U2 Problemas de programación lineal.
Características de la P.L.
1. Linealidad asume que no puede haber términos así: X1X2 a14 X32 logX4 ex sin(x) X1/X2
2. Asume las propiedades aditivas y multiplicativas.
• Si una unidad tipo A necesita 3 horas en la máquina y una unidad tipo B necesita 2½ horas,
entonces ambas necesitan 5½ horas.
• Si una unidad tipo A necesita 2 hora en la máquina, entonces 10 unidades tipo A necesitan 20
horas.
3. La función que se va a optimizar (maximizar o minimizar) se llama Función Objetivo; fíjese que no
aparece ningún término independiente o constante. Los valores de las Xj son independientes de
cualquier constante.
Si la función objetivo tiene una constante como, por ejemplo: Z = 10 + 3X1 + 2X2 (aquí la constante
es 10), ella se ignora y se procede a optimizar: W = 3X1 + 2X2, una vez conocido el valor de W,
entonces Z = 10 + W
U2 Problemas de programación lineal.
Características de la P.L.
4. Cuando se dice que el problema tiene m restricciones, el valor de m no incluye las
restricciones de no negatividad.
5. Cualquier conjunto de Xj que satisface las m restricciones y la condición de no negatividad Xj ≥ 0; !j
se llama una solución factible al problema, de lo contrario es una solución no factible.
6. Una solución factible que optimiza la función objetivo se llama una solución factible óptima.
7. Usualmente hay un número infinito de soluciones factibles al problema, de todas estas, tiene que
hallarse una óptima.
U2 Problemas de programación lineal.
Tips para formular modelos matemáticos de P.L.
Identificar verbalmente las variables de decisión.
Exprese el objetivo del problema en palabras y después, mediante el lenguaje matemático, construya
una función (Función Objetivo) en términos de las variables de decisión y, cuidando que las unidades
sean homogéneas.
Exprese cada restricción en palabras.
No se puede olvidar colocar la restricción de no negatividad Xj ≥ 0.
Formúlelos con la rapidez que le sea posible y no lea en un problema más de lo que se le da
U2 Problemas de programación lineal.
Ejemplo: Problema de Producción
Cementos Bio-Bio tiene tres máquinas: A, B y C en las que puede fabricar dos productos: Hormigón
Simple (Producto 1) y Hormigón reforzado (Producto 2) ; Todos los productos deben ir a cada máquina
y cada uno va en el mismo orden: Primero a la máquina A, luego a la máquina B y por último a la
máquina C.
¿Qué cantidad de cada producto (1, 2) se debe manufacturar cada semana, para obtener la máxima
ganancia?
¿Cuántas horas por semana se deja de usar cada máquina?
U2 Problemas de programación lineal.
Solución
a. Definir las variables:
Xj = Unidades a producir por semana del producto j-ésimo (j1=Producto 1,
j2=Producto 2)
b. Función objetivo: Maximizar Z = X1 + 3/2 X2
c. Restricciones
2X1+ 2X2 ≤ 16 Restricción debida a las horas disponibles por semana de la MQ A
X1+ 2X2 ≤ 12 Restricción debida a las horas disponibles por semana de la MQ B
4X1+ 2X2 ≤ 28 Restricción debida a las horas disponibles por semana de la MQ C
d. Condición de no negatividad Xj ≥ 0; j = 1, 2
U2 Problemas de programación lineal.
Métodos de Resolución: Método Gráfico
El método gráfico en programación lineal se utiliza para resolver problemas con dos variables, donde se
grafican las restricciones y la función objetivo en un plano cartesiano para encontrar la solución óptima. Este
método es visual y ayuda a comprender los conceptos básicos de optimización, aunque su aplicación es
limitada a problemas con pocas variables.
Pasos del método gráfico:
1. Graficar las restricciones: Cada restricción (desigualdad lineal) se representa como una línea en el plano
cartesiano. La zona factible, que representa todas las soluciones posibles, se encuentra delimitada por la
intersección de todas las restricciones.
2. Identificar la zona factible: Se determina la región del plano que satisface todas las restricciones al mismo
tiempo. Esta región puede ser un polígono convexo.
Graficar la función objetivo: La función objetivo (que se quiere maximizar o minimizar) también se representa
como una línea en el plano. Esta línea se desplaza para encontrar el punto óptimo dentro de la zona factible.
Encontrar la solución óptima: Se busca el punto de la zona factible que optimiza la función objetivo (el punto
más alejado en la dirección de maximización o minimización). Este punto suele ser un vértice de la zona
factible.
U2 Problemas de programación lineal.
Métodos de Resolución: Método Gráfico
Consideraciones:
Limitaciones:
El método gráfico solo es adecuado para problemas con dos variables, ya que es difícil visualizar más
dimensiones.
Región factible:
La región factible puede ser acotada (un polígono) o no acotada (con "aberturas"). En el caso de
regiones no acotadas, la solución óptima puede no existir o ser infinita.
Solución única o múltiple:
Un problema de programación lineal puede tener una solución única, múltiples soluciones (en un
segmento de la región factible) o ninguna solución (cuando la región factible es vacía o la función
objetivo no está acotada).
U2 Problemas de programación lineal.
Resolución mediante el método gráfico
Método Gráfico
16
4X
28 1 +
2X
14
12
2
≤
10
2X
1 +
16 2X
≤
8
2
4
X1 +
2X ≤
2
Región factible de 12 2
solución óptima
0
0 2 4 6 8 10 12 14
U2 Problemas de programación lineal.
Ejercicio N°1: Problema de Transporte de Material
Un camión de transporte tiene capacidad de transportar como máximo 9 toneladas y 30 m3 por viaje.
En un viaje desea transportar al menos 4 toneladas del material A y un peso del material B que no sea
inferior a la mitad del peso que transporta A. Sabiendo que cobra $800.000 por toneladas
transportadas de material A ya que ocupa un volumen de 2 m3 por tonelada y $600.000 por tonelada
transportada de material B ya que ocupa un volumen 1.5 m3 por tonelada.
¿Cómo se debe cargar el camión para obtener la ganancia máxima si para cada tonelada cargada
gasta en promedio $200.000 de gasolina?
U2 Problemas de programación lineal.
Solución
a. Definir las variables
b. Función objetivo
c. Restricciones
d. Condición de no negatividad
U2 Problemas de programación lineal.
Solución mediante Método Gráfico
U2 Problemas de programación lineal.
Ejercicio N°2: Problema de Producción
Una fábrica de hormigón produce dos tipos de hormigón A y B. El beneficio que arroja el hormigón A
es de $40.000/camión y el de B $60.000/camión. La producción diaria no puede superar 4000 m3 del
modelo A ni 3000 m3 del B debido a las condiciones producción de la planta.
El departamento de mercadeo informa que la demanda de acuerdo a los pedidos recibidos es de 600
m3 ¿Cuántas m3 de cada modelo debe producir la fábrica para obtener el máximo beneficio?
U2 Problemas de programación lineal.
Solución
a. Definir las variables
b. Función objetivo
c. Restricciones
d. Condición de no negatividad
U2 Problemas de programación lineal.
Solución mediante Método Gráfico
U2 Problemas de programación lineal.
Ejercicio N°3: Problema de
Construcción
La constructora Casas Ltda. se ha adjudicado la construcción de 100 casas.
El contrato la obliga a construir dos tipos de casas, la casa tipo campo se venden a $60.000.000 y las
de tipo rancho $50.000.000
Para la casa tipo campo se necesitan 20 horas carpintería y 100 horas de obra civil y para ranchos se
necesita 25 horas carpintero y 80 horas de obra civil, los costos de materia prima para la fabricación
de cualquier tipo de casa es de $20.000.000, el costo por hora de obra civil es de $10.000 (un maestro
y dos ayudantes) y el costo de hora carpintería es de $5.000, de acuerdo a la disponibilidad de mano
de obra se cuenta con un equipo que nos ofrece 8000 horas de obra civil y 3000 horas de carpintería.
Maximice el beneficio de producción
U2 Problemas de programación lineal.
Solución
a. Definir las variables
b. Función objetivo
c. Restricciones
d. Condición de no negatividad
U2 Problemas de programación lineal.
Solución mediante Método Gráfico
U2 Problemas de programación lineal.
Ejercicio N°4: Problema de costo por construcción
Un constructor va a edificar dos tipos de vivienda A y B dispone de $600 millones y el coste de una
casa de tipo A es de $13 millones y $8 millones una tipo B.
El número de casa de tipo A ha de ser, al menos, del 40% del total y el de tipo B, el 20% por lo menos.
Si cada casa de tipo A se vende a $16 millones y cada una de tipo B en $9 millones ¿Cuántas casas de
cada tipo debe construir para obtener el beneficio máximo?
U2 Problemas de programación lineal.
Solución
a. Definir las variables
b. Función objetivo
c. Restricciones
d. Condición de no negatividad
U2 Problemas de programación lineal.
Solución mediante Método Gráfico
U2 Problemas de programación lineal.
Método Simplex
El método simplex es un algoritmo utilizado en programación lineal para encontrar la solución óptima
a problemas de optimización que involucran múltiples variables y restricciones lineales. Es un método
iterativo que mueve repetidamente de una solución factible a otra mejor, hasta que se alcanza la
solución óptima o se determina que no existe una solución óptima.
1. Formulación del problema: Se define el problema de optimización en términos de una función
objetivo (que se busca maximizar o minimizar) y un conjunto de restricciones lineales.
2. Forma estándar: Se transforma el problema a su forma estándar, donde todas las restricciones
son ecuaciones y las variables son no negativas.
3. Tabla simplex inicial: Se crea una tabla inicial, que representa la solución básica factible (SBF)
inicial y se calcula el valor de la función objetivo para esa solución.
U2 Problemas de programación lineal.
Método Simplex
4. Criterio de optimalidad: Se evalúa si la SBF actual es óptima. Si no lo es, se identifica una variable
que puede entrar a la base (variable no básica con costo reducido negativo para maximización o
positivo para minimización) y otra que debe salir (variable básica que se hace cero).
5. Iteración: Se realiza una operación de pivoteo para pasar a una nueva SBF adyacente, mejorando
el valor de la función objetivo. Este paso se repite hasta que se alcanza la optimalidad o se
determina que el problema no tiene solución.
6. Solución óptima: Cuando no se encuentra ninguna variable que pueda mejorar la solución, se ha
alcanzado la solución óptima.
U2 Problemas de programación lineal.
Método Simplex
Ejemplo: Resolver el siguiente problema por método gráfico y método simplex
