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

Vista previa del material en texto

las en forma de ecuaciones lineales. Por otra parte, 
las restricciones que imponen las condiciones de 
ambos problemas se pueden expresar en forma de 
inecuaciones lineales.
Resolución:
Si representamos por “x" el número de jugos de 
limón e “y" el número de jugos de fresa, se tiene 
que la función de costo es: Z = 30x + 20y
Por otra parte, las condiciones del problema impo­
nen las siguientes restricciones:
• De número: x + y < 80
• De preservación: 0,5x + 0,2 y < 9000
• Las variables "x" e “y" han de ser, lógicamente, 
no negativas; es decir: x >. O, y > O
El conjunto de restricciones es:
X + y < 80
0,5x + 0,2 y < 9000
X > O, y > O
<4 PROBLEMA GENERAL
Un problema de programación lineal con dos variables, 
tiene la siguiente formulación general:
Maximizar z = f(x; y} = ax 
sujeto a: a,x + b,y < c,
asX + b^y < C2
by + c
a„x + b„y < c„
Pudiendo cambiarse maximizar por minimizar, y el sen­
tido de las desigualdades.
En un problema de programación lineal intervienen:
La función f(x; y) = ax + by + c, llamada función 
objetivo y que es necesario optimizar En esa 
expresión ■'x" e “y" son las variables de decisión, 
mientras que a, b y c son constantes.
Las restricciones deben ser inecuaciones lineales. 
Su número depende del problema en cuestión. El 
carácter de desigualdad viene impuesto por las 
limitaciones, disponibles o necesidades, que son: 
inferiores a... (menores: < o < ); como mínimo de 
-,, (mayores: > o > ), Tanto si se trata de maximizar 
como de minimizar, las desigualdades pueden dar­
se en cualquiera de los dos sentidos,
• Ai conjunto de valores de "x” e “y’' que verifican to­
das y cada una de las restricciones se le denomina 
conjunto (o región) factible. Todo punto de ese con­
junto puede ser solución del problema; todo punto 
no perteneciente a ese conjunto no puede ser so­
lución. En el apartado siguiente veremos cómo se 
determina ia región factible.
La solución óptima del problema será un par de 
valores (x,,; ŷ ) del conjunto factible que haga que 
f(x; y) tome el valor máximo o minimo.
Determ inación de la reg ión factib le
La solución de un problema de programación lineal, en 
el supuesto de que exista, debe estar en la región de­
terminada por las distintas desigualdades. Esta recibe 
el nombre de región factible y puede estar o no acotada.
acotada no acotada
La región factible incluye o no los lados y los vértices, 
según que las desigualdades sean en sentido amplio 
(< o >) o en sentido estricto {< o >).
El procedimiento para determinar la región factible es 
el siguiente:
• Se resuelve cada inecuación por separado, es 
decir, se encuentra el semiplano de soluciones de 
cada una de las inecuaciones.
La región factible está formada por la intersección 
o región común de las soluciones de todas las 
inecuaciones.
Los sistemas de inecuaciones lineales pueden pre­
sentar varias opciones respecto a sus soluciones: 
puede no existir solución; en el caso de que exista, 
el conjunto solución puede ser acotado o no.
£/emp/o:
Dibuja la región factible asociada a las restricciones:
X + y > 4 
y < 4 
y > X
Las rectas asociadas son: 
r; X + y = 4; s: y = 4; t: y = X
A. Elegimos el punto 0(0; 0), que se encuentra 
en el semiplano situado por debajo de la rec­
ta. Introduciendo las coordenadas (0; 0) en la 
inecuación x + y > 4, vemos que no la satisface: 
O + O = O < 4. Por tanto, el conjunto de solu­
ciones de la inecuación es el semiplano situado 
por encima de la recta r: x + y = 4
www.full-ebook.com
(0; 0)
Procedemos como en el paso anterior. Las 
coordenadas (0: 0) satisfacen la inecuación 
y < 4 {O < 4). Por tanto, el conjunto de solucio­
nes de la inecuación es el semiplano que inclu­
ye al punto O.
La recta t asociada a la restricción pasa por el 
origen, lo cual significa que si probáramos con 
el punto 0(0; 0) no llegaríamos a ninguna con­
clusión, Elegimos el punto (1; 0) y vemos que 
no satisface la inecuación y > x (y = O < 1 = x). 
Por tanto, el conjunto solución de esta inecua­
ción es el semiplano determinado por la recta t 
que no incluye at punto (1; 0).
D. La región factible está tomada por los puntos 
que cumplen las tres restricciones, es decir, se 
encuentran en los tres semiplanos anteriores.
Valores óptim os
Analicemos el ejemplo siguiente:
Resuélvase el siguiente conjunto de desigualdades, 
gráficamente.
X + y < 5, X + 2y < 8, X e W , y e IN*
La gráfica será:
Los pares ordenados que satisfacen 
las desigualdades son; 
(1;1),(1;2),(1;3), (2:1), (2:2), (3;1)
A este ejemplo podremos ahora añadir otra cuestión. 
¿Cuál es el valor máximo de a) x + 3y; b) 2x + y; 
c) X + y; respecto at conjunto de pares ordenados ha­
llados?
Como tenemos solo seis posibilidades esta cuestión 
puede responderse por agotamiento, o sea, compro­
bando todas estas posibilidades.
Valores de x + 3y:
Para (1; 1)= 1 + 3 = 4
(1: 2)= ̂1 +6 = 7
(1; 3)= ̂1 + 9 = 10
Para (2; 1)=.2 + 3 = 5 
(2 : 2 ) = 2 + 6 = 8 
(3; 1) =.3 + 3 = 6
Una verificación rápida indica que el mejor valor {o el 
máximo en este caso) es 10, cuando x = 1 e y = 3. 
Verificamos que el valor máximo de 2x + y es 7, cuando 
X = 3 e y = 1. Examinemos: x + y
Los valores de x + y: 
Para (1; 1) 1 + 1 = 2
(1; 2) 1 + 2 = 3
(1:3) 1 + 3 = 4
Para (2; 1) 2 + 1 = 3 
(2; 2) 2 + 2 = 4 
(3; 1) 3 + 1 = 4
Aquí el valor máximo es evidentemente 4, pero hay tres 
pares ordenados que dan este valor: {1 ; 3), (2; 2) y (3; 1 ). 
La resolución por agotamiento es adecuada para po­
cas posibiiidades. o sea, para decidir entre unas pocas 
soluciones posibles después de una eliminación, pero 
también podemos aplicar un método gráfico que es 
bastante más directo. (Ver figura).
Sea: x + 3y = k (k; cte.)
1 1y = - -jX + -gk, que es la ecuación de una recta de 
pendiente 1.
Dicha recta es AB, pero AB corta al eje y en (0; 1).
1En consecuencia, —k = 1
O
k = 3.
Análogamente, puede trazarse la recta CD, lo que con­
duce a k = 6. Recordemos que estamos tratando de ha­
llar el máximo de x + 3y, esto es, obtener el valor mayor 
de k, lo que significa encontrar el mayor vaior de .
O
Dg m o ^ que una vez que tenemos una recta guia, tal 
como AB, podemos utilizar una regia y una escuadra 
para obtener una recta paralela que satisfaga las dos 
condiciones siguientes:
I. La ordenada en el origen debe ser tan grande 
como sea posible.
www.full-ebook.com
Al menos contenga un punto de los dados dentro 
del área restringida.
Es claro que la recta EF satisface ambas condiciones
k = 10, o más fá-y podemos decir que; -^k = 3-^>3 o
cilmente, leer las coordenadas del único punto que 
satisface las condiciones originales de la desigualdad, 
(1; 3), lo que nuevamente da x + 3y = 10.
Ensayar el mismo método con 2x + y, poniendo 
2x + y = k, o sea, y = -2x + k, y comprobar con su 
resultado anterior.
Cuando se hace lo mismo para x + y = k. se obtendrá 
que e! valor máximo es 4, y que la recta que da esto 
pasa por los tres puntos que hemos hallado antes.
¿Cuál es el valor mínimo de x + y si x e ¡N“*, y e IN‘ , 
x + y < 10; 2x -I- y > 10: X + 4y > 8?
Primero hacemos una gráfica de las desigualdades.
En este caso podemos considerar la recta x + y = 10 
como guía.
Sea x + y= k => y = - x + k
Deseamos que k sea mínimo, esto es, la recta pedida 
deberá cortar al eje "y" en un valor tan pequeño como 
sea posible.
Dichas rectas son AB y CD, pero la mejor es EF, que da 
k = 6. Pasa por (5; 1) que también da x + y = 6,
Tipos de soluciones
Los problemas de programación lineal (PPL) con dos 
variables se clasifican de acuerdo al tipo de solución 
que presentan; asi tenemos;
Factibles. Si existe el conjunto de soluciones o valores 
que satisfacen las restricciones. A su vez, pueden ser:
Con solución única 
Ejemplo:
En una urbanización se van a construir casas de dos 
tipos: A y B, La empresa constructora dispone para ello 
de un máximo de 1800 millones de um siendo el costo 
de cada tipo de casa de 30 y 20 millones, respectiva­
mente, El ayuntamiento exige que el número total de 
casas no sea superior a 80,
Sabiendo que elbeneficio obtenido por la venta de una 
casa de tipo A es 4 millones y de 3 millones por una de
tipo B, ¿cuántas casas deben construirse de cada tipo 
para obtener el máximo beneficio?
Variables: x = n.* de casas tipo A; y = n." de casas 
tipo B
Función objetivo; Maximizar Z = f(x; y) = 4x + 3y 
Conjunto de restricciones: El costo total
30x + 20y < 1800. El ayuntamiento impone 
X + y < 80. De no negatividad; x > 0; y > 0.
Tiene por región factible la región sombreada.
Si hallamos los valores de la función objetivo en cada 
uno de los vértices;
F(0) = f{0: 0) = 0; f(C) = f(60; 0) = 240; 
f(D) = f(20; 60) = 260; f(E) = f(0; 90) = 240
La solución es única y corresponde al vértice para el 
que la función objetivo toma el valor máximo. En este 
caso es el vértice D(20; 60). Por tanto, se deben cons­
truir 20 casas de tipo A y 60 de tipo B con un costo de 
260 millones de um.
Con solución múltiple;
Si existe más de una solución.
Por ejemplo: maximizar la función Z = f(x; y) = 4x + 2y 
sujeta a las restricciones: 2x + y < 4 ;x - y < 1 ; x > 0 ,y > 0
Los valores de la función objetivo en cada uno de los 
vértices son:
f(0) = f(0: 0) = 0, f(A) = f(1;0) = 4; 
f(B) = f(5/3; 2/3) = 8, f(C) = f(0; 4) = 8
La función objetivo alcanza el valor máximo en los vér­
tices B y C, por tanto, en todos los puntos del segmen­
to BC. Hay infinitas soluciones, solución múltiple, que 
corresponden a los puntos del segmento situado entre 
dos vértices de ta región factible.
En estos casos, como ya vimos en el capítulo anterior, 
la función objetivo es paralela a una de las restricciones.
Con solución no acotada; cuando no existe limite para 
la función obietivo.
www.full-ebook.com
Por ejemplo, maximizar la función Z = f(x; y) = x 
sujeta a las restricciones: y < 2x; y > x/2
Tiene por región factible la zona sombreada que apare­
ce en la figura, que es una región no acotada. La fun­
ción crece indefinidamente para valores crecientes de
“x” e "y".
En este caso no existe un valor extremo para la función 
objetivo, por lo que puede decirse que el problema ca­
rece de solución.
Para que suceda esta situación la región factible debe 
estar no acotada.
No factibles. Cuando no existe el conjunto de solucio­
nes que cumplen las restricciones, es decir, las restric­
ciones son inconsistentes.
Por ejemplo, maximizar la función Z = f(x; y) = 3x + 8y 
sujeta a las restricciones: x + y > 6 ; x - ^ y < 2 ; x > 0 ; 
y >0
No existe la región factible, ya que las zonas sombrea­
das que aparecen en la figura son únicamente solucio­
nes de alguna de las inecuaciones.
Por tanto, el conjunto de soluciones del sistema de des­
igualdades no determina ninguna región factible. Este 
tipo de problemas carece de solución.
Ejemplos:
1. Una empresa especializada en la fabricación de 
mobiliario para casas de muñecas, produce cierto 
tipo de mesas y sillas que venden a 2000 um y 
3000 um por unidad, respectivamente. Desea sa­
ber cuántas unidades de cada articulo debe fabri­
car diariamente un operario para maximizar los 
ingresos, teniéndose las siguientes restricciones:
- El número total de unidades de los dos tipos no 
podrá exceder de 4 por día y operario.
- Cada mesa requiere 2 horas para su fabrica­
ción; cada silla, 3 horas. La jornada laboral 
máxima es de 10 horas.
- Ei material utilizado para cada mesa cuesta 
400 um. El material utilizado para cada silla cues-
ta 200 um, Cada operario dispone de 1200 um 
diarias para material.
• Expresar la función objetivo y las restricciones 
del problema.
• Representar gráficamente la región factible y 
calcular los vértices de la misma.
• Resolver el problema.
Resolución:
• Las variables son; “x": n.° de mesas fabricadas 
por operario y día, "y": n.° de sillas fabricadas 
por operario y día. Por tanto, la función objetivo 
es:
F(x: y) = 2000x + 3000y
X + y <4 
2x + 3y < 10 
400x + 200y<1200 
x > O ; y > O
Las restricciones son:
Representación gráfica:
Las coordenadas de los vértices son; 
A(0; 0); B(3; 0); C(2; 2); D(0; 10/3)
• El mayor beneficio se produce a lo largo del 
segmento que va del vértice C al D, que es 
uno de ios lados de la región factible. El único 
punto de este lado con coordenadas enteras 
es el vértice C, que será por tanto la solución 
del problema. Un operario debe fabricar dia­
riamente 2 mesas y 2 sillas para optimizar el 
beneficio.
Dos pinturas A y B tienen ambas dos tipos de pig­
mentos p y q; A está compuesto de un 30% de p y 
un 40% de q, B está compuesto de un 50% de p y 
un 20% de q, siendo el resto incoloro. Se mezclan 
Ay B con las siguientes restricciones:
La cantidad de A es mayor que la de B. Su diferen­
cia no es menor que 10 gramos y no supera los 30 
gramos. B no puede superar los 30 gramos ni ser 
inferior a 10 gramos.
• ¿Qué mezcla contiene la mayor cantidad del 
pigmento p?
¿ Q u é m e z c la h a c e q m ín im o ?
www.full-ebook.com