Кириш. Чизиқли программалаштириш (1-маъруза машғулоти)

«шимоли-ғарбий бурчак» усули

• «Шимоли-ғарбий бурчак» усулининг ғояси қуйидагилардан иборат. Энг аввал шимоли-ғарбда жойлашган. номаълумнинг қийматини аниқлаймиз. Агар а1b1 бўлса, =а11 ва =0 , (j=2,m) агар b1а1 бўлса, =b11 ва =0 (i=2,n) бўлади. Фараз қилайлик, 1-ҳол бажарилсин. Бу ҳолда 1-қадамдан сўнг масаланинг ечимларидан ташкил топган матрица қуйидаги кўринишда бўлади

1-қадам.

• Энди иккинчи қатордаги биринчи элементнинг қийматини топамиз:
• Агар a2>b1-a1 бўлса, x21= b1-a1 ва xi1=0, (i=3,m),
• Агар a2a1 бўлса, x21= a2 ва x2j=0, (i=2,n),
• Фараз қилайлик, янги матрица учун ҳам биринчи ҳол бажарилсин, у ҳолда

X11=a1	0	0	…	0	0
x21	x22	x23	…	x2n	a2
…	…	…	…	…	…
Xm1	xm2	xm3	…	xmn	am
b1 –a1	b2	b3	…	bn

2-қадам.

X11 =a1	0	0	…	0	0
X21 =b1 –a1	x22	x23	…	x2n	a2-b1+a1
…	…	…	…	…	…
0	xm2	xm3	…	xmn	am
0	b2	b3	…	bn

• Худди шундай ҳар бир қадамда бирорта xij нинг қиймати топилади. xij =min(aibj) ва ai ёки bj нолга айлантирилади.
• Бу жараён барча ai ва bj лар нолга айлангунча такрорланади. Маълумки, ҳар бир xij нинг қиймати ai ва bj ларнинг турли комбинацияларини айириш ёки қўшиш ёрдами билан топилади, шунинг учун ai ва bj лар бутун бўлганда топилган таянч билан бутун сонли бўлади. Бундан ташқари таянч режадаги нолдан фарқли xij номаълумлар сони m+n-1 дан ошмайди.

Минимал элемент усули

• Минимал ҳаражатлар усули. Транспорт масаласининг ечимини топиш учун керак бўладиган итерациялар сони бошланғич таянч режасини танлашга боғлиқ. Оптимал режага яқин бўлган таянч режани топиш масаланинг оптимал ечимини топишни тезлаштиради. Адабиётда транспорт масаласининг бошланғич режасини топиш учун транспорт ҳаражатларини назарга олувчи кўп усуллар маълум. Уларнинг ҳаммаси шимолий-ғарб бурчак усулининг транспорт ҳаражатларини назарга олувчи модифицирланган ҳолидир.

Асосий теоремалар

• 1-теорема. Ҳар қандай кўринишдаги ёпиқ моделли транспорт масаласи ечимга эга.
• 2-теоремa. Транспорт масаласининг шартларидан тузилган матрицанинг ранги га тенг.
• 3-теорема. Ихтиёрий транспорт масаласининг оптимал ечим мавжуддир.
• 4-теорема. Транспорт масаласининг ҳар қандай ечимидаги xij (xij >0) ларнинг сони m+n-1 дан ортмайди. Бундай xij Pij ларга мос векторлар чизиқли боғлиқсиз бўлади.
•  

Потенциал усул ғояси

• Транспорт масаласининг бошланғич таянч ечимидан бошлаб, оптимал ечимга яқинроқ бўлган янги таянч ечимларга ўтиб бориб, чекли сондаги интеракциядан сўнг масаланинг оптимал ечимини топиш масаласини ҳал қилишда потенциаллар усулидан фойдаланиш мумкин. Ҳар бир интеракцияда топилган таянч ечим оптимал ечим эканини текшириш учун ҳар бир маҳсулот ишлаб чиқарувчи (таъминотчи) ва истеъмол қилувчи (истеъмолчи) пунктда унинг потенциали деб аталувчи ва сонлар мос қўйилади. Бу потенциаллар шундай танланадики, бунда ўзаро боғланган таъминотчи ва истеъмолчиларга мос келувчи потенциаллар йиғиндиси sij га тенг бўлиши керак.

Чизиқсиз программалаштириш масаласининг классификацияси ва умумий кўринишдаги математик модели.

• Дейлик, n ўлчовли Эвклид фазоси En да f(Х),g1(Х),...,gm(Х) функциялар берилган бўлсин. Қуйидаги
• g1(Х)≥0
• g2(Х) ≥ 0
• ...........
• gm(Х) ≥ 0
• шартларниг барчасини қаноатлантирувчи Х=( х1,х2,...,хn) векторларни жоиз векторлар, ёки қисқача қилиб жоиз нуқталар деб атаймиз.Агар f(Х),g1(Х),...,gm(Х) функциялардан камида биттаси чизиқсиз бўлса берилган масала чизиқсиз программалаштириш масаласи дейилади.
• Барча жоиз нуқталар орасидан f(Х) функцияга экстремал қиймат берувчи нуқтани топиш масаласини шартли экстремум масаласи деб атаймиз.Масала символик кўринишда қуйидагича ёзилади:
• f(Х)￫min(max) (1)
• gi(Х) ≥ 0, (2)
• Бу ерда gi(x)Ј0, , муносабатлар қўйилган шартларни ифодалайди. Шу сабабли, мос масалага шартли экстремум масаласи деб аталади. Агар масалада i=0 бўлса, яъни (2) каби еки бошқача шартлар қўйилмаса, мос масалага шартсиз экстремум масаласи дейилади ва бундай масалалар математик анализ курсида етарли даражада ўрганилган. Биз бу ерда асосий эътиборни шартли экстремум масаласига қаратимиз.