Matemática Aplicada

Trabajo Práctico N°3

Prof. Miguel Martínez
Prof. Diego Lupiañez
Introducción a la Programación Lineal

La Programación Lineal es una técnica matemática utilizada para dar solución a problemas que se
plantean muy comúnmente en diversas disciplinas como Economía, Ingeniería, Sociología, Biología,
etc.
En esencia, se trata de optimizar (maximizar o minimizar) una función lineal de dos o más variables
(Función Objetivo) teniendo en cuenta que las mismas deben cumplir determinadas exigencias
derivadas de la escasez de recursos disponibles en la realidad.
El problema de asignar convenientemente recursos escasos es un problema conocido desde la
antigüedad, especialmente en el mundo de la economía, aunque una solución matemática al mismo es
relativamente reciente.
Fue en la década de los años 40 del siglo XX que a través del trabajo de equipos formados por
matemáticos, economistas y físicos, entre los cuales se destaca George B. Dantzing, se sentaron las
bases para la resolución de problemas de Programación Lineal y No Lineal.
Una buena forma de comprender la esencia del tema es plantear un problema concreto, el cual se
desarrollará para ir incorporando gradualmente todos los conocimientos matemáticos necesarios para
su resolución.

Problema: Una tapicería está dedicada al tapizado de dos tipos de sillones a los que denominaremos
tipo (A) y tipo (B). Cada unidad del sillón tipo (A) necesita 10 metros de tela de tapicería y 12 horas
de trabajo, mientras cada unidad de los del tipo (B) necesita 15 metros de tela y 16 horas de trabajo.
La tapicería dispone semanalmente de 300 metros de tela y 336 horas de trabajo. Los sillones del tipo
(A) dan a la empresa una utilidad de $ 1500, y los del tipo (B) una utilidad de $ 2100.
Suponiendo que todos los sillones tapizados se venden y que no existe escasez de otros elementos
como hilo, clavos, tachuelas, etc., se desea saber cuántos sillones de cada tipo deben tapizarse para que
la empresa obtenga máxima ganancia.

Resolución:
En todo problema de Programación Lineal encontraremos una tarea que debe realizarse con la
máxima “efectividad”, que en nuestro caso será lograr que la ganancia de la empresa expresada en
$/semana sea máxima.
Esa ganancia, que llamaremos G, deberemos expresarla como función lineal de dos variables.
A tales efectos llamaremos:
x al número de unidades de sillones tapizados por semana , tipo (A)
y al número de unidades de sillones tapizados por semana , tipo (B)
Como las utilidades de la venta son 1500 y 2100 pesos por unidad respectivamente, la función G será
tal que:
G(x,y) = 1500x + 2100y ( $ / sem.)
La escasez de recursos, en nuestro caso los metros de tela disponibles por semana de la tapicería
(300m) y las horas de trabajo posibles por semana (336 horas), imponen limitaciones a nuestras
variables, limitaciones a las que denominaremos “restricciones” y que se traducen matemáticamente
por inecuaciones lineales.
En efecto:
Si cada sillón del tipo (A) necesita 10m de tela y cada sillón del tipo (B) necesita 15m de tela, deberá
cumplirse
10x + 15y ≤ 300 (1)
Por otra parte si cada sillón del tipo (A) insume 12 horas de trabajo para su tapizado y cada sillón del
tipo (B) insume 16 horas deberá cumplirse:
12x + 16y ≤ 336 (2)

1
El propio significado físico de las variables impone además restricciones de no negatividad:
x ≥ 0 (3) y ≥ 0 (4)
En resumen el modelo matemático adoptado para resolver el ejercicio propuesto consiste en
maximizar la función G tal que G(x,y) = 1500x + 2100y debiendo las variables cumplir con las
restricciones:
10x + 15y ≤ 300 (1)
12x + 16y ≤ 336 (2)
x≥0 (3)
y≥0 (4)

En primer lugar debemos resolver gráficamente este sistema de inecuaciones lineales, para ello
tomemos primero la inecuación (1) 10x + 15y ≤ 300. Resolver la inecuación significa hallar el
conjunto de pares ordenados (x,y) que verifiquen la doble condición:
10x +15y = 300
10x + 15 y < 300
Los infinitos pares (x,y) que cumplen la primera condición son coordenadas de los infinitos puntos de
la recta de ecuación 10x + 15y = 300. Esta recta divide al plano en dos semiplanos y desde el punto
de vista gráfico uno de ellos es la solución de la inecuación 10x + 15y < 300. Queda por determinar
cuál de los dos es la solución. Para ello basta que tomemos un punto arbitrario del plano no
perteneciente a la recta que hemos considerado y verifiquemos si sus coordenadas verifican o no la
inecuación.
Si la verifican, el semiplano al cual pertenece el punto será el buscado, en caso de que no verifiquen el
semiplano buscado será el opuesto. Si nuestra recta no pasa por el origen de coordenadas el punto
más sencillo para efectuar el tanteo es justamente el (0,0).
Tendremos entonces: 10∙0+15∙0 = 0 < 300. Por lo tanto, el origen de coordenadas verifica la
desigualdad y el semiplano que lo contiene representará gráficamente la solución buscada.
La unión de la recta y el semiplano hallado es la solución de la restricción número (1) de nuestro
problema.
En forma similar resolvemos las restantes restricciones y obtenemos las siguientes regiones del plano:

Estamos en condiciones de hallar los puntos (x,y) que verifican todas las restricciones impuestas,
basta para ello hallar el conjunto intersección de los cuatro semiplanos que hemos representado en las

2
figuras anteriores. Ello nos conduce al polígono convexo OABC al que denominaremos “recinto de
puntos factibles” o simplemente “región factible”, queriendo significar con ello que cualquier punto
perteneciente a él tiene por coordenadas un par de números (x,y) que verifican el sistema de
inecuaciones formado por las restricciones, mientras que las coordenadas de cualquier punto del
plano no perteneciente al recinto no verifican el sistema.

Los vértices del polígono convexo son O(0;0), A(0;20), B(12;12) y C(28;0)

Si tomamos por ejemplo el punto P(5;6) que evidentemente pertenece al recinto podemos concluir
que la empresa puede decidir tapizar 5 sillones del tipo (A) y 6 sillones del tipo (B) a la semana pues
sus recursos se lo permiten. En ese caso la ganancia que obtendría sería: G(5;6) = 1500∙5 +2100∙6
= 20100 $/sem. Si bien se trata de una opción posible para la empresa, no resulta conveniente. Por
ejemplo los pares (0;20) y (28;0) dan una ganancia mayor, 42000 $/sem.
Por otro lado, si tomamos por ejemplo el punto (20,30) que claramente es exterior al polígono,
teóricamente la empresa podría obtener una ganancia de:
G(20;30) = 1500∙20 + 2100∙30 = 93000 $/sem.
Sin embargo la tapicería no estaría en condiciones de tapizar 20 sillones tipo (A) y 30 sillones tipo (B)
a la semana pues no contaría con la tela ni con las horas de trabajo necesarias para ello.
Desde el punto de vista matemático la dupla (20; 30) viola las restricciones (1) y (2).
Si bien seguimos sin saber aún cuál o cuáles pares solucionan nuestro problema hemos avanzado en
su resolución pues conocemos el conjunto de los pares posibles.
Para dar solución definitiva al problema haremos uso de las curvas de nivel de la función G. Llamamos
curvas de nivel de una función f de variables x , y a la familia de curvas del plano que cumplen que
f(x ,y) = k con k ∈ ℝ
En nuestro caso las curvas de nivel de la función G cumplirán:
1500x + 2100y = k
Se puede reconocer fácilmente que se trata de una familia de rectas de pendiente m = -1500/2100 y
ordenada en el origen b = k/2100. Las rectas serán por consiguiente paralelas entre sí. En la
siguiente figura se representan algunas rectas para distintos valores de k

Observamos que al aumentar k la recta se traslada en la dirección del vector u que es perpendicular a
la familia de rectas, alejándose del origen de coordenadas.

3
Podemos preguntarnos porqué utilizar el concepto de curvas de nivel en la resolución de nuestro
problema. ¿Qué propiedad tienen las curvas de nivel que vuelve pertinente su aplicación?
Consideremos por ejemplo la recta correspondiente a k = 30000. Cualquier punto de esa recta tiene
por coordenadas (x,y) que verifican la ecuación de la misma , es decir la ecuación : 1500x + 2100y =
30000. Como el primer miembro de esta ecuación es la expresión analítica de la función ganancia G, la
conclusión es que si la empresa tapizara un número x de sillones del tipo (A) e y sillones del tipo (B)
siendo (x,y) coordenadas de un punto cualquiera de esa recta , la ganancia que obtendría sería de
30000 $ / sem.
En este sentido podríamos decir que cada curva de nivel, en nuestro caso cada recta, es una “recta de
ganancia constante” y la ganancia está dada justamente por el valor de k.
Cada una de las rectas está indicando entonces una posible ganancia a obtener por la empresa, por lo
menos teóricamente. Porqué afirmamos “por lo menos teóricamente”. Pues porque no debemos
olvidarnos de la “región factible” que ya hemos determinado.
Podemos afirmar entonces, que la empresa no tendrá la opción de elegir cualquier recta de nivel para
trabajar sino sólo aquellas que contengan puntos de la región factible.
Deberemos buscar la recta de nivel correspondiente al mayor valor de k que contenga algún punto de
la región factible. Para lograrlo podemos representar gráficamente alguna de ellas, por ejemplo la
correspondiente a k=0 que obviamente pasará por el origen de coordenadas, y luego trasladarla en la
dirección y sentido correctos (en nuestro caso en la dirección de u) hasta encontrar el punto buscado.
Obtenemos así el vértice B del polígono de puntos factibles, vértice cuyas coordenadas son (12, 12).

Hemos alcanzado finalmente la solución a nuestro problema: la empresa deberá tapizar 12 sillones del
tipo (A) y 12 sillones del tipo (B) y obtendrá por ello una ganancia de 1500∙12 + 2100∙12 = 43200
$/sem. ∎

El hecho de que la función ganancia de nuestro problema se maximizara en un vértice del polígono de
puntos factibles no ha sido casual. Es posible demostrar la siguiente proposición: “El valor máximo y/o
mínimo de la función objetivo, en un problema de programación lineal de dos variables, ocurre
siempre en uno de los vértices o lado del recinto poligonal convexo de puntos factibles, sea este
recinto acotado o no acotado”.
Cuando la pendiente de las curvas de nivel de la función coincida con la pendiente de uno de los lados
del recinto de puntos factibles, la función se maximizará o minimizará en todos los puntos de ese lado.

De acuerdo a lo dicho anteriormente, basta con hallar los vértices de la región factible y evaluar cada
vértice en la función a optimizar para hallar el valor óptimo buscado.

Problemas propuestos:
Para resolver cada uno de los siguientes problemas se sugiere a) Graficar la región factible b) Hallar
las coordenadas de todos los vértices del polígono de puntos factibles c) Determinar, evaluando en la
función objetivo cada punto obtenido en el inciso anterior, el punto o los puntos para los cuales se
optimiza la función.

4
① Un fabricante produce bicicletas y motos, las cuales se procesan a través de dos centrales de
producción mecánica. La primera dispone de un máximo de 120 horas y la segunda de 180. La
producción de una bicicleta requiere 6 horas de la primera central y 3 horas de la segunda. La
producción de una moto requiere 4 horas de la primera central y 10 horas de la segunda. Si la
ganancia por cada bicicleta es de $450 y la de cada moto es de $550, determinar el número de
bicicletas y motos que deben fabricarse mara maximizar la ganancia y cuál es esa ganancia.

② Un nutricionista le prescribe a un paciente una ingesta, durante cierto período de tiempo, de al

menos: 40mg de vitamina B1 y 30mg de B2. Existen dos compuestos diferentes, el A y el B. Cada
píldora del compuesto A contiene 1mg de B1 y 1mg de B2 y tiene un valor de $0,40 (40 centavos).
Cada píldora del compuesto B contiene 2mg de B1 y 1mg de B2 y tiene un valor de $0,50. Hallar la
combinación de píldoras más conveniente que debe adquirir el paciente para satisfacer sus
requerimientos vitamínicos al menor costo y determinar ese costo.

③ Un taller de armado de computadoras produce dos modelos de las mismas que llamaremos Mod. I
y [Link]. El Mod. I requiere 1 hora de mano de obra especializada y 2 horas de mano de obra no
especializada. El Mod II requiere 1 hora de mano de obra especializada y 1 hora de no especializada.
Se disponen de 120 horas de mano de obra especializada y 200 horas de mano de obra no
especializada por semana. El Mod. I produce una utilidad de $60 por unidad y el Mod. II de $30 por
unidad.
a) ¿Cuántas posibilidades de obtener máximas utilidades existen? ¿Cuál es esa máxima utilidad?
b) ¿Cuál es el menor número de unidades del modelo I y el correspondiente número de unidades del
modelo II que deben armarse por semana para obtener máximas utilidades?
c) ¿Cuál es el mayor número de unidades del modelo I y el correspondiente número de unidades del
modelo II que deben armarse por semana para obtener máximas utilidades?

④ Una fábrica elabora mesas de dos calidades distintas I y II con madera de cedro, caoba y vidrio de
los cuales se dispone de 54m 2, 64m2 y 30m2 respectivamente. Cada mesa de calidad I produce una
ganancia de $350 y $250 la de calidad II. Para la elaboración de las mesas I se requieren 0,6m 2 de
cedro, 0,4m2 de caoba y 0,3m 2 de vidrio. Para la elaboración de las mesas II se requieren 0,3m 2 de
cedro, 0,8m2 de caoba y 0,3m2 de vidrio. Se pide el beneficio máximo y la cantidad de mesas que
produce ese beneficio.

⑤ Una fábrica textil confecciona polleras y pantalones. Para cada pollera se usan 70cm de tela y 3
horas de mano de obra, para cada pantalón se usan 1,5mts de tela y 1 hora de mano de obra. Además,
existe un compromiso comercial con una tienda a la que deben proveer de 50 prendas en total. Se
dispone de 210mts de tela y al menos 100 horas de mano de obra. Si la ganancia por cada pantalón es
de $40 y por cada pollera de $60 ¿Cuántas polleras y pantalones conviene fabricar para tener mayor
ganancia?

⑥ Minimizar la función f(x,y) = 12x + 8y sujeta a las siguientes restricciones:

1) 3x + 2y ≥ 1 2) 4x + y ≥1 3) x ≥ 0 4) y ≥ 0

Respuestas:

① 10 bicicletas y 15 motos. Ganancia=$12750

② 20 píldoras del compuesto A y 10 del B. Costo=$13
③ a) 21 posibilidades, ganancia máxima $6000 b) 80 Mod I, 40 Mod II c) 100 Mod I, 0 Mod II
④ 80 mesas calidad I y 20 mesas calidad II. Beneficio=$33000
⑤ 50 polleras, 0 pantalones. Ganancia=$300
⑥ Mínimo=4, para 1/5≤x≤1/3 , 0≤y≤1/5