Intro Prog Lineal_version2016

Vista previa del material en texto

1
 
ÁLGEBRA Y GEOMETRÍA ANALÍTICA 
 
Capítulo 0 : INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL 
 Resolución geométrica de p roblemas con dos incógnitas 
 
En muchos problemas prácticos se nos pide cumplir una tarea de manera óptima. Por ejemplo, 
maximizar ganancias, minimizar costos, minimizar esfuerzos, hacer una administración 
eficiente de recursos humanos, planear una dieta, etc. 
Los modelos matemáticos de muchos de estos problemas, relacionados con la logística de la 
toma de decisiones, se llaman “programas matemáticos” (aquí “programa” se utiliza como “plan 
de acción”). De estos programas, los más simples son los programas lineales en los cuales es 
lineal la función que se desea maximizar o minimizar y también son lineales las inecuaciones 
que definen la región en la cual debe encontrarse la solución del problema, si es que existe. 
 
Comenzaremos considerando el siguiente problema de contaminación: 
 
 
Un fabricante elabora cierto producto químico en cualquiera de sus dos plantas X e Y. La 
planta X puede fabricar un máximo de 30 toneladas por semana y la planta Y un máximo de 40 
toneladas por semana. El fabricante quiere producir por lo menos 50 toneladas por semana. 
Se encontró que, semanalmente, la cantidad de partículas suspendidas en la atmósfera de una 
población vecina es de 10 kg por cada tonelada del producto fabricado en la planta X y es de 
15 kg por cada tonelada del producto fabricado en Y. 
¿Cuántas toneladas deben fabricarse semanalmente en cada planta para minimizar la cantidad 
total de partículas suspendidas en la atmósfera? 
 
 
(a) Formulación matemática del problema (modelado) 
 
Si designamos con x e y a la cantidad de toneladas semanales del producto fabricadas en 
cada una de las plantas X e Y respectivamente, la cantidad total producida semanalmente es 
yx + , y como se quiere producir al menos 50 toneladas por semana, tenemos la desigualdad 
50≥+ yx . 
La planta X puede fabricar como máximo 30 toneladas semanales, entonces 30≤x . 
Análogamente 40≤y . Por supuesto, x e y no pueden ser negativas, es decir 0≥x e 
.0≥y 
Finalmente, la cantidad total de partículas suspendidas semanalmente en la atmósfera (en kg) 
es yxk 1510 += , cantidad que se desea minimizar (llamada función objetivo ). 
“Juntando” toda la información anterior resulta que el problema a resolver puede formularse de 
la siguiente manera: 
 
 
 Encontrar los valores de x e y tales que 
 
- minimicen yxk 1510 += y 
- satisfagan las siguientes restricciones 50≥+ yx 
 30≤x 
 40≤y 
 0≥x 
 .0≥y 
 
 
 
 
 
2
(b) Interpretación geométrica y solución 
 
1º) Graficamos la región definida por las restricciones, llamada región factible. 
 (en este problema es el triángulo ABC sombreado, que resulta de la intersección de las 
 regiones definidas por las 5 desigualdades del problema) 
 
 x = 30 
 
 
 
 
 B C y = 40 
 
 
 A 
 
 
 
 
 
 x + y = 50 
 
 
 xy
15
10−= (recta de nivel para k = 0 ) 
 
 2º) Haciendo k = 0 en la función a minimizar obtenemos la recta por el origen, 
01510 =+ yx , llamada recta de nivel para k=0. Representamos gráficamente esta 
recta (línea punteada que pasa por el origen de coordenadas) y notamos que, como 
estamos buscando un punto de la región factible que pertenezca a alguna de las rectas 
de nivel kyx =+1510 para el menor valor de k posible, sólo tenemos que “trasladar 
hacia arriba” (manteniendo la dirección) a la recta punteada por el origen hasta 
encontrar el primer punto de la región factible por donde pase. Resumiendo: 
 
el primer punto de la región factible que una de la s rectas de nivel encuentre 
producirá el valor mínimo de la función objetivo 
 
En este problema el mínimo se alcanza en el vértice A, cuando 30=x e 20=y , lo cual 
significa que para minimizar la contaminación el fabricante debe producir, semanalmente, 
30 toneladas de su producto en la planta X y 20 toneladas en la planta Y. 
De esta manera la cantidad mínima de partículas en la atmósfera será de 600 kg cada semana. 
En efecto, reemplazando 30=x e 20=y en la ecuación de la función objetivo obtenemos el 
valor de k mínimo, 600)20(15)30(10 =+ . 
 
En general , frente a un problema de programación lineal con dos incógnitas, región factible en 
el 1er cuadrante y función objetivo con ambos coeficientes positivos, podemos proceder así: 
1. representar gráficamente la región de restricciones (región factible ) 
2. representar gráficamente la recta de nivel por el origen, cuya ecuación corresponde a la 
función (objetivo) a minimizar o maximizar cuando ésta se anula 
3. trasladar hacia arriba esa recta (recta de nivel por el origen) hasta encontrar, cuando sea 
posible, la o las soluciones del problema 
 
 
 
3
Otras situaciones en problemas de programación line al con dos incógnitas ( 0, ≥yx ) 
 
a) La región factible es ACOTADA (es decir, puede ser encerrada en un círculo) y las 
rectas de nivel no son paralelas a ningún lado del polígono: UNICA SOLUCION 
 
 
 
 
 C 
 
 C produce el máximo (es el último punto de 
 B la región, que pertenece a una recta de nivel) 
 
 
 A produce el mínimo 
 
 
 
 
 A D 
 
 
 Recta de nivel por el origen 
 
 
 
b) La región factible es acotada y las rectas de nivel son paralelas a un lado del polígono: 
 
 
 INFINITAS SOLUCIONES 
 C Infinitos puntos de máximo: 
 todos los puntos del lado CD, 
 el beneficio es el mismo en todo pto de CD. 
 
 B 
 
 
 
 
 
 
 A D 
 
 Recta de nivel por el origen A paralela al lado CD 
 
 
CONCLUSIÓN: Cuando la región factible es ACOTADA el problema de maximizar o 
minimizar una función lineal puede producir ÚNICA SOLUCIÓN (algún vértice del 
polígono) o INFINITAS SOLUCIONES (todos los puntos de una arista del polígono) 
 
 
 
 
 
 
 
4
c) La región factible NO es ACOTADA 
 
 
 
 NO hay punto de máximo 
 B 
 
 
 A 
 A es punto de mínimo 
 
 
 
 
 
 
 Recta de nivel no paralela a los lados de la región 
 
 
CONCLUSIÓN: Cuandola región factible NO es ACOTADA , si existen extremos pueden 
alcanzarse en un vértice, segmento o semirrecta (por qué? Representar gráficamente) 
 
d) La región factible es VACÍA (es decir, las regiones definidas por las desigualdades no 
tienen subregión común): NO HAY MAXIMO NI MINIMO 
 
 
 
 
 
En problemas de programación lineal con dos incógnitas que tengan solución única, ésta es el 
punto de intersección entre dos rectas, las que contienen a dos segmentos consecutivos de la 
región factible. 
¿Y con tres incógnitas? 
• Veremos que una ecuación lineal con tres incógnitas representa un plano en el 
espacio. 
• Si la región de restricciones es acotada será un poliedro 
• Si la solución fuese única resultaría de interceptar tres planos que contengan caras 
concurrentes y la resolución geométrica se complica. Existen otros métodos para 
resolver programas lineales que no se estudian en esta asignatura, por ejemplo el 
método simplex. 
 
 Redactado por: Mg Adriana Frausin 
Bibliografía: 
• Strang G. “Algebra Lineal y sus aplicaciones” Capítulo 8. 4ª edición 2007. Ed.Thomson. 
• Noble B. y Daniel J. “Algebra lineal aplicada” Capítulo 2. 3ªedición 1989. Prentice Hall. 
 
5
 
 
PROBLEMAS RESUELTOS: más ejemplos 
Como ejemplo de un problema de programación lineal en que la función objetivo debe 
maximizarse , considere el siguiente problema de producción con dos variables: 
El granjero Lopez tiene 480 hectáreas en la que se puede sembrar 
ya sea trigo o maíz. El calcula que tiene 800 horas de trabajo 
disponible durante la estación crucial del verano. 
Dados márgenes de utilidad y los requerimientos lab orales 
mostrado s a la derecha: ¿Cuántas hectáreas de cada uno debe 
plantar para maximizar su utilidad? ¿Cuál es ésta utilidad 
máxima? 
Maíz: 
Utilidad: $40 por ha. 
Trabajo: 2hs por ha. 
 
Trigo: 
Utilidad: $30 por ha. 
Trabajo: 1hs por ha. 
 
Solución: Tabulando la información dada tenemos la siguiente tabla 
 Maíz Trigo Elementos disponibles 
Horas 2 1 800 
Hectáreas 1 1 480 
Utilidad por unidad $40 $30 
Si llamamos x a las hectáreas de maíz e y a las hectáreas de trigo, entonces la ganancia total 
P, en dólares, que es la función objetivo por maximizar,está dada por: 
P=40x+30y 
La cantidad total de tiempo por hectárea para sembrar maíz y trigo está dada por: 2x+y 
horas que no debe exceder las 800 horas disponibles para el trabajo. Así se tiene la 
desigualdad: 
2x+y < 800 
En forma análoga, la cantidad de hectáreas disponibles está dada por x+y , y ésta no 
puede exceder las hectáreas disponibles para el trabajo, lo que conduce a la desigualdad. 
x+y < 480 
Por último, naturalmente, x e y no pueden ser negativas, de modo que: 
 
x>0 
y>0 
 
En resumen, el problema en cuestión consiste en maximizar la función objetivo: 
 
P=40x+30y 
sujeta a las restricciones: 
2x+y<800 
x+y<480 
x>0 
y>0 
 
 
6
El sistema de desigualdades define la región factible S que aparece en la figura 
siguiente. Cada punto de S, o solución factible ,es un candidato para resolver este problema. 
 
La recta de nivel por el origen de coordenadas permite intuir que, el último punto de S que 
dicha recta encuentra al ser trasladada hacia arriba es (320, 160). VERIFICAR 
Rta: para maximizar las ganancias el granjero deberá sembrar 320 hectáreas de maíz y 
160 hectáreas de trigo, siendo la utilidad máxima de $ 17.600. 
Observación 1 : No es casualidad que la solución óptima de los problemas desarrollados 
aparezcan como vértices del conjunto factible. De hecho, estos resultados son consecuencia 
del siguiente teorema básico de la programación lineal, que se enuncia sin demostración. 
Teorema 
Básico 
Si un problema de programación lineal tiene una solución, entonces ésta debe 
aparecer en un vértice, o esquina, del conjunto factible S asociado con el 
problema. Además, si la función objetivo P se optimiza en dos vértices adyacente 
de S, entonces se optimiza en todos los puntos del segmento de recta que une 
estos vértices, en cuyo caso existe una infinidad de soluciones al problema 
EJEMPLO CON INFINITAS SOLUCIONES y región factible acotada : 
Si para la región factible S del ejemplo anterior, se considera maximizar la función objetivo 
P=40x+40y tendríamos infinitas soluciones, en efecto: 
 
Maximizar: P=40x+40y 
 
(0,0) 0 
(0,480) 19.200 
(320,160) 19.200 
(400,0) 16.000 
 
Supóngase que la utilidad por hectáreas es de $40 para 
ambos, maíz y trigo. La tabla para este caso muestra la 
misma utilidad total en los vértices (0,480) y (320,160), ya 
que la pendiente de la recta que pasa por estos dos 
vértices es (-1), coincide con las pendientes de las rectas 
de nivel correspondientes a la función objetivo P. Esto 
significa que la línea de utilidad en movimiento abandona la 
región sombreada por el lado determinado por esos vértices 
(adyacentes), así todo punto en ese lado da una utilidad 
máxima. 
 
Observación 2 : Aunque el teorema básico arroja un poco de luz acerca de la naturaleza de la 
solución de un problema de programación lineal, no indica cuándo tiene solución. El siguiente 
teorema establece ciertas condiciones que garantizan la existencia de solución de un problema 
de programación lineal y resume las distintas situaciones analizadas. 
 
7
Teorema de 
Existencia de 
una solución 
 
Suponga un problema de programación lineal con un conjunto factible S y una 
función objetivo P = ax + by. 
1. Si S está acotado, entonces P tiene un valor máximo y un valor mínimo en S. 
2. Si S no está acotado y tanto a como b son no negativos, entonces P tiene un 
valor mínimo en S, si las restricciones que definen a S incluyen las 
desigualdades x>=0 e y>=0. 
3. Si S es el conjunto vacío, entonces el problema de programación lineal no 
tiene solución; es decir, P no tiene un valor máximo ni uno mínimo 
UN EJEMPLO CON REGIÓN FACTIBLE NO ACOTADA y soluci ón única: 
Aplicaremos los conceptos antes emitidos al siguiente problema de nutrición, basado en 
los requerimientos, en el cual hay que minimizar la función objetivo. 
Un nutricionista asesora a un individuo que sufre u na deficiencia de hierro y vitamina B, 
y le indica que debe ingerir al menos 2400 mg de hi erro, 2100 mg de vitamina B- 1 
(tiamina) y 1500 mg de vitamina B-2 (riboflavina) d urante cierto período de tiempo. 
Existen dos píldoras de vitaminas disponibles, la m arca A y la marca B. Cada píldora de 
la marca A contiene 40 mg de hierro, 10 mg de vitam ina B-1, 5 mg de vitamina B- 2 y 
cuesta 6 centavos. Cada píldora de la marca B conti ene 10 mg de hierro, 15 mg de 
vitamina B-1 y de vitamina B-2, y cuesta 8 centavos . 
¿Cuáles combinaciones de píldoras debe comprar el paciente para cubrir sus 
requerimientos de hierro y vitamina al menor costo? 
 Marca A Marca B Requerimientos mínimos 
Hierro 40 mg 10 mg 2400 mg 
Vitamina B-1 10 mg 15 mg 2100 mg 
Vitamina B-2 5 mg 15 mg 1500 mg 
Costo por píldora (US$) 0,06 0,08 
Solución: Sea x el número de píldoras de la marca A e y el número de píldoras de la marca B 
por comprar. El costo C, medido en centavos, función objetivo por minimizar, está dado por 
C = 6x+ 8y 
La cantidad de hierro contenida en x píldoras de la marca A e y número de píldoras de la 
marca B está dada por 40x+10y mg, y esto debe ser mayor o igual a 2400 mg. Esto se traduce 
en la desigualdad. 
40x+10y>2400 
Consideraciones similares con los requisitos mínimos de vitaminas B-1 y B-2 conducen a 
las desigualdades siguientes: 
10x+15y>2100 
5x+15y>1500 
Así, el problema en este caso consiste en: 
Minimizar C=6x+8y 
Sujeta a: 40x+10y >2400 
10x+15y>2100 
5x+15y>1500 
x>0 
y>0 
 
8
 
El conjunto factible S definido por el sistema de restricciones aparece en la siguiente 
figura. Los vértices del conjunto factible S son A(0,240); B(30,120); C(120; 60) y D(300,0). 
 
Los valores de la función objetivo C en estos vértices son: 
Vértice C=6x + 8y 
A (0,240) 1920 
B(30,120) 1140 
C(120,60) 1200D(300,0) 1800 
La tabla muestra que el mínimo de la función objetivo C=6x+8y ocurre en el vértice 
B(30,120) y tiene un valor de 1140. En efecto, B es el primer vértice que la recta de nivel 
encuentra (VERIFICAR). 
RTA: Así el paciente debe adquirir 30 píldoras de la marca A y 120 de la marca B, con un 
costo mínimo de $11,40. 
 
Problemas propuestos disponibles en Campus Virtual bajo etiqueta: 
 
Guías de Ejercicios para Clases Prácticas: 0- Progr amación Lineal 
 
 
Recopilación 2016- Cátedra “Álgebra y Geometría Analítica” UTN- Facultad Regional Santa Fe