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

Міне  бұл есеп тасымал есебі деп (жабық тасымал есебі деп) аталады.

Жоғарыда  айтып кеткендей, тасымал есебін сызықтық жоспарлау есебі ретінде  қарауға болады. Онда ол есептің  түрі мынадай болады:

 

       (3)

     (4)

Бұл сызықтық жоспалау есебінің ерекшелігі, шектеулердегі белгісіздердің алдындағы  коэффициенттер бірге тең. Осы ерекшелікті пайдаланып есепті жеңілірек әдіспен шығаруға болады.

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

Енді  осыларға тоқталыңқырай кетелік.

Айталық  болсын, яғни қоймадағы материалдар сұраныстан көп болсын. Әрине тасымал жасалып болғаннан кейін қоймалардың бірінде немесе бірнешеуінде артық материал қалуы керек. Бізге қай қоймада артық зат қалса да бәрі бір болсын делік. Онда біз қосымша n+1 -інші тұтынушы енгіземіз де ол  материалға сұраныс беріп отыр деп есептейміз. Барлық қоймалардан осы тұтынушыға тасу шығыны нольге тең деп есептейміз, яғни c_in+1 = 0 болсын деп жаңа тасымалдау есебін шығарады. Есеп шыққаннан кейін n+1 -  інші тұтынушыға келуі керек материалдар қоймада қалады. Яғни x_in+1 мөлшеріндегі материалдар  i - інші қоймада қалады.

 

Енді    болсын, қоймадағы материалдар мөлшері сұранп отырған материалдар мөлшерінен аз болсын. Егер бізге қай тұтынушыға материал жетпей қалса да бәрі бір болса, онда қосымша m+1  -інші қойма енгізіп сол қоймада жетпей тұрған материалдар мөлшері бар деп есептейміз. Және бұл кезде осы қоймадан барлық тұтынушыларға материал тасу бағасы нольге тең деп есептейміз, яғни  c_m+1j = 0. Сосын есеп жабық есеп түріне келеді, есеп шыққаннан кейін осы ойдан енгізген қоймадан тасылатын заттар тұтынушыларға бармай қалады, яғни олардың сұраныстары орындалмайды.

Енді  тағы да   болсын делік.  Біз тағы да ойдан шығарылған бір қойма қосып онда   мөлшеріндегі жетпей тұрған материалдар бар деп есептейміз.  Бірақ алдыңғыдан өзгешелігі енді осы қоймадан тқтынушыларға материал тасу бағасы нольге тең деп алмаймыз. Айталық j - інші тұтынушы  m+1   - інші қоймадан материалдың бір өлшемін (кг, метр, т.с.с.) алмай қалса ол   мөлшеріндегі шығынға (немесе алынбай қалған табысқа) тап болатын болсын. Сол шығын мөлшері c_m+1j   деп есептейміз. Сонда бұл қоймадан «тасылуы» керек материалдар жоқ материалдар болғандықтан ондай материалдарды тұтынушыларға бармайды. Есепті жабық түрге келтірдік, бірақ мақсаттық функцияның түрі енді басқаша болады, онда тек қана тасымал шығындары ғана емес, сұранған материалдар алынбай қалғанда болатын тұтынушылардың шығындары да есептеледі:

 

Жалпы тасымал есебінің шартын келтіргенде  оны төмендегідей таблица түрінде  жазады (осы таблица әрі қарай  есеп шығарған кезде қолданылады).

 

		Тұтынушылар								Қоймадағы материалдар мөлшері (сумма запасов)
		B1		B2		…		Bn
Қоймалар	A1		c11		c12		…		c1n
	A2		c21		c22		…		c2n
	…		…		…		…		…	…
	Am		cm1		cm2		…		cmn
Сұраныстар (сумма заявок)

 

Ескерту. (4) шарттар сызықтық тәуелді болады, себебі олардың оң жақтары (1) шартты қанағаттандыруы керек. Сонымен (4) системадағы m+n теңдеулерде m+n-1   тәуелсіз теңдеулер бар. Белгісіздер саны m×n . Теңдеуді базистік айнымалылар саны   m+n-1, ал бос айнымалылар саны k= m×n-( m+n-1)=(m-1)×(n-1)  болады. Ал тасымал есебі сызықтық жоспарлау есебінің дербес жағдайы болғандықтан есеп шешімінде ең болмағанда

(m-1)×(n-1)

тасымал нольге тең болуы  керек.

Есеп  шығарған кезде A_i  қоймасынан B_j  тұтынушыға тасылатын материал мөлшері   A_i бағаны мен B_j жолының қиылысындағы ұяға жазылады. Ол ұяны (i,j))  деп белгілейміз. Таблицадағы нольге тең емес тасымалдар мөлшері жазылған ұяларды базистік ұялар деп, ал қалған ұяларды (яғни тасымал болмайтын ұяларды) бос ұялар деп аталық.

 

 

Базистік жоспар

 

 

Тасымал есебін көп жағдайда потенциал әдісімен шешеді. Оның негізгі идеясы мынандай:

• әуелі бастапқы базистік жоспарды құрады (яғни бастапқы тасымалды жасайды), мұнда тасымал жасалатын ұяларға тасылатын материал мөлшері жазылады;
• осы жоспар тиімді жоспар ма, әлде тиімсіз жоспар ма, соны анықтайды (оны анықтайтын арнайы әдіс бар);
• егер ол тиімсіз жоспар болса оны жақсартатын жаңа жоспар құрады (оның да әдісі бар);
• сосын тағы да осы жаңа жоспар тиімді ме, болмаса әлі де жақсарту керек па тексереді;
• осылай әрі қарай тиімді жоспарға жеткенге дейін жасай береді.

Есеп  шығарып жатқанда бастапқы жоспар, немесе кейін жақсартылған жоспарлар  азыған жоспар болмауын қадағалау керек.

Егер  жоспардағы базистік ұялардың саны  m + n -1  - ден кіші болса, ондай жоспарды азыған жоспар дейді. Егер есеп шығарып жатқан кезде базистік жоспар азыған жоспар болса онда кейбір ұяларға нольге тең тасымал қойып базистік ұялар санын қажетті мөлшерге, яғни  m + n -1 - ге жеткізу керек болады. Нольге тең тасымал жасағанда тасымалдағы тасылатын материал мөлшері де тасуға кеткен шығын да өзгермейді. Бірақ нольдік тасымалды кез келген ұяға қоюға болмайды. Төменде толықтырылған жоспар қанағаттандыруы керек шарт келтірілген.

 

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

• сынық сызық тұйық сызық болады, яғни сынық сызықтың басы мен аяғы бір ұяда болады;
• сынық сызықтың төбелері ұяда болады;
• сынық сызықтың көрші екі төбесі бір жолда немесе бір бағанда орналасады;
• сынық сызықтың қабырғалары өзара қиылысуы мүмкін, бірақ қиылысу нүктесі сынық сызықтың төбесі болмауы керек.

Сынық сызықтың төбелерін циклдің ұялары деп те атайды.

 

Егер  базистік жоспарда цикл жоқ болса, ондай жоспарды ациклдік жоспар деп атайды. Тиімді тасымал жоспары ациклді жоспар болатыны дәлелденген мәселе. Сондықтан алғашғы базистік жоспар да, кейінгі базистік жоспарлар да ациклдік болуы керек. Егер базистік жоспар азып кеткен жоспар болса, оны нольдік тасымалмен толықтырғанда оның ациклдік болу шартын қадағалау керек.

Алғашқы базистік жоспар құрудың солтүстік-батыс, минимальдық элемент деген екі  әдісі жиі қолданылады, біз оларға тоқталамыз.

 

 

 

 

 

 

 

Бастапқы базистік жоспарды анықтау

 

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

 

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

 

		Тұтынушылар												Қоймалардағы материалдар  мөлшері
		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
	A4		1		6		7		5		3		4	50
Сұраныстар қосындысы		30		70		20		60		40		30		250

 

 

Солтүстік-батыс бұрыш  ережесі

 

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

Сонымен келтірілген таблицаның сол жақ  жоғары бұрышына тасымал жүргіземіз, яғни   A1 - ден  B1 -ге тасимыз. Енді   A1 - дегі материал мөлшері мен B1 - дің сұраныс мөлшеріне қарап төмендегі тасымалдардың бірін істейміз:

1. B1 - дің сұранысы A1 - дегі материал мөлшерінен көп, онда A1 - дегі материалдың бәрін B1  -ге тасимыз да, жетпегенін  A2 - ден аламыз, сосын таблицаның  A1 қоймасы тұрған жолын әрі қарай қарастырмаймыз. Әрі қарай осылай етіп A2 - мен жұмыс істейміз. Біздің мысалда бұл жағдай қолданылмайды;
2. B1 - дегі сұраныс пен A1 - дегі материал мөлшері тең. Онда A1 - дегі материалдың бәрі  B1 - ге тасылады. Сонымен бұл жағдайда A1  мен B1  бірін бірі қанағаттандырады. Енді бұл кезде әрі қарай не істеу керектігін төмендегі ескертуден қараңыз. Біздің мысалда бұл жағдай да орындалмай тұр;
3. B1 - дегі сұраныс A1 - дегі материал мөлшерінен аз. Бұл біздің мысалымыздағы жағдай.   A1 – ден 30 бірлік материалды B1  - ге тасып оның сұранысын толық қанағаттандырамыз да B1  бағанын әрі қарай қарастырмаймыз. Енді  A1 - де 100 - 30 = 70 бірлік материал қалды.  Оны B2 - ге тасып оның  сұранысын толық қанағаттандырып таблицаның B2 бағаны мен  A1  жолын жабамыз да процедураны әрі қарай жалғастыра береміз. Егер осы қадамымызда B2  толық қанағаттанбай қалса жетпегенін  A2 – ден тасыр едік, ал егер бұл қадамда керісінше A1 - де тасылмаған материал қалып қойса оны B3 - ке тасу керек болар еді.

 

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

 

Толтырылған таблица төменде келтірілген.

 

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