Download - 7. PL_01
-
Programacin Lineal
-1-
-
Programacin Lineal
INTRODUCCION
Programacin Lineal
INTRODUCCION.-Es considerado uno de los avances cientficos msimportante de mediados del siglo XX S impacto haimportante de mediados del siglo XX. Su impacto hasido extraordinario.
L i li l (PL) h i tLa programacin lineal (PL) es una herramienta pararesolver problemas de optimizacin utilizando modelosmatemticos donde las restricciones y funcin objetivomatemticos donde las restricciones y funcin objetivoson funciones lineales.
Los problemas que se ajustan al modelo de la PL seLos problemas que se ajustan al modelo de la PL seconocen como problemas de programacin lineal(PPL). La PL es una tcnica poderosa para resolver( ) p pPPL.
-2-
-
Programacin Lineal
DEFINICION
Programacin Lineal
DEFINICION.-La PL es una tcnica que consiste en optimizar(ma imi ar o minimi ar) na f ncin lineal llamada(maximizar o minimizar) una funcin lineal llamadafuncin objetivo.
E ti d ti i l b d dEntindase por optimizar como la bsqueda de unasolucin (un valor mximo o mnimo) dentro de unaregin factible (conjunto de soluciones) delimitada porregin factible (conjunto de soluciones) delimitada porun conjunto de restricciones tambin lineales.
-3-
-
Programacin Lineal
REPRESENTACIN MATEMTICA DE UN P P L
Programacin Lineal
REPRESENTACIN MATEMTICA DE UN P.P.L..-1) Representacin algebraica desarrollada.-
nn2211 xcxcxcZOptimizar +++= Lsujeto asujeto a
1nn1212111 b),,(xaxaxa =+++ L
M2nn2222121 b),,(xaxaxa =+++ L
mnmn22m11m b),,(xaxaxa =+++ LM
i0xi -4-
-
Programacin Lineal
REPRESENTACIN MATEMTICA DE UN P P L
Programacin Lineal
XcZOptimizar =sujeto asujeto a
b),,(XA =0X
REPRESENTACIN MATEMTICA DE UN P.P.L..-2) Representacin matricial compacta.-
-5-
-
Programacin Lineal
FORMAS DE UN P P L
Programacin Lineal
FORMAS DE UN P.P.L..-1) Forma cannica de maximizacin.-
XcZMax =sujeto asujeto a
bXA 0X
-6-
-
Programacin Lineal
FORMAS DE UN P P L
Programacin Lineal
XcZMin =sujeto asujeto a
bXA 0X
FORMAS DE UN P.P.L..-2) Forma cannica de minimizacin.-
-7-
-
Programacin Lineal
REGLAS DE EQUIVALENCIA
Programacin Lineal
REGLAS DE EQUIVALENCIA.-Regla 1.-
a) Max Z = cX es equivalente a Min -Z = -cX.
ejemplo xx3x2ZMax +=ejemplo 321 xx3x2ZMax +=321 xx3x2ZMin +=es equivalente a
b) Min Z = cX es equivalente a Max -Z = -cX.
iejemploes equivalente a
321 x6x5x4ZMin +=321 x6x5x4ZMax +=q 321
-8-
-
Programacin Lineal
REGLAS DE EQUIVALENCIA
Programacin Lineal
REGLAS DE EQUIVALENCIA.-Regla 2.-
a) La restriccin j-sima de la forma cjixi bj esequivalente a la restriccin -cjixi -bj.ejemploes equivalente a
55x3x6x4 321 +55x3x6x4 +es equivalente a
b) La restriccin j-sima de la forma cjixi bj esequivalente a la restriccin -cjixi -bj
55x3x6x4 321 +equivalente a la restriccin cjixi -bj.ejemplo 31x7x2x3 321 +es equivalente a 3x1 + 2x2 7x3 31
-9-
-
Programacin Lineal
REGLAS DE EQUIVALENCIA
Programacin Lineal
REGLAS DE EQUIVALENCIA.-Regla 3.-
La restriccin j-sima de la forma cjixi = bj puededescomponerse como la interseccin de dosrestricciones cjixi bj y cjixi bj.ejemplo
65119j p
es equivalente a
6x5x11x9 321 =+q
6x5x11x9 321 +6x5x11x9 + 6x5x11x9 321 +
-10-
-
Programacin Lineal
REGLAS DE EQUIVALENCIA
Programacin Lineal
REGLAS DE EQUIVALENCIA.-Regla 4.-
a) Si se tiene m restricciones de la forma AX b,pueden convertirse en igualdad mediante la adicinde un vector Y, llamado vector de variables deholgura. El vector Y tiene m componentes nonegativasnegativas.ejemplo 15x5x6 21 +
19x7x3 se convierte a
19x7x3 21 15xx5x6 321 =++ 32119xx7x3 421 =+
-11-
-
Programacin Lineal
REGLAS DE EQUIVALENCIA
Programacin Lineal
REGLAS DE EQUIVALENCIA.-b) Si se tiene m restricciones de la forma AX b,
p eden con ertirse en ig aldad mediante la resta depueden convertirse en igualdad mediante la resta deun vector Y, llamado vector de variables de exceso.El vector Y tiene m componentes no negativasEl vector Y tiene m componentes no negativas.
ejemplo35x2x7 21 +
se convierte a
21
21x9x8 21 +se convierte a
35xx2x7 321 =+21xx9x8 421 =+ 421
-12-
-
Programacin Lineal
REGLAS DE EQUIVALENCIA
Programacin Lineal
REGLAS DE EQUIVALENCIA.-Regla 5.-
Una variable no restringida xi, (xi -, +), puedeescribirse como la diferencia de dos variables nonegativas. Sea xi una variable no restringida, luego
kji xxx =donde xj 0 y xk 0. Se cumple que:
Si xi > 0 entonces xj > xki j kSi xi = 0 entonces xj = xkSi 0 tSi xi < 0 entonces xj < xk
-13-
-
Programacin LinealProgramacin Lineal
FORMULACION DE PROBLEMAS DEPROBLEMAS DE PROGRAMACION
LINEALLINEAL
-14-
-
Programacin Lineal
PROBLEMA 01
Programacin Lineal
PROBLEMA 01.-Se tiene que abastecer urgentemente una zonadeclarada en emergencia se disponen de dos tipos dedeclarada en emergencia, se disponen de dos tipos deaviones, el A y el B.
C t ti f t l d b tiblCaractersticas referente al consumo de combustible,aceite, carga til y tiempo que demora de ida y vueltaestn en la tabla adjunta igualmente estn en ella laestn en la tabla adjunta, igualmente estn en ella ladisponibilidad de aceite y combustible de la base,plantear el problema con miras a que se transporte lamxima carga posible con la gasolina y el aceitedisponible.
-15-
-
Programacin LinealProgramacin Lineal
A B DisponibilidadTIPO DE AVION
A B DisponibilidadGasolina/hora 8 12 800 galonesAceite/hora 0.25 0.2 40 galonesg
Horas de viaje 5 4Carga til (kg) 400 480
-16-
-
Programacin Lineal
SOLUCION
Programacin Lineal
SOLUCION.-Variables de decisinA : nmero de viajes del avin tipo A a la zona en
emergencia.B : nmero de viajes del avin tipo B a la zona en
emergencia.
-17-
-
Programacin Lineal
Restricciones
Programacin Lineal
Restriccin por disponibilidad de gasolina:Restricciones
800B)12()4(A)8()5( +800B48A40 +
Restriccin por disponibilidad de aceite:40B)200()4(A)250()5( 40B)20.0()4(A)25.0()5( +
40B80.0A25.1 +Restricciones de no negatividad:
0BA 0B,A -18-
-
Programacin Lineal
Funcin objetivo
Programacin Lineal
B480A400ZMax +=Funcin objetivo
B480A400ZMax +
-19-
-
Programacin Lineal
El programa queda:
Programacin Lineal
B480A400ZMax +=El programa queda:
B480A400ZMax +sujeto a
800B48A40 800B48A40 +40B80.0A25.1 +
0B,A
-20-
-
Programacin Lineal
PROBLEMA 02
Programacin Lineal
PROBLEMA 02.-Se desea averiguar las cantidades de ciertos alimentosq e deben comerse para satisfacer ciertosque deben comerse para satisfacer ciertosrequerimientos nutritivos a un costo mnimo.Supongamos que las consideraciones se limitan aSupongamos que las consideraciones se limitan aleche, carne, huevos y a las vitaminas A, C y D.
Supongamos que el nmero de miligramos deSupongamos que el nmero de miligramos devitaminas contenidas en cada unidad de alimentos seda en la tabla siguiente:
-21-
-
Programacin LinealProgramacin Lineal
VITAMINAMnimo
requerido a Galn de
l hLibra de Docena de
h
A 1 1 10 1C 100 10 10 50
qdiario (mg)
leche carne huevos
C 100 10 10 50D 10 100 10 10
Costo en soles 40 44 20
-22-
-
Programacin Lineal
SOLUCION
Programacin Lineal
SOLUCION.-
Variables de decisinL : cantidad de leche en galonesC : cantidad de carne en librasH : cantidad de huevos por docena
-23-
-
Programacin Lineal
Restricciones
Programacin Lineal
Restriccin por requerimiento mnimo de vitamina A:Restricciones
1H10CL ++Restriccin por requerimiento mnimo de vitamina C:Restriccin por requerimiento mnimo de vitamina C:
50H10C10L100 ++Restriccin por requerimiento mnimo de vitamina D:
10H10C100L10 ++Restricciones de no negatividad:
0HCL 0H,C,L -24-
-
Programacin Lineal
Funcin objetivo
Programacin Lineal
H20C44L40ZMin ++=Funcin objetivo
H20C44L40ZMin ++
-25-
-
Programacin Lineal
El programa queda:
Programacin Lineal
El programa queda:
H20C44L40ZMin ++=sujeto a
H20C44L40ZMin ++
110C 1H10CL ++50H10C10L100 ++
0HCL 10H10C100L10 ++
0H,C,L
-26-
-
Programacin Lineal
PROBLEMA 03
Programacin Lineal
La compaa Mauser, fabricante de fusiles automticos,ti 3 d t t l l f ttiene 3 departamentos en los cuales se manufacturansus modelos S-1000 y S-2000, las capacidadesmensuales son las siguientes:
Requerimientos unitarios de tiempo (en horas)
mensuales son las siguientes:
de tiempo (en horas)
DepartamentosHoras disponibles en el siguiente mes
Modelo S-2000
Modelo S-1000
Departamento 1 4 2 1,600Departamento 2 2.5 1 1,200Departamento 3 4.5 1.5 1,600
PROBLEMA 03.- Propuesto
-27-
-
Programacin Lineal
La utilidad del modelo S 1000 es de 40 dlares por
Programacin Lineal
La utilidad del modelo S-1000 es de 40 dlares porunidad y la del modelo S-2000 es de 10 dlares porunidad; suponiendo que la compaa puede venderunidad; suponiendo que la compaa puede vendercualquier cantidad de estos productos, debido acondiciones favorables de mercado.
Determinar el nmero de unidades de cada modelo quese debe de fabricar de manera que se maximice lautilidad total.
-28-