Algebra teorica y practica - Mikhaild P Flores-pagina (98)

Vista previa del material en texto

• rProgramación 
lineal
O
D
•+—
a
o
ü
G e o rg e B e rn a rd D an tz ig n a c ió el 
8 d e n o v ie m b re d e 1914 y m u ­
r ió e l 13 d e m a y o d e 2005. Fue 
u n p ro feso r, fís ico y m a te m á t ic o 
e s ta d o u n id e n s e r e c o n o c id o p o r 
d e s a r ro l la r e l « m é to d o sim plex» 
y es c o n s id e ra d o c o m o e l p a d re 
d e la p ro g r a m a c ió n lin ea l. R ec i­
b ió m u c h o s h o n o re s , ta le s c o m o 
la M ed a lla N a c io n a l d e C ien c ia s 
e n 1975 y e l p re m io d e te o r ía 
Jo h n v o n N e u m a n n e n 1974.
F u e m ie m b ro d e la A c a d e m ia 
N a c io n a l d e C ien c ias , la A c a d e ­
m ia N a c io n a l d e In g e n ie r ía y la 
A c a d e m ia A m e r ic a n a d e A rtes 
y C ien c ia s . O b tu v o su lic e n c ia ­
tu r a e n M a te m á tic a s y F ísica en 
la U n iv e rs id a d d e M a ry la n d en 
1936, su g ra d o d e m à s te r e n M a­
te m á tic a s e n la U n iv e rs id a d de 
M ich ig an y su d o c to r a d o e n la 
U n iv e rs id a d d e C a lifo rn ia , Ber-
b e le y e n 1946. A d e m á s , re c ib ió u n d o c to r a d o h o n o r a r io e n la U n iv e rs id a d d e M a ry la n d ( 1976).
In ic ia lm e n te ib a a a c e p ta r u n p u e s to c o m o p ro fe s o r e n B erbeley , p e ro fu e p e r s u a d id o p o r su 
e sp o s a y c o le g a s d e l P e n tá g o n o p a r a v o lv e r a las F u erzas A é rea s c o m o c o n s e je ro m a te m á t ic o 
d e la USAF F u e a h í. e n 1947. d o n d e p o r p r im e ra v e z p re s e n tó u n p ro b le m a d e p ro g ra m a c ió n 
lin e a l y p r o p u s o e l « m é to d o sim plex» p a ra re so lv e rlo . E n 1952 se c o n v ir t ió e n in v e s tig a d o r m a ­
te m á tic o e n la C o rp o ra c ió n RAND. e n c u y o s o rd e n a d o r e s c o m e n z ó a im p le m e n ta r la p ro g r a ­
m a c ió n lin ea l.
F u e n te . W ífeipedia
1314-EE.UU., 2005
www.full-ebook.com
<4 DEFINICIÓN y
La programación lineal es un algoritmo matemático. 4
consistente en una secuencia de procesos y métodos 2 x -3 y > 6
que permiten resolver problemas de optimización. En el 2
presente anexo, centraremos nuestro trabajo en aque­
. f 1 »
• (3:0)• t i ........................... j
llos problemas de programación lineal que presentan - 2 0 2 4 6 8 X
dos variables (bidimensionales). -2 ■ (0; -2)
^ DESIGUALDADES LINEALES ■4 •
Una desigualdad lineal entre dos variables “x" e “y" es 
cualquier relación de la forma Ax + By + C > O (o 0) o 
Ax + By + C > O (o < 0). La gráfica de una desigual­
dad lineal consta de todos aquellos puntos (x; y) que 
satisfacen la desigualdad. Consiste de una región del 
plano Ky, no solo de una linea o curva
La gráfica de la desigualdad Ax + By + C > O es un 
semiplano acotado por la linea recta cuya ecuación es 
Ax + By + C = 0.
La gráfica de y > mx + b es el semiplano debajo de la li­
nea y = mx + b y la gráfica de y < mx + b es el semipla­
no debajo de la linea y = mx + b. Si la gráfica incluye a la 
linea, la indicamos con una línea continua; de otra forma 
usamos una línea a trazos. Este tipo de líneas siempre 
corresponde a una desigualdad estricta (> o <) y una 
línea continua está asociada a una desigualdad débil 
(> o <).
Ejemplo:
Bosqueje la gráfica de la desigualdad lineal; 2x - 3y < 6 
Resolución:
En primer termino resolvemos en la desigualdad dada 
para "y” en términos de "x" {esto es, la expresamos en 
una de las formas y > mx + b o y < mx + b).
2x - 3y < 6
- 3y < -2x + 6
O
Luego: y > x - 2O
p
Enseguida graficamos la línea y = - 2. Para x = O,
tenemos que y = -2 . Así, (0; - 2 ) es un punto sobre la
p
línea. De nuevo, cuando y = O, tenemos que ^x - 2 = O,O
entonces x = 3, En consecuencia, (3; 0) es otro punto 
sobre la línea. Graficamos estos puntos y los unimos 
mediante una linea a trazos (porque tenemos una des­
igualdad estricta).
Puesto que la desigualdad dada, cuando la resolvemos 
para y, contiene el signo mayor que, la gráfica es el se- 
mipiano situado por arriba de la linea a trazos. (Véase 
la figura siguiente):
<4 SISTEMA DE INECUACIONES
Si consideramos {(x; y) : x + 2y = 5} fl {(x; y): 3x - y = 8}, 
vemos que es un conjunto con un elemento, es decir, 
{(3; 1)} (Véase la figura A).
Cambiemos ahora las ecuaciones a desigualdades, y 
consideremos la intersección.
{(x; y): x + 2y < 5} n {(x; y): 3x - y < 8} 
que está representada en la figura B.
Como hemos rayado los dos semiplanos que no se 
piden, toda la parte no sombreada de la gráfica es la 
intersección pedida. El punto (1; 1) está en esta área y 
podemos utilizarlo como comprobación: 
1 + 2 < 5 ; 3 - 1 < 8 , que son ambas verdaderas.
De hecho el conjunto es infinito, pero los pares ordena­
dos que forman sus elementos están restringidos por 
la condición x < 3. Cualquier punto con una abscisa
www.full-ebook.com
“x” de 3 o mayor estaré en la parte rayada. Podemos 
demostrar esto algebraicamente.
Ejemplo:
X + 2y < 5 
2 y < 5 \ 6 x - 2 y < 1 6
3x - y 7x <. 21 
X < 3
En este caso no hay restricción sobre el vator de la 
ordenada “y”, pero en otros ejemplos puede suceder 
lo contrario, o puede haber resthcciones tanto en “x" 
como en “y”. Si se trata de eliminar “x" para obtener una 
condición que rija "y”, se hallará que esto es imposible. 
Ejemplo:
Hallar las restricciones sobre “x" e “y" si: 
y < 2x ~ 4 y 2y > x + 4.
y < 2x - 4 
2y > X + 4
2x - y > 4 
- X + 2y -■ 4
4x - 2y > 
- X + 2y > 
3x >
X
X + 4 >
En consecuencia: 2y > x + 4 > 8 => y > 4.
Por tanto, x > 4 o y > 4 son las restricciones. Esto se 
ve también en la gráfica de la figura siguiente;
Puede también obtenerse la condición y > 4, eliminan­
do "x" de las dos desigualdades. Esto no podria efec­
tuarse en el ejemplo anterior, porque necesitaría hacer 
una resta de desigualdades.
Volvamos al prim er ejemplo: si se da una tercera des­
igualdad además de las otras dos del ejemplo 1, el área 
pedida puede reducirse a ta interior de un triángulo {ver 
figura).
Por ejemplo, 5x + 3y > 4 deja el triángulo ABC.
Hasta ahora hemos considerado intersecciones que 
nos dan conjuntos infinitos porque x c E: y e IR. Sin 
embargo, para muchos problemas prácticos x e IN'", 
y € IN’ . Por ejemplo, un problema en que interviene
la distribución de obreros y camiones puede tener
como solución ideal S^obreros y 6y camiones. Sería 
absurdo.
¿Qué es la program ación lineal?
En infinidad de aplicaciones de la realidad cotidiana o 
especializada se presentan situaciones en las que se 
exige maximizar o minimizar algunas funciones que es­
tán sujetas a determinadas limitaciones, denominadas 
restricciones.
Ejemplos:
1 Problema de maximización. En una granja se 
preparan dos ciases de alimento, P y Q mezclando 
dos productos A y B. Un saco de P contiene 8 kg de 
A y 2 kg de B, y un saco de Q contiene 10 kg de Ay 
5 kg de B. Cada saco de P se vende a 300 nuevos 
soles y cada saco de Q a 800 nuevos soles. Si en 
la granja hay almacenados 80 kg de A y 25 kg de 
B. ¿cuántos sacos de cada tipo de alimento deben 
prepararse para obtener los máximos Ingresos?
Resolución:
Si designamos por “x" al número de sacos da 
alimentos de clase P y por "y" el número de sa­
cos de clase Q que se han de vender, la función; 
z = 300x + 800y representará ia cantidad de um 
obtenidas por la venta de los sacos, y por tanto es 
la que debemos maximizar.
Podemos hacer un pequeño cuadro que nos ayude 
a obtener las resthcciones:
n.® kg de A kg de B
p X 8x 2x
Q y 10y 5y
< 80 <25
2.
Por otra parte, las variables ‘x" e "y”; lógicamente, 
han de ser no negativas, por tanto: x > O, y > 0; 
entonces el conjunto de restricciones es;
8x + lOy < 80 
2x + 5y < 25 
X > O, y > O
Problema de minimización. Una compañía para 
promocionar una marca de productos lácteos se 
basa en el reparto gratuito de jugos con sabor a 
limón o a fresa. Se decide repartiral menos 30 000 
Jugos. Cada jugo de limón necesita para su elabo­
ración 0,5 gramos de un producto de preservación 
y cada jugo de fresa necesita 0,2 gramos del mis­
mo producto. Se dispone de 9 kilogramos de este
p r o d u c t o p a r a p r e s e r v a c i ó n .
El costo de producción de un jugo de limón es de 
30 um y 20 um uno de fresa.
En ios dos ejemplos descritos está claro que tanto 
la cantidad que deseamos maximizar como la can­
tidad que deseamos minimizar podemos expresar­
www.full-ebook.com