PREUNIVERSITARIO

2021-2

TEMA
Programación lineal II
17.2
 CONTENIDO
➢Cálculo de los mínimos y máximos de un
PPL
• Método analítico
• Método geométrico

➢Ejemplo: Gepetto S.A.

➢Ejemplo: Dorian Auto
➢Casos especiales
• Número infinito de soluciones óptimas
• Sin soluciones factibles
• PPL no acotado
5/07/2021 Cepreuni 2020-2 2
CÁLCULO DE LOS MÍNIMOS Y/O
MÁXIMOS DE UN PPL:

• Método geométrico
• Método analítico

3
 Planteamiento del problema
En la figura adjunta se
aprecia una región factible
C convexa y acotada,
delimitada, en este caso,
por seis (06) inecuaciones
(podrían ser menos o más
inecuaciones)

Siendo z x, y = ax + by una función objetivo definida en dicha región

convexa, deseamos determinar y/o identificar y/o localizar los puntos de
dicha región donde la función objetivo alcance un mínimo y un máximo.
4
 Método geométrico

Este consiste en hacer uso simultaneo de los Teoremas de invarianza

y de monotonía:
situamos el vector u = a, b y una línea recta de vector normal
u = a, b , de modo que la región convexa quede contenida en el
semiplano que está en la dirección del vector u.

5
Hecho esto:
I. desplazamos la recta en la
dirección del vector normal u:
II. el(los) primer(os) punto(s) de
contacto, entre la línea recta y la
región 𝐂, es(son) donde la función
alcanza un mínimo.
III. el(los) último(s) punto de
contacto, entre la línea recta y la
región 𝐂, es(son) donde la función
alcanza su máximo.

6
 Método analítico
Este consiste en hacer un uso
directo del Teorema de
existencia, evaluamos la
función objetivo en cada una de
las esquinas, es decir
calculamos
z(esquina1 ), z(esquina2 )
z esquina3 , z esquina4
z esquina5 , z(esquina6 )

Y, una vez hecho esto, comparamos estos valores y vemos en cual de

estos la función objetivo alcanza un menor o mayor valor.
7
EJEMPLO: GEPETTO S.A.

8
Ejemplo: Gepetto
S.A.
Gepetto S.A. confecciona muñecos y trenes de madera.
Cada muñeco produce un beneficio neto de S/3, mientras
que cada tren produce un beneficio neto de S/2. Un
muñeco de madera requiere 2 horas de trabajo de
acabado y 1 hora de trabajo de carpintería, mientras que
un tren requiere 1 hora de trabajo de acabado y requiere 1
hora trabajo de carpinteria. Cada semana dispone
solamente 100 horas de acabado y 80 horas de
carpinteria. También la demanda de muñecos es como
mucho 40.

Gepetto quiere maximizar sus beneficios.

¿Cuántos muñecos y cuántos trenes debe fabricar?
9
 Formulación matemática del
PPLde Decisión: x = nº de muñecos producidos a la semana
Variables
y = nº de trenes producidos a la semana

Muñeco Tren

Beneficio (S/. / und.) 3 2

Acabado (hr / und) 2 1 ≤ 100

Carpintería (hr / und) 1 1 ≤ 80

Demanda (und) ≤ 40

10
 Formulación matemática del
VariablesPPL
de Decisión: x = nº de muñecos producidos a la semana
y = nº de trenes producidos a la semana

Muñeco Tren
Beneficio por tipo de
3x 2y Max z = 3x + 2y
producto (S/.)
Horas de acabado por
2x 1y ≤ 100 2 x + y ≤ 100
tipo de producto (hr)
Horas de carpintería por
1x 1y ≤ 80 x + y ≤ 80
tipo de producto (hr)
Demanda (und) ≤ 40 x ≤ 40
x ≥ 0, y ≥ 0 (no
negatividad)
11
 Nota: Frases
equivalentes
p≥q p≤q
• p al menos q • p a lo sumo q
• p a lo menos q • p a lo más q
• p como mínimo q • p como máximo q
• p cuanto menos q • p como mucho q
• p por lo menos q • p solamente q

Ejemplo 1: Los anuncios Ejemplo 2: Se dispone de

sean vistos por lo menos solamente 100 horas de
30 millones de varones. acabado.
p ≥ 30 p ≤ 100
p: n° de varones (millones) p: n° de horas de acabado

12
 Formulación matemática del
ParaPPL
el problema de Gepetto, combinando la función objetivo y
las restricciones, tenemos el siguiente modelo de optimización:

Max z = 3x + 2y (función objetivo)

Sujeto a (s.a:)
2 x + y ≤ 100 (restricción de acabado)
x + y ≤ 80 (restricción de carpinteria)
x ≤ 40 (restricción de demanda de muñecos)
x ≥ 0 (restricción de signo)
y ≥ 0 (restricción de signo)

13
 Región factible
Y
Aplicando el Teorema u = (2,1) u = (1,0) Restricciones
de separación 2 x + y ≤ 100
𝟐𝐱 + 𝐲 = 𝟏𝟎𝟎 x + y ≤ 80
graficamos cada 100

semiplano. x ≤ 40
80
𝐱 = 𝟒𝟎 x ≥ 0
La intersección de y ≥ 0
todos los semiplanos 60

(restricciones) nos da 𝐱 + 𝐲 = 𝟖𝟎
la región factible. 40

20

u = (1,1)

20 40 60 80 X

14
 Región factible
Y
Por el Teorema de Restricciones
la convexidad, la 2 x + y ≤ 100
𝟐𝐱 + 𝐲 = 𝟏𝟎𝟎
región factible (al 100 x + y ≤ 80
estar limitado por x ≤ 40
rectas) es un 80 E 𝐱 = 𝟒𝟎 x ≥ 0
conjunto convexo y ≥ 0
acotado. D
60

En esta caso, la 𝐱 + 𝐲 = 𝟖𝟎
40
región factible es el
polígono ABCDE. C: Región
20 Factible C

B
A 20 40 60 80 X

15
 Región factible
Y
Los vértices de Restricciones
la región 2 x + y ≤ 100
factible son 100 x + y ≤ 80
intersecciones x ≤ 40
de dos rectas. 80
𝐄(𝟎, 𝟖𝟎) x ≥ 0
y ≥ 0
60
𝐃 = (𝟐𝟎, 𝟔𝟎)

40

Región
20 Factible 𝐂(𝟒𝟎, 𝟐𝟎)

𝐀(𝟎, 𝟎) 20 40 60 80 X
𝐁(𝟒𝟎, 𝟎)
16
 Método Gráfico
Y
Max z = 3x + 2y

Aplicando el Teoremas 100

de invarianza y de
monotonía, la función 𝐳 80
𝐄(𝟎, 𝟖𝟎)
se mantiene constante
en las rectas cuya 60
𝐃 = (𝟐𝟎, 𝟔𝟎)
normal es u = a, b = u = (3,2)

(3,2), y 𝐳 crece a medida 40

que estas rectas se
desplazan en la Región
𝐂(𝟒𝟎, 𝟐𝟎)
20 Factible
dirección del vector
normal u = a, b = (3,2)
𝐀(𝟎, 𝟎) 20 40 60 80 X
𝐁(𝟒𝟎, 𝟎)

17
 Método Gráfico
Y
Max z = 3x + 2y
La última recta de z que 100
interseca (toca) la
región factible indica la 𝐄(𝟎, 𝟖𝟎)
80
solución óptima para el
PPL. Para el problema 60
𝐃 = (𝟐𝟎, 𝟔𝟎)
de Gepetto, esto ocurre u = (3,2)
en el punto D(20,60). 40

La solución óptima es: Región

𝐂(𝟒𝟎, 𝟐𝟎)
x = 20 muñecos 20 Factible
y = 60 trenes
z = 180 soles de beneficio 𝐀(𝟎, 𝟎) 20 40 60 80 X
𝐁(𝟒𝟎, 𝟎)

18
 Método Analítico
Y
Max z = 3x + 2y
100
Como la region factible
es un conjunto convexo, (0, 80)
80
delimitado por rectas y
acotado, entonces por el (20, 60)
Teorema de existencia, 60

la función objetivo toma

su valor maximo en los 40

vértices de la región Región

Factible (40, 20)
factible. 20

(40, 0)
(0, 0) 20 40 60 80 X

19
 Método Analítico
Y
Calculemos el valor de z
en los vértices de la
100
región factible.
Vértice z = 3x + 2y 80
(0, 80)
(0, 0) 0
(20, 60)
(40, 0) 120 60

(40, 20) 160

40
(𝟐𝟎, 𝟔𝟎) 𝟏𝟖𝟎
Región
(0, 80) 160 20 Factible (40, 20)

La solución óptima es:

(40, 0)
x = 20 muñecos
(0, 0) 20 40 60 80 X
y = 60 trenes
z = 180 soles de beneficio
20
EJEMPLO: DORIAN AUTO

21
Ejemplo: Dorian Auto

La empresa quiere emprender una campaña publicitaria

en TV y tiene que decidir comprar los tiempos de anuncios
en dos tipos de programas: del corazón y fútbol. Cada
anuncio del programa del corazón es visto por 6 millones
de mujeres y 2 millones de hombres. Cada partido de
fútbol es visto por 3 millones de mujeres y 8 millones de
hombres. Un anuncio en el programa de corazón cuesta S/
50,000 y un anuncio del fútbol cuesta S/ 100,000. Dorian
Auto quisiera que los anuncios sean vistos por lo menos
30 millones de mujeres y 24 millones de hombres.

Dorian Auto quiere saber cuántos anuncios debe contratar en

cada tipo de programa para que el coste de la campaña
publicitaria sea mínimo.

22
 Formulación matemática del
PPLde Decisión: x = nº de anuncios en programa de corazón
Variables
y = nº de anuncios en programa de fútbol

Corazón Futbol
Coste
50 100
(miles de S/. / anuncio)
Vistas de Mujeres
6 3 ≥ 30
(millones/anuncio)
Vistas de Varones
2 8 ≥ 24
(millones/anuncio)

23
 Formulación matemática del
VariablesPPL
de Decisión: x = nº de muñecos producidos a la semana
y = nº de trenes producidos a la semana

Corazón Futbol
Coste total
50x 100y Min z = 50x + 100y
(miles de S/.)
Vistas de Mujeres 6x + 3y ≥ 30
6x 3y ≥ 30
(millones)
Vistas de Varones 2x + 8y ≥ 24
2x 8y ≥ 24
(millones)
x ≥ 0, y ≥ 0 (no
negatividad)

24
 Formulación matemática del
ParaPPL
el problema de Dorian Auto, combinando la función objetivo y
las restricciones, tenemos el siguiente modelo de optimización:

Min z = 50x + 100y (función objetivo)

Sujeto a (s.a:)
6 x + 3y ≥ 30 (restricción de acabado)
2x + 8y ≥ 24 (restricción de carpinteria)
x ≥ 0 (restricción de signo)
y ≥ 0 (restricción de signo)

25
 Región factible
Aplicando el Y Restricciones
Teorema de 14 6 x + 3y ≥ 30
separación 2x + 8y ≥ 24
12
graficamos cada 6x + 3y = 30 x ≥ 0
semiplano. 10 y ≥ 0
8 u = (6,3)
La intersección
6
de todos los
semiplanos 4
2x + 8y = 24
(restricciones)
2 u = (2,8)
nos da la región
factible.
X
2 4 6 8 10 12 14

26
 Región factible
Por el Teorema Y Restricciones
de la convexidad, 14 6 x + 3y ≥ 30
la región factible 2x + 8y ≥ 24
12
(al estar limitado 6x + 3y = 30 x ≥ 0
por rectas) es un 10 y ≥ 0
conjunto 8
Región
convexo. Factible
6

En este caso no 4
es acotada. 2x + 8y = 24
2

X
2 4 6 8 10 12 14

27
 Región factible
Los vértices de Y Restricciones
la región 14 6 x + 3y ≥ 30
factible son 2x + 8y ≥ 24
12
intersecciones 6x + 3y = 30 x ≥ 0
de dos rectas. 10 y ≥ 0
𝐀(𝟎, 𝟏𝟎)
8
Región
Factible
6

4
2x + 8y = 24
2
B(𝟒, 𝟐)
𝐂(𝟏𝟐, 𝟎)
X
2 4 6 8 10 12 14

28
 Método Gráfico
Y
Min z = 50x + 100y
14

Aplicando el Teoremas de
12
invarianza y de
monotonía, la función 𝐳 𝐀(𝟎, 𝟏𝟎)
10

se mantiene constante en Región

8
las rectas cuya normal es Factible
u = 50,100 , y 𝐳 decrece 6

a medida que las estas −w = (−1, −2)

4
rectas se desplazan en la
dirección del vector 2
B(𝟒, 𝟐)
normal −u = (−50, −100) 𝐂(𝟏𝟐, 𝟎)
X
Se podría usar el vector 2 4 6 8 10 12 14

normal −𝐰 = (−𝟏, −𝟐)

29
 Método Gráfico
Y
Min z = 50x + 100y
14

La última recta de z que

12
interseca (toca) la región
factible indica la solución 𝐀(𝟎, 𝟏𝟎)
10

óptima para el PPL. Para Región

8
el problema de Dorian Factible
Auto, esto ocurre en el 6

punto B(4,2) −u = (−1, −2)

4

La solución óptima es: 2

B(𝟒, 𝟐)
x = 4 anuncios en Corazón 𝐂(𝟏𝟐, 𝟎)
y = 2 anuncios en Futbol X
2 4 6 8 10 12 14
z = 400 mil soles

30
 Método Analítico
Min z = 50x + 100y Y 𝑮
14
𝑯
Vamos a tomar la región
factible que se muestra en la 12

figura y como es un conjunto 𝐀(𝟎, 𝟏𝟎)

10 𝐅
convexo, delimitado por Región
8
rectas y es acotado, entonces Factible
por el Teorema de existencia, 6

la función objetivo toma su 𝑬

4
valor mínimo en los vértices
de la región factible. 2
B(𝟒, 𝟐) 𝐂(𝟏𝟐, 𝟎)
Luego Podemos hacer crecer 2 4 6 8 10 12
𝐃14 X

la región factible
indefinidamente.
31
 Método Analítico
Calculemos el valor de z en los Y
vértices de la región factible. 14
𝑯
Vértice z = 3x + 2y 12

A(0, 10) 10000 𝐀(𝟎, 𝟏𝟎)

10 𝐅
B(4, 2) 𝟒𝟎𝟎 Región
8
C(12, 0) 6000 Factible
6
Los valores en los demás vértices
𝑬
de la region factible son mayores 4

que el valor en el vértice B

2
B(𝟒, 𝟐) 𝐂(𝟏𝟐, 𝟎)
La solución óptima es:
x = 4 anuncios en pr. corazón 2 4 6 8 10 12
𝐃14 X

y = 2 anuncios en pr. futbol

z = 400 mil soles
32
 Casos especiales
Los dos ejemplos anteriores, Gepetto y Dorian Auto,
tienen, cada uno, una única solución óptima.
No en todos los PPL ocurre esto. Se pueden dar
también las siguientes posibilidades:
• Algunos PPL tienen un número infinito de
soluciones óptimas.
• Algunos PPL no tienen soluciones factibles (no
tienen región factible).
• Algunos PPL son no acotados.

Veamos un ejemplo por cada caso:

33
Ejemplo 1: Número infinito de soluciones óptimas
Y
60
Consideremos el
u = (3,2)
siguiente problema: 50
C
max z = 3x + 2y
40
s.a: 3x + 2y ≤ 120
x + y ≤ 50 B
x ,y ≥ 0
30 Región
Factible
z = 120
Cualquier punto (solución) 20

situado en el segmento AB
z = 60
puede ser una solución 10
z = 100
óptima de z = 120.
A
10 20 30 40 50 X
34
Ejemplo 2: Sin soluciones factibles
Y
Consideremos el 60 No existe
siguiente problema: Región
Factible
50
max z = 3x + 2y x ≥ 30

s.a: 3x + 2y ≤ 120 40
x + y ≤ 50 y ≥ 30
x + y ≤ 50
x ≥ 30 30

y ≥ 30
x ,y ≥ 0 20

No existe región 10 3x + 2y ≤ 120

factible
10 20 30 40 50 X
35
 Ejemplo 3.1: PPL no acotado
Max z = 2x – y Y
6
u = (2, −1)
s.a: x– y ≤ 1
u u
2x + y ≥ 6 5

x, y ≥ 0
4 C: Región Factible
La funcion z se
2x + y = 6
mantiene constante en 3
las rectas cuya normal
x– y= 1
es u = (2, −1), y crece 2
en la dirección de u =
(2, −1) , pero estas 1
rectas no salen de la
región C (ya que no es
acotada). Por lo tanto 1 2 3 4 5 X
no existe máximo. 36
 Ejemplo 3.2: PPL no acotado
Min z = 2x – y Y −u −u −u = (−2,1)
6
s.a: x– y ≤ 1
2x + y ≥ 6 5

x, y ≥ 0
4 C: Región Factible
La funcion z se mantiene
2x + y = 6
constante en las rectas 3
cuya normal es u =
x– y= 1
(2, −1) , y decrece en la 2
dirección de −u = (−2,1),
pero estas rectas no salen 1
de la región C (ya que no
es acotada). Por lo tanto
no existe mínimo. 1 2 3 4 5 X
37