02 modelos de programación lineal.pptx

8/18/2019 02 Modelos de programación lineal.pptx

1/109

Modelos de programación

linealMiguel Mejía Puente

[email protected]

mailto:[email protected]:[email protected]


2/109

Contenido

• Problema de programación lineal.• Requerimientos del problema de programación lineal.

• Método gráfco para resolver problemas demaimi!ación con dos variables.

• Método gráfco para resolver problemas deminimi!ación con dos variables.

• Casos especiales de programación lineal.

• "olución de problemas de programación lineal

usando computadora.• #nálisis de sensibilidad gráfco $ por computadora.

3/29/16 Miguel Mejía Puente 2


3/109

Problema de programación lineal

Programación lineal %P&'

• (s una técnica de modelado usada en elproceso de toma de decisiones.

•Primera etapa.) variables de decisión.• "egunda etapa.) restricciones.

• *ercera etapa.) +unción objetivo.

Problema de programación lineal %PP&'

• ,estión de las industrias.



4/109

Requerimientos del problema deprogramación lineal

• &a programación lineal %P&' es un problema deoptimi!ación para el cual se e+ect-a losiguiente "e intenta maimi!ar %o minimi!ar' una +unción

lineal %llamada +unción objetivo' de las variables dedecisión. &os valores de las variables de decisión deben

satis+acer un conjunto de restricciones. Cadarestricción debe ser una ecuación o inecuación

lineal. /na restricción de signo es asociada con cada

variable.



5/109

Cinco suposiciones básicas de P&%0'

Certe!a. &os n-meros en la +unción objetivo$ las restricciones son conocidos concerte!a $ no pueden cambiar durante elperiodo en que se está 1aciendo el estudio.

Proporcionalidad. (iste en la +unciónobjetivo $ las restricciones.

#ditividad.) (l total de todas las actividades

es igual a la suma de las actividadesindividuales.



6/109

Cinco suposiciones básicas de P&%2'

3ivisibilidad.) &as soluciones no necesitanser n-meros enteros. &as soluciones sondivisibles $ pueden tomar cualquier valor

+raccionario.4o negatividad.) *odas las respuestas ovariables son no negativas %5 6'.&osvalores negativos de cantidades +ísicasson imposibles.



7/109

7ormulación de un problema deP& %0'

3ado un conjunto de m ecuaciones oinecuaciones lineales $ n variables de decisión8se requiere 1allar valores no negativos de estasvariables que satis+agan las restricciones $

maimicen o minimicen la +unción lineal de lasvariables llamada +unción objetivo.

Matemáticamente tenemos la siguiente+ormulación

9ariables de 3ecisión

: j 8 j ; 08 28


8/109

7ormulación de un problema deP& %2'

7unción objetivoMa %ó Min' = ; C

0:

0 > C

2:

2 > . . . . . . > C

n:

n

Restricciones

a00:0 > a02:2 > ... > a0n:n ?≤8 =8 ≥ b0

a20

:0 > a

22:

2 > ... > a

2n:

n ?≤8 =8 ≥ b

2

...

am0:0 > am2:2 > ...> amn:n ?≤

8=

8≥

bmRango de eistencia

: j ≥ 68 j ; 08 28


9/109

(jemplos de +ormulación de PP&%0'9ariables de decisión:0 n-mero de automóviles que se compran $ venden por mes

:2 n-mero de camionetas que se compran $ venden por mes

7unción objetivoMaimi!ar utilidades

Ma = ; A66 :0 > B66 :2 RestriccionesCantidad máima de automóviles que puede proveer el +abricante:0 ≤ A66

Cantidad máima de camionetas que puede proveer el +abricante:2 ≤ 266

*iempo disponible para preparar automóviles $ camionetas2 :0 > A :2 ≤ 66

Rango de eistencia:08 :2 ≥ 63/29/16 Miguel Mejía Puente 9


10/109

(jemplos de +ormulación de PP&%2'9ariables de decisión:0 cantidad de acres de brócoli que se cultivan $ venden por

temporada:2 cantidad de acres de coliDor que se cultivan $ venden por

temporada

7unción objetivoMaimi!ar utilidadesMa = ; E666 :0 > 0666 :2Restricciones3isponibilidad de acres para cultivar brócoli $ coliDor0 :0 > 0 :2 ≤ E66

Restricción gubernamental para cultivar brócoli0 :0 ≤ 266

3isponibilidad de tiempo en 1oras)1ombre2.E :0 > E.E :2 ≤ 0 266

Rango de eistencia3/29/16 Miguel Mejía Puente 10


11/109

(jemplos de +ormulación de PP&%A'9ariables de decisión:0 cantidad de camionetas que se compran $ venden durante el

aFo:2 cantidad de autobuses pequeFos que se compran $ venden

durante el aFo

:A cantidad de autobuses grandes que se compran $ vendendurante el aFo7unción objetivoMaimi!ar utilidadesMa = ; 2666 :0 > 2G66 :2 > HE66 :ARestricciones

Inversión disponibleHE66 :0 > 06E66 :2 > 2 666 :A ≤ E66666

Capacidad de mantenimiento %t es el tiempo de mantenimiento deuna camioneta't:0 > 0.Et :2 > At :A ≤ A6t3/29/16 Miguel Mejía Puente 11

é á


12/109

Método gráfco para resolverproblemas de maimi!ación condos variables• &a +orma más +ácil de resolver un problema de

P& con dos variables es con el método gráfco.

• (l método gráfco +unciona sólo cuandoeisten dos variables de decisión8 pero es

invaluable $a que da una idea de cómo+uncionan otros métodos.



13/109

(mpresa maderera %0'

• /na empresa maderera +abrica dos productos8mesas $ sillas8 que usan recursos limitados8tales como8 personal8 máquinas8 materiasprimas8 etc.

• &a empresa desea maimi!ar utilidades queestán basadas en la contribución de cadamesa $ silla producida.

• "e desea determinar cuántas mesas $ sillasdebería +abricar la empresa para maimi!arutilidades8 dados sus recursos limitados.



14/109

(mpresa maderera %2'


Maimi!ar la utilidad"ujeta a

Joras de carpintería utili!adas ≤ 2B6 1oras porsemana

Joras de pintura $ barni!ado utili!adas ≤ 066

Identifcar el objetivo $ las restricciones

Joras requeridas para producir una unidad

3epartamento Mesas

"illas3isponibilida

d%1orasKsema

na'Carpintería Pintura $

barni!ado

B2

A0

2B6066

/tilidad %/M porunidad'

L.66E.66


15/109

epresen ac n gr ca e as


16/109

&as condicionesde no

negatividad :0 56 $ :2 5 6signifcan quesiempre se

trabaja en elprimercuadrante.

epresen ac n gr ca e asrestricciones%0'




17/109

epresen ac n gr ca e asrestricciones%2'

• &a restricción de Carpintería es B:0 > A:2 2B6.

• "e grafca la restricción en +orma de igualdadB:0 > A:2 ; 2B6.

Primero8 sea :0 ; 6 $ resuelva para el punto

donde la línea cru!a el eje :2. B%6' > A%:2' ; 2B68:2 ; G6 sillas.

3espués sea :2 ; 6 $ resuelva para el punto

donde la línea cru!a el eje :0. B%:0' > A%6' ; 2B68:0 ; H6 mesas.

• &a restricción de Carpintería está limitada porla línea que va del punto %:0 ; 68 :2 ; G6' al3/29/16 Miguel Mejía Puente 17



18/109

epresen ac n gr ca e asrestricciones%A'




19/109

epresen ac n gr ca e asrestricciones%B'

• &a restricción de Pintura $ Narni!ado es 2:0 >0:2 066.

• "e grafca la restricción en +orma de igualdad2:0 > 0:2 ; 066.

Primero8 sea :0 ; 6 $ resuelva para el punto

donde la línea cru!a el eje :2. 2%6' > 0%:2' ; 0668

:2 ; 066 sillas.

3espués8 sea :2 ; 6 $ resuelva para el punto

donde la línea cru!a el eje :0. 2%:0' > 0%6' ; 0668

:0 ; E6 mesas.

• &a restricción de Pintura $ Narni!ado está3/29/16 Miguel Mejía Puente 19



20/109

epresen ac n gr ca e asrestricciones%E'




21/109

epresen ac n gr ca e asrestricciones%H'


é ó í


22/109

Método de solución de línea deisoutilidad

0. ,rafque todas las restricciones $ encuentre laregión +actible.

2. "eleccione una línea de utilidad $ grafque estapara encontrar la pendiente.

A. Mueva la línea de la +unción objetivo endirección para incrementar la utilidad mientrasse mantiene la pendiente. (l -ltimo punto entocar la región +actible es la solución óptima.

B. (ncuentre los valores de las variables dedecisión en este -ltimo punto $ calcule lautilidad.



23/109

&ínea de isoutilidad %0'

• Comience asignando utilidades iguales acantidades arbitrarias pero pequeFas enunidades monetarias %/M'.

• (legimos una utilidad de = ; 206. (ste es un nivel de utilidad que puede ser

alcan!ado con +acilidad sin violar ninguna de lasdos restricciones.

• &a +unción objetivo se escribe como 206 ; L:0

> E:2.



24/109

&ínea de isoutilidad %2'

• &a +unción objetivo es justo la ecuación de una líneallamada línea de isoutilidad. (sta representa todas las combinaciones de %:08 :2' que

producirían una utilidad total de 206.• Para tra!ar la +unción objetivo8 se procede de

manera similar a la que se empleó para tra!ar lasrestricciones Primero8 sea :0 ; 6 $ resuelva para el punto donde la

línea cru!a el eje :2. 206 ; L%6' > E%:2'8 :2 ; B2 sillas. 3espués8 sea :2 ; 6 $ resuelva para el punto donde la

línea cru!a el eje :0. 206 ; L%:0' > E%6'8 :0 ; A6 mesas.

• &a +unción objetivo está limitada por la línea que vadel punto %:0 ; 68 :2 ; B2' al punto %:0 ; A68 :2 ;6'.



25/109

&ínea de isoutilidad %A'

• *odos los puntos en la línea representansoluciones +actibles que producen una utilidadde 206.

• Obviamente8 la línea de isoutilidad de 206 no

produce la más alta utilidad posible para laempresa.• "e tra!an dos líneas más8 = ; 2G6 $ = ; AGE8

cada una de las cuales produce una utilidadma$or.

• "e tra!a otra línea8 = ; EH6.



26/109

&ínea de isoutilidad %B'



27/109

&ínea de isoutilidad %E'

• Cuando :0 ; 68 EH6 ; L%6' > E%:2'8 :2 ; 002sillas.

• Cuando :2 ; 68 EH6 ; L%:0' > E%6'8 :0 ; G6mesas.

• (sta línea no se considera porqué no llega atocar la región +actible.

• &a línea con ma$or utilidad que toca elcontorno de la región +actible pasa por el punto

esquina %:0 ; A68 :2 ; B6' $ tiene una utilidadde = ; B06.



28/109

"olución óptima



29/109


30/109

Punto esquina %0'

• &a región +actible para el problema de la (mpresa Madereraes un polígono de cuatro lados con cuatro puntos esquina.(stos puntos son los designados como 08 28 A8 $ B.

• Para encontrar los valores %:08 :2' que producen la utilidadmáima8 se locali!an las coordenadas de cada puntoesquina $ se calcula su utilidad.

Punto 0 %:0 ; 68 :2 ; 6'8 /tilidad ; L%6' > E%6' ; 6

Punto 2 %:0 ; 68 :2 ; G6'8 /tilidad ; L%6' > E%G6' ; B66

Punto A %:0 ; A68 :2 ; B6'8 /tilidad ; L%A6' > E%B6' ; B06

Punto B %:0 ; E68 :

2 ; 6'8 /tilidad ; L%E6' > E%6' ; AE6



31/109

Punto esquina %2'


Método gráfco para resolver


32/109

Método gráfco para resolverproblemas de minimi!ación condos variables• &os problemas de P& de minimi!ación

con dos variables8 también pueden serresueltos gráfcamente.

• (isten dos métodos para encontrar lasolución óptima línea de isocosto $punto esquina.


Método de solución de línea de


33/109

Método de solución de línea deisocosto

0. ,rafque todas las restricciones $ encuentrela región +actible.

2. "eleccione una línea de isocosto $ grafqueesta para encontrar la pendiente.

A. Mueva la línea de la +unción objetivo endirección para decrementar el costo mientrasse mantiene la pendiente. (l -ltimo punto entocar la región +actible es la solución óptima.

B. (ncuentre los valores de las variables de

decisión en este -ltimo punto $ calcule elcosto.


Método de solución del punto


34/109

Método de solución del puntoesquina

0. ,rafque todas las restricciones $ encuentrela región +actible.

2. (ncuentre los puntos esquina de la región+actible.

A. Calcule el costo en cada punto esquina de laregión +actible.

B. "eleccione el punto esquina con el menorvalor de la +unción objetivo. (sta es lasolución óptima.



35/109

Ingrediente Marca 0%o!.Klb.'

Marca 2 %o!.Klb.'

Requerimientomínimo mensual

por pavo %o!.'

# N C

06 A 6

6BG0.E

Costo %/MKlb.' 6.62

6.6A

EB

6.E

,ranja de pavos



36/109

Problema de minimi!ación

9ariables de decisión:0 n-mero de libras adquiridas del alimento marca 0:2 n-mero de libras adquiridas del alimento marca 27unción objetivoMinimi!ar costos

Min = ; 2 :0 > A :2RestriccionesE :0 > 06 :2 5 6 %requerimiento mínimo del ingrediente #'B :0 > A :2 5 BG %requerimiento mínimo del ingrediente N'6.E :0 5 0.E %requerimiento mínimo del ingrediente C'

Rango de eistencia:08 :2 5 6


Método de solución de la línea de


37/109

Método de solución de la línea deisocosto %0'

0. "e constru$e la región +actible.2. "e tra!a una línea de isocosto8 por ejemplo =

; EB o sea EB ; 2:0 > A:28 sin embargo8

eisten muc1os puntos en la región +actible

que darían un costo total más bajo.A. "e mueve la línea de isocosto de +orma

paralela 1acia el origen.




38/109

Método de solución de la línea deisocosto %2'

A. (l -ltimo punto que toca mientras a-n estáen contacto con la región +actible es lasolución óptima. (ste punto tiene lascoordenadas %:0 ; G.B8 :2 ; B.G' $ tiene uncosto asociado de A0.2. &as coordenadas+ueron 1alladas resolviendo un sistema dedos ecuaciones para :0 $ :2.




39/109

Método de solución de la línea deisocosto %A'


Método de solución del punto


40/109

pesquina%0'0."e constru$e la región +actible.2."e encuentran los puntos esquina. (ste

problema tiene tres puntos esquina 08 2 $ A.

Punto 0 %:0 ; A8 :2 ; 02'8 Costo ; 2%A' > A%02' ;

B2Punto 2 %:0 ; G.B8 :2 ; B.G'8 Costo ; 2%G.B' >

A%B.G' ; A0.2

Punto A %:0 ; 0G8 :2 ; 6'8 Costo ; 2%0G' > A%6'

;AH&a solución óptima es el punto 2.


Método de solución del puntoi


41/109

pesquina%2'


Casos especiales de


42/109

Casos especiales deprogramación lineal %0'

Cuatro casos especiales se planteancuando se utili!a el método gráfco pararesolver problemas de P&.

• In+actibilidad.• 4o acotamiento.• 3egeneración.

• M-ltiples soluciones óptimas.


Casos especiales de


43/109

Casos especiales deprogramación lineal %2'

• In+actibilidad.) (n este caso no 1a$ región +actible.• 4o acotamiento.) &a +alta de una o más restricciones

puede 1acer que la región +actible sea infnitamentegrande %región no acotada'8 en tal caso la soluciónóptima $ la +unción objetivo podrían ser no acotadas.

• 3egeneración.) (n el gráfco cuando se observa que másde dos restricciones pasan por la solución óptima8 seafrma que la solución óptima es degenerada.

• M-ltiples soluciones óptimas.) Cuando eiste paralelismoentre la +unción objetivo $ una de las restricciones quecon+orman la región +actible $ que coincide con la+unción objetivo8 se tiene m-ltiples soluciones óptimas.


I + tibilid d


44/109

In+actibilidad


X2

X1

8

6

4

2

0

0 2 4

6 8

Región que

satis+ace latercera restricción

Región que satis+ace las dos primerasrestricciones

4 t i t


45/109

4o acotamiento


:2

:0

0E

06

E

6 6 E 06 0E

Región +actible

:0 5 E :2 06

:0 > 2:2 5 06

3egeneración


46/109

3egeneración


:2

:0

0E

06

E

6 6 E 06 0E26 A6

Región +actible

:0 5 E :2 06

2:0 > A:2 5 B6

:0 A6Min = ; A :

0

> :2

&ínea de

isoutilidad

M-ltiples soluciones óptimas


47/109

M-ltiples soluciones óptimas


Ma = ; A :0 > 2 :2"ujeta a H :0 > B :2 2B

:0 A

Con :08 :2 5 6

&ínea de isoutilidad para02.66 /M sobre el

segmento AB

&ínea de isoutilidad para G.66 /M A

B

AB

6

430 :0

:2

&a solución óptima se compone de todas lascombinaciones de :

0

$ :2

a lo largo del

segmento AB

"olución de problemas deprogramación lineal usando


48/109

programación lineal usandocomputadora


&indo PC

Programa de computadora &I43O


49/109

g p%0'


Pantalla de ingreso de datos



50/109

g p%2'


Reporte de +ormulación



51/109

g p%A'


Reporte de solución

#nálisis de sensibilidad gráfco $


52/109

por computadora %0'

• &as soluciones óptimas 1an sido encontradas bajosuposiciones deterministas.

• (sto signifca que se supone una certe!a completaen los datos $ relaciones de un problema.

• Por ejemplo las utilidades unitarias son fjas8 lascantidades de recursos disponibles conocidas8 eltiempo necesario para producir 0 unidad es eacto8

Pero en el mundo real8 las condiciones sondinámicas $ cambiantes.


#nálisis de sensibilidad gráfco $d


53/109

por computadora %2'

• /na manera de reconciliar esta discrepanciaentre los supuestos deterministas $ lascondiciones dinámicas $ cambiantes delmundo real es determinar cuán sensible es la

solución óptima a los supuestos del modelo $los datos.

• (l análisis de sensibilidad permite

eperimentar con los valores de los datos deentrada.


7ormas para reali!ar el análisis deibilid d


54/109

sensibilidad

Ja$ dos métodos para determinar lasensibilidad de una solución óptima a loscambios.

• Método de ensa$o $ error.• #nálisis postoptimal.


Método de ensa$o $ error


55/109

Método de ensa$o $ error

(ste método resuelve todo el problema8 depre+erencia con una computadora8 cada ve! quecambia un dato de entrada o parámetro.

(sto puede tomar muc1o tiempo para probaruna serie de posibles cambios.


#nálisis postoptimal


56/109

#nálisis postoptimal

3espués que el problema de P& 1a sido resuelto8se intenta determinar un intervalo de cambiosen los parámetros que no a+ectan la soluciónóptima o cambian las variables en la solución.

(sto se reali!a sin resolver el problemanuevamente.


#nálisis de sensibilidad usando elé d áf


57/109

método gráfco


9ariación de los coefcientes de la+ ió bj i áf %0'


58/109

+unción objetivo gráfco %0'

"upónganse que los datos de las restriccionespermanecen invariables $ que solo se cambianlos coefcientes de la +unción objetivo.

(l cambio de los coefcientes de la +unciónobjetivo8 produce un cambio en la pendiente deesta.

(sto puede a+ectar o no a la solución óptima $ alvalor óptimo de la +unción objetivo.


9ariación de los coefcientes de la+ ió bj ti áf %2'


59/109

+unción objetivo gráfco %2'

Regla"i un coefciente de la +unción objetivo esaumentado %disminuido'8 la solución óptima nocambia8 pero el valor óptimo de la +unción

objetivo aumenta %disminu$e' en un valor iguala dic1a cantidad multiplicada por el valor de lavariable asociada a ese coefciente.


9ariación de los coefcientes de la+ ió bj ti áf %A'


60/109

+unción objetivo gráfco %A'


0.E C0 B

C0 ; B

= ; A0.2 > %B)2'QG.B ; BG

C0 ; 0.E

= ; A0.2 > %0.E)2'QG.B ; 2L

9ariación de los coefcientes de la+ ió bj ti áf %B'


61/109

+unción objetivo gráfco %B'


0.E C2 B

C2 ; 0.E

= ; A0.2 > %0.E)A'QB.G ; 2B

C2 ; B= ; A0.2 > %B)A'QB.G; AH

9ariación en los lados derec1os%0'


62/109

%0'

"in modifcar la +unción objetivo8 veamos a1oravariaciones en el lado derec1o de lasrestricciones.

/n cambio en el lado derec1o de una restricciónocasiona un movimiento paralelo de la restricciónmodifcada.

(sto puede a+ectar tanto a la solución óptimacomo al valor óptimo de la +unción objetivo.




63/109

%2'

• "i el lado derec1o de una restricción escambiado &a región +actible cambiará %a menos que la

restricción no sea parte de la región +actible' la solución óptima cambiará.

• (l valor del cambio en la +unción objetivo resulta de 0 unidad de cambio en el ladoderec1o de una restricción8 $ es llamadoprecio dual.


9ariación en los lados derec1os%A'


64/109

%A'

• (l precio dual indica el valor en que la +unciónobjetivo será modifcado como consecuenciade modifcar 0 unidad en el lado derec1o dela restricción asociada a dic1o precio dual.

• "in embargo8 el valor del cambio posible del

lado derec1o de una restricción es limitado.• "i el valor +uera cambiado más allá de loslímites permitidos8 entonces el valor de la+unción objetivo $a no se modifcaría por elprecio dual.

• Por ello8 el precio dual sólo es válido dentrode los límites permitidos.


9ariación en los lados derec1os gráfco %0'


65/109

gráfco %0'


H6 b0

0AE

b0 ; 0AE

= ; 2QA > AQ02; B2

b0 ; H6= ; 2Q02 > AQ6; 2B

9ariación en los lados derec1os gráfco %2'


66/109

gráfco %2'


precio dual ;)6.2B

P3 ; ) S= K Sb

P3 ; ) %A0.BB A0.2' K %0 6' ; )6.2B

9ariación en los lados derec1os gráfco %A'


67/109

gráfco %A'


AB.E b2

L2

b2 ; AB.E

= ; 2QA > AQL.E

; 2G.E b2 ; L2= ; 2Q0G > AQ6; AH

9ariación en los lados derec1os gráfco %B'


68/109

gráfco %B'


precio dual ;)6.26

P3 ; ) S= K Sb

P3 ; ) %A0.B A0.2' K %B BG'; )6.26

9ariación en los lados derec1os gráfco %E'


69/109

gráfco %E'


)T bA

B.2

bA ;)T

= ; )T

bA ; B.2= ; 2QG.B > AQB.G; A0.2

9ariación en los lados derec1os gráfco %H'


70/109

gráfco %H'


precio dual ;6.66

P3 ; S= K Sb

P3 ; %A0.2 A0.2' K %2.E 0.E'; 6.66

#dición o eliminación de restricciones


71/109

Ja$ una observación general que nos indica deinmediato el método gráfco. (sta se refere alos e+ectos de agregar o eliminar restricciones.9eamos algunos casos

• &a adición de restricciones a un modelo o bienempeora el valor óptimo de la +unción objetivoo lo deja inalterado.

• &a eliminación de restricciones de un modelo o

bien mejora el valor óptimo de la +unciónobjetivo o lo deja inalterado.


#nálisis de sensibilidad usando unprograma de computadora


72/109

programa de computadora


&indo PC



73/109


9ariación de los coefcientes de la+unción objetivo %0'


74/109

+unción objetivo %0'

• &I43O produce un reporte de sensibilidad.• (ste reporte muestra los incrementos $decrementos admisibles para los coefcientesde la +unción objetivo.

•"umando el incremento admisible% ALLOWABLE INCREASE' al valor actual%CURRENT COEF ' se obtiene el límite superior.

• Restando el decremento admisible% ALLOWABLE DECREASE' del valor actual%CURRENT COEF ' se obtiene el límite in+erior.


9ariación de los coefcientes de la+unción objetivo %2'


75/109


0.E C0 B

0.E C2 B

Reporte deanálisis desensibilidad

9ariación de los coefcientes de la+unción objetivo %A'


76/109

u c ó obje o %A'

"i la solución óptima es no degenerada8 podemosafrmar lo siguiente

UCuando un coefciente en particular esaumentado %disminuido' en una cantidadaceptable %es decir8 dentro del rango donde labase óptima no cambia'8 la solución óptima nocambia8 pero el valor óptimo de la +unción objetivoaumenta %disminu$e' en un valor igual a dic1a

cantidad multiplicada por el valor de la variableasociada a ese coefcienteV.



R t d


77/109

)T bA B.2Wprecio dual ;

6.663/29/16 Miguel Mejía Puente 77

H6 b0 0AEW

precio dual ;

)6.2BAB.E b2 L2W

precio dual ;)6.26

Reporte de

análisis desensibilidad



78/109

%2'•

&os valores del lado derec1o de lasrestricciones a menudo representan recursosdisponibles para la empresa.

• &os recursos podrían ser 1oras de mano deobra o tiempo de máquina o qui!ás dinero omateriales de producción disponibles.


9ariación en los lados derec1os%A'


79/109

%A'• "i el lado derec1o de una restricción es cambiado

&a región +actible cambiará %a menos que larestricción no sea parte de la región +actible' $ lasolución óptima cambiará.

• (l valor de cambio en la +unción objetivo que

resulta de 0 unidad de cambio en uno de losrecursos disponibles es llamado precio dual. (lprecio dual de una restricción es el mejoramientodel valor de la +unción objetivo que resulta del

incremento de 0 unidad en el lado derec1o de larestricción.


Precio dual Precio sombra %0'


80/109

(l precio dual de un recurso indica el valor enque la +unción objetivo será incrementada %odecrementada' debido a otra unidad delrecurso.

"in embargo8 el valor del incremento posible dellado derec1o de un recurso es limitado.


Precio dual Precio sombra %2'


81/109

"i el valor +uera incrementado más allá dellímite superior8 entonces la +unción objetivo $ano se incrementará por el precio dual.

"i +uera ecedido este n-mero límite delrecurso8 qui!ás cambie la +unción objetivo8 peropor un valor di+erente al precio dual.


Precio dual Precio sombra %A'


82/109

#sí8 el precio dual solo es relevante dentro de loslímites $ dentro de tales la epresión del preciosombra es

Precio sombra ; X= K Xb

3onde X= es la variación de la +unción objetivo $ Xb es la variación del lado derec1o dentro del

límite en donde la base óptima actual no cambia.


9ariación en el lado derec1o de unarestricción


83/109

• Caso 0.) 7unción objetivo demaimi!ación.

• Caso 2.) 7unción objetivo deminimi!ación.


Caso 0.) Maimi!ación&ado derec1o de una restricción

%0'


84/109

%0'"i la solución óptima es no degenerada $ la +unciónobjetivo es de maimi!ación8 podemos afrmar

UCuando el lado derec1o de una restricciónactiva del tipo ≤ es aumentado en una cantidadaceptable %dentro del rango'8 la base óptima no

cambia8 pero la solución óptima sí cambia8 $ elvalor óptimo de la +unción objetivo aumenta enun valor igual a dic1a cantidad multiplicada porel valor del precio dual asociado a esa

restricciónV.



%2'


85/109

%2'



%A'


86/109

%A'"i la solución óptima es no degenerada $ la +unciónobjetivo es de maimi!ación8 podemos afrmar

UCuando el lado derec1o de una restricción activadel tipo ≤ es disminuido en una cantidadaceptable %dentro del rango'8 la base óptima no

cambia8 pero la solución óptima sí cambia8 $ elvalor óptimo de la +unción objetivo disminu$e enun valor igual a dic1a cantidad multiplicada porel valor del precio dual asociado a esa

restricciónV.



87/109


%E'


88/109

%E'&a restricción :

0

G tiene

precio dual %preciosombra' igual a A.

&a restricción :2 06

tiene precio dual %preciosombra' igual a 6.

"e afrma que lasrestricciones del tipo ≤ siempre tienen preciosombra no ne ativo 3/29/16 Miguel Mejía Puente 88


5 %0'


89/109

5 %0'"i la solución óptima es no degenerada $ la +unciónobjetivo es de maimi!ación8 podemos afrmar

UCuando el lado derec1o de una restricción activadel tipo ≥ es aumentado en una cantidadaceptable %dentro del rango'8 la base óptima no


restricciónV.


Caso 0.) Maimi!ación&ado derec1o de una restricción5 %2'


90/109

5 %2'


Caso 0.) Maimi!ación&ado derec1o de una restricción5 %A'


91/109

5 %A'"i la solución óptima es no degenerada $ la +unciónobjetivo es de maimi!ación8 podemos afrmar

UCuando el lado derec1o de una restricción activadel tipo ≥ es disminuido en una cantidadaceptable %dentro del rango'8 la base óptima no


restricciónV.


Caso 0.) Maimi!ación&ado derec1o de una restricción5 %B'


92/109

5 %B'


Caso 0.) Maimi!ación&ado derec1o de una restricción5 %E'


93/109

5 %E'&a restricción E:

0 ) B:

2 5

)26 tiene precio dual%precio sombra' igual a 6.&a restricción :2 5 A tieneprecio dual %precio sombra'

igual a )E.&a restricción E:0 > B:2 526 tiene precio dual %preciosombra' igual a 6.

"e afrma que lasrestricciones del tipo ≥ siempre tienen preciosombra no ositivo


Caso 0.) Maimi!ación


94/109

4uevo valor óptimo de = ; #ntiguo valor óptimode = > %precio sombra de la restricción i'Q%Sbi'

3onde

*anto el precio sombra de la restricción i8 como

la variación del lado derec1o dado por Sbi debenreempla!arse con su signo respectivo.

#demás

Sbi Y 6 cuando aumenta el lado derec1o $ Sbi Z

6 cuando disminu$e el lado derec1o.


Caso 2.) Minimi!ación&ado derec1o de una restricción %0'


95/109

%0'"i la solución óptima es no degenerada $ la +unción

objetivo es de minimi!ación8 podemos afrmarCuando el lado derec1o de una restricción activa del tipo ≤ es aumentado en una cantidadaceptable %dentro del rango'8 la base óptima no


restricción.


Caso 2.) Minimi!ación&ado derec1o de una restricción %2'


96/109

%2'


Caso 2.) Minimi!ación&ado derec1o de una restricción %A'


97/109

%A'"i la solución óptima es no degenerada $ la +unción

objetivo es de minimi!ación8 podemos afrmarCuando el lado derec1o de una restricción activadel tipo ≤ es disminuido en una cantidadaceptable %dentro del rango'8 la base óptima no


restricción.


Caso 2.) Minimi!ación&ado derec1o de una restricción %B'


98/109

% '


Caso 2.) Minimi!ación&ado derec1o de una restricción %E'


99/109

% '&a restricción :0 G

tiene precio dual%precio sombra' igual a6.&a restricción :2 06

tiene precio dual%precio sombra' igual a2.H."e afrma que lasrestricciones del tipo ≤ siempre tienen preciosombra no ne ativo3/29/16 Miguel Mejía Puente 99

Caso 2.) Minimi!ación&ado derec1o de una restricción5 %0'


100/109

% '"i la solución óptima es no degenerada $ la +unción

objetivo es de minimi!ación8 podemos afrmarCuando el lado derec1o de una restricción activadel tipo ≥ es aumentada en una cantidadaceptable %dentro del rango'8 la base óptima no

cambia8 pero la solución óptima sí cambia8 $ elvalor óptimo de la +unción objetivo aumenta enun valor igual a dic1a cantidad multiplicada porel valor del precio dual asociado a esa restricción

cambiado de signo.


Caso 2.) Minimi!ación&ado derec1o de una restricción5 %2'


101/109

% '


Caso 2.) Minimi!ación&ado derec1o de una restricción5 %A'

"i l l ió ó i d d l + ió


102/109

"i la solución óptima es no degenerada $ la +unción

objetivo es de minimi!ación8 podemos afrmarCuando el lado derec1o de una restricción activadel tipo ≥ es disminuida en una cantidadaceptable %dentro del rango'8 la base óptima no

cambia8 pero la solución óptima sí cambia8 $ elvalor óptimo de la +unción objetivo disminu$e enun valor igual a dic1a cantidad multiplicada porel valor del precio dual asociado a esa restricción

cambiado de signo.


Caso 2.) Minimi!ación&ado derec1o de una restricción5 %B'


103/109


Caso 2.) Minimi!ación&ado derec1o de una restricción5 %E'

& t i ió E: B:


104/109

&a restricción E:0 ) B:2 5

)26 tiene precio dual%precio sombra' igual a)6.H.&a restricción :2 5 A tiene

precio dual %preciosombra' igual a 6.&a restricción E:0 > B:2 526 tiene precio dual

%precio sombra' igual a 6."e afrma que lasrestricciones del tipo ≥ siempre tienen precio3/29/16 Miguel Mejía Puente 104

Caso 2.) Minimi!ación

4 l ó ti d = # ti l ó ti


105/109

4uevo valor óptimo de = ; #ntiguo valor óptimo

de = ) %precio sombra de la restricción i'Q%Sbi'

3onde

*anto el precio sombra de la restricción i8 comola variación del lado derec1o dado por Sbi deben

reempla!arse con su signo respectivo.

#demás

Sbi Y 6 cuando aumenta el lado derec1o $ Sbi Z6 cuando disminu$e el lado derec1o.3/29/16 Miguel Mejía Puente 105

9ariación en los lados derec1os%2B'

"i la solución óptima es no degenerada


106/109

"i la solución óptima es no degenerada8

podemos afrmarCuando el lado derec1o de una restriccióninactiva es aumentado %disminuido' en unacantidad aceptable %dentro del rango'8 lasolución óptima no cambia.


Costo reducido

"i una solución óptima es no degenerada $


107/109

"i una solución óptima es no degenerada8 $

tiene una variable de decisión cu$o valor óptimoes cero8 podemos afrmar lo siguiente

U(l coefciente de esa variable en la +unción

objetivo debe ser cambiado por lo menos en elcosto reducido8 con el objeto de que 1a$a unasolución óptima en la que la variable apare!cacon un valor positivoV.


Costo reducido &I43O


108/109


(l costo reducido es elvalor en que debe serincrementado elcoefciente de la variable

no básica en la +unciónobjetivo para obtener unasolución óptimaalternativa.

&I43O


109/109

Modelos de programaciónlineal

7in del tema

02 modelos de programación lineal.pptx

Documents