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. Ejemplo Gepetto S.L., manufactura
muñecos y trenes de madera. 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?
Variables de Decisión x = nº de muñecos
producidos a la semana y = nº de trenes producidos a la
semana Función Objetivo. En cualquier PPL, la
decisión a tomar es como maximizar (normalmente el
beneficio) o minimizar (el coste) de alguna función de las
variables de decisión. Esta función a maximizar o
minimizar se llama función objetivo. Max z = 3x + 2y El
objetivo de Gepetto es elegir valores de x e y para maximizar 3x
+ 2y. Usaremos la variable z para denotar el valor de la
función objetivo. La función objetivo de Gepetto
es: Este problema es un ejemplo típico de un problema de
programación lineal (PPL). Restricciones Son desigualdades
que limitan los posibles valores de las variables de
decisión. En este problema las restricciones vienen dadas
por la disponibilidad de horas de acabado y carpintería y
por la demanda de muñecos. También suele haber
restricciones de signo o no negatividad: x = 0 y = 0
Restricción 1: no más de 100 horas de tiempo de
acabado pueden ser usadas. Restricción 2: no más de
80 horas de tiempo de carpinteria pueden ser usadas.
Restricción 3: limitación de demanda, no deben
fabricarse más de 40 muñecos. Estas tres
restricciones pueden expresarse matematicamente por las
siguientes desigualdades: Restricción 1: 2 x + y = 100
Restricción 2: x + y = 80 Restricción 3: x = 40
Cuando x e y crecen, la función objetivo de Gepetto
también crece. Pero no puede crecer indefinidamente
porque, para Gepetto, los valores de x e y están limitados
por las siguientes tres restricciones: Restricciones
Además, tenemos las restricciones de signo: x = 0 e y =
0
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) 2 x + y = 100 (acabado) x + y = 80
(carpinteria) x = 40 (demanda muñecos) Variables de
Decisión x = nº de muñecos producidos a la
semana y = nº de trenes producidos a la semana
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) Para el problema de Gepetto,
combinando las restricciones de signo x = 0 e y = 0 con la
función objetivo y las restricciones, tenemos el siguiente
modelo de optimización: Formulación
matemática del PPL
Región factible x = 40 e y = 20 está en la
región factible porque satisfacen todas las restricciones
de Gepetto. Sin embargo, x = 15, y = 70 no está en la
región factible porque este punto no satisface la
restricción de carpinteria [15 + 70 > 80].
Restricciones de Gepetto 2x + y = 100 (restricción
finalizado) x + y = 80 (restricción carpintería) x
= 40 (restricción demanda) x = 0 (restricción
signo) y = 0 (restricción signo) 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.
Solución óptima La mayoría de PPL tienen
solamente una solución óptima. Sin embargo, algunos
PPL no tienen solución óptima, y otros PPL tienen
un número infinito de soluciones. Más adelante
veremos que la solución del PPL de Gepetto es x = 20 e y =
60. Esta solución da un valor de la función
objetivo de: z = 3x + 2y = 3·20 + 2·60 = 180 €
Cuando decimos que x = 20 e y = 60 es la solución
óptima, estamos diciendo que, en ningún punto en la
región factible, la función objetivo tiene un valor
(beneficio) superior a 180. Para un problema de
maximización, una solución óptima es un
punto en la región factible en el cual la función
objetivo tiene un valor máximo. Para un problema de
minimización, una solución óptima es un
punto en la región factible en el cual la función
objetivo tiene un valor mínimo. Se puede demostrar que la
solución óptima de un PPL está siempre en la
frontera de la región factible, en un vértice (si
la solución es única) o en un segmento entre dos
vértices contiguos (si hay infinitas soluciones)
Representación Gráfica de las restricciones 2x + y
= 100 Cualquier PPL con sólo dos variables puede
resolverse gráficamente. Por ejemplo, para representar
gráficamente la primera restricción, 2x + y = 100 :
Dibujamos la recta 2x + y = 100 (Gp:) 20 (Gp:) 20 (Gp:) 40 (Gp:)
60 (Gp:) 80 (Gp:) 40 (Gp:) 60 (Gp:) 80 (Gp:) 100 (Gp:) Y (Gp:) X
Elegimos el semiplano que cumple la desigualdad: el punto (0, 0)
la cumple (2·0 + 0 = 100), así que tomamos el
semiplano que lo contiene.
Dibujar la región factible Puesto que el PPL de Gepetto
tiene dos variables, se puede resolver gráficamente. La
región factible es el conjunto de todos los puntos que
satisfacen las restricciones: 2 x + y = 100 (restricción
de acabado) x + y = 80 (restricción de carpintería)
x = 40 (restricción de demanda) x = 0 (restricción
de signo) y = 0 (restricción de signo) Vamos a dibujar la
región factible que satisface estas restricciones.
(Gp:) Y (Gp:) X (Gp:) 20 (Gp:) 20 (Gp:) 40 (Gp:) 60 (Gp:) 80
(Gp:) 40 (Gp:) 60 (Gp:) 80 (Gp:) 100 2x + y = 100 Restricciones 2
x + y = 100 x + y = 80 x = 40 x = 0 y = 0 Dibujar la
región factible Teniendo en cuenta las restricciones de
signo (x = 0, y = 0), nos queda:
(Gp:) Y (Gp:) X (Gp:) 20 (Gp:) 20 (Gp:) 40 (Gp:) 60 (Gp:) 80
(Gp:) 40 (Gp:) 60 (Gp:) 80 (Gp:) 100 x + y = 80 Restricciones 2 x
+ y = 100 x + y = 80 x = 40 x = 0 y = 0 Dibujar la región
factible
(Gp:) Y (Gp:) X (Gp:) 20 (Gp:) 20 (Gp:) 40 (Gp:) 60 (Gp:) 80
(Gp:) 40 (Gp:) 60 (Gp:) 80 (Gp:) 100 x = 40 Restricciones 2 x + y
= 100 x + y = 80 x = 40 x = 0 y = 0 Dibujar la región
factible
(Gp:) Y (Gp:) X (Gp:) 20 (Gp:) 20 (Gp:) 40 (Gp:) 60 (Gp:) 80
(Gp:) 40 (Gp:) 60 (Gp:) 80 (Gp:) 100 2x + y = 100 x + y = 80 x =
40 La intersección de todos estos semiplanos
(restricciones) nos da la región factible Dibujar la
región factible Región Factible
(Gp:) Y (Gp:) X (Gp:) 20 (Gp:) 20 (Gp:) 40 (Gp:) 60 (Gp:) 80
(Gp:) 40 (Gp:) 60 (Gp:) 80 (Gp:) 100 2x + y = 100 x + y = 80 x =
40 Región Factible La región factible (al estar
limitada por rectas) es un polígono. En esta caso, el
polígono ABCDE. A B C D E Como la solución
óptima está en alguno de los vértices (A, B,
C, D o E) de la región factible, calculamos esos
vértices. Vértices de la región factible
Restricciones 2 x + y = 100 x + y = 80 x = 40 x = 0 y = 0
Región Factible E(0, 80) (20, 60) C(40, 20) B(40, 0) A(0,
0) Vértices de la región factible Los
vértices de la región factible son intersecciones
de dos rectas. El punto D es la intersección de las rectas
2x + y = 100 x + y = 80 La solución del sistema x = 20, y
= 60 nos da el punto D. (Gp:) 20 (Gp:) 20 (Gp:) 40 (Gp:) 60 (Gp:)
80 (Gp:) 40 (Gp:) 60 (Gp:) 80 (Gp:) 100 (Gp:) Y (Gp:) X D B es
solución de x = 40 y = 0 2x + y = 100 x = 40 x + y = 80 C
es solución de x = 40 2x + y = 100 E es solución de
x + y = 80 x = 0
(Gp:) Y (Gp:) X (Gp:) 20 (Gp:) 20 (Gp:) 40 (Gp:) 60 (Gp:) 80
(Gp:) 40 (Gp:) 60 (Gp:) 80 (Gp:) 100 Región Factible (0,
80) (20, 60) (40, 20) (40, 0) (0, 0) Max z = 3x + 2y z = 0 z =
100 z = 180 Para hallar la solución óptima,
dibujamos las rectas en las cuales los puntos tienen el mismo
valor de z. La figura muestra estas lineas para z = 0, z = 100, y
z = 180 Resolución gráfica
Región Factible (0, 80) (20, 60) (40, 20) (40, 0) (0, 0)
Max z = 3x + 2y z = 0 z = 100 z = 180 La última recta de z
que interseca (toca) la región factible indica la
solución óptima para el PPL. Para el problema de
Gepetto, esto ocurre en el punto D (x = 20, y = 60, z = 180).
(Gp:) 20 (Gp:) 20 (Gp:) 40 (Gp:) 60 (Gp:) 80 (Gp:) 40 (Gp:) 60
(Gp:) 80 (Gp:) 100 (Gp:) Y (Gp:) X Resolución
gráfica
Región Factible (0, 80) (20, 60) (40, 20) (40, 0) (0, 0)
Max z = 3x + 2y También podemos encontrar la
solución óptima calculando el valor de z en los
vértices de la región factible. Vértice z =
3x + 2y (0, 0) z = 3·0+2·0 = 0 (40, 0) z =
3·40+2·0 = 120 (40, 20) z = 3·40+2·20
= 160 (20, 60) z = 3·20+2·60 = 180 (0, 80) z =
3·0+2·80 = 160 (Gp:) 20 (Gp:) 20 (Gp:) 40 (Gp:) 60
(Gp:) 80 (Gp:) 40 (Gp:) 60 (Gp:) 80 (Gp:) 100 (Gp:) Y (Gp:) X La
solución óptima es: x = 20 muñecos y = 60
trenes z = 180 € de beneficio Resolución
analítica
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.
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.
Un problema de minimización Dorian Auto fabrica y vende
coches y furgonetas.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 50.000 € y un anuncio del fútbol cuesta
100.000 €. Dorian Auto quisiera que los anuncios sean vistos
por 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.
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
50.000 € y un anuncio del fútbol cuesta 100.000
€. Dorian Auto quisiera que los anuncios sean vistos por 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. Formulación del
problema:
Variables de decisión: x = nº de anuncios en programa
de corazón y = nº de anuncios en fútbol Min z
= 50x + 100y (función objetivo en 1.000 €) s.a: 6x +
3y = 30 (mujeres) 2x + 8y = 24 (hombres) x, y = 0 (no
negatividad) Formulación del problema:
(Gp:) X (Gp:) Y (Gp:) 2 4 6 8 10 12 14 (Gp:) 14 12 10 8 6 4 2 Min
z = 50 x + 100y s.a. 6x + 3y = 30 2x + 8y = 24 x, y = 0 6x + 3y =
30 2x + 8y = 24 Dibujamos la región factible.
(Gp:) X (Gp:) Y (Gp:) 2 4 6 8 10 12 14 (Gp:) 14 12 10 8 6 4 2 La
región factible no está acotada Región
Factible Calculamos los vértices de la región
factible: A B C El vértice A es solución del
sistema 6x + 3y = 30 x = 0 Por tanto, A(0, 10) El vértice
B es solución de 6x + 3y = 30 2x + 8y = 24 Por tanto, B(4,
2) El vértice C es solución de 2x + 8y = 24 y = 0
Por tanto, C(12, 0)
Región Factible Resolvemos por el método
analítico A(0, 10) B(4, 2) C(12, 0) (Gp:) X (Gp:) Y (Gp:)
2 4 6 8 10 12 14 (Gp:) 14 12 10 8 6 4 2 El coste mínimo se
obtiene en B. Solución: x = 4 anuncios en pr.
corazón y = 2 anuncios en futbol Coste z = 400 (mil
€) Evaluamos la función objetivo z en los
vértices.
Región Factible Resolvemos por el método
gráfico A(0, 10) B(4, 2) C(12, 0) (Gp:) X (Gp:) Y (Gp:) 2
4 6 8 10 12 14 (Gp:) 14 12 10 8 6 4 2 El coste mínimo se
obtiene en el punto B. Solución: x = 4 anuncios en pr.
corazón y = 2 anuncios en futbol Coste z = 400 (mil
€) Min z = 50 x + 100y s.a. 6x + 3y = 30 2x + 8y = 24 x, y =
0 Z = 600 Z = 400
Número de Soluciones de un PPL 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). 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: Veamos un ejemplo de
cada caso.
Número infinito de soluciones óptimas max z = 3x +
2y s.a: Cualquier punto (solución) situado en el segmento
AB puede ser una solución óptima de z =120.
Consideremos el siguiente problema: 3x + 2y = 120 x + y = 50 x ,
y = 0 (Gp:) 10 (Gp:) 10 (Gp:) 20 (Gp:) 30 (Gp:) 40 (Gp:) 20 (Gp:)
30 (Gp:) 40 (Gp:) 50 (Gp:) 50 (Gp:) 60 (Gp:) Y (Gp:) X z = 60 z =
100 z = 120 A B C Región Factible
Sin soluciones factibles s.a: max z = 3×1 + 2×2 No existe
región factible Consideremos el siguiente problema: 3x +
2y = 120 x + y = 50 x = 30 y = 30 x , y = 0 (Gp:) 10 (Gp:) 10
(Gp:) 20 (Gp:) 30 (Gp:) 40 (Gp:) 20 (Gp:) 30 (Gp:) 40 (Gp:) 50
(Gp:) 50 (Gp:) 60 (Gp:) Y (Gp:) X No existe Región
Factible y = 30 x = 30 x + y = 50 3x + 2y = 120
PPL no acotado max z = 2x – y s.a: x – y = 1 2x + y =
6 x, y = 0 La región factible es no acotada. Se muestran
en el gráfico las rectas de nivel para z = 4 y z = 6. Pero
podemos desplazar las rectas de nivel hacia la derecha
indefinidamente sin abandonar la región factible. Por
tanto, el valor de z puede crecer indefinidamente. (Gp:) 1 (Gp:)
1 (Gp:) 2 (Gp:) 3 (Gp:) 4 (Gp:) 2 (Gp:) 3 (Gp:) 4 (Gp:) 5 (Gp:) 5
(Gp:) 6 (Gp:) Y (Gp:) X z = 4 z = 6 Región Factible