bolo 5 - programacion lineal1
DESCRIPTION
Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1Lineal1TRANSCRIPT
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 1/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 1
PROGRAMACION LINEAL
1. GENERALIDADES
La programación lineal, es el elemento más consistente y difundido de laInvestigación Operativa, encuentra aplicaciones en la solución de diversosproblemas dentro el campo técnico-económico. Como ser, en problemas detransporte, de mezcla y conuntado de materiales, de asignación de recursos, etc.,y en problemas sobre planificación de la producción de materiales y bienes. !epuede decir, "ue esta #ltima es una de las aplicaciones, de este método, de mayor provec$o dentro la econom%a y permite medir el tama&o óptimo de la produccióncon el fin de obtener un resultado económico má'imo de las operaciones otambién determinar las condiciones de producción para las cuales el costo deproducción del producto o de los productos sea m%nimo.
Un programa lineal, es un modelo matemático en el cual las relaciones
algebraicas que lo conforman son todas necesariamente de primer grado.
(un"ue el planteo y elaboración de un programa lineal puede efectuarseindependientemente de sus aplicaciones, se prefiere a"u%, tomar una referenciaeconómica con este fin.
!ea )y* un fenómeno económico, resultante de muc$os efectos elementales "uelos denominaremos e+, e..en !i admitimos "ue estos gozan de la ley de
composición aditiva, tendr%amos y=e
1+e
2+e
3………e
n
y=∑i=1
n
e j
nnn xae
xae
xae
=
=
=
..............
222
111
/or otro lado admitiremos "ue todo efecto elemental e + esproporcional a su causa "ue denominaremos ' o sea
UNV. CABRERA PLANTARROSA PAOLA
0+1
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 2/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 2
2eemplazando obtenernos
nn xa xa xa y .......2211 ++=
∑=
=n
i
j j xa y1
3onde los elementos a , son coeficientes de proporcionalidad 0escalares1 entrecausas y efectos elementales. Como las causas ' pueden ser de distintanaturaleza y tama&o a determinarse, las llamaremos desde a$ora variables dedecisión.
!i en un problema4 m5+ efectos son todos proporcionales a )n* causas y estoocurre en muc$os problemas económicos al menos de una manera bastanteapro'imada4 entonces el problema puede ser descrito por medio de m5+ formas
lineales del tipo 01 como sigue
nnmmmm
nn
nn
xa xa xa y
xa xa xa y
xa xa xa y
12211
22221212
12121111
.......
................................................
.......
.......
++=
++=
++=
nnmmmm xa xa xa y ,..............,, 12211111 ++++ ++=
UNV. CABRERA PLANTARROSA PAOLA
01
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 3/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 3
mm b y
b y
b y
=
=
=
<
>
<
>
<
>
............
22
11
Consideremos a$ora "ue los primeros efectos no pueden ser ilimitados0no deben rebasar l%mites impuestos por ciertas condiciones1, sino "ue debenproducirse dentro de ciertas fronteras o sea
mnnmmm
nn
nn
b xa xa xa
b xa xa xa
b xa xa xa
≤≥++
≤≥++
≤≥++
12211
22222121
11212111
.......
................................................
.......
.......
O también
UNV. CABRERA PLANTARROSA PAOLA
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 4/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 4
mi
b xa yn
i
j j
......3,2,1
1
1
=
≥≤=∑=
O finalmente
/or otro lado consideraremos "ue el #ltimo efecto m5+ sintetiza el grado derealización del fin "ue interesa optimizarlo, es decir $acerlo má'imo o m%nimo,respetando las limitaciones de los )m* efectos anteriores.
nnm
m
m
m
ca
ca
ca
z y
=
=
=
=
+
+
+
+
,1
12,1
11,1
1
................
/ara diferenciar de las anteriores relaciones llamaremos
nn xc xc xc z +++= ........2211
6ntonces el #ltimo efecto puede escribirsecomo
UNV. CABRERA PLANTARROSA PAOLA
071
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 5/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 5
∑=
=n
j
j j xc z 1
6n los problemas en los "ue se emplea el método de la programación lineal,interesa precisamente determinar un e'tremo del efecto )z*, pero para el caso sedebe tomar en cuenta la condición de e'istencia de l%mites de variación para losprimeros )m* efectos, o sea se trata de estudiar el e'tremo de una funcióncondicionada.
/or otro lado vamos a acordar "ue las variables ' de las relaciones 071 y 081 seannecesariamente no-negativas, por"ue la negatividad de las variables ' carece de
sentido en problemas de naturaleza técnica o económica.
0x
1,2,.....mi;
j ≥
=><∑=
j
n
i j
jij b xa
2esumiendo todas las consideracionesanteriores4 reuniendo las relaciones 071 y 081 podemos escribir finalmente
∑=
=n
i j
j j xc z OPT )(
6l conunto de relaciones 091 as% obtenido se denomina /rograma Lineal, en elcual las relaciones
UNV. CABRERA PLANTARROSA PAOLA
081
091
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 6/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 6
0x
1,2,.....mi;
j ≥
=>=<∑=
i
n
i j
jij b xa
!on denominadas condiciones, restricciones o limitaciones del problema )y*,
∑=
=n
i j
j j xc z OPT )(
6s la función del fin, función obetivo o función económica 0función de producción1si se trata de un programa lineal "ue sintetiza un problema de naturalezaeconómica.
/ara comprender meor podemos decir "ue en un programa lineal, lasrestricciones constituyen un conunto de relaciones "ue describen el problema y lafunción económica el obetivo deseado.
La programación lineal tiene por finalidad plantear y resolver problemas por mediodel estudio y solución de modelos del tipo 091.
6studiar y resolver un programa lineal es encontrar un valor óptimo para la funcióneconómica respetando las restricciones impuestas. 6n términos algebraicos,encontrar un conunto de valores ' "ue $aga má'imo el valor de la función obetivo)z*, cumpliendo las inecuaciones 0:1 o sea
∑=
=n
i j
j j xc z OPT z de Mino Máx )(
UNV. CABRERA PLANTARROSA PAOLA
0;1
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 7/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 7
0x
1,2,.....mi;
j ≥
=>=<∑=
i
n
i j
jij b xa
!ometida a las condiciones
2. EJEMPLOS DE PROGRAMACION LINEAL
!e dan a continuación algunos eemplos, sobre la forma de formular un problema
como un programa lineal. 6l contenido de los eemplos, no indica de ningunamanera "ue la programación lineal se pueda aplicar solo a ese tipo de problemasy en las condiciones restringidas en cuanto a datos y variables de estos. !e $anelegido los eemplos "ue e'pondremos por su fácil comprensión, por"ue contienenun n#mero reducido de datos y se prestan a los fines didácticos.
6s importante anotar "ue la programación lineal, $a encontrado aplicacionesdiversas en distintos campos de la econom%a, como en la solución de problemasde planificación en los "ue se desea determinar estados óptimos desde el puntode vista económico (1)
EJEMPLO 1. <na pe"ue&a fábrica, se dedica a elaborar sobre una má"uina, tresproductos diferentes4 p+, p, y p7, trabaando 89 $oras semanales. Losrendimientos económicos de estos son +8=.+== y :9 u.m. 0deducidos costos deproducción y otros1 respectivamente. Las velocidades de producción de p+, p, yp7 son 9= pzs>$ora y :9 pzs>$ora. !e sabe por otro lado, "ue el mercado paraestos productos es cuando mas +=== pzs para p+, 9== pzs para p y +9== pzs parap7 por semana.
?ue cantidades de los productos p+, p, y p7, deber%a elaborar la fábrica para "ueel rendimiento económico total sea má'imo. Calculando los rendimientoseconómicos individuales por $ora tendr%amos
2endimiento alfabricar por $ora
u.m.>$ora
UNV. CABRERA PLANTARROSA PAOLA
0:1
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 8/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 8
p+
p
p7
+8= um>pzs @ 9= pzs>$ A :===+== um>pzs @ 9 pzs>$ A 9== :9 um>pzs @ :9 pzs>$ A 9;9
Las velocidades de producción o rendimientos técnicos por $ora, $an sidoe'presadas en unidades monetarias. /odr%amos pensar, en el siguiente plan deproducción4 elaborar primero, piezas del producto p+ $asta la cantidad tope "ueabsorbe semanalmente el mercado, acto seguido piezas del producto p7, $asta lacantidad tope de demanda y finalmente elaborar el producto p .
/ara ese plan, se re"uiere )t* $oras de trabao de la má"uina, igual a la suma det+, t y t7, tiempos necesarios para elaborar la demanda de p +, p y p7.
semht t
sem pzsh pzs p /20;
/1000/50: 1
1
1 ==
(l elaborar
semht t
sem pzsh pzs p /20;
/500/25: 2
2
2 ==
semht t
sem pzsh pzs p /20;
/1500/75: 3
3
31 ==
semhr t t t t /60321 =++=6l tiempo total semanal para producir las
demandas es
/ero no debemos olvidar "ue la má"uina "ue se dispone en la fábrica, puedefuncionar solo 89 $oras semanales y se re"uerir%a ;=-89A+9 $rs>sem adicionales
UNV. CABRERA PLANTARROSA PAOLA
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 9/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 9
para satisfacer la demanda con la producción, lo "ue no es posible cumplir. 6lbuen criterios nos conduce luego a tomar la siguiente decisión disponer =$rs>sem para producir piezas de p+, = $rs>sem para producir piezas de p7 yfinalmente 9 $rs>sem para elaborar piezas del producto p .
hrs
xpzs
hr
pzs
51
25=
6n 9 $oras se elaborarán +9 pzs del producto p,calculado con la relación
pzs x 12525*5 ==
Con las producciones indicadas, el rendimiento económico será
/2O3<CBO /2O3<CCID/E!>!6F(D(
BI6F/OF(?<ID(GO2(!
IDH26!O <.F.
p+
p
p7
+===+9==+9
==
9
+8=.===++.9==+.9==
BOB(L 89 ;9.===
ormularemos a$ora, un programa lineal con los datos del problema.
Llamemos '+, ' y '7 las cantidades de piezas a elaborar por semana, de losproductos p+, p y p7. 6n este caso son las variables controlables o de decisión delproblema, cuyos niveles deben ser determinados respetando las condiciones delproblema, de tal modo "ue se tenga un rendimiento económico óptimo vales decir má'imo, de las operaciones de producción.
UNV. CABRERA PLANTARROSA PAOLA
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 10/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 10
/asamos en primer término a elaborar las restricciones del programa lineal con losdatos del problema.
15003 ≤
x 5002 ≤
x 10001 ≤ x !abemos "ue las cantidades a producir
no deben sobrepasar la demanda semanal, o sea algebraicamente tendr%amos
hrs x p 75/33 = hrs x p 25/22 = hrs x p 50/11 =/or otra parte, los
tiempos para producir semanalmente '+, ' y '7 de p+, p y p7 serán
4575/25/50/ 321 ≤++ x x x ($ora bien, la suma de tiempos de
fabricación de los productos no debe ser mayor "ue el tiempo má'imo de trabaosemanal de la má"uina, por consiguiente el tiempo total para producir '+, ' y '7
pzs, debe ser menor o cuando más igual a 89 $oras, es decir
6750263 321 ≤++ x x xO bien
03 ≥ x 02 ≥ x 01 ≥ x2elación "ue sintetiza la limitación técnica respecto del
rendimiento de la má"uina para producir los 7 productos. 3ebemos recordar también "ue '+, ' y '7 deben ser variables no-negativas, o sea
(s% $emos obtenido las condiciones, restricciones o limitaciones del problema.?ueda elaborar la función económica u obetivo del problema, "ue sintetice el
UNV. CABRERA PLANTARROSA PAOLA
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 11/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 11
resultado económico total "ue se logrará, por la producción de los 7 productos p +,p y p7
/ara el efecto consideremos "ue
2esultado económico al elaborar '+ pzs de p+
+8= '+ um
2esultado económico al elaborar ' pzs de p
+== ' um
2esultado económico al elaborar '7 pzs de p7
:9 '7 um
321 75100140 x x x z ++= /or tanto el resultado total será
O función obetivo a ser optimizada.
En resumen tenemos:
10001 ≤ x 01 ≥ x
02 ≥ x 5002 ≤ x
03 ≥ x 15003 ≤ x
UNV. CABRERA PLANTARROSA PAOLA
!egunda limitación restricciones
económicas por efecto de la demanda
/rimera limitación restricciones
naturales de no-negatividad
01)(1)
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 12/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 12
6750263 321 ≤++ x x x
321 75100140)( x x x z Max ++=unción económica 0o función
de producción1
Las relaciones 0J1, 0K1, 0+=1 y 0++1 constituyen un programa lineal elaborado conlos datos del problema planteado. La meor pol%tica de producción semanal será,un conunto '+, ' y '7 "ue $aga má'imo el valor de )z* y satisfaga a la vezrestricciones impuestas a través del sistema (1). La b#s"ueda de tal conunto seefectuará un vez conocido un método de solución de programas lineales, lo "ueveremos en los puntos 0;1 y 0:1
3. NOTACION MATRICIAL DE LOS PROGRAMAS LINEALES.
!i el problema "ue se sintetiza por medio de un programa lineal, lleva )n* variablesde decisión o efectivas y )m* limitaciones o restricciones4 entonces el programa seescribirá (1)
0x
1,2,.....mi;
j ≥
=≤∑=
i
n
i j
jij b xa
∑=
=n
i j
j j xc z OPT )(
0x j ≥
UNV. CABRERA PLANTARROSA PAOLA
(1)
Bercera limitación restricciones técnica derendimiento de la má"uina
0++1
26!B2ICCIOD6!
<DCIOD OM6BINO
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 13/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 13
0x j ≥La condición 4 de no negatividad incluida en las restricciones
proviene de la consideración "ue en un fenómeno técnico-.económico o de
organización intervienen un cierto n#mero de variables 0controlables1 a condiciónde "ue tendrán significado cuando y solo cuando sean positivas o nulas. /or estarazón llamaremos a las restricciones , restricciones naturales, "ue detodas maneras se incluyen en los programas lineales.
($ora bien, en el conunto de restricciones, es siempre posible agregar unacantidad de variables ' 0A+,,7m1 para transformar las desigualdades enigualdades. 6fectuada esta operación el sistema de restricciones se transformaen
mnnnn
b x xa ik
n
j
jij
++++=
==+∑=
,...3,2,1 x
.....m1,2,3,4...i;
k
1
!e a&adió una variable por cada restricción, "ue podr%a tener coeficiente igual a45+,= o -+4 seg#n el caso. Las variables a&adidas de este modo reciben el nombrede variables de $olgura (1)
1
i
mn
j
jij b xa =∑+
=
6n estas condiciones un programa lineal en su formageneral se escribir%a
∑+
=
=mn
j
j j xc z OPT 1
)(
UNV. CABRERA PLANTARROSA PAOLA
0K1
0+=1
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 14/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 14
cx z OPT
xb Ax
=
≥
=
)(
0
Introduciendo notación matricial,
=
++
++
++
mnmnmnmmm
mnnn
mnnn
aaaaa
aaaaa
aaaaa
A
,1,,2,1,
,21,2,22221
,11,1,11211
.........
...............................
.........
.........
3onde
Es la Matriz rectangular de dimensión mx(n+m)
UNV. CABRERA PLANTARROSA PAOLA
0++1
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 15/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 15
=
mb
b
b
b
.........
2
1
=
+
+
mn
n
x
x
x
x
x
...
...1
2
1
).... ..... ( 121 mnnn cccccc ++=)'* matriz columna o vector de
incógnitas de n5m elementos, y )b* matriz columna o vector de m elementosindependientes 0debido a la e'istencia de m limitaciones1.
Fatriz fila o vector formado por los n5m coeficientes de las variables en la funciónobetivo, y finalmente z variables 0matriz de un solo elemento1 dependiente de )'* ycuyo valor debe ser optimizado.
EJEMPLO 2. Bomemos el programa lineal siguiente
3
72
8 2
2
21
21
≤
≤+
≤+
x
x x
x x
0, 21 ≥ x xRESTRICCIONES
UNV. CABRERA PLANTARROSA PAOLA
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 16/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 16
21)( x x Z MAX +=FUNCION OBJETIVO
(&adiendo variables de $olgura en las restricciones y en la función obetivotendr%amos
RESTRICCIONES
3 00 0x
70 02
800 2
54321
54321
54321
≤++++
≤++++
≤++++
x x x x
x x x x x
x x x x x
54321 000)( x x x x x Z MAX ++++=FUN
CION OBJETIVO
($ora utilizaremos notación matricial
=
5
4
3
2
1
)0 0 0 1 1()(
x
x
x x
x
Z MAX
=
3
78
1 0 0 1 0
0 1 0 2 10 0 1 1 2
5
4
3
2
1
x
x
x x
x
UNV. CABRERA PLANTARROSA PAOLA
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 17/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 17
=
3
7
8
b
=
5
4
3
2
1
x
x
x
x
x
x
=
1 0 0 1 0
0 1 0 2 1
0 0 1 1 2
A
O sea
)0 0 0 1 1(=c
4. EL MÉTODO SIMPLEX O DE DANTZING
cx z OPT
x
b Ax
=
≥
=
)(
0
Bomemos el programa lineal 0++1 en el "ue sabemos"ue el sistema PAb, es no-redundante y el n#mero de variables es superior aln#mero de ecuaciones y O/BAF(P.
UNV. CABRERA PLANTARROSA PAOLA
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 18/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 18
!i admitimos "ue e'iste un espacio 6 de soluciones posibles de 0/.L.1, entoncestodo punto ' Q 6 "ue sea solución posible de base será necesariamente un puntoe'tremo de 6. 6ntre todos los puntos "ue representan soluciones posibles debase de 0/.L.1 e'istirá alguno "ue $aga 0F(P1zA c' este punto es el "ue interesaencontrar.
La idea esencial del algoritmo de 3antzig, consiste en aplicar sucesivamente lascondiciones de realización y optimidad 0+1 y 0+71, la solución se encuentracuando ya no es posible meorar la función obetivo.
01 ≤− − jii j A Acc 0
0 1≥
≥
− b A x
i
i
!ea ' A 0'i, ' 1 (1) una solución posible de base inicial de 0/.L.1 para la cual z tieneun valor y (i es la matriz de base asociada a las variables de base ' i.
/ongamos ('Ab en su forma canónica
1
b x A x An
i j
j j
mn
ni
ii =+∑∑=
+
+=
11
∑∑=
+
+=
+=n
j
j j
mn
ni
ii xc xc z
UNV. CABRERA PLANTARROSA PAOLA
0/.L.1
0+710+1
0+81
0+91
7/18/2019 Bolo 5 - Programacion Lineal1
http://slidepdf.com/reader/full/bolo-5-programacion-lineal1 19/19
INGENIERIA COMERCIAL - INVESTIGACION OPERATIVA 19
,...2,1
0
n j
x j
=
=
/ero
1
∑+
+=
=mn
ni
ii xc z 1
b x Amn
ni
ii =∑+
+=
Luego
UNV. CABRERA PLANTARROSA PAOLA
/or"ue se trata de una solución posiblede bases
0+:10+;1