Tema 28 - Programación lineal

Vista previa del material en texto

87UNI SEMESTRAL 2013 - III ÁLGEBRA TEMA 32
PROGRAMACIÓN LINEAL
ÁLGEBRA
I. RESOLUCIÓN GRÁFICA DE UN SISTE-
MA DE ECUACIONES LINEALES
Dado un sistema de inecuaciones lineales conformado
por dos o más inecuaciones, la solución gráfica de dicho
sistema es la región que se determina al intersectar
todos los semiplanos originados por las inecuaciones
que conforma el sistema.
Ejemplo:
Resolver:
2x y 4 ... (1)
3x y 6 ... (2)
 

 
Resolución:
Inicialmente graficamos los semiplanos que correspon-
dan a cada inecuación del sistema:
(1) 2x y 4 y 4 2x     ; semiplano ubicado por en-
cima de la recta y = 4 – 2x, incluyendo a ésta.
y
4
2
x
(2) 3x y 6 3x y 6      
 y 3x 6 
semiplano ubicado por debajo de la recta y = 3x – 6,
incluyendo a ésta.
y
–6
2
x
Finalmente el conjunto solución del sistema viene dado
por la intersección de los semiplanos hallados, veamos:
x
y
4
–6
2
(2)
(1)
CS
II. PROGRAMACIÓN LINEAL
A. Concepto
Es un modelo matemático mediante el cual se
resuelve un problema indeterminado, formulado por
ecuaciones lineales, optimizando la función objetivo,
también lineal.
La programación lineal consiste en optimizar (mini-
mizar o maximizar) una función lineal, que llamare-
mos función objetivo, de tal forma que las varia-
bles de dicha función estén sujetas a una serie de
restricciones que expresamos mediante un siste-
ma de inecuaciones lineales.
B. Función objetivo
Es una función lineal en dos variables que debemos
maximizar o minimizar. La función objetivo presenta
la siguiente forma:
F(x; y) ax by c  
donde a, b y c son constantes y x, y se llaman
variables de decisión.
C. Conjunto de restricciones
Es el sistema de inecuaciones lineales con dos
incógnitas que expresan un conjunto de limitaciones
que presenta el problema propuesto.
Aquí también se consideran a las variables de decisión
como valores no negativos, es decir x 0 y 0   .
D. Soluciones factibles
Son cada una de las soluciones que verifican al con-
junto de restricciones, cada solución factible se
representa por un punto del plano cartesiano.
E. Región factible
Se llama así al conjunto convexo formado por todos
los puntos que representan a las soluciones factibles,
en una región poligonal.
La región factible puede, o no, ser acotada, la pri-
mera incluye los puntos de su frontera y la otra no.
Observación: Sólo las regiones factibles aco-
tadas presentan siempre solución, en las otras
puede o no existir solución.
DESARROLLO DEL TEMA
88UNI SEMESTRAL 2013 - III ÁLGEBRA
PROGRAMACIÓN LINEAL
TEMA 32
Exigimos más!
F. Solución óptima
Es el punto cuyas coordenadas hacen de la función
objetivo un valor máximo o mínimo.
La solución óptima, en caso de existir, se alcanza
en un vértice de la región factible.
x
y
CB
A
D
S
S = región factible
A, B, C y D son posibles puntos de organización.
Problema 1
Determine el valor mínimo que toma la
función objetivo, P(x, y) = 10x + 20y
sujeta a las restricciones:
x y 2
x 2y 2
y x
 
  
 
Resolución:
Ubicación de incógnita
Valor mínimo de la función objetivo P
Análisis de los datos o gráficos
x y 2
P(x;y) 10x 20y x 2y 2
y x
 

   
 
Operación del problema
x = y
-1
1
2
A(1;1)
2
B(2;0)
x - 2y = 2
x + y = 2
Para A (1;1)
 P = 10(1) + 20(1) = 30 
Para B (2;0)
 P = 10(2) + 20(0) = 20 
Respuesta: 20
Problema 2
En relación a un programa lineal, indi-
que la secuencia correcta, después de
determinar si la proposición es verda-
dera (V) o falsa (F):
I. Las condiciones de no negatividad
significan que todas las variables de
decisión deben ser positivas.
II. El número de puntos extremos de
la región admisible es finito.
III. En un programa lineal pueden
variarse los coeficientes de la fun-
ción objetiva y aún mantenerse la
solución óptima.
UNI 2010 - I
Resolución:
Ubicación de incógnita
Valor de verdad
Operación del problema
I. FALSO
Tal condición establece que las
variables de recisión deberan ser
mayores o iguales que cero, es
decir: x 0 y 0   .
II. FALSO
En el caso de que el polígono sea
no acotado los puntos extremos
no se podrían determinar.
III. VERDADERO
De acuerdo con la Regla de Permu-
tación esta proposición es perfec-
tamente válida.
Respuesta: FFV
Problema 3
Un lago se llena de dos especies de
peces S1 y S2. La especie S1 proporcio-
na un peso promedio de 4 kg de car-
ne y la especie S2 un peso promedio
de 2 kg.
Dos tipos de comida F1 y F2 están dis-
ponibles en el lago. El requerimiento
promedio de la especie S1 es 1 unidad
de F1 y 3 unidades de F2, mientras que
el requerimiento de S2 en 2 unidades
de F1 y 1 unidad de F2 cada día. Si se
dispone diariamente de 500 unidades
de F1 y 900 unidades de F2, determine
el número total de peces en el lago
que maximice el peso total de carne
de pescado.
UNI 2011 - I
Resolución:
Ubicación de incógnita
* n° de peces de la especie S1: x;
peso promedio (S1) = 4 kg.
* n° de peces de la especie S2: y;
peso promedio (S2) = 2 kg.
Análisis de los datos o gráficos
Función objetivo: F(x; y) = 4x + 2y
S (x)1 S (y)2
F1
F2
1x
3x
2y
1y
Operación del problema
x 2y 500
3x y 900
x, y 0
 

  
 
Graficando:
y
900
(0;250) (260;120)
(300;0)
500
x0
I. F(0,250) = 500
II. F(260;120) = 1280 (máximo)
III. F(300,0) = 1200
El número de peces que maximiza
es: 260 + 120 = 380
Respuesta: 380
III. MÉTODO ANALÍTICO O MÉTODO DE
LOS VÉRTICES
A. Descripción
Se determina la región factible calculando las coor-
denadas de todos sus vértices, luego cada punto
que corresponde a un vértice se reemplaza en la
función objetivo esperando obtener con alguno de
ellos un valor máximo o mínimo según corresponda
a la optimización.
B. Teorema
Si la función objetivo asume el mismo valor óptimo
en dos vértices de la región factible, también asume
el mismo valor en los puntos del segmento limitado
por dichos vértices.
problemas resueltos