Сызықтық жоспарлаудағы екіұшты есеп

 

Жоғарыда  айтылған нольдік тасымал  A2 - ден   B2 -ге істелген.

 

Базистік  жоспар тасымалы (таблицадаңы тасымал) мақсаттық функцияның төмендегі  мәнін (барлық тасуға кеткен шығын) береді:

 

L₀=30×7+70×3+20×3+40×8+20×2+20×6+20×3+30×4=1140.

 

Бұл әрине тиімді тасымал емес.

 

Ескерту. Әрбір тасымал жасағаннан кейін жаңылысып кетпес үшін таблицаның оң жағы мен төмендегі жағына тасығаннан кейін қалған материалдар мөлшері мен қанағаттандырылмай қалған сұраныс мөлшерлерін жазып қойған дұрыс.

 

 

 

 

 

Минималь элемент ережесі

 

Біз жоғарыда солтүстік-батыс әдісін келтірдік. Осылай етіп солтүстік-шығыс, немесе оңтүстік-татыс, оңтүстік-шығыс сияқты әдістер қарауға  болады. Тек әйтеуір бір базис  жасау керек болғасын жәй бір  бұрыштан бастап істелген процедура  ғой, оның тасымал шығындарымен ешқандай байланысы жоқ. Сондықтан бастапқы базистік жоспарымыз тиімді базистік жоспардан тым алыс орналасқан болуы  да мүмкін. Келтірейін деп отырған  минималь элемент ережесінде тасымал  шығындары әуел бастан ақ ескеріліп  шама келгенше алғашқы базистік жоспарды тиімді жоспарға жақынырақ алуға  мақсатталған. Дегенмен кей жағдайда солтүстік-батыс әдісінің базистік жоспары тиімді жоспарға минималь элемент  жоспарынан жақынырақ болуы мүмкін (өте сирек болады).

 

Таблицаны қарастырып тасымал шығыны ең аз болатын  ұяны таңдап аламыз. Біздің жағдайда ол (4,1) ұясы  с₄₁=1. Сондықтан тасымал мөлшерін таңдап аламыз: х₄₁=min{50,30}=30, яғни A4  қоймасынан B1  тұтынушыға 30 бірлік материал тасимыз, сонда A4  қоймасында 20 бірлік материал қалады. B1  бағанын әрі қарай қарастырмаймыз, себебі B1 тұтынушының сұранысы толық қанағаттандырылды. Осы қадамнан кейінгі (яғни  B1 бағаны алып тасталған) таблицаны C1 деп белгілейміз.

 

С матрицасы		Тұтынушылар												Қоймадағы материалдар мөлшерінің қосындысы
		B1		B2		B3		B4		B5		B6
Қоймалар	A1		7		3		8		4		5		2	100
	A2		5		7		3		8		4		6	60
	A3		3		8		4		2		6		9	40
								40
	A4		1		6		7		5		3		4	20
		30
Сұраныстар қосындысы		30		70		20		60		40		30		220

 

 

С1 матрицасы		Тұтынушылар										Қоймадағы материалдар мөлшерінің қосындысы
		B2		B3		B4		B5		B6
Қоймалар	A1		3		8		4		5		2	100
	A2		7		3		8		4		6	60
	A3		8		4		2		6		9	0
						40
	A4		6		7		5		3		4	20
Сұраныстар қосындысы		70		20		20		40		30		180

 

Әрі қарай осылай жалғастыра береміз

 

С2 матрицасы		Тұтынушылар										Қоймадағы материалдар мөлшерінің қосындысы
		B2		B3		B4		B5		B6
Қоймалар	A1		3		8		4		5		2	70
										30
	A2		7		3		8		4		6	60
	A4		6		7		5		3		4	20
Сұраныстар қосындысы		70		20		20		40		0		150

 

Ең  соңында мынандай таблица аламыз:

 

С3 матрицасы		Тұтынушылар				Қоймадағы материалдар мөлшерінің қосындысы
		B4		B5
Қоймалар	A2		8		4	40
	A4		5		3	20
Сұраныстар қосындысы		20		40		60

 

 

Сонымен осы табылған тасымалдарды бастапқы таблицаға жинақтасақ мынадай алғашқы  базистік жоспарды аламыз:

 

		Тұтынушылар												Қоймадағы материалдар мөлшерінің қосындысы
		B1		B2		B3		B4		B5		B6
Қоймалар	A1		7		3		8		4		5		2	100
				70				0				30
	A2		5		7		3		8		4		6	60
						20		20		20
	A3		3		8		4		2		6		9	40
								40
	A4		1		6		7		5		3		4	50
		30								20
Сұраныстар қосындысы		30		70		20		60		40		30		250

 

 

Мақсаттық функцияның мәні, яғни осы базистік жоспардағы тасымал шығыны L₀=740 болады. Енді осыны солтүстік-батыс әдісімен табылған тасымал жоспарымен салыстыралық: ол L₀=1140. Сонымен осы екі базистік жоспардың қайсысы тиімді жоспарға жақынырақ екені көрініп тұр. Әрине, егер алғашұы жоспарымыз тиімді жоспарға жақынырақ болса, кейін тиімді жоспарды іздегенде жасайтын қадамдар саны аз болады.

 

 

Тасымал есебін шығарудың  потенциалдар әдісі

 

Потенциалдар  әдісін мысал арқылы түсіндірген  қолайлырақ болады.

 

	В1	В2	В3	В4	В5
А1	1	2	3	4	5
А2	3	1	5	3	2
А3	4	2	1	5	1
А4	2	3	1	2	4

Мысал. А1, А2, А3, А4 пунктерінде орналасқан қоймаларда біртектес материалдардың сәйкес  50, 40, 60, 21   тонналары бар болсын. Осы материалдарға В1, В2, В3, В4, В5  пунктерінде орналасқан тұтынушылардан сәйкес  15, 25, 36, 10, 85   тонна материалдарға сұраныс келіп түскен болсын. Бір тонна материалды қоймадан тұтынушыға жеткізу шығындары мың теңгемен  есептегенде таблицада келтірілген.  Барлық сұраныстар толығымен қанағаттандырылатын жалпы тасымал шығыны мейлінше аз болатын тасымал жоспарын жасау керек.

 

Шешуі. Есепті шығару үшін сол жақтаңы таблицаны құралық. Ол таблицадағы ұялардың жоғарғы оң жақ бұрышына кішкентай ұяшық жасап, оларға сол ұяшыққа сәйкес тасымал бағалары жазылған.

 

	В1		В2		В3		В4		В5					В1		В2		В3		В4		В5
А1		1		2		3		4		5	50		А1		1		2		3		4		5	50
														15		25		10
А2		3		1		5		3		2	40		А2		3		1		5		3		2	40
																		26		10		4
А3		4		2		1		5		1	60		А3		4		2		1		5		1	60
																						60
А4		2		3		1		2		4	21		А4		2		3		1		2		4	21
																						21
	15		25		36		10		85					15		25		36		10		85

 

Енді  солтүстік-батыс әдісімен алғашқы  базистік жоспар құрамыз. A1  пунктінен B1  пунктіне тасымал жасаймыз,  B1 тұтынушы тек қана  15 тонна сұрап отырғандықтан  A1 пунктінде тағы да 35 тонна материал қалып қойды. B1 бағаны толық қанағаттандырылғандықтан ол бағанды әрі қарай қарастырмаймыз. Әрі қарай A1  пунктінен  B2  тұтынушыға 25 тонна материал тасимыз, оның сұрап отырғаны 25 тонна ғана. Ол қанағаттандырылып болғандықтан ол бағанды да әрі қарай қарастырмаймыз. Енді A1 пунктінде әлі де 10 тонна материал қалды. Оны B3  пунктіне тасимыз. Бірақ ол тасымал B3  тұтынушыны қанағаттандырмайды, оған әлі де 26 тонна керек. Бірақ   A1 пунктінде материал таусылғандықтан  A1 жолын әрі қарай қарастырмаймыз. Енді  B3 тұтынушының сұранысынан қалып тұрған 26 тонна материалды  A2 пунктінен тасимыз. Сонда B3  тұтынушы толық қанағаттандырылады. B3  бағанын әрі қарай қарастырмаймыз. Енді A2  пунктінде тасылмаған 14 тонна материал қалды. Оның 10 тоннасын B4  тұтынушыға тасимыз, ол толық қанағаттандырылғандықтан  B4 бағанын әрі қарай қарастырмаймыз. Енді  A2 пунктінде тасылмаған   4 тонна материал қалды, оны   B5 тұтынушыға тасимыз. A2  пунктінде материал қалған жоқ, сондықтан A2  жолын әрі қарай қарастырмаймыз. Енді  B5 тұтынушыға әлі де 84 тонна материал керек. A3  пунктінде 60 тонна бар, оның бәрін де B5  тұтынушыға тасимыз. A3  пунктінде материал қалған жоқ,  A3 жолын әрі қарай қарастырмаймыз. Енді B5  тұтынушыға әлі де 21 тонна материал керек. Оны A4 пунктінен тасимыз. A4  пунктінде материал қалған жоқ. Есеп жабық есеп болғандықтан барлық материал тасылды, барлық сұраныс қанағаттандырылды.

Сонымен бізде алғашқы базистік жоспар бар. Ол жоғарыдағы оң жақтағы таблицада  келтірілген. Тасымал шығын 15*1+25*2+10*3+26*5+10*3+4*2+60*2+21*4 =467 болады. Енді осы базистік жоспарды жақсарту керек.

Енді  осы мақсатпен потенциалдық әдісті қолданамыз. Номерлері ij  (i жол номері, j  баған номері) болатын ұяға  ui, vj   сандарын сәйкестікке қоямыз. Бұл сандарды потенциалдар деп атаймыз. Енді

 

сij=ui+vj

 

теңдеулерін құрамыз. Мұнда сij саны i пунктінен j  пунктіне бір тонна материал тасуға кететін шығын. Төмендегідей теңдеулер системасын құрамыз:

u1+v1=1; u1+v2=2; u1+v3=3; u2+v3=5; u2+v4=3; u2+v5=2; u3+v5=1; u4+v5=4.

Теңдеулер саны 8 (толтырылған ұяшықтар саны 8, теңдеулер тек толтырылған ұяшықтар үшін құрылады). Белгісіз  ui, vj шамалар саны 9 (барлық уақыттар теңдеулер санынани 1 санына көп болады).  Сондықтан белгісіздердің біреуіне (қалаған белгісізге) қалаған мәнімізді беріп, қалған белгісіздерді табамыз. Айталық u1=0  деп алалық. Оны бірінші теңдеуге қойып v1 - ді табамыз. Оның мәнін екінші теңдеуге қойып v2  -ні табамыз. Әрі қарай шеше беріп мынандай шешімдерді аламыз: