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

 

u1=0; u2=2; u3=1; u4=4;

v1=1; v2=2; v3=3; v4=4; v5=0.

Енді тасымал жасалмаған ұялар  үшін  ui+vj-сij  өрнектердің мәндерін есептейміз (тасымал жасалған ұяларда олар нольге тең, солай қылып теңдеу құрған болатынбыз).

 

u1+v4-с14=0+1-4=-3;

u1+v5-с15=0+0-5=-5;

u2+v1-с21=2=1-3=0;

u2+v2-с22=2+2-1=3;

u3+v1-с31=1+1-4=-2;

u3+v2-с32=1+2-2=1;

u3+v3-с33=1+3-1=3;

u3+v4-с34=1+1-5=-3;

u4+v1-с41=4+1-2=3;

u4+v2-с42=4+2-3=3;

u4+v3-с43=4+3-1=6;

u4+v4-с44=4+1-2=3.

Енді осы мәндердің ішінде оң сандар бар ма, жоқ па соны тексереміз. Егер жоқ болса; онда есептің шешілгені, қарастырып отырған базистік жоспар тиімді жоспар. Біздің жағдайымызда оң сандар бар. Олардың ішінде ең үлкенін  таңдаймыз (егер олар бірнешеу болса  кез келген біреуін таңдаймыз). Бізде  ең үлкені 6  саны, ол (4,3)  тасымалына сәйкес болып тұр. Енді цикл құрастырамыз. Ол циклдің бір төбесі 6 саны тұрған төбе (4,3)  болады да қалған төбелері тасымал жасалған ұяларда жататын болуы керек. Айта кететін жайт циклдің төбесі барлық уақытта төрт бола бермейді, бірақ барлық уақытта жұп сан болуы керек. Цикл қабырғалары өзара қиылысуы мүмкін, бірақ қиылысу нүктесі цикл төбесі болмауы керек.

Енді (4,3)  төбесіне «+» таңбасын қоямыз, келесі төбеге «-» таңбасын қойып осылай кезек кезек циклдің барлық төбесіне қойып шығамыз. Содан кейін теріс таңбалар тұрған төбелердің ішінен ең аз мөлшердегі тасымалды таңдап алып (бізде ол 21) тасымалдарды қайта жасап шығамыз. Барлық «+» таңбалы төбелерге 21 санын қосып «-» таңбалы төбелерден 21 санын алып тастаймыз. Ол таблицада көрсетілген.

 

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

 

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

 

Тасымал шығыны

 

15*1+25*2+10*3+5*5+10*3+25*2+60*2+21*1 =282.

 

Егер алдыңғы базистік жоспардағы шығынмен (467) салыстырсақ базистік жоспардың жақсарғанын көреміз.

 

 

Ескерту. Жаңадан базистік жоспар құрған кезде базистік ұялардың сандары потенциалдардың санынан 1 – ге кем болуын қадағалап отыру керек. Циклдің «теріс» төбелерінде бірдей тасымал болған төбеле саны 1 – ден көп бола қойса оларда тасымалды қайтадан есептегенде тасымал болмай қоюы мүмкін. Ондай кезде бос қылып 1 ғана төбені қалдырып қалғандарына ноль жазып тасымал бар деп есептеу керек. Согл нольдік тасымал бар төбелер үшін де потенциалдарды табуға арналған теңдеуді құру керек. Яғни жақсарған базистік жоспар азып кеткен жоспар болмауын қадағалап отыру керек.

 

Бірінші қадамдағыдай операцияны қайтадан жаңа базистік жоспар үшін жасаймыз, яғни тасымал бар ұялар үшін потенциалдарды есептеуге арналған теңдеулер системасын ui+vj-сij құрамыз. u1=0  деп алып сол системаны шешсек мынандай шешімдер аламыз:

 

u1=0; u2=2; u3=1; u4=-2; v1=1; v2=2; v3=3; v4=1; v5=0.

 

Енді бос ұялар үшін ui+vj-сij  өрнегінің мәнін есептесек мыналарды аламыз:

 

u1+v4-с14=-3;       u1+v5-с15=-5;          u2+v1-с21=0;        u2+v2-с22=3;           u3+v1-с31=-2; u3+v2-с32=1;          u3+v3-с33=3;          u3+v4-с34=-3;         u4+v1-с41=-3;        u4+v2-с42=-3; u4+v4-с44=-3;          u4+v5-с45=-6

 

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

 

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

 

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

 

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

 

 

Тасымал шығыны мынаған тең:

 

15*1+20*2+15*3+5*1+10*3+25*2+60*1+21*1=267.

 

Өткендегілермен салыстырып (282,   467) базистік жоспардың жақсарғанын көреміз.

 

Енді тағы да потенциалдарды анықтаймыз:

 

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

ui+vj-сij   өрнектерінің мәндерін тасымал жоқ ұяларға есептейміз:

 

u1+v4-с14=0;            u1+v5-с15=-2;            u2+v1-с21=-3;             u2+v3-с23=-3;     u3+v1-с31=-5; u3+v2-с32=-2;           u3+v3-с33=0;             u3+v4-с34=-3;           u4+v1-с41=-3;      u4+v2-с42=-3; u4+v4-с44=0;           u4+v5-с45=-3.

 

Бұлардың ішінде оң мән жоқ, демек  бұл базистік жоспар тиімді жоспар болғаны. Тасымал шығыны  267 мың  теңге.

 

Тасымал есебі сызықтық жоспарлау  есебінің жеке жағдайы болғанымен одан ерекшелігі барлық уақытта шешімі болады. Есеп шешімі жалғыз болмайды. Тиімді базистік жоспарды тапқаннан кейін потенциалдарды есептегеннен кейін тасымал жоқ ұялардағы ui+vj-сij  өрнектің мәндерін есептегенде олардың ішінде нольге теңдері болса онда ең болмағанда тасымал есебінің тағы да бір тиімді шешімі бар болғаны. Егер тиімді шешім бірнешеу болған кезде олардың ішінен біреуін әртүрлі себептермен таңдап алуға болады (мысалы көптеген бірге істеп келе жатқан ара қатынасы жақсы компанияға ыңғайлысын таңдауға болады).

 

         Төменде тиімді шешімнің екі базистік жоспары келтірілген:

 

	В1	В2	В3	В4	В5			В1	В2	В3	В4	В5
А1	15	20	15				А1	15	14	19	1
А2		5		10	25		А2		11		3	27
А3					60		А3			2		58
А4			21				А4			15	6

 

 

 

 

Тасымал есепті MS Excel программасын қолданып шешу мысалы

 

Мысал (Ресей оқулықтарынан алынған). Мына Наро-Фоминск, Солнечногорск, Домодедово, Балашиха, Ногинск пункіттерінде орналасқан ет комбинаттары бар.  Оларда төмендегідей ет мөлшері бар:

 

Наро-Фоминск – 300 т, Солнечногорск – 240 т, Домодедово-170 т, Балашиха -120 т, Ногинск-320 т, всего 1150 тонна.

 

Осы ет комбинаттарына Мәскеудің әртүрлі  аудандарында орналасқан тұтынушылардан сұраныс түскен:

 

Лужники-240 т, Сокол-115 т, Измайлово-280 т, Юго-Запад-370 т, барлығы 1005 тонна. Яғни есеп жабық есеп емес.

Тасымал шығыны (рубль/тонна, ескі рубольдермен есептелген) төмендегә таблицада  көрсетілген.

 

 

 

 

Енді MS Excel программасын ашамыз. Онда сызықтық жоспарлау есебін шешкендегідей – «Поиск решения» опциясын қолданамыз (егер ол қондырылмаған болса сызықтық жоспарлау есебінде көрсетілгендей әдіспен оны қондырамыз).  Сосын төмендегідей таблица жасаймыз (формулалар түсінікті болуы үшін MS Excel бетінің бағандары мен жолдарының аттары суретте көрсетілген).