Solución de Modelos de Programación Lineal

MÉTODO GRAFICO

Modelación y Programación Matemática

INTRODUCCIÓN

En la presentación actual se muestra la solución de varios tipos

de problemas de programación lineal que solamente tienen en su
formulación dos variables, empleando el Método Gráfico.
Se trabajará entonces en el plano cartesiano.

Los pasos a seguir son:

1. Representar en el plano cartesiano cada una de las

restricciones

2. Determinar el espacio de soluciones factibles ó

Región Factible, definido por el conjunto de
restricciones.

3. Encontrar la solución óptima que permita maximizar

ó minimizar cierta Función Objetivo.
 1. Representación de las Restricciones en
el Plano Cartesiano
Una recta (Hiperplano en R2), divide al plano en dos semi-espacios

Recta X1 - 2X2 = 5 Recta X = 2

Semiespacio X1 - 2X2 < 5

X2

X
1 2 3 4 5 0 1 2 3
0 X1

Semiespacio X1 - 2X2 > 5 Semiespacio X<2 Semiespacio X>2

 1. Representación de las Restricciones en
el Plano Cartesiano
Podemos decir entonces que:

Restricción: X1 – 2X2 >5 X2

El semi-espacio de puntos representados por la

restricción, se suele mostrar con una flecha tal 1 2 3 4 5
como lo muestra el gráfico. Usualmente, para 0 X1
verificar cual es el semi-espacio de puntos que la
restricción representa, se suele probar con un punto
para poder concluir. Aquí podemos probar
fácilmente con el punto (0,0), dándonos cuenta que
la restricción NO representa los puntos del SEMI-
ESPACIO SUPERIOR. X2

Restricción: X1 = 2
1 2 3 4 5
0 X1
Esta restricción representa exactamente los punto sobre la
recta X1 = 2.
 2. Determinación de la REGION FACTIBLE

Para encontrar la región factible deben graficarse todas las restricciones en un

mismo plano cartesiano y posteriormente determinar los puntos de intersección
de TODOS los semi-espacios.

EJEMPLO:
Dibujar la región factible asociada a las siguientes 3 restricciones:

r x + y ≥ 4
y ≤ 4
s
y ≥ x
t

REGION
FACTIBLE
 2. Determinación de la REGIÓN FACTIBLE

Al determinar la región factible de un modelo de PL, la figura

geométrica resultante se le conoce como Poliedro Convexo, y
por tanto se dice que un conjunto de restricciones forman un
conjunto poliédrico. La convexidad es un concepto de gran
importancia en optimización.
Un conjunto C es un conjunto convexo si el segmento rectilíneo que
une cualquier par de puntos de C se encuentra completamente en C.

Si la Región Factible es Convexa, la solución optima del

problema de PL se encontrará en uno de los vértices.
 2. Determinación de la REGION FACTIBLE

La región factible puede ser acotada ó no acotada.

Región factible acotada Región factible no acotada

(Politopo)

La importancia de la región factible se centra en los vértices, ya que

en alguno (s) de ellos estará la solución óptima del problema.
 2. Determinación de la REGION FACTIBLE

Tenga en cuenta que si al graficar las restricciones ocurre que no existe

una región de intersección, cuyos puntos sean comunes a TODAS las
restricciones, esto indica que el problema no tiene región factible y por
tanto no tiene solución.

EJEMPLO: Determine la Región Factible de un problema de optimización lineal con

las siguientes restricciones:
R1 ➔ X1 + X2 ≤ 3
R2 ➔ X2 ≥ 4 X2
Obvias ➔ X1, X2 ≥0

No hay región
factible 1 2 3 4 5
0 X1
 3. Búsqueda de la SOLUCION OPTIMA

Estudiemos el siguiente EJEMPLO:

Maximizar Z = 2X1 + X2
Sujeta a: 2X1 - X2 ≤ 8
X1 - X 2 ≤ 3
X1 + 2X2 ≤ 14
X1 + 4X2 ≤ 24
Xj > 0 ; j = 1, 2

Existen dos métodos para

hallar el vértice óptimo:
A) Utilizar la recta de la
función Objetivo para
hallar el óptimo.
B) Evaluar el valor de Z en
cada vértice, y escoger
aquel vértice que
maximice Z.
 3. Búsqueda de la SOLUCION OPTIMA

Método B
El valor de la función objetivo en cada una de las esquinas del área de
soluciones factible es:
Z(0,0) = 2(0) + 0 = 0 Z(0,6) = 2(0) + 6 = 6
Z(4,5) = 2(4) + 5 = 13 Z(6,4) = 2(6) + 4 = 16 ➔ Punto OPTIMO
Z(5,2) = 2(5) + 2 = 12 Z(3,0) = 2(3) + 0 = 6

Método A
Se dibuja la recta Z = 2X1+X2
viéndola de la forma y=mx+b,
así: X2 = - 2X1 + Z
Aquí se graficó para Z = 2 por
conveniencia para observar la
recta dentro de la Región
Factible. Para obtener el Z
máximo, debe obtenerse el
máximo intercepto de esta
recta con el eje X2. sin salirse
de la región factible.
 Ejemplo: Un problema de maximización

Formulación Modelo de programación lineal

Max 5x1 + 7x2

s.a. x1 < 6
2x1 + 3x2 < 19
x1 + x2 < 8

x1 , x2 > 0
 Ejemplo: Un problema de maximización

► Grafica de la primera restricción

x2

8
7
6
x1 < 6
5
4
3
2 (6, 0)
1
x1
1 2 3 4 5 6 7 8 9 10
 Ejemplo: Un problema de maximización
► Gráfica de la segunda restricción

x2

8 (0, 6 1/3)
7
6
5
4 2x1 + 3x2 < 19
3
2 (9 1/2, 0)
1
x1
1 2 3 4 5 6 7 8 9 10
 Ejemplo: Un problema de maximización
► Grafica de la tercera restricción

x2
(0, 8)
8
7 x1 + x2 < 8
6
5
4
3
2
1
(8, 0)
x1
1 2 3 4 5 6 7 8 9 10
 Ejemplo: Un problema de maximización

► Grafica de la cuarta restricción

x2
x1 + x2 < 8
8
7
6
x1 < 6
5 x1, x2 > 0
4
3 2x1 + 3x2 < 19
2
1
x1
1 2 3 4 5 6 7 8 9 10
 Ejemplo: Un problema de maximización

►Región de la solución factible

x2

8
7
6
5
4
3
Región
2 Factible
1
x1
1 2 3 4 5 6 7 8 9 10
 Ejemplo: Un problema de maximización

► Linea de la función objetivo

x2

8
7
(0, 5)
6 Función Objetivo
5 5x1 + 7x2 = 35
4
3
2
(7, 0)
1
x1
1 2 3 4 5 6 7 8 9 10
 Ejemplo: Un problema de maximización

► Solución Optima (Metodo A)

x2
Función Objetivo
5x1 + 7x2 = 46

Solución Optima
(x1 = 5, x2 = 3)

Región
Factible

x1
 Ejemplo: Un problema de maximización

►Solución Optima (Metodo B)

FORMA ESTANDAR DEL
x2 MODELO

Max 5x1 + 7x2 + 0x3 + 0x4 + 0x5

8
8
s.a. x1 + x3 = 6
7
5
2x1 + 3x2 + x4 = 19
6
5 x1 + x2 + x5 = 8
4 4 x1, x2 , x3 , x4 , x5 > 0
3 Región 3
2 Factible
VARIABLES DE
1 7
1 2 HOLGURA:
x1 “ LO QUE SOBRA”
1 2 3 4 5 6 7 8 9 10
6
 Soluciones básicas factibles y no factibles

1. x1= 0, x2 = 0, x3 = 6, x4 = 19, x5 = 8
2. x1= 6, x2 = 0, x3 = 0, x4 = 7, x5 = 2
3. x1= 6, x2 = 2, x3 = 0, x4 = 1, x5 = 0
x2
4. x1= 5, x2 = 3, x3 = 1, x4 = 0, x5 = 0
8 5. x1= 0, x2 = 61/3, x3 = 6, x4 = 0, x5 = 12/3
8
6. x1= 8, x2 = 0, x3 = -2, x4 = 3, x5 = 0
7 Soluciones
5 7. x1= 91/2, x2 = 0, x3 = -31/2, x4 = 0, x5 = - 11/2
6 No Factibles
8. x1= 0, x2 = 8, x3 = 6, x4 = -5, x5 = 0
5
9. x1= 6, x2 = 21/3, x3 = 0, x4 = 0, x5 = -1/3
4 4
Max 5x1 + 7x2 + 0x3 + 0x4 + 0x5
3 3
Región s.a. x1 + x3 = 6
2 Factible
2x1 + 3x2 + x4 = 19
1 7
1 2 6 x1 + x2 + x5 = 8
x1
1 2 3 4 5 6 7 8 9 10
 Soluciones factibles

1. x1= 0, x2 = 0, x3 = 6, x4 = 19, x5 = 8
x2 2. x1= 6, x2 = 0, x3 = 0, x4 = 7, x5 = 2
3. x1= 6, x2 = 2, x3 = 0, x4 = 1, x5 = 1
8
SOLUCIÓN 4. x1= 5, x2 = 3, x3 = 1, x4 = 0, x5 = 0
7 5 OPTIMA 5. x1= 0, x2 = 6, x3 = 0, x4 = 1, x5 = 2
6
5
4
4
3 Como puedo hallar la
Feasible 3 solución optima?
2
Region
1
1 2
1 2 3 4 5 6 7 8 9 10
x1
Reemplazando en la Función Objetivo
 Ejemplo: Un problema de minimización

Formulación de programación lineal

Min 5x1 + 2x2

s.a. 2x1 + 5x2 > 10

4x1 - x2 > 12
x1 + x2 > 4

x1, x2 > 0
 Ejemplo: Un problema de minimización

►Región de la solución factible

x2 Región Factible

4x1 - x2 > 12
5

4 x1 + x2 > 4

3
2x1 + 5x2 > 10
2

1
x1
1 2 3 4 5 6
 Ejemplo: Un problema de minimización

►Región de la solución factible

x2 Min z = 5x1 +
2x2
4x1 - x2 > 12
5

4 x1 + x2 > 4

3
2x1 + 5x2 > 10
2

1
x1
1 2 3 4 5 6
 Ejemplo: Un problema de minimización

►Región de la solución factible

x2 Min z = 5x1 +
2x2
4x1 - x2 > 12
5

4 x1 + x2 > 4

3
2x1 + 5x2 > 10
2 Optimo: x1 = 16/5
x2 = 4/5
1
x1
1 2 3 4 5 6
EJEMPLO 2: Problema de dieta.
Un comprador está tratando de seleccionar la combinación más barata de dos
alimentos, que debe cumplir con ciertas necesidades diarias de vitaminas. Los
requerimientos vitamínicos son por lo menos 40 unidades de vitamina W, 50
unidades de vitamina X y 49 unidades de vitamina Y. Cada kilo del alimento A
proporciona 4 unidades de vitamina W, 10 unidades de vitamina X y 7 unidades de
vitamina Y; cada kilo del alimento B proporciona 10 unidades de W, 5 unidades de X
y 7 unidades de Y. El alimento A cuesta 5 pesos/kilogramo y el alimento B cuesta 8
pesos/kilogramo.

B
Minimizar Z = 5A + 8B
Restricciones: Región
10A + 5B ≥ 50 Factible
4A + 10B ≥ 40 vitamina W
10A + 5B ≥ 50 vitamina X
7A + 7B ≥ 49
7A + 7B ≥ 49 vitamina Y
A ≥ 0, B ≥ 0
4A + 10B ≥ 40

A
B
Observando la Minimización de Z,
a través del análisis de la recta
Z = 5A + 8 B, el vértice b de la
región factible es entonces el que
logra ese mínimo valor de Z.

Z= 60
La solución menos costosa es 5
kilogramos de alimento A y 2
kilogramos de alimento B. El costo
total de esta combinación es:
Z = 41 pesos
Z= 40
A

Resultados de prueba y error

Punto Coordenadas Z = 5A + 8B
a A = 10, B = 0 50
b A = 5, B = 2 41 Optimo
c A = 3, B = 4 47
d A = 0, B = 10 80
 Observemos que en general:
Minimizar Z = Maximizar (-Z) [y viceversa]

Minimizar Z = 5A + 8B Maximizar (-Z) = - 5A - 8B

Restricciones: Restricciones:
4A + 10B ≥ 40 = 4A + 10B ≥ 40
10A + 5B ≥ 50 10A + 5B ≥ 50
7A + 7B ≥ 49 7A + 7B ≥ 49
A ≥ 0, B ≥ 0 A ≥ 0, B ≥ 0

Verificación de los Vértices Verificación de los Vértices

Punto Coordenadas Min Z = 5A + 8B Punto Coordenadas Max (-Z) = -5A - 8B
a A = 10, B = 0 50 a A = 10, B = 0 - 50
b A = 5, B = 2 41 Óptimo b A = 5, B = 2 - 41 Optimo
c A = 3, B = 4 47 c A = 3, B = 4 - 47
d A = 0, B = 10 80 d A = 0, B = 10 - 80
 CASOS ESPECIALES

Problema de múltiples soluciones

Maximice Z = (5/2)X1 + X2
Sujeto a: 3X1 + 5X2 ≤ 15
5X1 + 2X2 ≤ 10
Xj > 0 ; j = 1, 2

Problema de solución infinita

Minimice Z = - X1 + X2

Sujeto a: X1 - X2 ≥ 0
- 0,5X1 + X2 ≤ 1
Xj > 0 ; j = 1, 2

Problema sin solución

Ocurre cuando NO HAY REGION FACTIBLE
EJEMPLO 3: Problema de mezcla de productos.
Un fabricante está tratando de decidir sobre las cantidades de producción
para dos artículos: mesas y sillas. Se cuenta con 96 unidades de material y
con 72 horas de mano de obra. Cada mesa requiere 12 unidades de material y
6 horas de mano de obra. Por otra parte, las sillas usan 8 unidades de
material cada una y requieren 12 horas de mano de obra por silla. El margen
de contribución es el mismo para las mesas que para las sillas: $5.00 por
unidad. El fabricante prometió construir por lo menos dos mesas.

x1 = número de mesas producidas

x2 = número de sillas producidas

Maximizar Z = 5x1 + 5x2

Restricciones:
12x1 + 8x2 ≤ 96
6x1 + 12x2 ≤ 72
x1 ≥2
x1 ≥ 0, x2 ≥ 0, ENTEROS
SOLUCION EJEMPLO 3
Análisis de la Maximización
de la Función Objetivo:
Z = 5X1 + 5X2

a a

c c
b d b d

El punto que maximiza la Función Objetivo

es el punto c.
Calculando el punto c como el punto de
intersección de las dos rectas se obtiene
que X1=6, X2=3, Z= 45
Problemas Propuestos

Problema propuesto 1

En un almacén se guarda aceite de girasol y de oliva. Para

atender a los clientes se han de tener almacenados un mínimo
de 20 bidones de aceite de girasol y 40 de aceite de oliva y,
además, el número de bidones de aceite de oliva no debe ser
inferior a la mitad del número de bidones de aceite de girasol.
La capacidad total del almacén es de 150 bidones. Sabiendo que
el gasto de almacenaje es el mismo para los dos tipos de aceite
(1 unidad monetaria) . ¿Cuántos bidones de cada tipo habrá que
almacenar para que el gasto sea máximo?
Problema Propuesto 2:
Resuelva el siguiente modelo de programación lineal:

Maximizar Z = 3x1 + 2x2

sujeta a 1/40x1 + 1/60x2  1
1/50x1 + 1/50x2  1
X1  30
x2  20
x1   x2  
Problema Propuesto 3:
Resuelva el siguiente modelo de programación lineal:

Maximizar Z = 2x1 – x2
sujeta a x1 – x2  1
2x1 + x2  6
x1   x2  