Байланысты: Сызықтық программалаудың көліктік мәселесі адамның іс
Q =d 11 x 11 +d 12 x 12 +d 22 x 22 +d 23 x 23 +d 33 x 33 +d 34 x 34 = = 5 x 40 + 2 x 20 + 10 x 40 + 2∙40 + 8 ∙40 + 5∙60 = 200+40+400 + 80 + 320+ 300 = 1340 бірлік
d ij коэффициенттері жалған немесе жанама шығындар деп аталады; олар α және β , d' ij = α i + β j жанама шамалар арқылы өрнектеледі . Мұндағы α i және ( - β j ) параметрлері механикаға ұқсастығы бойынша i -ші шығу нүктесінің және j -ші келу нүктесінің потенциалдары деп аталады. Потенциалды мәндер сызықтық теңдеулер жүйесінен анықталады: α i + β j = dij Бұл теңдеулердіңәрқайсысы х ij негізгі айнымалысынасәйкес келеді (m + n - 1) . Сондықтан потенциалдардың бірін, мысалы, нөлге тең етіп, ерікті түрде орнатуға болады.
Потенциалдар үшін теңдеулер жүйесін ары қарай шешіп, жолдар мен бағандардың потенциалдарының мәндерін, барлық жалған шығындар d ij және γ ij коэффициенттерін табамыз . Егер барлық бос ұяшықтар үшін γ rs ≤ 0 болса, онда кез келген бос айнымалыны базиске көшіру мақсат функциясының мәнін төмендетпейді, сондықтан таңдалған тірек жоспар оңтайлы емес. Егер кейбір γ rs >0 болса,онда бұл жоспарды max γ rs сәйкес бос айнымалыны тасымалдау арқылы жақсартуға болады., сондай-ақ базистен оған тиесілі айнымалыны алып тастау арқылы бірінші жоғалады. Жаңа негізгі жоспарға көшуді және мысалды пайдалана отырып оңтайлы жоспарды іздеуді қарастырамыз. Негізгі жоспарды қалыптастырудың тағы бір тәсілін Фогель ұсынған. Бұл әдісті бірінші оқылымда өткізіп жіберуге болады, өйткені ол мәтінде одан әрі қолданылмайды.