Transcript
Universidad Autónoma de Tamaulipas Facultad de Ingeniería “Arturo Narro Siller” Investigación de Operaciones I
Program a ció ciónn Linea Lineall Introducción.
X 2
Mé t odo gr áf i co R 1
Mé t odo símpl ex R 2
X 1
R 3
Aplicaciones
Ing . Jo séGab riel Go n zález Tu rr u b iates
I ntro duc ción a la Prog P rog ramació ramación n Lineal
" Lo s qu e m andan genera ge neralmente lmente m ueve ueven n las m anos y dicen 'He 'H e co ns iderado to das las alternativa al ternativas'. s'. Pero Pe ro eso es c asi siemp re basura. Lo m ás pr ob able es q ue n o pu dies en estudiarr todas las estudia la s co m binaciones." binaciones. "
Georg e B. Dantzig Dantzig , el e l cr ea eado do r de la pro gr amación lineal, en un a entrevista pub licada en e n The College Colle ge Mathematical Jo ur nal, marzo d e 1986 19 86..
I ntro duc ción a la Prog P rog ramació ramación n Lineal
" Lo s qu e m andan genera ge neralmente lmente m ueve ueven n las m anos y dicen 'He 'H e co ns iderado to das las alternativa al ternativas'. s'. Pero Pe ro eso es c asi siemp re basura. Lo m ás pr ob able es q ue n o pu dies en estudiarr todas las estudia la s co m binaciones." binaciones. "
Georg e B. Dantzig Dantzig , el e l cr ea eado do r de la pro gr amación lineal, en un a entrevista pub licada en e n The College Colle ge Mathematical Jo ur nal, marzo d e 1986 19 86..
Reflexión Considere el problema de asignar 70 hombres a 70 empleos. Una “actividad” consiste en asignar el i -ésimo hombre al jésimo empleo. Las restricciones son dos: en primer lugar hay 70 hombres, cada uno de los cuales debe asignarse a un puesto, y en segundo lugar, cada uno de los 70 puestos existentes debe estar ocupado. El nivel de una actividad puede ser 1, lo cual indica que está siendo usada, o 0, lo cual significa que no. En consecuencia hay 2 x 70 = 140 restricciones y 70 x 70 = 4900 actividades con 4900 variables correspondientes de decisión uno-cero. Por desgracia también hay factorial de 70 permutaciones o formas de hacer las asignaciones. El problema consiste en comparar éste factorial de 70 formas y elegir la que sea la óptima o 'mejor' según algún criterio previamente establecido.
Intro duc ción a la PL Un a d e las té c n ic as m ás d if u n d id as d e la (IO) es la pr o g ram aci ón l in eal (PL ). El é x ito d e es táher ram ien ta s e d ebe al hecho de que es m uy flexible para describ ir un g ran núm ero de situ acion es r eales en áreas tales co m o: m ilitar, indu str ial, agr íc ol a, tr ans p or te, de la ec o n om ía, de s is tem as d e sal u d, e inclus o en las ciencias so ciales y d e la cond ucta. Un factor qu e ha ayudado a su amplio uso es la dispon ibilidad de prog ram as de com putado ra m uy eficientes para resolver prob lemas de grandes m agnitudes de PL . De hech o, la PL deber ía co ns id erars e com o u na b ase im po rtan te del d esarr ol lo d e otr as té cn ic as de la IO, inc lui das la pr og ram ación ent era, la esto cást ica, la de flu jo d e redes y la cu adrática. Desd e este pu nto de v ista, el co no cim iento de la PL es fu nd am ental p ara im pl emen tar est as té cn ic as adic ion ales. Por lo que resulta interesante saber que pro gramación lineal y que no lo es, a co ntinu ación se m encionan algunas definicion es.
Definicion es de PL “... trata la planeación de las actividades para obtener un
resultado óptim o, esto es, el resultado qu e mejor alcance la m eta esp ecif icad a (seg ún el m od elo m atem átic o) entre to das l as alternativas de solución.” Frederick S. Hiller
“... es un problema de minimizar o maximizar una función lineal
en la presencia de restricciones lineales del tipo dedesigualdad, igualdad o ambas.” Mok htar S. Bazaraa
Definicion es de PL A barc a los m é tod os de s olu ción d e un a gran variedad d e pr ob lemas d e la sig uiente naturaleza: se tiene algu na cantidad (tal com o u n c osto o un tiemp o) que tiene una fun ción lin eal de cierto núm ero d e variables lineales. Se requ iere, a su v ez, qu e estas v ariables satisfagan u n sistem a de igualdades y desigu aldades lineales. Es necesario hallar v alores n o negativos d e las v ariables qu e h ag an m áx im a o m ín im a a la can ti d ad d ad a.
A. S. Basarov
Definicion es de PL “... es una técnica matemática para encontrar los mejores usos
de la organización. El adjetivo lineal se usa para describir la relación en dos o más variables, una relación que es directa y precisamente proporcional. El término programación se refiere al uso de ciertas técnicas matemáticas para obtener la mejor solución posible a un problema que involucra recursos limitados.” Rich ad I. Levin
Supuestos y lim itacion es de la PL Proporcionalidad Supuestos
Aditividad Divisibilidad Determi nístico
Limitaciones
Estático No suboptimiza
Modelo g eneral de PL
Optimizar
Coeficientes objetivo
Variables de decisión
X 0 C 1 X 1 C 2 X 2 ...... C n X n Sujeto a:
Coeficientes tecnológicos
Coeficientes recur so
a11 X 1 a12 X 2 ..... a1n X n (, , )b1 a21 X 1 a22 X 2 ..... a2 n X n (, , )b2 .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
am1 X 1 am 2 X 2 ..... amn X n (, , )bm X 1,2,.....n > 0
Condi ciones té cnicas o No negatividad
Transformaciones al mo delo general de PL Dado que el objetivo fundamental de la PL es el de optimizar una f unción l ineal sujeta a una serie . de restr icciones lineales y variables no-negativas Dependiendo de la situación, resulta ventajoso efectuar ciertas mani pulaciones al modelo general para expr esarlo en formas equivalentes que sean más fáciles de compr ender, solucionar o anal izar. A continuación se presentan l as tr ansformaciones de mayor uti lidad.
Transformaciones al mo delo general de PL 1.- El objeti vo puede cambiarse de maximi zación a minimización y viceversa. L a minimización de una función f (x), es matemáti camente equivalente a la maximi zación del negativo de tal f unción, -f (x); complementariamente, la maximi zación una función g(x), es matemáticamente equivalente a la minimización del negativo de la misma, - g(x). Por ejemplo, M áx: X 0 = 8X 1 + 14X 2 - 5X 3 es matemáti camente equival ente a M ín: X´ 0 = - X 0 = -8X 1 -14X 2 +5X 3
Transformaciones al Transformaciones al mo delo general de PL PL
2.- El E l sen titido do de de u n a des desi gu gual aldad dad pu pueede i n ve verr titirr se. Cuando Cu ando una un a de desi gual gualda dadd se se mu mull titipl plii ca po porr ((-1), 1), su su sentido puede invertirse. Si es “ < " cambia a “ > " , Porr ej emp mpll o: si es “ > " cambia a “ < " . Po 2X 1 + 9X 2 - 4X 3 > 9
al mul mu l tipl tiplii car l a por (-1), se con convi vieer te en en -2X 1 - 9X 2 + 4X 3 < -9
Transformaciones al Transformaciones al mo delo general de PL PL 3.- Un U n a ecuaci ecuació ón pue puede de tr ans ansff or ormar marsse a des desi gual dade dadess. E sto se bas basaa en en el h ech cho o de que toda ecuaci ón pu pue ede r eempl az azar arsse por dos de dessi gu gual aldade dadess en sen ti dos opu opue estos. Porr ej emplo: Po 3X 1 + 5X 2 - 8X 3 = 10 es ma matt emát i cam came en te equ quii val vale en t e a las l as dos si gu guii en t es desigualdades 3X 1 + 5X 2 - 8X 3 < 10 3X 1 + 5X 2 - 8X 3 > 10
eloo genera generall de PL Transformaciones a l m od el 4.- Cuando se tiene una desigualdad “ < " , pue puede de tr ansf ansfor ormar marsse a una un a ecuaci ecuació ón , si si se l e su ma al l ado i zqui er do u na nue n ueva va va varr i able able,, n o-n o-ne ega gatitiva va,, ll amad amada a varii abl var ablee de f al altan tante te dado dado que qu e sol solame amen n te tomar ával valor ore es posii ti vos cuan pos cuando do el el l ado i zqui er do se sea men men or al l ado derr echo. Por ej empl de mplo: o: 9X 1 + 7X 2 - 3X 3 < 5 pue pu ede r eempl az azar arsse por 9X 1 + 7X 2 - 3X 3 + s 4 = 5 , s 4 > 0 E s pr prá ácti ctica ca común común con conssi de derr ar como cer cer o al coe coeff i ci cie en te objj etitivo ob vo de de l a var var i ab abll e de f al altant tante e.
Transformaciones al m od elo general de PL 5.- Una desigualdad “ > " puede cambiarse a ecuación, si se le resta al lado izquierdo una nueva variable no- negativa, llamada variable de sobrante; tal nombre obedece a que dicha variable tomaráun valor positi vo, sólo cuando el lado izquierdo sea mayor que el derecho. Por ejemplo, -5X 1 + 7X 2 - 2X 3 > 15 puede reordenarse como -5X1 + 7X2 - 2X3 - S4 = 15 , S4 > 0
Tambié n es usual asignar un valor de cero al coeficiente objeti vo de la variable de sobrante.
Transformaciones al m od elo general de PL 6.- Una variable irrestr icta en signo puede redefinirse en función de variables no-negativas. El modelo general de la PL presentado considera a todas las variables como no- negativas. En ciertos problemas se involucran variables irrestr ictas en signo, es decir que pueden tomar valores positi vos, negativos o cero; generalmente dichas variables están asociadas a temperaturas, saldos financieros, niveles de inventario, etc. Cuando en un problema se presenten variables irrestr ictas, tambié n llamadas variables libres, deben substi tuirse por la diferencia de dos variables no negativas. Por ejemplo, si la variable X 7 es irrestr icta, entonces puede reempl azarse por X 7 = X 7 + - X 7 -
,
X 7 + y X 7 - > 0
For m ato s Canónic o y Est ánd ar 1.- El formato Canóni co Un modelo de PL estáen f ormato canónico si todas las variables son no-negativas y todas las restr icciones son del tipo " < " para un objeto de maximización, o si todas las restr icciones son del tipo " > " para un objetivo de mini mización. Este formato es de gran utilidad en el análisis del modelo de PL . 2.- El formato Estándar Un modelo de PL estáen for mato estándar si todas las var iabl es son no-negativas y todas las restr icciones son i gual dades, tanto en maximización como minimización. Este for mato serásiempr e en la solución de problemas de PL . A conti nuación se presentan los modelos generales de PL planteados mediante los formatos canónicos y estándar.
Transformaciones al mo delo general de PL Formato Canónico Caso de minimización Minimizar
Caso de maximización Maximizar
n
n
X 0 C j X j
X 0 C j X j
j 1
j 1
Sujeto a:
Sujeto a: n
aij X j
n
bi
j 1
bi
j 1
X j
aij X j
j
0
,2,..., 1
X j
m
j
0
,2,..., 1
m
Transformaciones al mo delo general de PL Formato Estándar Caso de minimización Minimizar
Caso de maximización Maximizar
n
n
X 0 C j X j
X 0 C j X j
j 1
j 1
Sujeto a:
Sujeto a: n
aij X j
n
bi
j 1
bi
j 1
X j
aij X j
j
0
,2,..., 1
X j
m
j
0
,2,..., 1
m
Ap licacion es de los form atos Ejem plo 1 Formato Lib re
Máx . X 0 = 15X 1 + 28X 2 – 17X 3 Sujeto a: 2X 1 + 4X 2 – 3X 3 > 150
4X 1 + 2X 2 + 4X 3 = 220 5X 1 + 3X 2 + 2X 3 < 80 X 1, 2, 3 > 0
a) Cambie la func ión o bjetivo d el m od elo d e PL qu e estáen fo rm ato lib re (FL). b) Exprese el mod elo de PL que estáen fo rm ato l ib re (FL) a form ato can ónic o (FC). c) Exprese el m od elo de PL que estáen fo rm ato l ib re (FL) a form ato es tán d ar (FE).
Ap licacion es de los form atos a) Camb ie la fu nc ión ob jetivo del m od elo de PL q ue estáen fo rm ato lib re (FL). Transformación Máx . X 0 = 15X 1 + 28X 2 - 17X 3
Mín . - X 0 = -15X 1 - 28X 2 + 17X 3
Sujeto a: 2X 1 + 4X 2 – 3X 3 > 150
Máx. (-1) X 0 = 15X 1 + 28X 2 - 17X 3 (-1)
4X 1 + 2X 2 + 4X 3 = 220 5X 1 + 3X 2 + 2X 3 < 80 X 1, 2, 3 > 0
Mín . - X 0 = -15X 1 - 28X 2 + 17X 3
Ap licacion es de los form atos b) Expr ese el mo delo de PL q ue estáen fo rm ato lib re (FL) a form ato canónic o (FC). Transformación Form ato Canónico (-1) 2X 1 + 4X 2 – 3X 3 > 150 (-1) Máx . X 0 = 15X 1 + 28X 2 - 17X 3
- 2X 1 - 4X 2 + 3X 3 < - 150
Sujeto a: Transformación
- 2X 1 - 4X 2 + 3X 3 < - 150 4X 1 + 2X 2 + 4X 3 < 220 - 4X 1 - 2X 2 - 4X 3 < - 220 5X 1 + 3X 2 + 2X 3 < 80 X 1, 2, 3 > 0
4X 1 + 2X 2 + 4X 3 = 220 Sustituir por: 4X 1 + 2X 2 + 4X 3 < 220 4X 1 + 2X 2 + 4X 3 > 220 Se aplica la transform ación a la segund a desigualdad
(-1) 4X 1 + 2X 2 + 4X 3 > 220 (-1) 4X 2X 4X < - 220
Ap licacion es de los form atos c) Expr ese el mo delo de PL q ue estáen fo rm ato lib re (FL) a form ato es tán d ar (FE). Transformación Fo rm ato Es tán d ar 2X 1 + 4X 2 – 3X 3 > 150 Máx . 2X 1 + 4X 2 – 3X 3 - S 1 = 150 X 0 = 15X 1 + 28X 2 - 17X 3 Sujeto a:
Transformación
2X 1 + 4X 2 – 3X 3 - S 1
= 150
4X 1 + 2X 2 + 4X 3
= 220
5X 1 + 3X 2 + 2X 3
+ s 3 = 80
X 1, 2, 3 > 0 S 1 > 0 s 3 > 0
5X 1 + 3X 2 + 2X 3 < 80 5X 1 + 3X 2 + 2X 3
+ s 3 = 80
Ap licacion es de los form atos Ejem plo 2 Formato Lib re
Mín . X 0 = 21X 1 - 18X 2 + 28X 3 Sujeto a: - 2X 1 + 4X 2 + 3X 3 < 350
6X 1 + 4X 2 + 2X 3 > 220 5X 1 + 2X 2 + 3X 3 = 180 X 1, 2, 3 > 0
a) Cambie la func ión o bjetivo d el m od elo d e PL qu e estáen fo rm ato lib re (FL). b) Exprese el mod elo de PL que estáen fo rm ato l ib re (FL) a form ato can ónic o (FC). c) Exprese el m od elo de PL que estáen fo rm ato l ib re (FL) a form ato es tán d ar (FE).
Ap licacion es de los form atos a) Camb ie la fu nc ión ob jetivo del m od elo de PL q ue estáen fo rm ato lib re (FL). Transformación Mín . X 0 = 21X 1 - 18X 2 + 28X 3
Mín . X 0 = 21X 1 - 18X 2 + 28X 3 Sujeto a: - 2X 1 + 4X 2 + 3X 3 < 350
Mín . (-1) X 0 = 21X 1 - 18X 2 + 28X 3 (-1)
6X 1 + 4X 2 + 2X 3 > 220 5X 1 + 2X 2 + 3X 3 = 180 X 1, 2, 3 > 0
Máx. - X 0 = -21X 1 + 18X 2 - 28X 3
Ap licacion es de los form atos b) Expr ese el mo delo de PL q ue estáen fo rm ato lib re (FL) a form ato canónic o (FC). Transformación Form ato Canónico (-1) - 2X 1 + 4X 2 + 3X 3 < 350 (-1) Mín . X 0 = 21X 1 - 18X 2 + 28X 3
2X 1 - 4X 2 - 3X 3 > - 350
Sujeto a: Transformación
2X 1 - 4X 2 - 3X 3 > - 350 6X 1 + 4X 2 + 2X 3 > 220
5X 1 + 2X 2 + 3X 3 = 180 Sustituir por:
5X 1 + 2X 2 + 3X 3 > 180
5X 1 + 2X 2 + 3X 3 < 180
- 5X 1 - 2X 2 - 3X 3 > - 180
5X 1 + 2X 2 + 3X 3 > 180
X 1, 2, 3 > 0
Ap licar la transform ación segund a desigualdad
(-1) 4X 1 + 2X 2 + 4X 3 < 180 (-1) 4X 2X 4X > - 180
en la
Ap licacion es de los form atos c) Expr ese el mo delo de PL q ue estáen fo rm ato lib re (FL) a form ato es tán d ar (FE). Transformación Fo rm ato Es tán d ar - 2X 1 + 4X 2 + 3X 3 < 350 Máx . - 2X 1 + 4X 2 – 3X 3 + s 1 = 350 X 0 = 21X 1 - 18X 2 + 28X 3 Sujeto a:
Transformación
- 2X 1 + 4X 2 + 3X 3 + s 1
= 350
5X 1 + 3X 2 + 2X 3
- S 2 = 220
5X 1 + 2X 2 + 3X 3
= 180
X 1, 2, 3 > 0 s 1 > 0 S 2 > 0
6X 1 + 4X 2 + 2X 3 > 220 6X 1 + 4X 2 + 2X 3
- S 2 = 220
Ap lica licacion cion e s de los form a tos Ejem Eje m plo 3 Formato Lib re
M ín . X 0 = 11X 1 - 32X 2 + 42X 3 Sujeto a: 4 X 1 + 2 X 2 + X 3 = 190
4 X 1 + 2X 2 + 3 X 3 > 90 6 X 1 + 5 X 2 + 3 X 3 > 180 X 1,
3 >
0
X 2 = irrestric ta
a) Cambie la func ió iónn o bjetivo d el m od elo d e PL qu e estáen fo rm ato lib re (FL). b) Exprese E xprese el mod elo de PL que estáen fo rm ato l ib re (FL) a form ato can ónic o (FC). (FC). c) Exprese el el m od elo de PL que estáen fo rm ato l ib re (FL) a form ato es tán d ar (FE (FE). ).
Ap lica licacion cion e s de los form a tos Ejemplo 3
+ Sustituir X 2 = X 4 - X 5
Formato Libre
M ín .
M ín .
X 0 = 11X 1 - 32X 2 + 42X 3
- + 4 2 X X 0 = 11X 1 – 32(X 4 + - X 5 ) 3 - + 4 2 X X 0 = 11X 1 – 32(X 4 + - X 5 ) 3
Sujeto a: 4 X 1 + 2 X 2 + X 3 = 190
4X 1 + 2 X 2 + 3X 3 > 90 6 X 1 + 5 X 2 + 3 X 3 > 180 X 1,
3 >
0
X 2 = irrestricta
Sujeto a: 4 X 1 + 2 X X 4 + - - 2 2 X X 5 - + X 3 = 190 4 X 1 + 2 X X 4 + - 2 X X 5 - + 3 X 3 > 90 6 X 1 + 5 X X 4 + - 5 X X 5 - + 3 X 3 > 180
X 1,
3 >
0
X 4 + , X 5 - > 0
Ap lica licacion cion e s de los form a tos a) Camb ie la fu nc ión ob jetivo del m od elo de PL q ue estáen fo rm ato lib re (FL). (FL). Transformación M ín . X 0 = 11X 1 - 32X 4 + – 3 2 X 5 - + 28X 3
M ín . - + 4 2 X X 0 = 11X 1 – 32(X 4 + - X 5 ) 3
Sujeto a:
M ín . (-1) X 0 = 11X 1 - 32X 4 + - 32X 5 - + 28X 3 (-1)
4 X 1 + 2 X X 4 + - - 2 2 X X 5 - + X 3 = 190 4 X 1 + 2 X X 4 + - 2 X X 5 - + 3 X 3 > 90 6 X 1 + 5 X X 4 + - 5 X X 5 - + 3 X 3 > 180 X 1,
M áx . - X 0 = -11X 1 + 32X 4 + + 32X 5 - - 28X 3
3 >
0
X 4 + , X 5 - > 0
Ap licacion es de los form atos b) Expr ese el mo delo de PL q ue estáen fo rm ato lib re (FL) a form ato canónic o (FC). Transformación Form ato Canónico 4X 1 + 2X 4 + - 2X 5 - + X 3 = 190 Mín . Sustituir por: X 0 = 11X 1 + 32X 4 + - 32x 5 - + 28X 3 4X 1 + 2X 4 + - 2X 5 - + X 3 < 190 Sujeto a: 4X 1 + 2X 4 + - 2X 5 - + X 3 > 190 - 4X 1 - 2X 4 + + 2X 5 - - X 3 > - 190 Ap licar la transfo rm ación en la + - 4X 1 + 2X 4 + 2X 5 +X 3 > 190 prim era desigu aldad 4X 1 + 2X 4 + - 2X 5 - + 3X 3 >
90
- 6X 1 - 5X 4 + + 5X 5 - - 3X 3 > - 180 X 1, 2, 3 > 0
(-1) 4X 1 + 2X 4 + - 2X 5 - + X 3 < 190
(-1)
- 4X 1 - 2X 4 + + 2X 5 - - X 3 > - 190 Transformación (-1) 6X 1 + 5X 4 + - 5X 5 - + 3X 3 < 180 (-1)
- 6X 1 - 5X 4 + + 5X 5 - - 3X 3 > - 180
Ap licacion es de los form atos c) Expr ese el mo delo de PL q ue estáen fo rm ato lib re (FL) a form ato es tán d ar (FE). Transformación Fo rm ato Es tán d ar - 2X 1 + 4X 2 + 3X 3 < 350 Mín . - 2X 1 + 4X 2 – 3X 3 + s 1 = 350 + - X 0 = 11X 1 + 32X 4 - 32x 5 + 28X 3 Sujeto a:
Transformación
4X 1 + 2X 4 + - 2X 5 - + X 3
= 190
4X 1 + 2X 4 + - 2X 5 - + 3X 3 - S 2 6X 1 + 5X 4 + - 5X 5 - + 3X 3 X 1, 2, 3 > 0 s 3 > 0 S 2 > 0
= 90
+ s 3 = 180
6X 1 + 4X 2 + 2X 3 > 220 6X 1 + 4X 2 + 2X 3
- S 2 = 220
Mé to d o s d e s o lu c ión
Símplex
Dos fases
Algebraico
M grande
Programación lineal Gráfico Símplex revisado Karmarkar
Dual Símplex
Construc ción d e m od elos de PL Ejemplo 1. Una planta puede fabricar cualqui er combinación de cinco productos diferentes. L a fabricación de cada producto requiere cierto ti empo en tr es máquinas diferentes, como se indica en la siguiente tabl a. Todas las cifras están expresadas en minutos por libra de producto.
PRODUCTO A B C D E
TIEMPO-MÁQUINA (min/lb) 1 2 3 12 8 5 7 9 10 8 4 7 10 3 7 11 2
Cada máquina estádisponible durante 128 horas por semana. Los productos A, B, C, D y E son muy competi tivos y pueden venderse cualquier canti dad que se produzca a precios por libra de $5, $4, $5, $4 y $4, respecti vamente. L os costos variables de mano de obra son $4 por hora para las máquinas 1 y 2 y $3 por hora en la máquina 3. L os costos de material son $2 por cada libra de los productos A y C, y $1 por cada li bra de los productos B, D y E. L o que se desea es maximizar las ganancias de la compañ ía. F ormule el modelo de programación lineal correspondiente.
Utili dad = PV-[(CM )+(CVM Om )+(CVM Om )+(CVM Om )] 1 2 3 Donde: PV = Pr ecio de venta CM = Costo del material. CVMOm quina 1. 1 = Costo var iable de mano de obra en la má CVMOm quina 2. 2 = Costo var iable de mano de obra en la má 3. CVMOm quina 3 = Costo var iable de mano de obra en la má Cálculo de costos variables de mano de obra en la máquina 1 . Producto A. 1 hora = $4
Producto B. 1 hora = $4
Producto C. 1 hora = $4
60 minutos = $4
60 minutos = $4
60 minutos = $4
= 12 minutos = X X = $ 0.80/lb
=
7 minutos = X X = $ 0.47/lb
=
8 minutos = X X = $ 0.53/lb
Solución: Resumen de inf ormación relevante: Producto A
B
C
D
E
Precio venta ($/lb)
$
5.00
$
4.00
$
5.00
$
4.00
$
4.00
Costo de Material ($/lb)
$
2.00
$
1.00
$
2.00
$
1.00
$
1.00
Costo variable M.O ($/lb) Maq.1
$
0.80
$
0.47
$
0.53
$
0.67
$
0.47
Costo variable M.O ($/lb) Maq.2
$
0.53
$
0.60
$
0.27
$
$
0.73
Costo variable M.O ($/lb) Maq.3
$
0.25
$
0.50
$
0.35
$
0.15
$
0.10
Utilidad ($/lb)
$
1.42
$
1.43
$
1.85
$
2.18
$
1.70
-
Resumen de inf ormación relevante: Máquinas
Tiempo máquina minutos por libra por producto
1
12
7
8
2
8
9
4
3
5
10
7
10
3
Minutos disponibles por semana
7
7680
11
7680
2
7680
Formulación: Variable de decisión: X i = L ibras del producto i a fabricar por semana. i = 1, 2, 3, 4 y 5 Objetivo: X 0 = Utilidad /semana Restricciones:
M áquina 1
Tiempo disponi ble por semana
M áquina 2 M áquina 3
Condi ci ones té cnicas. X 1 , X 2 , X 3 , X 4 , X 5 > 0
M odelo M atemáti co de Programación L ineal : M áx: Utilidad X 0 = 1.42 X 1 + 1.43 X 2 + 1.85 X 3 + 2.18 X 4 + 1.70 X 5 $
=
Semana
$
Libras
Libra
Semana
Suj eto a: minutos
Libras
Libra
Semana
=
minutos Semana
12X 1 + 7X 2 + 8X 3 + 10X 4 + 7X 5 < 7680 Máquina 1 8X 1 + 9X 2 + 4X 3
+ 11X 5 < 7680 Máquina 2
5X 1 + 10X 2 + 7X 3 + 3X 4 + 2X 5 < 7680 Máquina 3 X 1 , X 2 , X 3 , X 4 , X 5 > 0
Constr ucción de modelos de PL Ejemplo 2. La Compañía Par es un pequeño fabricante de equipo y suministros para golf. El distribuidor de Par cree que existe un mercado tanto para una bolsa de golf de precio moderado, denominada modelo estándar, como para una bolsa de precio elevado, denominada modelo de lujo. El distribuidor está tan confiado en el que, si Par puede hacer las bolsas a un precio competitivo, el distribuidor comprará todas las bolsas que Par pueda fabricar durante los siguientes tres meses. Un análisis cuidadoso de los requerimientos de tiempo de producción para las cuatro operaciones de manufactura y la estimación hecha por el departamento de contabilidad de la contribución a la ganancia por bolsa. Tiempo de producción (horas/bolsa) Producto
Corte y teñido
Estándar
7/10
1/2
1
1/10
$ 10
1
5/6
2/3
1/4
$ 9
De lujo
Costura
Terminado
Inspección y empaque
Ganancia por bolsa
El director de manufactura estima que dispondrán de 630 horas de tiempo de corte y teñido, 600 horas de tiempo de costura, 708 horas de tiempo de terminado y 135 horas de tiempo de inspección y empaque para la producción de bolsas de golf durante los siguientes tres meses. a) Si la compañía desea maximizar la contribución a la ganancia total, ¿Cuántas bolsas de cada modelo debería fabricar? b) ¿Cuántas horas de tiempo de producción se programaran para cada operación? c) ¿Cuántas horas de tiempo de ocio se tendrán en cada operación?
Formulación: Variable de decisión: X i = Número de bolsas de modelo i a f abricar por tr imestr e i = 1, 2 Objetivo: X 0 = Ganancia/tr imestre Restricciones: Tiempo disponible por tr imestr e Condi ci ones té cnicas. X 1 , X 2 > 0
Cor te y teñ ido Corte Terminado I nspección y empaque
M odelo M atemáti co de Programación L ineal : M áx: Ganancia X 0 = 1.42 X 1 + 1.43 X 2 $
=
Trimestre
$
Bolsa
Bolsa
Trimestre
Suj eto a: Hora
Bolsas
Bolsa
Semana
7/10X 1 +
=
Horas Semana
X 2 < 630 Corte y teñido
1/2X 1 + 5/6X 2 < 600 Costura X 1 + 2/3X 2 < 708 Terminado 1/10X 1 + 1/4X 2 < 135 Inspección y empaque X 1 , X 2 > 0
Constr ucción de modelos de PL Ejemplo 3. Tom’s produce varios productos alimenticios mexicanos y los vende a
Western F oods, cadena de ti endas de abarrotes localizada en Texas y Nuevo México. Tom’s fabrica dos salsa: Western Foods Salsa y México
City Salsa. Esencialmente, ambos productos son mezclas de tomates enteros, 30% de salsa de tomate y 20% de pasta de tomate. L a M é xico Ci ty Salsa, ti ene una consistencia más espesa y tr oceda. Cada tarr o de salsa producida pesa 10 onzas. Par a el período de producción actual, Tom’s puede adquirir hasta 280 libras de tomates enteros, 130 libras de
salsa de tomate y 100 libras de pasta de tomate; el precio por libra de estos ingredientes es de $0.96, $0.64 y $0.56, respecti vamente. El costo de las especias y de los demás ingr edientes es de apr oximadamente $0.10 por recipiente. Tom’s compra tarros de vidrio vacíos a $0.02 cada
uno, y los costos de etiquetado y llenado se estiman en $0.03 por cada tarro de salsa producido. El contrato de Tom’s con Western Foods
resulta en ingresos por ventas de $1.64 por cada tarro de Western F oods Salsa y de $1.93 por cada tar ro de M é xico Ci ty Salsa.
Solución: Resumen de inf ormación relevante: Onzas/recipiente Tomates enteros
Salsa de tomate
Pasta de tomate
Wastern Foods Salsa
5
3
2
Mexico City Salsa
5
3
2
280
130
100
Costo por libra
$ 0.96
$ 0.64
$
0.56
Costo por onza ocupada
$ 0.30
$ 0.12
$
0.07
Salsa
Disponibilidad Mat. Prima (lb)
Resumen de información relevante:
Salsa
costo especias ($/recip)
Costo de tarros vacíos
Etiquetad o ($/recip)
Precio venta($/recip)
Wastern Foods Salsa
$
0.10
$
0.02
$
0.03
$
1.64
$
1.00
Mexico City Salsa
$
0.10
$
0.02
$
0.03
$
1.93
$
1.29
Utilidad
Utilidad = PV-[(CM Pte)+(CM Pst)+(CM Ppt)+(Ce)+(Ct)+(Cet)] Donde: PV = Precio de venta CM Pte = Costo de la materia prima (tomates enteros) CM Pst = Costo de la materia prima (salsa de tomate) CM Ppt = Costo de la materia prima (pasta de tomate) Ce = Costo de las especias Ct = Costo del tarro Cet = Costo del etiquetado.
Formulación: Variable de decisión: X 1 = Número de recipientes a producir de Western F oods Salsa por periodo. X 2 = Número de recipientes a pr oducir M é xico City Salsa por periodo
Objetivo: X 0 = U tili dad /periodo
Restricciones: M ateria Prima
Tomates enteros Salsa de tomate Pasta de Tomate
Condi ci ones té cnicas. X 1 , X 2 > 0
M odelo M atemáti co de Programación L ineal : M áx: Utilidad X 0 = X 1 + 1.29X 2 $ Periodo
$
Recipiente
Recipiente
Periodo
=
Suj eto a: onzas
recipiente
recipiente
periodo
=
onzas periodo
5X 1 + 5X 2 < 4480 Tomates enteros 3X 1 + 3X 2 < 2080 Salsa de tomate 2X 1 + 2X 2 < 1600 Pasta de tomate X 1 , X 2 > 0
Constr ucción de modelos de PL Ejemplo 3.
Hexxon Oil Company tiene seis consultores de petróleo, tres de los cuales están actualmente en los E. U., dos en Rusia y uno en Nigeria. Arabia Saudita ha solicitado dos consultores durante una semana a una tarifa de $4200 cada uno. Venezuela ha solicitado dos consultores durante una semana a una tarifa de $4000 cada uno. Indonesia ha solicitado tres consultores tres consultores durante una semana a una tarifa semanal de $4000 cada uno. Los gastos semanales por consultor son de $1400 en Arabia Saudita, $1000 en Venezuela y $700 en Indonesia. La tabla siguiente muestra las tarifas de viaje redondo (en dólares) para enviar por avión a los consultores:
Desde Estados Unidos Rusia Nigeria
Hacia Arabia Saudita
Venezuela
Indonesia
1800 1600 1300
800 1800 1200
2000 1700 1500
¿C óm o asig n aría lo s c o n su lto res p ara o b ten er la m ejo r g an an cia?
Form ule un mo delo de Prog ramación Lineal
Solución: Resum en de inform ación Cantidad de consultores ofertados
País origen
3
E. U.
Viaje redondo en avión
$1,800 $ 800
País destino
Cantidad de consultores demandados
Tarifa
A. S.
2
$4,200
$1,400
V.
2
$4,000
$1,000
I.
3
$4,000
$ 700
Gastos semanales
$2,000 $1,600 2
$1,800
R.
$1,700 $1,300 1
N.
$1,200
$1,500
6
7
Oferta
Demanda
Formulación: Variable de decisión: X ij = Número de consul tores en el país i enviados al país j. i = 1, 2 y 3 y j = 1, 2 y 3 (EU, R y N) (AS, V e I )
Objetivo: X 0 = Utili dad Uti li dad = Tarifa – (Gastos + Vi aje redondo en avi ón)
Restricciones: Oferta
Estados Uni dos Rusia Nigeria
Condi ci ones té cnicas. X ij > 0
i = 1, 2, 3
j = 1, 2, 3
Demanda
Ar abia Saudita Venezuela Indonesia
M odelo matemáti co de PL : U11 = 4200 – (1400 + 1800)
Maximizar utilidad
X 0 = 1000X 11 + 2200X 12 + 1300X 13 + 1200X 21 + 1200X 22 + 1600X 23 + 1500X 31 + 1800X 32 + 1800X 33
U12 = 4000 – (1000 + 800) U13 = 4000 – (700 + 2000)
Suj eto a: X 11 + X 12 + X 13
=3
Cons ultores en EU
=2
Consu ltores en R.
X 31 + X 32 + X 33 = 1
Consu ltores en N.
X 21 + X 22 + X 23
X 11
+ X 21 X 12
+ X 31 + X 22
X 13
+ X 32
+ X 23
X ij > 0
<2
Cons ultores a enviar AS
<2
Cons ultores a enviar V
+ X 33 < 3 i = 1, 2, 3 j
1, 2, 3
Cons ulto res a env iar I
Constr ucción de modelos de PL Ejemplo 4. El gru po ind us trial A ntar, S. A ., analiza la po sib ilidad d e orientar su in versión hacia otros s ectores en dond e se encuentra operando actu almente. El presupu esto disp onib le para inv ersio nes de esta natu raleza se h a fijado en 100,000,000 de pesos. Tom and o en cu enta las áreas d e inv ersi ón actu ales, el director de finanzas ha recom endado qu e las nuevas inversion es se realic en en la in du st ria petr ol era y s ider úrg ic a, asíco m o en Cert ifi c ado s d e la Teso rer ía Gener al del Es tad o (CETES). Especialmente, ha identificado siete opor tunid ades de inv ersión, asíco m o las tasas de rend im iento esperadas de las m ism as. Esta inform ación se expon e a co ntinu ación.
Opc iones de inversión
Tasa de rendim iento (%)
Petróleo y deriv ado s, S. A . Indu stria Petro lera, S. A . Petróleos del No rte, S. A. Ac eros Mon clov a, S. A Sid erúrg ic a Nacio nal, S. A . Hierro y A cero, S. A. CETES
25 33 20 35 23 27 30
El con sejo de admin istración a imp uesto, por s u p arte, la sigu iente estrategia de inversión:
No s e debe des tin ar m ás d el 50% d el tot al de la inv ersi ón a una indu stria en p articular. La inv ersión CETES debe equiv aler po r lo m enos al 25% del total inv ertido en sid erúrg ica. La inv ersión en Indu str ia Petro lera, S. A ., la cu al resulta ser la de may or rend im ient o, aun qu e tamb ié n d e may or ries go , no puede exceder al 50% d el total a inv ertir en el sector petrolero. El total a invertir en s iderúrgic a debe ser p or lo m enos igual al invertid o en p etróleo. ¿Q u érec o m en d ac io n es (c an tid ad y o p c io n es d e in v ers ión ) pueden hacerse con resp ecto a este portafolio?
Solución: Variable de decisión: X 1 = Cantidad ($) a invertir X 2 = Cantidad ($) a invertir X 3 = Cantidad ($) a invertir X 4 = Cantidad ($) a invertir X 5 = Cantidad ($) a invertir X 6 = Cantidad ($) a invertir X 7 = Canti dad ($) a invertir
en Petróleo y Derivados, S. A. en I ndustri a Petrolera, S. A. en Petróleos del Norte, S. A. en Aceros de M onclova, S. A. en Siderúrgica Nacional, S. A. en H ierro y Acero, S. A. en CETE S, S. A.
Objetivo: X 0 = Tasa de rendimiento total
Restricciones:
Presupuestal. M áxi ma inversión por industr ial Administrativas
M ínima inversión en CETES M áxi ma inversión en I ndustr ia Petr olera, S. A. I nversiones en i ndustr ia siderúrgica y petr olera.
Condi ci ones té cnicas. X i > 0
i = 1, 2, 3, 4, 5, 6, 7
M odelo matemáti co de PL : Maximizar X 0 = 0.25X 1 + 0.33X 2 + 0.20X 3 + 0.35X 4 + 0.23X 5 + 0.27X 6 + 0.30X 7 Sujeto a:
X 1 + X 2 + X 3 + X 4 + X 5 + X 6 + X 7 < 100,000,000
Presupuesto
Máxim a in versión po r in du stria. X 1 + X 2 + X 3 X 4 + X 5 + X 6
< 50,000,000
Petrolera
< 50,000,000
Siderúrgica
Mín im a in v ers ión en C ETES X 7 < 0 .25(X 4 + X 5 + X 6 ) - 0.25X 4 - 0.25X 5 - 0.25X 6 + X 7 < 0
Máxim a inv ersión en Ind us tria Petro lera X 2 < 0 .50(X 1 + X 2 + X 3 ) - 0.50X 1 + 0.50X 2 - 0.50X 3
<0
Inv ersiones en in du stria petrolera y siderúrgic a X 1 + X 2 + X 3 < X 4 + X 5 + X 6
X 1 + X 2 + X 3 - X 4 - X 5 - X 6 < 0
Condi ci ones té cnicas. X i > 0
i = 1, 2, 3, 4, 5, 6, 7
Resumen del modelo: Maximizar X 0 = 0.25X 1 + 0.33X 2 + 0.20X 3 + 0.35X 4 + 0.23X 5 + 0.27X 6 + 0.30X 7 Sujeto a:
X 1 + X 2 + X 3 + X 4 + X 5 + X 6 + X 7 < 100,000,000
Presupuesto
X 1 + X 2 + X 3
< 50,000,000
Petrolera
< 50,000,000
Siderúrgica
X 4 + X 5 + X 6
- 0.25X 4 - 0.25X 5 - 0.25X 6 + X 7 < 0 - 0.50X 1 + 0.50X 2 - 0.50X 3
<0
X 1 + X 2 + X 3 - X 4 - X 5 - X 6
<0
X i > 0
i = 1, 2, 3, 4, 5, 6, 7
Mín im a in v ers ión en CETES Máxi m a inv ersión en Ind us tria Petrolera Inv ersiones en ind us tria petro lera y sid erúrgic a
Constr ucción de modelos de PL Ejemplo 5. La princ ipal sucu rsal de un Banc o requiere de 8 a 15 cajeros d e serv icio , dependiend o de la h or a del d ía, co m o se in dic a en la tabla 1. Los cajeros de tiem po com pleto trabajan 8 horas con secutiv as a $15 la hora, com enzando con a las 8 A. M. Los cajeros de tiempo parcial trabajan 4 ho ras co ns ecutivas a $8 la ho ra, co m enzan d o a l as 8 A . M., 10 A . M. o 12 del m edi o d ía. Las regulaciones sin dicales requieren que a toda ho ra al m enos 60% de los cajeros sean de tiem po c om pleto. Com o g erente del person al, haga un a recom endación r especto al núm ero de empleados de tiem po c om pleto y de tiempo p arcial requeridos a lo lar go del d ía para m inim izar el cos to di ario t ot al.
Requ erimientos d e cajeros del Banco .
Periodo 8 – 10 10 – 12 12 – 2 2 – 4
A .M. Med io d ía P.M. P.M.
Núm ero m ín im o d e caj ero s 8 10 15 12
Construir el mo delo d e PL correspondiente
Solución: Variables de decisión: X 1 = Número de cajeros de ti empo completo a contr atar por día. Y a. i = Número de cajeros de tiempo parcial i a contratar por dí i = 1, 2, 3. ( hora de entr ada 8, 10 y 12 del mediodía)
Objetivo: X 0 = Costo total diario C t = Salario cajeros TC + salario cajeros TP
Restricciones: 8 – 10 am Requerimientos por periodo
10 -12 del mediodía 12 – 2 pm 2 – 4 pm
8 – 10 am Políti ca sindical para tur no completo
10 -12 del mediodía 12 – 2 pm 2 – 4 pm
Condi ci ones té cnicas. X 1 > 0 Y i > 0
Enteras i = 1, 2, 3
M odelo matemáti co de PL : Minimizar X 0 = 120X 1 + 32Y 1 + 32Y 2 + 32Y 3 $
$
cajeros
cajero
día
=
día
Sujeto a:
Requerimiento de cajeros p or p eriodo X 1 + Y 1
Period o de 8 – 10 a.m.
=8
cajeros
cajeros
día TC
día TP
=
cajeros día
X 1 + Y 1 + Y 2
= 10
Period o de 10 – 12 d el m ed io d ía
X 1
+ Y 2 + Y 3
= 15
Period o de 12 – 2 p.m .
X 1
+ Y 3
= 12
Period o de 12 – 2 p.m .
Políti ca sindical par a turno completo Y sabemos que una prop orción es X 1 + Y 1
X 1
=
1
P(x) =
X 1
X 1 + X 2 + . . . + X n
> 0.60
X 1 + Y 1 X 1
) > 0.60 (X 1 + Y 1
X 1
> 0.60X 1 + 0.60Y 1
X 1 - 0.60X 1 - 0.60Y 1
>
0
0.40X 1 - 0.60Y 1
>
0
Period o d e 8 – 10 a.m.
0.4X 1 - 0.60Y 1 - 0.60Y 2
>0
Period o de 10 – 12 d el m ed io d ía
0.4X 1
- 0.60Y 2 - 0.60Y 3 > 0
Period o de 12 – 2 p.m.
0.4X 1
- 0.60Y 3 > 0
Period o de 12 – 2 p.m.
X 1 > 0 Y i > 0
Enteras i = 1, 2, 3
Resumen del modelo: Minimizar X 0 = 120X 1 + 32Y 1 + 32Y 2 + 32Y 3
Sujeto a: X 1 + Y 1
= 8
Period o de 8 – 10 a.m .
X 1 + Y 1 + Y 2
= 10
Period o de 10 – 12 d el m ed io d ía
X 1
+ Y 2 + Y 3
= 15
Period o de 12 – 2 p.m .
X 1
+ Y 3
= 12
Period o de 12 – 2 p.m .
0.40X 1 - 0.60Y 1
> 0
Period o d e 8 – 10 a.m.
0.4X 1 - 0.60Y 1 - 0.60Y 2
> 0
Period o de 10 – 12 d el m ed io d ía
0.4X 1
- 0.60Y 2 - 0.60Y 3 > 0
Period o de 12 – 2 p.m.
0.4X 1
- 0.60Y 3 > 0
Period o de 12 – 2 p.m.
X 1 > 0 Y i > 0
i = 1, 2, 3
Enteras
Universidad Autónoma de Tamaulipas Facultad de Ingeniería “Arturo Narro Siller” Investigación de Operaciones I
Mé to d o Gráfic o Solución óptima única
X 2
Solución óptima múlti ple
R 1
R 2
R 3
X 1
Solución ilimitada Solución inf actible
Ing . J os éGab riel Go n zález Tu rru b iates
Ejem plo 1 Burro ughs Garment Com pany fabrica camisas p ara caballero y blus as para dam a para Walm ark Disco unt Stor es. Walm ark aceptarátod a la pr od uc ción qu e le prop or cio ne Bu rro ug hs . El proceso de produ cción incluye corte, costu ra y emp acado. Bu rrou ghs emplea a 25 trabajado res en el departamento d e co rte, a 35 en el departamento de co stu ra y a 5 en el departam ento de emp acado. La fabrica trabaja un tu rno de 8 ho ras, sólo 5 d ías a la sem ana. La tab la sig uien te pro po rc io na los requerim ientos de tiem po y las utilidades po r unid ad para las dos p rendas: Prenda Camisas Blusas
Corte 20 60
Minutos por unidad Costura Empacado 70 12 60 4
1.- Constru ir el mo delo de PL. 2.- So lu ci o n ar el m o del o c on el m é to do g ráfic o
Utilidad por unidad ($) 2.50 3.20
Solución: Variables de decisión: X 1 = N úmero de camisas a fabricar por semana. X 2 = Número de blusas a fabricar por semana.
Objetivo: X 0 = Utilidad por semana
Restricciones: Departamento corte Tiempo disponible por departamento a la semana
Departamento costura Departamento empaque
Condi ci ones té cnicas. X 1, X 2 > 0
M odelo matemáti co de PL : Maximizar X 0 = 2.50X 1 + 3.20X 2 $
=
semana
$
camisas
camisa
semana
+
$
blusas
blusas
semana
Sujeto a: Cálcu lo d el tiem po d isp on ible po r sem ana 25 obreros
35 obreros
5 obreros
8
8
8
horas día-obrero horas día-obrero horas día-obrero
5
5
5
días semana días semana días semana
= 1000 = 1400 = 200
horas semana horas semana horas semana
Departamento corte Departamento costura Departamento empaque
20X 1 + 60X 2 < (1000)(60) minutos
camisas
camisa
semana
+
Departam ento co rte
minutos
blusas
blusas
semana
=
horas
minutos
semana
hora
70X 1 + 60X 2 < (1400)(60)
Departamento cos tura
12X 1 + 4X 2 < (200)(60)
Departamento emp aque
X 1, X 2 > 0
Resumen del modelo: Maximizar X 0 = 2.50X 1 + 3.20X 2 Sujeto a: 20X 1 + 60X 2 < 60,000
Departament o co rte
70X 1 + 60X 2 < 84,000
Departamento cos tura
12X 1 + 4X 2 < 12,000
Departamento emp aque
X 1, X 2 > 0
Mé todo Gráfico: Paso 1. Representar las v ariables de decis ión en un eje co o rd enad o X Y. (Co n d ic io nes té c ni c as) X 2
Blusas
X 1 Camisas
Mé todo Gráfico: Paso 2. Calcu lar las c oor denadas de intersección los ejes para cada restricc ión y representarlas en el prim er cu adrante. Intersección co n los ejes (X 1 , X ) 2 20X 1 + 60X 2 < 60,000 70X 1 + 60X 2 < 84,000
Blusas
12X 1 + 4X 2 < 12,000
(X 1 , X ) 2
(0, 1000)
(3000, 0)
(0, 1400)
(1200, 0)
(0, 3000)
(1000, 0)
3000
(-1)
20 X 1 + 60X 2 < 60,000 (-1) 70 X 1 + 60X 2 < 84,000 50 X 1
2000
< 24,000 X 1 = 480
Sustitu ir X1 en la Restric ción 1 1000 B
Región Factible
C
20(480) + 60X 2 < 60,000 X 2 = 840 D
A 1000
2000
3000
Camisas
Mé todo Gráfico: Paso 3. Calc ular las altern ativ as d e s olu ción (cada v é rti ce d e la región factib le) Alternativas
A
B
C
D
Utilidad X0 =
0
$3,200
$3,888
$2,500
Camisas X1 =
0
0
480
1,000
Blusas X2 =
0
1,000
840
0
Esta es la solu ción óptim a
Mé todo Gráfico: Paso 4. Calcular las variables de holg ur a para cada restric ción de la so luc ión óptim a. Primero se transform an a igualdades todas las restricciones. 20 X 1 + 60X 2 + s 1
= 60,000
70 X 1 + 60X 2
= 84,000
+ s 2
12 X 1 + 4X 2
+ s 3
= 12,000
Segun do s e sustituyen lo s valores obtenidos para X1 y X2 de la solución óp tim a y s e d es p eja la v ariab le d e h o lg u ra d e c ad a res tric c ión . 20 X 1 + 60X 2 + s 1
= 60,000
20(480) + 60(840) + s 1 = 60,000 9600 + 50400 + s 1 = 60,000 60000 + s 1 = 60,000 s 1 = 0
Departam ento corte
70 X 1 + 60X 2 + s 2
= 84,000
Departamento cos tura
70(480) + 60(840) + s 2 = 84,000 33,600 + 50,400 + s 2 = 84,000 84,000 + s 2 = 84,000 s 2 = 0
12 X 1 + 4X 2 + s 3
= 12,000
12(480) + 4(840) + s 3
= 12,000
5,760 + 3,360 + s 3 = 12,000 9,120 + s 3 = 12,000 s 3 = 2,880
Departamento emp aque
Interpretación d e los resultados del m odelo.
Bu rrou gh s Garm ent Com pany, deberáfabric ar 480 camis as y 840 blus as, con este plan d e pro du cción lo graráob tener una u tilidad d e $3,888 po r sem ana Si Bu rroughs Garment Company lleva acabo este program a de pro du cc ión con su m irálas 1000 ho ras/semana qu e disp on e en el d epar tam en to d e c or te. As í, co m o tam b ié n , co n s u m irásu s 1400 ho ras/semana del departamento d e costu ra. Sin emb argo, en el departamento de empacado d e las 200 horas/semana disp on ibles solo ut ilizará152 ho ras/sem ana, com o c on sec uen ci a se tend ráun oc io d e 48 ho ras/semana, lo que equivale a 1.2 obreros o cios os y solo trab ajarían 3.8 ob rero s/sem ana en p ro m edio .
Solu ción óptim a únic a
Ejem plo 2 Máx .
X 2
X 0 = 3X 1 + 4X 2
Sujeto a:
Coordenadas
2X 1 + 3X 2 < 12
( 0, 4) ( 6, 0)
2X 1 + X 2 < 8
( 0, 8) ( 4, 0 )
X 1 , X 2 > 0
Región Factible Ev alu ac ión d e v é rt ic es
(-1)
B
C
D
X 0 =
0
16
17
12
X 1 =
0
0
3
4
X 2 =
0
4
2
0
s 1 =
12
0
0
4
8
4
0
0
2X 1 + X 2 = 8 (-1) 2X 2 = 4 X 2 = 2 2X 1 + X 2 = 8
B C
2X 1 +
2= 8 X 1 = 3
A A
2X 1 + 3X 2 = 12
D
X 1
La solu ción óptim a se presenta en el v é rtic e C
Solu ción óptim a múltip le ó alternativa
Ejem plo 3 Máx .
X 2
Puntos óptimo s
X 0 = 2X 1 + 3X 2 Coordenadas
Sujeto a: 2X 1 + 3X 2 < 30
( 0, 10) ( 15, 0)
- X 1 + X 2 < 5
( 0, 5) ( - 5, 0)
X 1 + X 2 > 5
( 0, 5) ( 5, 0)
X 1
( 0, 10)
< 10
X 1 , X 2 > 0
B
A
Región factible
Solución B
E
Soluc ión C
X 0 = 30
s 2 = 0
X 0 = 30
s 2 = 35/3
X 1 = 3
S 3 = 6
X 1 = 10
S 3 = 25/3
X 2 = 8
s 4 = 7
X 2 = 10/3
s 4 = 0
s 1 = 0
C
s 1 = 0
D
X 1
La pendiente de la función objetivo es igual a la pendiente de alguna de sus restricciones m X0 = mR1
Ejem plo 4
Soluc ión ilim itada ó No Aco tada
Máx . X 0 = X 1 + 2X 2
Sujeto a:
Coordenadas
-2X 1 + X 2 < 4
(0, 4) (-2 , 0)
X 1 - 3X 2 < 3
(0, -1) ( 3, 0)
X 2
X 1 , X 2 > 0
X 1
Soluc ión Infactible
Ejem plo 5 Máx . X 0 = X 1 + 2X 2
Sujeto a:
Coordenadas
X 1 + 2X 2 < 4
(0, 2) (4, 0)
2X 1 + 3X 2 < 12
(0, 4) (6, 0)
X 2
X 1 , X 2 > 0
X 1
Universidad Autónoma de Tamaulipas Facultad de Ingeniería “Arturo Narro Siller” Investigación de Operaciones I
El prob lem a de trans po rte Introducción Mé todo Esquina Nor oeste Mé todo de Apr oximaci ón de Vogel
Ing . J os éGab riel Go n zález Tu rru b iates
I ntroducción al problema de transporte El pr ob lema d e trans po rte, este co ns iste b ásic ament e en tran sp or tar m ercan cías d esd e vari os or ígen es (co m o pu eden ser, fábr icas) a varios destin os (por ejem plo , almacen es y bo degas ). Sin em barg o, el m od elo s e pud e aplicar tam bié n en s itu acio nes pr áctic as co m o lo s on el con tro l de inventarios, la pro gram ación d el em pleo y la asign ación d e person al entre otros . En s íel pro blem a de trans po rte, es u n pro gram a lineal que p u ed e s er r es u elt o a tr av é s d el m é to d o s ím p lex . Sin em b ar g o , por la naturaleza especial de su estructu ra es po sible el desarro llo d e un pro cedim iento d e so luc ión, deno m inado té cn ica d e tr ans p o rt e, el c ual es m ás ef ic ien te en t é rm in o s d e calc ul o .
Definición y aplicación del modelo de tr ansporte El mod elo de transpo rte bus ca determ inar un c urs o de acc ión de trans po rte de u na m ercanc ía desd e varias fu entes a v arios destin os . Entre lo s d atos qu e requiere el mo delo es tán: 1. Nivel de oferta en c ada fuente y la cantidad de demanda en cada destino . 2. El cos to d e transp orte unitario de la mercancía de cada origen a cada destino . Com o s ólo hay un tipo de m ercanc ía, un dest ino p uede recib ir su dem anda de un a o m ás fu entes. El mo delo tiene co m o o bjetiv o determ inar la c antid ad q ue s e enviaráde c ada or igen a cada destino , de tal form a que minim ice el cos to de transp orte total.
El mod elo d e transpo rte se puede representar com o u na red con m orígenes y n d estino s. Un orig en o u n d estino se represent a po r un nod o. El arco qu e une una fuente con u n d estino representa la ruta po r la cu al se tran sp or ta la merc anc ía. La c antid ad de la of erta en el origen i a i y la dem anda en el destino j es b j . El costo de trans po rte unitario entre el origen i y el destino j es C ij . Origen a 1
1
a 2
a m
Destino C 11 ; X 11
1
b 1
2
2
b 2
m
n
b m
C m n ; X m n
M odelo general de PL para el problema de transporte M inimizar X 0
m
n
i 1
j 1
C ij X ij
Sujeto a : m
X ij
b j
i 1 n
X ij
ai
j 1
X ij
0
i 1, 2, . . . , m j 1, 2, . . . , n
Este mo delo imp lica que el total de la oferta debe ser cuand o m enos ig ual a la cantidad dem andada.
Ejemplo 1 Em pacado ra la Mod erna, S.A . de C.V., tiene actu almente tr es plantas, distrib uidas en Tamaulipas. Cada planta prod uc e latas de ch iles en escabeche, qu e son empacadas en cajas d e cien latas de 102 g. Ac tualmente cuenta con tres centros de dis trib uc ión para la zon a nort e de la repúblic a mexic ana. Lo s cos tos d e transp orte por cada camión desde las plantas hasta los c entros d e distribu ción, se m uestran en la tabla.
Planta
P1 P2 P3
Centro de distribución CD1 CD2 CD3 $1250 $1380 $1000 950 1230 840 1520 1420 1360
Cada centro de distr ibuc ión r equiere 15, 20 y 18 camio nes sem analment e. Por o tro lado , se sabe que cada planta tiene dis po nib les 12, 25 y 16 respectiv ament e. Se pide: 1. C o n s t r u y a el m o d el o d e P L . 2. Resuelva usando el paquete WinQSB. An otando el número de iteracion es con que fue resuelto.
Tabla Símplex de transpor te Coeficientes de costo s
Variables de decisión
1250
X 11
1380
X 12 950
X 21
Demanda
840 25
X 22 1420
X 32 15
12
X 13
X 21
X 31
1000
1230
1520
Suministro
1360 16
X 33 20
18
Mé todo de Esquina Nor oeste Cel d as b ás ic as
1250
1380
1000 12
12
950
1230
840 25
20
3
1520
2
1420
1360 16
16
Celdas No B ás ic as
15
20
18
X 0 = (12)(1250)+(3)(950 )+(20)(1230)+(2 )(840)+(16)(1360 ) X 0 = 15000 + 2850 + 24600 + 1680 + 21760
u 1 = 0
u 1 + v 1 = 1250 u 2 + v 1 = 950 u 2 + v 2 = 1230 u 2 + v 3 = 840 u 3 + v 3 = 840
u 2 = 1530
1250
v 1 = 1250
12
1380
-1400 950
v 2 = -300
1000
-1390
1230
3
20
840
1300
2
1420
-330
15 20 Cálc u lo d e v ari ab les n o b ás ic as
1360 16
16
18
C ij * = C ij - (u i + v ) j C 12 * = 1380 - (1250 + 1530) C 12 * = -1400
12
25 1520
v 3 = 220
u 3 = 1140
C 13 * = 1000 - (1250 + 1140) C 12 * = -1390
Mé todo de cruce de arroyo u 1 = 0 1250
(-) v 1 = 1250
12
950
1000
-1390
(-) 1230
12
840 25
20
3
1520
v 3 = 220
u 3 = 1140
(+) 1380 -1400
(+) v 2 = -300
u 2 = 1530
2
1420
1300
-330
15
20
1360 16
16
18
