PROGRAMACIÓN LINEAL

MÉTODO RÁFICO

FACULTAD DE CIENCIAS HUMANAS Y DE

LA EDUCACIÓN
PROGRAMA DE MAESTRIA EN
EDUCACIÓN
MENCIÓN EN ENSEÑANZA DE LA
MATEMÁTICA

Ing. Mg. Marco Guachimboza

Ejemplo
Gepetto S.L., manufactura muñecos y trenes de madera.
Cada muñeco:
• Produce un beneficio neto de 3 $.
• Requiere 2 horas de trabajo de acabado.
• Requiere 1 hora de trabajo de carpinteria.
Cada tren:
• Produce un beneficio neto de 2 $.
• Requiere 1 hora de trabajo de acabado.
• Requiere 1 hora trabajo de carpinteria.
Cada semana Gepetto puede disponer de:
• Todo el material que necesite.
• Solamente 100 horas de acabado.
• Solamente 80 horas de carpinteria.
También:
• La demanda de trenes puede ser cualquiera (sin límite).
• La demanda de muñecos es como mucho 40.

Gepetto quiere maximizar sus beneficios.

¿Cuántos muñecos y cuántos trenes debe fabricar?
 Este problema es un ejemplo típico de un problema de
programación lineal (PPL).

Variables de Función Objetivo. En cualquier Restricciones

Decisión PPL, la decisión a tomar es Son desigualdades que
como maximizar (normalmente el limitan los posibles
x = nº de muñecos beneficio) o minimizar (el coste) valores de las variables
producidos a la de alguna función de las de decisión.
semana variables de decisión. Esta En este problema las
y = nº de trenes función a maximizar o minimizar restricciones vienen
producidos a la se llama función objetivo. dadas por la
semana disponibilidad de horas
El objetivo de Gepetto es de acabado y carpintería
elegir valores de x e y para y por la demanda de
muñecos.
maximizar 3x + 2y. Usaremos
También suele haber
la variable z para denotar el restricciones de signo o
valor de la función objetivo. La no negatividad:
función objetivo de Gepetto es: x≥0
y≥0
 Formulación matemática del PPL
Variables de Decisión x = nº de muñecos producidos a la semana
y = nº de trenes producidos a la semana

Muñeco Tren

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

Acabado 2 1 ≤ 100 2 x + y ≤ 100 (acabado)

Carpintería 1 1 ≤ 80 x + y ≤ 80 (carpinteria)

Demanda ≤ 40 x ≤ 40 (demanda muñecos)

x ≥0 (restricción de signo)

y ≥0 (restricción de signo)
 Formulación matemática del PPL

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)
 Región factible

La región factible de un PPL es el conjunto de todos los puntos

que satisfacen todas las restricciones. Es la región del plano
delimitada por el sistema de desigualdades que forman las
restricciones.

x = 40 e y = 20 está en la región Restricciones de Gepetto

factible porque satisfacen todas 2x + y ≤ 100 (restricción finalizado)
las restricciones de Gepetto. x + y ≤ 80 (restricción carpintería)
Sin embargo, x = 15, y = 70 no x ≤ 40 (restricción demanda)
está en la región factible porque x ≥0 (restricción signo)
este punto no satisface la y ≥0 (restricción signo)
restricción de carpinteria
[15 + 70 > 80].
 Representación Gráfica de las restricciones
Y
Cualquier PPL con sólo dos
variables puede resolverse
100
gráficamente. 2x + y = 100

Por ejemplo, para representar 80

gráficamente la primera
restricción, 2x + y ≤ 100 :
60
Dibujamos la recta 2x + y = 100

Elegimos el semiplano que 40

cumple la desigualdad: el
punto (0, 0) la cumple
(2·0 + 0 ≤ 100), 20

así que tomamos el

semiplano que lo contiene.
20 40 60 80 X
 Dibujar la región factible
Y

100
2x + y = 100
Restricciones
2 x + y ≤ 100
80
x + y ≤ 80
x ≤ 40
60
x ≥0
y ≥0
40

Teniendo en
cuenta las 20
restricciones de
signo (x ≥ 0, y ≥ 0),
nos queda: 20 40 60 80 X
 Dibujar la región factible
Y

100

Restricciones 80

2 x + y ≤ 100
x + y ≤ 80 60 x + y = 80
x ≤ 40
x ≥0 40

y ≥0

20

20 40 60 80 X
 Dibujar la región factible
Y

100

Restricciones 80
x = 40
2 x + y ≤ 100
x + y ≤ 80 60

x ≤ 40
x ≥0 40

y ≥0

20

20 40 60 80 X
 Dibujar la región factible
Y
La intersección
de todos estos
semiplanos 100
2x + y = 100
(restricciones)
nos da la región
80
factible x = 40

60

x + y = 80
40

Región
20 Factible
Acotada

20 40 60 80 X
 Vértices de la región factible
Y Restricciones
La región factible (al
2 x + y ≤ 100
estar limitada por
rectas) es un polígono. 2x + y = 100 x + y ≤ 80
100
En esta caso, el x ≤ 40
polígono ABCDE. x ≥0
80 E x = 40
Como la solución y ≥0
óptima está en alguno
D
de los vértices (A, B, C, 60

D o E) de la región
x + y = 80
factible, calculamos 40
esos vértices.
Región
20 Factible C
Acotada
B
A 20 40 60 80 X
 Vértices de la región factible
Y
Los vértices de la región factible
son intersecciones de dos
rectas. El punto D es la 100
intersección de las rectas 2x + y = 100

2x + y = 100 x = 40
80 E(0, 80)
x + y = 80
La solución del sistema x = 20,
D (20, 60)
y = 60 nos da el punto D. 60

B es solución de
40
x = 40
y=0
Región
C es solución de C(40, 20)
20 Factible
x = 40 x + y = 80

2x + y = 100 B(40, 0)
E es solución de A(0, 0) 20 40 60 80 X
x + y = 80
x=0
 Solución óptima

Para un problema de maximización, una solución Se puede demostrar

óptima es un punto en la región factible en el cual que la solución
la función objetivo tiene un valor máximo. Para un óptima de un PPL
problema de minimización, una solución óptima es está siempre en la
un punto en la región factible en el cual la función frontera de la región
objetivo tiene un valor mínimo. factible, en un
vértice (si la
solución es única) o
La mayoría de PPL tienen solamente una solución
en un segmento
óptima. Sin embargo, algunos PPL no tienen
entre dos vértices
solución óptima, y otros PPL tienen un número
contiguos (si hay
infinito de soluciones.
infinitas soluciones)
 Resolución gráfica
Y
Max z = 3x + 2y

Para hallar la 100

solución óptima,
(0, 80)
dibujamos las 80
rectas en las
cuales los puntos (20, 60)
tienen el mismo 60

valor de z.
La figura muestra 40

estas lineas para

Región
z = 0, z = 100, y z (40, 20)
20 Factible
= 180
(40, 0)
(0, 0) 20 40 60 80 X
z = 180
z=0 z = 100
 Resolución gráfica
Y
Max z = 3x + 2y
La última recta de 100

z que interseca
(toca) la región (0, 80)
80
factible indica la
solución óptima (20, 60)
para el PPL. Para 60

el problema de
Gepetto, esto 40
ocurre en el
punto D (x = 20, y Región
(40, 20)
= 60, z = 180). 20 Factible
Cuando decimos que x = 20 e y = 60
(40, 0)
es la solución óptima, estamos
diciendo que, en ningún punto en la (0, 0) 20 40 60 80 X
región factible, la función objetivo tiene
un valor (beneficio) superior a 180. z = 180
z=0 z = 100
 Resolución analítica
Y
Max z = 3x + 2y
También podemos encontrar la 100
solución óptima calculando el
valor de z en los vértices de la
80
(0, 80)
región factible.

Vértice z = 3x + 2y (20, 60)

60
(0, 0) z = 3·0+2·0 = 0
(40, 0) z = 3·40+2·0 = 120
(40, 20) z = 3·40+2·20 = 160 40

(20, 60) z = 3·20+2·60 = 180

Región
(0, 80) z = 3·0+2·80 = 160 (40, 20)
20 Factible
La solución óptima única
(40, 0)
Factible es:
x = 20 muñecos (0, 0) 20 40 60 80 X
y = 60 trenes
z = $ 180 de beneficio
 Hemos identificado la región factible para el
problema de Gepetto y buscado la solución
óptima, la cual era el punto en la región
factible con el mayor valor posible de z.
Interpretación: Se deberá producir 20 muñecos y 60 trenes para
obtener un beneficio máximo de 180 dólares.

2 x + y ≤ 100 x + y ≤ 80 x ≤ 40 Se utilizó todas las horas

2(20)+60 ≤ 100 20+60 ≤ 80 20 ≤ 40 disponibles tanto en el
Proceso de acabado y
40+60≤ 100 80 ≤80 carpintería, además se
100 ≤ 100 degaron de hacer 20
muñecos
Recuerda que:

• La región factible en cualquier PPL

está limitada por segmentos (es un
polígono, acotado o no).

• La región factible de cualquier PPL

tiene solamente un número finito de
vértices.

• Cualquier PPL que tenga solución

óptima tiene un vértice que es óptimo.
 Número de Soluciones de un PPL

El ejemplo anteriors, Gepetto, tiene 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 (alternativas o múltiples
soluciones óptimas).
• Algunos PPL no tienen soluciones factibles (no
tienen región factible).
• Algunos PPL son no acotados: Existen puntos en
la región factible con valores de z arbitrariamente
grandes (en un problema de maximización).
Veamos un ejemplo de cada caso.
 Número infinito de soluciones óptimas
Y Nota: Un problema factible que tenga la recta
de iso‐beneficio(Z) paralela a la recta de una
Consideremos el siguiente 60 restricción que contenga un punto extremo
problema: óptimo, tendrá todo un segmento de puntos
óptimos.
max z = 3x + 2y C Para encontrar el punto Máximo trazamos las
50 rectas paralelas de Z con
s.a: 3x + 2y ≤ 120 respecto a cada vértice, observamos que el
mayor valor en el eje y, es el segmento AB, eso
x + y ≤ 50 40
implica que hay múltiples soluciones

x,y≥0
Cualquier punto (solución) B
30 Región
situado en el segmento AB Factible
puede ser una solución óptima z = 120

de z =120. 20

z = 60
Recuerda: En la resolución 10
analítica z = 100
Cuando hay al menos dos
puntos con el mismo valor A
de Z, entonces existen 10 20 30 40 50 X
soluciones óptimas múltiples
 Sin soluciones factibles
Y
Consideremos el siguiente 60
problema: No existe
Región Factible
max z = 3x1 + 2x2 50
x ≥ 30

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

x ≥ 30
y ≥ 30 30

x,y≥0
20

10 3x + 2y ≤ 120

No existe región factible

10 20 30 40 50 X
 PPL no acotado
max z = 2x – y Y
s.a: x–y≤1 6
Región Factible
2x + y ≥ 6
5
x, y ≥ 0

La región factible es no 4
acotada. Se muestran en el z=4
gráfico las rectas de nivel
3
para z = 4 y z = 6. Pero
podemos desplazar las
rectas de nivel hacia la 2

derecha indefinidamente sin z=6

abandonar la región factible. 1
Por tanto, el valor de z
puede crecer
indefinidamente. 1 2 3 4 5 X
 • Ing. Mg. Marco guahcimboza

24
Copyright (c) 2004 Brooks/Cole, a division of Thomson Learning, Inc.