Programacin Lineal

Un modelo de programacin lineal proporciona un mtodo eficiente para

determinar una decisin ptima, (o una estrategia ptima o un plan ptimo)
escogida de un gran nmero de decisiones posibles.
En todos los problemas de Programacin Lineal, el objetivo es la
maimi!acin o minimi!acin de alguna cantidad.
Construccin de los Modelos de Programacin Lineal
"e forma obligatoria se deben cumplir los siguientes re#uerimientos para
construir un modelo de Programacin Lineal.
1. $uncin objetivo. ($. %). "ebe &aber un objetivo (o meta o blanco) #ue la
optimi!acin desea alcan!ar.
'. (estricciones ) decisiones. "ebe &aber cursos o alternativas de accin o
decisiones, uno de los cu*les permite alcan!ar el objetivo.
+. La $. % ) las restricciones son lineales. "eben utili!arse solamente
ecuaciones lineales o desigualdades lineales.
Modelo standard de Programacin Lineal
%ptimi!ar n n
X C X C X C Z + + + =
2 2 1 1 . $uncin objetivo.
,ujeta a restricciones
1 1 2 12 1 11
b X a X a X a
n n
+ + +
2 2 2 22 1 21
b X a X a X a
n n
+ + +
m n mn m m
b X a X a X a + + +
2 2 1 1
"ebiendo ser
0 , , ,
2 1

n
X X X
"onde-
.j - variables de decisin, j / 0,'.., n.
n - nmero de variables.
m - nmero de restricciones.
aij , bi , cj constantes, i / 0,'.., m.
Pasos para la construccin del modelo
0. "efinir las variables de decisin.
'. "efinir el objetivo o meta en trminos de las variables de decisin.
+. "efinir las restricciones.
1. (estringir todas las variables para #ue sean no negativas.
Ejemplo- 2aller de mantenimiento.
Un taller de mantenimiento fabrica dos tipos de pie!as para la reparacin de
e#uipos fundamentales del proceso productivo. Estas pie!as re#uieren un cierto
tiempo de trabajo en cada una de las tres m*#uinas #ue las procesan. Este
tiempo, as3 como la capacidad disponible (&) ) la ganancia por cada pie!a se
muestran en el cuadro siguiente-
Mquina
Tiempo por Pieza
Fondo de Tiempo(h)
A B
' ' 045
0 ' 0'5
1 ' '65
!anancia ("#Pieza) 4 1
,e logra vender todo lo producido ) se desea determinar la cantidad de
pie!as a fabricar #ue optimice la ganancia.
$ormulando el modelo
1
X
- 7mero de pie!as del tipo 8.
2
X - 7mero de pie!as del tipo 9.
%ptimi!ando la ganancia (:).
2 1
4 6 X X MaxZ + =
,ujeto a las restricciones-
160 2 2
2 1
+ X X $ondo de tiempo de la m*#uina 0.
120 2
2 1
+ X X
$ondo de tiempo de la m*#uina '.
280 2 4
2 1
+ X X $ondo de tiempo de la m*#uina +.
;omo ninguna variable implicada puede ser negativa.
0
1
X
<
0
2
X
M$todos de solucin
M$todo gr%ico&
El mtodo gr*fico se utili!a para la solucin de problemas de PL,
representando geomtricamente a las restricciones, condiciones tcnicas ) el
objetivo.
El modelo se puede resolver en forma gr*fica si slo tiene dos variables.
Para modelos con tres o m*s variables, el mtodo gr*fico es impr*ctico o
imposible.
;uando los ejes son relacionados con las variables del problema, el mtodo
es llamado mtodo gr*fico en actividad. ;uando se relacionan las restricciones
tecnolgicas se denomina mtodo gr*fico en recursos.
Los pasos necesarios para reali!ar el mtodo son-
0. =raficar las soluciones factibles, o el espacio de soluciones (factible), #ue
satisfagan todas las restricciones en forma simult*nea.
'. Las restricciones de no negatividad
0
i
X
conf3an todos los valores posibles.
+. El espacio encerrado por las restricciones restantes se determinan
sustitu)endo en primer trmino por / para cada restriccin, con lo cual se
produce la ecuacin de una l3nea recta.
1. 2ra!ar cada l3nea recta en el plano ) la regin en cual se encuentra cada
restriccin cuando se considera la desigualdad lo indica la direccin de la
flec&a situada sobre la l3nea recta asociada.
>. ;ada punto contenido o situado en la frontera del espacio de soluciones
satisfacen todas las restricciones ) por consiguiente, representa un punto
factible.
4. 8un#ue &a) un nmero infinito de puntos factibles en el espacio de soluciones,
la solucin ptima puede determinarse al observar la direccin en la cual
aumenta la funcin objetivo.
?. Las l3neas paralelas #ue representan la funcin objetivo se tra!an mediante la
asignacin de valores arbitrarios a fin de determinar la pendiente ) la direccin
en la cual crece o decrece el valor de la funcin objetivo.
Ejemplo
@aimi!ar-
2 1
2 3 X X Z + =
(estricciones- 6 2
2 1
+ X X (0)
8 2
2 1
+ X X
(')
1
2 1
+ X X (+)
2
2
X
(1)
0
1
X (>)
0
2
X
(4)
;onvirtiendo las restricciones a igualdad ) represent*ndolas gr*ficamente se
tiene-
6 2
2 1
= + X X (0)
8 2
2 1
= + X X
(')
1
2 1
= + X X (+)
2
2
= X
(1)
0
1
= X (>)
0
2
= X
(4)
,oluciones
@aimi!ar
2 1
2 3 X X Z + =
Punto
( )
2 1
, X X
:
8 ( ) 0 , 0 5
9 ( ) 0 , 4 0'
; ( ) 3 . 1 , 3 . 3 0'.4 (Aptima)
" ( ) 3 , 2 0'
E ( ) 3 , 1 B
$ ( ) 2 , 0 1
Para obtener la solucin gr*fica, despus de &aber obtenido el espacio de
solucin ) graficada la funcin objetivo el factor clave consiste en decidir la
direccin de mejora de la funcin objetivo.
M$todo 'imple(
El mtodo simple es un procedimiento iterativo #ue permite tender
progresivamente &acia la solucin ptima. Es un procedimiento sistem*tico )
eficiente para encontrar ) probar soluciones situadas en los vrtices de
optimalidad.
El mtodo re#uiere #ue las restricciones sean ecuaciones en lugar de
inecuaciones, lo cual se logra aCadiendo variables de &olgura a cada inecuacin
del modelo, variables #ue nunca pueden ser negativas ) tienen coeficiente 5 en la
funcin objetivo. Para el modelo formulado anteriormente tenemos-
0 4 6
2 1
= X X Z
160 2 2
1 2 1
= + + S X X
120 2
2 2 1
= + + S X X
280 2 4
3 2 1
= + + S X X
2odas las variables son no negativas.
La solucin b*sica inicial se obtiene seleccionando las variables de &olgura
como variables b*sicas, resultando conveniente disponer los valores como se
muestran en la tabla siguiente-
i D9 : .0 .' ,0 ,' ,+ 9i
0 : 0 E 4 E1 5 5 5 5
' ,0 5 ' ' 0 5 5 045
+ ,' 5 0 ' 5 0 5 0'5
1 ,+ 5 1 ' 5 5 0 '65
;ada ecuacin debe tener una nica variable b*sica (D9), con el coeficiente
unidad en la fila correspondiente.
Esta solucin b*sica debe ser eaminada para observar si puede ser
mejorada. La presencia de coeficientes negativos en la $% indica #ue la solucin
b*sica puede ser mejorada, pues el valor de : se incrementar*.
;uando no &a) coeficientes negativos, significa #ue la solucin es ptima.
Para encontrar una solucin mejorada es necesario-
Elegir la variable #ue entra como la de ma)or coeficiente negativo (
1
X )
Elegir la variable #ue sale como a#uella #ue al ser removida permita #ue la
variable #ue entra a la base pueda tener un valor tan grande como sea
posible, sin violar alguna de las restricciones en el modelo. En este caso la
variable 3
S
deja la base ) a su ve!
1
X se introduce como la nueva variable
b*sica.
El elemento pivote es el coeficiente #ue est* en la interseccin de la columna
de la variable #ue entra ) la fila de la variable #ue sale.
Los valores correspondientes a la nueva fila pivote se obtienen dividiendo los
coeficientes de la fila pivote en la tabla inicial por el elemento pivote.
Las otras filas de la solucin mejorada se calculan por la epresin-
7ueva fila / $ila anterior F elemento de la columna pivote (nueva fila pivote)
8s3, se obtiene la siguiente tabla-
i D9 : .0 .' ,0 ,' ,+ 9i
5 : 0 5 E 0 5 5 0.> 1'5
0 ,0 5 5 0 0 5 E5.> '5
' ,' 5 5 0.> 5 0 E 5.'> >5
+ )* + * +&, + + +&-, .+
;omo se puede apreciar esta no es an la solucin ptima GPor #uH
Iterando nuevamente se obtiene la tabla correspondiente #ue se muestra a
continuacin-
i D9 : .0 .0 ,0 ,' ,+ 9i
5 : 0 5 5 0 5 0 115
0 .' 5 5 0 0 5 E 5.> '5
' ,' 5 5 5 E 0.> 0 5.> '5
+ .0 5 0 5 E 5.> 5 5.> 45
GEs esta la solucin ptimaH ,i lo es determine entonces los valores de las
variables para el ptimo.
,e &a aplicado el algoritmo para el caso del modelo standard, cuando se
presentan problemas con restricciones J o / ) el criterio de optimi!acin es
m3nimo, entonces &a) #ue introducir variables artificiales ) se sugiere convertir el
problema en un problema de maimi!ar.
Aspectos Fundamentales /el M$todo 'imple(
Encuentra una solucin ptima
Es un mtodo de cambio de bases
(e#uiere #ue la funcin objetivo sea epresada de tal forma #ue cada variable
b*sica tenga como coeficiente 5
(e#uiere #ue cada variable b*sica apare!ca en una ) solamente una ecuacin
de restriccin.