Транспорттық есептiң қойылуы
Транспорттық есептi дельта-әдiс
жүктеу/скачать 457.5 Kb.
|
Транспорттық есептi дельта-әдiсарқылы шешу Транспорттық есептiң оптимальдi жоспарын жасаған кезде оған кеткен уақытта ұлкен мән бар. Ал 10-15 мердiгерлер мен 15-20 тҰтынушысы бар транспорттық есептi шешуде 4 – 5 сағат ұздiксiз есептеулер қажет етедi. МҰның себебi бастапқы жасалатын жоспардың оптимальдiк жоспардан алыстығы. Практика кјрсеткендей дельта-әдiсi мен потенциалдар әдiсiн бiрге қолданған кезде оптимальдi жоспарын 4 – 5есе тез табуға болады. Сонымен қатар таблица қанша ұлкен болған сайын соншалықты бҰл әдiстiң тиiмдiлiгi байқалады. БҰл дельта әдiспен әдiсiмен шешкенде әрқашан оптимальдi жоспардың анықталуына кепiл бередi. Ал егер дельта әдiсiменшығарылған транспорттық есептiң оптимальдi шешiмi шықпаса онда бҰл есептi шешу кезiнде кеткен қателiктерден болғаны. Дельта әдiсiнiң алгоритмiн 1-шi таблицада кјрсетiлген транспорттық есептi мысалға кетiре отырып кјремiз. 1. Сij таблицасын, әр бағананың кiшi мәнiн алып басқа мәндерiнен алып тастап ,јсiмiн алу нәтижесiнде Сij таблицасына айналдырамыз. Сij м әндерiн сәйкесiнше Сij мәндерiнiң астына орналастырамыз. 2,Сij таблицасын әр қатардың ең кiшi јсiмшесiн алып, басқа јсiмшелерден осы кiшi јсiмшенi алп тастау нәтижесiнде ^Сij таблицасын аламыз. мәндерiн Сij мәндерiнiң астына жазып аламыз. Егер бельгiлi бiр қатарда нольдiк јсiмше пайда болса, ол қатарды қалдырып, келесi нольдiк јсiмшесi жоқ қатарда јсiмшенi анықтауға јтемiз. 1-шi таблицада јсiмшесiн анықтауға жататын А4 қатары, себебi minС ij =1 сол қатарда орналасқан. 3-шi таблицада кјрсетiл“-“ген нольдер бағаналарының ең кiшi сандарына қатысты бағананың кiшi јсiмшесiн кјрсетедi. 3. Жалғыз нольдiк јсiмшесi бар бағаналарды қарап, мердiгерлердiң запастарына қарамастан, сол клеткаға Вj қажеттiлiктерiн жазамыз. Онан соң екi нольдiк јсiмшесi бар бағаналарды алып, бҰл кезде алдынғы жiктелген қажеттiлктер мен мердiгерлердiң запастарын ескере отырып толтырамыз. Сонан соң ұш нольдiк јсiмшесi бар және онан да кјп нольдiк јсiмшесi бар бағаналарды барлық тҰтынушы қажеттiлiктерiн мердiгерлерге толық жуктегенше толтырамыз.
1-таблицада В1,В2,В3,В5 және В6 бағаналарында бiр – бiреуден нольдiк јсiмшелерi бар. БҰл клеткаларға сәйкес қажеттiлiктердi жазамыз. В4 бағанасында А2В4 және А4В4 клеткаларында орналасқан екi нольдiк јсiмшесi бар. Сондықтан А4 мердiгер зепасын толық қанағаттандыру мақстында 150 бiрлiк бекiтемiз, ал қалған 100бiрлiктi А2 мердiгерге бекiтемiз. Нәтижесiнде алғашқы жiктеулер тҰтынушылардың қажеттiлiгiн мердiгердiң нольдiк јсiмшесi арқылы орналастырулар алдық. 4. қатарлар үшiн аi=ai-xij j=1,2,…m. Егер аi барлығы нольге тең болса, жоспардың қҰрастырылуы аяқталады. Жүктiң барлығы ең кiшi баға јсiмiмен жiктелгендiктен бҰл жоспар оптимальдi болып есептеледi. Жалпы алғанда А.бiр қатарлар үшiн аi =0 (бҰл қатарлар нольдiк деп аталады) Б. басқалары үшiн 0 , мҰндай қатарлар асырмалы деп аталады да “-“ таңбасыиен белгiленедi, ал үшiншiлерi үшiн аi 0 мҰндай қатарлар жеткiлiксiз деп аталады да, “+“ таңбасыиен белгiленедi. Мысалды қарастырсақ а1=450-200=250, а 2=400-100=300, а3=150-700=-550, а4=150-150=0, а5=250-250=0, бҰл дегенiмiз А1 және А2 жеткiлiксiз , А3 асырмалы ал А4 және А5 нольдiк қатарлар. Жабық модель үшiн әрқашан асырмалы қатарлардың аi жиынтығы жеткiлiксiз қатарлардың аi жиынтығына тең болу керек. Ал бiз мақсатты жоспар алуымыз үшiн А3 асырмалы қатардың 550 бiрлiгiн А1 және А2 жеткiлiксiз қатарларға сәйкесiнше 250 және 300 бiрлiктермен орналастыруымыз керек. Бастапқы қателiктер бағаналардың нольдiк јсiмшелерi бойынша жiктелгендiктен кейiнгi қалған қажеттiлiктердi жiктеуiмiз сәйкесiнше транспорттық шығындардың јсуiне алып келедi. Ал бiз қалған жiктелмеген 550 бiрлiк қажеттiлiктi А1 және А3 мердiгерлердiң арасында транспорттық шығындардың минимальдi јсiмшесiн қанағаттандыратындай етiп қайта жiктеуiмiз қажет. БҰл үшiн келесi операцияларды орындаймыз. 5 Асырмалы қатарда клеткалары бар бағаналарды V белгiсiмен белгiлеймiз 1-таблицада ол В2 және В3 бағаналары. 6 ¦рбiр (асырмалы) жеткiлiксiз және нольдiк қатарлар үшiн ^Сij мәндерiнiң ең кiшiсiн таңдап, соңғы бағанаға орналастырамыз. Бiздiң мысалда (А1жеткiлiксiз қатарлар үшiн) min (8,10)=8, (А2 жеткiлiксiз қатарлар үшiн) min (3,4)=3.(А4 нольдiк қатар үшiн) min(4,3)=1 және (А5 нольдiк қатар үшiн) min (12,3)=3. БҰл мәндер бiздiң ендiгi қатарымызда А3 мердiгерден А1,А2,А4,А5 сәйкесiнше мердiгерлерге жүктегенде болатын минимальдi транспорттық шығындардың јсуiн кјрсетедi. 7 Таблицаның соңғы балансындағы жеткiлiксiз қатарлардың ең кiшi ^Сij мәнiн алып, оны ^Сi0j нольдiк қатардағы мәндермен салыстырамыз. БҰл жағдайда екi тұрлi жауап алуымыз мүмкiн, а) әр нольдiк қатар үшiн min ^Сij ^Сi0j, б) кейбiр нольдiк қатарлар үшiн min ^Сij ^Сi0j. 8 Егер (а) шарты орындалса, онда сјзсiз min ^Сij сәйкесiнше асырмалы қорлардан белгiленген бағананың жеткiлiксiзклеткаға қажеттiлiктi қайта жiктеймiз. қайта жiктеу шамасы min(Xij аir ) бҰл жерде Xij - тасымалдау шамасы, ал асырмалы қатардың белгiленген бағанада орналасқан, аir асырмалы және жеткiлiксiз қатардатҰрған айырмашылықтар шамасы. 9 Егер кейбiр нольдiк қатарлар үшiн (б) шарты орындалса, онда осы нольдiк қатар арқылы асырмалы қатардан жеткiлiксiз қатарға јтетiн жолмен қайта жiктеудi тексеремiз. Берiлген жолды анықтау үшiн немесе қҰрастыру үшiн берiлген бағанада^Сi0j min ^Сij үшiн клетканы тауып, оны “+“ белгiсiмен белгiлеймiз, сол қатардан толтырылған клетканы тауып “-“ белгiсiмен белгiлеймiз, бiрақ ол асырмалы қатарда орналасу керек, бҰл берiлген жолдың бастамасы болып табылады. Жылжуды берiлген жол бойымен “-“ тан“+“ ке јтемiз, осының нәтижесiнде нольдiк қатарға тұсемiз, онан соң нольдiк қатар бойымен толтырылған клеткағакјшiп оны “-“ таңбамен белгiлеймiз, сонан соң бағана бойымен жеткiлiксiз қатарға кјшiп, оны “+“ таңбасымен белгiлеймiз. жолымыз қҰрастырылды. Егер матрицада нольдiк қатарлар кјп болса, онда қайта бјлу сызығы бiрнеше нольдiк қатарлар арқылы јтуi мүмкiн және олардың мјлшерi айтарлықтай јседi, сондықтан келесiережеге сұйену қажет. Бiр нольдiк қатардан басқасына јту кезiнде алынған јсiмшелер сомасын аламыз және оны берiлген қатардың кјрсетiлген минимумына теңестiрiп кјремiз. Егер алынған сома берiлген минимумынан асып кетсе, онда берiлген қатар бойымен сызықты қҰрастыруды тоқтатамыз. Сонымен қатар егер жеткiлiксiз қатарға јту кезiнде јсiмшелердiң жиынтығы басқа кез келген нольдiк қатарға кјшу кезiнде алынған јсiмшелердiң жиынтығынан кјп болса сызықтың нольдiк қатар арқылы жалғасуын қарастырудың қажетi жоқ. 10 ¦р сызықтық жол үшiн алгебралық јсiмшелердiң жиынтығы ^Сij қҰрастырамыз. Және оны терiс деп санаймыз егер “-“ балгiмен белгiленген клеткада орналасса, оң деп санаймыз егер “+“ белгiленген клеткада орналасса. алынған соманы min^Сij мен салыстырамыз. А) егер барлық қҰрастырылған сызықтық жолдар үшiн ^Сij min^Сij болса, онда оларды шығарып тастап сјзсiз қайта жiктеудi iске асырамыз. Б) егер ^Сij min^Сij онда осы шама үшiн ең кiшiсi бойынша қайта жiктеудi бастаймыз. БҰл жағдайда мүмкiн болатын қайта жiктеулер сызық бойымен min(xirjp; air ) ға тең болады, бҰл жерде xirjp - таңбасымен белгiленген , 1 r m , 1 p n , клеткада орналасқан тасымалдауларды кјрсетiлетiн сан air – сызықтық жол басталып аяқталатын жеткiлiксiз және асырмалы қатарда орналасқан айырмашылықтар, 1 r m. сызықтық жолмен келе “-“ таңбасымен белгiленген клеткалар санын алып тастаймыз, және “+“ таңбасымен белгiленген клеткаларда орналасқан қайта жiктеу шамасын қосамыз. Осындай шамаға сондай-ақ air шамасын јзгертемiз. Нәтижесiнде мердiгерлерге жүктелген тҰтынушылардың жаңа нҰсқасын аламыз. 1-шi таблицаның соңғы бағанасында жеткiлiксiз қатар үшiн ^Сij= min(8;3)=3 табамыз. бҰл шаманы нольдiк қатар үшiн ^Сi0 j мен салыстырамыз. А4 нольдiк қатарлар үшiн алгоритмнiң 7-шi пунктiнiң (б) шарты қанағаттандырылады, сондықтан, қайта жiктеудi сызықтық жолмен жұргiземiз. сызықтық жолды қҰрастыру үшiн белгiленген бағанада және А4 қатарында тҰрған 1-ге =^С42 сiмшесiн табамыз және осы клетканы “+“ деген белгiмен белгiлеймiз. асырмалы қатарда орналасқан және В2 бағанасындағыА3В2 толтырылған клеткаға кјшiп оны “-“ деген белгiмен белгiлеймiз. жылжуды А3В2 - В2А4 сызығының буындарынан бастап А4 нольдiк қатарына келемiз,ондағы толтырылған А4В4 клетканы табамыз оны “-“ таңбасымен белгiлеймiз , сонан соң В4 бағанасы бойымен жеткiлiксiз қатардың клеткасына јтемiз. Берiлген мысалда сызықтық жолды екi нүктеде А1В4 және А2В4 аяқтауға болады және олардың таңбалары “+“ А3В2 –В2А4 –А4В4 – В4А1 және А3В2 –В2А4 – А4В4 – В4А2 деген екi сызықтық жол алынды. Сызықтық жолдар арқылы јсiмшелер сомасын табамыз. ^Сij=-0+1-0+1=2 бiрiншi сызық үшiн ^Сij=-0+1-0+0=1 екiншi сызық үшiн Екi жағдайда да сомасы 3-тен кiшi. Сондықтан екеуi де бiзге жарайды. қайта жiктеу үшiн 12 екiншi сызықтық жолды таңдаймыз. қайта жiктеу шамасын анықтаймыз, min(350,150,550,300)=150. Сызықтық жолмен жылжий келе 150 бiрлiктi жiктеп бјлемiз, содан кейiн a2 және a3 осындай бiрлiкке јзгертемiз. нәтижесiнде 2-шi таблицада кјрсетiлген жаңа жiктелген қажеттiлiктердi аламыз. 11 қайта жiктеуден кейiн берiлген бағаналарды шығару мүмкiндiгiн қарастырамыз. Бағаналарды белгiлеулерден шығарып тастаймыз егер, асырмалы қатадың толтырылған клеткасы толтырылмаған клеткаға немесе асырмалы қатар нольдiк қатарға јзгерсе. МҰндай жағдайда келесi операцияларды алгоритмнiң 6-шi пунктiнен бастаймыз. Егер белгiленген бағаналар саны јзгерiссiз қалса келесi операцияларды алгоритмнiң 7-шi пунктiнен бастаймыз. 12 қайта жiктеу процесiн барлық қатарларға айналғанша қайталай беремiз. Алынған тасымалдау жоспары оптимальдiлiкке потенциалдар әдiсiмен тексеремiз. 2-шi таблицада белгiленген бағаналар мен жеткiлiсiз қатарлар бiрiншi операциядан кейiн јзгерiссiз қалды, сондықтан алдынғы жағдайдағыдай min^Сij=3 және А4 қатары үшiн 13 бар. А2В2 клеткасынан басталатын сызықтық жолмен қайта жiктелудi тексеремiз және ол сызық А4 қатарының А4В4 клеткасынан јтедi. Бiрақ А4В2 клеткасынан А4 нольдiк қатар бойымен жұруге болмайды, себебi онда басқа толтырылған клеткалар жоқ. Нольдiк А5 қатар үшiн min^Сi0j=3 бар, сондықтан сјзсiз А3 қатарынан А2В2 клеткасына қайта тiркеймiз себебi ол клетка min ^Сij. Ендiгi жағдайда қайта жiктеу шамасын анықтаймыз min(150,400,150)=150 және оны 2-шi таблицаға јндiрiп енгiземiз. Нәтижесiнде 3-шi таблицада келтiрiлген жаңа бекiтiлгендердi аламыз. қайта жiктеу нәтижесiнде А3В2 клеткасы бос болып қалады, В2 бағанасы белгiленгендерден шықты, А2 қатары нольдiк қатар болды. Таблица -2
min ^Сij асырмалы және нольдiк қатарлар үшiн белгiленген бағаналарды тауып, осы мәндердi соңғы бағаналарға енгiземiз. Жеткiлiксiз бағаналар үшiн min^Сij=10 табамыз. Нольдiк қатарда орналасқан ^Сi0j мәндерiнiң кез келгенi оннан кiшi, сондықтан қайта жiктеу мүмкiншiлiгiн барлық нольдiк қатарлар үшiн тексеру керек. Тексерудi А5 қатарынан (нольдiк) бастаймыз. Себебi оған min^Сi0j =3 сәйкес. А5В3 клеткасын оң деп алып сызықтық жолды “-“ таңбсымен белгiленетiн А3В3 клеткасынан бастаймыз. А5 қатарында толтырылған клетка екеу, сондықтан олардың әр-қайсысы бойынша жұрiп јсiмшелердiң сомасын анықтаймыз, А3В3 -А5В3- А5В5- В5А1=-0+3-0-1=4 А3В3 -А5В3-А5В6-В6А1=-0+3-0+5=8 Бiрiншi сызықтық жол үшiн јсiмшелер сомасы тјртке тең болғандықтан басқа да нольдiк қатарлар үшiн ^Сi0j =4, олар арқылы қайта жiктеу тиiмдi емес. қайта жiктеу min(400,150, 150)=150 бiрiншi сызықтық жолмен жұргiзiледi. Нәтижесiнде А5 қатарындағы (нольдiк) А5В3 клеткасынан сызықтық жолмен қҰрастыруды бастаймыз. Ол 4-шi таблицада кјрсетiлген Таблица -3
А3В3-В3А5-А5В6-В6А1 -0+3-0+5=8 және А3В3-В3А5-А5В6-В6А2-А2В4-В4А1 -0+3-0+3-0+1=7 Сызықтық жолдары 4-тен әлде қайда ұлкен мәндер кјрсетiлiп отыр, сондықтан қайта жiктеулердi басқа нольдiк қатарлар арқылы мүмкiндiгiн тесеремiз. А2 қатар үшiн А3В3-В3А2-А2В4-В4А1 –0+4-0+1=5 А3В3-В3А2-А2В2-В2А1 -0-4-3+8=9 А4 қатары үшiн А3В3-В4А4-А4В2-В2А1 –0+4-1+8=11 А3В3-В3А4-А4В2-В2А2–А2В4-В4А1 –0+4-1+3-0+1=7 Ішiншi сызықтық жол арқылы қайта жiктеудi iске асырамыз. min(250,250, 100,100) =100. Нәтижесiнде барлық қатарлары нольге келтiрiлген 5-шi таблицаны аламыз. Ал бҰл дегенiмiз соңғы операция нәтижесiнде жоспарымыз алынды. қҰрастырылған потенциалдар жұйесi бҰл жоспардың потимальдi екенiн кјрсетедi. Дельта әдiсiмен шешкенде итерация саны кјбiне қатарлар санына байланысты болады. Сондықтан mn болғанда тҰтынушыларды мердiгерлер деп алады, ал mn болғанда мердiгерлердi тҰтынушыларға байланысты- рады. Дельта әдiс сонымен қатар тарнспорттық есептi ашық тұрiн жабық тұрге келтiрмей есептеуге мүмкiндiк бередi. Таблица -4
Таблица -5
Дельта әдiсiн кјбiне ЭЕМ мен есептейдi, ал ЭЕМ-сiз есептегенде ашық есептi жабық модельге айналдырып алады. Транспорттық есептердi шешуде дельта әдiсiн есеп јте кјп мердiгерлер мен тҰтынушылардан тҰрғанда бiзге јте тиiмдi, және қатар саны кјбейген сайын бҰл әдiстiң тиiмдiлiгi байқала бередi. Дельта әдiспен шешкен кезде оптимальдi шешiм шығуына кепiл бар. Дельта әдiсi сонымен қатар ашық транспорттық есептердi жабық кұйге келтiрмей шығаруға мүмкiндiк бередi.Ал егер транспорттық есеп шағын болса дифференциалды рента әдiсiн пайдаланамыз себебi дифференциалды рента әдiсi јте қарапайым логикалық шешу жолдарына негiзделген және есептеу әдiсi де қарапайым. жүктеу/скачать 457.5 Kb. Достарыңызбен бөлісу:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||