Сызықты болады. Айнымалылардағы шектеулер (олардың көп болуы мүмкін) сызықтық
жүктеу/скачать 1,21 Mb.
|
Сызықтық программалаудың көліктік мәселесі адамның іс
- Бұл бет үшін навигация:
- 23∙19 + 7∙3 + 20∙18 + 2∙10 + 14∙24 + 1∙100 +3∙48 = = 437 + 21 + 360 + 20 +3 36 + 100 + 246 = 1
| 2-мысал Вогельдің жуықтау әдісі
Көп жағдайда бұл әдіс оңтайлыға жақын анықтамалық жоспарды береді. Үлкен матрицалар үшін ыңғайлы. Көлік шығындары бойынша ең оңтайлы емес бағытты таңдағаны үшін алынатын айыппұл ұғымы қолданылады. Әрбір жол және әрбір баған үшін айыппұл әртүрлі шығындар көрсеткіштері бар маршруттарды талдау нәтижесінде анықталады (көлік шығындарының екі түрлі деңгейі арасындағы айырмашылық ретінде). Алдымен матрицаның ұяшығы (кесте) толтырылады, онда ең үлкен айыппұл жазылады. Ұяшықты толтырғаннан кейін айыппұлдар қайта есептеледі және т.б. барлық ресурстар таратылғанға дейін. Алгоритм қадамдары : 1. Әрбір жолдағы және әрбір бағандағы ең төменгі баға мен оған ең жақын мән арасындағы айырмашылықтарды есептеу. Жол айырмашылықтары айырмашылық бағанында оңға жазылады, баған айырмашылықтары айырмашылық жолында жазылады. Мысалы, A 1 жолдары үшін айырмашылық A 1 B 2 - A 1 B 3 \u003d 38 - 24 \u003d 14 және т.б. 2-КЕСТЕ – Көлік тапсырмасының негізгі жоспарын алудың Фогель әдісі 2. Жолдардағы да, бағандардағы да барлық айырмашылықтардан іздеу максималды. Біздің мысалда максималды айырмашылық 38 және A 2 жолында . Максималды айырмашылықтың айналасында қорап сызайық. 3. Ресурстардың максималды мүмкін сомасының ең төмен құны ( A 2 B 2 = 18 ) (ең үлкен айырмашылық бар жол) ұяшыққа орналастыру . Ол 20-ға тең, яғни. жіберушінің бүкіл ресурсы A 2 . A 2 жіберушінің барлық ресурстары таусылғандықтан, біз A 2 жолын келесі есептеулерден алып тастаймыз, ол үшін осы жолдың барлық ұяшықтарын нүктелермен белгілейміз. 4. Бағандар мен жолдардағы айырмашылықтарды есептеу, ресурстары бар ұяшықтардағы және нүктесі бар ұяшықтардағы (жол немесе баған алынып тасталды) және жолдағы немесе бағандағы ең үлкен айырмашылықты анықтау ( B 3 = 76 ). 5. Максималды айырмашылығы бар қатардағы немесе бағандағы ең аз элементті табу ( A 1 B 3 = 24 ) және осы ұяшыққа ресурстың максималды мүмкін мөлшерін орналастыру, No 4 кезеңге оралу және т.б. Ақырында CF Q= 23∙19 + 7∙3 + 20∙18 + 2∙10 + 14∙24 + 1∙100 +3∙48 = = 437 + 21 + 360 + 20 +3 36 + 100 + 246 = 1 Бұл мән Vogel анықтамалық жоспарына сәйкес келеді. жүктеу/скачать 1,21 Mb. Достарыңызбен бөлісу:
|