Proyecto CLAVEMAT EPN
Curso en lnea:
Matemtica Discreta
Mdulo 1: Programacin Lineal
Contenidos: Carlos Ajila y Juan Carlos Trujillo
Estructura pedaggica: Victoria Novillo
Dibujos: Carlos Ajila y Andrs Miniguano
15 de febrero 15 de junio de 2016
ltima actualizacin: 14 de febrero de 2015
Programacin Lineal
Introduccin
En el primer ao del Bachillerato General Unificado ecuatoriano, el bloque Matemtica
Discreta aborda el estudio de la Programacin Lineal, herramienta de las matemticas
para maximizar o minimizar una cantidad, principalmente utilidad o costo, sujeta a un
conjunto de restricciones.
En este mdulo, te presentamos una introduccin a la Programacin Lineal a travs del
mtodo geomtrico denominado principio del vrtice que, por su potencia y sencillez,
es adecuado para ofrecer a las y los estudiantes una idea clara de la Programacin
Lineal, recurriendo exclusivamente a los conceptos y propiedades de las rectas en un
sistema de coordenadas.
Programas lineales
Un programa lineal o problema de programacin lineal es un problema que consiste
en maximizar o minimizar una funcin lineal, a la que llamars funcin objetivo, y
que est sujeta a varias restricciones expresadas mediante igualdades y desigualdades
lineales.
Ejemplos
1. Dada la funcin linealf : D R
(x, y) 7 2x 7y
donde
D =
(x, y) R2 :
2x + 3y 21,
3x + 2y 12,
y 5,
x 0,
y 0
,
1
se buscan todos los elementos (a, b) D para los que la funcin f toma el valor
ms pequeo posible; es decir, los puntos (a, b) que satisfagan la desigualdad
f (a, b) f (x, y)
para todo (x, y) D .
La siguiente es la manera como se enuncia este problema:
minimizar 2x 7y
sujeta a
2x + 3y 21,
3x + 2y 12,
y 5,
x 0,
y 0
Las letras x e y se denominan variables de decisin y las desigualdades
expresadas a travs de estas letras se llaman restricciones de la funcin
objetivo.
2. Dada la funcin linealf : D R
(x,y) 7 3x + y,
donde
D =
(x,y) R2 :
x 5y = 4,
4x y 3,
x + y 2,
x 0,
y 0
,
el programa lineal es el problema de encontrar todos los puntos (a,b) D en los
que la funcin f toma el valor ms grande posible; es decir,
f (a,b) f (x,y)
para todo (x,y) D .
En este caso, el problema se enuncia de la siguiente forma:
maximizar 3x + y
sujeta a
x 5y = 4,
4x y 3,
x + y 2,
x 0,
y 0
Observa que la primera restriccin de la funcin objetivo es una igualdad.
Proyecto CLAVEMAT-EPN 2 ltima actualizacin: 14-02-2016
3. En el siguiente programa lineal
maximizar 5x +2y 3z
sujeta a
2x y = 5,
8x 3y + z 13,
x + y 3z 4
x 0,
y 0,
z 0,
la funcin objetivo es la funcin lineal f definida por
f : D R
(x,y,z) 7 f (x,y,z) = 5x +2y 3z
donde
D =
(x, y, z) R3 :
2x y = 5,
8x 3y + z 13,
x + y 3z 4,
x 0,
y 0,
z 0.
.
El programa de programacin lineal consiste en encontrar todos los elementos
(a,b,c) del conjunto D que satisfacen la desigualdad
f (a,b,c) f (x,y,z)
para todo (x,y,z) D .
Observa que en este problema hay tres variables de decisin: x, y y z y una de
las restricciones es una igualdad: 2x y = 5.
Tal vez te preguntes por qu en los tres ejemplos las ltimas restricciones expresan que
las variables de decisin deben tomar valores reales positivos. En este curso no contars
con las herramientas necesarias para justificar el hecho de que incluir variables que
puedan tomar valores negativos eleva el problema a un alto grado de complejidad.
Otra caracterstica de los ejemplos presentados es que las restricciones se expresan
nicamente a travs de desigualdades del tipo menor o igual () o mayor o igual
(). La teora y los algoritmos desarrollados para resolver los problemas planteados no
se aplican cuando estn presentes desigualdades estrictas.
Proyecto CLAVEMAT-EPN 3 ltima actualizacin: 14-02-2016
Modelos de programas lineales
Concebimos que unmodelo matemtico es
un sistema de conceptos y smbolos matemticos que pretenden describir
uno o varios aspectos de un fenmeno o situacin de la realidad.
La construccin de un modelo con Programacin Lineal requiere de las siguientes
etapas:
1. Tipificacin del problema. En este paso se establece si el problema es de
maximizacin o deminimizacin.
2. Identificacin de las variables de decisin. En esta etapa se determinan las
variables de decisin que representan los elementos que caracterizan el
problema: si estos cambian, las soluciones tambin lo hacen.
3. Formulacin de la funcin objetivo. En este paso debers preguntarte: Qu
es lo que quiero maximizar o minimizar? La respuesta a esta pregunta tiene que
expresarse a travs de una funcin lineal.
4. Establecimiento de las restricciones. Aqu se expresarn los lmites de las
variables de decisin. Estos lmites son los que restringen a la funcin objetivo.
No obstante la gran variedad de problemas que se pueden resolver mediante
Programacin Lineal, uno de los ms sencillos (y ya clsico) es el denominado
problema de mezclas. Este consiste fundamentalmente en optimizar los costos de
produccin o la utilidad en la fabricacin de un cierto nmero de productos para lo cual
se dispone de una cantidad limitada de materia prima o recursos. Adems, en este
problema la demanda de los productos a fabricarse es una de las restricciones de la
funcin objetivo.
Ejemplo: El problema de mezclas
En una panadera se disear un programa de produccin diaria que le
permita obtener la mayor utilidad con la venta de los tres tipos de
panes que elabora: palanquetas, pan de yema y enrollados. La
demanda mnima diaria es de 100 unidades de palanquetas, 70 de pan
de yema y 230 unidades de enrollados.
Por otro lado, la elaboracin de:
20 palanquetas requiere 1 libra de harina y 2 huevos;
15 panes de yema, 1 libra de harina y 3 huevos; y
25 enrollados requiere 1 libra de harina nicamente.
Proyecto CLAVEMAT-EPN 4 ltima actualizacin: 14-02-2016
Adems, diariamente la panadera dispone nicamente de 50 libras de
harina y 8 docenas de huevos.
Finalmente, la utilidad diaria genera por la venta de:
una palanqueta es 2 centavos de dlar,
un pan de yema es 3 centavos, y
un enrollado es 2 centavos.
Cul es la produccin ptima? Es decir, cuntas unidades de
palanquetas, pan de yema y enrollados debern elaborarse
diariamente para obtener la mayor utilidad?
Solucin. Para resolver el problema, vas a seguir cada una de las etapas explicadas.
1. Tipificacin del problema. En este problema, se quiere disear un programa de
produccin diaria de pan para obtener la mayor utilidad posible. Por tanto, este es
un problema de maximizacin de la ganancia obtenida por la venta del pan de los
tripos.
2. Identificacin de las variables de decisin. El programa de produccin consiste
en averiguar cuntas unidades de cada tipo de pan deben elaborarse diariamente.
Luego, las variables de decisin son las siguientes:
Variable Significado
x nmero de unidades de palanquetas producidas diariamente,
y nmero de unidades de pan de yema producidas diariamente
z nmero de unidades de enrollados producidas diariamente
3. Formulacin de la funcin objetivo. Puesto que cada unidad de palanquetas tiene
un precio de venta de 2 centavos; es decir, 0.02 dlares, al venderse x unidades de
palanquetas, la ganancia obtenida sera de 0.02x dlares.
Un razonamiento similar te indica que la utilidad obtenida al vender y unidades de
pan de yema sera de 0.03y dlares por vender z unidades de enrollados, un total de
0.02z dlares. Luego, la utilidad total ser igual a
0.02x +0.03y +0.02z
dlares. Por tanto, la funcin objetivo es
(x, y, z) 7 0.02x +0.03y +0.02z.
4. Establecimiento de las restricciones. Como puedes notar, hay dos tipos de
restricciones: las impuestas por la demanda mnima de pan diaria y las impuestas
por las cantidad de materia prima que se dispone en la panadera.
Proyecto CLAVEMAT-EPN 5 ltima actualizacin: 14-02-2016
Cada da se debern elaborar al menos 100 unidades de palanquetas, 70 de pan
de yema y 230 de enrollados. Luego, las restricciones correspondientes son:
x 100,
y 70,
z 230.
Cada da se requiere una libra de harina para elaborar 20 palanquetas, 15 panes
de yema, y 25 enrollados. Entonces, para elaborar 1 palanqueta se requiere de
1/20 de libra de harina, para 1 pan de yema, 1/25 de libra de harina y para
1 enrollado, se necesita 1/25 de libra de harina. En resumen, en la panadera
deber haber120
x +115
y +125
z
libras de harina cada da.
Ahora bien, sabes que se dispone nicamente de 50 libras cada da. Por tanto,
las variables de decisin debern satisfacer la siguiente desigualdad:
120
x +115
y +125
z 50,
que es equivalente a
15x +20y +12z 15000.
Por otro lado, en lo que respecta a los huevos, se requieren 2 para hornear 20
palanquetas; es decir, cada palanqueta requiere de 2/20 o 1/10 de un huevo.
Para la elaboracin de 15 panes de yema, se requieren 3 huevos; es decir, cada
pan de yema necesita 3/15 o 1/5 de un huevo.
Finalmente, cada enrollado requiere de 2/25 de un huevo.
Luego, como se dispone de 8 docenas de huevos (96) cada da, las variables de
decisin deben tambin satisfacer la restriccin siguiente:
110
x +15y +
225
z 96
que es equivalente a:
5x +10y +4z 4800.
Por ltimo, no es posible producir una cantidad negativa de panes; luego, hay tres
restricciones adicionales:
x 0, y 0 y z 0.
Proyecto CLAVEMAT-EPN 6 ltima actualizacin: 14-02-2016
En resumen, el programa lineal para este problema de mezclas es el siguiente:
maximizar 0.02x +0.03y +0.02z
sujeta a
x 100,
y 70,
z 230,
15x + 20y + 12z 15000,
5x + 10y + 4z 4800,
x 0,
y 0,
z 0.
Observa que si x 100, entonces tambin ocurre que x 0. Luego, la restriccin x 0
es redundante. De manera anloga, las restricciones y 0 y z 0 son redundantes. Por
tanto, el programa lineal puede escribirse de manera ms concisa:
maximizar 0.02x +0.03y +0.02z
sujeta a
x 100,
y 70,
z 230,
15x + 20y + 12z 15000,
5x + 10y + 4z 4800.
Ejemplo: El problema de la dieta
El diseo del men para el almuerzo en el comedor de una escuela incluye siempre
zanahoria, col y pepino. La informacin nutricional y los costos de estos alimentos
se muestran en la siguiente tabla:
Alimento Zanahoria Col Pepino Requerimiento por porcin
Vitamina A [mg/kg] 35 0.5 0.5 0.5 mg
Vitamina C [mg/kg] 60 300 10 15 mg
Fibra [g/kg] 30 20 10 4g
Costo [$/kg] 0.75 0.5 0.15 -
Cul es la cantidad de cada alimento que debers utilizar en la preparacin de
manera que el costo de produccin sea el mnimo?
Solucin.
1. Tipificacin del problema. Puesto que buscas que costo de preparacin de cada
Proyecto CLAVEMAT-EPN 7 ltima actualizacin: 14-02-2016
plato de comida sea mnimo, este es un problema deminimizacin.
2. Identificacin de las variables de decisin. Las variables requeridas son la
siguientes:
Variable Significado
x Cantidad (en kg) de zanahoria en una porcin de comida
y Cantidad (en kg) de col en una porcin de comida
z Cantidad (en kg) de pepino en una porcin de comida
3. Formulacin de la funcin objetivo. Buscas minimizar el costo de produccin de
cada plato de comida. Luego, la funcin objetivo deber proveer dicho costo.
Para determinarla, supn que utilizas x kilogramos de zanahoria, y de col y z de
pepino; entonces, el costo de cada plato ser de
0.75x +0.5y +0.15z
dlares. Por tanto, la funcin objetivo es
(x, y, z) 7 0.75x +0.5y +0.15z.
4. Establecimiento de las restricciones. En primer lugar, considera las cantidades
mnimas de vitaminas A y C y de fibra en cada porcin de comida. Puesto que x [kg]
de zanahoria, y [kg] de col y z [kg] de pepino aportan con 35x [mg], 0.5y [mg] y 0.5z
[mg] de vitamina A, respectivamente, cada plato contendr
35x +0.5y +0.5z
miligramos de vitamina A. Pero, como se requieren al menos 0.5 [mg] de esta
vitamina, la funcin objetivo est sujeta a la siguiente restriccin:
35x +0.5y +0.5z 0.5.
Un razonamiento similar respecto de la vitamina B te da una segunda restriccin
para la funcin objetivo:
60x +300y +10z 15,
y en lo que respecta a la fibra, una tercera restriccin:
30x +20y +10z 4.
Finalmente, las cantidades requeridas de cada alimento son nmeros positivos. Por
tanto, tienes las siguientes tres restricciones adicionales:
x 0, y 0 y z 0.
Proyecto CLAVEMAT-EPN 8 ltima actualizacin: 14-02-2016
En resumen, el programa lineal para la dieta es el siguiente:
minimizar 0.75x +0.5y +0.15z
sujeta a
35x + 0.5y + 0.5z 0.5,
60x + 300y + 10z 15,
30x + 20y + 10z 4,
x 0,
y 0,
z 0.
El siguiente ejemplo es un problema complejo de la Programacin Lineal.
Ejemplo: El problema de cortar rollos de papel
Una fbrica de papel produce rollos de papel de 1 metro de alto cada uno. A partir
de estos se elaboran rollos para la venta de 12, 17, 30 y 42 centmetros de alto.
Para obtener los rollos con las alturas indicadas, se utilizan los siguientes cuatro
patrones de corte:
Longitud Patrn 1 Patrn 2 Patrn 3 Patrn 4
12 cm 3 1 0 1
17 cm 2 0 3 1
30 cm 1 0 0 2
42 cm 0 2 1 0
Desperdicio [cm] 0 4 7 11
Si un pedido de rollos de papel consiste de:
10 rollos de 30 centmetros,
15 de 42 centmetros,
12 de 17 centmetros, y
20 de 12 centmetros,
cuntos rollos de un metro se deben cortar con cada patrn para satisfacer este
pedido de manera que el desperdicio de papel sea mnimo?
Solucin.
1. Tipificacin del problema. Este es un problema de minimizacin pues se busca
Proyecto CLAVEMAT-EPN 9 ltima actualizacin: 14-02-2016
minimizar la cantidad de papel que se desperdicia.
2. Identificacin de las variables de decisin. Las variables a considerar son las
siguientes:
Variable Significado
x Nmero de rollos a ser cortados segn el patrn 1
y Nmero de rollos a ser cortados segn el patrn 2
z Nmero de rollos a ser cortados segn el patrn 3
w: Nmero de rollos a ser cortados segn el patrn 4
3. Formulacin de la funcin objetivo. Si se cortan x rollos segn el patrn 1, y segn
el patrn 2, z segn el patrn 3 y w segn el patrn 4, el desperdicio de papel ser de
0, 4y, 7z y 11w centmetros, respectivamente. Por tanto, la funcin objetivo ser
(x, y, z, w) 7 4y +7z +11w.
4. Establecimiento de las restricciones. En primer lugar, establece el nmero de rollos
de 12 centmetros que se obtendran: 3x con el patrn 1, y con patrn 2, 0 con el
tercer patrn y w rollos con el patrn 4. Luego, el total de rollos de 12 centmetros es
3x + y +w
de donde, como el pedido solicita 20 de esta longitud, la funcin objetivo est sujeta
a la restriccin
3x + y +w 20.
Demanera similar, puedes obtener tres restricciones adicionales. En efecto, en lo que
respecta a los rollos de 17 centmetros, tienes que la funcin objetivo est restringida
por la desigualdad
2x +3z +w 12;
segn los rollos de 30 centmetros:
x +2w 10;
y por los rollos de 40 centmetros:
2y + z 15.
Finalmente, la funcin objetivo est sujeta a las siguientes cuatro restricciones:
x 0, y 0, z 0 y w 0.
Proyecto CLAVEMAT-EPN 10 ltima actualizacin: 14-02-2016
Por tanto, el programa lineal para este problema es:
minimizar 4y +7z +11w
sujeta a
3x + y + + w 20,
2x + + 3z + w 12,
x + + 2w 10,
2y + z 15,
x 0,
y 0,
z 0,
w 0.
La regin factible
En esta seccin vas a aprender a resolver un programa lineal cuya funcin objetivo
tiene nicamente dos variables, debido a que apela a la representacin geomtrica de
la funcin objetivo y las restricciones. Para problemas con ms variables, existen
herramientas computacionales que te permiten resolver fcilmente un programa lineal.
Recuerda que la representacin grfica de una ecuacin lineal (igualdad) es una recta
en el plano cartesiano y la de una inecuacin lineal (desigualdad) es un semiplano que
tiene como borde o arista la recta correspondiente de la inecuacin.
A modo de recordatorio, te presentaremos ejemplos de las representaciones grficas de
ecuaciones e inecuaciones.
Proyecto CLAVEMAT-EPN 11 ltima actualizacin: 14-02-2016
Ejemplo
La grfica de la ecuacin lineal
3x 2y = 4
es la siguiente:
En cambio, la desigualdad
3x 2y 4
representa la siguiente regin del plano:
Para identificar esta regin, se ha utilizado el principio geomtrico denominado
axioma de separacin del plano :
Proyecto CLAVEMAT-EPN 12 ltima actualizacin: 14-02-2016
Una recta divide al plano cartesiano en dos regiones no vacas,
disjuntas y convexas, de modo que:
el segmento que une dos puntos en una misma regin no interseca la
recta; y
el segmento que une dos puntos en regiones diferentes interseca
siempre la recta dada.
Para determinar cul de estas regiones es la buscada, se procede de la siguiente
manera:
1. Elige dos puntos: uno a cada lado de la recta; por ejemplo, los puntos Q = (2,0)
y P = (0,0).
2. Verifica si estos puntos satisfacen la desigualdad. En el caso del punto Q ,
tenemos que
6 = 3 22 0 4;
luego no la satisface. En cambio el punto P s:
0 = 3 02 0 4.
3. La regin que contiene a P es la regin buscada:
Recuerda que los programas lineales contienen nicamente desigualdades del tipo y
y, por tanto, la recta que delimita las regiones del plano determinadas por inecuaciones
de este tipo tambin pertenece a tales regiones.
Para que resulte ms sencillo identificar grficamente cul de las dos regiones
representa una desigualdad, usars una flecha que inicie en el borde del semiplano y
que apunte en la direccin de la regin de los puntos que satisfacen la desigualdad. Por
Proyecto CLAVEMAT-EPN 13 ltima actualizacin: 14-02-2016
ejemplo, el semiplano determinado por la desigualdad x + y 0 se representa
grficamente as:
Ahora te mostramos algunos ejemplos de la representacin grfica de las restricciones
de un programa lineal.
Ejemplos
1. La representacin grfica de cada una de las siguientes desigualdades
2x + 4y 17,
2x + y 8,
2x + y 0,
y 0.
produce la siguiente figura:
Proyecto CLAVEMAT-EPN 14 ltima actualizacin: 14-02-2016
que es la regin encerrada por el polgono cuyos vrtices son los puntos O , P ,
Q y R.
2. Las siguientes desigualdades
x + 3y 12,
3x + y 12,
5x + 9y 45.
tambin producen una regin factible vaca:
3. La representacin grfica de las desigualdades
x + y 4,
3x + y 4,
x + 5y 6
es la siguiente:
Proyecto CLAVEMAT-EPN 15 ltima actualizacin: 14-02-2016
En este caso la regin es infinita, en el sentido de que no se puede encerrar por
un polgono. Este tipo de regiones aparecen en problemas reales y las llamars
regiones no acotadas.
4. En los ejemplos anteriores han aparecido nicamente desigualdades; en el
siguiente aparece una igualdad:
4x + 3y 12,
x + 2y 2,
2x + y = 5
tiene como grfica la siguiente:
Las desigualdades representan una regin, pero al incluir la igualdad, debes
Proyecto CLAVEMAT-EPN 16 ltima actualizacin: 14-02-2016
considerar la parte de esta regin que se interseca con la recta determinada por
dicha igualdad. El resultado es en este caso un segmento de recta de extremos
E y F .
A continuacin te presentamos las definiciones de los diferentes tipos de regiones que
has visto.
Definicin: Regin factible
Llamars regin factible de un programa lineal al conjunto de todos los puntos
que verifican todas las restricciones correspondientes.
La representacin grfica de la regin factible lleva el nombre de polgono
asociado al programa lineal.
Cuando no exista ningn punto que verifique simultneamente todas las
restricciones de un programa lineal, la regin factible se denominar vaca.
Si la regin factible consiste de un nico punto, se dir que regin factible se
degenera a un punto.
Si el polgono asociado al programa lineal es un segmento de recta, dirs que la
regin factible se degenera a un segmento.
Cuando puedas encerrar al polgono asociado al programa lineal dentro de una
circunferencia que tenga centro en el origen del plano cartesiano, dirs que la
regin factible est acotada.
Los siguientes ejemplos ilustran los casos anteriores.
Ejemplos
1. La regin factible del programa lineal
minimizar 3x 8y +1
sujeta a
x + y 2,
x 0,
y 0
se representa grficamente as:
Proyecto CLAVEMAT-EPN 17 ltima actualizacin: 14-02-2016
Como puedes ver, no posee punto alguno; es decir, es vaca.
Se puede apreciar que los tres semiplanos determinados por cada restriccin
no se intersecan, lo que se interpreta como el hecho de que no existen puntos
que satisfagan las tres restricciones simultneamente.
Puedes llegar a la misma conclusin sin la necesidad de dibujar las
desigualdades. En efecto, supn que existe un punto (a, b) que s satisface las
tres restricciones simultneamente; es decir, el punto (a, b) satisface las tres
desigualdades:a + b 2,
a 0,
b 0
.
Ahora bien, a 0 es equivalente a a 0 de donde, como b 0, obtienes
a+ b 0.
Pero tambin tienes la restriccin
a+ b 2.
Entonces tienes que
2 a+ b 0,
lo que, por la propiedad transitiva de las desigualdades, produce la desigualdad
2 0
que es falsa. Esta contradiccin se obtiene por la suposicin de la existencia del
punto (a,b). Eso quiere decir que la regin factible es vaca.
Proyecto CLAVEMAT-EPN 18 ltima actualizacin: 14-02-2016
2. La regin factible del programa lineal
maximizar 5x +3y 2
sujeta a
2x + y 6,
x + 2y 6,
x + y 4
se degenera al punto (2, 2) como puedes observar en la representacin grfica
correspondiente:
Observa que el punto A es el nico que satisface las tres restricciones del
programa lineal.
Puedes deducir esto sin necesidad de recurrir al grfico. En efecto, si (x,y) son
las coordenadas del punto A, este satisface las tres desigualdades:
2x + y 6,
x + 2y 6,
x + y 4.
.
Si sumas trmino a trmino las dos primeras, obtendrs
3x +3y 12
de donde, al dividirla entre 3, obtienes
x + y 4
Proyecto CLAVEMAT-EPN 19 ltima actualizacin: 14-02-2016
que, junto con la tercera restriccin, te da
4 x + y 4;
es decir,
x + y = 4
o, lo que es lo mismo,
y = 4 x.
De esta igualdad y las dos primeras restricciones, obtienes
x + 4 6,
x + 8 6,
lo que es equivalente a tenerx 2
x 2.
Pero la segunda de estas desigualdades es equivalente a la desigualdad x 2;
luego,
2 x 2,
lo que significa que x = 2 y que, junto con y = 4 x, te y = 2.
En resumen, (x,y) = (2,2) como lo muestra el grfico.
3. En un ejemplo anterior, viste que la regin factible correspondiente de un
conjunto de desigualdades y una igualdad es un segmento de recta. En este
ejemplo, la regin factible tambin es un segmento aunque no hayan
igualdades.minimizar x +2y 5
sujeta a
x 2y 2,
x 2y 2,
5x + 6y 30,
3x + y 3.
La representacin grfica de la correspondiente regin factibles es
Proyecto CLAVEMAT-EPN 20 ltima actualizacin: 14-02-2016
Como puedes ver, la regin factible consta nicamente de los puntos del
segmento de extremos Q y R.
4. La regin factible del programa lineal
maximizar 4x +3y +2
sujeta a
3x + y 3,
x 3y 3,
x + y 1,
5x + 4y 20
es acotada porque el grfico del polgono asociado al programa lineal puede ser
encerrado en una circunferencia cuyo centro est en el origen:
Proyecto CLAVEMAT-EPN 21 ltima actualizacin: 14-02-2016
5. La regin factible del siguiente programa lineal no est acotada:
maximizar 2x 3y 4
sujeta a
x + y 2,
x 0,
y 0,
y 5,
como puedes apreciarlo en el siguiente dibujo:
Observa que no hay circunferencia que pueda encerrar esta regin.
Antes de seguir, te presentamos la definicin de restriccin redundante.
Proyecto CLAVEMAT-EPN 22 ltima actualizacin: 14-02-2016
Definicin: Restriccin redundante
Llamars a una restriccin de un programa lineal redundante si este programa y
el que se obtiene al eliminar la restriccin tienen el mismo polgono asociado.
Ejemplo
El polgono asociado al programa lineal
minimizar 2x +2y 5
sujeta a
2x + 3y 12,
2x + y 8,
5x + 6y 30,
x 0,
y 0
es el siguiente:
Ahora bien, si eliminas la restriccin
5x +6y 30
Proyecto CLAVEMAT-EPN 23 ltima actualizacin: 14-02-2016
obtendrs el nuevo programa lineal
minimizar 2x +2y 5
sujeta a
2x + 3y 12,
2x + y 8,
x 0,
y 0
cuyo polgono asociado es
y que es igual al del programa lineal original.
En la seccin siguiente, te presentaremos el principio principio del vrtice en el que se
fundamenta el mtodo de solucin de un problema de programacin lineal con dos
variables.
En matemtica, existen varios objetos que llevan el nombre de vrtice. En este curso
adoptars la siguiente definicin:
Definicin: Vrtice
Un vrtice de un polgono convexo es un punto sobre uno de los lados del polgono
tal que puede trazarse un segmento de recta que pase a travs de l y que cumpla
las tres condiciones siguientes:
Proyecto CLAVEMAT-EPN 24 ltima actualizacin: 14-02-2016
El vrtice no es ninguno de los extremos del segmento.
El segmento no corta ningn otro punto de los lados del polgono.
El segmento no puede tener uno de sus extremos dentro del polgono y el
otro extremo fuera.
Ejemplo
A travs del siguiente grfico vas a identificar un vrtice y un punto que no lo es.
El punto F es un vrtice del polgono, pues se encuentra sobre el borde del polgono
y, adems, sobre l se ha trazado el segmento de extremos H y G que verifican las
tres condiciones exigidas para ser vrtice.
Del mismo modo, puedes ver que los puntos A, B , C , D y E son tambin vrtices del
polgono.
Por otro lado, el punto M, que se encuentra sobre el borde del polgono, no es un
vrtice. Por qu? Porque si trazas dos segmentos que pasen por el punto M, uno
que tenga la misma direccin que el lado donde se encuentra dicho punto y otro
con una direccin diferente.
En el primer caso, el segmento tiene como extremos los puntos I y J , y tiene ms
de un punto en comn con el lado del polgono de extremos D y C .
En el segundo caso, el segmento de extremos K y L tiene un extremo dentro del
polgono y el otro, fuera.
La pregunta que surge a continuacin es:
cmo se calculan los vrtices de un polgono asociado a un programa
lineal?
Como podrs observar en los distintos ejemplos presentados hasta ahora, los vrtices
siempre se encuentran sobre el borde de los semiplanos. Recuerda que el borde del
Proyecto CLAVEMAT-EPN 25 ltima actualizacin: 14-02-2016
semiplano es una recta, que se obtiene al sustituir los smbolos o por = de la
respectiva desigualdad. Luego, cada vrtice es el punto de interseccin de dos de estas
rectas.
Ahora bien, notars que no todos los puntos que verifican las dos propiedades
mencionadas pertenecen a la regin factible; por ello, debes determinar cules de
estos s verifican todas las restricciones del programa lineal.
A continuacin, te presentamos el procedimiento para encontrar los vrtices del
polgono asociado al programa lineal.
Paso 1.- Cambia todos los smbolos de desigualdad ( y ) que aparezcan en las
restricciones por el smbolo =.
Paso 2.- Resuelve todos los sistemas de dos ecuaciones obtenidos en el paso 1.
Paso 3.- Identifica qu soluciones pertenecen a la regin factible. Estos sern los
vrtices del polgono asociado.
Ejemplo
Aplica el procedimiento anterior para identificar los vrtices del polgono asociado
al siguiente programa lineal:
minimizar 4x 2y
sujeta a
x 4y 0,
x + y 5,
x + 2y 8,
5x + 4y 16.
Solucin. Para ello, grafica el polgono asociado. Obtendrs el siguiente dibujo:
Proyecto CLAVEMAT-EPN 26 ltima actualizacin: 14-02-2016
Paso 1.- Sustituye los smbolos de desigualdad por el smbolo de igualdad; obtienes
el siguiente sistema de ecuaciones lineales:
x 4y = 0,
x + y = 5,
x + 2y = 8,
5x + 4y = 16.
Paso 2.- Resuelve los 6 sistemas de dos ecuaciones lineales.
Empieza con el sistema formado por las ecuaciones
x 4y = 0 y x + y = 5.
Obtendrs que
y = 1 y x = 4.
Luego el punto de coordenadas (4, 1), que corresponde al punto C de la grfica, es
un candidato a ser un vrtice de la regin factible.
Ahora considera el sistema:
x 4y = 0
x + 2y = 8,
cuya solucin es el punto de coordenadas (16/3,4/3) y que corresponde al punto F
en la grfica.
El sistema
x 4y = 0
5x + 4y = 16
tiene como solucin el punto (4,1), que es el punto D en la grfica.
La solucin del sistema
x + y = 5
x + 2y = 8
est dada por el punto B en la grfica, cuyas coordenadas son (2, 3).
El siguiente sistema es
x + y = 5
5x + 4y = 16.
Su solucin es el punto (4/9,41/9) y corresponde al punto E de la grfica.
Finalmente, queda el sistema
x + 2y = 8
5x + 4y = 16.
Su solucin est dada por el punto (0, 4), que es el punto A en la grfica.
Proyecto CLAVEMAT-EPN 27 ltima actualizacin: 14-02-2016
Paso 3.- Ahora debes verificar qu puntos de los encontrados en el paso anterior
satisfacen todas las restricciones.
El punto A satisface todas las restricciones:
Restriccin Evaluacin Significado
x 4y 0 04 4 = 16 0 Verifica la restriccin
x + y 5 0+4 = 4 5 Verifica la restriccin
x +2y 8 0+2 4 = 8 8 Verifica la restriccin
5x +4y 16 5 0+4 4 = 16 16 Verifica la restriccin
Luego,
el punto A es un vrtice del polgono asociado.
Mira lo que sucede con el punto F :
Restriccin Evaluacin Significado
x 4y 0163
4 43= 0 0 Verifica la restriccin
x + y 5163
+43=203 5 No verifica la restriccin
x +2y 8163
+2 43= 8 8 Verifica la restriccin
5x +4y 16 5 163
+4 43=
643
16 Verifica la restriccin
No satisface una de las restricciones por lo que no pertenece a la regin factible y, por
tanto, no es un vrtice.
Con un procedimiento similar, verifica los resultados de la siguiente tabla:
Punto Coordenadas Observacin
A (0,4) Satisface todas las restricciones
B (2,3) Satisface todas las restricciones
C (4,1) Satisface todas las restricciones
D (4,1) Satisface todas las restricciones
E (4/9,41/9) No satisface la restriccin x +2y 8
F (16/3,4/3) No satisface la restriccin x + y 5
En conclusin, los puntos A, B , C y D son los vrtices del polgono.
En la prctica, la determinacin de los vrtices se realiza grficamente.
Proyecto CLAVEMAT-EPN 28 ltima actualizacin: 14-02-2016
Cmo proceder si el programa lineal tiene ms de dos variables?
La complejidad del estudio de la regin factible se incrementa a medida que crece el
nmero de variables. Aunque con tres variables es posible graficar las restricciones, el
trabajo puede resultar bastante complicado. A partir de cuatro variables, no haymanera
de dibujar las restricciones. En ese caso se recurre a aplicaciones informticas que nos
permitirn resolver los problemas con relativa sencillez.
El principio del vrtice
El principio del vrtice expresa de manera sencilla cul es la solucin de un programa
lineal con dos variables cuando su regin factible es acotada. Podrs aprender
fcilmente su utilizacin a travs de los ejemplos que te presentamos a continuacin.
Al final de esta seccin te ofreceremos una explicacin de por qu el mtodo funciona.
Definicin: Solucin de un programa lineal
Un punto (a,b) es solucin de un programa lineal si y solo si
El punto (a,b) est en la regin factible (es decir, verifica todas las
restricciones del programa lineal), y
la funcin objetivo alcanza su valor mximo o su valor mnimo en el punto
(a,b).
Recuerda que el significado de que f alcance un mximo en el punto (a,b) significa que
si (x,y) es cualquier otro punto de la regin factible, debe verificarse la desigualdad
f (x,y) f (a,b).
De manera anloga, que f alcance un valor mnimo en el punto (a,b) significa que para
cualquier otro punto (x,y) en la regin factible, se tiene
f (x,y) f (a,b).
Proyecto CLAVEMAT-EPN 29 ltima actualizacin: 14-02-2016
Principio: Principio del vrtice
En un programa lineal cuya regin factible es acotada, la solucin es uno de los
vrtices de dicha regin.
Sorprendente!, verdad? Observa la sencillez del resultado:
cuando la regin factible es acotada, todo lo que debes hacer para encontrar
la solucin es determinar los vrtices de esta regin. Al menos uno de ellos
ser la solucin del programa lineal.
Ejemplos
1. Considera el programa lineal
minimizar 4x 2y
sujeta a
x 4y 0,
x + y 5,
x + 2y 8,
5x + 4y 16.
En el ltimo ejemplo de la seccin anterior calculaste los vrtices de la regin
factible de este problema:
A(0,4), B(2,3), C(4,1) y D(4,1).
Si calculas los valores que toma la funcin objetivo en cada uno de estos
vrtices, obtendrs lo siguiente:
Vrtice Coordenadas Valor de 4x 2y
A (0,4) 4 02 4 = 8
B (2,3) 4 22 3 = 2
C (4,1) 4 42 1 = 14
D (4,1) 4 (4)2 (1) = 14
Como puedes ver, la funcin objetivo alcanza su valor ms pequeo, 14, en el
vrtice D(4,1). Luego, la solucin al programa lineal es el punto D(4,1).
Proyecto CLAVEMAT-EPN 30 ltima actualizacin: 14-02-2016
2. Considera el programa lineal anterior ligeramente modificado:
minimizar 4x 2y +4
sujeta a
x 4y 0,
x + y 5,
x + 2y 8,
5x + 4y 16.
Como la regin factible es la misma que en el problema anterior, los vrtices son
los mismos. Los valores que toma la nueva funcin objetivo para este programa
lineal en los vrtices son los siguientes:
Vrtice Coordenadas Valor de 4x 2y +4
A (0,4) 4 02 4+4 = 4
B (2,3) 4 22 3+4 = 6
C (4,1) 4 42 1+4 = 18
D (4,1) 4 (4)2 (1) + 4 = 10
Como puedes ver, el mnimo se alcanza en el mismo vrtice D(4,1).
Los dos ejemplos anteriores, son un caso particular del siguiente concepto:
Definicin: Programas lineales equivalentes
Dos programas lineales son equivalentes si ambos tienen la misma solucin.
Los programas lineales de los dos ejemplos anteriores son equivalentes, pues ambos
tienen la misma solucin. El siguiente es un principio que establece condiciones
suficientes para la equivalencia de programas lineales.
Principio
Supn que dos programas lineales:
1. Tienen la misma regin factible;
2. al menos uno de los dos tiene solucin;
3. sus funciones objetivo son f (x,y) y g(x,y), respectivamente; y
4. c es una constante.
Proyecto CLAVEMAT-EPN 31 ltima actualizacin: 14-02-2016
Entonces, puedes concluir que:
Si f (x,y) = g(x,y) + c y ambos programas lineales son de maximizacin o
ambos son de minimizacin, los programas lineales son equivalentes.
Si f (x,y) = g(x,y) + c y uno de los programas lineales es de maximizacin y
el otro es de minimizacin, los programas lineales son equivalentes.
A continuacin te presentamos varios ejemplos que ilustran el uso de este principio.
Ejemplo
Considera los siguientes programas lineales:
1. Programa lineal 1:
maximizar 5x +6y 3
sujeta a
2x + y 4,
2x + y 7,
x + 2y 8,
2x + y 16,
x + 3y 0.
2. Programa lineal 2:
maximizar 5x +6y +2
sujeta a
2x + y 4,
2x + y 7,
x + 2y 8,
2x + y 16,
x + 3y 0.
3. Programa lineal 3:
maximizar 5x +6y
sujeta a
2x + y 4,
2x + y 7,
x + 2y 8,
2x + y 16,
x + 3y 0.
Las siguientes con las respectivas funciones objetivo:
f (x,y) = 5x +6y 3, g(x,y) = 5x +6y +2 y h(x,y) = 5x 6y.
Proyecto CLAVEMAT-EPN 32 ltima actualizacin: 14-02-2016
Como los tres programas lineales tienen las mismas restricciones, tambin tienen
la misma regin factible.
Adems, observa que
f (x,y) = g(x,y) + (5)
f (x,y) = h(x,y) + (3).
Esto significa que los programas lineales 1 y 2 son equivalentes, y tambin lo son
los programas lineales 1 y 3. En otras palabras, los tres programas lineales tienen
la misma solucin. De este modo, si resuelves uno de ellos, los otros dos quedan
resueltos tambin.
Resuelve el programa lineal 1. Para ello, obtn el polgono asociado:
Los vrtices de este polgono son los puntos:
A = (0,0), B = (1,2), C = (0,4), D = (3,1) y E = (2,3).
Ahora calcula los valores que toma la funcin objetivo en estos puntos. Obtienes
lo siguiente:
Proyecto CLAVEMAT-EPN 33 ltima actualizacin: 14-02-2016
Vrtice Coordenadas Valor de 5x +6y 3
A (0,0) 5 0+6 03 = 3
B (1,2) 5 (1) + 6 23 = 14
C (0,4) 5 0+6 43 = 21
D (3,1) 5 3+6 13 = 12
D (2,3) 5 2+6 33 = 5
Luego, el mximo es alcanzado en el vrtice C ; por tanto, el punto (0,4) es la
solucin para los tres programas lineales.
Por qu funciona el principio del vrtice?
A continuacin te ofrecemos una explicacin de por qu el principio del vrtice te
provee la solucin de un programa lineal cuya regin factible es acotada.
Para ello, requieres de la siguiente definicin:
Definicin: Curvas de nivel
Las curvas de nivel de una funcin lineal f : D R definida por f (x,y) = ax+by+
c, son todas las rectas que tienen por ecuacin
ax + by + c = k
donde k es una constante.
Por otra parte, recuerda que dos rectas son paralelas si y slo si tienen la misma
pendiente; luego, es claro, de la definicin anterior, que
una recta es una curva de nivel de f (x,y) si y slo si es paralela a la recta de
ecuacin f (x,y) = 0.
Ejemplo
Considera la funcin lineal f : R2 R, definida por
f (x,y) = 2x 3y +1.
Proyecto CLAVEMAT-EPN 34 ltima actualizacin: 14-02-2016
Las siguientes son los grficos de las curvas de nivel para f donde k = 6, k = 3,
k = 0, k = 3, k = 6 y k = 9:
Propiedades de las curvas de nivel
Considera la funcin lineal f definida por f (x,y) = ax + by + c. Sus curvas de nivel estn
representadas por las ecuaciones de la forma
ax + by + c = k.
Si b > 0,
1. las curvas de nivel se trasladan hacia arriba conforme el valor de k se incrementa
y
2. se desplazan hacia abajo conforme el valor de k disminuye.
En cambio, si b < 0,
1. las curvas de nivel se mueven hacia abajo al incrementarse el valor de k y
2. se mueven hacia arriba cuando k disminuye.
Finalmente, si b = 0, las curvas de nivel son rectas verticales; luego, consideramos los
siguientes casos:
1. Si a > 0, las rectas verticales se trasladan hacia la derecha al incrementarse el
valor de k y hacia la izquierda en caso de que el valor de k disminuya.
Proyecto CLAVEMAT-EPN 35 ltima actualizacin: 14-02-2016
2. Si a < 0, las rectas se mueven hacia la derecha al disminuir el valor de k y hacia la
izquierda en el caso contrario.
Con esto en mente, ests listo para mirar por qu funciona el principio del vrtice.
El principio del vrtice tras bambalinas
A menos que se diga lo contrario, f representar la funcin objetivo de un programa
lineal definida por
f (x,y) = ax + by + c.
Hay ocho posibilidades:
Caso Parmetros Tipo de problema
1 b > 0 Maximizacin
2 b > 0 Minimizacin
3 b < 0 Maximizacin
4 b < 0 Minimizacin
5 b = 0 y a > 0 Maximizacin
6 b = 0 y a > 0 Minimizacin
7 b = 0 y a < 0 Maximizacin
8 b = 0 y a < 0 Minimizacin
Por el teorema de equivalencia de programas lineales, estos ocho casos se reducen a
cuatro. En efecto, en primer lugar, la regin factible es la misma. Luego,
en el caso 3, maximizar ax +by+ c es lo mismo que minimizar ax by c y, como
b < 0, tienes que b > 0; por tanto, este caso es el mismo que el 2.
En el caso 4, minimizar ax + by+ x es equivalente a maximizar ax by c y, dado
que b < 0, tienes b > 0; de modo que este caso es el 1.
De manera similar, puedes observar que el caso 7 es el caso 6 y el 8, el caso 5. De forma
que de los ocho casos te has quedado nicamente con cuatro.
Casos 1 y 2.- Imagina que el polgono asociado al programa lineal es el siguiente:
Proyecto CLAVEMAT-EPN 36 ltima actualizacin: 14-02-2016
Has representado tambin la curva de nivel ax + by + c = k con k = k0; esta atraviesa
el polgono. Ahora, como b > 0, al incrementar los valores de k, la curva de nivel se
desplazar hacia arriba. Incrementa los valores de k todo lo que sea posible mientras
la curva est en la regin factible. Supn que
k0 < k1 < k2 < < kM
y, a partir de kM , ya no puedes dar nuevos valores, puesto que la curva de nivel saldra
de la la regin factible. El siguiente dibuja la situacin:
Puedes observar que la curva de nivel toca el vrtice C (que supondrs tiene
Proyecto CLAVEMAT-EPN 37 ltima actualizacin: 14-02-2016
coordenadas (xM ,yM )) y ya no puedes incrementar los valores de k sin salirte de la
regin factible; es decir, el valor de
ax + by + cz = k
ya no puede ser incrementado; esto significa que para cualquier punto (x,y) de la
regin factible se tiene que
ax + by + cz kM = axM + byM + c.
Por tanto, has encontrado un mximo de la funcin objetivo, que es kM . Esto significa
que, si el problema es de maximizacin, has hallado su solucin en el vrtice C .
Y si el problema es de minimizacin? Todo lo que debes hacer es dar a k valores cada
vez ms pequeos, hasta que no te sea posible hacerlo sin que la curva de nivel se
salga de la regin factible:
Considera que estos valores son
k0 > k1 > k2 > > km
y observa que al final se ha hecho contacto con el vrtice F , que asumirs tiene por
coordenadas (xm ,ym). De manera similar al otro caso: ya no se puede disminuir el
valor de k, lo que significa que hemos encontrado el valor mnimo que puede tomar la
funcin objetivo, que es km y as el vrtice F es la solucin al problema de
minimizacin.
Casos 5 y 6.- La idea es exactamente la misma que en los dos casos ya explicados;
solo recuerda que si aumentas los valores de k en la ecuacin de la curva de nivel
Proyecto CLAVEMAT-EPN 38 ltima actualizacin: 14-02-2016
ax + by + c = k, sta se desplazar a la derecha y si aumentas los valores de k, la
curva de nivel se desplazar hacia la izquierda.
Para finalizar, te presentamos un ejemplo de un programa lineal con su solucin.
Ejemplo
Una compaa fabrica calculadoras cientficas y graficadoras. Por un lado, la
demanda mnima diaria es de 100 calculadoras cientficas y 80 graficadoras. Por
otro lado, la capacidad instalada en la fbrica no permite una produccin diaria
ms all de 200 y 170 calculadoras cientficas y graficadoras, respectivamente.
Adems, debido a compromisos ya adquiridos con las empresas distribuidoras de
estos productos, la compaa debe fabricar al menos 200 calculadoras en total
cada da. En el caso de solo se produjeran calculadoras cientficas, podran
transportarse un mximo de 250 de stas.
Finalmente, la caja de las calculadoras graficadoras tienen el doble de volumen de
la caja de las calculadoras cientficas.
Debido a una cada de los precios en el mercado, actualmente la produccin y
venta de calculadoras cientficas genera una prdida de 2.00 dlares, mientras
que la produccin y venta de calculadoras graficadoras genera una ganancia de
7.00 dlares.
Cul debera ser el programa de produccin que permita obtener la mayor
utilidad?
Solucin.
1. Tipificacin del problema. Se busca obtener el mayor beneficio econmico para la
compaa; luego, se trata de un problema de maximizacin.
2. Identificacin de las variables de decisin. Considera las siguientes variables:
Variable Significado
x Nmero de calculadoras cientficas
y Nmero calculadoras graficadoras
3. Formulacin de la funcin objetivo. Por cada x unidades producidas de
calculadoras cientficas hay una prdida de 2x dlares; pero esto es lo mismo que
decir que hay un beneficio de 2x. Por otra parte, por cada y unidades producidas de
calculadoras graficadoras, el beneficio es de 7y dlares. As, el beneficio total (la
funcin objetivo) es
2x +7y.
Proyecto CLAVEMAT-EPN 39 ltima actualizacin: 14-02-2016
4. Planteamiento de las restricciones. En primer lugar, obtn las restricciones de
demanda.
La compaa debe producir mnimo 100 calculadoras cientficas y 80 calculadoras
graficadoras; es decir, tienes que x 100 y y 80.
Ahora, determinar las restricciones debido a los lmites de produccin: no se pueden
producir ms de 200 calculadoras cientficas y no ms de 170 graficadoras; luego,
x 200 y y 170.
Los lmites impuestos por el contrato de venta, el cual establece que no se puede
producir menos de 200 calculadoras en total diariamente, genera la restriccin x +
y 200.
Finalmente, los lmites impuestos por la capacidad de transporte establecen que
podran transportarse mximo 250 calculadoras cientficas de ellas. Y como el
espacio ocupado por dos calculadoras graficadoras puede ser ocupado por una
calculadora cientfica, tienes la restriccin
x +y2 250,
o lo que es lo mismo:
2x + y 500.
En resumen, el modelo de programacin lineal que resulta es el siguiente:
maximizar 2x +7y
sujeta a
x 100,
y 80,
x 200,
y 170,
x + y 200,
2x + y 500.
Observa que no tiene sentido producir una cantidad negativa de calculadoras, pero al
exigir que x 100 y que y 80, queda establecido que no se admiten cantidades
negativas ambas variables.
Para resolver este programa lineal, grafica la regin factible. Obtendrs lo siguiente:
Proyecto CLAVEMAT-EPN 40 ltima actualizacin: 14-02-2016
Ahora identifica los vrtices. Para ello, cambia las desigualdades por igualdades en las
restricciones. Obtendrs lo siguiente:
x = 100,
y = 80,
x = 200,
y = 170,
x + y = 200,
2x + y = 500.
Forma los sistemas de ecuaciones que resultan de tomar dos a dos las ecuaciones
precedentes y los resuelves. Obtendrs lo siguiente:
Ecuacin 1 Ecuacin 2 Solucin
x = 100 y = 80 (x,y) = (100,80)
x = 100 x = 200 No hay solucin
x = 100 y = 170 (x,y) = (100,170)
x = 100 x + y = 200 (x,y) = (100,100)
x = 100 2x + y = 500 (x,y) = (100,300)
y = 80 x = 200 (x,y) = (200,80)
y = 80 y = 170 No hay solucin
y = 80 x + y = 200 (x,y) = (120,80)
y = 80 2x + y = 500 (x,y) = (210,80)
x = 200 y = 170 (x,y) = (200,170)
x = 200 x + y = 200 (x,y) = (200,0)
x = 200 2x + y = 500 (x,y) = (200,100)
y = 170 x + y = 200 (x,y) = (30,170)
y = 170 2x + y = 500 (x,y) = (165,170)
x + y = 200 2x + y = 500 (x,y) = (300,100)
Proyecto CLAVEMAT-EPN 41 ltima actualizacin: 14-02-2016
Con estos puntos obtenidos, ubica en la grfica de la regin factible los vrtices
obtenidos:
A = (100,100), B = (100,170), C = (165,170), D = (200,100), E = (200,80)y F = (120,80).
Podras tambin haber verificado qu punto o puntos satisfacen todas las restricciones
pero, en vista de la cantidad de puntos (son trece) y el total de 6 restricciones, este sera
un trabajo largo y tedioso. Por esto es recomendable ubicar los puntos obtenidos en la
grfica y as identificar los que pertenecen a la regin factible.
Finalmente, en la tabla siguiente encontrars los valores que toma la funcin objetivo
en cada uno de los vrtices:
Vrtice Coordenadas Valor de 2x +7y
A (100,100) 2 100+7 100 = 500
B (100,170) 2 100+7 170 = 990
C (165,170) 2 165+7 170 = 860
D (200,100) 2 200+7 100 = 300
E (200,80) 2 200+7 80 = 360
F (120,80) 2 120+7 80 = 320
Puedes observar que el valor mximo se produce en el vrtice B = (100,170). As, la
solucin del programa lineal es el punto (100,170).
Solucin al problema:
deben fabricarse 100 calculadoras cientficas y 170 calculadoras
graficadoras diariamente que la compaa obtenga una utilidad de 990
dlares cada da.
Proyecto CLAVEMAT-EPN 42 ltima actualizacin: 14-02-2016
Top Related