Universidad Autónoma de Nuevo León
Facultad de Ciencias Físico Matemáticas
Laboratorios de Programación Lineal
Enero – Junio 2023
I – CAMBIO DE SENTIDO DE UN PROBLEMA
1. Convierta los siguientes problemas de Programación Lineal a problemas de maximización o
minimización según sea el caso.
a) 𝑚𝑖𝑛 𝑧 = −8𝑥1 + 3𝑥2 − 6𝑥3 + 5𝑥4 b) 𝑚𝑎𝑥 𝑧 = −4𝑥1 − 𝑥2 − 2𝑥3
𝑠. 𝑎. 𝑠. 𝑎.
−𝑥1 + 2𝑥2 − 𝑥3 − 3𝑥4 ≤ 6 −4𝑥1 − 𝑥2 − 𝑥3 ≥ 6
2𝑥1 − 𝑥2 − 8𝑥3 ≥ 10 𝑥1 − 11𝑥2 ≤ 10
𝑥2 + 4𝑥3 − 7𝑥4 ≥ 8 𝑥2 − 𝑥3 ≤ 8
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
-1-
Universidad Autónoma de Nuevo León
Facultad de Ciencias Físico Matemáticas
Laboratorios de Programación Lineal
Enero – Junio 2023
II - FORMA CANÓNICA Y FORMA ESTÁNDAR
1. Plantee los siguientes problemas de Programación Lineal en su forma canónica y su forma
estándar.
a) 𝑚𝑎𝑥 𝑧 = 2𝑥1 + 3𝑥2 + 4𝑥3 b) 𝑚𝑖𝑛 𝑧 = 2𝑥1 + 𝑥2 + 8𝑥3
𝑠. 𝑎. 𝑠. 𝑎.
𝑥1 + 𝑥2 + 𝑥3 ≥ 1 2𝑥1 + 𝑥2 − 7𝑥3 ≤ 10
𝑥1 − 2𝑥2 = 7 7𝑥1 + 2𝑥2 + 5𝑥3 = 9
2𝑥1 + 𝑥3 ≤ 5 3𝑥1 + 3𝑥2 + 5𝑥3 ≥ 3
𝑥1 , 𝑥2 ≥ 0, 𝑥3 libre |8𝑥1 + 9𝑥2 + 5𝑥3 | ≤ 1
𝑥1 , 𝑥2 ≥ 0, 𝑥3 ≤ 0
c) 𝑚𝑎𝑥 𝑧 = 2𝑥1 − 3𝑥2 + 5𝑥3 d) 𝑚𝑎𝑥 𝑧 = 5𝑥1 + 𝑥2 − 𝑥3
𝑠. 𝑎. 𝑠. 𝑎.
𝑥1 + 𝑥2 ≤ 2 𝑥1 + 𝑥3 ≤ 7
3𝑥1 + 𝑥2 − 𝑥3 ≥ 3 9𝑥1 − 𝑥2 + 2𝑥3 = 5
2𝑥1 + 𝑥3 ≤ 5 −7𝑥2 + 4𝑥3 ≥ 14
𝑥1 , 𝑥2 ≥ 0, 𝑥3 libre 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0
e) 𝑚𝑎𝑥 𝑧 = 4𝑥1 − 5𝑥2 f) 𝑚𝑖𝑛 𝑧 = −3𝑥1 + 2𝑥2
𝑠. 𝑎. 𝑥1 + 4𝑥2 ≥ 2 𝑠. 𝑎.
2𝑥1 + 𝑥2 ≤ 6 𝑥1 + 2𝑥2 ≤ 5
𝑥1 + 2𝑥2 ≤ 5 3𝑥1 + 𝑥2 − 𝑥3 ≥ 3
𝑥1 + 𝑥2 ≥ 1 2𝑥1 + 𝑥3 ≤ 5
𝑥1 , 𝑥2 ≥ 0, 𝑥3 libre 𝑥1 , 𝑥2 ≥ 0, 𝑥3 libre
-2-
Universidad Autónoma de Nuevo León
Facultad de Ciencias Físico Matemáticas
Laboratorios de Programación Lineal
Enero – Junio 2023
III - REPRESENTACIÓN MATRICIAL
1. Dados los siguientes problemas de programación lineal, identifique la matriz de coeficientes
𝐴, el vector de costos 𝑐 y el vector de recursos 𝑏.
a) 𝑚𝑎𝑥 𝑧 = −𝑥1 − 5𝑥2 − 𝑥3 + 6𝑥4 b) 𝑚𝑖𝑛 𝑧 = 3𝑥1 + 9𝑥2 + 4𝑥3
𝑠. 𝑎. 𝑠. 𝑎.
2𝑥1 + 𝑥2 + 𝑥3 + 7𝑥4 = 2 7𝑥1 − 2𝑥2 − 8𝑥3 = 15
𝑥1 + 𝑥2 + 9𝑥3 = 4 −3𝑥1 − 16𝑥2 = 1
𝑥2 + 𝑥3 − 𝑥4 = 3 𝑥2 + 𝑥3 = 5
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0 𝑥1 , 𝑥2 , 𝑥3 ≥ 0
c) 𝑚𝑎𝑥 𝑧 = 3𝑥1 + 𝑥2 + 2𝑥3 d) 𝑚𝑖𝑛 𝑧 = −3𝑥1 + 2𝑥2
𝑠. 𝑎. 𝑠. 𝑎.
2𝑥1 + 3𝑥2 + 𝑥3 ≤ 10 𝑥1 + 2𝑥2 ≤ 5
𝑥1 + 2𝑥2 + 3𝑥3 ≤ 10 2𝑥1 + 𝑥2 ≤ 15
𝑥1 , 𝑥2 , 𝑥3 ≥ 0 𝑥1 , 𝑥2 ≥ 0
2. Dada la matriz de coeficientes, el vector de costos y el vector de recursos, construya un
problema de programación lineal de la forma
𝑚𝑎𝑥 𝑧 = 𝑐𝑥
𝑠. 𝑎.
𝐴𝑥 = 𝑏
𝑥≥0
a) 𝐴 = (−3 −9) b) 21 −1 −11 7
8 −1 𝐴 = (−10 20 40 0)
−13 8 −1 −1
5
𝑏=( )
13 2
𝑏 = (4 )
𝑐 = (−6,5) 3
𝑐 = (−9,5,6,2)
-3-
Universidad Autónoma de Nuevo León
Facultad de Ciencias Físico Matemáticas
Laboratorios de Programación Lineal
Enero – Junio 2023
IV - MODELADO DE PROBLEMAS
Dados los siguientes enunciados, construya un problema de programación lineal que modele el
problema.
1- Un agricultor tiene un terreno en el que cosecha papas y calabazas. Para su siguiente cosecha
quiere utilizar al menos 4 hectáreas de su terreno. Cada hectárea de cultivo de papas requiere
20 horas máquina y 100kg de abono, y cada hectárea de cultivo de calabazas necesita 10
horas de maquinaria y 300kg de abono, pero esta temporada el agricultor cuenta con 180
horas de maquinaria y 2400kg de abono. Además, el agricultor quiere que el número de
hectáreas que se dediquen al cultivo de calabazas sea mayor o igual que el número de
hectáreas que se dediquen al cultivo de papas. Si el agricultor obtiene $3,000 USD por cada
hectárea de cultivo de papas y $1500 USD por cada hectárea de cultivo de calabazas, ¿cuántas
hectáreas debería dedicar a cada cultivo para maximizar su utilidad?
2- En un restaurante se necesita preparar un ponche frutas de al menos 500 galones que sea al
menos 20% jugo de naranja, 10% jugo de toronja y 5% jugo de arándano. El restaurante tiene
en su inventario 5 tipos de bebidas que contienen estos ingredientes en diferentes
cantidades. En la tabla se muestra el porcentaje que de cada jugo que contiene, así como el
inventario con el que dispone el restaurante y el costo por galón.
¿Qué cantidad de cada bebida debe utilizar para preparar el ponche con un costo total mínimo?
Jugo de Jugo de Jugo de Costo por Disponibilidad
Naranja Toronja Arándano Galón
Bebida A 40 % 40 % 0% $ 1.50 200 gal
Bebida B 5% 10 % 20 % $ 0.75 400 gal
Bebida C 100 % 0% 0% $ 2.00 100 gal
Bebida D 0% 100 % 0% $ 1.75 50 gal
Bebida E 0% 0% 0% $ 0.25 800 gal
-4-
Universidad Autónoma de Nuevo León
Facultad de Ciencias Físico Matemáticas
Laboratorios de Programación Lineal
Enero – Junio 2023
3- Una empresa de Rústicos fabrica entre muchos otros productos tres tipos de sillas A, B y C,
las cuales se venden a precio de 11, 13, 12 $ c/u respectivamente. Las sillas pasan por tres
procesos, para lo cual disponen de máximo de 17, 13 y 15 horas respectivamente a la semana.
La A requiere 3hrs de corte, 1 hora para ensamblado y 3 horas de pintura. La silla B requiere
1 hora para corte, 4 horas para ensamblado y 3 horas de pintura. Y finalmente la silla tipo C,
requiere 5 horas para corte, 2 para ensamblado y 2 horas para pintura. La empresa busca
maximizar sus ganancias.
-5-
Universidad Autónoma de Nuevo León
Facultad de Ciencias Físico Matemáticas
Laboratorios de Programación Lineal
Enero – Junio 2023
V - MÉTODO GRÁFICO
1. Dados los siguientes problemas de programación lineal:
• Dibuje la región de soluciones factibles.
• Identifique si la región es vacía o no.
• Identifique si la región es acotada o no acotada.
• Encuentre geométricamente el óptimo del problema.
a) 𝑚𝑎𝑥 𝑧 = 𝑥1 − 𝑥2 b) 𝑚𝑎𝑥 𝑧 = 3𝑥1 + 2𝑥2
𝑠. 𝑎. 𝑠. 𝑎.
−𝑥1 + 3𝑥2 ≤ 0 2𝑥1 + 𝑥2 ≤ 2
−3𝑥1 + 2𝑥2 ≥ −3 3𝑥1 + 4𝑥2 ≥ 12
𝑥1 , 𝑥2 ≥ 0 𝑥1 , 𝑥2 ≥ 0
c) 𝑚𝑖𝑛 𝑧 = 0.4𝑥1 + 0.6𝑥2 d) 𝑚𝑖𝑛 𝑧 = 1.5𝑥1 + 3𝑥2
𝑠. 𝑎. 𝑠. 𝑎.
𝑥1 + 2𝑥2 ≥ 2 𝑥1 + 2𝑥2 ≥ 7
2𝑥1 + 2𝑥2 ≥ 2 3𝑥1 − 4𝑥2 ≤ 14
𝑥1 , 𝑥2 ≥ 0 𝑥1 + 𝑥2 ≥ 5
𝑥1 , 𝑥2 ≥ 0
e) 𝑚𝑎𝑥 𝑧 = 4.5𝑥1 + 5𝑥2 f) 𝑚𝑎𝑥 𝑧 = 8𝑥1 + 10𝑥2
𝑠. 𝑎. 𝑠. 𝑎.
6𝑥1 + 7𝑥2 ≤ 75 𝑥1 + 2𝑥2 ≤ 20
4𝑥1 + 5𝑥2 ≤ 50 𝑥1 + 𝑥2 ≤ 15
𝑥1 , 𝑥2 ≥ 0 𝑥1 , 𝑥2 ≥ 0
-6-
Universidad Autónoma de Nuevo León
Facultad de Ciencias Físico Matemáticas
Laboratorios de Programación Lineal
Enero – Junio 2023
VI - SOLUCIONES BÁSICAS
1. Identifique todas las posibles bases de los siguientes problemas de programación lineal. Para
cada una de ellas determine:
• Las variables básicas
• Las variables no básicas
• La solución que genera la base
• Si la solución es factible
• El valor objetivo
a) 𝑚𝑖𝑛 𝑧 = 𝑥1 + 𝑥2 b) 𝑚𝑎𝑥 𝑧 = 2𝑥1 + 3𝑥2
𝑠. 𝑎. 𝑠. 𝑎.
𝑥1 + 2𝑥2 ≤ 4 𝑥1 + 𝑥2 ≤ 2
𝑥1 ≤ 1 2𝑥1 − 𝑥2 ≤ 3
𝑥1 , 𝑥2 ≥ 0 𝑥1 + 3𝑥2 ≤ 5
𝑥1 , 𝑥2 ≥ 0
c) 𝑚𝑖𝑛 𝑧 = −5𝑥1 − 5𝑥2 d) 𝑚𝑎𝑥 𝑧 = 𝑥1 + 𝑥2
𝑠. 𝑎. 𝑠. 𝑎.
3𝑥1 + 5𝑥2 ≤ 30 5𝑥1 + 8𝑥2 ≤ 4000
𝑥1 + 5𝑥2 ≤ 20 2𝑥1 + 𝑥2 ≤ 400
𝑥1 , 𝑥2 ≥ 0 𝑥1 , 𝑥2 ≥ 0
e) 𝑚𝑎𝑥 𝑧 = 2𝑥1 + 4𝑥2 f) 𝑚𝑖𝑛 𝑧 = 5𝑥1 + 3𝑥2
𝑠. 𝑎. 𝑠. 𝑎.
𝑥1 + 𝑥2 ≥ 5 𝑥1 + 𝑥2 ≤ 10
6𝑥1 + 2𝑥2 ≥ 12 3𝑥1 + 2𝑥2 ≤ 15
𝑥1 , 𝑥2 ≥ 0 𝑥1 , 𝑥2 ≥ 0
-7-
Universidad Autónoma de Nuevo León
Facultad de Ciencias Físico Matemáticas
Laboratorios de Programación Lineal
Enero – Junio 2023
VII - MÉTODO SIMPLEX
1. Encuentre el óptimo de los siguientes problemas de programación lineal utilizando el método
Simplex Tabular.
a) 𝑚𝑎𝑥 𝑧 = 3𝑥1 + 2𝑥2 b) 𝑚𝑎𝑥 𝑧 = 3𝑥1 + 4𝑥2 + 1.5𝑥3
𝑠. 𝑎. 𝑠. 𝑎.
2𝑥1 + 5𝑥2 ≤ 35 −𝑥1 − 2𝑥2 ≥ −10
−3𝑥2 + 2𝑥2 ≥ −18 2𝑥1 + 2𝑥2 + 𝑥3 ≤ 10
2𝑥1 + 4𝑥2 ≤ 26 𝑥1 , 𝑥2 , 𝑥3 ≥ 0
𝑥1 , 𝑥2 ≥ 0
c) 𝑚𝑎𝑥 𝑧 = 2𝑥1 + 𝑥2 d) 𝑚𝑎𝑥 𝑧 = 7𝑥1 + 4𝑥2 + 3𝑥3
𝑠. 𝑎. 𝑠. 𝑎.
𝑥1 + 𝑥2 ≤ 9 𝑥1 + 2𝑥2 + 2𝑥3 ≤ 30
𝑥1 + 2𝑥2 ≤ 12 2𝑥1 + 𝑥2 + 2𝑥3 ≤ 45
𝑥1 , 𝑥2 ≥ 0 𝑥1 , 𝑥2 , 𝑥3 ≥ 0
2. Dado el siguiente problema de programación lineal, obtenga la solución óptima y el valor de
la función objetivo. Si existen empates, rómpalos con la regla lexicográfica.
𝑚𝑖𝑛 𝑧 = 3𝑥1 + 2𝑥2
𝑠. 𝑎.
𝑥1 + 𝑥2 ≤ 6
2𝑥1 − 𝑥2 ≤ 0
𝑥1 ≤ 2
𝑥1 , 𝑥2 ≥ 0
3. Dado el siguiente problema de programación lineal, obtenga la solución óptima y el valor de
la función objetivo.
𝑚𝑎𝑥 𝑧 = 2𝑥1 + 𝑥2
𝑠. 𝑎
𝑥1 − 𝑥2 ≤ 10
2𝑥1 − 𝑥2 ≤ 40
𝑥1 , 𝑥2 ≥ 0
-8-
Universidad Autónoma de Nuevo León
Facultad de Ciencias Físico Matemáticas
Laboratorios de Programación Lineal
Enero – Junio 2023
4- Dado el siguiente problema de programación lineal, obtenga la solución óptima y el valor de
la función objetivo. Determine si el problema tiene múltiples soluciones óptimas, y de ser así,
encuéntrelas.
𝑚𝑎𝑥 𝑧 = 3𝑥1 + 2𝑥2
𝑠. 𝑎
𝑥1 + 𝑥3 = 4
2𝑥2 + 𝑥4 = 12
3𝑥1 + 2𝑥2 + 𝑥5 = 18
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0
-9-
Universidad Autónoma de Nuevo León
Facultad de Ciencias Físico Matemáticas
Laboratorios de Programación Lineal
Enero – Junio 2023
VIII - MÉTODO DE LA GRAN M
1. Encuentre el óptimo de los siguientes problemas de Programación Lineal utilizando el método
de La Gran M.
a) 𝑚𝑖𝑛 𝑧 = 4𝑥1 + 4𝑥2 + 𝑥3 b) 𝑚𝑖𝑛 𝑧 = 3𝑥1 + 8𝑥2
𝑠. 𝑎. 𝑠. 𝑎.
2𝑥1 + 𝑥2 + 𝑥3 ≤ 2 𝑥1 + 4𝑥2 ≥ 3.5
2𝑥1 + 𝑥2 ≤ 3 𝑥1 + 2𝑥2 ≥ 2.5
2𝑥1 + 𝑥2 + 3𝑥3 ≥ 3 𝑥1 , 𝑥2 ≥ 0
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
c) 𝑚𝑖𝑛 𝑧 = 2𝑥1 − 3𝑥2 d) 𝑚𝑖𝑛 𝑧 = 600𝑥1 + 400𝑥2
𝑠. 𝑎. 𝑠. 𝑎.
𝑥1 + 𝑥2 ≤ 3 2𝑥1 + 𝑥2 ≥ 8
2𝑥1 + 3𝑥2 ≥ 6 6𝑥1 + 𝑥2 ≥ 12
𝑥1 ≥ 0, 𝑥2 𝑙𝑖𝑏𝑟𝑒 𝑥1 + 3𝑥2 ≥ 9
𝑥1 , 𝑥2 ≥ 0
e) 𝑚𝑖𝑛 𝑧 = 2𝑥1 + 3𝑥2 f) 𝑚𝑖𝑛 𝑧 = 2𝑥1 + 3𝑥2
𝑠. 𝑎. 𝑠. 𝑎.
2𝑥1 + 𝑥2 ≥ 1 0.5𝑥1 + 0.25𝑥2 ≤ 4
𝑥1 + 𝑥2 ≤ 10 𝑥1 + 3𝑥2 ≥ 20
𝑥1 , 𝑥2 ≥ 0 𝑥1 + 𝑥2 = 10
𝑥1 , 𝑥2 ≥ 0
- 10 -
Universidad Autónoma de Nuevo León
Facultad de Ciencias Físico Matemáticas
Laboratorios de Programación Lineal
Enero – Junio 2023
IX - DUALIDAD
1. Dados los siguientes Problemas Primales de Programación Lineal, encuentre sus respectivos
Problemas Duales.
a) 𝑚𝑎𝑥 𝑧 = 5𝑥1 + 8𝑥2 + 3𝑥3 b) 𝑚𝑎𝑥 𝑧 = 𝑥1 + 𝑥2 + 𝑥3 + 2𝑥4
𝑠. 𝑎 𝑠. 𝑎
𝑥1 − 𝑥2 + 𝑥3 ≥ 3 𝑥1 + 2𝑥3 − 𝑥4 ≥ 10
𝑥1 − 2𝑥2 ≤ 10 𝑥1 + 𝑥3 − 𝑥4 ≤ 30
𝑥1 + 𝑥3 = 4 𝑥1 , 𝑥2 ≥ 0, 𝑥3 ≤ 0, 𝑥4 𝑙𝑖𝑏𝑟𝑒
𝑥1 ≥ 0, 𝑥2 ≤ 0, 𝑥3 𝑙𝑖𝑏𝑟𝑒
c) 𝑚𝑖𝑛 𝑧 = 3𝑥1 + 4𝑥2 d) 𝑚𝑖𝑛 𝑧 = 4𝑥1 − 10𝑥2 + 8𝑥3
𝑠. 𝑎 𝑠. 𝑎
𝑥1 + 𝑥2 ≥ 3 𝑥1 + 𝑥2 + 𝑥3 = 30
2𝑥1 − 𝑥2 ≤ 8 2𝑥1 + 𝑥2 ≤ 20
3𝑥1 + 𝑥2 = 15 3𝑥1 + 𝑥2 − 𝑥3 = 14
𝑥1 ≥ 0, 𝑥2 ≤ 0 𝑥1 − 𝑥2 − 𝑥3 ≤ 10
𝑥1 ≥ 0, 𝑥2 , 𝑥3 𝑙𝑖𝑏𝑟𝑒
e) 𝑚𝑎𝑥 𝑧 = 𝑥1 + 2𝑥2 − 2𝑥3 f) 𝑚𝑖𝑛 𝑧 = 𝑥1 − 2𝑥2 + 𝑥4
𝑠. 𝑎 𝑠. 𝑎
2𝑥1 + 𝑥2 + 5𝑥3 ≥ 1 −𝑥1 + 2𝑥2 + 𝑥3 = 2
4𝑥1 + 𝑥2 + 2𝑥3 ≤ 5 2𝑥1 − 𝑥3 + 𝑥4 ≤ 0
𝑥1 ≥ 0, 𝑥2 ≤ 0, 𝑥3 𝑙𝑖𝑏𝑟𝑒 𝑥1 + 𝑥2 + 𝑥3 = 15
. 𝑥1 ≥ 0, 𝑥2 ≤ 0
2. Encuentre el óptimo de los siguientes problemas de Programación Lineal utilizando el método
Simplex Dual.
𝑚𝑖𝑛 𝑧 = 3𝑥1 + 2𝑥2 + 𝑥3
𝑠. 𝑎
3𝑥1 + 𝑥2 + 𝑥3 ≥ 3
−3𝑥1 + 3𝑥2 + 𝑥3 ≥ 6
𝑥1 + 𝑥2 + 𝑥3 ≤ 3
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
- 11 -
Universidad Autónoma de Nuevo León
Facultad de Ciencias Físico Matemáticas
Laboratorios de Programación Lineal
Enero – Junio 2023
X - PROBLEMAS DE ASIGNACIÓN
1. a) Formule el modelo matemático para el problema de asignación dadas los siguientes
beneficios.
b) Use el método húngaro para resolver el problema formulado en a).
T1 T2 T2 T4
M1 9 21 23 8
M2 22 19 19 13
M3 23 12 19 18
M4 11 16 8 20
2. Escribe los cambios que habría en el modelo si M2 puede realizar las tareas 2 y 3
3. a) Plantea el siguiente problema de asignación.
b) Use el método húngaro para resolver el problema planteado
Un turista nacional planea salir el fin de semana a la isla de Ometepe. Hay cuatro artículos
que desea llevar consigo, pero entre todos sobrepasan los 5kg que considera puede cargar.
El peso y el valor de cada artículo es:
Artículo 1 2 3 4
Peso 2 3 4 5
Valor 3 4 5 6
- 12 -
Universidad Autónoma de Nuevo León
Facultad de Ciencias Físico Matemáticas
Laboratorios de Programación Lineal
Enero – Junio 2023
XI - PROBLEMAS DE TRANSPORTE
1- Para cada problema formule el problema de transporte y resolver usando el algoritmo de la
esquina noroeste.
a) Supongamos que una empresa productora de barras de pan tiene dos almacenes A1 y A2
desde los cuales debe enviar pan a tres panaderías P1, P2 y P3. Las ofertas, las demandas y
los costes de envió se dan en el siguiente diagrama.
b) Una empresa produce un único artículo en tres plantas, A1, A2 y A3. La capacidad de
producción mensual de la empresa está limitada a 1500 unidades mensuales en cada una de
las plantas. La empresa tiene 4 clientes mayoristas cuyas demandas mensuales son 1000,
1200, 1500 y 1000 unidades respectivamente.
C1 C2 C3 C4
A1 30 10 25 20
A2 15 25 30 10
A3 20 30 15 20
- 13 -
