unid 5 optimizacion de redes

7/25/2019 Unid 5 Optimizacion de Redes

1/23

Instituto Tecnolgico De Villahermosa.

1


2/23

Asignatura:

Investigacin de Operaciones II

Catedrtico:

Ing. Zinath Javier ernimo

!nidad ".

Optimi#acin De $edes

Alumnos:

%esenia Contreras &aga'a$omn (ernnde# )strada

*idman Antonio (ernnde# OvandoJosu+ ),ra-n Aguilar u#mn

ucio (ernnde# #aroChristian &+nde# $am-re#Cesar /ah0m pe# en

Villahermosa, Tabasco a Diciembre del 2010

1/DIC)

!/IDAD V O2TI&IZACI3/ D) $)D)4

INTRODUCCIN.................................................................................................3

2


3/23

5.1 Terminolo!a""""""""""""""""""""""""""...#

5.2 $roblema de la r%&a m's cor&a. Redes c!clicas ( ac!clicas"""""""..".)

5.3 $roblema del 'rbol de m!nima e*+ansin""""""""""""""".-

5.# $roblema de l%/o m'*imo"""""""""""""""""""""1#

5.5 $roblema de l%/o de cos&o m!nimo""""""""""""""""".15

5.) $roramacin lineal en &eor!a de redes""""""""""""""""1)

Concl%sin..........................................................................................................1

ibliora!a..........................................................................................................1

I/T$OD!CCI3/

3


4/23

Uno de los ma(ores desarrollos recien&es en Ines&iacin de O+eraciones ha sido el

r'+ido aance &an&o en la me&odolo!a como en la a+licacin de los modelos de

o+&imi4acin de redes.

os +roblemas de redes s%ren en %na ran ariedad de si&%aciones como +or e/em+lolas redes de &rans+or&e, el6c&ricas en in %na inmensa lis&a 7%e +redominan en la ida

diaria. a re+resen&acin de redes se %&ili4a en 'reas &an diersas como +rod%ccin,

dis&rib%cin, locali4acin de ins&alaciones en in %n sin n8mero de 'reas. De hecho %na

re+resen&acin de redes nos +ro+orciona %n +anorama eneral &an +oderoso ( %na a(%da

conce+&%al +ara is%ali4ar las relaciones en&re los com+onen&es del sis&ema 7%e se

%&ili4a casi en &odas las 'reas cien&!icas, sociales ( econmicas.

9e dar'n a conocer en es&e &raba/o diersos &i+os im+or&an&es de +roblemas de redes (

al%nas ideas b'sicas sobre cmo resolerlos.

".5 T)$&I/OO1A

4


5/23

Una red o rao consis&e de +%n&os, ( l!neas 7%e conec&an +ares de +%n&os. os +%n&os sellaman nodos o 6r&ices. as l!neas de llaman arcos. os arcos +%eden &ener %nadireccin asociada, en c%(o caso se denominan arcos diriidos. 9i %n arco no &ienedireccin normalmen&e se le denomina rama. 9i &odos los arcos en la red son diriidos,la red se denomina %na red diriida. 9i &odos los arcos son no:diriidos, la red es %nared no:diriida.

Dos nodos +%eden es&ar conec&ados +or %n con/%n&o de arcos. Una &ra(ec&oria ;+a&h eninl6s< es %na sec%encia de arcos dis&in&os ;con nodos no re+e&idos< conec&ando a losnodos. Una &ra(ec&oria diriida desde nodo i al nodo / es %na sec%encia de arcos, cada%no de los c%ales a+%n&a al nodo / ;si es 7%e ha( direccin


6/23

Aodelo del l%/o m'*imo.

Aodelo del l%/o del cos&o m!nimo.

Aodelo de minimi4acin de redes

=l modelo de minimi4acin de redes o +roblema del 'rbol de m!nima e*+ansin &iene7%e er con la de&erminacin de los ramales 7%e +%eden %nir &odos los nodos de %na red,&al 7%e minimice la s%ma de las loni&%des de los ramales escoidos. No se debenincl%ir ciclos en la sol%cin del +roblema.

$ara crear el 'rbol de e*+ansin m!nima &iene las si%ien&es carac&er!s&icas@

1. 9e &ienen los nodos de %na red +ero no las liad%ras. =n s% l%ar se +ro+orcionan lasliad%ras +o&enciales ( la loni&%d +osi&ia +ara cada %na si se inser&a en la red. ;as

medidas al&erna&ias +ara la loni&%d de %na liad%ra incl%(en dis&ancia, cos&o (&iem+o.igura ;5@

I&eracin 0@ el nodo 1 llea la e&i7%e&a +ermanen&e G0,:H.

I&eracin 1@ los nodos 2 ( 3, 7%e se +%eden alcan4ar direc&amen&e desde el nodo 1 ;el%l&imo nodo ro&%lado +ermanen&emen&e


10/23

a sol%cin en la i%ra :11 +ro+orciona la dis&ancia m's cor&a a cada nodo en la red,/%n&o con s% r%&a.

".< 2$O7)&A D) 8$7O D) &1/I&A )2A/4I3/

=s&e +roblema considera %na red no diriida ( cone*a. =n ella se debe encon&rar %n'rbol de e*+ansin con la loni&%d m!nima de s%s arcos.

Algoritmo para el pro9lema del r9ol de eBpansin m-nima.

1.: selecciona, de manera arbi&raria, c%al7%ier nodo ( se conec&a ;es decir, se area %naliad%ra< al nodo dis&in&o m's cercano.

2.: se iden&iica el nodo no conec&ado m's cercano a %n nodo conec&ado ( se conec&anes&os dos nodos ;es decir, se area %na liad%ra en&re ellos


11/23

Aplicacin de este algoritmo al pro9lema del r9ol de eBpansin m-nima deseervada par

a adminis&racin de seerada +arK necesi&a de&erminar los caminos ba/o los c%ales sedeben en&ender las l!neas &elenicas +ara conec&ar &odas las es&aciones con %na loni&%d

&o&al m!nima de cable. 9e describir' +aso a +aso la sol%cin de es&e +roblema con baseen los da&os 7%e se dan a con&in%acin.

os nodos ( dis&ancias +ara el +roblema se res%men ense%ida, en donde las l!neasdeladas ahora re+resen&an liad%ras +o&enciales.

0

C

B

A

E

D

T

11


12/23

6 6 "

" =

< 5

= 5

=

=n orma arbi&raria, se selecciona el nodo 0 como inicio. =l nodo no conec&ado m'scercano a 0 es >. se conec&a el nodo > al nodo 0.

0

C

B

A

E

D

T

6 6 "

" =

< 5

12


13/23

= 5

=

0

C

B

A

E

D

T=l nodo no conec&ado m's cercano a c%al7%iera de los nodos 0 o > es el nodo ;m's

cercano a >.

6 6 " " =

< 5

= 5

=

13


14/23

=l nodo no conec&ado m's cercano a 0, > o es el nodo C ;m's cercano a


15/23

C

B

A

E

D

T

=l nodo no conec&ado m's cercano a 0, >, o C es el nodo = ;m's cercano a


16/23

D

T

=l nodo no conec&ado m's cercano a los nodos 0,>, , C o = es el nodo D ;m's cercanoa =


17/23

T

6 6 "

" =

< 5

= 5

#

Todos los nodos han 7%edado conec&ados, +or lo 7%e es&a es la sol%cin ;o+&ima< 7%e seb%scaba. a loni&%d &o&al de las ramas es 1# millas.

>%n7%e con es&e +rocedimien&o a +rimera is&a +%ede +arecer 7%e la eleccin del nodoinicial aec&ar!a la sol%cin inal ; ( la loni&%d &o&al de las liad%ras


18/23

".= 2ro9lema de ,luEo mBimo

=n %na red con l%/o de ca+acidades en los arcos, el +roblema es de&erminar el l%/om'*imo +osible +roenien&e de los or!enes de orma &al de ahoar las ca+acidades del%/os de los arcos. Considere %na red con m nodos ( n arcos con %n l%/o sim+le de

bienes. Deno&e el arco de l%/o ;i a /< como Li/. >sociamos cada arco a %na ca+acidad del%/o, Ki/. =n es&a red, deseamos encon&rar el l%/o &o&al m'*imo en la red, M, del nodo 1al nodo m.

=n la orm%lacin de la +roramacin lineal, el ob/e&io es ma*imi4ar M. =l mon&o 7%e+ar&e del orien +or arias r%&as. $ara cada nodo in&ermedio, lo 7%e en&ra debe ser i%ala lo sale. =n al%nas r%&as los l%/os +%eden &omar ambas direcciones. a ca+acidad 7%e

+%ede ser eniada a %na direccin en +ar&ic%lar &ambi6n es mos&rada en cada r%&a

.

18


19/23

"." 2ro9lema de ,luEo de costo m-nimo

=l +roblema de l%/o de cos&o m!nimo &iene %na +osicin med%lar en&re los +roblemasde o+&imi4acin de redes +rimero, abarca %na clase am+lia de a+licaciones ( se%ndo,s% sol%cin es m%( eicien&e.

Todos los +roblemas de red an&eriores son casos es+eciales del +roblema de l%/o decos&os m!nimo. >l i%al 7%e el +roblema de l%/o m'*imo, es&e considera l%/os en lasredes con ca+acidades. >l i%al 7%e el +roblema del camino mas cor&o, es&e considera%n cos&o +or l%/o hacia %n arco. >l i%al 7%e el +roblema de &rans+or&e, es&e +ermi&em8l&i+les or!enes ( des&inos. $or lo &an&o, &odos es&os +roblemas +%eden ser is&oscomo casos es+eciales del +roblema de l%/o de cos&os m!nimo.

=l +roblema es minimi4ar el cos&o &o&al s%/e&o a la dis+onibilidad ( la demanda deal%nos nodos, ( de la cone*in s%+erior de l%/o a &ra6s de cada arco

a solucin ptima es: 56 F 56G 5< F G 6< F G 6= F =G


20/23

La programacin lineal es actualmente la tcnica matemtica utilizada ms actualmente gracias

a ue el algoritmo simple! es mu" e#iciente " al desarrollo de la computacin$ Lo ue se %usca

con la aplicacin de la programacin lineal es resol&er pro%lemas comunes " a la &ez mu"

&ariados de la empresa en donde en general se tienen necesidades por satis#acer con cierto

n'mero de recursos limitados o escasos " con el o%(eti&o de lograrlo en #orma ptima$

Ejemplo

)na empresa *a de(ado de #a%ricar ciertos productos+ li%erando de esta #orma las cargas de

produccin ue ten,an sus euipos en los departamentos de mauinado$ -*ora se tienen *oras

muina ue se pueden utilizar en los productos denominados 1+2+3 de la siguiente manera.

/uina oras por pieza de producto oras /a$ isponi%les

1 2 3 por semana

resadora 9 3 5 500

orno 5 4 350

ecti#icadora 3 2 150

)tilidad

pieza 50 20 25

ecomendacin del /,nimo /,nimo /,nimo

epto$ tas a rod$ 30 15 20

Formular un modelo de Programacin Lineal para este problema

e#inicin de &aria%les a utilizar en el mtodo de programacin lineal

:ea. ;( < n'mero de piezas de producto (=( a #a%ricar para ma!imizar la utilidad$

uncin econmica " o%(eti&o.

/-; ?< 50;1 @ 20;2 @ 25;3 A =ls)nidad> =)nidad:em>B < Als:em$B

Sujeta a restricciones de horas mquina disponibles por semana

resadora. 9;1 @ 3;2 @ 5;3 C 500 *oras muina #resadora

orno. 5;1 @ 4;2 C 350 *oras muina torno

ecti#icadora. 3;1 @ 2;3 C 150 *oras mauina recti#icadora

20


21/23

Dondiciones de signos pare las &aria%les.

;1 C 30 piezas

;2 C 15 piezas

;3 C 20 piezas

CO/C!4I3/

os modelos de o+&imi4acin de redes cons&i&%(en %na herramien&a m%( sencilla +ara laencon&rar la sol%cin +&ima a los +roblemas de l%/o de redes, +or7%e +ro+orcionanalori&mos 'ciles de com+render ( a+licar 7%e com+arados con el m6&odo sim+le*dismin%(en el n8mero de i&eraciones 7%e res%elen el +roblema. 9i se a+licara elm6&odo sim+le* en %n +roblema de dis&rib%cin o de redes, &endr!amos m%chasariables ( res&ricciones en el modelo ( se &endr!a 7%e %&ili4ar herramien&ascom+%&acionales +ara encon&rar la sol%cin o+&ima de %na orma r'+ida, ahora con losmodelos de redes solo habr!a 7%e a+licar las i&eraciones al rao 7%e oriina la

re+resen&acin de la red del +roblema ( l%eo a+licar el alori&mo 7%e corres+onde, 7%e+%ede ser el alori&mo de la r%&a m's cor&a, alori&mo +ara encon&rar el 'rbol dee*+ansin m!nima, alori&mo de la &ra(ec&oria de a%men&o o el alori&mo de l%/om'*imo.

>%n7%e los +roblemas de l%/o de cos&o m!nimo ( el de la r%&a m's cor&a +%edenorm%larse como modelos de +roramacin lineal +ara l%eo a+licar el m6&odo sim+le*,no es conenien&e s% %&ili4acin. $or o&ro lado sol%cionar el +roblema %&ili4ando redesme/ora la eiciencia de los c'lc%los.

21


22/23

7I7IO$A>1A

MredericK 9. iller ( Perald Q. iberman. Ines&iacin De O+eraciones . AcPra:ill.96+&ima =dicin. 2002.

amd( >. Taha. Ines&iacin De O+eraciones. =diciones >laomea. C%ar&a =dicin.1--1

22


23/23

23

unid 5 optimizacion de redes

Documents