Unidad_1

7/21/2019 Unidad_1

http://slidepdf.com/reader/full/unidad1-56db081f14a1d 1/375

1

Unidad 1

Programación Lineal

7/21/2019 Unidad_1


2

• ¿Qué es un problema?

• Soluciones:

Absolución

Resolución

Solución

Disolución

• ¿Por qué decimos que un problema es compleo?

• An!lisis de problemas: ¿Quién resuel"e los problemas?

• ¿Qué en#endemos por iden#i$icar un problema?

1%1 &n#roducción a la Programación Lineal

7/21/2019 Unidad_1


3

¿Qué es Investigación de Operaciones?

El uso de las matemáticas y las computadoras para ayudar a tomar decisiones racionales rente a pro!lemas de administración comple"os

7/21/2019 Unidad_1


#

Aplicación de las técnicas de la administración a problemas (sistemas):

$etermin%sticos

&oda la inormación necesaria para o!tener unasolución se conoce con certe'a

Estocásticos

(arte de la inormación no se conoce con certe'a

7/21/2019 Unidad_1


)

*étodo +ient%ico para resolver pro!lemas comple"os

En las +iencias En ,dministración

$e%nase el pro!lema -ecoléctense los datos .ormulénse /ipótesis (rue!énse /ipótesis Eval0ense resultados O!ténganse conclusiones

$e%nase el pro!lema -ecoléctense los datos $e%nanse soluciones alternativas Eval0ense soluciones alternativas elecciónese la me"or alternativa (uesta en práctica

7/21/2019 Unidad_1


¿Qué se /ace en la realidad?

Estar !ien inormado +onocer todastodas las alternativas er o!"etivo ser optimi'ador económico4

*uc/assoluciones

$einir el

pro!lema

Esta!lecerlos criteriosde solución

5uscar las

soluciones

olución

atisactoria

,umentar loscriterios

(ocassoluciones

$isminuircriterios

7/21/2019 Unidad_1

http://slidepdf.com/reader/full/unidad1-56db081f14a1d 7/375 6

¿Qué /ace un $irector de Empresa para escoger la acción máseectiva para alcan'ar las metas de la Organi'ación?

Esta!lecer 'ri#erio 7ue usará eleccionar un con"unto de al#erna#i"as para considerarlas $eterminar el modelo 7ue se usará y los valores de los parámetros $eterminar la alternativa 7ue optimiza el criterio

7/21/2019 Unidad_1


,portes9 &écnicas de (rogramación :ineal

; <eorge $ant'ig =,.4> *ars/all ood y *urray <eisler

; assily :eontie modelo insumo@producto4

• *étodo impleA

; <omory programación lineal discreta4

; :ester .ord y $B C9 .ulDerson redes> trayectoria cr%tica4

• +(* y (E-&

7/21/2019 Unidad_1


CONSTRUCCIÓN D !OD"OS CUANTITATI#OS

:os métodos cuantitativos se emplean9

• +omo gu%a en la toma de decisiones

• +omo ayuda en la toma de decisiones

• (ara automati'ar la toma de decisiones

7/21/2019 Unidad_1

http://slidepdf.com/reader/full/unidad1-56db081f14a1d 10/375 1F

'arac#er(s#icas de los Sis#emas Adminis#ra#i"os

• De$: )Sis#ema%%%%

• *ipos de sis#emas: 'errados+ abier#os

,odelos:

• -orma#i"os+ descrip#i"os

• 'oncre#os+ Abs#rac#os ver!ales o sim!ólicos4

• Aplicación Inventarios4

• *écnica (rogramación :ineal4

• 'omparación de ,odelos valide'> conial!ilidady la simplicidad4

7/21/2019 Unidad_1


• Dimensionalidad de los modelos unidades4

• *oma de decisiones

• Dimensionalidad de los modelos unidades4

Cate$or%a Consec&encia

+ertidum!re $eterministas

-iesgo (ro!a!il%sticas

Incertidum!re $esconocidas

+onlicto Inluidas por un oponente

7/21/2019 Unidad_1


Uso de Datos para la Toma de Decisiones

) ) De#ermina primero los .ec.os+ después puedes De#ermina primero los .ec.os+ después puedes

#ergi"ersarlos como #e pla/ca0% ,ar *2in#ergi"ersarlos como #e pla/ca0% ,ar *2in

) ) Los .ec.os no dean de e3is#ir porque se ignoren0% Los .ec.os no dean de e3is#ir porque se ignoren0%

Aldous 4u3le5 Aldous 4u3le5

7/21/2019 Unidad_1


• ¿Qué son los datos?¿Qué son los datos?

Son hechos o conceptos conocidos o supuestos ySon hechos o conceptos conocidos o supuestos y generalmente se expresan en números generalmente se expresan en números

• Tipos de datosTipos de datos

Internos y externos Internos y externosObjetios y subjetiosObjetios y subjetios

• !e"uerimientos de datos en di#erentes nieles de !e"uerimientos de datos en di#erentes nieles de

la Organizaci$nla Organizaci$n

%ontrol operatio%ontrol operatio

%ontrol &dministratio%ontrol &dministratio

'laneaci$n estratégica 'laneaci$n estratégica

7/21/2019 Unidad_1

http://slidepdf.com/reader/full/unidad1-56db081f14a1d 14/375 1#

ituación9 Inersi$n

%onsidere el problema en#rentado por (ar)* graduado de la maestr+a de

administraci$n de empresas* "uién recientemente obtuo un puesto como

analista #inanciero en una compa,+a de -all Street. /no de los bene#icios

adicionales es un plan de retiro en el "ue el empleado pone 01 de su ingreso

mensual. 2a compa,+a iguala esta cantidad. 3l dinero de este plan es entonces

inertido en dos #ondos4 un #ondo de acciones y un #ondo de bonos. 3l

5epartamento de 6ene#icios le ha pedido a (ar) "ue especi#i"ue la #racci$n de

este dinero "ue habr+a "ue inertir en cada #ondo. (ar) ha analizado el

rendimiento anterior de estos #ondos y se ha enterado de "ue el #ondo de

acciones ha crecido a una tasa anual promedio de 781* mientras "ue el #ondo

de bonos* ha promediado una retribuci$n anual de 91. 'ara diersi#icar su

cartera y para controlar el riesgo* no desea poner todos los hueos en una sola

canasta* ha identi#icado dos pautas4

7. :inguno de los #ondos debe tener m;s del <01 de la inersi$n total.

=.2a cantidad inertida en el #ondo de acciones no debe exceder del doble

inertido en el #ondo de bonos.

7/21/2019 Unidad_1


1)

1 $einición del pro!lema

El pro!lema de *arD está !ien deinido> se conoce elo!"etivo glo!al> las limitaciones !ásicas para la toma dedecisión

2 $esarrollo del *odelo *atemático

EApresar el pro!lema en orma matemática ormular elmodelo4> por lo 7ue se re7uiere determinar las varia!lesinvolucradas

7/21/2019 Unidad_1


1

Garia!les de decisión9

9 .racción de capital por invertir en acciones5 9 .racción de capital por invertir en !onos

(ara el pro!lema se desean escoger valores para 7ue estasvaria!les9

1 *aAimicen la retri!ución anual esperada2 atisagan todas las pautas de inversión

7/21/2019 Unidad_1


16

@ .unción O!"etivo

El o!"etivo glo!al de un pro!lema de decisióneApresado en una orma matemática en términos delos datos y de las varia!les de decisión9

*aAimi'ar F>1 H F>F 5

> !estricciones limitaciones@Es un l%mite so!re los valores de las varia!les en unmodelo matemático t%picamente impuestos porcondiciones eAternasB

7/21/2019 Unidad_1


18

@ ing0n ondo tenga más del 6)J de lo invertido

≤ F>6) l%mite superior en el ondo de acciones4

5 ≤ F>6) l%mite superior en el ondo de !onos4

@ :a racción S invertida en el ondo de acciones no de!e

eAceder del do!le de la racción ' invertida en el ondode !onos

≤ 2 5 ó @ 2 5 ≤ F

@ +ada racción de!e ser no negativa

> 5 ≥ F

7/21/2019 Unidad_1


1

.inalmente el modelo resultante es9


u"eto a9

≤ F>6)

5 ≤ F>6)

@ 2 5 ≤ F

> 5 ≥ F

7/21/2019 Unidad_1


2F

3 -esolución del modelo matemático

,l resolver el pro!lema usando cual7uier técnica setienen los siguientes valores para las varia!les dedecisión9

K F>6) y

5K F>6)

<enerando una retri!ución de9

F>1 L F>6) H F>F L F>6) K F>12 12J4

Soler 7

http://var/www/apps/conversion/tmp/scratch_6/C:%5CArchivos%20de%20programa%5CMicrosoft%20Office%5COFFICE11%5CEXCEL.EXE

7/21/2019 Unidad_1


21

# Galidación y +ontrol de la olución

,l o!servar los valores de las varia!les de decisiónKF>6) y 5KF>6)4 se ve 7ue no tienen sentidoB o se

puede invertir un 6)J en am!os ondossimultáneamenteB

May un error> no se incorporó una restricción> esto es>los recursos disponi!ilidadB

H 5 K 1

7/21/2019 Unidad_1


22

) *odiicación del *odelo


u"eto a9

≤ F>6) 5 ≤ F>6)

@ 2 5 ≤ F

H 5 K 1

> 5 ≥ F

7/21/2019 Unidad_1


23

-esolviendo nuevamente se tiene 7ue9

K F>6 y5 K F>3333

.inalmente la retri!ución es

F>1 L F>6 H F>F L F>33333 K F>86 8>6J4

ota9 Emplear olver para determinar elvalor de las varia!les de decisión

http://var/www/apps/conversion/tmp/scratch_6/C:%5CArchivos%20de%20programa%5CMicrosoft%20Office%5COFFICE11%5CEXCEL.EXE

7/21/2019 Unidad_1


2#

1B2 +onstrucción de *odelos de (:

(odelo de 'rogramaci$n 2ineal

Es un modelo matemático en el 7ue lasrelaciones entre varia!les son lineales y

donde /ay un solo o!"etivo o medida derendimientoB

:a venta"a 7ue tiene el modelo es 7ueeAiste una técnica matemática 7ue permite determinar la decisión óptimaB

7/21/2019 Unidad_1


2)

El modelo de (: tiene un con"unto de "ariables de decisión> una

$unción obe#i"o la 7ue de!e maAimi'arse o minimi'arse y uncon"unto de relaciones o res#riccionesB

A B % 7 C 7 D % = C = D ......... % n C n

A 9 es un o!"etivo económico !eneicios> producción> costos> etc4

% i 9 coeicientes constantes actores de ponderación4

C i 9 varia!les de decisión n4

su"eto a !estricciones m@ 49

&7 C

7 D &

= C

= D ......... &

n C

n ≤ 67

.................................................. &7 C 7 D &= C = D ......... &n C n ≤ 6m

.O-*,:IN,+I $E: *O$E:O $E (:

7/21/2019 Unidad_1


2

(atricialmente se tiene4

Gector de varia!les o

niveles de actividad

Gector de Pcostos o

actor de ponderación

=

=

n x

x

x

B

2

1

[ ]n

ccc BBB21

7/21/2019 Unidad_1


26





, =

5 =

nb

b

b

2

1

mnmm

n

n

aaa

aaa

aaa

BB

BBBBBBBB

BB

BB

21

22221

11211

7/21/2019 Unidad_1


28

Entonces

Optimi'ar N K +& R K Sc1 c2 c3T

n x

x

x

2

1

K ∑=

n

j

j j xc1

su"eto a

, R 5y R ≥ F

≤>

7/21/2019 Unidad_1


2

E"emplo 19=na mue!ler%a produce dos tipos de productos> sillas ymesasB upóngase 7ue el !eneicio marginal por cadasilla es de U8 y por cada mesa es de U1FB (ara la

producción se dispone de 2F /oras /om!re //4 y de 1Funidades de madera um4B (ara la construcción de unasilla se re7uieren 8 // y 2 um> y para la construcción de

una mesa se re7uieren // y # umB ¿+uántas sillas ymesas se de!en construir para o!tener el mayor !eneicio?B

7/21/2019 Unidad_1


3F

-ecursos illas *esas$isponi!ilidad de

recursos

-19 /oras /om!re 8 2F

-29 unidades de madera

2 # 1F

5eneicios U8 U1F

7/21/2019 Unidad_1


31

Eormulaci$n del '2

ea

C 7 9 V de sillas C = 9 V de mesas

.unción O!"etivo9

(ax A B FC 7 D 78C =

u"eto a9

FC 7 D 9C = ≤ =8 GG hh=C 7 D HC = ≤ 78 GG um

C 7 ≥ F y C = no negatiidad@

7/21/2019 Unidad_1


32

E"emplo 29

$os productos se ela!oran al pasar en orma sucesiva por tres

má7uinasBEl tiempo por má7uina asignado a los dos productos está limitadoa 1F /oras por d%a

El tiempo de producción y la ganancia por unidad de cada

producto son9

Producto Máquina 1 Máquina 2 Máquina 3 Ganancia $

1 10 6 8 2

2 5 20 15 3

Minutos por unidad

O!tenga el modelo de (: para maAimi'ar la ganancia

olución9

7/21/2019 Unidad_1


33

olución9

1B Garia!les de decisión

R1 9 +antidad del producto 1

R2 9 +antidad del producto 2

2B .unción O!"etivo9 *aAimi'ar ganancia

*,R N K 2 R1 H 3 R2

3B -estricciones

1F R1 H ) R2 ≤ FF

R1 H 2F R2 ≤ FF 8 R1 H 1) R2 ≤ FF

R1 > R2 ≥ F

ó 2# R1 H #F R2 ≤ 18FF

R1 > R2 ≥ F

E"emplo 39

7/21/2019 Unidad_1


3#

E"emplo 39-*+ posee una pe7ueWa á!rica de pinturas para interiores y eAteriores decasa para su distri!ución al mayoreoB e utili'an dos materiales !ásicos> , y 5B:a disponi!ilidad máAima de , es de toneladas diarias> la de 5 es de 8

toneladas por d%aB :a necesidad diaria de materia prima por tonelada de pintura para interiores y eAteriores se resumen en la siguiente ta!la9

=n estudio de mercado /a esta!lecido 7ue la demanda diaria de pintura parainteriores no puede ser mayor 7ue las pinturas para eAteriores en más de unatoneladaB ,simismo> el estudio seWala 7ue la demanda máAima de pintura para

interiores está limitada a dos toneladas diariasBEl precio al mayoreo es de U3BFFF para la pintura de eAteriores y U2BFFF para la deinterioresB

¿+uánta pintura para eAteriores e interiores de!e producir la á!rica de pinturas

-*+ todos los d%as para maAimi'ar el ingreso !ruto?

olución9

7/21/2019 Unidad_1


3)

olución9

1B Garia!les de decisión

R1 9 &oneladas de pintura de eAteriores producidas por d%a

R2 9 &oneladas de pintura para interiores producidas por d%a

2B .unción O!"etivo9 *aAimi'ar ganancia

*,R N K 3 R1 H 2 R2 miles de unidades monetarias3B -estricciones R1 H 2 R2 ≤

2 R1 H R2 ≤ 8

@ R1 H R2 ≤ 1

R2 ≤ 2

R1 > R2 ≥ F

7/21/2019 Unidad_1


3

E"emplo #9=na empresa a!rica dos productos> , y 5B En su ela!oración> cada

producto de!e pasar por dos seccionesB El suministro de mano de o!rade la sección 1 es 1FF /oras y el de la sección 2 es 2FF /orasBEl tiempo de mano de o!ra cuesta U2 por /ora en la sección 1 y U1>)en la sección 2B :as /oras de mano de o!ra necesarias por unidad decada producto son las siguientes9

(roducto , (roducto 5

ección 1 # 3

ección 2 2 8

:a cantidad máAima de unidades de 5 7ue puede venderse es igual a

treintaX la de , es veinticuatroB :a materia prima para cada productocuesta U) por unidadB El precio unitario de , es U3F y el de 5 es U2)U

a4 +onstruya el modelo de (: correspondienteB

7/21/2019 Unidad_1


36

1B3 olución de (ro!lemas (:

EAisten varias métodos> entre ellos se tiene

1B3B1 *étodo <ráico

1B3B2 *étodo impleA

7/21/2019 Unidad_1


38

1B3B1 *étodo <ráico

Este método es muy limitado por la incapacidad devisuali'ar más de tres dimensionesB in em!argo esrecomenda!le usarlo para i"ar los conceptos 7ue sonaplica!les a los otros métodos de resoluciónB

7/21/2019 Unidad_1


3

:os pasos a seguir son9

1B +onstruir el modelo

2B <raicar cada una de las restricciones en el sistemaormado por las varia!les de decisiónB

3B Identiicar la región 'ona4 acti!le

#B $eterminar el valor o!"etivo GO4 a partir de la uncióno!"etivo en cada uno de los vértices de la 'ona acti!leB

i es minimi'ar> considerar el menor o el mayor en casode maAimi'arB

E"emplo

7/21/2019 Unidad_1


#F

E"emplo

(-O&-,+ produce dos l%neas de e7uipo pesadoB =na de estasl%neas de productos llamada e7uipo para remoción de escom!ros4

se destina esencialmente a aplicaciones de construcciónB :a otral%nea llamada e7uipos orestales está destinada a la industriamadereraB El miem!ro más grande de la l%nea de e7uipos pararemover escom!ro el E@4 y el miem!ro mayor de la l%nea de

e7uipos orestales el .@4 se producen en el mismo departamento ycon el mismo e7uipoB Maciendo uso de las predicciones económicas para el próAimo mes> el gerente de mercadotecnia de (-O&,+ "u'ga 7ue durante ese periodo será posi!le vender los E@ y los .@7ue la empresa pueda producirB :a administración de!e a/ora

recomendar una meta de producción para el próAimo mesB Es decir>¿cuántos E@ y .@ de!en producirse?B En la toma de decisión> los

principales actores a considerar son los siguientes9

7/21/2019 Unidad_1


#1

1B (-O&-,+ tendrá una utilidad de U)BFFF por cada E@ 7ue se

venda y U#BFFF por cada .@B

2B +ada producto pasa por operaciones mecánicas tanto en eldepartamento , como en el departamento 5

3B (ara la producción del próAimo mes> estos dos departamentostienen disponi!les 1)F y 1F /oras respectivamenteB +ada E@consume 1F /oras en el departamento , y 2F /oras en eldepartamento 5> mientras 7ue cada .@ consume 1) /oras en eldepartamento , y 1F /oras en el departamento 5B

7/21/2019 Unidad_1


#2

#B +on o!"eto de cumplir un compromiso con el sindicato> el totalde /oras de tra!a"o 7ue se dedicarán a la veriicación de los

productos terminados del próAimo mes no puede ser menor en1FJ a una meta esta!lecida de 1)F /orasB Esta actividad sereali'a en un tercer departamento 7ue no tiene relación con losdepartamentos , y 5B +ada E@ re7uiere de 3F /oras decompro!ación y cada .@> 1F /orasB

)B +on el o!"eto de mantener su posición actual en el mercado> laalta gerencia /a decretado 7ue para la pol%tica de operación esnecesario construir al menos un .@ por cada 3 E@B

B =n consumidor importante /a ordenado un total de por lo menoscinco aparatos en cual7uier com!inación de E@ y .@4 para el

próAimo mes> as% es 7ue por lo menos de!e producirse esacantidad

7/21/2019 Unidad_1


#3

*odelo de (:

a4 Garia!les de decisión9 !4 *aAimi'ar N9

c4 u"eto a9

<ráica de (-O&-,+<ráica de (-O&-,+

7/21/2019 Unidad_1


##

<ráica de (-O&-,+<ráica de (-O&-,+

Nona acti!le

<ráica de (-O&-,+ y unción =tilidad<ráica de (-O&-,+ y unción =tilidad

7/21/2019 Unidad_1


#)



7/21/2019 Unidad_1


#


olución

óptima

7/21/2019 Unidad_1


#6

+álculo de E y .

Gértice +9 -esolver el sistema4

1FE H 1). K 1)F

2FE H 1F. K 1F

E K #>)

. K 6

y GO K )BFFF#>)4 H #BFFF64

22B)FF H 28BFFF

#O * +,-+,,

7/21/2019 Unidad_1


#8

+onsumo9 /oras4

$epto ,9 1F#>)4 H 1)64 K 1)F

$epto 59 2F#>)4 H1F64 K 1F

$epto (rue!as9 3F#>)4 H 1F64 K 2F)

En los departamentos , y 5 el consumo es

igual a la disponi!ilidad en cam!io en eldepartamento de prue!as se consumió más delm%nimo eAigidoB

7/21/2019 Unidad_1


#

1B3B2 *étodo impleA

1B .orma estándar del *odelo de (:

2B oluciones 5ásicas

3B *étodo impleA (rimal9 ,lgoritmo

7/21/2019 Unidad_1


,B .orma estándar del *odelo de (:

• &odas las restricciones son ecuaciones consegundos miem!ros no negativos

• &odas las varia!les son no negativas• :a unción O!"etivo puede ser maAimi'ación

o minimi'ación

, 1 -estricciones

7/21/2019 Unidad_1


)1

,B1 -estricciones=na restricción del tipo

4 puede convertirse en

ecuación mediante la suma de una varia!le de/olgura restando una varia!le de e.ceso4 al primermiem!ro de la restricciónB

E"emplo914 desigualdad9 3A1 H 12A2 2F

igualdad 3A1 H 12A2 H ./

K 2F con ./

,

24 desigualdad9 8A1 H 1FA2 12F

igualdad 8A1 H 1FA2 @ .0 K 12F con .0 ,

7/21/2019 Unidad_1


)2

,B2 egundo miem!ro no negativo

e multiplica la desigualdad ecuación4 por @1

E"B 3R1 H 2R2 @)

@3R1 @ 2R2 YK )

, 3 Garia!les irrestrictas

7/21/2019 Unidad_1


)3

,B3 Garia!les irrestrictas

=na varia!le irrestricta no restringida4 .i puedeeApresarse en términos de dos varia!les no negativasmediante el uso de la sustitución9

:a sustitución de!e reali'arse en todas las

restricciones y en la unción o!"etivo

F> ZZZ ≥ii

x xZZZiii

x x x −=

.orma Estándar

7/21/2019 Unidad_1


)#

E"emplo9

Escri!a el siguiente modelo de (: en la orma estándar9

*,R ' K 2A1 H 3A2

su"eto a

A1 H A2 K 1F

@2A1 H 3A2 ≤ @)

6A1 @ #A2 ≤

A1 irrestricta y

A2 ≥ F

.orma Estándar

7/21/2019 Unidad_1


))

olución

, # .unción O!"etivo

7/21/2019 Unidad_1


)

,B# .unción O!"etivo

El modelo estándar de programación lineal puede serutili'ado para resolver pro!lemas del tipo de maAimi'ación ode minimi'ación> algunas veces sirve para convertir una ormaa la otraB

:a maAimi'ación de una unción e7uivale a laminimi'ación del nega#i"o de la misma unción y viceversaB

E"emplo9 *,R ' K )A1 H 3A2 H )A3

es matemáticamente e7uivalente a

*I @'4 K @)A1 @ 3A2 @ )A3

5 oluciones 5ásicas

7/21/2019 Unidad_1


)6

5B oluciones 5ásicas

En un (: con m ecuaciones y n incógnitas

• =na solución !ásica asociada se determina /aciendo n@mvaria!les iguales a cero y luego> resolviendo las m ecuaciones con las restantes m incógnitas> siempre 7ue la

solución eAista y sea 0nica• En la (: nos reerimos a las n6m varia!les 7ue se /acencero como 1ariables no b2sicas (e.ternas)> y a las m varia!les restantes como 1ariables b2sicas siempre 7ue

eAista una solución 0nica4- e dice 7ue una solución !ásica es acti!le si todos los

valores de su solución son no negativos

,lgoritmo del método impleA

7/21/2019 Unidad_1


)8

g p

II+IO

O!tener .orma Estándar orma aumentada4

+onstruir ta!la inicial

*ientras :O S3& ptimo

[

Identiicación varia!les de entrada\alida

$esarrollo de la ta!la revisada

]

.I

7/21/2019 Unidad_1


)

+B *étodo impleA (rimal

Tabla Simple General

! " !1 !2 ## !n 0 0 ## 0

ariables alores de

%ásicas Soluci&n '1 '2 ## 'n 'n(1 'n(2 ## 'n(m

0 'n(1 b1 a11 a12 ## a1n 1 0 ## 0

0 'n(2 b2 a21 a22 ## a2n 0 1 ## 0

# ## ## ## ## ## ## ## ## ## ##

# ## ## ## ## ## ## ## ## ## ##

0 'n(m bm am1 am2 ## amn 0 0 ## 1

) "

! " * ) " '''

+onstrucción de la ta!la inicial

E"emplo9

7/21/2019 Unidad_1


F

" p

$ado el siguiente (: encontrar su soluciónaplicando el método impleA

7/21/2019 Unidad_1


1

.orma Estándar aumentada4

M+' ) , 3 '1 ( 2 '2 ( 0'3 ( 0 '- ( 0 '5 ( 0 '6

s a

1. '1 ( 2 '2 ( '3 ( 0 '- ( 0 '5 ( 0 '6 , 6

2. 2 '1 ( '2 ( 0 '3 ( '- ( 0 '5 ( 0 '6 , 83. * '1 ( '2 ( 0 '3 ( 0 '- ( '5 ( 0 '6 , 1

-. 0 '1 ( '2 ( 0 '3 ( 0 '- ( 0 '5 ( '6 , 2

'1/ '2/ '3/ '-/ '5/ '6 , 0

7/21/2019 Unidad_1


2

&a!la Inicial

7/21/2019 Unidad_1


3

olución Inicial9Garia!le Entrante y aliente

*ayor contri!ución

I t i

7/21/2019 Unidad_1


#

Instruccionesa. !"* )" l maor para ariable entrante

b. Se diide la columna soluci&n por los coe4icientes de la columna de la ariable que entra se elie el menor de los positios

c. !omo la ariable que entra es soluci&n entonces la columna debe ser de ceros un 1

i. Se diide la 4ila completa por el pivote alor de la intersecci&n 4ila columna.

ii. Para conertir los otros coe4icientes a cero se utili7a la 4ila resultante del punto anterior

se multiplica por alun coe4iciente de tal 4orma que al sumarlo restarlo. a la 4ila de inters

el coe4iciente sea cero

* Para la 4ila de '3 se multiplica por *1 se suma

* Para la 4ila de '5 s&lo 9a que sumar

* Para la 4ila de '6 a es un cero

:a nuea tabla es;

7/21/2019 Unidad_1


)

ueva &a!la

7/21/2019 Unidad_1


egunda Iteración

& !l l

7/21/2019 Unidad_1


6

&a!la resultante

7'umple la prueba de op#imalidad7

7/21/2019 Unidad_1


8

=n (ro!lema de *inimi'ación (enali'ación9 *4

*I N K 2 R1 H 8 R2

sa

14 ) R1 H 1F R2 K 1)F24 R1 ≤ 2F

34 R2 ≥1#

R1 ≥ F

.orma estándar9

7/21/2019 Unidad_1


.orma estándar9

-estricciones9

14 ̂ a es una igualdad9 ) A1 H 1FA2 K 1)F24 &iene varia!le de /olgura9 A1 H A# K 2F

34 &iene una varia!le de eAceso9 A2 @ A K 1#

-esumen9

) A1 H 1FA2 K 1)F

A1 H A# K 2F

A2 @ A K 1#__ o es posi!le determinar un grupo de varia!les !ásicas ``

.orma estándar9

7/21/2019 Unidad_1


6F

o a está da 9

En el e"emplo anterior maAimi'ación4 todas lasrestricciones ten%an varia!les de /olgura las 7ue seconsidera!an como varia!les !ásicas> pero no es as% eneste caso> por lo tanto /ay 7ue 7ue agregar varia!les

artiiciales R3 y R)4 asociadas a un costo muy alto *4 para asegurarse 7ue al inal sean varia!les eAternas y no participen en la solución> para las restricciones 14 y 34BEstas varia!les artiiciales participan en la unción

o!"etivo multiplicadas por el coeiciente *B

7/21/2019 Unidad_1


61

*odelo Estándar,umentado4

M<= ) , 2 '1 ( 8 '2 ( M '3 ( 0 '- ( M '5 ( 0 '6

1. 5 '1 ( 10 '

2 ( '

3( 0 '

- ( 0 '

5 ( 0 '

6 , 150

2. '1 ( 0 '2 ( 0 '3 ( '- ( 0 '5 ( 0 '6 , 20

3. 0 '1 ( '2 ( 0 '3 ( 0 '- ( '5 ( * '6 , 1-

'1/ '2/ '3/ '-/ '5/ '6 , 0

&a!la Inicial

7/21/2019 Unidad_1


62

:as varia!les !ásicas son9 R3> R# y R)

! " 2 8 M 0 M 0

%ase Soluci&n '1 '2 '3 '- '5 '6

M '3 150 5 10 1 0 0 0

0 '- 20 1 0 0 1 0 0

M '5 1- 0 1 0 0 1 *1

) "

! " * ) " '''

7/21/2019 Unidad_1


63

Iteración 1

! " 2 8 M 0 M 0

%ase Soluci&n '1 '2 '3 '- '5 '6

M '3 150 5 10 1 0 0 0

0 '- 20 1 0 0 1 0 0

M '5 1- 0 1 0 0 1 *1

) " 16-M 5M 11M M 0 M *M! " * ) " ''' 2*5M 8*11M 0 0 0 M

Entra R2 y sale R)

7/21/2019 Unidad_1


6#

Iteración 2

! " 2 8 M 0 M 0

%ase Soluci&n '1

'2

'3

'-

'5

'6

M '3 10 5 0 1 0 *10 10

0 '- 20 1 0 0 1 0 0

8 '2 1- 0 1 0 0 1 *1

) " 112(10M 5M 8 M 0 *10M(8 10M*8

! " * ) " ''' 2*5M 0 0 0 11M*8 *10M(8

Entra R y sale R3

7/21/2019 Unidad_1


6)

Iteración 3

! " 2 8 M 0 M 0

%ase Soluci&n '1 '2 '3 '- '5 '6

0 '6 1 0,5 0 0/1 0 *1 1

0 '- 20 1 0 0 1 0 0

8 '2 15 0/5 1 0/1 0 0 0

) " 120 - 8 0/8 0 0 0! " * ) " ''' *2 0 M*0/8 0 M 0

Entra R1 y sale R

7/21/2019 Unidad_1


6

ituación .inal

%ase Soluci&n '1 '2 '3 '- '5 '6

2 '1 2 1 0 0/2 0 *2 2

0 '- 18 0 0 *0/2 1 2 *2

8 '2 1- 0 1 0 0 1 *1 ) " 116 2 8 0/- 0 - *-

! " * ) " ''' 0 0 M*0/- 0 M*- -

:a solución es óptima todos los elementosde la 0ltima ila son cero o positivos4B

7/21/2019 Unidad_1


66

1B # ,nálisis de sensi!ilidad

ensi!ilidad implica preguntarse ¿7ué suceder%a s%

,4 +am!ia un coeiciente del lado derec/o de lasrestricciones

54 +am!ia uno de los coeicientes de la unción o!"etivo

7/21/2019 Unidad_1


68

1B #B1 Interpretación <ráica

E"emplo9

7/21/2019 Unidad_1


6

-ecordando el pro!lema de (rotacB

*aA N9 )BFFF E H #BFFF .

sa

1F E H 1) . b 1)F2F E H 1F . b 1F3F E H 1F . 13)

E @ 3 . b F E H . ) E F y . F

,4 +am!ios en los términos independientes:a sol ción era9

7/21/2019 Unidad_1


8F

:a solución era9E K #>)

. K 6

y N K )FB)FF

upongamos

a4 Que se dispone de una /ora adicional en eldepartamento , 1)1 /oras4

!4 Que se dispone de una menos en eldepartamento , 1# /oras4

c4 :o anterior pero para el departamento 5

7/21/2019 Unidad_1


81

&ra'ado de la gráica

7/21/2019 Unidad_1


82

+aso a4

1F E H 1) . K1)1 K E K 1)1\1F y . K 1)1\1)

Esta recta 7ueda un poco despla'ada a la derec/aB u pendiente no cam!ia> por tanto el punto + se /atrasladado al punto +B :a solución se mantiene en laintersección de las rectas 1F E H 1) . K 1)1

2F E H 1F . K1F

7/21/2019 Unidad_1


83

+


7/21/2019 Unidad_1


8#

+aso ! 4

1F E H 1) . K1# K E K 1#\1F y . K 1#\1)

Esta recta 7ueda un poco despla'ada a la i'7uierdaB u pendiente no cam!ia> por tanto el punto + se /atrasladado al punto +B :a solución se mantiene enla intersección de las rectas 1F E H 1) . K 1#

2F E H 1F . K 1F

7/21/2019 Unidad_1


8)

+


7/21/2019 Unidad_1


8

:a solución a/ora es9

7/21/2019 Unidad_1


86

$epartamento , f1 lado derec/o4

a4 E K #>#) . K 6>1 y N K )FB)F

!4 E K #>)) . K 6>1 y N K )FB3)F

$epartamento 5 f1 lado derec/o4

c14 E K #>)6) . K >) y N K )FB6)

c24 E K #>#2) . K 6>F) y N K )FB32)

7/21/2019 Unidad_1


7/21/2019 Unidad_1


8

$einición9

(recio dual> valor marginal o precio som!ra esel cam!io incremental en los !eneicios porcam!io unitario en el término independiente deuna restricción

7/21/2019 Unidad_1


F

54 +am!ios unitarios en los coeicientes de launción o!"etivo

+oeiciente de E9 )FF1 N K )FB)F#>)

E9 # N K )FB#)>)

+oeiciente de .9 #FF1 N K )FB)F6

.9 3 N K )FB#3

7/21/2019 Unidad_1


1

1B #B 2 Interpretación de la &a!la impleA9

Inormación 7ue se puede o!tener de la ta!la simpleA

:a solución óptima• El estado de los recursos

• :os precios duales

• ensi!ilidad de la solución óptima a cam!ios de disponi!ilidadde recursos> ganancia marginal coeB de la .O4 y uso derecursosB

& !l l l ió i

7/21/2019 Unidad_1


2

&a!la resultante9 olución ptima

7/21/2019 Unidad_1


3

olución óptima para el pro!lema demaAimi'ación4

Garia!le de Galor

decisión óptimo $ecisión

'1 3 1>3 Producir 3/333 ton pintura eterior

'2 1 1>3 Producir 1/333 ton pintura interior

) 12 2>3 Ganancia resultante unidades $

Estado de los -ecursos

7/21/2019 Unidad_1


#

Estado de los -ecursos

'lasi$icación de las res#ricciones: escasa+ abundan#e 5a seaque la solución óp#ima )consuma0 o no la can#idad

disponible del recursoB

e determina a partir de las varia!les de /olgura9

'3 , 0 scasa Materia Prima +

'- , 0 scasa Materia Prima %

'5 , 3 +bundante :?mite en eceso para '1 sobre '2

'6 , 2>3 +bundante :?mite en la demanda de '1

(recio $ual Galor unitario de un recurso4

7/21/2019 Unidad_1


)

• y1 K 1\3 miles de unid mon\ton adicional materia prima ,

• y2 K 1 1\3 miles de unid mon\ton adicional materia prima 5• y3 K F

• y# K F

Esta inormación se o!tiene de la ta!la simpleA óptimaconsiderando los coeicientes de la ila de N

%ase Soluci&n '1 '2 X3 X4 X5 X6

) 12 2>3 3 2 1/3 1 1/3 0 0

7/21/2019 Unidad_1


El mismo resultado se puede o!tener de la ecuación de N

óptimo9

) , 12 2>3 * 1/3 '3 ( 1 1/3 '- + 0 X5 + 0 X6)

i se cam!ia R3 de su nivel cero actual> N cam!iará a nivel de 1\3 demiles de unidad monetaria por toneladaB (ero un cam!io en R3 e7uivale acam!iar el recurso , en una cantidad igual

R1 H 2 R2 H R3 K

Esto signiica 7ue el precio dual de la materia prima , es 1\3

(ara la materia prima 5 es 1 1\3 y para los recursos 3 y # son ceroB

1B +am!io máAimo en la disponi!ilidad de -ecursos

7/21/2019 Unidad_1


6

• +am!iar el recurso materia prima , en la cantidad $1

Esto signiica 7ue el recurso materia prima , será H $1

i $1 F> se produce un aumento

i $1 Y F> se produce una disminución

¿+ómo /acerlo?

7/21/2019 Unidad_1


8

¿+ómo /acerlo?

, la restricción inicial agregar $1 y resolver aplicandosimpleA

El cam!io sólo aecta a la solución el segundo miem!ro4>considerando 7ue las constantes del segundo miem!ronunca se utili'an de pivoteB

Iteraciones sucesivas conducen a9

7/21/2019 Unidad_1


Iteraciones sucesivas conducen a9

Iteración

Ecuación F 1 2 óptima4

' F 12 34 45/ H 1\3 $1

1 H $1 2H $1 05/ H 2\3 $1

2 8 # 3,5/@1\3 $1

3 1 ) / @ 1 $1

# 2 2 45/ @ 2\3 $1

7/21/2019 Unidad_1


1FF

&a!la9 olución óptima

¿Qué /acer con toda esta inormación?¿Qué /acer con toda esta inormación?

7/21/2019 Unidad_1


1F1

• (rocurar 7ue la solución siga siendo acti!le

Esto signiica 7ue las varia!les !ásicas no de!enser negativasB *antener la no negatividad

14 R2 K #\3 H2\3 $1 ≥ F24 R1 K 1F\3 @1\3 $1 ≥ F

34 R) K 3 @ $1 ≥ F

#4 R K 2\3 @2\3 $1 ≥ F

e consideran dos casos9

7/21/2019 Unidad_1


1F2

• +aso 19 $1 F

14 e satisace con cual7uier valor

24 $1 ≤ 1F

34 $1 ≤ 3

#4 $1 ≤ 3

En consecuencia $1 de!e ser a lo más 1

• +aso 29 $1 Y F

7/21/2019 Unidad_1


1F3

24> 34 y #4 se satisacen siempre

14 $1≥ @2

en este caso $1≥ @2

-esumen9 @2 ≤ $1 ≤ 3

6 7 4 ≤ !ateria prima A ≤ 68300 ≤≤ !ateria prima A!ateria prima A ≤≤ 99

• Maciendo el mismo análisis para la materia

7/21/2019 Unidad_1


1F#

Maciendo el mismo análisis para la materia prima 5 se tiene9

@2 ≤ $2 ≤ #

7 4 ≤ !ateria prima ' ≤ 80

66 ≤≤ !ateria prima '!ateria prima ' ≤≤ 3434

2 +am!io máAimo en la relación

7/21/2019 Unidad_1


1F)

2B +am!io máAimo en la relación=tilidad\+osto marginal

:a .O nunca se utili'a como ecuación pivote> por lotanto cual7uier cam!io en sus coeicientes la

aectarán sólo a ella en la ta!la óptimaB

(ueden ocurrir dos casos9 7ue las varia!les sean !ásicas o no en ta!la óptimaB

+aso 19 Garia!les !ásicas

7/21/2019 Unidad_1


1F

+aso 19 Garia!les !ásicas

+am!iar la ganancia marginal de R1 de 3 a 3 H $1

$1 puede ser positivo o negativo

:a .O tendrá la orma

N K 3H$14R1 H 2R2

=tili'ando este nuevo coeiciente se llega a lasiguiente ta!la óptima9

7/21/2019 Unidad_1


1F6

:os 0nicos cam!ios en los coeicientes no !ásicos R3 yR# de la ecuación de N

Estos cam!ios pueden determinarse de la ta!la original>

7/21/2019 Unidad_1


1F8

p g >multiplicando los coeicientes no !ásicos y el segundo miem!rode la ila de R1 por $1> y luego sumandolo a la ila N óptimoB

+, 12 1>3 ( 10>3 @1 % , 1>3 * 1>3 @1 ! , ->3 ( 2>3 @1

(ara el caso de maAimi'ación9

7/21/2019 Unidad_1


1F

1\3 @ 1\3 $1 ≥ F y

#\3 H 2\3 $1 ≥ F

de la primera $1 ≤ 1

y de la segunda $1 ≥ @2

@2 ≤ $1 ≤ 1

.inalmente9 3@2 ≤ +1 ≤ 3 H 1

1 ≤ +1 ≤ #

_____ Inténtelo para +2 `````

+aso 29 Garia!les no !ásicas

7/21/2019 Unidad_1


11F

+aso 29 Garia!les no !ásicas

=n cam!io en los coeicientes o!"etivos pueden aectarsólo a los coeicientes de la ecuación de N la columnacorrespondiente no se utili'a como pivote4B

El caso en estudio no sirve por7ue R1 y R2 son !ásicas enla ta!la óptimaB

E"emplo9

7/21/2019 Unidad_1


111

E"emplo9ea N K )R1 H 2R2

para las mismas restricciones del e"emplo en estudioB:a ta!la resultante es9

R2 es a/ora no !ásica

7/21/2019 Unidad_1


112

2

El o!"etivo es cam!iar su coeiciente +2 K 2 a +2 H $2 yluego encontrar el intervaloB

,l aplicar el nuevo coeiciente /a!rá un cam!io en elcoeiciente de F>) a F>) @ $2

En general> el cam!io $ del coeiciente o!"etivo originalde una varia!le no !ásica conduce IE*(-E aldecremento en la misma cantidad del coeiciente o!"etivoen la ta!la óptimaB

:a ta!la permanecerá óptima en tanto 7ue F>) @$2 ≥ F

esto es> $2 ≤ F>)

7/21/2019 Unidad_1


113

El intervalo es

@ininito ≤ $2 ≤ F>) H2

@ininito ≤ $2 ≤ 2>)

E"emplo9

7/21/2019 Unidad_1


11#

-esolver el siguiente (: empleando simpleA y reali'ar

un análisis de sensi!ilidadB

*,R N K 3'1 ( 2'2 (5'3

sa'1 ( 2'2 ( '3 A 500

3'1 ( 2'3 A -60

'1 ( -'2 A -20

'1 /'2 / '3 B 0

1B) *étodo impleA $ual

7/21/2019 Unidad_1


11)

+uando los pro!lemas de (: no tienen una solución acti!le !ásica inicial con sólo /olguras> se pueden resolver sin utili'ar

varia!les artiiciales> entregando la misma inormaciónB

• D;INICIÓN D" <RO'"!A DUA"

El dual es un pro!lema de (: 7ue se o!tiene matemáticamentede un modelo primal de (: dadoB :os pro!lemas primal y dualestán relacionados a tal grado 7ue la solución de uno de ellos

conduce en orma automática a la solución del otroB

• En la mayor%a de los procedimientos de (:> el dual se

7/21/2019 Unidad_1


11

deine para varias ormas del primal> dependiendo delos tipos de restricciones> de los signos de lasvaria!les y del sentido de la optimi'aciónB

• e incluirá una deinición 0nica del pro!lema dual 7ue

incluye automáticamente a todas las ormas del primalB e !asa en el /ec/o de 7ue el pro!lema de (:de!e calcularse en orma estándar antes de resolverlomediante el método simpleA o simpleA dual> de esta

manera al deinir el pro!lema dual mediante la ormaestándar> los resultados serán consistentes con lainormación contenida en la ta!la simpleABB

:a orma estándar general del primal se deine como9

7/21/2019 Unidad_1


116

∑==

n

j

j j xc z 1

maAimi'ar o minimi'ar

∑=

n

j

jij xa1

su"eto a i K 1> 2> BBBBB> m " K 1> 2> BBB> n

x " ≥F

:otar "ue las n ariables x j * incluyen los excesos y las holguras.

3l es"uema se muestra en el siguiente diagrama4

7/21/2019 Unidad_1


118

ariables primales

'1 '2 ## ' " ## 'n

!1 !2 ## ! " ## !n

a11 a12 ## a1" ## a1n b1 1

a21 a22 ## a2" ## a2n b2 2

## ## ## ## ## ## ##

## ## ## ## ## ## ##

am1 am2 ## am" ## amn bm m

egundomiem!ro derestricciones

duales

+oeicientes

del primer

miem!ro de lasrestricciones

duales

"@ésima

restriccióndual

.uncción

o!"etivo deldual

Garia!le

dual

El diagrama muestra 7ue el dual se o!tiene simétricamente del

7/21/2019 Unidad_1


11

g 7 primal de acuerdo con las siguientes reglas9

• (ara toda restricción primal /ay una varia!le dual• (ara toda varia!le primal /ay una restricción dual• :os coeicientes de las restricciones de una varia!le primal orman

los coeicientes del primer miem!ro de la restricción dual

correspondiente> el coeiciente o!"etivo de la misma varia!le seconvierte en el segundo miem!ro de las restricción dualX y elsegundo miem!ro de la restricción primal se convierte en elcoeiciente o!"etivo de la respectiva varia!le dual

Estas reglas indican 7ue el pro!lema dual tendrá m varia!les y1>y2> BBB> ym4 y n restricciones> correspondientes a A1> A2 >BBBB> An4B

7/21/2019 Unidad_1


12F

En la ta!la siguiente se muestra como determinar los elementos

restantes del pro!lema dual9 sentido de la optimi'ación> tipo derestricciones y el signo de las varia!les dualesB

.unción O!"etivo $ual

Estándar del primal .unción o!"etivo -estricciones Garia!les*aAimi'ación *inimi'ación ≥ Irrestrictas*inimi'ación *aAimi'ación ≤ Irrestrictas

Todas las restricciones primales son ecuaciones y todas las

ariables son no negatias.

E"emplo 19

(rimal *aAimi'ar N K ) R H 12 R H # R

7/21/2019 Unidad_1


121

(rimal *aAimi'ar N K ) R1 H 12 R2 H # R3

su"eto a R1 H 2 R2 H R3 ≤ 1F 2 R1 @ R2 H 3 R3 K 8

R1> R2> R3 ≥ F

(rimal estándar *aAimi'ar N K ) R1 H 12 R2 H # R3 H F R#

su"eto a R1 H 2 R2 H R3 H R# K 1F

2 R1 @ R2 H 3 R3 HF R# K 8

R1> R2> R3 ≥ F

$ual *inimi'ar h K 1F y1 H 8 y2

su"eto a R 9 y H 2 y ≥ )

7/21/2019 Unidad_1


122

su"eto a R19 y1 H 2 y2 ≥ ) R29 2 y1 @ y2 ≥ 12

R39 y1 H 3 y2 ≥ # R#9 y1 H F y2 ≥ F y1> y2 irrestricta

y1 es irrestricta> pero además está Pdominada por y1 ≥ F> la restricción

dual asociada con R#> entonces al eliminar la redundancia el modelo es9*inimi'ar h K 1F y1 H 8 y2

su"eto a9 y1 H 2 y2 ≥ )

2 y1 @ y2 ≥ 12 y1 H 3 y2 ≥ #

y1 ≥ F> y2 irrestricta

$ual.inal

7/21/2019 Unidad_1


123

=nidad 2

(rogramación :ineal,plicaciones

2B1 *odelo de &ransporte

7/21/2019 Unidad_1


12#

El o!"etivo general es encontrar el me"or plan de distri!ución> esdecir> la cantidad 7ue se de!e enviar por cada una de las rutasdesde los puntos de suministro /asta los puntos de demandaB

El Pme"or plan es a7uel 7ue minimi'a los costos totales de env%o>

produ'ca la mayor ganancia u optimice alg0n o!"etivo corporativoBe de!e contar con9

i4 ivel de oerta en cada uente y la cantidad de demanda

en cada destinoBii4 +osto de transporte unitario de mercader%a desde cada

uente a cada destinoB

=.7 (odelo de Transporte

7/21/2019 Unidad_1


12)

&am!ién es necesario satisacer ciertas restricciones9

1B o enviar más de la capacidad especiicada desde cada punto desuministro oerta4B

2B Enviar !ienes solamente por las rutas válidasB3B +umplir o eAceder4 los re7uerimientos de !ienes en los puntos

de demandaB


Es7uemáticamente se podr%a ver como se muestra en la siguiente

Gráficamente: Para m fuentes y n destinos

7/21/2019 Unidad_1


12

Es7uemáticamente se podr%a ver como se muestra en la siguienteigura

Destinos;&entes1 1

22

n

m = n i d a d e s d e d e m a n d a

= n i d a d e s

d e o e r t a

s2

sm

d2

s1d1

dn

Ri"9 cantidad transportada desde la uente i al destino "

+11> R11

+mn> Rmn

+i"9 +osto del transporte unitario desde la uente i al destino "donde

*odelo general de (: 7ue representa al modelo de &ransporte


7/21/2019 Unidad_1


126

o x

d x

s x

xc A

ij

j

m

i

ij

i

n

jij

m

i

n

j

ijij

≥

≥

≤

=

∑

∑

∑∑

=

=

= =

1

1

1 1

jB7*=*...*n

iB7*=*...*m

El modelo implica 7ue al menos la oerta de!e ser igual a la demanda

para toda i y j

minimizar

s aa

*odelo general de (: 7ue representa al modelo de &ransporte


7/21/2019 Unidad_1


128

*odelo de transporte e7uili!rado9 Oerta K $emanda

i

n

j

ij S x =∑=1

jB7* =* *....*n j

m

i

ij 5 x =∑=1

iB7* =* *....*m

F≥ij x para toda i y j

,plicaciones del modelo de &ransporte


7/21/2019 Unidad_1


12

El *odelo de &ransporte no sólo es aplica!le al movimiento de productos> sino 7ue tam!ién> como modelo se puede aplicar a otrasáreas tales como9

• (laniicación de la (roducción

• +ontrol de Inventarios

• +ontrol de (roveedores

• Otras

E"emplo9


7/21/2019 Unidad_1


-(< tiene cuatro plantas ensam!ladoras en EuropaB Estánu!icadas en :eip'ig> ,lemania 14Xancy> .rancia 24X :ie"a>5élgica 34> y &il!urgo> Molanda #4B :as má7uinasensam!ladoras usadas en estas plantas se producen en Estados

=nidos y se em!arcan a EuropaB :legaron a los puertos de,msterdan 14> ,m!eres 24 y El Mavre 34B

:os planes de producción del tercer trimestre "ulio aseptiem!re4 ya /an sido ormuladosB :os re7uerimientos la

demanda en destinos4 de motores diesel E@# son lossiguientes9

(lanta +antidad de *otores14 :eip'ig #FF


7/21/2019 Unidad_1


4 p g24 ancy FF

34 :ie"a 2FF#4 &il!urgo )FFTotal 4,,,

(uerto +antidad de *otores

14 ,msterdan )FF

24 ,m!eres 6FF

34 El Mevre 8FF

Total 4,,,

:a cantidad disponi!le de má7uinas E@# en los puertosoerta enor%genes4 son9

:os costos U4 de transporte de un motordesde un origen a un destino son9


7/21/2019 Unidad_1


132

$esde elorigen

1 2 3 #

1 12 13 #

2 # 1F 11

3 1F 12 #

,l destino

3- #ariables de decisión+onstrucción del modelo de (:


7/21/2019 Unidad_1


133

Ri" K n0mero de motores enviados del puerto i a la planta "

i K 1> 2> 3

" K 1> 2> 3> #

4- ;&nción Ob=eti1o

*inimi'ar N K 12 R11 H 13 R12 H #R13 H R1# H R21 H #R22 H

1FR23 H 11R2# H 1FR31 H R32 H 12R3# H #R1#

14 Oerta9 :a cantidad de elementos enviados no puede eAceder lacantidad disponi!le

/- Restricciones:=.7 (odelo de Transporte

7/21/2019 Unidad_1


13#

R11 H R21 H R31 ≥ #FFR12 H R22 H R32 ≥ FF

R13 H R23 H R33 ≥ 2FF

R1# H R2# H R3# ≥ )FF

pR11 H R12 H R13 H R1# ≤ )FF

R21 H R22 H R23 H R2# ≤ 6FF

R31 H R32 H R33 H R3# ≤ 8FF

24 $emanda9 $e!e satisacerse la demanda de cada planta

Ri" ≥ F para iK1> 2> 3X "K 1> 2> 3> #y de no negatividad

l ió d l * d l d


7/21/2019 Unidad_1


olución del *odelo de

&ransporte

,lgoritmos Espec%icos


7/21/2019 Unidad_1


13

,lgoritmos Espec%icos

2B1B1 -egla de la es7uina noroeste *E4

2B1B2 *étodo por aproAimación de Gogel *,G4

2B1B3 *étodo del costo m%nimo *+*42B1B# *étodo del paso secuencial y

2B1B) $I*O método de distri!ución modiicada4

$escripción de los algoritmos=.7 (odelo de Transporte

7/21/2019 Unidad_1


136

:a regla de la es7uina noroeste> el método de aproAimación

de Gogel y el método del costo m%nimo son alternativas paraencontrar una solución inicial acti!leB

El método del escalón y el $I*O son alternativas para proceder de una solución inicial acti!le a la óptimaB

(or tanto> el primer paso es encontrar una solución inicialacti!le> 7ue por deinición es cual7uier distri!ución deoertas 7ue satisaga todas las demandas

$escripción de los algoritmos=.7 (odelo de Transporte

7/21/2019 Unidad_1


138

=na ve' o!tenida una solución !ásica acti!le> el algoritmo

procede paso a paso para encontrar un me"or valor para launción o!"etivoB

:a solución óptima es una solución acti!le de costo m%nimo

(ara aplicar los algoritmos> primero /ay 7ue construir unata!la de transporteB

&a!la Inicial=.7 (odelo de Transporte

7/21/2019 Unidad_1


13

@estinosCrien 1 2 3 - n C4ertas

1 !11 !12 !13 !1- #### !1n

2 !21 !22 !23 !2- #### !2n

3 !31 !32 !33 !3- #### !3n

### #### ##### #### #### ####

m !m1 !m2 !m3 !m- #### !mn

@emanda

&a!la Inicial del E"emplo=.7 (odelo de Transporte

7/21/2019 Unidad_1


1#F

PlantasPuertos 1 2 3 - C4erta

1 12 13 - 6

500

2 6 - 10 11

D003 10 E 12 -

800

@emanda -00 E00 200 500 2000

2B1B1 -egla de la es7uina oroeste=.7 (odelo de Transporte

7/21/2019 Unidad_1


1#1

e inicia el proceso desde la es7uina i'7uierda superior

e u!ican tantas unidades como sea posi!le en la ruta

+antidad de =nidades K *%nimodisponi!ilidad> demanda4

:as siguientes asignaciones se /acen o !ien recorriendo /acia laderec/a o !ien /acia a!a"oB

:as demandas se satisacen recorriendo sucesivamente de

i'7uierda a derec/a y las oertas se destinan recorriendo dearri!a /acia a!a"oB

(rimera asignación


7/21/2019 Unidad_1


1#2


1 12 13 - 6

-00 100 500

2 6 - 10 11D00

3 10 E 12 -

800

@emanda 0 -00 E00 200 500 2000

7/21/2019 Unidad_1


Es7uina oroeste9 olución inal acti!le


7/21/2019 Unidad_1


1##


1 12 13 - 6

-00 100 100 500

2 6 - 10 11D00 0 D00

3 10 E 12 -

100 200 500 0 800

@emanda 0 -00 0 E00 200 500 2000

Galor .O9 #FFL12H1FFL13H6FFL#H1FFLH2FFL12H)FFL#K U1#B2FF

2B1B2 *étodo de aproAimación deGogel *,G4


7/21/2019 Unidad_1


1#)

Gogel *,G4*,G usa inormación de costos mediante el concepto decosto de oportunidad para determinar una solución inicialacti!leB

eleccionar en una ila la ruta más !arata y la 7ue le sigueB

Macer su dierencia penalidad 4> 7ue es el costo adicional porenviar una unidad desde el origen actual al segundo destino yno al primeroB

En nuestro caso> para el puerto1> +13 y +1#X (enalidad K @ #

*,G asigna un costo de penalidad por no usar la me"or rutaen esta ilaB

2B1B2 *étodo de aproAimación de Gogel:o anterior se repite para cada ila y cada columna> esto es>


7/21/2019 Unidad_1


1#

determinar todas las penalidades

:os pasos iterativos de *,G son los siguientes9

3- Identiicar la ila o columna con la máAima penalidadB

4B+olocar la máAima asignación posi!le a la ruta no usada 7ue

tenga menor costo en la ila o columna seleccionada en el punto1 los empates se resuelven ar!itrariamente4

/B -ea"ustar la oerta y demanda en vista de esta asignaciónB

0B Eliminar la columna en la 7ue /aya 7uedado una demanda F ola ila con oerta F4> de consideraciones posterioresB

+B +alcular los nuevos costos de penalidadB

2B1B2 *étodo de aproAimación de Gogel=.7 (odelo de Transporte

7/21/2019 Unidad_1


1#6

El *,G contin0a aplicando este proceso en orma sucesiva/asta 7ue se /aya o!tenido una solución acti!leB

:os resultados o!tenidos se muestran en las siguientes ta!las

2B1B2 *étodo de aproAimación de Gogel(aso F9 +álculo de penalidades


7/21/2019 Unidad_1


1#8

Plantas

Puertos 1 2 3 - C4erta Penalidades1 12 13 - 6 2

500

2 6 - 10 11 2

D00

3 10 E 12 - 5

800

@emanda -00 E00 200 500 2000

Penalidades - 5 6 2

+alculadas todas las penalidades> la mayorcorresponde a la columna 3 penalidad K 4

(aso 19 Identiicar máAima penalidad ila o columna4

2B1B2 *étodo de aproAimación de Gogel(aso 29 ,signación de unidades *Ioerta>demanda44


7/21/2019 Unidad_1


1#

(aso 39-ea"uste de oerta y demanda

Plantas

Puertos 1 2 3 - C4erta

1 12 13 - 6

200 300 5002 6 - 10 11

D00

3 10 E 12 -

800

@emanda -00 E00 0 200 500 2000

2B1B2 *étodo de aproAimación de Gogel

(aso #9 Eliminar columna ila4 con demanda oerta4 F(aso #9 Eliminar columna ila4 con demanda oerta4 F


7/21/2019 Unidad_1


1)F

4 4 4 4

Plantas


1 12 13 - 6

200 300 500

2 6 - 10 11D00

3 10 E 12 -

800

@emanda -00 E00 0 200 500 2000

2B1B2 *étodo de aproAimación de Gogel(aso )9 +alcular los nuevos costos de penalidad


7/21/2019 Unidad_1


1)1

Plantas

Puertos 1 2 3 - C4erta Penalidades

1 12 13 - 6 6

200 300 500

2 6 - 10 11 2

D003 10 E 12 - 5

800

@emanda -00 E00 0 200 500 2000

Penalidades - 5 2

2B1B2 *étodo de aproAimación de Gogel-epitiendo los pasos anteriores> inalmente se llega a la siguiente


7/21/2019 Unidad_1


1)2

solución

Plantas


1 12 13 - 6

200 300 300 500

2 6 - 10 11

D00 0 D003 10 E 12 -

-00 200 200 600 800

@emanda -00 E00 0 200 200 500 2000

¿Es solución acti!le? ¿m H n @ 1 K ? I

+osto9 2FFL#H3FFLH6FFL#H#FFL1FH2FFLH2FFL# K U12BFFF

7/21/2019 Unidad_1


2B1B3B *étodo del +osto *%nimo contB4E"emplo9 ,plicar *+* a la ta!la de transporte


7/21/2019 Unidad_1


1)#


1 12 13 - 6

500

2 6 - 10 11

D003 10 E 12 -

800

@emanda -00 E00 200 500 2000

=nidades a asignar K *I2FF>#FF4 K 2FF

EAisten tres rutas costo m%nimoB Eli"amos la 13(aso 2

2B1B3B *étodo del +osto *%nimo contB4(aso 39 &ac/ar ila o columna columna 34


7/21/2019 Unidad_1


1))


1 12 13 - 6

200 300 500

2 6 - 10 11

D00

3 10 E 12 -

800

@emanda -00 E00 0 200 500 2000

,0n 7uedan más de una ila o columna sin tac/arB Ir a paso 2

,"ustar oertas y demandas ila 1 y columna 34

(aso )

(aso #

7/21/2019 Unidad_1


7/21/2019 Unidad_1


2B1B3B *étodo del +osto *%nimo contB4(aso 29 -uta de costo menor @ 32

=nidades K *I2FF>3FF4 K 2FF


7/21/2019 Unidad_1


1)8

(aso #9 &ac/ar a"ustar ila 3 y columna 2


1 12 13 - 6

200 300 500

2 6 - 10 0

D00 0 D00

3 10 E 12 - 100

200 500 300 800

@emanda -00 200 E00 0 200 0 500 2000

,0n 7uedan más de una ila o columna sin tac/arB Ir a paso 2(aso )

> 4(aso 39 &ac/ar columna 2


=nidades K *I#FF>1FF4 K 1FF


7/21/2019 Unidad_1


1)



1 12 13 - 6

200 300 500

2 6 - 10 0

D00 0 D00

3 10 E 12 - 100 0

100 200 500 300 800

@emanda 300 -00 200 E00 0 200 0 500 2000

,0n 7uedan más de una ila o columna sin tac/arB Ir a paso 2(aso )

> 4(aso 39 &ac/ar ila 3


=nidades K *I3FF>3FF4 K 3FF


7/21/2019 Unidad_1


1F



1 12 13 - 6 0

300 200 300 500

2 6 - 10 0

D00 0 D00

3 10 E 12 - 100 0

100 200 500 300 800

@emanda 300 -00 200 E00 0 200 0 500 2000

Queda sólo una ila sin tac/arB &erminar (aso )

> 4(aso 39 &ac/ar ila 1 ó columna 1 sólo una de ellas4

2B1B3B *étodo del +osto *%nimo contB4¿Es solución acti!le? ¿m H n @ 1 K ? I


7/21/2019 Unidad_1


11

+omparación de los resultados

+osto9 3FFL12H2FFL#H6FFL#H1FFL1FH2FFLH)FFL# K U12BFFF

*étodo -utas +osto *E U1#B2FF *,G U12BFFF *+* U12BFFF

:os tres métodos entregan soluciones !ásicas acti!les> pero ninguno asegura 7ue la solución sea óptimaB

+onclusión

2B1B#B *étodo de (asos ecuenciales.undamento


7/21/2019 Unidad_1


12

Este método comien'a con una solución inicial acti!leB

En cada paso se intenta enviar art%culos por una ruta que

no se .a5a usado en la solución acti!le actual> en tantose elimina una ruta usada actualmenteB

En cada cam!io de ruta de!e cumplirse 7ue91B :a solución siga siendo acti!le y

2B Que me"ore el valor de la unción o!"etivo

El procedimiento termina cuando no /ay cam!io de rutas7ue me"oren el valor de la unciónB

2B1B#B *étodo de pasos secuenciales contBB4

=sar la solución actual *E *,G o *+*4 para crear una

Al$oritmo


7/21/2019 Unidad_1


13

=sar la solución actual *E> *,G o *+*4 para crear unatrayectoria 0nica del paso secuencialB =sar estas trayectorias

para calcular el costo marginal de introducir a la solucióncada ruta no usadaB

i todos los costos marginales son iguales o mayores 7ue

cero> terminarX se tendrá la solución óptimaB i no> elegir lacelda 7ue tenga el costo marginal más negativo empates seresuelven ar!itrariamente4

=sando la trayectoria del paso secuencial> determine el

máAimo n0mero de art%culos 7ue se pueden asignar a la rutaelegida en el punto 2 y a"ustar la distri!ución adecuadamenteB

-egrese al paso 1

1

2

3

#

2B1B#B *étodo de pasos secuenciales contBB4Al$oritmo (aso 1


7/21/2019 Unidad_1


1#

a4 (onga un signo 8 en la celda de interés no ocupada

!4 (onga un signo 7 en una celda usada de la misma ila

c4 (onga un 8 en una celda usada de la misma columna

El proceso contin0a alternando los signos 8 y 7 tanto en las ilascomo en las columnas /asta 7ue se o!tenga una sucesión deceldas #ra5ec#oria4 7ue satisagan dos condiciones

1B May un signo 8 en la celda desocupada original de interés> y2B +ual7uier ila o columna 7ue tenga un signo 8 de!e tener

tam!ién un signo 7 y viceversaB



7/21/2019 Unidad_1


1)

Plantas


1 12 13 - 6

-00 100 100 500

2 6 - 10 11D00 0 D00

3 10 E 12 -

100 200 500 0 800

@emanda 0 -00 0 E00 200 500 2000

Soluci$n b;sica #actible obtenida aplicando el método de la 3s"uina :oroeste



7/21/2019 Unidad_1


1


1 12 13 - 6

-00 100 * ( 100 500

2 6 - 10 11

D00 0 D00

3 10 E 12 -

100 ( 200 * 500 0 800

@emanda 0 -00 0 E00 0 200 0 500 2000

&rayectoria 19 H+13@+12H+32@+33


Plantas


7/21/2019 Unidad_1


16

Plantas


1 12 13 - 6-00 100 * ( 100 500

2 6 - 10 11

D00 0 D00

3 10 E 12 -

100 ( 200 * 500 0 800

@emanda 0 -00 0 E00 0 200 0 500 2000

19 H#4@134H4@124K @12 29 H4@134H4@#4 K @2

39 H4@#4H134@124K 3 #9 H1F4@#4H4@124 K 3

)9 H114@#4H4@#4 K 12 9 H1F4@4H134@124K 2

+ostos de las &rayectorias



7/21/2019 Unidad_1


18

19 H#4@134H4@124K @12 29 H4@134H4@#4 K @2

39 H4@#4H134@124K 3 #9 H1F4@#4H4@124 K 3

)9 H114@#4H4@#4 K 2 9 H1F4@4H134@124K 2

:a solución acti!le O es óptima ``

e selecciona la trayectoria 1 costo marginal más negativo4

2B1B#B *étodo de pasos secuenciales contBB4

Al$oritmo (aso 3 <eneración de la nueva ta!la4


7/21/2019 Unidad_1


1

¿+uántas unidades se pueden asignar a la ruta elegida?

,cción -uta =nidades disponi!les en

celdas decrecientes,umentar 1 unidad 13

$isminuir 1 unidad 12 1FF

,umentar 1 unidad 32


2B1B#B *étodo de pasos secuenciales contBB4Al$oritmo (aso 3 <eneración de la nueva ta!la4


7/21/2019 Unidad_1


16F

Plantas


1 12 13 - 6

-00 * 100 ( 100 500

2 6 - 10 11D00 0 D00

3 10 E 12 -

200 ( 100 * 500 0 800

@emanda 0 -00 0 E00 0 200 0 500 2000

+osto9 U13BFFF+osto9 U13BFFF

2B1B#B *étodo de pasos secuenciales contBB4Al$oritmo (aso #


7/21/2019 Unidad_1


161

Golver al (aso 19(ara cada trayectoria evaluar costo marginal

Plantas


1 12 13 - 6-00 100 100 500

2 6 - 10 11

D00 0 D00

3 10 E 12 -

200 100 500 0 800@emanda 0 -00 0 E00 0 200 0 500 2000

2B1B#B *étodo de pasos secuenciales contBB4Al$oritmo (aso 29 Elección de +*g menor


7/21/2019 Unidad_1


162

Plantas

Puertos 1 2 3 - C4erta1 12 13 - 6

-00 (12 100 (10 100 500

2 6 - 10 11

*E D00 (3 (12 0 D00

3 10 E 12 -*10 200 100 500 0 800

@emanda 0 -00 0 E00 0 200 0 500 2000

:a celda más negativa es c 31 @1F4 y la trayectoria es9+31 ; +33 H +13 ; +11



7/21/2019 Unidad_1


163

¿+uántas unidades se pueden asignar a la ruta elegida?

,cción -uta =nidades disponi!les enceldas decrecientes

,umentar 1 unidad 31


,umentar 1 nidad 13

$isminuir 1 unidad 11 #FF



7/21/2019 Unidad_1


16#

+osto9 U12BFFF+osto9 U12BFFF


1 12 13 - 6

300 200 100 500

2 6 - 10 11

D00 0 D00

3 10 E 12 -

100 200 500 0 800

@emanda 0 -00 0 E00 0 200 0 500 2000

2B1B#B *étodo de pasos secuenciales contBB4Al$oritmo (aso #


7/21/2019 Unidad_1


16)

Golver al (aso 19(ara cada trayectoria evaluar costo marginal

Plantas


1 12 13 - 6

300 200 100 500

2 6 - 10 11

D00 0 D00

3 10 E 12 -

100 200 500 0 800

@emanda 0 -00 0 E00 0 200 0 500 2000

7/21/2019 Unidad_1


2B1B)B *étodo de $istri!ución *odiicada $I*O4Al$oritmo

1 =sar la solución actual E *,G o *+*4 y las siguientes


7/21/2019 Unidad_1


166

1B =sar la solución actual E> *,G o *+*4 y las siguientes

operaciones a4 y !4 para determinar el costo marginal de enviarmaterial para cada una de las rutas no usadasB

&sociar a cada #ila un +ndice ui y a cada columna un +ndice j

a4 Macer u1 K FB Encuéntrese los %ndices de las ilas u2> BBB> um y los%ndices de las columnas v1> BBBB> vn tales 7ue ci" K ui H v " para cadacelda usadaB

!4 ea ei" K ci" @ uiHv "4 para cada celda no usadaX ei" será el costo

marginal de introducir la celda ruta4 i> " a la soluciónB

:os pasos 2 a # son los mismos 7ue en el método secuencialB

2B1B)B *étodo de $istri!ución *odiicada $I*O4=.7 (odelo de Transporte

7/21/2019 Unidad_1


168

Aplicar el al$oritmo al problema en est&dio >comparar res&ltados obtenidos con los métodosanteriores

Comentar res&ltados

?&é e.plica @&e e.istan dos sol&cionesóptimas actibles

2B1B)B *étodo de $istri!ución *odiicada $I*O4Aplicación

Plantas

v "


7/21/2019 Unidad_1


16

!osto por

Futa en uso motor 6$. cuaci&n

11 12 u1 ( 1 , 12

12 13 u1 ( 2 , 13

22 - u2 ( 2 , -

32 E u3 ( 2 , E

33 12 u3 ( 3 , 12

3- - u3 ( - , -


1 12 13 - 6-00 100 100 500

2 6 - 10 11

D00 0 D00

3 10 E 12 -100 200 500 D00 800

@emanda 0 -00 0 E00 200 500 2000

(aso F9 ,sociar %ndices

ui

2B1B)B *étodo de $istri!ución *odiicada $I*O4

(aso1Ba4 Sol&cionar la ec&ación


7/21/2019 Unidad_1


18F

EAisten ecuaciones y siete varia!les entonces se /ace u1 K Fpuede ser cual7uiera4 y se determina el resto de los %ndices

v1 K 12 v2 K 13 u2 K @ u3 K @# v3 K 1 v# K 8

(aso 1B!4 +alcular los costos marginales para cada celda no usadaB

ei" K ci" @ ui H v "4

2B1B)B *étodo de $istri!ución *odiicada $I*O4+ostos marginales para las celdas no usadasB

e K c @ u H v 4


7/21/2019 Unidad_1


181

ei" ci" ui H v "4

14 e13 K c13 @ u1 H v34K # @ F H 14 K @12

24 e1# K c1# @ u1 H v#4K @ F H 84 K @2

34 e21 K c21 @ u2 H v14K @ @ H 134 K 2#4 e23 K c23 @ u2 H v34K 1F @ @ H 14 K 3

)4 e2# K c2# @ u2 H v#4K 11 @ @ H 84 K 12

4 e31 K c31 @ u3 H v14K 1F @ @# H 124 K 2

2B1B)B *étodo de $istri!ución *odiicada $I*O4Plantas



7/21/2019 Unidad_1


182

1 12 13 - 6

-00 100 -12 -2 100 500

2 6 - 10 11

2 D00 3 12 0 D00

3 10 E 12 -

2 100 200 500 D00 800@emanda 0 -00 0 E00 200 500 2000

(aso 29 (rue!a de OptimalidadB

May costos negativos por lo tanto no es óptima

:a ruta de reasignación es9 H+13 @+33 H+32 @+12 más negativo> @124

2B1B)B *étodo de $istri!ución *odiicada $I*O4(aso 39 ,signación de unidades a la ruta elegidaB

=nidades disponi!les a mover9


7/21/2019 Unidad_1


183

p

$isminuir 1 unidad +12 1FF$isminuir 1 unidad +33 2FF

Plantas


1 12 13 - 6-00 100 100 500

2 6 - 10 11

D00 0 D00

3 10 E 12 -200 100 500 D00 800

@emanda 0 -00 0 E00 200 500 2000

2B1B)B *étodo de $istri!ución *odiicada $I*O4Guelta al (aso 19

!osto por

$


7/21/2019 Unidad_1


18#

Futa en uso motor $. cuaci&n

11 12 u1 ( 1 , 1213 - u1 ( 3 , -

22 - u2 ( 2 , -

32 E u3 ( 2 , E

33 12 u3 ( 3 , 12

3- - u3 ( - , -


e /acer u1 K F y se determina el resto de los %ndices

v1 K 12 v2 K 1 v3 K # v# K @# u2 K 3 u3 K 8

(aso 1B!4 +alcular los costos marginales para cadacelda no usadaB ei" K ci" @ ui H v "4


ei" K ci" @ ui H v"4


7/21/2019 Unidad_1


18)

ei" ci" ui v "4

14 e12 K c12 @ u1 H v24K 13 @ F H 14 K 12

24 e1# K c1# @ u1 H v#4K @ F @ #4 K 1F

34 e21 K c21 @ u2 H v14K @ 3 H 124 K @#4 e23 K c23 @ u2 H v34K 1F @ 3 H #4 K 3

)4 e2# K c2# @ u2 H v#4K 11 @ 3 @ #4 K 12

4 e31 K c31 @ u3 H v14K 1F @ 8 H 124 K @1F



1 12 13 ( - 6


7/21/2019 Unidad_1


18


May costos negativos por lo tanto no es óptima

:a ruta de reasignación es9 H+31 @+33 H+13 @+11

1 * 12 13 ( - 6

-00 1E 100 1 100 5002 6 - 10 11

0 D00 3 12 0 D00

3 ( 10 E * 12 -

*1 200 100 500 D00 800@emanda 0 -00 0 E00 200 500 2000

2B1B)B *étodo de $istri!ución *odiicada $I*O4(aso 39 ,signación de unidades a la ruta elegidaB

=nidades disponi!les a mover9


7/21/2019 Unidad_1


186

$isminuir 1 unidad +11 #FF$isminuir 1 unidad +33 1FF

Plantas


1 12 13 - 6300 200 100 500

2 6 - 10 11

D00 0 D00

3 10 E 12 -100 200 500 D00 800

@emanda 0 -00 0 E00 200 500 2000

2B1B)B *étodo de $istri!ución *odiicada$I*O4Guelta al (aso 19!osto por

F t t $. i&


7/21/2019 Unidad_1


188


u1 K F y se determina el resto de los %ndices

v1 K 12 v2 K 11 v3 K # v# K u2 K @ 6 u3 K @2

(aso 1B!4 +alcular los costos marginales para cadacelda no usadaB ei" K ci" @ ui H v "4

Futa en uso motor $. cuaci&n

11 12 u1 ( 1 , 1213 - u1 ( 3 , -

22 - u2 ( 2 , -

31 10 u3 ( 1 , 10

32 E u3 ( 2 , E

3- - u3 ( - , -


ei" K ci" @ ui H v"4


7/21/2019 Unidad_1


18

i" i" i "4

14 e12 K c12 @ u1 H v24K 13 @ F H 114 K 2

24 e1# K c1# @ u1 H v#4K @ F H 4 K F

34 e21 K c21 @ u2 H v14K @ @6 H 124 K 1#4 e23 K c23 @ u2 H v34K 1F @ @6 H #4 K 13

)4 e2# K c2# @ u2 H v#4K 11 @ @6 H 4 K 12

4 e33 K c33 @ u3 H v34K 12 @ @2 H #4 K 1F



1 12 13 - 6


7/21/2019 Unidad_1


1F


o /ay costos negativos por lo tanto es óptima

GO K 3FFL12H2FFL#H6FFL#H1FFL1FH2FFLH)FFL#KU12BFFF

1 12 13 - 6

300 0 200 0 100 5002 6 - 10 11

1 D00 13 12 0 D00

3 10 E 12 -

100 200 10 500 D00 800@emanda 0 -00 0 E00 200 500 2000

Ger &ransporte -(< E7uili!rio

2B1BB *odelo de &ransporte9 ituaciones Especiales


7/21/2019 Unidad_1


11

1B olución en pro!lemas de maAimi'ación de transporte

2B El caso en 7ue la oerta eAcede a la demandaB

3B Eliminación de rutas inacepta!lesB

#B $egeneración en pro!lemas de transporteB

)B (ropiedades especiales del modelo de transporte



7/21/2019 Unidad_1


12

1B olución en pro!lemas de maAimi'ación de transporteB

a4 e utili'an los !eneicios marginales en lugar de los costosBe asignará unidades a la celda 7ue tenga el mayor valormarginal y el procedimiento concluirá cuando todas las rutastengan valores marginales nega#i"osB

!4 +onvertir la ta!la de !eneicios en una ta!la de costo9 e !usca el !eneicio mayor> en cada celda se le resta al mayorel !eneicio de la celdaB E"emplo9


&a!la de !eneicios


7/21/2019 Unidad_1


13

1- 1E 12

1D 1E 15

16 20 11

6 1 8

3 1 5

- 0 E

2

3

@estinos

G u e n t e s

1 2 3

1

@estinos

1 2 3

G u e n t e s

1

2

3

*ayor K 2F

&a!la de costo


2B El caso en 7ue la oerta eAcede a la demandaB


7/21/2019 Unidad_1


1#

e utili'a un destino icticio en la ta!la de transporteB econsidera como nulo el costo de enviar una unidad a dic/odestino desde cada una de las uentes or%genes4B

i la demanda es mayor 7ue la oerta el pro!lema no tiene

solución acti!le> sin em!argo el administrador podr%aa!astecer toda la demanda 7ue sea posi!le a un costom%nimoB

e utili'a un origen icticioB El costo de a!astecer cual7uier

destino desde dic/o origen será ceroB in em!argo podr%a/a!er un cargo por orden no cu!iertaB

Ger &ransporte -(< O$4 y OY$

7/21/2019 Unidad_1




7/21/2019 Unidad_1


1

)B (ropiedades especiales del modelo de transporte

&odo pro!lema de transporte es posi!le resolverlo mediante

algoritmos 7ue usan sólo la adición y la sustracciónB

i todas las oertas y demandas tienen valores enteros en un

pro!lema de transporte> los valores óptimos de las varia!lesde decisión serán tam!ién enterosB

E"ercicios


7/21/2019 Unidad_1


16

uponer 7ue se tienen tres á!ricas *1> *2 y *3 7ue producen3> #8 y 33 toneladas respectivamente> de un cierto producto7ue de!e llevarse a cuatro destinos> $1> $2> $3 y $#> los cualesre7uieren #F> 36> 18 y 2) toneladasB

:os costos están dados por la siguiente ta!la9

1

$1 $2 $3 $#

*1 2 3 1 2

*2 1 # 6

*3 8 # )

<laniicación de la prod&cción:


2

7/21/2019 Unidad_1


18

¿+uánto /ay 7ue producir en cada periodo para satisacer lademanda al m%nimo costo tanto de producción como de

almacena"e4?B

S&p&esto: o eAiste inventario inicial ni inalB

(lantear el pro!lema usando el modelo de transporteB

Encuentre las respuestas usando olverB

ituación9

2B2 *odelo de ,signación

7/21/2019 Unidad_1


1

,signar m tra!a"os o tra!a"adores4 a n má7uinasB

=n tra!a"o i K1> 2> 3 >BBB>m4 cuando se asigna a la má7uina j K1>2>BBBB>n4 incurre en un costo ci"B

El o!"etivo es asignar los tra!a"os a las má7uinas uno a uno almenor costoB

:a ormulación de este pro!lema puede considerarse como uncaso especial del modelo de transporteB

$escripción

:os tra!a"os representan las Puentes y las má7uinas los

7/21/2019 Unidad_1


2FF

Pdestinos:a oerta disponi!le en cada uente es 1 como tam!ién loes la demanda en cada destinoB

ci" es el costo de transportar asignar4 el tra!a"o i a la

má7uina j

El costo puede representar tam!ién caracter%sticas decompetencia de cada tra!a"ador

$escripción

E l t ! " d b i d

7/21/2019 Unidad_1


2F1

En el caso 7ue un tra!a"o no deba ser asignadopor7ue no cumple con los re7uisitos4 a una má7uinaactividad4 en particular> este costo de!e tener unvalor alto *4

En el caso de eAistir dese7uili!rio> esto es> mástra!a"os 7ue má7uinas o más má7uinas 7ue tra!a"os>

/ay 7ue e7uili!rar con má7uinas o tra!a"os iguradosicticios4> logrando de esta orma 7ue m K n

EApresión matemática del modelo

7/21/2019 Unidad_1


2F2

F> si el i@ésimo tra!a"o no se asigna a la "@ésima má7uina1> si el i@ésimo tra!a"o se asigna a la "@ésima má7uina

C i" K

*á7uina1 2 BB n

% 77 % 7= J.. % 7n

% =7 % == J.. % =n

J.. J.. J.. J..% n7 % n= J.. % nn

1

2

BBn

&ra!a"o

3

3

B--3

3 3 B-- 3

(or lo tanto el modelo está dado por9

7/21/2019 Unidad_1


2F3

minimi'ar ' K ∑∑= =

n

i

n

j

ijij xc1 1

su"eto a 11

=∑=

n

j

ij x iK1>2> BBB>n

11

=∑=

n

i

ij x "K1>2>BBn

xi" K F ó !ien 1

E"emplo9

:a gerencia general de -(< e"emplo de transporte4 con sede

7/21/2019 Unidad_1


2F#

g g " p p 4

en 5ruselas> este aWo> como parte de su auditor%a anual> decidió7ue cada uno de sus cuatro vicepresidentes visite e inspeccionecada una de sus plantas de ensam!la"e durante las primeras dossemanas de "unioB :as plantas están u!icadas en :eip'ig,lemania4> ancy .rancia> :ie"a 5élgica4 y &il!urgoMolanda4B

(ara decidir a 7ue vicepresidente enviar a una plantadeterminada> se asignaron puntos puntos costos4 a cada uno de ellos

de acuerdo a su eAperiencia> /a!ilidades lengu%sticas> tiempo7ue durará la inspección y otrosB Estos datos se muestran en lasiguiente ta!la9

E"emplo

P:+=T+

7/21/2019 Unidad_1


2F)

P:+=T+

:eip7i 1. =anc2. :ie"a 3. Tilburo-.

inan7as . 1. 2- 10 21 11

MercadotecniaM. 2. 1- 22 10 15

Cperaciones C. 3. 15 1D 20 1E

PersonalP. -. 11 1E 1- 13

(lantear el modelo de (:

E"emplo9 *odelo de (:

*I N K 2# R11 H 1F R12 H BBB H 1# R#3 H 13 R##

7/21/2019 Unidad_1


2F

su"eto a9a4 Oerta R11 H R12 H R13 H R1# K 1

R21 H R22 H R23 H R2# K 1

R31 H R32 H R33 H R3# K 1

R#1 H R#2 H R#3 H R## K 1

!4 $emanda R11 H R21 H R31 H R#1 K 1

R12 H R22 H R32 H R#2 K 1

R13 H R23 H R33 H R#3 K 1R1# H R2# H R3# H R## K 1

c4 o negatividad Ri" K F iK1>BBB>#> "K1>BBBB>#

7/21/2019 Unidad_1


*étodo M0ngaro9<aso ,9 +onstruir la matri' de asignación

(ara o!tener la solución óptima cada nueva matri' de asignación

7/21/2019 Unidad_1


2F8

de!e satisacer9 'ropiedad 79 &odos los n0meros son no negativos 'ropiedad =9 +ada ila y cada columna tiene al menos una celda con

un valor cero

<aso 39

a4 -educción de ilas9a4 -educción de ilas9 -estar el costo menor de cada ila a la ilacorrespondiente y\o

!4 -educción de columnas9 !4 -educción de columnas9 -estar el costo menor de cada columnaa la columna correspondiente

+on esto se crea una nueva matri' con las propiedades 1 y 2

*étodo M0ngaro9

<aso 49 $eterminar si la matri' es reducida (rue!a de Optimalidad4B

7/21/2019 Unidad_1


2F

&ra'ar el menor n0mero de l%neas rectas so!re las ilas y columnas para cu!rir todos los cerosB

i el n0mero de rectas es igual al n0mero de ilas o columnas se dice7ue esta matri' es reducidaB

i la matri' no es reducida pasar al paso /> sino pasar al paso 0

*étodo M0ngaro9

<aso /9 *ovimiento

7/21/2019 Unidad_1


21F

$e todas las celdas no cru'adas identii7ue una con el menorvalor y /aga lo siguiente9

a4 -estar el valor a cada celda no cru'ada

!4 umar el valor a cada celda de intersección de rectas

Golver al paso 4

*étodo M0ngaro9

< 0 l ió ó ti , i ió 4

7/21/2019 Unidad_1


211

<aso 09 olución óptima ,signación4

(rimero se asigna a las 7ue tengan sólo una alternativa> se vanmarcando y as% sucesivamente

$eterminar el costo9 e suman todos los costos

correspondientes a las asignaciones o sumar todos los pi y 7 "4B

¿Qué valor se o!tiene al sumar todos los valores 7ue se restaronen las reducciones de ilas y columnas?

E"emplo9 ,pli7ue el método M0ngaro al e"emplo

<aso ,9 *atri' de ,signación

7/21/2019 Unidad_1


212

1 2 3 - pi

2- 10 21 11

M 1- 2210

15C 15 1D 20 1E

P 11 1E 1- 13

q "

<aso ,9 *atri' de ,signación

ota9 3n negrita los menores de cada #ila

(aso 19 -educción de ilas y columnas

1 2 3 - pi

1- 0 11 1 10

7/21/2019 Unidad_1


213

M - 12 0 5 10C 0 2 5 - 15

P 0 8 3 2 11

q " 1

1 2 3 - pi

1- 0 11 0 10

M - 12 0 - 10

C 0 2 5 3 15

P0

8 3 1 11q " 1

. i l a s

+ol umnas

(aso 29 $eterminar si la matri' es reducida

1 2 3 - pi

7/21/2019 Unidad_1


21#

1 2 3 - pi

1- 0 11 0 10

M - 12 0 - 10

C 0 2 5 3 15

P 0 8 3 1 11

q " 1

o es reducida9 sólo tres rectas para ser reducida de!en ser #4

Ir al paso 3

(aso 39 *ovimiento eleccionar el menor9 restar a lasno tac/adas> sumar a las intersecciones4

1 2 3 - pi

7/21/2019 Unidad_1


21)

1- 0 11 0 10M - 12 0 - 10

C 0 2 5 3 15

P 0 8 3 1 11

q " 1

1 2 3 - pi

15 0 12 0 10

M - 11 0 3 10

C 0 1 5 2 15

P 0 D 3 0 11

q " 1 ( 1

Golver al paso 2 ``

Iteración paso 29

1 2 3 - pi

7/21/2019 Unidad_1


21

1 2 3 - pi

15 0 12 0 10

M - 11 0 3 10

C 0 1 5 2 15

P 0 D 3 0 11

q " 1 ( 1

e tac/an todos los ceros con cuatro rectas> por tanto es óptima

Ir al paso # ``

(aso #9 ,signación

1 2 3 - pi

15 0 12 0 10

7/21/2019 Unidad_1


216

M - 11 0 3 10C 0 1 5 2 15

P 0 D 3 0 11

q " 1 ( 1

%osto K c12 H c23 H c31 Hc##

K 1FH1FH1)H13 K #8

∑∑ += ji " p%osto

K1F H 1F H 1) H 11 H 1 H 1 K #8

Ger ,signación -(<

*odelo de ,signación9 Otras consideracionesEl modelo de asignación de -(< es un modelo de minimi'aciónen el cual el n0mero de vicepresidentes es igual al n0mero de

plantas> y todas las asignaciones posi!les son acepta!lesB

7/21/2019 Unidad_1


218

+onsideremos a/ora modelos tipo asignación donde no todas lascondiciones anteriores se cumplenB En particular se consideraránsituaciones en las 7ue9

1 May una desigualdad entre el n0mero de Ppersonas porasignar y el n0mero de Pdestinos 7ue re7uieren personasasignadasB

2 May un modelo de maAimi'ación3 EAisten asignaciones inacepta!les

*odelo de ,signación9 Otras consideraciones3- Oertas > demandas desi$&ales

a) Oerta ma>or @&e la demanda

7/21/2019 Unidad_1


21

uponer 7ue el presidente de -(< 7uiere auditar a la planta de&il!urgo> por tanto tendrá 7ue decidir cual de los cuatrovicepresidentes de!e asignar a cada una de las tres plantasrestantesB

Sol&ción: e elimina la restricción 7ue re7uer%a unvicepresidente para &il!urgoB El resultado de este cam!io es 7uela /olgura para uno de los cuatro vicepresidentes será 1 en lanueva solución óptima

Ger ,signación -(< O$4

*odelo de ,signación9 Otras consideraciones3- Oertas > demandas desi$&ales

b) Demanda ma>or @&e la oerta

7/21/2019 Unidad_1


22F

uponer 7ue el vicepresidente de (ersonal tiene 7ue via"ar aIllinois durante la primer semana de "unio> por lo tanto no puede

participar en la auditor%a en EuropaB

Sol&ción: e agrega un vicepresidente icticio igual al modelode transporte4 para o!tener una solución acti!le> pero es claro7ue una de las plantas 7uedará sin auditarB

*odelo de ,signación9 Otras consideraciones4- a> &n modelo de ma.imiEación

:a respuesta de asignación es un !eneicio y no un costo

7/21/2019 Unidad_1


221

E"emplo9 uponga 7ue -(< tiene 7ue asignar vendedores a susterritorios de ventaB

EAisten cuatro personas !ien capacitadas listas para serasignadas y tres territorios re7uieren un nuevo vendedorB =node los vendedores no será asignadoB

En este caso la asignación de un vendedor cual7uiera a un

territorio se mide por el incremento marginal esperado en lacontri!ución de dic/a asignación a las gananciasB

*odelo de ,signación9 Otras consideraciones4- a> &n modelo de ma.imiEación

:a matri' de ganancia es la siguiente

7/21/2019 Unidad_1


222

Contribución del

Vendedor\a

Territorio

1

Territorio

2

Territorio

3

A 40$ 30$ 20$B 18$ 28$ 22$

C 12$ 16$ 20$

D 25$ 24$ 27$

Ger ,signación Gendedores -(<

*odelo de ,signación9 Otras consideraciones/- Sit&aciones con asi$naciones inaceptables

E"emplo9 uponga 7ue el presidente de -(< no tiene

7/21/2019 Unidad_1


223

" p p g 7 p

el menor deseo de 7ue el vicepresidente deOperaciones realice una auditor%a a la (lanta ancyB

Sol&ción: ,signar un costo ar!itrariamente alto a estaPruta> de tal modo 7ue al restar de él cual7uiern0mero inito se o!tiene siempre un valor mayor 7ue

otros n0meros relevantes

Ger ,signación -(< inacepta!le

2B3 *odelo de &rans!ordoste modelo permite @&e las &nidades no 1a>andirectamente desde &n ori$en a &n destinoF sino@&e pasen por nodos intermedios o transitorios-

7/21/2019 Unidad_1


22#

@&e pasen por nodos intermedios o transitorios-

+ada origen> punto intermedio y destino inal se representancomo nodos y se conectan a través de arcos dirigidos

-estricción en cada nodo transitorio9 suma #lujos entrantes B suma #lujos saliente

&am!ién se puede representar por medio de una matri' donde unmi" K 1 cuando eAiste un enlace directo entre el nodo i y el nodo

"X y mi" K F cuando no /ay enlace directo entre estos nodos

*odelo de &rans!ordo9 ,lgoritmo

&niciali/ación: Encuentre un plan de em!ar7ue acti!le 7uesatisaga todas las restricciones de suministro y demanda> al

1

7/21/2019 Unidad_1


22)

mismo tiempo 7ue mantiene un e7uili!rio en todos los nodosde trans!ordoB

Prueba de 8p#imalidad: (rue!e el plan de em!ar7ue actual para ver si es óptimo> es decir> si es el plan 7ue incurre en los

costos totales m%nimosB i es as%> deténgase con la soluciónóptima> sino vaya al paso 3B

,o"imien#os: =se el /ec/o de 7ue el plan de em!ar7ueactual no es óptimo para crear un nuevo plan de em!ar7ue

acti!le con menos costo total 7ue el actualB Gaya al paso 2B

2

3

+onsideraciones9

• 2os pasos del algoritmo son análogos a los del algoritmo de pasos sucesios escal$n@B

7/21/2019 Unidad_1


22

• &anto los nodos origen como los destinos pueden ser a su ve'nodos de trans!ordoB

• ,l igual 7ue el modelo de transporte> puede /a!er dese7uili!rio>en ese caso se agregan uentes o destinos icticios con costo ceroB

• El numero total del sistema está dado por el total de la oerta o dela demandaB

• , cada nodo de trans!ordo se asigna un suministro demanda4

igual a su suministro demanda4 original cero> si no coincideoriginalmente con un destino4 más el total de unidades delsistemaB Esto permite 7ue todas las unidades puedan pasar por unempalme dadoB

E"emplo 19$eterm%nese un programa de em!ar7ue 7ue cu!ra todas lasdemandas a un costo m%nimo total para los datoscorrespondientes al siguiente grao costo en U4B

7/21/2019 Unidad_1


226

3 #

2 #3

6 2

1 3 )

2 #

H) @3F

H6F

H1)

@3F @#)

8

olución

• :os sitios 1 y 2 son or%genes• :os sitios ) y son destinos

7/21/2019 Unidad_1


228

• El sitio 3 es origen y empalme• El sitio # es destino y empalme• :a oerta es mayor 7ue la demanda por tanto se re7uiere un

destino icticio 7ue demande 6) unidades•

,gregar 18F unidades a cada empalme oerta y demanda4• El costo de las unidades 7ue van de un empalme como origen4a él mismo como destino4 y de cual7uier origen al sitio icticioes ceroB

• , las rutas no permitidas se les asocia un valor relativamente

alto por 1BFFF4

:a ta!la inicial es9

7/21/2019 Unidad_1


22

3 - 5 6 C4erta

1 E5

3 1000 8 1000 0

2 D0

2 D 1000 1000 0

3 1E50 3 - - 0

- 180

1000 0 1000 2 0

@emanda 180 210 30 -5 D5

C r ? 5 e n e s

@estinos

:a ta!la inal es9

7/21/2019 Unidad_1


23F

3 - 5 6 C4erta

1 20 75 E5

3 1000 8 1000 0

2 70 D0

2 D 1000 1000 0

3 90 30 30 45 1E50 3 - - 0

- 180 180

1000 0 1000 2 0

@emanda 180 210 30 -5 D5

@estinos

C r ? 5 e n e s

+osto K 2FL3H6)LFH6FL2HFLFH3FL3H3FL#H#)L#H18FLFKU)F

E"emplo 29=na corporación necesita transportar 6F unidades de un producto> del sitio 1 alos sitios 2 y 3 en cantidades de #) y 2) unidades> respectivamenteB :as tariasci" en miles de pesos por unidad4 de carga aérea entre los sitios comunicados

por carguero se dan en la ta!la> en la cual las l%neas punteadas indica 7ue no /ay

7/21/2019 Unidad_1


231

servicio disponi!leB $eterm%nese un programa de em!ar7ue 7ue asigne eln0mero re7uerido de art%culos a cada destino> a un costo m%nimo de transporteB

ing0n em!ar7ue re7uiere de vuelo directo> se permiten los env%os empleando puntos intermediosB

1 2 3 #1 BBBB 38 ) 3#

2 38 BBB 26 BBB

3 ) 26 BBB 1# 3# BBB 1 BBB

E"emplo 39

1

8

1FF

12F

26

odos de trans!ordo

7/21/2019 Unidad_1


232

2

3

#

) 6

1F

11

2FF

1)F

8F

6F

11F

3

#

##

)

)

66

8

8

(lanteamiento del modelo (: 9

Plan#ear el modelo de PL para el eemplo mos#rado en el

gra$o an#erior%

7/21/2019 Unidad_1


233

2B#B *odelos de -edes

7/21/2019 Unidad_1


23#

2B#B1 &eor%a de <raos

2B#B2 *odelo de la -uta más corta2B#B3 *odelo del jr!ol EApandido *%nimo

2B#B# (ro!lema del .lu"o *áAimo

2B#B1 Introducción a la &eor%a de <raos<rao no dirigido9

=n grao no dirigido < consiste en un con"unto G de vértices

7/21/2019 Unidad_1


23)

o nodos4 y un con"unto E de lados ramas o enlaces4 tales 7uecada lado e ! está asociado a un par no ordenado devértices y KB i un lado e está asociado a un 0nico par devértices v y h> entonces eK *K4 o eKK*4B

<rao dirigido9=n grao dirigido o digrao4 < consiste en un con"unto G devértices o nodos4 y un con"unto E de lados o ramas4 tales 7uecada lado e ! está asociado a un par ordenado de vérticesB

i un lado e está asociado a un par ordenado 0nico de vértices y K> se escri!e e B *K@.

7/21/2019 Unidad_1


2B#B1 Introducción a la &eor%a de <raos odo de demanda9

odo 7ue va a reci!ir los productos para cumplir con una

7/21/2019 Unidad_1


236

demanda conocidaB

odo de trans!ordo9 odo 7ue reci!e productos desde otros nodos para sudistri!uciónB

,rco enlace49:%nea de una red 7ue conecta un par de nodosB e le utili'a pararepresentar una ruta válida desde el nodo origen al nodo de

distri!uciónB

2B#B1 Introducción a la &eor%a de <raos,rco dirigido9

Indica el sentido de movimiento de los productosB

7/21/2019 Unidad_1


238

+amino9=na secuencia de nodos en una red unidos por arcos dirigidos ono dirigidos4

&rayectoria la'o49Es un camino cerrado ciclo4 donde el primer nodo es a su ve' el0ltimoB

2B#B1 Introducción a la &eor%a de <raos-epresentación de un grao9

7/21/2019 Unidad_1


23

-epresentación *atricial

i4 *atri' de ,dyacencia

ii4 *atri' de costo !eneicio4

=n grao se puede representar matemáticamente como9

a4 =na matri' !4 =na lista enla'adac4 jr!ol

2B#B1 Introducción a la &eor%a de <raos contB4*atri' de ,dyacencia9

7/21/2019 Unidad_1


2#F

(ara un grao L> es una matri' & de dimensión :x: >donde &Mi*jN es verdadero 14 si> y sólo si> eAiste un arco7ue vaya del vértice i al vértice j. En ausencia de arcodirecto se representa generalmente por FB

E"emplo9$ado el siguiente grao encontrar su matri' deadyacencia

2B#B1 Introducción a la &eor%a de <raos contB421

7/21/2019 Unidad_1


2#1

3 #

1 9 ;

1 3 3

9 3

3; 3

2B#B1 Introducción a la &eor%a de <raos contB4*atri' de +osto9

7/21/2019 Unidad_1


2#2

(ara un grao L eti"uetado> es una matri' % de dimensión :x: > donde &Mi*jN es el costo valor de la eti7ueta4 si> ysólo si> eAiste un arco 7ue vaya del vértice i al vértice j.

En ausencia de arco directo se representa generalmente por in#inito costo eAtremadamente alto> para la

simulación se /ace uso de un valor uera de conteAto4B

E"emplo9$ado el siguiente grao encontrar su matri' de costo

2B#B1 Introducción a la &eor%a de <raos contB421 1F

7/21/2019 Unidad_1


2#3

3#

1 9 ;

1 3, 3+

9 34

4,; +

1) 2F 12

)

2B#B1 Introducción a la &eor%a de <raos contB4

7/21/2019 Unidad_1


2##

(ara un grao no dirigido> tanto la matri' de adyacenciacomo la matri' de costo son simétricas> esto es9

,Si>"T K ,S">iT

ó

+Si>"T K +S">iT

E"emplo Introductorioeymour *iles es el gerente de distri!ución de NighellB Nighelldistri!uye sus motores oruga en cinco estados del medio oesteB (or lo

7/21/2019 Unidad_1


2#)

regular> eymour *iles tiene 1F aparatos E@ in situ en lo 7uedesignaremos como local 1B Estos tractores de!en ser enviados a losdos locales de construcción más importantes designados como 3 y #Be necesitan tres E@ en el local 3 y siete en el local #B $e!ido aitinerarios arreglados con anterioridad> relativos a la disponi!ilidad

de conductores> los tractores solo pueden ser distri!uidos de acuerdocon las rutas alternativas 7ue se muestran en el grao de la iguraB

:a igura tiene un n0mero 83, en el nodo 1> esto signiica 7ue /ay 1F

aparatos E@ disponi!les oerta4B :os indicadores 7/ y 79 asociados alos locales 3 y #> respectivamente> denotan los re7uerimientosdemandas4 de éstosB

3

c3#u#3

c23

@3

u3#c#3

7/21/2019 Unidad_1


2#

1 2 #

)

c12 c2#

c2) c)#

c)3

H1F @6

-utas alternativas para el destino 3

1@2@3> 1@2@#@3> 1@2@)@#@3> 1@2@)@3

u12

u23

u)3

c)#u2)

u2#

:os costos ci" son unitariosB (or e"emplo el costo derecorrer el arco )>34 es c)3 por cada tractorB

7/21/2019 Unidad_1


2#6

$e!ido a los acuerdos sostenidos con los conductores>Nighell de!e cam!iarlos en cada local 7ue se encuentreso!re la rutaB :as limitaciones en la disponi!ilidad deconductores ocasionan 7ue /aya una cota superior en el

n0mero de tractores 7ue pueden recorrer cual7uier arcodadoB

(or e"emplo9 u)3 es la cota superior o capacidad en el arco)>34B

El pro!lema de ygmour consiste en encontrar un plan deem!ar7ue 7ue satisaga la demanda y las restricciones decapacidad a costo m%nimoB

El pro!lema en particular se conoce como modelode trans!ordo con capacidadesB

7/21/2019 Unidad_1


2#8

EApresar el pro!lema como un (:

a4 Garia!les de decisión

Ai" K n0mero total de E@ 7ue se enviarán a travésdel arco i>"4B

K lu"o del nodo i al nodo "

!4 .unción O!"etivo

*I N K+12R12H+23R23H+2#R2#H+2)R2)H+3#R3#H+#3R#3H+)3R)3H+)#R)#

c4 -estricciones

7/21/2019 Unidad_1


2#

la red ?i*j@ dear todos losc x ijij cos>F ≤≤

s aH R12 K 1F

@ R12HR23HR2#HR2) K F

@R23 @R#3 @R)3 HR3# K @3 @R2# HR#3 @R3# @R)# K @6

@R2) HR)3 HR)# K F

5alance

de

lu"o

*atri' Incidencia nodo@arco

a r c o

7/21/2019 Unidad_1


2)F

odo 1>24 2>34 2>#4 2>)4 #>34 )>34 3>#4 )>#4 :$

1 H1 F F F F F F F 1F

2 @1 H1 H1 H1 F F F F F

3 F @1 F F @1 @1 H1 F @3

# F F @1 F H1 F @1 @1 @6

)F F F @1 F H1 F H1 F

;orm&lación General del !odelo de Transbordo con Capacidades C ij denotan el lu"o del nodo i al nodo j a lo largo del arco 7ue

7/21/2019 Unidad_1


2)1

conecta esos nodosB 2j representa la oerta en el nodo j

ijij ij xc∑

sBaB

minimice

n j 2 x x j) )j) j) >BBBB>2>1> ==− ∑∑

la red ?i*j@ dear todos losc x ijij cos>F ≤≤

Resol1er para las si$&ientes capacidades > costos Ca"acidad

de\a #itio 1 #itio 2 #itio 3 #itio 4 #itio 5

#itio 1 10

#itio2 4 3 3

7/21/2019 Unidad_1


2)2

#itio 2 4 3 3#itio 3 2

#itio 4 4

#itio 5 3 5

Coto %nitario

de\a #itio 1 #itio 2 #itio 3 #itio 4 #itio 5

#itio 1 $100

#itio 2 $45 $50 $20

#itio 3 $60

#itio 4 $85

#itio 5 $10 $55

Ger trans!ordo con capacidades

7/21/2019 Unidad_1


2B#B2 *odelo de la -uta más corta

a4 ,lgoritmo9 <rao no dirigido

7/21/2019 Unidad_1


2)#

+onsiderénse todos los nodos 7ue estén directamenteconectados con el origenB Eti7uetarlos con la distancia alorigen y su nodo predecesorB Eti7uetas temporales>

Sdis#ancia+ nodoTB$e entre todos los nodos con eti7uetas temporales>escoger el 7ue tenga la distancia menor y se marca como

permanenteB i todos están con eti7uetas permanentes se

va al paso cuatroB

1

2

2B#B2 *odelo de la -uta más corta <$4

&odo nodo 7ue no tenga eti7ueta permanente> tendrá eti7ueta

l á i i : l 0l i d3

,lgoritmo9

7/21/2019 Unidad_1


2))

temporal o estará sin eti7uetaB ea : el 0ltimo nodo coneti7ueta permanenteB +onsiderénse todas las eti7uetas de losvecinos de : directamente conectados a : mediante unarco4B (ara cada uno de estos nodos calc0lese la suma de su

distancia a :B i el nodo en cuestión no está eti7uetado>as%gnese una eti7ueta temporal 7ue conste de esta distancia yde : como predecesorB i el nodo en cuestión ya tieneeti7ueta temporal> cám!iese sólo si la distancia reciéncalculada es menor 7ue la componente de distancia de laeti7ueta actualB En este caso> la eti7ueta contendrá estadistancia y a : como predecesorB -egresar al paso 2

7/21/2019 Unidad_1


7/21/2019 Unidad_1



olución9

7/21/2019 Unidad_1


2)8

M

1

2

3

#

)

68

#1

1

1

1

2

26

3

33

8>M4

#>M4

)>14

>348>24

>34>#4

>64

ó

19Ger e"emplo 1 -uta mas corta 29 Macer pro!lema 1 gu%a 2 E"emplo 2 -uta mas corta

E

(ara su práctica y e"ercitación neuronal

7/21/2019 Unidad_1


2)

,

6

1 3

5

+

$.

<

1

#

2

1F8

1F

)

6#

3


Es una técnica eA/austiva> esto es> prue!a todas las alternativas

i!l

!4 ,lgoritmo de 5ij)stra

7/21/2019 Unidad_1


2F

posi!lesB

Opera a partir de un con"unto S de vértices cuya distancia máscorta desde el origen ya es conocidaB Inicialmente S contiene sóloel nodo de origenB En cada paso se agrega alg0n vértice restante a S > cuya distancia desde el origen es la más corta posi!leB

(ara cada paso del algoritmo> se utili'a una matri' 5 pararegistrar la longitud del camino más corto a cada vérticeB

2B#B2 *odelo de la -uta más corta <$4,lgoritmo de 5ij)stra

II+IOF4 G K [1> 2> 3> #> BBB> n]14 K [1] \\ nodo 1 se supone 7ue es el origen

24 ( iB= M t n M

7/21/2019 Unidad_1


21

24 (ara iB= Masta n Macer 34 $i K +1i

#4 (ara iB7 Masta n>7 Macer )4 Elegir un vértice K en >S tal 7ue 5K sea un m%nimo

4 agregar K a S

64 (ara cada vértice en >S Macer I $hH+hv4Y$v4 \\(v K h

$v K $hH+hv84 \\$vKm%nimo$v>$hH+hv4

.I

7/21/2019 Unidad_1



Inicial

F4 G K [1> 2> 3> #> )]

14 [1]

7/21/2019 Unidad_1


23

14 K [1]24

34 $2 K 1F> $3 K in> $#K3F> $) K 1FF

#4 Iterar # veces

)4 eleccionar nodo con distancia más corta de >S >

En el e"emplo es el nodo =

Iteración S w 2 3 4 5

<nicial H1I ** 10 in4 30 100


4 ,gregar el nodo = a S 9 K [1>2]

64 Iterar kG@k> G@ K [3>#>)]4

$3 m%nimo$3 $2H+234 m%nimoin 1FH)F4 F

7/21/2019 Unidad_1


2#

$3Km%nimo$3>$2H+234 Km%nimoin>1FH)F4 K F

$#Km%nimo$#>$2H+2#4 Km%nimo3F>1FHin4 K 3F

$)Km%nimo$)>$2H+2)4 Km%nimo1FF>1FHin4 K 1FFIteración S w 2 3 4 5

<nicial H1I ** 10 in4 30 100

1 H1/2I 2 10 60 30 100


2a Iteración

G@ K [3>#>)]

)4 h K #

4 K [1 2 #]

7/21/2019 Unidad_1


2)

4 K [1>2>#]64 Iterar kG@k G@ K [3>)]

$3Km%nimo$3>$#H+#34 Km%nimoF>3FH2F4 K )F

$)Km%nimo$)>$#H+#)4 Km%nimo1FF>3FHF4 K F


<nicial H1I ** 10 in4 30 100

1 H1/2I 2 10 60 30 100

2 H1/2/-I - 10 50 30 E0


3a Iteración

G@ K [3>)]

)4 h K 3

4 K [1 2 # 3]

7/21/2019 Unidad_1


2

4 K [1>2>#>3]64 Iterar kG@k G@ K [)]4

$)Km%nimo$)>$3H+3)4 Km%nimoF>)FH1F4 K FIteración S w 2 3 4 5

<nicial H1I ** 10 in4 30 100

1 H1/2I 2 10 60 30 100

2 H1/2/-I - 10 50 30 E03 H1/2/-/3I 3 10 50 30 60


#a Iteración

G@ K [)]

)4 h K )

4 K [1 2 # 3 )]

7/21/2019 Unidad_1


26

4 K [1>2>#>3>)]64 Iterar kG@k G@ K []4


<nicial H1I ** 10 in4 30 100

1 H1/2I 2 10 60 30 100

2 H1/2/-I - 10 50 30 E0

3 H1/2/-/3I 3 10 50 30 60

- H1/2/-/3/5I 5 10 50 30 60

&a!la .inal

¿+uál es el camino?

(ara conocer el camino /ay 7ue incluir otra matri' ' devértices> tal 7ue ' contenga el vértice inmediato anterior a en el camino más corto

7/21/2019 Unidad_1


28

en el camino más cortoB

e asigna a ' valor inicial 7 para todo ≠ 7

:a matri' ' se actuali'a después de la l+nea FB

i $h H +hv Y $v en la l%nea 8> después se /ace (v K h

,l término de la corrida del algoritmo> el camino a cadavértice puede encontrarse regresando por los vértices

predecesores de la matri' (

¿+uál es el camino?

(ara el e"emplo> la matri' ( de!e tener los valores

(2 K1 (3 K # (# K 1 () K 3

7/21/2019 Unidad_1


2

( K1> ( K #> ( K 1> ( K 3(ara encontrar el camino más corto del vértice 1 al )> se siguenlos predecesores en orden inversoB

3 es el predecesor de )# es el predecesor de 3

1 es el predecesor de #

(ro!lema de los caminos más cortos entretodos los pares de nodos

(ara visuali'ar el pro!lema se emplea un grao dirigido < KG>,4 en el 7ue cada arco → K tiene un costo no negativo+ El pro!lema consiste en encontrar el camino de longitud

7/21/2019 Unidad_1


26F

+v>hB El pro!lema consiste en encontrar el camino de longitudmás corta menor costo4 entre v y h para cada par ordenado devértices v>h4B

,lgoritmo de .loyd

e utili'a una matri' ,> donde ,i" K +i" para toda i≠ "> si noeAiste camino directo entre i y " se supone 7ue +i" K inB +adaelemento de la diagonal se /ace ceroB

'roblema de los caminos m;s cortos entre todos los pares de nodos

$espués se /acen n iteraciones en la matri' ,B

,l inal de la D@ésima iteración ,i" tendrá por valor la longitud

más pe7ueWa de cual7uier camino 7ue vaya desde el vértice i/asta el vértice " y 7ue no pase por un vértice mayor 7ue D

7/21/2019 Unidad_1


261

más pe7ueWa de cual7uier camino 7ue vaya desde el vértice i/asta el vértice " y 7ue no pase por un vértice mayor 7ue DBEsto es> i y "> los vértice eAtremos del camino> pueden sercual7uier vértice> pero todo vértice intermedio de!e ser menoro igual a DB

En la D@ésima iteración se aplica la siguiente órmula paracalcular ,

D@1,i"

D ,i" K minD@1,iD H D@1,D"


(ara calcular ,i"> se compara D@1,i"> el costo de ir de i a " sin pasar por D o cual7uier otro nodo con numeración mayor> con

D@1,iD H D@1,D"> el costo de ir primero de i a D y después de D a ">sin pasar a través de un vértice mayor 7ue DB i el paso por el

vértice D produce un camino más económico 7ue el de D@1,i" se

7/21/2019 Unidad_1


262

vértice D produce un camino más económico 7ue el de D@1,i"> seelige ese costo para D ,i"B

D @ 1 , i D

D@1,i"

D @ 1 , D "

i

D

"


Al$oritmo de ;lo>d \\ e supone 7ue se cuenta con la matri' de costo +

F4 II+IO

14 $esde i K 1 Masta

24 $esde " K 1 Masta

7/21/2019 Unidad_1


263

24 $esde " K 1 Masta 34 ,i" ← +i"

#4 $esde i K 1 Mas ta

)4 ,ii K F4 $esde D K 1 Masta

64 $esde i K 1 Masta

84 $esde " K 1 Masta

4 I ,iD H ,D" Y ,i"41F4 ,i" K ,iD H ,D"

114 .I


Rec&peración de caminos para el Al$oritmo de ;lo>d

+uando es de interés conocer el camino más corto

entre dos vértices /ay 7ue consignarlo en una matri'

7/21/2019 Unidad_1


26#

entre dos vértices> /ay 7ue consignarlo en una matri'

(> donde (i" tiene el vértice D 7ue permitió a .loyd

encontrar el valor menor de ,i"B i (i" es cero> el

camino de i a " es directoB


Al$oritmo de ;lo>d !odiicadoF4 II+IO14 $esde i K 1 Masta 24 $esde " K 1 Masta

34 ,i" ← +i"

7/21/2019 Unidad_1


26)

34 ,i" ← +i"

34 (i" ← F

#4 $esde i K 1 Mas ta )4 ,ii K F

4 $esde D K 1 Masta 64 $esde i K 1 Masta 84 $esde " K 1 Masta 4 I ,

iD

H ,D"

Y ,i"

4

1F4 ,i" ← ,iD H ,D"

1F4 (i" ← D

114 .I


=emplo: ,pli7ue .loyd al grao ponderado mostrado en laigura

8

7/21/2019 Unidad_1


26

12 3

2

8

3

2

)


Sol&ción:

Tabla Inicial

= d 1 2 3

7/21/2019 Unidad_1


266

=odos 1 2 3

1 0 8 5

2 3 0 in4

3 in4 2 0

F,i"


Sol&ción:

Desp&és de la primera iteración

7/21/2019 Unidad_1


268

1,i"

=odos 1 2 3

1 0 8 5

2 3 0 8

3 in4 2 0


Sol&ción:

Desp&és de la se$&nda iteración

= d 1 2 3

7/21/2019 Unidad_1


26

2,i"

=odos 1 2 3

1 0 8 5

2 3 0 8

3 5 2 0


Sol&ción:

Desp&és de la tercera iteración

= d 1 2 3

7/21/2019 Unidad_1


28F

3,i"

=odos 1 2 3

1 0 D 5

2 3 0 8

3 5 2 0

2B#B3 *odelo de ár!ol eAtensión m%nima

=n ár!ol es un grao 7ue tiene sus n nodos értices4

conectados conexo4 con n@1 arcos aristas4> no

$einición 1

7/21/2019 Unidad_1


281

conectados 4 con n 1 arcos 4> noeAistiendo ciclos caminos cerrados4

$einición 2 =n ár!ol de eApansión de costo m%nimo es a7uel en 7uetodos los enlaces tienen longitudes costos4 m%nimas

,lgoritmo para el pro!lema del ár!ol de eApansión m%nimaB

*étodo <ráico

7/21/2019 Unidad_1


282

e selecciona un nodo cual7uiera y se conecta alnodo más cercano a ésteB

e identiica el nodo no conectado más cercano aun nodo conectado y se conectan estos dos nodos

Empates se deciden en orma ar!itrariaB :osempates indican 7ue eAisten soluciones

alternativas para la construcciónB

1

2

ota9

E"emplo9 Encontrar el ,E* para el siguiente grao

7/21/2019 Unidad_1


283

M

1

2

3

#

)

68

#1

1

1

1

2

26

3

33

6

olución 9

7/21/2019 Unidad_1


28#

M

1

2

3

#

)

6

1

1

1

1

2

2

#

,lgoritmo ta!ular (aso ,cción

F e construye la ta!la de costos de enlaces

1 e comien'a ar!itrariamente con cual7uier nodoB e designa a

este nodo como conectado y se pone una marca al lado de la

7/21/2019 Unidad_1


28)

y pila correspondiente al nodoB e tac/a el %ndice de la columna7ue corresponde a élB

2 +onsiderando todas las ilas marcadas> !uscar el m%nimo en lascolumnas cuyo %ndice a0n no /aya sido tac/ado encerrándoloen un c%rculoB $esignándose de esta manera el nuevo nodoconectadoB e tac/a el %ndice de la columna y pone una marcaen la ila correspondiente a este nodoB e repite este paso /asta

7ue todos los nodos estén conectadosB3 :os nodos encerrados en c%rculo identiican el ár!olB

,plicación ,lgoritmo ta!ular

=odo J 1 2 3 - 5 6 D

&a!la inicial

7/21/2019 Unidad_1


28

J - D 8

1 - 6 1

2 6 1 2

3 1 1 1

- D 1 3 3 2

5 2 3 3

6 3 3 1D 8 2 1


Inicio9 odo M

=odo J 1 2 3 - 5 6 D! J - D 8a4

7/21/2019 Unidad_1


286

=odo J 1 2 3 - 5 6 DJ - D 8

! 1 - 6 1

2 6 1 2

3 1 1 1- D 1 3 3 2

5 2 3 3

6 3 3 1D 8 2 1

a4

!4


odo 1

=odo J 1 2 3 - 5 6 D

! J - D 8! 1 - 6 1

a4

7/21/2019 Unidad_1


288

! 1 - 6 1

2 6 1 2

! 3 1 1 1

- D 1 3 3 2

5 2 3 3

6 3 3 1

D 8 2 1

4 !4

c4


"o#o $ 1 2 3 4 5 6 7

! $ 4 D 8

&a!la inal

a4

7/21/2019 Unidad_1


28

$ 4 D 8

! 1 - 6 1

! 2 6 1 2

! 3 1 1 1! 4 D 1 3 3 2

! 5 2 3 3

! 6 3 3 1

! 7 8 2 1

a4

!4

c4

6

,r!ol de eApansión m%nima 9

7/21/2019 Unidad_1


2F

M

1

2

3

#

)

6

1

1

1

1

2

2

#

2B#B# (ro!lema del .lu"o *áAimo

En este pro!lema /ay un solo nodo #uente nodo de

entrada4 y un solo nodo destino nodo de salida4> y elresto son nodos de trans!ordoB El pro!lema consiste en

$escripción

7/21/2019 Unidad_1


21

4 y 4> yresto son nodos de trans!ordoB El pro!lema consiste enencontrar la máAima cantidad de lu"o total petróleo>gas> eectivo> mensa"es> tránsito> etcB4 en una unidad detiempoB

:a cantidad de lu"o por unidad de tiempo en cada arco está limitada por las restricciones de capacidad.

3ste problema se puede representar como una red

dirigida y conexa.

(ara cada nodo interno de!e cumplirse 7ue9 #lujo "ue sale del nodo B #lujo "ue entra al nodo

En términos ormales> siendo 3 la uente y n el

destino el pro!lema consiste en9*,R

$escripción

7/21/2019 Unidad_1


22

p*,R # si i K 1

su"eto a si i K n

8 en otro caso

F ≤ Ai" ≤ ui"> para todos i>"4 de la red

Ai" 9 lu"o por unidad de tiempo por el arco i>"4

ui" 9 capacidad del arco i>"4

9 lu"o total a través de la red

# x x j

ji

j

ij −=− ∑∑

+onsidérese la i@ésima restricción> para alg0nvalor i"o de i> :a suma se considera

so!re toda " para la cual el arco i>"4 con i i"o>

pertene'ca a la redB Entonces> será el lu"o

total 7ue sale del nodo i En orma seme"ante la

$escripción

∑ j

ij x

∑ jij x

7/21/2019 Unidad_1


23

total 7ue sale del nodo iB En orma seme"ante> la

suma se considera so!re toda " para la cual

eAista el arco ">i4 en la red> i i"o4B $e modo 7ue

es el lu"o 7ue entra al nodo i

∑ j

ji x

∑

,ntes de /acer la presentación ormal delalgoritmo> revisemos el siguiente e"emploB

,lgoritmo

2 #

7/21/2019 Unidad_1


2#

2

#

#

3

2

1

1

3 )

<rao inicial9 Iniciali'ación delos lu"os en cada nodo,lgoritmo

FF

2 #

7/21/2019 Unidad_1


2)

+onsideremos un camino desde el nodo 1 al nodo E"emplo9 1@2@)@

#

FF

F

F

F

F

#

12

3

2F

3 )

1

Se dice @&e la cantidad de l&=o a lo lar$o de dicHo

recorrido es $ac#ible si:

o eAcede la capacidad de ning0n arco del camino

+on eAcepción de los nodos 1 y > el lu"o en cada nodo

de!e satisacer la condici$n de conseraci$n

1

2

7/21/2019 Unidad_1


2

La can#idad m!3ima que puede $luir desde la $uen#e a lo

largo de un camino es igual a la menor de las

capacidades de los arcos de dic.o camino,l asignar un lu"o a un arco nos atendremos a las reglas9

1

2

e reduce la capacidad en la dirección del lu"o cantidad de lu"o4

e aumenta la capacidad en sentido opuesto cantidad de lu"o4

E"emplo9 +onsiderar el arco 1@2

&signar dos unidades a este arco4

&plicando las reglas 7 y = se tiene

1 2# F

7/21/2019 Unidad_1


26

e gener$ una capacidad #icticia en la dirección 2@1Enviar una unidad de 2 a 1

1 2 2 422

1 2 1 4

13

7/21/2019 Unidad_1


,plicar el algoritmo al grao del e"emplo9

FF

2 #

(aso Inicial

7/21/2019 Unidad_1


2

#

FF

F

F

F

F

#

12

3

2F

3 )

1

Iteración 19

FF

2 #

Elegir ar!itrariamente el camino 1@3@)@cmin K *I>#>24K2X actuali'ando la red se tiene

7/21/2019 Unidad_1


3FF

#

FF

F

F

F

F

#

12

3

2F

3 )

1

#

2

2 2

F

2

2 2

Iteración 29

2

Elegir ar!itrariamente el camino 1@2@#@cmin K *I#>>4K#X actuali'ando la red se tiene

#

7/21/2019 Unidad_1


3F1

#F

F F

F

F

F

F

F

#

1

2

23

2

2

F

2

3

#

)

1

#

2 F

2

2 #

F

#

#

2

22

Iteración 39

FF

Elegir ar!itrariamente el camino 1@3@2@#@cmin K *I#>3>2>24K2X actuali'ando la red se tiene

#2

7/21/2019 Unidad_1


3F2

#F

F F

F

F

2

F

F

#

12

1

2

F

2

3

#

)

1

2

#F

2

2

8

#

F

2

8

22

#

2

3

F

2 2

#

+álculo de la cantidad de lu"o en cada arco

e determina comparando la capacidad inicial de cada arcocon la capacidad inicialB (ara cada arco la regla es9

i la capacidad inal es menor 7ue la capacidad inicial>l l l di i E t l tid d d l l " t é

7/21/2019 Unidad_1


3F3

calcular la dierenciaB Esta es la cantidad del lu"o a travésdel arcoB

E"emplo9 ,rco 3@)

Inicial

.inal 223 )

F#3 )

.inal Y inicial entonces el lu"o es #@2K4

,plicando la regla anterior a todos los arcos se tiene el

siguiente grao9

#2 #

7/21/2019 Unidad_1


3F#

2

2

8

2

8

#

1

3 )

Unidad /

7/21/2019 Unidad_1


3F)

Administración de <ro>ectos

<RT > C<!

3 ,dministración de (royectos (E-& y +(*4&odo proyecto de!e ser compro!ado y controlado> dado 7ue éstetiene involucrado numerosas tareas interrelacionadasB

, través de algunas técnicas se puede responder a preguntas como9

7/21/2019 Unidad_1


3F

1B ¿+uándo ser%a lo más pronto 7ue el proyecto pudiera estarterminado?

2B (ara cumplir con este tiempo de conclusión> ¿7ué tareas soncr%ticas> en el sentido de 7ue un retraso en cual7uiera de esastareas provoca un retraso en la conclusión del proyecto?

3B Es posi!le acelerar ciertas tareas para terminar todo el proyecto

más pronto?B i es as%> ¿7ué tareas serán éstas y cuál ser%a elcosto adicional?

!étodo de la R&ta Cr%tica (C<!F 'ri#ical Pa#.

,e#.od ): !étodo &tiliEado para administrarpro>ectos en @&e los tiempos re@&eridos para

terminar las tareas indi1id&ales se conocen conrela#i"a cer#e/a (determin%sticos)

7/21/2019 Unidad_1


3F6

Técnica de 1al&ación de <ro>ectos (<RTF Program <"alua#ion and Re"ie2 *ec.nique): !étodo&tiliEado para administrar pro>ectos en @&e lostiempos re@&eridos para terminar las tareas

indi1id&ales son incier#os (probabil%sticos)-

rela#i"a cer#e/a (determin%sticos)-

3B1 $esarrollo de la -ed de (royectos

1B Identii7ue las tareas individuales 7ue componen el proyecto

(ara determinar el tiempo de conclusión de un proyecto puedeusar los siguientes pasos9

7/21/2019 Unidad_1


3F8

2B O!tenga una estimación del tiempo de conclusión de cadatareaB

3B Identii7ue las relaciones entre las tareasB ¿Qué tareas de!enconcluirse antes de 7ue otras puedan iniciarse?

#B $i!u"e un diagrama de red de proyecto para rele"ar lainormación de los pasos 1 y 3

E"emplo9

Traslado de las oicinas de &na ci&dad a otra

El directorio /a i"ado un pla'o máAimo de 22semanas para la mudan'a

7/21/2019 Unidad_1


3F

+onstrucción del diagrama de -ed9

2

,

7/21/2019 Unidad_1


31F

1

3

#

5 +

¿+ómo agregamos la actividad $?B us predecesoras inmediatas son , y +>además + es predecesora directa de .

,ctividades .icticias igurada49Es una actividad artiicial 7ue no re7uiere tiempo y 7ue seincluye en una red de proyecto para asegurar la relación de

precedencia correcta entre ciertas tareasB

<eneralmente se representan por l%neas segmentadas

7/21/2019 Unidad_1


311

<eneralmente se representan por l%neas segmentadasB

e usan sólo para rele"ar las relaciones de precedenciaadecuadas

2

#

,

+

Golviendo al e"emplo9 ,gregando el resto de las actividades a la red

inalmente se tiene

2)

,

$

E

M

7/21/2019 Unidad_1


312

1

3

#

6

8

5+

.

<

I

iguiendo con el e"emplo9 < y M tienen como predecesora inmediata

.> además am!as son predecesoras de > agregar actividad icticiaB

2)

,

$

E

M

7/21/2019 Unidad_1


313

1

3

#

6

8

5+

.

<

M

I

-ed .inal

.ic

-uta +r%tica9 $ar cumplimiento al pla'o l%mitee re7uiere de las estimaciones de tiempo de cada actividad supuestos4

7/21/2019 Unidad_1


31#

-etomando el e"emplo9 ,gregando los tiempos a las actividades

2)

,

$

E34

#4

84

7/21/2019 Unidad_1


31)

1

3

#

6

,

5+

.

<

M

I

)4

34

24

#4

24

)4

34

8 .ic

C2lc&lo de la r&ta cr%tica: Tiempo de término del pro>ecto

Deiniciones

*iempo de inicio m!s inmedia#o9 El tiempo

más cercano en 7ue una tarea posi!lementepueda iniciarse &I4

7/21/2019 Unidad_1


31

pueda iniciarse &I4

*iempo de #érmino m!s bre"e: El tiempo máscorto en el 7ue una tarea posi!lemente puedaconcluir &&4

-eglas a cumplir9 $ado 7ue en el proyecto eAisten tareas predecesoras es necesario conocer cuandotermina una y cuando empie'a la otra9

-egla

1B (ara calcular el &I de una tarea se de!e conocer los && de cadatarea predecesora inmediata

7/21/2019 Unidad_1


316

p

2B El &I más inmediato de una tarea de la 7ue se conocen lostiempos de término más !reves de todas sus tareas

predecesoras inmediatas es el m!3imo de todos esos tiemposde término más !revesB

3B &iempo de término más !reve K tiempo de inicio másinmediato4 H tiempo de tareat44

(asos para determinar los &I y && más inmediatos9

(aso

F Identiicar el nodo de inicio de la red del proyecto

+alcule y escri!a en cada arco saliente

a4 &I más cercano> esto es> F

7/21/2019 Unidad_1


318

1

!4 El && más !reve de acuerdo a la regla 3

&& más !reve K &I más inmediato4 H t4

K F H t

eleccionar cual7uier nodo donde todos los arcosentrantes /an sido eti7uetados con sus &I y &&

(asos para determinar los &I y && más inmediatos9

(aso

2 (ara el nodo seleccionado en el paso 1 calcule y registreen cada arco saliente

7/21/2019 Unidad_1


31

a4 El &I más !reve de acuerdo a la regla 2

&I más !reve K *,RI*O&& de los arcos entrantes4

!4 El && más !reve de acuerdo a la regla 3

&& más !reve K &I más inmediato H t

+álculo de &I y &&9

2)

3 T

$S8>12TE S 1 2

>2 F T

7/21/2019 Unidad_1


32F

1

3

#

6

, S F >

3

5 S F

> )

T

+ S

) > 8

T

. S 8>1 F T

< S 1 F >1 # T

MS1F>1 2 T

I S )> 1 F T

l S 2 F >2 3 T

8 .ic

Identiicación de las tareas cr%ticas9

(ara identiicar las tareas cr%ticas /ay 7ue reali'ar unrecorrido /acia atrás /asta el inicio del proyecto>

anali'ando cada tareaB3 lti Ti d té i : á t d d

7/21/2019 Unidad_1


321

3- ltimo Tiempo de término: :o más tarde 7ue puedeconcluirse una tarea> en tanto permita 7ue el proyecto secomplete lo más pronto posi!le

4- ltimo tiempo de inicio: :o más tarde 7ue puedainiciarse una tarea> pero inali'ando dentro de su tiempode términoB

/- Tarea s&cesora9 =na tarea para la 7ue la tarea de interéses una predecesora


(ara calcular el 0ltimo tiempo de término =&&4 de unatarea particular> de!e conocer los 0ltimos tiempos deinicio =&I4 de cada tarea sucesora inmediataB

-especto a una tarea de la 7ue se conocen los 0ltimos

Re$la0

+

7/21/2019 Unidad_1


322

tiempos de inicio de todas sus tareas sucesorasinmediatas> el 0ltimo tiempo de término =&&4 de esa

tarea es el m(nimo de los 0ltimos tiempos de inicio detodas las tareas sucesoras inmediatas

=&I K =&&@ t6


(asos para calcular los 0ltimos tiempos de inicio y término

F Identiicar el inal del proyectoB +alcular y escri!ir en cada arcoentrante9

a4 ltimo tiempo de término del proyecto

!4 ltimo tiempo de inicio -egla 49 =&IK=&&@t

7/21/2019 Unidad_1


323

1

2

3

4 p g 4

eleccione un nodo> cuyos arcos salientes /ayan sido eti7uetadostodos con sus =&I y =&&

(ara el nodo seleccionado paso 14 calcule y escri!a lo siguiente

a4 =&&K *I=&I arcos salientes4> regla )4

!4 =&IK=&& @ t regla 4

-epetir pasos 1 y 2 /asta cu!rir toda la red del proyecto


+álculo de =&& y =&I para cada actividad

,ctividad I =&& K 23=&I 23 ) 18

Iteración 3 odo ,ctividad =&& K 23

=&I K 23@3 K 2F

7/21/2019 Unidad_1


32#

Iteración 4

,ctividad icticia =&& K 2F

=&I K 2F@F K 2F

=&I K 23@) K 18

odo 6 ,ctividad E =&& K 2F

=&I K 2F@8 K 12

=&& K 2F

=&I K 2F@2 K 18

,ctividad M

2)

3 T

E S 1 2

>2 F T


+álculo de =&& y =&I para cada actividad B .inalmente se tiene

$S8>12T

S8>12T S 1 2 >2 F T

7/21/2019 Unidad_1


32)

1

3

#

6

, S F >

3

5 S F

> ) T

+ S

) > 8

T

S 2 F >2 3 T

. S 8>1 F T < S 1 F >1 # T

MS1F>12 T

I S )> 1 F T

l S 2 F >2 3 T

8

S ) > 8 T

S 1 8> 2 3 T

S 1 >2 F T

S18> 2F T

S 1 #> 1 2 T

S ) >

8 T

S F > )

T

.ic


Molgura9 Es la cantidad de tiempo 7ue puede demorar unaactividad sin aectar la ec/a de término del proyectoB

El valor de la /olgura para cada actividad está dada por9

/olgura K &I @ =&I K && @ =&&

E" l

7/21/2019 Unidad_1


32

E"emplo9

,ctividad +9 &I K )> =&I K )> && K 8> =&& K 8

Molgura K ) @ ) K 8 @ 8 K F

,ctividad I9 &I K )> =&I K 18> && K 1F> =&& K 23

:a actividad + tiene /olgura F> por tanto no puede

retrasarse> en cam!io la actividad I tiene 13 semanas de/olgura 7ue permite retrasar su inicioB


-esumen de los tiempos de las actividades del proyecto9

%ctivi#a # &ie 'po Inicio &( r' ino Inicio &( r' ino $o)*+ra

+ 3 0 3 5 8 5% 5 0 5 0 5 0

Tiempo más pr&imo de; Tiempo más le"ano de;

7/21/2019 Unidad_1


326

! 3 5 8 5 8 0

@ - 8 12 8 12 0

8 12 20 12 20 0

2 8 10 1- 16 6G - 10 1- 16 20 6

J 2 10 12 18 20 8

< 5 5 10 18 23 13

K 3 20 23 20 23 0

&iempo de e"ecución del proyecto9 23 semanas


,ctividad cr%tica es a7uella 7ue tiene /olgura cero

-uta cr%tica es una secuencia de tareas actividades4 cr%ticas 7ueconecta el principio del proyecto con el in

7/21/2019 Unidad_1


328

En nuestro e"emplo9

,ctividades cr%ticas9 5> +> $> E y

-uta cr%tica9 odos 37/747+797J

,ctividades '7C7D77K

.ormas de -educir la duración del proyecto9

1B ,nálisis Estratégico

,7u% el analista se pregunta9 P¿ 3ste proyecto tiene "ue

desarrollarse en la #orma programada actualmente?P. Enconcreto> ¿Todas las actiidades de la ruta cr+tica tienen "ue

realizarse en el orden especi#icado?P ¿'odemos hacer arreglos

7/21/2019 Unidad_1


32

realizarse en el orden especi#icado? . ¿'odemos hacer arreglos

para e#ectuar algunas de estas actiidades en #orma distinta de

c$mo aparecen en la ruta cr+tica?.

2B Eno7ue &áctico

El analista presupone 7ue el diagrama en curso es adecuado ytra!a"a para reducir el tiempo de ciertas actividades de la ruta

cr%tica asignando mayores recursosB (or e"emplo tiempo> aumentode mano de o!ra> etcB


(ara el e"emplo en estudio> el directorio estimó untiempo máAimo de 22 semanas para reali'ar el

7/21/2019 Unidad_1


33F

tiempo máAimo de 22 semanas para reali'ar el proyecto> y seg0n el estudio se /a determinado 7ue sere7uieren 23 semanas> ¿+ómo soluciona =dB el

pro!lema?B -ealice distintos supuestos válidos para susoluciónB ¿Es 0nica?B


,lternativa de solución

-eali'ados algunos estudios los responsa!les de la mudan'a> se

dan cuenta 7ue la actividad entrenamiento de los nuevosempleados4 de!e reali'arse en el nuevo ediicio después del l i id d E4 d é d l l l

7/21/2019 Unidad_1


331

completar la actividad E4 y después de 7ue el personal clave yde registros se /aya mudado al completar la actividad M4BEstos re7uerimientos se podr%an cam!iar9

• -eali'ar independientemente de M

• El entrenamiento reali'arlo en otras dependencias a un costoreducido y 7ue estén listos para cuando se termine la

construcciónB Esto re7uiere agregar otra actividad9 <aranti'arrecursos de entrenamiento> actividad C


+on los cam!ios anteriores> es posi!le 7ue la red

7/21/2019 Unidad_1


332

redeinida tenga una nueva ruta cr%tica con un tiempomenor> aun7ue todav%a insatisactorio mayor a las 22

semanas esta!lecidas4B

$iagrama de red para el proyecto redeinido

2)

,

$E

M34

#4

84

24

7/21/2019 Unidad_1


333

1

3

#

6

5+

. <

I

34

)4

34

24 #4

)4

34

8

C 34

.ic

,ctuali'ación de los tiempos para el proyecto redeinido

%ctivi#a # &ie 'po Inicio &( r' ino Inicio &( r' ino $o)*+ra

+ 3 0 3 5 8 5

% 5 0 5 0 5 0

! 3 5 8 5 8 0@ - 8 12 8 12 0

8 12 20 12 20 0

Tiempo más pr&imo de; Tiempo más le"ano de;

7/21/2019 Unidad_1


33#

8 12 20 12 20 0

2 8 10 11 13 3

G - 10 1- 13 1D 3

J 2 10 12 18 20 8< 5 5 10 15 20 10

K 3 1- 1D 1D 20 3

L 3 10 13 1- 1D -

,ctividades ruta cr%tica9 5@+@$@E$uración del proyecto9 2F semanas

3B3 (E-&9 Garia!ilidad en los tiempos de ,ctividades

Masta a/ora /emos tra!a"ado asumiendo 7ue lostiempos de duración de las actividades eran

determin%sticos> en consecuencia &I> &&> =&I y =&&tam!ién ueron deducidos como deterministasB +omo

7/21/2019 Unidad_1


33)

este supuesto no siempre es correcto> (E-& empleauna órmula especial para estimar los tiempos de las

actividadesB(E-& re7uiere de alguien 7ue cono'ca !ien unaactividad en cuestión> para producir tres estimacionesdel tiempo de éstaB

'3!T4 ariabilidad en los tiempos de &ctiidades

1B *iempo op#imis#a denotado por a49 el tiempom%nimoB &odo tiene 7ue marc/ar a la perecciónB

2 *i ! b bl d d 4 l i

7/21/2019 Unidad_1


33

2B *iempo m!s probable denotado por m49 el tiempo7ue se necesita en circunstancias ordinariasB

3B *iempo pesimis#a denotado por b49 el tiempomáAimoB ituación 7ue se da en el peor casoB


E"emplo9 (ara la actividad E 8 semanas4B ,leAaminar en detalle el proyecto de construcción del

interior se llegó a las siguientes estimaciones9a K #

7/21/2019 Unidad_1


336

m K 6

! K 1(ara estimar el valor esperado y la desviación estándar delos tiempos de la actividad> se asume 7ue el tiempo de laactividad es una varia!le aleatoria 7ue tiene unadistri!ución de pro!a!ilidad unimodal !etaB


Distrib&ción beta

7/21/2019 Unidad_1


338

# 6 8 1a m !

Estimación del tiempo esperadode actividad o tiempo promedio

# bmat e

++=

Estimación de la desviaciónestándar del tiempo de la actividad ab −=σ


stimación de tiempo

%ctivi#a# a ' , te #e-v e-t varian.a

+ 1/0 3/0 5/0 3/0 0/66D 0/---% 3/0 -/5 E/0 5/0 1/000 1/000

! 2 0 3 0 - 0 3 0 0 333 0 111

7/21/2019 Unidad_1


33

! 2/0 3/0 -/0 3/0 0/333 0/111

@ 2/0 -/0 6/0 -/0 0/66D 0/---

-/0 D/0 16/0 8/0 2/000 -/000

1/0 1/5 5/0 2/0 0/66D 0/---

G 2/5 3/5 D/5 -/0 0/833 0/6E-

J 1/0 2/0 3/0 2/0 0/333 0/111

< -/0 5/0 6/0 5/0 0/333 0/111

K 1/5 3/0 -/5 3/0 0/500 0/250L 1/0 3/0 5/0 3/0 0/66D 0/---


+álculo del tiempo esperado de inali'ación de proyectos

=na ve' determinado el tiempo promedio de cada

actividad> se puede calcular el tiempo de inali'aciónmás temprano esperado para el proyecto completoB

7/21/2019 Unidad_1


3#F

e determinan los tiempos de inicio y de término máscercano> como tam!ién los tiempos de término y deinicio más le"anoB +on estos tiempos se determina la/olgura en cada actividad> para inalmente determinar laruta cr%tica> eAactamente igual como se /i'o para tiempodeterministaB


(ro!a!ilidad de concluir el proyecto a tiempoEl análisis procede de la siguiente orma9

1B ea & el tiempo total 7ue durarán las actividades de la rutacr%ticaB

2B Encuéntrese la pro!a!ilidad de 7ue el valor de & resulte menoro igual 7ue cual7uier valor espec%ico de interés (ara el

7/21/2019 Unidad_1


3#1

o igual 7ue cual7uier valor espec%ico de interésB (ara ele"emplo en estudio !uscar%amos & ≤ 22 semanasB

=na !uena aproAimación de esta pro!a!ilidad se encuentraaceptando dos supuestos9

a4 :os tiempos de actividad son varia!les aleatoriasindependientesB

!4 :a varia!le & tiene una distri!ución aproAimadamente normalB


:a meta es encontrar ([& ≤ 22]> donde & es el tiempo a lo largode la ruta cr%ticaB

stad%sticas de la r&ta cr%tica:

222σσσσ +++=$esviación estándar

7/21/2019 Unidad_1


3#2

21 BBB

nT σ σ σ σ +++=$esviación estándar

iσ

9iσ $esviación estándar de i@ésimaactividad de la ruta cr%tica

T : es el tiempo esperado promedio4

stimación de terminación del pro>ecto

=so de la ta!la de distri!ución normal> entonces

de!emos calcular N para llegar a determinar la pro!a!ilidadB

7/21/2019 Unidad_1


3#3

σ

µ −

=

x

A

C2lc&los caso en est&dio

-uta cr%tica9 5@ +@ $ y E

& K 2F tiempo esperado> promedio calculado> µ4

7/21/2019 Unidad_1


3##

A K 22 tiempo eAigido4

3)6>2

)))>)

####>F111>F12

2

22222

=

=

+++=+++=

T

T

T

3 5% 6T

σ

σ

σ

σ σ σ σ σ

C2lc&los caso en est&dio

N K F>8#8)3)6>2

2F22 −= A

7/21/2019 Unidad_1


3#)

En la ta!la de N

(N≤ F>8#8)4 K F>8F

*atri' de Encadenamiento =na matri' de encadenamiento> es una matri' de A es lacantidad de actividades4 donde cada celda se marca con una R sila actividad de la ila re7uiere 7ue esté terminada la actividad dela columnaB Esta matri' ayuda a la construcción de la red +(*

(ara el e"emplo en estudio es9

7/21/2019 Unidad_1


3#

(ara el e"emplo en estudio es9

% $ I

%

'

' '

'

'

$ 'I '

' ' '

3B# +(*9 &-=EQ=E E&-E &IE*(O ^ +O&O +(* considera 7ue el tiempo eAtra costo4 puede reducir eltiempo de término de una actividad> y en consecuencia reducir eltiempo total del proyecto

Compra de tiempo:+(* usa dos estimaciones9 tiempo y costo normal> a lo 7ue se

7/21/2019 Unidad_1


3#6

p y > 7agregará tiempo y costo intensio

e asume 7ue estas estimaciones son lineales9

&iempo

Esuer'o normal

Esuer'o intensivo

+ o s

t o

$e!ido a las estimaciones de +(* se puede o!tener dos redeseAtremas9

1B -ed de costo normal

2 -ed de costo intensivo

%'(4 True"ue entre el costo y el tiempo

-ed de tiempo m%nimo ; costo m%nimo

7/21/2019 Unidad_1


3#8

2B -ed de costo intensivo

¿&odas las actividades de!en reali'arse en orma intensiva?

3B -ed de tiempo m%nimocosto m%nimo

1B +omen'ar con la red normal e ir reduciendo los tiempos detérmino /asta un m%nimoB

2B +omen'ar con la red de todo intensivo y Pdesintensiicaractividades para reducir el costo sin aectar el tiempo totalB


no@&es para encontrar red de tiempo m%nimo L costom%nimo

7/21/2019 Unidad_1


3#

actividades para reducir el costo sin aectar el tiempo totalB

3B +omen'ar con la ruta cr%tica de la red de todo intensivo con

un tiempo m%nimo> pero con todas la demás actividadesnormalesB $espués reducir las otras trayectorias como seanecesarioB

¿&odos son igualmente eicaces?


no@&e: Red normal > red&cción de tiempos

(royecto9 +onstrucción de una casa

+ctiidad Precedencia =ormal <ntensio =ormal <ntensio ∆ +osto+ 1 2. ninuna - 3 1 -00 2 000 600

iempo semanas. !osto miles $.

7/21/2019 Unidad_1


3)F

+ 1/2. ninuna - 3 1#-00 2#000 600

% 2/3. + 2 1 1#500 2#000 500

! 2/-. + 3 1 1#500 2#500 1#000

@ 2/D. + 1 1 600 600 **ic3/-. 0 0 ** ** **

-/5. %/ ! 3 2 1#300 2#000 D00

-/6. %/ ! 2 1 300 500 200

G 5/D. 2 1 800 1#200 -00

J 6/D. 2 1 600 1#000 -00


<aso 3: Red del pro>ecto

3 )

i consideramos la convención actividad@lec/a> el grao del proyecto es9

7/21/2019 Unidad_1


3)1

2

3

6

E34<24

M24

$14

1.24

#+34

524

,#4


<aso 4: Tiempos de Inicio > de TérminoF Hol$&ra > r&ta cr%tica

3 )

En el grao se muestran los tiempos de inicio y de término más próAimos y los más le"anos> y la ruta cr%ticaB El tiempo m%nimo

para la ruta cr%tica es de 12 semanas a un costo normal de U8BFFFB

7/21/2019 Unidad_1


3)2

2

3

6

5 2 4

S # > T

3 F 4 S 2

> 2

T

< 3 2 4 S 1 F >1

2 T

M24S>11T

M78*7=N1

.24S6>T#

+34S#>6T,#4SF>#T

F

F F

E 3 4

S 6 > 1 F

T

F12 12

$14S#>)T

MF*78NMH*<N

M 0 * < N

S < *

<

N

M8*HN

M < * 7 8 N

M 7 8 *7

= N

M77*7=N


<aso 4: Tabla de tiempos pró.imos > le=anos

Tiempo Tiempo más pr&imo de; Tiempo más le"ano de;

+ctiidad =ormal <nicio Trmino <nicio &érmino Jolura

+ 1/2. - 0 - - - 0% 2/3. 2 - 6 5 D 1

! 2/-. 3 - D - D 0

@ 2 D. 1 - 5 1 12 D

,ctividadescr%ticas

7/21/2019 Unidad_1


3)3

@ 2/D. 1 - 5 1 12 D

-/5. 3 D 10 D 10 0

-/6. 2 D E 8 10 1

G 5/D. 2 10 12 10 12 0J 6/D. 2 E 11 10 12 1

cr%ticas


<aso /: MIntensiicar acti1idades r&ta cr%tica

a4 ,ctividad ,9 de # a 3 semanas FF4

!4 ,ctividad +9 de 3 a 1 semana 1BFFF4c4 ,ctividad E9 de 3 a 2 semanas 6FF4

7/21/2019 Unidad_1


3)#

d4 ,ctividad <9 de 2 a 1 semana #FF4

¿Es posi!le /acer estas reducciones?


Red&cción de Acti1idades r&ta cr%tica

2

3

)

6

5 2

4 S # > T

< 3 2 1 4

M24S>11T1

.24S6>T#

+3 14,# 34

FF F

E 3

2 4

F

7/21/2019 Unidad_1


3))

2 61 #

:a ruta cr%tica disminuyó a 6 semanas> ¿seguirá manteniéndosecomo tal?B No

May 7ue ver si es posi!le reducir las actividades paralelas a la rutacr%tica inicial> sólo /asta igualar tiemposB

$14S#>)T

7/21/2019 Unidad_1



<aso 0: Res&men de las red&cciones

!osto

+ctiidad +cci&n +dicional =ormal Total

+ 1/2. 1 semana 600 1#-00 2#000 % 2/3. 1 semana 500 1#500 2#000

! 2 -. 2 semanas 1000 1 500 2 500

7/21/2019 Unidad_1


3)6

! 2/-. 2 semanas 1000 1#500 2#500

@ 2/D. ***** 600 600

-/5. 1 semana D00 1#300 2#000

-/6. 1 semana 200 300 500

G 5/D. 1 semana -00 800 1#200

J 6/D. ***** 600 600

$ 8#000 $ 11#-00


Grao inal

3 )

En el grao se muestran los tiempos de inicio y de término más próAimos y los más le"anos> y la ruta cr%ticaB El tiempo m%nimo

para la ruta cr%tica es de 6 semanas a un costo normal de U11B#FFB

7/21/2019 Unidad_1


3)8

2

3

6

5 1 4 S 3 >

# T 3 F 4 S #

> #

T

< 3 1 4 S >6 T

M24S)>6T

M0*<N1

.14S#>)T#

+14S3>#T,34SF>3T

F

F F

E 2 4

S # > T

F6 6

$14S3>#T

MH*0NM*HN

M 0 * < N S

<

* <

N

M8*N

M H * 9 N

M 9 *< N

M9*<N

¿Qué sucede si un proyecto lleva más tiempo del especiicado?

¿+onviene /acer más Pintensivo el proyecto o pagar la

penali'ación por atraso?=emplo:


Red óptima

7/21/2019 Unidad_1


3)

uponga 7ue en el proyecto de la casa /ay una penali'ación deU#)F por cada semana de tiempo eAtra después de oc/o semanasB¿+uál es la red óptima?B

Sol&ción: -educir la red en una semana cada ve' e ircomparando si los costos por intensiicar son menores a los

costos por penali'aciónB e termina cuando los costos de penali'ación son mayor a los costos de intensiicarB

1B -educir una semana de 12 a 11 semanas4

$e la red normal anali'ar ruta cr%tica,ctividades Incremento de +osto

, FF+ )FFE 6FF< #FF


Red óptima

7/21/2019 Unidad_1


3F

< #FF

+onclusión9 Intensiicar 1 semana la actividad <

#FFY#)F4B2B Intentar reducir una segunda semana de 11 a 1F4

&odos los costos incrementales de la ruta son mayores a la penali'aciónB Intentar por las v%as paralelasB

o /ay rutas alternativas cuya reducción impli7ue un costomenor al de penali'aciónB

%'(4 True"ue entre el costo y el tiempoSol&ción

2

3

)

6

5 2 4

< 3 1 4

M241

.24#

+34

<rao resultante

,#4

E 3 4

7/21/2019 Unidad_1


31

$14

+onviene /acer intensivo el proyecto /asta la semana 11 y pagarlas penali'aciones por las semanas de atraso

+osto total K +osto intensivo H costo penali'aciónK 8BFFF H #FF4 H 3L#)F K UB)F

%'(4 True"ue entre el costo y el tiempo=emplo

uponga 7ue un proyecto de investigación tiene las siguientesestimaciones9

+ctiidad =ormal <ntensio =ormal <ntensio

+ 1/2. 8 - 20#000 30#000

% 1/3. E 6 18#000 2D#000

! 2/3. 3 2 12#000 1D#000

@ 2/-. 10 D 25#000 3-#000

3 -. 6 - 15 000 23 000

Tiempo meses. !osto miles $.

7/21/2019 Unidad_1


32

a4 $i!u"e la redB +on los tiempos normales de las actividades>

encuéntrese la duración total del proyecto y la ruta cr%ticaB !4 upóngase 7ue el proyecto se de!e completar en un tiempo m%nimoB

¿+uál es el menor costo para el proyecto> es decir> cuál es la red detiempo m%nimocosto m%nimo?

c4 ¿+uál es el costo m%nimo para terminar el proyecto en 16 meses?

d4 El departamento de comerciali'ación dice 7ue cada mes 7ue el proyecto se pase de 1) meses le cuesta a la irma U)BFFFB ¿+uál es elcosto y duración óptimo del proyecto?

3/-. 6 - 15#000 23#000


!odelo de <" para C<! &iempo m%nimocosto m%nimo4

a4 Identiicación de Garia!les de decisión

Están relacionadas directamente con el tiempo a reducir encada tarea

î9 &iempo /oras> d%as> BB4 a reducir de la i@ésima actividad

^ 0 d l l t l ti id d ,

7/21/2019 Unidad_1


33

^,9 0mero de semanas en las cuales acortar la actividad ,

!4 .unción O!"etivoEl o!"etivo es minimi'ar los recursos adicionales totalesre7ueridos para satisacer el tiempo de término del proyectoB

(ara el e"emplo en estudio> en la ta!la de especiicaciones

agregamos dos columnas9 &iempo máAimo a reducir por tareay el costo adicional por semana intensiva



+ctiidad Precedencia =ormal <ntensio =ormal <ntensio

+ 1/2. ninuna - 3 1#-00 2#000 1 600

% 2/3. + 2 1 1#500 2#000 1 500

! 2/-. + 3 1 1#500 2#500 2 500

@ 2/D. + 1 1 600 600 0 **

ic3/-. 0 0 ** ** 0 **

Tiempo semanas. !osto miles $. Feducci&n

máima

!osto por

semana

7/21/2019 Unidad_1


3#

(or lo tanto la unción es9

*I N K FF^,H)FF^5H)FF^+H6FFÊH2FF^.H#FF^<H#FF^M

/ .

-/5. %/ ! 3 2 1#300 2#000 1 D00

-/6. %/ ! 2 1 300 500 1 200

G 5/D. 2 1 800 1#200 1 -00J 6/D. 2 1 600 1#000 1 -00



c4 Identiicación de las restricciones

(ara el e"emplo> se pueden agrupar en dos grupos

1B :a cantidad máAima de tiempo en el cual se puede acortarcada actividadB

7/21/2019 Unidad_1


3)

2B El tiempo de término del proyecto en este caso 12 semanas4

(ara el grupo 1> lo 7ue se necesita son las cotas superioresso!re las varia!les de decisión ^,> ^5> ^+> Ê> ^.> ^<> ^M4

dada por la columna P-educción máAima4 de la ta!la anteriorB



-estricciones de :%mite

FYK^,YK 1 l%mite de ,4

FYK^5YK 1 l%mite de 54

FYK^+YK 2 l%mite de +4

7/21/2019 Unidad_1


3

FYK^$YK F l%mite de $4

FYKÊYK 1 l%mite de E4

FYK^.YK 1 l%mite de .4

FYK^<

YK 1 l%mite de <4

FYK^MYK 1 l%mite de M4



-estricciones del grupo 2 están en unción de nuevas varia!les 7ueeApresan cuando las actividades 7ue salen de un determinadoevento pueden comen'arB -e7uiere conocer cuando terminan

todas las actividades 7ue llegan al eventoB $ependen de î

R1 9 tiempo en 7ue todas las actividades 7ue salen del evento 1 pueden comen'ar

7/21/2019 Unidad_1


36

R2 9 tiempo en 7ue todas las actividades 7ue salen del evento 2 pueden comen'ar

BBBBBBR6 9 tiempo en 7ue todas las actividades 7ue salen del evento 6 pueden comen'ar

,demás el proyecto de!e comen'ar en el tiempo 1 y terminar a lo más en 12semanas

R1 K F

R6 ≤ 12


3 )

E34<24

,sociando las varia!les a la red tenemos9

2@^ 4


524 3@Ê4 2@^<4F4

R3R)

7/21/2019 Unidad_1


38

2 6

M24

$14

1

.24

#

+34

2@^54

,#4

#@^,4 3@^+4 2@^.4

1@^$4

2@^M4

R1 R2R# R

R6



odo 2

&iempo de inicio de las tareas 7ue salen del nodo 2 ≥ tiempo determinación de todas las tareas 7ue entran al nodo 2

&iempo de inicio de las tareas 5> + y $ ≥ tiempo de terminaciónde la tarea , H tiempo acortado de la tarea ,4

7/21/2019 Unidad_1


3

R2 ≥ R1 H #@^,4

odo 3&iempo de inicio de las tareas 7ue salen del nodo 3 ≥ tiempo determinación de todas las tareas 7ue entran al nodo 3

&iempo de inicio de la tarea .icticia ≥ tiempo de terminación dela tarea 5 H tiempo acortado de la tarea 54

R3 ≥ R2 H 2@^54

%'(4 True"ue entre el costo y el tiempo!odelo de <" para C<! &iempo m%nimocosto m%nimo4

odo #&iempo de inicio de las tareas 7ue salen del nodo # ≥ tiempo determinación de todas las tareas 7ue entran al nodo #B

May dos arcos 7ue entran al nodo> las actividades E y . de!encomen'ar sólo cuando las tareas 7ue entran + y la icticia4 /ayanterminadoB $ando origen as% a dos restricciones una por cadaactividad4

7/21/2019 Unidad_1


36F

actividad4

-estricción de la actividad +

&iempo de inicio de las tareas E y . ≥ tiempo de terminación dela tarea +

&iempo de inicio de las tareas E y . ≥ tiempo de terminación dela tarea + H tiempo acortado de la tarea +4

R# ≥ R2 H 3@^c4 tarea +4


odo #-estricción de la actividad .icticia

&iempo de inicio de las tareas E y . ≥ tiempo de terminación dela tarea igurada

&iempo de inicio de las tareas E y . ≥ tiempo de terminación dela tarea .igurada H tiempo acortado de la tarea .igurada4

7/21/2019 Unidad_1


361

R# ≥ R3 H F tarea .igurada4

,plicando sistemáticamente el procedimiento y se escri!e unarestricción para cada actividad se o!tienen las siguientesrestricciones para los nodos ) al 6


odo )R) ≥ R# H 3@Ê4 actividad E4

odo R ≥ R# H 2@^.4 actividad .4

7/21/2019 Unidad_1


362

odo 6R6 ≥ R) H 2@^<4 actividad <4

R6 ≥ R H 2@^M4 actividad M4



*I N K FF^,H)FF^5H)FF^+H6FFÊH2FF^.H#FF^<H#FF^M

u"eto a9-estricciones de :%mite

FYK^,YK 1 l%mite de ,4

FYK^5YK 1 l%mite de 54

7/21/2019 Unidad_1


363

5 4

FYK^+YK 2 l%mite de +4

FYK^$YK F l%mite de $4

FYKÊYK 1 l%mite de E4

FYK^.YK 1 l%mite de .4

FYK^<YK 1 l%mite de <4

FYK^MYK 1 l%mite de M4



R1 K F

R6 ≤ 12

R2 ≥ R

1 H #@^

,4 tarea +4

R3 ≥ R2 H 2@^54 tarea 54

R ≥ R 3 ^ 4 +4

7/21/2019 Unidad_1


36#

R# ≥ R2 H 3@^c4 tarea +4

R# ≥ R3 H F tarea .igurada4R) ≥ R# H 3@Ê4 actividad E4

R ≥ R# H 2@^.4 actividad .4

R6 ≥ R) H 2@^<4 actividad <4R6 ≥ R H 2@^M4 actividad M4

R1> BBB> R6 ≥ F

'ara su entretenci$n=ercicios:

:a comple"idad de las redes +(* está más aectada por las interrelaciones 7ueel n0mero de nodosB (or e"emplo> considérese el proyecto siguiente9 +ctiidad =ormal <ntensio =ormal <ntensio

+ 1/2. 8 D 10#000 12#000

% 1/3. 15 10 12#000 1D#000

! 1/-. 12 6 13#000 1-#000

@ 2/3. E E D#000 D#000

2/5. 11 E 2#000 -#000

3/6. E 8 5#000 D#000

G -/3. E D 1-#000 16#000

J -/D. 13 12 8#000 10#000

< 5/6. D 5 6#000 10#000

7/21/2019 Unidad_1


K 5/8. 15 11 E#000 10#000

L 6 8. 10 5 3 000 8 000

Documents

Unidad_1