Сызықты болады. Айнымалылардағы шектеулер (олардың көп болуы мүмкін) сызықтық
=2 ∙70 + 3∙20 + 2∙10 + 1∙20 + 1∙10 + 2∙30 = 140 + 60 + 20 + 20 + 10 + 60 = 310 бірлік
жүктеу/скачать 1,21 Mb.
|
Сызықтық программалаудың көліктік мәселесі адамның іс
- Бұл бет үшін навигация:
- Біз х
| =2 ∙70 + 3∙20 + 2∙10 + 1∙20 + 1∙10 + 2∙30 = 140 + 60 + 20 + 20 + 10 + 60 = 310 бірлік Бұл жоспар бойынша тасымалдау құны төмендеді330 - 310 = 20 бірлік
Негізгі жоспар оңтайлы деп табылды ма? Жауапты потенциалдар үшін теңдеулер жүйесін құрастырып, шешкеннен кейін алуға болады. 2 . Негізгі жоспардың оңтайлылығын тексеру Потенциалдар үшін теңдеулер жүйесін анықтап, олардың мәндерін есептейік: α 1 + β 1 = d 11 = 2 ; α 1 + β 2 \ u003d d 12 \u003d 3 ; α 2 + β 3 = d 23 =бір; α 2 + β 4 \ u003d d 24 \u003d 2 ; α 3 + β 2 = d 32 = 1; α 3 + β 4 \ u003d d 34 \u003d 2. Бұл мәндердің әрқайсысы бір негізгі ұяшыққа сәйкес келеді. Жүйедегі белгісіздердің бірін ерікті түрде орнатуға болады. α 1 = 0 болсын. Содан кейін жүйені шешкеннен кейін потенциалдық мәндер алынады: α 1 = 0, α 2 = -2 , α 3 = -2, β 1 = 2, β 2 = 3, β 3 = 3, β4 = 4. D'[m, n] жалған шығындар матрицасын және Г[m, n] матрицасын құрамыз. Г [m, n] матрицасының бос ұяшықтарында γ i ,j > 0 (γ 14 = 1>0) болады. Жоспар оңтайлы емес. 3. Жаңа (жақсартылған) базалық деңгейге көшу x ij > 0 бос айнымалылардан біз оны негізге енгізу үшін бір x 14 таңдаймыз . Оны бұрынғыдай индекссіз х арқылы белгілеңіз . x оң x > 0 болуы керек екенін ескере отырып . Тасымалдау тепе-теңдігін сақтау шарты бойынша max x мәнін табайық. Ол үшін келесі негізгі жоспарды қолданамыз. Тасымалдау балансының шарттары сақталатындай етіп кесте ұяшықтарына x айнымалысын қосамыз өзгертілген жоспар Әлбетте, ең үлкен x негізгі ұяшықтардағы сол x ij арқылы анықталады, олардан осы х шегеріледі. Сондықтан, x 11 \ u003d min {x 12 , x 34 } \u003d {20, 30} \u003d 20 . x 12 >20 болғанда , тасымалдау x 12 теріс болады. Біз х 12 айнымалысын базистен шығарып, оны бос айнымалылар категориясына ауыстырамыз. Жаңа итерацияға көшу 1. Өзгертілген жоспардан жаңа базалық жоспар аламыз. Онда трафик көлемі алдыңғы базалық деңгейге қарағанда басқаша бөлінеді. Осы эталондық жоспар үшін тасымалдаудың жалпы құны мына түрде берілген: Q = d 11 ∙x 11 + d 14 ∙x 14 + d 23 ∙x 23 + d 32 ∙x 32 + d 24 ∙x 24 + d 34 ∙x 34 = =2 ∙70 + 3∙20 + 1∙20 + 2∙10 + 1∙30 + 2∙10 = 140 + 60 + 20 + 20 + 30 + 20 = 290 бірлік Бұл жоспар бойынша тасымалдау құны 310 - 290 = 20 бірлікке төмендеді. Негізгі жоспар оңтайлы деп табылды ма? Жауапты потенциалдар үшін теңдеулер жүйесін құрастырып, шешкеннен кейін алуға болады. жүктеу/скачать 1,21 Mb. Достарыңызбен бөлісу:
|