Мавзу: транспорт масаласининг қЎ

_ij) – матрицанинг m+n-1та компоненталари мусбат бўлиб, қолганлари нолга тенг бўлади. Агар транспорт масаласининг шартлари ва унинг таянч ечими юқоридаги жадвал кўринишда берилган бўлса, нолдан фарқли x_ij – лар жойлашган катаклар «банд катаклар», қолганлари «бўш катаклар» дейилади.
Агар банд катакларни вертикал ёки горизонтал кесмалар билан туташтирилганда ёпиқ кўпбурчак ҳосил бўлса, бундай ҳол циклланиш дейилади ва ечим таянч ечим бўлмайди. Демак, бирорта ечим таянч ечим бўлиши учун банд катаклар сони m+n-1 та бўлиб циклланиш рўй бермаслиги керак.
Шимолий-ғарб усули.
Транспорт масаласи жадвал кўринишида берилган бўлсин. Йўл харажатларини ҳисобга олмай B₁ истеъмолчининг талабини A₁ таъминотчи ҳисобига қондиришга киришамиз. Бунинг учун a₁ ва b₁ юк бирликларидан кичигини A₁B₁ катакнинг чап пастки бурчагига ёзамиз. Агар a₁< b₁ бўлса, B₁ нинг эҳтиёжини тўла қондириш учун A₂B₁ катакка етишмайдиган юк бирлигини A₂ дан олиб ёзамиз ва ҳ. к. Бу жараённи A_mB_n катакка етгунча давом этдирамиз. Агар (5) шарт ўринли бўлса, бу усулда тузилган ечим албатта таянч ечим бўлади.
1-мисол. Транспорт масаласининг бошланғич ечимини топинг.

Таъминотчилар	Истеъмолчилар						Заҳира ҳажми
	B1	B2	B3	B4	B5
A1	10 100	7	4	1	4	100
A2	2 100	7 150	10	6	11	250
A3	8	5 50	3 100	2 50	2	200
A4	11	8	12	16 50	13 250	300
Талаб ҳажми	200	200	100	100	250

Минимал қиймат усули.
Бу усулда бошланғич ечим қуриш учун аввал йўл харажати энг кичик бўлган катакка a_i ва b_j лардан кичиги ёзилади ва кейинги энг кичик қийматли катакка ўтилади ва ҳ. к. Бу усулда тузилган бошланғич ечимни бузилмаслик ва циклланишга текшириш шарт.
2-Мисол. Минимал қиймат усули билан бошланғич ечимини топинг.

Таъминотчилар	Истеъмолчилар						Заҳира ҳажми
	B1	B2	B3	B4	B5
A1	10	7	4	1 100	4	100
A2	2 200	7 50	10	6	11	250
A3	8	5	3	2	2 200	200
A4	11	8 150	12 100	16	13 50	300
Талаб ҳажми	200	200	100	100	250