8-Тақырып. Сызықтық бағдарламалаудың тасымалдау есебі Дәріс жоспары (1 сағат)

жүктеу/скачать 1,09 Mb. бет 5/5 Дата 30.03.2023 өлшемі 1,09 Mb. #77398

Байланысты:
‹ҐЄжЁп 8. ЊЏЋђ Є §

Бұл бет үшін навигация:

• Қажеттіліктер
• Жөнелту пунктері
• Жөнелту пунктері Белгіленген пунктер Қорлар
• “Аралық рента “
• 4. Тасымалдау есебінің ашық моделі.

Жөнелту пунктері	Белгіленген пунктер
Қорлар
	В1	В2	В3	В4
A1	1 30	2 20	4	1	50
A2	2	3 10	1 10	5 10	30
A3	3	2	4	4 10	10
Қажеттіліктер	30	30	10	20	90

3-кесте

Жөнелту пунктері	Белгіленген пунктер 3				Қорлар
	В1	В2	В3	В4
A1	1 30	1 -10	2 -2	1 +10	50
A2	2 0	3 20	1 10	5 -3	30
A3	3 +1	2 +3	4 -1	4 -10	10
Қажеттіліктер	30	30	10	20	90

_{ } сандардың арасында оң сандар бар болғандықтан, құрылып отырған тасымалдау жоспары оптималды болып табылмайды және жаңа тірек жоспарына ауысу қажет. _{ } оң сандар арасындағы ең көбі болып _{ } табылады, сондықтан да нақты бос тор көз үшін қайта есептеу циклын құрамыз. 2-кесте және осы цикл бойынша өзгеріс жасаймыз. Азайтылған тор көздердің сандарының ең азы 10-ға тең. Осы сан тұрған тор көз жаңа 3-кестеде бос болады. 3-кестеде басқа сандар мынадай ретте болады: 2-кестедегі косынды тор көзде тұрған 10 санына 10 қосамыз және азайтылған тор көзде тұрған 20 санынан 10 алып тастаймыз. А₂ жолымен В₄ бағанасы қиылысындағы тор көз бос қалады.
Бұл жоспардың оптималдылығын тексереміз. Қайтадан құру және белгілеу пунктерінің потенциалдарын табамыз. Бұл үшін келесідей теңдіктер жүйесін құрастырамыз:





_{ } дей отырып, _{ }, _{ }, _{ }, _{ }, _{ } аламыз. Әрбір бос тор көз үшін _{ } санын _{ }, _{ }, _{ }, _{ }, _{ }, _{ } дей отырып шығарамыз.
Осылай, нақты тасымалдау жоспарының оптималды емес екенін көреміз. Сондықтан да жаңа тірек жоспарына көшеміз.
Жаңа потенциалдың _{ } айырмашылықтарын салыстыра отырып, 4-кестедегі бос тор көздерге жауап беретін, // сандарымен сәйкес берілген потенциалдардың айырмашылықтары бәрі бос тор көз үшін // сандарынан асып түспейді. Демек, алынған жоспары оптималды болып табылады.

Бұл жоспарда тасымаддау құны _{ } құрайды.

4-кесте

Жөнелту пунктері	Белгіленген пунктер				Қорлар
	B1	B2	B3	B4
A1	1 30	2 0	4 -4	1 20	50
A2	2 0	3 20	1 10	5 -3	30
A3	3 -2	2 10	4 -4	4 -3	10
Қажеттіліктер	30	30	10	20	90

3⁰. Тасымалдау СБ есебін дифференциалдық рента әдісімен шешу.

Егер потенциалдар әдісімен транспорттық есептің оптималдық жоспарын анықтау үшін ең бірінші оның тірек жоспарын қүрып, одан кейін ол біртіндеп жақсартылса, ал дифференциалдық ренталар әдісімен ең бірінші тасымалданатын жүктің негізгі бөлігі ең тиімді түрде бөлінеді де (мүндай әрекет шартты-оптималды бөлу делінеді), осыдан кейін келесі итерацияларда жүктің бөчлінбей қалған беліктері біртіндеп бөлініп, аяғында тиімді оптималды жоспар қүрылады.

Мысал. Мына кестеде келтірілген мәліметтер бойынша есепті дифференциалдық ренталар әдісімен шығарайық.

	В1	В2	В3	В4	Жиналған мөлшері ai
А1	7	8	1	2	160
А2	4	5	9	8	140
А3	9	2	3	6	170
Керекті мөлшері bj	120	50	190	110	470

№1 – кестенің әр бағанасынаң минималды тарифтері бар торларды табамызда, оларды белгілейміз (кестеде мұндай торлардың бағалары жұддызшамен * белгіленген). Осы торларды максималды мүмкін бола алатындай шамалармен толтырамыз.

№1	В1	В2	В3	В4	ai	Жетпей- ді(-) Артық(+)
А1	7	8	50 1*	110 2*	160	- 140
А2	120 4*	5	9	8	140	+20
А3	9	50 2*	3	6	170	+120
Керекті мөлшері bj	120	50	190	110	470
Рента r	-	-	3-1=2	6-2=4

Ескерту. Барлық бағаналар бойынша тарифтері минималды торлар белгіленгеннен кейін, олардың барлықтары да мүмкін бола алатын ең үлкен шамалармен толтырылуға тиісті.
Есепте белгілерген торларды ең бірінші бағанадан кейінгі баңаға қарай толтырған дұрыс (соң жақтан оң жаққа қарай ).
Белгіленген торларды толтыру нәтижесінде шартты-оптималды жоспар алынады. Ол В_{1 ,} В₂ қабылдау пункттерін толығымен керекті мөлшерде жүкпен қамтамасыз етеді, В₃ пункті жүкпен керекті мөлшерде қамтамасыз етілмей қалады, ал В₄ пункті жүксіз қалды.
Осыдан кейін қабылдау мөлшеріне жетпей қалған немесе қабылдау мөлшеріненен артық қалған жолдар анықталынады. Есепте А₁ жолда 140 бірліктей жүк жетпейді, В₃ қабылдау пункті әлі 30 бірліктей жүк керек, ал В₄
қабылдау пунктіне 110 бірлік жүк керек. Осы бірінші А₁ жол-теріс таңбалы жол делінеді. А₂ және А₃ жолдарда жүктер артық, өйткені А₂ пункттен В₁ пунктке 120 бірлік жүк жеткізіледі, ал онда әлі 140- 120=20 бірліктей жүк қалды. А₃ пункттен В₂ пунктке 50 бірлік жүк жеткізіледі, онда әлі
170- 50=120 бірлік жүк қалды бірлік жүк қалды ( жүк артық қалған жолдар оң таңбалы делінеді ). Барлық жетпеген және артық жүк бірліктері бірдей:
120+20=140 бірлік жүк артық және 140 бірлік жүк жеткізілмеген.
Осы әрекеттерден кейін, жүктері артық жолдардың ең кіші тарифтерінен (олар А₃В₃ - 3 және А₃В₄ - 6) жүктері жетпейтін жолдардың ең кіші тарифтерін алып тастаймыз. В₁ және В₂ бағаналары үшін мұндай айырым анықталмайды себебі осы бағаналарда белгіленген торлар оң таңбалы (жүктері артық) жолдарда орналасқан. В₃ бағанасында белгіленген торда ең кіші тариф 1-ге тең, ал осы бағанада оң таңбалы жолдардың ең кіші тарифі
3-ке тең. Демек, олардың айырымы 3-1=2. Сондай-ақ В₄ бағанада: 6-2=4.
Сөйтіп, оларды №2 кестенің ақырғы жолына, өздерінің бағанасына жазамыз.
Табылған айырымдардыңең кішісі 2, осы санды: “Аралық рента “деп атайды. Осы әрекеттен кейін №2 кестені құрамыз. Бұл кестенің А₂ және А₃ оң таңбалы жолдарына №1 – кестедегі тарифтерді көшіріп жазамыз да, ал А₁
(теріс таңбалы ) жолдағы тарифтер олардың №1 – кестедегі мәндеріне аралық рентаның мәнін қосу арқылы анықталынады (№2 кесте).
№2 кестеде жоғарыдағы баяндалған әрекеттерді қайталаймыз. Кестеде толтырылған торлардың саны бірге артты. В₃ бағанада ең кіші тарифті (3) екі тор пайда болды. Белгіленген торларды жоғарыдағы келтірілген тәсілмен толтырамыз. Берілген бірдей мағынада есепте белгіленген торларды толтыру мынадай ретте жұргізіледі. Бірінші А₂В_1, А₁В_4, А₁В_3, А₃В_{3 ,} толтырамыз, себебі олар – ешқандай пікір тудырмайтынжалғыз торлар.

№2	В1	В2	В3	В4	ai	Жетпей- ді(-) Артық(+)
А1	9	10	50 3*	110 4*	160	- 0
А2	120 4*	5	9	8	140	+20
А3	9	50 2*	120 3*	6	170	-20
Керекті мөлшері bj	120	50	190	110	470
Рента r	-	5-2=3	9-3=6	8-4=4

Осыдан кейін тағы да жүктері жетпейтін жолдарды анықтаймыз.

Ескерту. Ең бірінші бір-бірден жұддызша * белгілері бар бағандар толтырылады. №2 кестеден – көріп отырмыз: әлі толық бөлінбеген жүк қалдықтары бар.Демек, шартты - оптималды жоспар алынған.Сондықтан келесі кестеге өтеміз. Ол үшін оң таңбалы жолдың ең кіші тарифтерінен теріс таңбалы ( А₃) жолдын белгіленген торлардың тарифтерін алып тастап, ренталарды табамыз, яғни 9-3=6 ; 5 – 2 =3 және 8-4=4 ( №3 кестені қараңыз).

№3	В1	В2	В3	В4	ai	Жетпей- ді(-) Артық(+)
А1	12	13	50 6*	110 7*	160	0
А2	120 4*	20 5*	9	8	140	0
А3	12	30 5*	140 6*	9	170	0
Керекті мөлшері bj	120	50	190	110	470

Ескерту. Әр итерациядан кейін толтырылатын торлардың саны кем дегенде бірге артып отырлады да, ал ескі толтырылңан торлар міндетті түрде толтырылуға тиісті.
Жаңа кестеде А₁ және А₃ (теріс таңбалы ) жолдардың тарифтері ескі (2-шi кестедегі) мәндеріне аралық рента 3-ті қосу арқылы табылған. Белгіленген торларды толтыру жоғарыдағы келтірілген тәртіппен жүгізіледі.
Толтырылған торлар саны немесе , есепте және олардың барлығының тарифы ең кіші мәнді.Демек, оптималды жоспар құрылды. Оны матрица түрінде былай жазуға болады:

Мақсат функциясы:


бірлік


4. Тасымалдау есебінің ашық моделі.

Біз алдыңғы тақырыпта жіберілетін жүктің қосымша қабылдау орындарына баратын жүктің қосындыларына тең болатын жағдайды қарас-тырған болатынбыз, яғни

_{ } мұндағы а_i (i = 1,2,... m) i - шаруашылықтан жіберілетін жүктің мөпшері, ал b_j (j=1.2,...n) j-ші қабылдауорнынақажеттізаттың(жүктің)мөлшері. Тәжірибелік есептерді шығарғанда көп жағдайларда а_i ≠ b_j болуы мүмкін. Транспорт есебіндегі мынажағдай:

орындалатын есептерді ашық транспорт есебі дейді. Кейде мүндай транспорт есептерін баланс бермейтін есептер деп те атайды.
Жабық транспорт есебін шығару үшін оны ашық транспорт есебіне келітру керек.

жүктеу/скачать 1,09 Mb.

Достарыңызбен бөлісу: