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

 

 

Таблица жасап болғасын төмендегі MS Excel ұяларына келтірілген формулаларды жазамыз.

 

B4:  =СУММ(C4:F4) B5:  =СУММ(C5:F5) B6:  =СУММ(C6:F6) B7:  =СУММ(C7:F7) B8: =СУММ(C8:F8)

C9:  =СУММ(C4:C8) D9:  =СУММ(D4:D8) E9:  =СУММ(E4:E8) F9:  =СУММ(F4:F8)

C16:  =СУММПРОИЗВ(C4:C8;C11:C15) D16:  =СУММПРОИЗВ(D4:D8;D11:D15) E16:  =СУММПРОИЗВ(E4:E8;E11:E15) F16:  =СУММПРОИЗВ(F4:F8;F11:F15) B16:  =СУММ(C16:F16) D17:  =B16/1000000

 

 

Есеп шешу схемасы төменде келтірілген:

 

• «Сервис-Поиск решения»;
• «Целевая ячейка» деген пункітке  В16 – ты қондырамыз;
• «Равной» деген пункітте  «Минимальному значению» деген опцияны таңдаймыз;
• «Изменяя ячейку:» С4:F8
• «Ограничения – Добавить» (осы диалогтің ішінде), «Добавление ограничения» деген диалог шығады;
• Келесі шектеулерді (ограничения) енгізу керек. Бірінші, екінші шектеулердің әрқайсысын енгізіп болғаннан кейін «Добавить» кнопкасын басасыз да келесі шектеуді енгізесіз. Ең соңғы шектеуді енгізгеннен кейін ОК кнопкасын басасыз;
• Алдыңғы диалог қайтадан шығады. Шектеулер терезесінен қосқан шектеулерді көріп оның дұрыстығын тексересіз;
• «Выполнить» кнопкасын басасыз;
• Жаңадан «Результаты поиска решения» деген диалог шығады. Әрә қарай осы диалогта көрсетілген нұсқаулармен жұмыс істейсіз. Егер ақпар керегі жоқ болса «Тип отчета» деген опцияны белгілемейсіз.

 

 

MS Excel программасының көмегі арқылы тасымал есебін шығарған кезде берілген есеп ашық есеп болса, оны жабық түрге келтіріп жатудың қажеті жоқ. Сол сияқты тасымал есебінде біз қарастырмаған шектеулер пайдалануға болады. Мысалы кей қоймадағы материалдардың бәрін немес бір белгілі бөлігін алып кету керек; кей тұтынушының сұранысын бірінші кезекте орындау керек; кей тұтынушы алатын материалдар көлемі белгілі мөлшерден аз болмауы керек т.с.с. «Поиск решения» деген опция өте икемді опция, тасымал есебін алдын ала түрлендірмей ақ шектеулердің көп түрін ескеріп шығара беруге болады. Сондай есеп түрлерін келтіре кетелік.

 

 

Тасымал есебіне  қосымша шарттар қою

 

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

 

Сұранысты орындауға кедергі (блокировка поставок). Бұл кезде кей қоймамен кей тұтынушының арасында тасымал жасау мүмкін болмай қалады. Мысалы көпір құлап қалуы, су тасқыны жолды шайып кетуі, жол жөндеу жұмыстары жүргізілуі т.с.с. әртүрлі себептер болуы мүмкін. Бұл кезде тарифтік матрицадағы сәйкес байланыстардағы тасымал шығынын өте үлкен санмен, айталық   санымен алмастырады. Сонда бұл жолмен тасу жұмысы өте қымбат болып, тиімді шешімге кірмей қалады. MS Excel программасын қолданып осындай есеп шығарғанда   санын тарифтік таблицадағы ең үлкен тасу шығынынан 1000-10000 есе үлкен қылып алса болады, сонда бұндай есепті MS Excel программасын қолданып шығару ешқандай қиындық туғызбайды.

Төмендегі мысалда   аралығында кедергі бар болып, оны ескеру үшін тарифтік бағаны өте үлкен санмен алмастыру мысалы көрсетілген.

 

		Тұтынушылар			Ұсыныс				Тұтынушылар			Ұсыныс
		B1	B2	B3					B1	B2	B3
Қоймалар	A1	6	5	4	55		Қоймалар	A1	6	5	4	55
	A2	1	2	4	45			A2	6000	2	4	45
	A3	3	2	3	50			A3	3	2	3	50
Сұраныс		35	25	90			Сұраныс		35	25	90

 

 

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

Бұндай жағдайда сол өткізу мүмкіндігі аз ұя тұрған бағанды екі бағанға бөледі. Бірінші бағанға сол бағанның тұтынушысының барлық сұранысы мен өткізу мүмкіндігінің айырмасын сұраныс тұрған жерге жазады. Ал екінші бағанға өткізу мүмкіндігінің шегін сұраныс ретінде жазады. Өткізу мүмкіндігі шектелген ұя екіге бөлінгенде шыққан бірінші ұядағы тарифтің орнына өте үлкен сан қойылады да (біз 6000 санын қойып отырмыз), екінші ұяға бұрынғы тарифті қалдырады. Сонда бірінші ұямен тасымал жасау тиімсіз болады. Бәрі түсінікті болуы үшін алдыңғы мысалда   - ден    - ге тасымалға шектеу қоялық, ол жерде тек 13 материал бірлігін өткізуге болатын болсын, ал   - дің сұранысы  25 бірлік. Яғни осы қя арқылы 13 бірліктен арқылы материал тасылмауы керек (кем тасуға, тіпті тасымауға болады), қалған материалдарды басқа қоймалардан алуына болады.  Тарифтік таблицалар төменде көрсетілген.

 

		Тұтынушылар			Ұсыныс				Тұтынушылар				Ұсыныс
		B1	B2	B3					B1	B2		B3
Қоймалар	A1	6	5	4	55					B2-1	B2-2
	A2	1	2	4	45		Қоймалар	A1	6	5	5	4	55
	A3	3	2	3	50			A2	1	6000	2	4	45
Сұраныс		35	25	90				A3	3	2	2	3	50
							Сұраныс		35	12	13	90

 

 

Аралық қоймалар арқылы тасымалдау (промежуточное складирование). Бұл кезде әуелі материалдарды аралық  C1,C2,…,Ck  қоймаларына тасып, сосын сол аралық қоймалардан тұтынушыларға жіберу керек. Бұндай есеп шығарғанда кеңейтілген тарифтік таблица жасайды. Шығару жолы түсінікті болуы үшін мынадай мысалды қарастыралық.

 

Мысал. Әртүрлі үш құрылыс алаңына ұсатылған тас (щебенка) апару керек, олардың мөлшері сәйкес 50, 60, 40 тонна болсын (барлық фракцияларын қосып есептегенде). Тас өндіретін төрт карьерде 100, 30, 40, 50 тонна тас өндіруге ұрықсат берілген (лимит берілген). Тас әуелі тасты уатып щебенка жасайтын екі зауытқа апарып уатылады, олар 100, 150 тонна тас уатып әртүрлі фракцияда щебенка шығаруға мүмкіндіктері бар. Есеп шығарғанда екі щебенка шығаратын зауыттың өнімдерінің өзіндік құны бірдей деп есептеңіздер, сонда олардың шығындары есептелмейді. Әуелі есеп шартының екі бөлігіне бөлек тариф таблица құралық:

 

 

		Зауыттар		Ұсыныс				Құрылыс алаңы			Ұсыныс
		C1	C2					B2	B3	B4
Карьерлер	A1	1	2	100		Зауыттар	C1	1	2	3	100
	A2	4	3	30			C2	4	3	2	150
	A3	6	8	40		Сұраныс		50	60	40
	A4	2	1	50
Сұраныс		100	150

 

 

Енді  кеңейтілген таблица құралық:

 

		Зауыттар		Құрылыс алаңы			Ұсыныс
		C1	C2	B2	B3	B4
Карьерлер	A1	1	2	М	М	М	100
	A2	4	3	М	М	М	30
	A3	6	8	М	М	М	40
	A4	2	1	М	М	М	50
Зауыттар	C1	0	М	1	2	3	100
	C2	М	0	4	3	2	150
Сұраныс		100	150	50	60	40

 

Мұндағы   мейлінше ұлкен сан, MS Excel арқылы шығарғанда ең үлкен тарифтен 1000-10000 есе қылып алса жеткілікті. Үлкен сандар алып отырған себебі зауыттан зауытқа, құрылыс алаңынан құрылыс алаңына материал тасудың мағынасы жоқ, ол тасуларға кедергі жасау керек.

 

 

 

Тағайындау туралы есеп

 

Тағайындау  туралы есеп (задача о назначениях) тасымалдау есебінің дербес жағдайы  деп есептеуге болады, дегенмен оның ерекшеліктері де бар.

Тағайындау туралы есеп. Айталық n жұмыс түрі және n  орындаушы бар болсын. Әр орындаушы әр жұмысты әртүрлі қабылетпен орындауы мүмкін. Олардың жұмыс түрлерін орындау қабылеттері c_ij (i=1,2,…,n; j=1,2,…,n)  арқылы бағалансын (i  - інші орындаушының  j - інші жұмысты орындау қабылеті). Барлық жұмыс тиімді түрде орындалуы үшін орындаушыларды жұмыстарға тағайындау әдісін табу керек.

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

 

xij =		1, егер i – інші орындаушыны j - інші жұмысқа жіберсе,
		0   егер басқаша болғанда

 

 

Онда тағайындау есебінің математикалық  моделін былай жазуға болады:

 

   (әр жұмысқа орындаушы  тағайындалуы керек)

 

   (әр орындаушы жұмысқа  тағайындалуы керек)

 

Тағайындау  туралы есеп тасымалдау есебінің дербес түрі, ал тасымалдау есебі сызықтық жоспарлау есебінің дербес түрі, сондықтан  бұл есепті айтылған есептерді шығару жолымен шығаруға болады.  Дегенмен тағайындау есебінің матрицаларының ерекшеліктері  бұл есепті басқа жолмен де шығаруға мүмкіндік береді, олардың бірі венгер әдісі (венгерский метод) деп аталады.

Мынандай  теорема бар.

 

Теорема. Егер тасымал есебіндегі сұраныс пен ұсыныстар бүтін сандар болса, онда олардың тиімді мәндері де бүтін сандар болады.

 

Ал  тағайындау есебіндегі сұраныс пен  ұсыныстың ролін атқарып тұрған сандар бүтін сандар болғандықтан есеп шешімі де бүтін сан болады. Сондықтан  есепті MS Excel арқылы шығарғанда нәтиежесі бөлшек сан болады деп қорықпай шығара беруге болады (бульдік айнымалылар қолданған дұрыс). Тағы да айта кететін жайт, егер әртүрлі себептермен кей тағайындау мүмкін болмаса, онда оның тарифін өте үлкен сан қылып өзгертіп есепті шығара беруге болады. 

 

Мысал. Бір кәсіпкердің қалада тамақ өнімдерін сататын алты нүктесі (киоск, дүкен т.с.с.) бар болсын. Келесі жұмыс күніне оның жұмысқа шығатын бес сатушысы бар болсын (бір сатушы санитарлық кітапшасын толтырып үлгере алмағандықтан жұмысқа жіберілмей отыр). Кәсіпкер өткен мерзімдердегі әрбір сатушыдан күнделікті түскен табысқа (выручка)  талдау жасап олардың әр сату нүктесіндегі жұмысына балама береді (яғни C матрицасын анықтайды). Оның жасаған матрицасын келтірейік: