Транспорттық есептiң қойылуы
Транспорт есепбiнiң тiрек жоспарын анықтау
жүктеу/скачать 457.5 Kb.
|
| 2. Транспорт есепбiнiң тiрек жоспарын анықтау
Транспорт есепбiнiң оптимал жоспарын анықтау, оның кейбiр тiрек жоспарын табудан басталады. Бұл жоспарды солтүстiк – батыс бұрышы әдiсi, минималды элемент әдiсi және т.б. әдiстермен табуға болады. Бұл әдiстiң мәнi, шарттық таблицада есеп шартын бiр клеткада толтыратын, әрқайсысындағы (n+m-1)- қадамымен, таяныш жоспарды табады. Б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лген қадамдар (m+n-2) қалай жасалғанынан, бiр жiберу және бiр тағайындалған нүктеден есептi алады. Осы жағдайларда тек бiр клетка бос қалады, ал қалған жiберу нүктесiнiң қоры қалған белгiленген нүкте қажеттiлiктерiне тең болады. Осы клетканы толтырып, (m+n-1) қадамын жасайды және 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нш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р интеграцияда, 2 рет жазылған минималды тариф айырмашылығын табады. Бұл айырмашылықты арнайы соларға бөл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н алғашқы жоспардағы n+m-1 клеткаларының бос емесiн алуға кепiлдеме беретiн әдiстердiң бiрiн қолданамызмыз. Алынған жоспарды оптималдылыққа тексеремiз. Теорема 2. Егер кейбiр таяныш жоспар үшiн X=(X)(i=1,m; j=1,n) транспортттық есепте келесi сандар бар, барлығы үшiн i=1, m және j=1n, яғни X=(X)- транспорттының есептiң оптималды жоспары. Анықтама 3. Сандар тағайындалған және тұтыну нүктесiне сәйкес потенциалдар деп аталады. Жасалған теорема транспорттық есеп шешiмiн табу ассортименттiн құруға мүмкiндiк бередi. Жоғарыда келтiрiлген әдiстердiң бiреуiнен таяныш жоспарды табайық. Жеткiзу және тағайындалған әрбiр нүктелер үшiн потенциалдарды анықтау үшiн, (3)-шi теңдiк жұйесiнен бұл сандарды табамыз. Мұнда, Сij-транспорттың есептiң шарттық таблицаларында толтырылған клеткалардан тұратын тарифтер. Толтырылған клеткалар саны (n+m-1)- ге тең болғандықтан, (n+m) айнымалысы бар (8) жұйе (n+m-1) теқдiгiн құрайды. Белгiсiздер саны теңдiк санынан бiр бiрлiкке жоғары болғандықтан, белгiсiздердiң бiреуiн тұындама санына тең деп алуға болады, мысалы, d1=0 деп алып, (8)-шi теңдiктен қалған белгiсiздiң шешiмiн табу керек. Сосын барлық потенциалдар табылған соң, әрбiр бос клетка үшiн Aij=Bj-Ai-Cij cандары анықталады. Егер кейбiр бос клеткалар үшiн Aij>0 болса, онда таяныш жоспар оптималдық болып табылады және басқа таяныш жоспарға өту қажет. Осы сан тиiс клетканы, толтыру керек. Таңдап алынған клетканы толтырып, басқа бос емес клеткалар қатарына жазылған және басқа бос емес клеткалар қатарымен байланысты және толтырумен байланысты, жабдықтау көлемiмен өзгерту қажет. Анықтама 4. Цикл деп – шарттық таблицада төбелерi, таблицаның бос емес клеткаларында орналасқан, сынық сызық деп аталады, ал звенья- циклдың әрбiр төбесiнде, қатар мен бағана жолында 2 звено кездесед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. Бұрын бос болған клетка бос емес болады, ал Хij сандарының минималдылығында тұрған минусты клетка бос болады. Нәтижесiнде берiлген бос клеткасы бар циклмен байланысты клеткалар аумағында орналастарылған жүктi жаңа таяныш жоспарды анықтайды. Берiлген таяныш жоспардан басқасына өту қайта есеп цикл бойынша қозғалыс деп аталады. Есеп цикл бойынша қозғалыстық бос емес клеткаларындағы саны өзгерiссiз қалады, яғни тең болып, (n+m-1) қалатындығын амон өту керек. Егер минустыларды Хij -дiң 2 бiрдей саны болса, онда осындай клеткалардың тен бiреуiн ғана босатады, ал қалғандарын бос емес етiп (нольдiк жабдықтаумен) қалдырады. Алынған жаңа жоспарды оптималдыққа тексередi. Бұл үшiн тағайындалған және анықьалған нүктелердiң потенциалын анықтайды және барлық бос емес клеткалар үшiн Aij=Bj-Ai-Cij сандарын табады. Егер осы сандардың арасында оңдары табылса, онда оптималдық жоспар алатынымыз белг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н қатарларды анықтайды. қорлары толық бөл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 жазылған. Алдыңғы таблицада мезетаралық рента жазылған, бағанада 2 бiрдей сан домалақшада қорытындыланады. Бағана санына қарағанда толықтырмалы клетканың саны жаңа таблицада көп болса, онда клеткаларды толтыруда, келесiлерден тұратын арнайы ереженi қолдану керек. Онда домалақшамен орналасқан бiр клеткасы бар бiр бағананы қарастырудан шығарады. Сосын домалақшамен орналасқан бiр клеткасы бар қатарда қарастырудан шектейдi. Осылай жалғастыра отырып, соңғы санның қадамынан кейiн, онда санмен толтырылатын домалақшалар орнатылған барлық клеткаларды толтырады. Егер тағайындалған нүктелер арасында жiберу нүктесi бар барлық жүктi бале алса, онда жаңа оптималдық жоспарды алады. Егер де оптималдық жоспар алынбаған болса, онда жаңа таблицаға өтедi. Ол үшiн қалдықтық және жетiспейтiн қатарлар, мезетаралық рента мен осының негiзiнде жаңа таблицаны құрады. Бұл жағдайда оның бөлiнбеген қалдығы 0-ге тең болған жағдайда, қатар белгiсiн анықтауды кейбiр қиыншылықтар тууы мүмкiн. Мiне мұндайда тағы бiр клетканы толтырылған клетканы, оң қатарда орналасқан жағдайда қатарды оң деп санайды. Жоғарыда бейнеленген интерацияда соқ ғы саннан кейiн бөлiнбеген қалдық нөльге тең болады, нәтижесiнде берiлген транспорттық есептiң оптималдық жоспарын алады. Мысал1: таблица 1 – де келтiрiлген алғашқы берiлгендер транспорттық есеп үшiн, оптималдық жоспарды табамыз. Таблица жiберу тағайындалған нүктелер қорлар пунктары В В2 В3 В4 А1 1 2 4 1 50 А 2 2 3 1 5 30 А 3 3 2 4 4 10 қажеттiлiк 30 30 10 20 90 Шешiмi: ең алдымен Солтүстiк-батыс бұрышының әдiсiн пайдаланып, есептiң сұйенушi жоспарын табады. Бұл жоспар таблица 1-де жазылған Табылған таяныш жоспарды оптималдыққа тексередi. Осымен байланысты жiберу және тағайындау нүктелерiнiң потенциалын табамыз. Потенциалды анықтау үшiн, 7 айнымашы бар 6 теңдiктi құрайтын, келесi жұйенi аламыз: B1-A1=1 B2-A1=2 B2-A2=3 B2-A2=1 B4-A2=5 B4-A3=4 Ai=0 теқ деп,B1=1, В2=2, B3=0, B4=4, A3=0, A2=-1 екенiн табамыз. әрбiр бос клетка үшiн келесiнi есептеймiз: Aij=Bj-Ai-Cij: d13=-4, d14=3, d21=d32=0, d31=-2, d33=4 Табылған сандарды рамналарға қорытындылап, таблица 2-нiң әрбiр бос клеткасына жазамыз. Егер Aij сандарында оңдары бар болса, онда қурылған тасымалдау жоспары оптималды болмайды және жақа таяныш жоспарға өту қажет болады. Aij сандарының iшiнде оңдары, ретiнде A14=3 болып табылады, сондықтан берiлген бас клетка үшiн қайта есептеу циклын құрып, осы цикл бойынша қозғалыс жасаймыз. Таблица 2. жiберу тағайындалған нүктелер қорлар нүктелер В В В В А 1 2 - 4 - 4 1 1 50 А 2 3+ 1 5 - 30 А 3 2 4 4 10 қажеттiлiк 30 30 10 20 90 Минусты клеткалардағы бұл сандардың кәсiбi 10-ға теқ болады. Бұл сан орналасқан клетка жаңа таблица 3-те бос сан болады. Таблица 3-те басқа сандан келесiдей болады. Таблица - -нiң плюстi клеткасында орналасқан 10 санына 10-ды қосамыз және таблица 2-нiң минусты клеткасында болатын, 20 санынан 10-ды шығарамыз. А2 қатары мен В4 бағанасының қиылысу қатары бос болады. Осындай жағдайлардан кейiн жаңа таяныш жоспарды табамыз. Т аблица 3. жiберу тағайындалған нүктелер қорлар нүктелер В В В В А 1 2 4 1 50 А 2 3 1 5 30 А 3 2 4 4 10 қажеттiлiк 30 30 10 20 90 Бұл жоспарды оптималдыққа тексеремiз. Жiберу және тағайындалған нүкте потенциалдарын табамыз. Ол үшiн келесi теқдiк жұйесiн құрамыз: B1-A1=1 B2-A1=2 D4-A1=1 B2-A2=3 B3-A2=1 B4-A3=4 A1=0 теқ деп, B1=B4=1, B2=2, B3=0, A3=-3, A2=-1 аламыз. Осындай жолмен, берiлген тасымалдау жоспарының оптималды емес екенiн, көремiз. Сондықтан жаңа таяныш жоспарға өтемiз. Т аблица 4. жеткiзу тағайындалған нүктелер қорлар нүктесi В В В В А 1 2 4 1 50 А 2 3 1 5 30 А 3 2 4 4 10 қажеттiлiк 30 30 10 20 90 Таблица 4-ң бос клеткаларына жауап беретiн жақа потенциалдық айырмашылығын салыстырып сәйкес сандармен, барлық бос клеткалар үшiн көрсетiлген потенцаалдар айырмашылығының сәйкес санға тең емес екенiн, көремiз. Демек, алынған жоспар: Х= оптималды болып табылады. Берiлген жоспарда тасымалдау құны. S=1*30+2*0+1*20+1*30+1*10+2*10=140 Мысал 2 . 4-кәсiпорын өнiм өндiру үшiн шинiзаттық 3 тұрiн қолданады. Шикiзатқа деген әрбiр кәсiпорының қажеттiлiгi 120,50,90 және 110 бiрлiкке тең (Шикiзатқа деген әрбiр кәсiпорыннық қажеттiлiгi). Шикiзат, оны ашудық 3 орнына бағытталған, ал қорлар 160,140,170 –ке тең. әрбiр кәсiпорынға шикiзат, оны алудың әрбiр нүктесiнен әкелiнедi. Жабдықтау тарифтерi танымал көлемдi болып табылады және матрицамен берiледi: С= Жалпы тасымалдау құны минималды болып табылатын, тасымалдаудық осындай жоспарын құру және минималды элемент әдiсiмен таяныш жоспарды табу керек. Шешiмi: Есептiң алғашқы берiлгендерiн таблица тұрiнде жазайық. 1-ге тең минималды тариф Х13 айнымалысы үшiн клеткада болады Х13=160 деп, бұл мәндi таблицаның клеткасына жазамыз және А1 қатарын уақытша қарастырудан шығарамыз, В1 тағайындалған нүкте қажеттiлiгiн 30 бiрлiкке тең деп есептеймiз. А1 және А2 екi қатарымен таблицаның қалған бөлiгiн және В1, В2, В3, В4 4 бағанамен және С төмен мәндi тарифпен, клетка А3 қатары мен В2 бағасының қиылысында болады. Х32=50 қойып, бұл мәндi таблицаның клеткасына енгiземiз. В2 бағанасын уақытша қарастырудан шығарамыз да, А3 нүктесiнiң қорларын 120 бiрлiкке тең деп есептеймiз. Сосын А2 және А3 2 қатары бар және B1, B3, B4 3 бағанасы бар таблицаның қалған бөлiгiн қарастырамыз. Ондағы Cij минималды тарифы A3 қатары мен В3 бағанасы қиылысқан клеткада орналасады және 3-ке тең болады. Жоғарыда бейнеленген әдiс бойынша бұл клетканы толтырамызда, А2 қатары мен В1 бағанасы, А3 қатары мен В4 бағанасы, А2 қатары мен В4 бағанасының қиылысында орналасқан, клетканы толтырамыз. Нәтижесiнде сұйенушi жоспарды табамыз. Х= Берiлген тасымалдау жоспарында тасымалдаудың жалпы құны S = 1*60+4*120+8*20+2*50+3*30+6*90=1530 құрайды. жiберу тағайындалған нүктесi қорлар нүктесi В В В В А 7 8 1 6 160 жүктеу/скачать 457.5 Kb. Достарыңызбен бөлісу:
|