Preview only show first 10 pages with watermark. For full document please download

Intproglineal-1

   EMBED


Share

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