Ўзбекистон Республикаси
Олий ва Ўрта махсус таълим вазирлиги

Гулистон давлат университети

Ҳ.Норжигитов

“ОПТИМАЛЛАШТИРИШ УСУЛЛАРИ”
ўқув қўлланма

Гулистон-2016

МУНДАРИЖА

I.	– Вариацион Ҳисоблаш
   1. Вариацион ҳисобнинг энг содда масаласи
   2. Эйлер –Лагранж тенгламаси.
   3. Беллман тенгламаси.
II.	–Оптимал бошқарув 
1.	Максимум принципи.
2.	Асосий масала
3.	Оптимал (энг кичик) вақт масаласи
III. Дифференциал ўйинлар 
1. Дифференциал ўйинлар назарияси учун керакли баъзи   
   маълумотлар.
2. Л.С.Понтрягин. I-усул
3. Л.С.Понтрягин. II-усул
IV. Чизиқли программалар.
1.	Чизиқли программалашнинг асосий масаласи.
2.	Чизиқли программалаш масаласини график усулда
    ечиш.
3.	Чизиқли программалаш масаласининг хоссалари.
4.	Симплекс усул.
5.	Сунъий базислар усули.
6.	Иккиламчи масала назарияси.
V. +авариқ прораммалаштириш. 
1. +авариқ программалаштиришнинг асосий масаласи, қавариқ тўплам ва функциялар.
2. +авариқ тўплам хоссалари.
3. +авариқ функциянинг хоссалари.
4. Силлиқ масалалар.
VI. Чизиқсиз программалаштириш.
1.	Чизиқсиз программалаштиришнинг асосий масаласи ва ечимнинг мавжудлиги. 
2.	Шартли минимум масаласи.
3.	Шартли тенгсизликлар типидп бўлган ҳолда функцияларни минимумлаштириш.
4.	Минимумнинг 2-тартибли етарли шарти.
5.	Силлиқ бўлмаган масалалар.
VII. Транспорт  масаласи.
1.	Транспорт масаласининг қўйилиши.
2.	Шимолий-\арб бурчак усули.
3.	Минимал баҳоли усул.
4.	Потенциаллар усули
5.	Транспорт масаласи учун мисоллар.

К И Р И Ш

Оптималлаштириш масалалари инсон фаолиятининг хилма-хил соҳаларида учрайди. Ҳар бир оқилона ҳаракат маълум бир маънода оптимал бўлади, чунки у, одатда, бошқа ҳаракат вариантлари билан таққослангандан сўнг танланади. Энг яхши усулда (яъни оптимал )танлаш масалаларига қизиқиш ҳамиша катта бўлиб келган, у кейинги 500 йил давомида  фан ва техниканинг жадал ривожланиши натижасида янада кучайди. Бир томондан, одамларга кўп холда, мавжуд воситалар ва ресурслардан юқори самара билан фойдаланиш талаб қилинадиган жараёнлар билан шу\улланишга тў\ри келса, иккинчи томондан, хисоблаш техникасининг ривожланиши натижасида инсоннинг ўрганиладиган жараёнларга таъсир қилиш имконияти ортиб боради.  
Ҳозирги замон амалий оптималлаштириш масалаларининг мураккаблиги билан бо\лиқ ўлароқ, қарор қабул қилишда борган сари “идрокка”, интуиция ва инсон асосланиш қийинлашиб бораяпти. Текширалаётган масалаларни математик моделлаштиришга асосланган илмий ёндашув зарур бўлиб бормоқда. 
Ҳозирги замон илмий-техника инқилоби натижасида оптималлаштириш назарияси ва унинг амалиётдаги  жадал қўлланиши ривожлана бошланди.  
қисқа вақт ичида назариянинг шундай янги бўлимлари (чизиқли программалаштириш, оптимал бошқарув назарияси ва бошқалар)пайдо бўлдики, улар амалда учрайдиган кўплаб оптималлаштириш масалаларини ечишнинг қатор тақрибий усулларини  яратишга олиб келди.
Мазкур қўлланмани ёзишда, айниқса 5-бобнинг баёнида Р.Габасов, Ф.Кириллованинг “Оптималлаштириш усуллари” китобидан кенг фойдаланилган.

I боб

	3. Эйлер –Лагранж тенгламаси. Фараз қилайлик, - оптимал чизиқ бўлсин,   эса , (-1,1) интервалда ўзгарувчи параметр бўлсин, эса  шартларни қаноатлантирувчи узлуксиз ва узлуксиз ҳосилага эга бўлган функция бўлсин. +уйидаги 

 (2)

функцияни кўрайлик. Равшанки, ихтиёрий  учун  чизиқ силлиқ бўлиб, у A ва B нуқталарни туташтиради. Бундан ташқари 

                                                            (3)

тенгсизлик ўринли. (3) тенгсизликнинг чап тамони нинг функциясидир; уни  билан белгилаймиз. Иккинчи тамондан, аёнки . Шундай қилиб,  тенгсизлик ихтиёрий  учун ўринли экан. Демак, 0 нуқтаси  функция учун минимум нуқта экан. 
(1)-формуладан кўриниб турибдики,  функциянинг силлиқ функциядир. Шунинг учун Ферма теоремасига асосан  тенгликка эга бўламиз, лекин  
                          (4)
бўлгани учун 
                                     (5) 
тенгликни осонликча ҳосил қиламиз  (Юқорида   . Аммо   бўлгани учун (5)-дан ихтиёрий  учун қуйидаги

                                             (6)  

тенгликка эга бўламиз. Энди                
                         (7)
формула ва  тенгликлардан фойдаланиб,  (6)-тенгликни қуйидагича ёзишимиз мумкин:

                                                            (8)

(7) ифодага бўлаклаб интеграллаш қоидаси қўлланилди).
Таъкидлаб ўтиш керакки, (8)-тенглик ихтиёрий учун ўринли. Хозир шу фактдан фойдаланиб,  қаноатлантирувчи тенгламани ҳосил қиламиз. 

Ёзувни қисқароқ қилиш учун биз вариацион ҳисобнинг асосий леммаси ёки  Лагранж леммаси деб аталувчи қуйидаги тасдиқдан фойдаланамиз  (унинг исботини 4п. да келтирамиз). 
Лагранж леммаси. Агар  узлуксиз функция бўлиб,   шартларни қаноатлантирувчи ихтиёрий узлуксиз функция учун 

                                                        (9)

тенглик бажарилса, у ҳолда  бўлади.
Шу леммага асосан (8)-дан 

                   (10)

айниятга эга бўламиз. Демак, оптимал чизиқ  қуйидаги Эйлер –Лагранж  тенгламаси деб аталувчи 
                                          (11)

тенгламани қаноатлантирар экан. Бу тенгламадан бизга керакли чизиқни топиш учун 
                                                   (12)

чегаравий шартлар ҳам ҳисобга олиниши керак. 
            Шундай қилиб, оптимал чизиқни (11) тенгламанинг (12) шартларни қаноатлантирувчи ечимлари ичидан қидиришимиз керак бўлади. 

Мисол.           (13) 

              

Бундан  қуйидагига эга бўламиз, 

Демак,   (с1 –константа ). Бундан  ва чегаравий шартлардан  ларга эга бўламиз. Шундай қилиб, агар оптимал чизиқ мавжуд бўлса, у қуйдаги 
                                                            (14)
кўринишда бўлар экан. 
 (11)-тенгламанинг (12)-шартларни қаноатлантирувчи ечимлари экстремаллар деб аталади.
	4. Лагранж леммасининг исботи.   Фараз қилайлик,  бўлсин (тескарисидан фараз қилиш усули). +ўшимча равишда,  деймиз, ( холи –машқ )  нинг узлуксизлиги  сабабли шундай   топиладики,  функцияси  да мусбат бўлади. ( холлари ҳам машқ сифатида кўрилиши мумкин).  ни шундай кўрамизки, у  ва    да  0 га тенг,   да мусбат бўлиб, ўзи эса силлиқ қилиб танланиши мумкин. Шу   функцияси учун  
                                           (15)
Иккинчи томондан, , бу эса (15)- муносабатга  зиддир. Лемма исбот бўлди. 
	5. Беллман тенгламаси. Динамик программалаштириш назариясига асосланиб, биз  ларни ўзгармас деб,  ларни эса ўзгарувчи деб қараймиз. Ундан ташқари,  х  нинг ўрнига  t, y нинг ўрнига    нинг ўрнига  нинг ўрнига янги ўзгарувчиларни киритамиз. +ўшимча равишда биз  соҳани кўрамиз ва қуйидаги иккита шартни бажарилган, деб ҳисоблаймиз. 

1-шарт. Шундай    соҳа мавжудки,  ихтиёрий  учун 

                          (16)

интегралга энг кичик қиймат берувчи оптимал чизиқ  мавжуд. 
 ни  билан белгилаймиз.  функция G соҳада аниқланган .
2-шарт.  функцияси узлуксиз ва  соҳада узлуксиз хусусий ҳосилалар  ва  га эга бўлсин.   
I. Теорема.   Агар юқоридаги иккита шарт бажарилса,  функция қуйидаги 
                        (17)

тенгламани   соҳада қаноатлантиради.
Изоҳ.  функцияси  Беллман функцияси, (17)-тенглама   Беллман тенгламаси   дейилади ([6] ни қаранг).
6.Биз  Беллман тенгламасини зарурий шарт сифатида ҳосил қилган бўлсакда, ундан маълум бир шартлар ёрдамида етарли шарт сифатида ҳам фойдаланиши мумкин.  Ҳозир шу масалага тўхталамиз.
	+уйида 1,2-шартларни бажарамиз, деб фараз қиламиз.
1-шарт. Шундай  , соҳада аниқланган, узлуксиз ва да узлуксиз хусусий ҳосилаларга эга бўлган функция мавжуд бўлиб, у  да (17) ни қаноатлантирсин.
2-шарт.   шундай нуқта бўлсинки, унинг учун силлиқ  , функция мавжуд бўлиб, у   шартларни қаноатлантирсин. 

II.Теорема. Агар юқорида келтирилган иккита шарт бажарилиб, - ихтиёрий силлиқ чизиқ бўлиб,  бўлса, 

тенгсизлик бажарилади,  яъни   чизи\и  G да жойлашган ва  ларни туташтирувчи барча силлиқ чизиқларга нисбатан  га энг кичик қиймат беради.  
	Исботи. , функцияни қарайлик. Бу функция узлуксиздир(исботи-ўқувчига). Яна,  эса силлиқ функциядир(исбот қилинг). У ҳолда 
                                 (18)

(17)-га асосан    Шунинг учун ((18))

                                 (19)

Ихтиёрий  учун  (19) ни    оралиқ бўйича интеграллаб, 
                   (20)

га эга бўламиз. (20)-дан  да 

                               (21)

муносабат келиб чиқади. Агар биз  эканлигини ҳисобга олсак, (21)-дан   тенгсизликни хосил қиламиз. Теорема исбот бўлди. 

Мисол.   бўлсин.

Кўрилаётган холда,    +уйидаги 

                                                          (22)

функцияни қарайлик. Бу функция G да узлуксиз,  да хусусий ҳосилаларга эга:                            
                                               (23) 

+уйидаги   функцияни киритайлик. У ҳолда (17)- тенглама 
                                                             (24)

шаклида ёзилади. Биз кўраётган ҳолда 

Агар  десак,  бўлади ва   бўлганлиги учун бевосита ҳисоблаб,  эканлигига ишонч ҳосил қилишимиз мумкин. Демак, (22)- функция (17)-тенгламани қаноатлдантиради (х<0 соҳада). Ихтиёрий   олиб,  деб,    чизиқни кўрсак,   бўлади. Демак, биринчи теоремага асосан  ихтиёрий   учун оптимал чизиқ экан. 
II боб

Оптимал бошқарув назариясининг 
асослари

1.	Саноат, техника ва фаннинг  ўсиши асримизнинг  50-йилларида математиканинг янги йўналиши-оптимал бошқарув назариясининг яратилишига олиб келди.
Назариянинг асосий натижалари Америкалик олим          Р. Беллман ва Россиялик олим Л.С. Понтрягинларнинг номлари билан бо\лиқ. Р. Беллман динамик программалаштириш усулига, Л.С. Понтрягин максимум принципи усулига асос солдилар.
Бу усуллар қўлланилиши мумкин бўлган масалаларга умуман айтганда, вариацион ҳисобнинг усулларини тадбиқ этиб бўлмас эди. Шундай мисоллардан бирини кейинги пунктларда ўрганамиз.
Иккинчи томондан, айтиш керакки, вариацион ҳисоб оптимал бошқарув назариясининг хусусий бир ҳоли бўлиб хизмат қилади.
2. Максимум принципи. Табиатда кечаётган жараёнлар икки гуруҳга бўлинади: бошқариладиган ва бошқарилмайдиган жараёнлар.
Биринчи гуруҳга автомобилнинг, самолётнинг учиши, ракетанинг ҳаракати мисол бўла олади. Иккинчи гуруҳга мисол қилиб юлдузларнинг ҳаракатини келтириш мумкин.
Биз фақат бошқариладиган жараёнларнигина ўрганамиз. Фараз қилайлик, бирор бир объект ( жараён ) нинг ҳолати  ўзгарувчилар  билан ифодалансин. Юқорида айтганимиздек, объект бошқарилувчи бўлиб, у    бошқарилувчи параметрлар ( ўзгарувчилар ) ёрдамида бошқарилсин. Объектнинг ҳаракати

                                        (1)

дифференциал тенгламалар билан ифодалансин. (1)-системага кирувчи   ўрнига вектор ўзгарувчи    ўрнига вектор  ўрнига вектор ларни киритайлик. У  ҳолда  (1)-система ўрнига битта вектор тенглама

                                                                    (2)

ҳосил бўлади. Бошқаручи вектор u ўзининг қийматларини бирор  тўпламдан қабул қилсин. Яна,  скаляр функция ҳам берилган деб ҳисоблаймиз. Берилган  ва  функцияларни силлиқ  деб фараз  қилинади.
Бошқарилувчи функция деб, бирор бир сегментда аниқланган, қийматлари U га тегишли қисм узлуксиз функцияга айтилади ( узлуксиз нуқталари сони чекли ). Бизга  бошқарилувчи функция берилган бўлсин. Уни (2)-нинг ўнг томонига  олиб бориб қўямиз:   Натижада қуйидаги

                                                                  (3)

дифференциал тенглама ҳосил бўлади. (3)-тенгламанинг ихтиёрий  ечимини кўрайлик. Бу ечимни  сегментда аниқланган деб ҳисоблаймиз. +уйидаги

                                                  (4)

интегрални ( функционал )   бошқарувчи функциянинг баҳоси дейилади ( ёки бошқарув усулининг баҳоси ҳам дейилади ).

Бошқарув назариясининг асосий масаласи қуйидагидан иборат.
Бизга ва    нуқталар берилган бўлсин. Агар  бошқарув усулига мос келган  ечим  шартларни қаноатлантирса, у ҳолда  функцияси жоиз функция,  эса жоиз траектория,  жоиз жуфтлик дейилади.
Асосий масала. Жоиз бошқарувчи функцияларнинг ичидан шундай функция топилсинки, натижада у ва унга мос қўйилган жоиз траекториядан тузилган жуфтлик учун (4)-функционал энг кичик қийматни қабул қилсин.
Агар шундай жуфтлик  мавжуд бўлса, у оптимал жуфтлик, унинг биринчи тузувчиси ( компонентаси ) оптимал бошқарув, иккинчи тузувчиси оптимал траектория дейилади.
Кўриниб турибдики, асосий масала икки масалага бўлинади. Биринчи масалада жоиз жуфтликларнинг мавжудлиги ўрганилса, иккинчи масалада  уларнинг ичидан энг «яхшиси» нинг борлиги тадқиқ этилади. Биринчи масала бошқарувчанлик масаласи, иккинчиси эса оптималлик масаласи дейилади
Энди қачон керакли жуфтлик мавжуд, қачон уларнинг ичида энг «яхшиси» бор, деган саволларга жавоб қидирмасдан, оптимал жуфтликни мавжуд деб, унинг қандай шартларни қаноатлантириши билан шу\уланамиз.
Фараз қилайлик, - оптимал жуфтлик бўлсин. Ундан фойдаланиб, қуйидаги

                                              (5)

қўшимча тенглама деб аталувчи чизиқли дифференциал тенгламани тузайлик. (5)- тенгламада  .
Л.С.Понтрягининг максимум принципи. Фараз қилайлик,  оптимал жуфтлик бўлсин. У ҳолда шундай тривиал бўлмаган   (5)-тенгламанинг ечими мавжудки, унинг учун

                     (6)

ва     бўлади.
3. Оптимал (энг қисқа) вақт масаласи. (4)-функционалда   деб, фараз қилайлик. Бу ҳолда  яъни, функционал х нуқтанинг  траектория бўйича  дан  гача бориш учун кетган ( сарф қилган ) вақтни билдиради. Демак,  оптимал бошқарувчи функция бўлса, y x нуқтани  дан  га эга қисқа вақт ичида  траектория бўйича олиб келар экан. Шунинг учун кўрилаётган ҳолда асосий масала оптимал ( энг қисқа ) вақт масаласи дейилади.
Ўрганилаётган ҳолда, юқорида келтирилган максимум принципи қуйидаги содда кўринишга эга бўлади. Аввалгидек,  оптимал жуфтлик бўлсин. Энди  бўлиб қўшимча тенглама эса

                                                    (7)

шаклда бўлади.
Оптимал ( энг қисқа ) вақт масаласи учун максимум принципи.  Агар   оптимал жуфтлик бўлса, (7)-тенгламанинг тривиал бўлмаган   ечими мавжудки,

                         (8)

ва    бўлади.

4. Шу келтирилган максимум принципидан фойдаланиб, қуйидаги бошқарув назариясининг энг содда масаласи деб аталувчи мисолни кўрайлик.
Мисолнинг тенгламалари:            
                                        (9)

ихтиёрий нуқта.
Бу мисол  учун  . Шунинг учун  ва   Шундай қилиб, максимум принципини қаноатлантирувчи бошқарилувчи функция  қуйидаги

                     (10)

шартларни қаноатлантиради. Демак,

                                           (11)

Кўриниб турибдики,  фақат иккита қиймат қабул қилиш мумкин  ва орти\и билан бир марта  бир қийматидан иккинчи қийматига ўтиши мумкин. Демак   траектория қуйидаги

                             (12)

системалар траекторияларидан тузилар экан.  (12)-системанинг траекторияларини топиш қийин эмас:
 Уларнинг графиклари 1-расмда тасвирланган.

1-расм

Келтирилган расмлардан фойдаланиб, максимум принципини қаноатлантирувчи траекторияларни қурамиз (2-расм)

2-расм

2-расмидан кўриниб турибдики, агар  нуқта АОВ чизиқдан юқорида жойлашган бўлса, аввал  бошқарув остида, кейин эса ( С нуқтага келганимиздан сўнг )   бошқарув остида ҳаракат қилади. Агар  нуқта ОВ чизи\ида жойлашган бўлса, биз   бошқарув усулини қўллашимиз керак.  (  нинг АОВ чизиқдан пастда ёки АО чизиқда жойлашиш ҳоллари 2-расмдаги  кўрсатмага асосан таҳлил этилади ).

5. Ўз-ўзидан кўриниб турибдики, максимум принципига  асосланиб, оптимал бўлиши мумкин бўлган бошқарувчи функциялар ва траекторияларни ажратиб олишимиз мумкин экан. Хусусан 2-расмдаги траекториялар ва уларга  мос келган бошқарувчи функцияларни биз оптимал бўлади, деб айта олмаймиз. Уларнинг оптимал бўлишлиги алоҳида текширилиши лозим.
Биз, энди  шу саволга ўтамиз. (2)-тенглама чизиқли бўлсин, яъни

                                                     (13)

бу ерда А-ўзгармас матрица, - ихтиёрий нуқта,   бўлсин.
Кўрилаётган ҳол учун қўшимча тенглама

                                                                    (14 )

кўринишни олади ( бу  ерда   - сатр-вектор ).
- ихтиёрий бошқарувчи функция,
-қуйидаги

                                                               (15)

тенгламанинг ечими,   эса (14)-тенгламанинг ечими бўлсин. Агар   барча   лар учун

                                                  (16)

бўлса у ҳолда  учлик экстремал учлик дейилади.

Теорема. ( Максимум принципининг етарлилиги ҳақида ). Агар   экстремал учлик бўлиб, деярли барча   лар учун

                                                              (17)

бўлса, у ҳолда  оптимал жуфтлик бўлади.
Исботи.   бўлиб,  бошқа жуфтлик бўлиб,  шартларни қаноатлантирсин     ( яъни  бошқарувчи функция  нуқтани  дан 0 га   га қараганда камроқ вақтда олиб келсин ). У ҳолда

                (18)

бўлади. Равшанки,

                 (19)
Ихтиёрий  учун (19) дан

                                    (20)

тенгликка эга бўламиз. (20)-тенгликдан

              (21)

тенгсизлик келиб чиқади ( бу ерда (18)  ва (20)-муносабатлардан фойдаланилади; ундан ташқари (16)-тенглик ҳам инобатга олинди ).
Иккинчи томондан,
    
                                                           (22)
тенгсизлик ҳам ўринли ( бу  ерда (20)-муносабатда  деб, (17)-шарт ҳам ҳисобга олинди ).   (21)  ва  (22)-тенгсизликлар бир-бирига зид. Бу зидликка биз  га қараганда «яхшироқ» бошқарувчи функция бор, деб фараз қилганимиз сабабли келдик.
Демак,  оптимал жуфтлик экан. Исбот қилинган теоремани 4-пунктда ўрганилган мисолга қўллайлик. Бу теореманинг текшириш керак бўлган шарти - (17)-тенгсизликдир. Бизда ((10))

                                                       (23)

бўлиб,  дир, чунки  бўлса, , бу эса  ечимнинг тривиал эмас фаразига зид. Шунинг учун  , кўпи билан, бир марта 0 га айланади; бошқа барча  лар учун  Демак, (17)-шарт  ўз-ўзидан бажарилади.
Шундай қилиб, 2-расмда келтирилган барча траекториялар оптимал бўлиб, уларга мос келган бошқарувчи функциялар оптимал бошқарувчи функциялар экан.
Исбот қилинган теоремани яна битта мисолга қўллайлик. Бу мисолни таҳлил қилаётганимизда ҳисоб-китобларни тушириб қолдирамиз; тафсилотларни  адабиётлардан топиш мумкин.

                             (24)

  ихтиёрий нуқта, .
(24)-система  учун  

                                                          (25)

ва   ва -ўзгармас сонлар, . Энди  ихтиёрий экстремал учлик бўлсин. Унда
 бўлиб,  агар   бўлса, ва  агар   бўлса. Равшанки,   функцияси ихтиёрий  сегментда чекли марта 0 га айланади. Шунинг учун ихтиёрий экстремал учлик  нинг биринчи иккита компонентасидан тузилган  жуфтлик оптимал  бўлади.
6. Мазкур пунктда оптимал  вақт масаласига Р. Беллманнинг динамик программалаштириш усулини қўллаймиз. Бунда қуйидаги иккита шартни бажарилган деб ҳисоблаймиз.
1-шарт.   нуқтани  ўз ичига олган шундай очиқ G тўплам мавжудки, ихтиёрий  нуқтадан   нуқтага энг қисқа вақт ичида ўтиш мумкин.
Оптимал вақт  билан, - ни эса   билан белгилайлик.  функцияси Беллман функцияси дейилади.
2-шарт.    функцияси  узлуксиз бўлиб, барча  нуқталарда унинг узлуксиз  хусусий ҳосилалари мавжуд.
Теорема. Юқоридаги иккита шарт бажарилса, функцияси  соҳада қуйидаги

                                                      (26)
тенгламани қаноатлантиради.
Изоҳ.  (26)-Беллман тенгламаси дейилади.Теореманинг исботи жуда содда, у [6]-адабиётда келтирилган.
Ҳозир, биз бу теореманинг барча шартларини қаноатлантирувчи мисолни кўрамиз.
Мисолнинг тенгламаси қуйидагича:
                                                          (27)

   ихтиёрий нуқта,  -ўзгармас сон.
Содда ҳисоблар шуни кўрсатадики, ихтиёрий  нуқтадан 0 нуқтага  бошқарувчи функция ёрдамида    вақт давомида етиб келиш мумкин. Кўрсатиш мумкинки, бу вақт оптимал вақт бўлади  ( машқ сифатида бу тасдиқни исбот қилинг ). Шунинг учун юқорида келтирилган 1-шарт бажарилган  2-шартга келсак,
                                                          (28)
функциянинг узлуксизлиги,  ҳосилаларнинг барча  нуқталарда мавжуд ва узлуксизлиги кўриниб турибди.
Шундай қилиб, (28)-функция (26)-тенгламани да қаноатлантирар экан ( асос-юқорида исбот қилинган теорема). Бу тасдиқни бевосита исбот қилиш ҳам мумкин.
Исбот қилинган теоремани 4-пунктда ўрганилган мисолга қўллаб бўлмайди, чунки у мисол учун қурилган Беллман функцияси АОВ чизи\ининг устида хусусий ҳосилаларга эга эмас [6].
Шунга қарамасдан,  Беллман тенгламасидан етарли шарт сифатида фойдаланиш мумкин. Бунинг учун унга бошқачароқ ёндашиш, яъни унинг ечимини умумийроқ маънода тушуниш керак [6]. (Худди 1-бобдаги каби етарли шарт таклиф қилиниши мумкин, аммо биз бу саволга тўхталмаймиз).

III боб

Дифференциал ўйинлар назариясининг
асослари

1. 	Дифференциал ўйинлар назариясининг тарихи XX- асрнинг 50-йилларидан бошланган. Америкалик олим Р.Айзекс 1950 йилда дифференциал ўйинларга ба\ишланган ўзининг биринчи илмий ишини чоп этмаган. Бир нечта мисолларни таҳлил этиш жараёнида у, ўзининг усулини яратган. Унинг «Дифференциал ўйинлар» деган китоби А+Шда 1965 йилда нашр қилинган (бу китоб 1967 йилда рус тилида чоп этилган [17). Бу борада рус олимлари Л.С.Понтрягин, Н.Н.Красовский, Б.Н.Пшеничний, Л.А.Петросян ва уларнинг шогирдлари номларини эслашимиз керак. 1966 йилда Л.СПонтрягиннинг чизиқсиз дифференциал ўйинларга ба\ишланган асосий иши, 1967 йилда унинг чизиқли қувиш ўйинларига аталган илмий ишлари ( ккита усули , 1971 йилда эса қочиш масаласи ҳақидаги тадқиқотлари эълон қилинган [17]. Дифференциал ўйинлар назарияси яратилишига Н.Н.Красовский ва унинг мактаби ҳиссаси катта. Бу соҳада Ўзбекистон олимларининг ҳам салмоқли илмий натижалари маълум Н.Сатимов, А.Азамов, Б.Рихсиев, А.Фозилов, Л.Югай ва бошқалар.
2. 	Дифференциал ўйинлар назарияси учун керакли баъзи маълумотлар.
1. А ва В , фазонинг ихтиёрий тўпламлари бўлсин. Уларнинг алгебраик йи\индиси деб

                                        (1)

тўпламга айтилади: айирмаси деб эса қуйдаги 

                                      (2)

тўпламга айтилади.

 Равшанки, умуман айтганда, 
-ҳақиқий сон бўлсин. А тўплам деб қуйидаги

                                                                   (3)

тўпламга айтилади. Арифметикадан фарқли ўлароқ, умуман айтганда, . Агар  белгиси билан  тўпламни белгиласак, кўрсатиш мумкинки, .
	Энди дифференциал ўйинлар назариясига биринчи марта 1967 йилда  Л.С.Понтрягин томонидан киритилган геометрик айирма ёки альтернатив айирма деб аталувчи амалнинг таърифини келтирамиз.
	А  ва В  тўпламларининг геометрик айирмаси деб қуйидаги
                                                    (4)

тўпламга айтилади. Бу амалнинг учта  ажойиб хусусиятини келтирамиз  А, В ва С тўпламлар учун
        
            (5)

муносабатлар ўринли.
+уйидаги

   (6)
Бу ерда  - бўш тўплам белгиси,(6)-формулани осонликча исбот қилиш мумкин.
2.  фазонинг барча тўпламостилари тўпламини  билан белгилайлик. 
 ва - ихтиёрий сонлар, бўлиб  бўлсин.
+уйидаги
                                                            (7)

акс эттириш кўп қийматли функция ёки кўп қийматли акс эттириш дейилади. 
	Мисоллар.     

	Кўп қийматли функцияларнинг интеграли  таърифини келтирамиз. Бизга  кўп қийматли функция берилган бўлсин. Унинг интеграли деб, қуйидаги

                                                       (8)
                 -жамланувчи функция,      
тўпламга айтилади. (8)-ёзувда  -одатдаги n-ўлчовли бир қийматли вектор функция, уни  акс эттиришнинг селектори ёки шохчаси дейилади. 
	Бошқача қилиб айтганда,  нинг интеграли унинг барча селекторлари интегралларидан ташкил  топган тўплам экан (Яна, (8)-ёзувда,  деб,  нинг Лебег интеграли тушунилади).
	+уйидаги тасдиқ интегрални ҳисоблашни осонлаштиради.
	Тасдиқ. Агар-манфий бўлмаган жамланувчи функция, бўлиб А қавариқ тўплам бўлса. 

                                                   (9)

бўлади.
3. Бизга  функцияси берилган бўлсин. Агар бу функция  маҳкамланганда t бўйича ўлчовли, t маҳкамланганда х бўйича узлуксиз бўлса, у ҳолда бу функцияси Каратеодори функцияси дейилади.
	+уйидаги 

                                                                  (10)

дифференциал тенгламани кўрайлик.   функцияси (10)-тенгламанинг ечими дейилади, агар:
1. I-оралиқ; 
2.  , -абсолют узлуксиз функция;
3. деярли барча  лар учун  тенглик ўринли бўлса. Бундай ечимни абсолют узлуксиз ёки умумлашган ечим дейилади. Баъзи ҳолларда у одатдаги ечим билан устма-уст тушади.
	Энди (10)-тенгламанинг қачон ечими мавжуд бўлади деган саволга жавоб берамиз.
Каратеодори теоремаси [12]. Айтайлтк -ихтиёрий маҳкамланган нуқта бўлсин. Фараз қилайлик:

1. 
соҳа мавжуд бўлсин;
2. , жамланувчи функция мавжуд бўлиб, барча 
 лар учун

тенгсизликлар бажарилсин. У ҳолда (10)-тенгламанинг  да аниқланган,   шартни қаноатлантирувчи ягона ечими мавжуд бўлад.
	Каратеодори теоремасининг барча шартларини қаноатлантирувчи  (10)-тенглама учун мисол келтирамиз.
	
Мисол.  бўлиб,  жамланувчи функция,   жамланувчи функция. Кўрилаётган ҳолда ечим учун формула ҳам чиқариш мумкин. Бу формула Коши формуласи дейилади. Бунинг учун қуйидаги
                                                             (11)
бир жинсли чизиқли тенгламани кўрайлик. Унинг фундаментал матрицасини  билан белгилайлик ( эслатиб ўтамиз:    Е-бирлик матрица ). У ҳолда  тенгламанинг ечими қуйидаги

                                   (12)

Коши формуласи билан берилади.
	Агар ўзгармас матрица бўлса, (12)-формула қуйидаги содда кўринишга эга бўлади:
                                    (13)
	Бу ерда  матрица   тенгламанинг  фундаментал матрицасидир  ((11)).
3. 1.  Дифференциал ўйин нима, деган саволга жавоб бериш учун қуйидаги содда мисолни кўрайлик.
 	 фазонинг  нуқтаси шу фазонинг у нуқтасини қувлаётган бўлсин.
Бу  нуқталарнинг ҳаракатлари

                                                              (14)

тенгламалар билан ифодаланиб, (14) даги ва лар бошқарилувчи  параметрлар бўлсин.  параметрни қувувчи параметр,  ни эса қочувчи параметр деб атаймиз. Улар ўз қийматларини    ва  радиусли шарлардан қабул қилишсин:   Яна  нуқта у нуқтани ушлади деймиз, агар   бўлса. 

 параметрни биз бошқарайлик,  ни эса бшқа  бир шахс («рақиб») бошқарсин. Биз   ни шундай бошқаришимиз керакки, натижада  қандай қилиб бошқарилмасин,   тенглик бажарилсин. Ўшанда биз ўз мақсадимизга эришамиз.  Агар биз қандай қилиб ўзимизнинг параметримиз   ни бошқармайлик,  ни шундай қилиб бошқариш мумкин бўлсаки,  тенглик ҳеч қачон бажарилмаса, бизнинг рақибимиз ўз мақсадига эришган бўлади.
	+уйидаги иккита тасдиқни исбот қилишимиз мумкин.
1-тасдиқ. Агар    бўлса,  нуқта  нуқтани доим ушлаб олади.
2-тасдиқ. Агар  бўлса,   нуқта  нуқтани ҳеч қачон ушлай олмайди.
	Ҳақиқатда ҳам. агар   деб олинса,  нуқта  билан   вақт ичида устма-уст тушади (бу ерда  ва   ва  уларнинг  даги ҳолатлари, ). Чунки, (14) даги   нинг ўрнига ихтиёрий ўлчовли  функцияни,  нинг ўрнига эса  ни олиб бориб қўйсак,

                                            (15)

га эга бўламиз.  Бу ердан эса эканлиги кўриниб турибди.

Энди  деб, қочувчи параметрни  деб танласак,
                       (16)

тенгликка эга бўламиз (бу ерда  ихтиёрий ўлчовли функция). (16) нинг икки томонини  га скаляр кўпайтирсак, 

га бўламиз. Бу ердан эса, барча  лар учун  эканлиги равшан.
	Юқоридаги мисолдан кўриниб турибдики, дифференциал ўйин берилиши учун унинг тенгламалари, тенгламаларда қатнашган параметрларнинг ўзгариш соҳалари ва ўйиннинг тўхташ шарти берилиши керак экан. 
	2. Биз қуйидаги чизиқли дифференциал ўйин деб аталувчи ўйинни кўрамиз. Бундай ўйин ўзининг тенгламаси (тенгламалар системаси)
                                 (17)

билан берилган бўлиб, унинг тўхташ шарти М шаклида берилади (яъни М бўлса, (17)-ўйин тугалланган (ёки тўхтаган) деб ҳисобланади);  (17) да  М тўплам терминал (тугалланувчи) тўплам дейилиб, у  нинг чизиқли фазоостиси деб ҳисобланади. Р ва Q тўпламлар компакт тўпламлар деб  фараз қилинади.
	(17)-ўйин  бошлан\ич нуқтада  вақтда тугалланади дейилади, агар шундай  функция мавжуд бўлиб, у қуйидаги 1 ва 2-шартларни қаноатлантирса:

1. ихтиёрий  ўлчовли функция учун  функция  ўлчовли функция;
2. ихтиёрий  ўлчовли функция учун

                                        (18) 

тенгламанинг  траекторияси  нинг бирор қийматида М тўпламга келиб тушади:         .
	Таърифда келтирилган  вақт ўйинни тугатиш (ушлаш) вақти дейилади. Равшанки, бу таъриф ўйиннинг тенгламаси чизиқсиз  бўлган ҳолда ҳам келтирилиши мумкин. Лекин асосий натижалар  чизиқли ўйинлар учун олганлиги учун биз фақат  чизиқли ўйинлар билан шу\улланамиз.
	3. М чизиқли фазоостининг   гача бўлган  ортогонал тўлдирувчисини  L  деб,   R  ни   L  га ортогонал проекцияловчи операторни (амални)  деб белгилайлик ва қуйидаги бошқа белгилашларни ҳам киритайлик:

                (19)
       
             (20)

Изоҳ.  тўплам Л.С.Понтрягиннинг 1-интеграли дейилади.
1-теорема. Агар бирор мусбат  учун 
                                                           (21)
бўлса,  бошлан\ич нуқтадан (17)-ўйинни  вақт ичида тугатиш мумкин. 
	Теореманинг исботи қийин бўлмаса ҳам, лекин жой олгани  сабабли уни тушириб қолдирамиз. Исботи ўрнига эса уни Л.С.Понтрягиннинг машҳур «контрол мисол» деб аталувчи мисолига қўллаймиз [17].

4. Мисол қуйидаги
                  
                           (22)

тенгламалар билан ифодаланиб, бу ерда  мусбат ўзгармас сонлар,  ўйиннинг терминал тўплами

	Энди ҳисоб-китобларни тушириб қолдириб (уларни тиклаш қийин эмас), қуйидаги тасдиқни келтирамиз.
Тасдиқ.  1. Агар  бўлса, чексиз сондаги бошлан\ич нуқталар борки, улардан (22)-ўйин тугатилади.
2. Агар  бўлса, барча бошлан\ич нуқталардан 
(22)-ўйин тугатилади.
3. Агар  бўлса, чексиз сондаги бошлан\ич нуқталар борки, улардан (22)-ўйинни тугатиш мумкин.
	Яна битта мисол кўрайлик. Мисолнинг тенгламалари

          (23)

кўринишда бўлиб, ўйиннинг терминал тўплами М бўлсин.
	Бу мисол «Бола ва тимсоҳ» ўйини дейилади.
	Равшанки, М чизиқли фазоости бўлмагани учун юқорида келтирган теоремани (23)-ўйинни таҳлил қилиш учун қўллаб бўлмайди. Бу мақсадга эришиш учун Л.С.Понтрягиннинг 2-усулига ўтамиз (юқоридаги теоремани Л.С.Понтрягиннинг 1-теоремаси ёки унинг 1-усули деб  аталади).
4. +уйида кўриладиган дифференциал ўйинларда терминал тўплам 
                                                        (24)

шаклида берилган деб ҳисобланади. Бу ерда М0 -чизиқли фазоости, М1 тўплам М0 нинг ортогонал  тўлдирувчисининг тўпламостиси деб фараз қилинади.
Юқоридагидек,  М0  нинг ортогонал тўлдирувчисини L билан, R ни L га ортогонал проекцияловчи амални  билан белгилайлик (бошқа белгилашлар -3. да келтирилган). 
Ихтиёрий мусбат  сонни олиб,  сегментни бўлувчи  нуқталарини олайлик. Бу бўлиш усулини   ҳарфи билан белгилайлик. +уйидаги
                     (25)

тўпламлардан фойдаланиб,

          (26)

тўпламларни тузайлик ва 

                                              (27)

тўпламни ажратиб олиб, 

                                                            (28)
тўпламни қурайлик.  тўплам Л.С.Понтрягиннинг 
2-интеграли дейилади.
2-теорема. Агар бирор мусбат   учун 

                                                               (29)

бўлса, у ҳолда  нуқтадан (17)-ўйинни тугатиш мумкин.

Изоҳ.  1-теоремада  ни  шаклида қурилган бўлса, 2-теоремада  нинг  вақтдаги қийматини топиш учун рақиб қўллаётган   функциянинг  сегментдаги барча қийматларидан фойдаланилади; бу ерда  -ихтиёрий мусбат сон.
2-теоремани (23)-мисолга қўлласак, (30)

деган натижага эришамиз. (30) да S тўплам  даги маркази О нуқтадан жойлашган радиуси  1 га тенг ёпиқ шар, Т эса    тегламанинг  биринчи мусбат илдизидир.
	Кўрсатиш мумкинки,  ҳолида барча бошлан\ич нуқталардан (23)-ўйин тугатилади,  ҳолида эса, барча бошлан\ич нуқталардан эмас, уларнинг чексиз қувватга эга бўлган қисмидан  ўйин тугатилади.
	5. Юқорида айтилганидек, 2-теоремани исбот қилаётганимизда   ни қуриш учун  дан фойдаланишга тў\ри келади. +уйида таърифланадиган теорема бўндай камчиликдан  ҳолис. Лекин, 2-теоремада М тўплам ихтиёрий эди, энди уни қавариқ, деб фараз қиламиз.
	Айтайлик  ихтиёрий манфий бўлмаган жамланувчи функция бўлиб, 
                                                               (31)
бўлсин.  дан фойдаланиб,  
                          
                           (32)
                                      (33)

тўпламларни тузайлик. Ниҳоят,
                                                       (34)

бўлсин.
3-теорема. Агар бирор мусбат   учун
                                                                                    
                                                          (35)

бўлса,  бошлан\ич нуқтадан (17)-ўйинни  вақт ичида тугатиш мумкин.
Изоҳ. 3-теоремада   шаклида   тузилади (яъни, худди 1-теоремадагидек).
	Мисол тариқасида (23)-ўйинни кўрайлик. Ҳисоблашлар шуни кўрсатадики (биз уларни тушириб қолдирамиз), барча  лар учун  Шунинг учун 4. даги 2-теорема ёрдамида (23)-ўйин учун келтирилган натижаларни 3-теоремани қўллаб ҳам олиш мумкин.
	Изоҳлар. 1. Кўрсатиш мумкинки, барча  лар учун .  
2. Мазкур пунктда келтирилган 3-теорема 1981 йилда  таклиф этилган бўлиб,  3-теорема нуқтаи назаридан (23)-мисол 1979 йилда ўрнатилган.
3.  1, 2, 3-теоремаларнинг (14)-мисолга тадби\и бир хил натижа-1  -тасдиққа олиб келади, 3, 1.). 
	6. Мазкур пунктда (17)-ўйинни яна бир масала-қочиш масаласи нуқтаи назаридан ўрганамиз. Энди биз v параметрни танлаймиз. Мақсадимиз z ни M га тушишига халақит қилиш (қаршилик кўрсатиш) [17].
Терминал тўплам М чизиқли фазоости, деб фараз қилинади. Унинг ортогонал  тўлдирувчиси бўлган L нинг ихтиёрий фазоостисини W ҳарфи билан белгилайлик.    билан R ни W га ортогонал проекциялаш амалини белгилайлик.

Теорема [17]. Агар шундай икки ўлчовли W ва натурал сон К мавужд бўлиб:
1. барча  тўпламлар  бир элементли тўпламлар,
2.  тўплами ички нуқтага эга бўлса, (17)-ўйинда V параметни шундай бошқариш мумкинки, z нуқта ихтиёрий бошлан\ич  нуқтадан чиқиб, ҳеч қачон М тўпламга келиб тушмайди.
	Келтирилган теорема нуқтаи назаридан (14), (22) ва (23)-мисолларни  таҳлил этайлик. Кўрсатиш мумкинки, агар (14)-мисолда  ва  (22)-мисолда  ва  , (23)-мисолда  бўлса, юқорида таърифланган теореманинг барча шартлари бажарилади; демак, бу ўйинларда ҳолат векторини терминал тўпламга  нинг барча мусбат қийматларида туширмаслик мумкин.

Айтилганларни таъкидлаш маъносида қуйидаги масалани кўрайлик

                                                      (5)
                                                                (6)
                                                              (7)
                                                               (8)
                                                                     (9)

Аввал (7)-тенгсизликни иккала томонини 1 га кўпайтириб масалани умумий кўринишга келтириб оламиз. Кейин  га манфиймаслик шарти қўйилмаганлиги сабабли, уни  га алмаштирамиз, (6) ва ўзгартирилган (7) тенгсизликларни чап томонларига мос равишда  ва  ларни  қўшиб, тенгсизлик белгилари ўрнига тенглик белгиларини ёзамиз. (5)-мақсад функция ишорасини алмаштирамиз. Бу ўзгартиришлардан сўнг (5)-(9) масала қуйидаги

каноник кўринишдаги масалага келади.
Агар охирги масала ечимини  билан белгиласак, га бошлан\ич масалани ечими (5) ни қиймати эса   га тенг бўлади.

2. Чизиқли программалаш масаласини график усулда ечиш

Агар  ўзгарувчилар сони  бўлса масалани график усулда, яъни чизма орқали ҳам ечиш мумкин. Биз  ҳолни кўриб ўтамиз. Ўзгарувчилар сони  бўлганлиги сабабли чизиш ишларини  текисликда олиб бориш мумкин. Демак, бу ҳолда чизиқли программалаш масаласининг умумий кўриниши қуйидагича бўлади

                                                          (10)
                                                            (11)

........................
                            (12)

бу ерда -ўзгармас сонлар. Тушунарлики, (11) тенгсизликни ҳар бири  текисликда ярим текисликни аниқлайди. Буни аниқлаш учун ихтиёрий бирорта тенгсизликни оламиз, масалан , уни тенглик ҳолда ёзсак  бўлиб,  текислигида унга тў\ри  чизиқ-ярим текисликни чегараси мос келади. Энди, тенгсизликка мос ярим текисликни аниқлаш учун тў\ри чизиқ устида ётмаган бирор нуқта координаталарини тенгсизликни чап томонига олиб бориб қўшиш керак, агар бунда тенгсизлик ўринли бўлса, демак нуқта изланаётган ярим текисликда ётган бўлади, акс ҳолда изланаётган ярим текисликда бу нуқта ётмайди. Шундай усул билан (11)ни ҳар бир тенгсизлигига мос келган ярим текисликлар топилади ва уларнинг кесишмаси (12) шарт билан биргаликда чегараланган ёки чегараланмаган қавариқ кўп бурчакни-жоиз режалар тўпламини аниқлайди. 
Мақсадимиз шу кўпбурчакда (10)  функцияни максимал қийматини топишдир. Бунинг учун фараз қиламизки, мақсад функцияни қиймати бирор  сонига тенг бўлсин, яъни

                                                          (13)

 ни  қиймати ҳозирча бизни қизиқтирмайди, чунки ке-йинчалик у ўзгартирилади. Текисликда (13) тенгликка мос келган тў\ри чизиқ олинади. Равшанки,  нинг ўзгариши бу тў\ри чизиқни  параллел суриш билан эквивалентдир. Бундан ташқари бу тў\ри чизиқнинг нормали ни чап томонидаги функциянинг градиенти ҳисобланади.
Демак, нормал бўйича тў\ри чизиқ сурилса, функция қиймати  сони ортади ва аксинча  нормалга қарши томонга сурилса, функция қиймати камаяди, (ни қиймати кичраяди). Шунинг учун (13) билан аниқланган тў\ри чизиқни паралел суриш билан, яъни ни орттириб ёки камайтириб, уни жоиз режалар тўплами-кўпбурчакдан ўтадиган қилиб олиш керак. Кейин, бу тў\ри чизиқни нормал  бўйича параллел суриб кўпбурчак четига олиб келиш лозим. Натижада (10)-мақсад функция максимал қийматга эришади. Чунки, тў\ри чизиқни  бўйича параллел суриш мақсад функциянинг қийматини ошишига олиб келади, лекин кўпбурчакдан чиқиб кетилади, аксинча га қарши суриш кўпбурчакдан чиқармаслик мумкин, аммо (10)-мақсад функциянинг қиймати камаяди. Демак, кўпбурчакни  йўналиш бўйича четида бўлган режа (режалар) да (10)-мақсад функция энг катта қийматга эришади ва бу режа-оптимал режа (10)-(12) масаланинг ечими бўлар экан. Равшанки, агар йўналиш бўйича кўпбурчакни чети йўқ бўлса, (10)-мақсад функциянинг максимал қиймати йўқ (у ихтиёрий сондан катта).

+уйидаги чизиқли программалаш масаласи берилган бўлсин:
Пахта чигитини қайта ишловчи завод чигитдан уч хил маҳсулот 1-пахта ё\и, 2-шулиха, 3-пахта чивити ишлаб чиқаради. Бу завод чигитни иккита таъминотчи: I ва II пахта чивиш заводидан сотиб олади. I ва II пахта чивиш заводларидан чиқадиган чигитлар турли сифатли бўлганлиги сабабли, уларнинг ҳар бир тонна чигитидан чиқадиган 1, 2 ва 3 маҳсулотлар нисбати ҳам турличадир. I-таъминотчи-заводни ҳар тонна чигитини 0,2 қисми 1-маҳсулотга, 0,3 қисми 2-маҳсулотга, 0,4 қисми 3-маҳсулотга қолган 0,1 қисми чиқинди бўлса, II-таъминотчининг ҳар тонна чигитини 0,3 қисми 1-маҳсулотга, 04, қисми 2-маҳсулотга, 0,2 қисми 3-маҳсулотга ва қолган 0,1 қисми чиқинди бўлади. Бундан ташқари 1-маҳсулотга бўлган талаб  2-маҳсулотга бўлган талаб , 3-маҳсулотга бўлган талаб  бўлсин. Чигитдан маҳсулот олувчи завод I-таъминотчининг ҳар бир тонна чигитидан 8 бирлик, II-таъминотчининг ҳар бир тонна чигитидан 10 бирлик соф фойда олсин. Чигитдан маҳсулот олувчи завод I, II таъминотчи заводлардан чигит сотиб олса, биринчидан талаблар иложи борича қондирилади; иккинчидан умумий соф фойда максимал бўлади.
Бу  масалани қуйидаги жадвал кўринишида ёзиб олиш қулайлик ту\диради,

Маҳсулот	I таъминотчи завод	II таъминотчи завод	Маҳсулотга бўлган 	
1	0,2	0,3	 90	
2	0,3	0,4	135	
3	0,4	0,2	100	
Соф фойда	8	10		

Агар  ва  билан I ва II таъминловчилардан мос равишда сотиб олиниши керак бўлган чигитлар миқдорини белгиласак. Берилишига асосан I-заводдан сотиб олинган  чигитдан мос равишда 0,2, 0,3, 0,4  1, 2 ва 3 маҳсулотлар ишлаб чиқарилади, ҳудди шундай II заводнинг  чигитидан 0,3, 0,4, 0,2  1, 2, 3 маҳсулотлар ишлаб чиқарилади. Демак, маҳсулотлар миқдори мос равишда 0,20,3,  0,30,4  ва 0,40,2,  га тенг бўлиб, маҳсулотларга бўлган чегарани ҳисобга олсак

                            (14)
	
тенгсизлаклар системасига эга бўламиз. Лекин чигитдан маҳсулот олувчи заводни олинган чигитлардан кўрадиган фойдаси  га тенг. Демак, мақсад функция ни (14)-шарт остида максимумини топиш керак экан. Ўзгарувчилар сони 2 та бўлганлиги сабабли бу масалани график усул билан ечамиз. Бунинг учун (14)-тенгсизликлар системаси билан аниқланган кўпбурчакни-жоиз режалар тўпламини чизиб оламиз. Текисликда  координаталар системасини киритайлик ва (14)-тенгсизликларнинг ҳар бирини тенглик ҳолга келтириб мос тў\ри чизиқларни аниқлайлик. Бу чизиқлар 1- расимда кўрсатилган

1-расм.

Энди (14) тенгсизликни ҳар бири қайси ярим текисликни аниқлашини топиш учун (0,0) нуқта координаталарини тенгсизликларга қўйсак, улар ўринли бўлади, демак координата боши жойлашган ярим текисликлар кесишмаси билан  нуқталар биргаликда ОАВД тўртбурчакни -жоиз режалар тўпламини беради. Энди бу жоиз режалар тўпламидан оптимал режани топиш учун  чизиқни чизайлик (демак, фараз этилганки вақтинча мақсад функциянинг қиймати 1600 га тенг деб) у 1-расмда EF га мос келади.  вектор эса бу EF чизиққа нормал бўлиб, чизмада кўрсатилган томонга йўналган. EF чизиқ ОАВД тўртбурчак билан кесишиб турганлиги сабабли мақсад функцияни қийматини катталаштириш учун, уни с вектор бўйича параллел силжитамиз ва 1-расмдаги ҳолатни эгаллаганда суришни тўхтатамиз, чунки энди яна суриш ОАВД тўртбурчакдан чиқиб кетишга олиб келади. Демак, бу ҳолда сурилган тў\ри чизиқ билан ОАВД тўртбурчак умумий ягона В нуқтага эга бўлар экан. 

Бу В нуқта (14) даги биринчи ва учинчи тенгсизликларга мос келган тў\ри чизиқларнинг кесишиш нуқтасидир. Шунинг учун  тенгламалар системасини ечиб В (150, 200) нуқтани координаталарини топамиз. Бу эса оптимал режа ни аниқлаб беради. Яъни шу режада  мақсад функция максимум қийматга эришади: 
Шундай қилиб чигитдан машсулот  ишлаб чиқарувчи завод таъминловчи заводлардан мос равишда 150 ва 200 чигит сотиб оладиган бўлса, биринчи ва учинчи, маҳсулотга бўлган талаб тўла, иккинчи маҳсулотга бўлган талаб эса қисман қондирилар экан. Лекин, бунда заводни олган соф фойдаси максимал бўлиб, у 3200 бирликка тенг.

3. Чизиқли программалаш масаласининг хоссалари.
	
Бизга каноник кўринишдаги қуйидаги чизиқли программалашни масаласи 
                                                       (1)
                           ,                                (2)
                                                                 (3)
ёки матрица кўринишида
                                                               (1’)
                                                                        (2’)
                                                                         (3’)
берилган бўлсин, бу ерда ,  -ўзгармас матрицалар, -ўзгарувчилардан тузилган вектор.  дегани   масаланинг мақсад функцияси, (2),  (2‘),  (3),  (3’) лар чегаралар деб аталади. Агар  белгилашни киритсак, (2) (2’) ларни қуйидагича  кўринишда ёзиш мумкин бўлади.
Таъриф 1:  (1)-(3) масаланинг жоиз  режаси бўлсин. Агар  режани мусбат  компонентларига  мос келган  векторлар чизиқли бо\лиқ бўлишмаса,  режа (1)-(3) масаланинг таянч режаси деб аталади.  векторларни ҳар бири  ўлчовли бўлганлиги учун таъриф 1.дан кўриниб турибдики, таянч  режанинг мусбат компонентлари кўпи билан  та бўлади.
 	Таъриф 2: Таянч режа хосмас деб аталади, агар уни мусбат компонентлари сони  га бўлса, акс ҳолда хос деб аталади.
Таъриф 3: Чизиқли программалаш масаласи хосмас деб аталади, агар унинг барча таянч режалари хосмас бўлишса. Акс ҳолда масала хос деб аталади.
Кўрсатиш мумкинки, (2), (3) шартларни қаноатлантирувчи  вектор  тўплами фазода кўпёқликни ташкил этади.
Теорема 1. (2), (3) шартларни қаноатлантирувчи  векторлар тўплами қавариқ кўпёқликдир.
Исботи. -векторлар (2), (3) ёки (2’), (3’) шартларни қаноатлантирсин. У ҳолда, ихтиёрий  сонлари учун  чунки демак, кўпёқликнинг, ихтиёрий икки нуқтасини чизиқли қавариқ комбинацияси, яна шу тўпламга тегишли бўлар экан. Бундан, уни қавариқлиги келиб чиқади. Теорема исботланди. 
Теорема 2. Жоиз режалар тўпламида мақсад функция (1) ўзининг энг катта қийматига кўпёқликни учида эришади. Агар мақсад функция энг катта қийматига кўпёқликнинг бирдан кўп нуқтасида эришса, бу нуқталарни чизиқли қавариқ комбинациясидан иборат бўлган ихтиёрий нуқтасида ҳам энг катта қийматига эришади.
	Исботи. Фараз этайлик, жоиз режалар тўплами чагараланган кўпёқликдан иборат бўлсин. Маълумки, бу чегараланган, ёпиқ кўпёқликда чизиқли (1) функция ўзининг  энг катта қийматига бирор  нуқтада эришади. 
	Агар кўпёқликни учларини  деб белгиласак, кўпёқли қавариқ бўлганлиги сабабли, шундай  сонлари мавжудки, улар учун қуйидаги тенглик ўринли
	                                                     (4)
-нуқталарда (1) - функциянинг энг катта қиймати  бўлсин, яъни
	                                               (5)
	Мақсад функция чизиқли функция эканлигидан (4) ва (5)ни ҳисобга олган ҳолда қуйидаги муносабатларни ҳосил қиламиз.
	      (6)
	лекин   функцияга максимум қиймат берувчи бўлганлиги учун 
	                                    
демак .
Кўпёқликни  учида функция (1) ўзининг энг катта қийматига эришар экан. Теореманинг иккинчи қисмини исботлаш учун фараз этайлик  жоиз режаларда мақсад функция энг катта қийматга эришсин ва  га тенг бўлсин, у ҳолда (1)-чизиқли функция эканлигини ҳисобга олган ҳолда, ихтиёрий   сонлари учун   тенглик ўринли.
Теорема исбот бўлди.
Теорема 3.  жоиз режа (2), (3) шартлар билан аниқланган кўпёқликнинг учи бўлишлиги учун, унинг мусбат компонентларига мос келган  векторлар чизиқли эркин бўлиб, уларнинг  коэффициентли чизиқли комбинацияси   га тенг  бўлиши зарур ва етарлидир.
Исботи. Умумийликка зарар келтирмаган ҳолда нинг мусбат компонентлари  деб олайлик.
Зарурлиги. Фараз этайлик  жоиз режа бўлиб, биринчи  та компонентаси мусбат бўлсин. У ҳолда қолган та компонентаси нолга тенг ва  жоиз режалигини ҳисобга олган ҳолда
	                                                       (7)
	тенгликка эга бўламиз. Энди векторларни чизиқли эркли эканлигини кўрсатиш керак. Бунинг учун тескарисини фараз этамиз векторлар чизиқли бо\лиқ бўлишсин,
бу дегани шундай  сонлар топиладики улар учун   бўлиб,
                                                 (8)
тенглик бажарилади, бу ерда (8) тенгликнинг ўнг томонида -ўлчамли нол вектор  ёзилган.  (8)-тенгликнинг иккала томонини  сонга кўпайтириб (7) тенгликка қўшамиз ва айирамиз 

 лар мусбат бўлганлиги учун шундай   борки, унинг учун 
                        
тенгсизликлар ўринли бўлади. Бундан    ва   режаларни ҳосил қиламиз, лекин 
                              
бу эса ни кўпбурчак учи эканлигига зиддир. Демак,  векторлар чизиқли эркли экан.
Етарлилиги. Фара этайлик  векторлар чизиқли эркли бўлиб, мусбат  лар учун
                                                       (9)
тенглик бажарилсин. Кўрсатамизки  вектор жоиз режа бўлиб, кўпёқликни учи бўлади. ни жоиз эканлиги, уни тузилиши  (9) тенгликдан келиб чиқади. Фараз қтлайлик,  кўпёқликни учи бўлмасин, яъни шундай турли  -жоиз режалар борки,
                                                               (10)
тенглик бажарилади. -режани охирги n-к та компонентлари нол. Жоиз режалар бўлмаганлиги учун  ларни ҳам охирги компонентлари нолга тенг, яъни
                
лар жоиз режалар бўлганлиги учун
                                                        (11)
                                                     (12)
(11) 	дан (12) айириш орқали 
                                                  (13)
муносабатга келамиз. Лекин  векторлар чизиқли эркли, шунинг учун

бу эса  лар турли дейилганига зид, демак (10) тенглик бўлиши мумкин эмас, яъни -кўпёқликни учи экан.
Теорема исбот бўлди.
Натижа.  векторлар ўлчами  бўлганлиги учун кўпёқликни учларига мос келган режанинг мусбат компонентлари сони  дан ошиб кетмайди. Кўпёқликлар бир учига  чизиқли эркли  векторлар системаси мос келади.
Булардан келиб чиқадики, таянч режа билан кўпайган учлари ўртасида ўз аро бир қийматил мослик бор.

4.  Симплекс усул

	Умуман олганда сиплекс усул Гаусс-Жорданнинг тенгламалар системасини ечиш усулига асосланган. (Бу усул айрим адабиётларда кетма-кет йўқотиш усули деб ҳам аталади). Шу билан бирга симплекс усули базисларни алмаштиришда муҳим рол ўйнайди. Шунинг учун аввал  базисларни алмаштиришга тўхталиб ўтамиз. Шуни таъкидалаш керакки бу алмаштириш усули ҳам Гаусс-Жордан усулига асосланган  лар  ўлчамли векторлар бўлсин ва умумийликка зарар келтирмаган ҳолда -векторлар чизиқли эркли ёки m ўлчамли фазода базис ташкил этган бўлишсин. Ҳозир  векторларнинг  ихтиёрисини базис векторларнинг бирортаси билан алмаштириш масаласини кўрамиз. Яъни янги базислар системасини тузиш  масаласини кўрамиз. -лар  базис ташкил  этганлиги учун ихтиёрий -ўлчамли векторни  бу базисларни чизиқли комбинацияси кўринишда ифодалаш мумкин, хусусан ихтиёрий  вектор учун  шундай  сонлар мавжудки улар учун 
                            ,                       (14)

тенглик ўринли бўлади. Ҳозир (14) тенгликда фойдаланиб  векторни  базис векторларни бирортасига алмаштирамиз. Фараз этайлик (14)-тенгликда  бўлсин. -ўлчамли ихтиёрий -векторни олайлик, унда юқорида айтилганга асосан, шундай  сонлари мавжудки, улар учун
                                                          (15)
тенглик ўринли. (14)-тенгликни  сонга бўлиб, кейин - га кўпайтириб (15) га қўшамиз. Агар  бўлганда  ни ўрнига  ни олиш ҳеч нарсани ўзгартирмаган бўлар эди, шунинг учун  деб олинган. Демак, қўйидаги 

                   ,             (16)
тенгликка эга бўламиз. Агар (16) да ,  белгилашларни киритсак, 
                                              (17)
тенгликка эга бўламиз. Демак ихтиёрий -ўлчамли  векторни  векторларни чизиқли комбинацияси орқали ёзиш мумкин экан. Бу эса  векторлар базис ташкил этишини билдиради. 
	Фараз қилайлик каноник кўринишда берилган чизиқли программалаш масаласи хосмас бўлсин ва умумийликка зарар келтирмаган холда -таянч режани мусбат компонентлари  бўлсин. Теорема 3 га асосан
                                                          (18)
тенглик ўринли ва бу таянч режада мақсад функциянинг қиймати
                               ,                         (19)
га тенг. Ихтиёрий  векторни  базис векторлар бўйича ёйилмаси ягона бўлиб, қуйидаги
                                            (20)
кўринишда бўлсин. +уйидаги
                                            (21)
белгилашни киритайлик.
Теорема 4. Агар бирор  учун  бўлса, берилган  режа оптимал эмас. Шундай янги  режа қуриш мумкинки, унинг учун

тенгсизлик ўринли бўлади.
Исботи. (20) ва (21) ни  сонга кўпайтириб мос равишда (18) ва (19)дан айирсак

ёки
                    ,               (22)
              .        (23)
эга бўламиз. 
Энди  сонни аниқлаймиз,  лар мусбат бўлганлиги учун, шундай  сонни топиш мумкинки, унинг учун  вектор жоиз режа бўлади.  Теорема шартига асосан , демак (23) дан келиб чиқадики,  жоиз режада  мақсад функция қиймати .
Теорема исбот бўлди.
     	Симплекс усул билан берилган масалани ечиш учун бирорта бошлан\ич таянч режа маълум бўлиши керак. Бошлан\ич таянч режани топишнинг бир қанча усуллари мавжуд. Тенгламалар системасини бевосита ечишда суъний базислар усули ва бошқалар. Бунда маълумки таянч режа бу кўпбурчакнинг учларига мос келади. Шунинг учун таянч режаларни қуйидаги кўринишда.
                                 
бўлган тенгламалар системасини ечиш орқали топиш мумкин, бу ерда . Демак, кўпи билан  та тенгламалар системасини ечиш керак бўлади. Равшанки, бунда,  сонлари катта бўлса, бу усул билан бошлан\ич таянч режаларни топиш мураккабдир. Бунинг учун тенгламаларнинг ўнг томони манфиймас сонларга (тенгламани иккала томонини-1 га кўпайтириш орқали) ўзгартирилади.
	Шундан сўнг, янги ўзгарувчилар -базис ўзгарувчилар ҳар бир тенгламанинг чап томонига мос равишда қўшилади. Натижада  бошлан\ич таянч режага эга бўламиз (агар  бўлса хосмас таянч режа ҳосил қиламиз).
Теорема 5. Агар бирор таянч режа учун шундай  топилсаки  бўлиб,  тенгсизликлар ўринли бўлса, у ҳолда мақсад функция юқоридан чегараланмаган.
Исботи. Умумийликка зарар келтирмасган ҳолда -масаланинг таянч режани теорема шартларини бажаради деб олишимиз мумкин. У ҳолда шундай  борки, унинг учун  ва  шартлар бажарилади. +уйидаги векторни кўрайлик: ,  сони векторнинг  компонентасига тенг ва у режалар ҳақиқатдан,  бўлганлиги учун , энди
                                      
чегарани бажарилишини кўрсатамиз  .
	Иккинчи томондан, мақсад функциянинг бу режадаги қиймати 

га тенг. Лекин  эканлигидан  да  бўлишлиги келиб чиқади, яъни  функция режалар тўпламида юқоридан чегараланмаган. Шу билан теорема        тўла исботланди.
	Симплекс усулни махсус кўринишдаги жадвал орқали олиб бориш қулайлик ту\диради.	+уйидаги каноник кўринишдаги
                                                    (24)
                                                     (25)
                                                             (26)
чизиқли программалашни айни хосмас масаласи берилган бўлиб, умумийликка зараз келтирмаган ҳолда  ни  масаланинг бошлан\ич таянч режани деб олишимиз мумкин. Унга мос келган  векторлар  ўлчамли фазода базисни ташкил этади. Устунлари  базис векторлардан иборат бўлган, хосмас   матрица мос режани базис матрицаси деб аталади. Демак,

ёки
,

бу ерда   ни базис компонентларидан тузилган  ўлчамли вектор. Бошлан\ич таянч режа га мос келган жадвал кўриниши қуйидагича

   	С		c1	c2		cm				
АБ	СБ	X								
	C1		1	0		0				
	C2		0	1		0				
				:		.			.	
	Cm		0	0		1				
 zj-	cj	z(x)								

Энди ҳар бир  векторни  базислар бўйича ёйилмасини кўрайлик

ёки
                                 ,                                   (27)
бу ерда -вектор уcтун,  хосмос матрица бўлганлиги учун (27) тенгламалар системаси ҳар бир  да ягона  ечимга эга. Бу вектор устун жадвални  устунига ёзилади. Текшириш осонки ; 1-сони векторнинг -компонентаси.
	Бу ерда  белгилаш киритилган;  ларни топиш учун  вектор устуни  вектор устунга скаляр кўпайтириб, натижада  ни айириш лозим ва чиққан сонни мос равишда охирги сатрни  устунига ёзиб қўйиш керак. Кўрсатиш осонки , демак,  ни оптималлигини аниқлаш учун ларнинг ишорасини текшириш етарли экан.
	Юқорида айтилганларни қуйидаги сонли мисолда намойиш этайлик,
                     ,                             (28)
                                 ,                              (29)
                                 ,                             (30)
                                                                  (31)
бу ерда , агар (29), (30) тенгламалар системасида  деб, уни  га нисбатан ечсак   ечимни ҳосил қиламиз. Демак,  хос мос та—режа бўлиб, биринчи ва иккинчи компонента базис бўлади ва базис матрица   векторлардан   тузилган, яъни
,
(27)-формуладан фойдаланиб  векторларни аниқлаймиз:
,
.
	Юқоридаги кўрсатмага асосан  ва  ларни топайлик: 

Демак, бошлан\ич жадвални кўриниши қўйидагича бўлар экан
	C		-1	4	9		
АБ	СБ	X					
	-1	3	1	0			
	4	1	0	1	2		
zj-	cj	1	0	0	-2		
Бундан  эканлиги кели чиқади. Охирги   бўлганлиги сабабли бошлан\ич оптимал эмас,  нинг мос устун элементлари ичида мусбати бўлганлиги учун теоремага асосан бу режани яхшилаш мумкин (тў\риро\и мақсад функциянинг қийматини катталаштириш мумкин). Бу кейинги жадвалда амалга оширилади.
	Агар охирги сатрда  ларни бирортаси манфий бўлиб унга мос келган устунда мусбат элемент топилмаси, демак теорема 5 га асосан масаланинг ечими йўқ, мақсад функция юқоридан чегараланмаган бўлади. Агар устундаги элементларни камида биттаси мусбат бўлса, кейинги жадвалга ўтилиб, янги таянч режа аниқланади. Бунинг учун базислар системасидан бирор векторни алмаштириш керак бўлади. Агар  ларнинг бир нечтаси манфий қийматли  бўлса, соддалик учун уларнинг энг кичиги танлаб олинади, фараз этайлик у  бўлсин, бу элемент жойлашган устун ҳал қилувчи устун деб аталади. Сўнг унга мос келган устун  элементларидан мусбатлари танлаб олиниб уларга мос келган  ( устундаги мос элемент) нисбатлар тузилади ва улар мос равишда охирги қўшимча устунга ёзиб қўйилади. Охирги устунда минимум элемент жойлашган сатр ҳал қилувчи  сатр деб олинади, (у k-номерли бўлсин).
Ҳал қилувчи устун  билан, ҳал қилувчи сатр  кесишган жойдаги элемент - ҳал қилувчи элемент деб аталади. Шу билан бирга бундан яна шу нарса маълум бўладики, базисдаги  векторни   векторга алмаштириш керак, бу эса бошқа таянч режага ўтилганлигини ҳам билдиради, яъни   базис ўзгарувчи  га алмашади. Иккинчи жадвални АБ ва СБ 

устунидаги   ва ларни мос равишда  ва  га алмаштириб, кейин уни тўлдириш керак бўлади. 
Ҳал қилувчи сатр ва устун катакларидан бошқа барча катаклар бир ҳил қоида «тўртбурчак қоидаси» орқали тўл-дирилади. Унинг маъноси шуки, тўлдирмоқчи бўлган катак билан ҳал қилувчи элемент жойлашган катаклар тўртбурчак диогоналнинг қарама-қарши учлари ҳисобланади, яъни схематик равишда қуйидагича тўртбурчак тузилади

   xij

   xis

   xki

   xks

Бу ерда  тўлдирилиши керак бўлган катакдаги элемент қиймати  лар тўртбурчакнинг иккинчи диогонал қарама-қарши катак элементлари, -эса ҳал қилувчи элемент. Бу тўртта элемент ёрдамида схемада кўрсатилган каби пропорция тузилади ва худди  -«номаълум» элемент каби пропорциядан у топилади, яъни 

бу сон, номаълум деб аталган  сондан айрилиб, мос катакка ёзиб қўйилади. (Бу ерда шуни эътиборга олиш керакки,  деб олинган). Иккинчи жадвал қуйидагича тўлдирилади

                           (32)
Ҳал қилувчи сатрга мос катаклар эса оддий
                                                                   (33)
формула ёрдамида тўлдирилади. Ҳал қилувчи устундаги катакларни эса ҳал  қилувчи элемент жойлашган мос катакдан бошқалари ноль сони билан тўлдирилиб чиқилади, чунки  вектор базис векторлар системасига киритилган бўлиб, у ягона ёйилишга эга бўлиб қолади. Шу усул билан иккинчи жадвални барча катаклари тўлдирилади ва бу ўтиш янги таянч  режа  устунда ҳосил бўлади. Унинг оптималлигини аниқлаш учун охирги сатр элементларини ишорасига қараш керак, агар улар ичида манфийлари бўлмаса, демак топилган режа оптимал, акс ҳолда, худди аввалгидай кейинги учинчи жадвалга ўтиш керак бўлади.
	Буларни аввал кўрилган сонли мисолда намойиш этамиз. 1-жадвалдан кўриниб турибдики, бошлан\ич  режа оптимал эмас, чунки . Шунинг учун  ҳал қилувчи устун бўлади. Ҳал қилувчи сатр элементни топиш учун, ҳал қилувчи устунни мусбат элементлари ёрдамида

нисбатларни охирги устун (0-устуни)га ёзамиз ва бу устундаги энг кичик элемент - жойлашган сатр ҳал қилувчи сатр бўлади. Демак, ҳал қилувчи элемент- бўлиб, (у-1-жадвалда юлдузча билан белгиланган) бу  базис векторни  векторга алмаштириш кераклигини билдиради. Шунинг учун 2-жадвалда ,4 мос равишда ,9 га алмаштирилган.
  
    2-жадвал

	С		-1	4	9	
АБ	СБ	Х				
	-1	5/2	1	-1/2	0	
	9	1/2	0	1/2	1	
     zj-	cj	2	0	1	0	

Энди бошқа катакларни тўлдирамиз, аввал  ва  базис векторлар устунини тўлдириш мақсадга мувофиқ. Бунинг учун  сатр билан  устун кесишган катакни 1 билан, қолган устун катакларини ноль билан тўлдириш керак бўлади.
 устун худди шундай тўлдирилади. 2-жадвалдаги  сатр 1жадвалдаги ҳал қилувчи сатрга мос келади, шунинг учун бу сатр (33)-формуладан фойдаланиб тўлдирилади. Энди қолган катакларни тўлдириш учун (32) формуладан фойдаланиш керак: масалан 2-жадвалнинг   сатр ч устундаги катагини (яъни мақсад функцияни янги режадаги қийматини) тўлдириш учун,     деб (32) даги мос қийматларни қўйсак
 ни ҳосил қиламиз.
2-жадвалда  ҳосил бўлиб, уларнинг ичида манфийлари йўқ, демак топилган режа  оптимал бўлиб, бунда мақсад функция (28) нинг қиймати   га тенг экан. Шундай қилиб (28)-(31) масала ечилди.
5. Сунъий базислар усули

+уйидаги каноник кўринишдаги
                              ,                             (1)
                                                (2)
                                                      (3)
чизиқли программалаш масаласи берилган бўлсин. Маълумки, бу масалани симплекс усул билан ечиш учун бошлан\ич таянч режани аниқлаб олиш керак. Лекин  лар катта сонлар бўлса, бошлан\ич таянч режани топиш қийинчилик ту\дириши мумкин. Шунинг учун, бунда бошқача йўл тутилади. Аниқро\и, янги, ёрдамчи чизиқли программалаш масаласи шундай тузиладики, унда бошлан\ич таянч режа осонгина аниқланади. Шундан сўнг бу ёрдамчи масалага  симплекс усул қўлланиб, бошлан\ич масаланинг таянч режаси топилади ёки ечими йўқлиги аниқлаб берилади.  Тушинарликки,   деб фараз этишимиз мумкин. У ҳолда (2) тенгламалар системасининг ҳар бир тенгламаси чап томонига мос равишда  қўшилиб ёзилади ва бу янги ўзгарувчилар базис ўзгарувчилар деб қабул қилинади. Янги ҳосил бўлган тенгламалар системасини ечими сифатида    ни олиши мумкин, бу ерда нол турган компоненталар сони  та.
I.	Ёрдамчи масаланинг кўриниши қуйидагича
                                                        (4)
                                            (5)
                                                       (6) 
бўлади.
Бу масалани бошлан\ич таянч режаси  дир. Бу таянч режанинг базис матрицаси  ўлчамли бирлик матрицадир. Шунинг учун бошлан\ич жадвални тўлдириш ҳеч қандай қийинчилик ту\дирмайди. +ўшимча (4)-(6) масала ечилганда икки хол бўлиши мумкин: 
а.  функциянинг максимал қиймати нолдан фарқли .
б.  функцияни максимал қиймати нолга тенг .
	Биринчи а ҳолда  ўзгарувчиларни камида биттаси нолдан фарқли, бу эса (2) тенгламалар системаси (3)-шарт остида биргаликда эмаслигини билдиради.
	Ҳақиқатдан, агар биргаликда десак ва уни бирор жоиз ечимини  билан белгиласак  қўшимча  масаланинг таянч режаси бўлиб, бунда мақсад функция  ни қиймати нолга тенг. Бу эса фаразга қарама-қаршидир. 
	Энди б ҳолни кўрайлик, ундан келиб чиқадики агар  қўшимча (4)-(6) масаланинг оптимал режаси бўлса, . Лекин базис векторлар системасида  векторлар иштирок этиб қолиши мумкин. Агар шундай бўлса, биз бошлан\ич масала учун базис ўзгарувчилар ва базис матрицани бевосита аниқлай олмаймиз. Ёрдамчи масалани ечишдаги  охирги оптимал жадвални   устунлари жойлашган бўлаги (1)-(3) масаланинг мос қисми деб аталади. Шу мос  қисмга қараб бошлан\ич масаланинг базис матрицасини аниқлаш мумкин. Бунинг учун қуйидаги икки вазиятни кўриш керак. 
1. +ўшимча  базис векторлар  жойлашган сатрларда нолдан фарқли элемент йўқ. Бу дегани барча  векторлар базис векторларнинг чизиқли комбинациясида қўшимча векторлар олдидаги коэффициентлари нольга тенг. Яъни, аслида базис векторлар сони дан кичик бўлиб, (2)-тенгламалар системасига мос  кенгайтирилган матрицани ранги дан кичик, бу дегани тенгламалар чизиқли бо\лиқ ва айрим тенгламаларни ташлаб юбориш мумкин. Демак, бу вазиятда базис ўзгарувчилар сони ҳам, базис векторлар сони ҳам дан кам бўлар экан.
2. +ўшимча  базис векторлар  жойлашган сатрларда камида биттасида нольдан фарқли элемент бор. У ҳолда, бу нолдан фарқли элемент янги жадвалга ўтишда ҳал қилувчи элемент ролини ўйнайди ва албатта, кейинги жадвалда базис векторлар ичида  векторлар биттага камаяди. Шундан сўнг, яъни биринчи вазиятга келамиз, ёки яна кейинги жадвалга ўтиш билан  базис векторларда  векторлар қатнашишини биттага камайтирамиз.
	Иккала вазиятда қўшимча (4)-(6) масалага мос келган  оптимал режанинг биринчи  та компонентаси кейинги ўтишларда ўзгармай қолади. Бу охирги оптимал жадвалда ноллардан иборат бўлган сатрларни ташлаб юбориш орқали, биз бошлан\ич (1)-(3) масала учун биринчи жадвал тузган бўламиз, яъни ҳисоб-китобларни шу жадвалдан бошлаб давом эттириш мумкин.
II. Бу пунктда кўриладиган усул, айрим адабиётларда -М-усул еб аталган. Бу усулда ёрдамчи масала қуйидагича тузилади 
                     ,                (19)
                                          (20)
                      ,               (21)
бу ерда М етарлича катта мусбат сон деб фараз қилинади. (Ҳисоблаш давомида унинг қиймати иштирок этмайди). Бу усулнинг I пунктда кўрилган усулдан афзаллиги шуки: асосий ёрдамчи масалани ечиб бошлан\ич режани топиш ва кейин асосий масалани ечишга бўлинмасдан, бирдан ёрдамчи масала ҳам, асосий масала ҳам ечилади. Лекин М-параметрни коэффициентлари учун қўшимча яна бир сатр қўшилади, бу эса ҳисоблаш жараёнига озгина бўлса ҳам қийинчилик ту\диради.
	Ёрдамчи масала (19)-(21) дан кўриниб турибдики, уни бошлан\ич режасини топиш ҳеч қандай қийинчилик ту\дирмайди.

Ёрдамчи (19)-(21) масала симплекс усул билан ечилганда учта ҳол бўлиши мумкин.
а. (19)-(21) масаланинг ечими йўқ, унда асосий (1)-(3) масала ҳам ечимга эга эмас (яъни, ё жоиз режалар тўплами бўш, ёки мақсад функция юқоридан чегараланмаган);
б. (19)-(21) масала  оптимал режага эга, лекин бу режанинг  компоненталарини камида биттаси нолдан фарқли, унда асосий (1)-(3) масаланинг шартлари (2), (3) лар биргаликда эмас (жоиз режалар тўплами бўш):
с. (19)-(21) масала оптимал режага эга ва барча  бунда  асосий масаланинг оптимал ечими бўлади. 
	Маълумки,  сонларни аниқлашда мақсад функцияни ташкил этган ўзгарувчилар олдидаги коэффициентлар ҳам иштирок этади. Шунинг учун ёрдамчи (19)-(21) масала ечилаётганда  ларни аниқлашда М параметр ҳам иштирок этади. Шунга кўра  ларни қуйидагича ёзамиз: 
                           ,             (22)
яъни -М  параметр коэффициенти,   озод ҳад коэффициенти оптималлик шартига асосан - бўлиши керак, лекин (22) дан келиб чиқадики  ни ишораси  ни ишораси билан бир хил (чунки   етарлича катта мусбат сон), агар  бўлиб қолса  бўлади. Шунинг учун аввал  ларни ишорасини номанфий қилишга интилиш керак ва шу мақсадда симплекс жадвалда яна  бир сатр  лар учун ажратилади. Жадвал  устидаги ҳисоб-китоблар аввалга қоида «тўрт бурчак» усули  билан олиб борилади.
Энди а ҳолдаги тасдиқни исботлайлик. Ёрдамчи (19)-(21) масала ечимга эга бўлмасин, яъни шундай   номер борки, 
  ва 
тенгсизликлар ўринли бўлсин. Кўрсатамизки,  бўла олмайди. Ҳақиқатдан, агар  бўлса, , бу ерда -базис ўзгарувчиларни мақсад функция (19) даги коэффициентлари. Агар базис ўзгарувчилар таркибида сунъий базислар ҳам бўлса, мос  коэффициент М га тенг. Демак,  , чунки , М эса етарлича катта мусбат сон. Бу эса  га қарама-қарши. Демак,  бўлиши керак экан. Бунда, тушунарликки, агар базисда бирор сунъий базис вектор иштирок этса, у жойлашган мос сатрда  бўлади. Фараз этайлик, асосий масала (1)-(3) нинг жоиз режалар тўплами бўш бўлмасин ва  (1)-(3) масаланинг жоиз режаси бўлсин. +уйидагича янги жоиз режа  ни ихтиёрий  параметр учун тузамиз.
,
, агар  базис вектор бўлса, акс ҳолда  бу режанинг жоизлиги қуйидаги муносабатлардан келиб чиқади:

,
чунки -жоиз режа бўлганлиги учун биринчи йи\инди  га тенг. +авс ичидаги ифода нолга тенг, чунки . Юқоридаги таъкидга асосан сунъий базис бу ёйилмада ноль коэффициент билан иштирок этади.
Энди  жоиз режада мақсад функциянинг қийматини топайлик 

,
агар , чунки .
Шундай  қилиб, асосий  масаланинг мақсад функцияси ҳам юқоридан чегараланмаган экан. Яна шундай вазият бўлиши мумкинки, бунда ёрдамчи масаланинг мақсад функцияси юқоридан чегараланмаган, лекин бошлан\ич масалада жоиз режалар тўплами бўш.

6. Иккиламчи масала назарияси

Берилган  чизиқли программалаш масаласи билан бирга, яна бошқа масалани (бу ҳам чизиқли программалаш масаласи) бирга кўриш масалани ечиш нуқтаи-назаридан қулайлик ту\дириши мумкин. Биринчи масала тў\ри масала, иккинчиси эса биричисига нисбатан иккиламчи ёки  қўшма деб  аталади. Улар биргаликда иккиламчи жуфтликни ташкил этишиб, ечимлари ўртасида  ўзаро бо\лиқлик мавжуддир.
	+уйида турли кўринишда бўлган иккиламчи жуфт масалалар келтирилган, 

Тў\ри масала:                   Иккиламчи масала:

1. 

2.                 

3. 

4. 

	Агар, тў\ри масала каноник кўринишидан фарқли бўлса, уни мос ҳолга келтириб, кейин унинг иккиламчи масаласини тузиш керак. 
1 ва 2- пунктдаги масалалар симметрик бўлмаган, 3 ва 4-пунктдагилар эса симметрик масалалар деб аталади. (Ҳақиқатан, улар мос равишда ўзаро иккиламчидир).
	Умумийликка зарар келтирмаган ҳолда келтириладиган лемма ва тероремалар фқат қуйидаги икки кўринишдаги иккиламчи жуфт масалаларга тегишлидир
Тў\ри масала I:               Икккиламчи масала II:     
    
Тў\ри масала III:             Иккиламчи масала IV:

Лемма 1. (I)-(III)  масаланинг ихтиёрий жоиз  режасида мақсад функциясининг қиймати (II), (IV) масаланинг функциясини қийматидан катта бўлиб кетмайди, яъни . Агар бирор  мос жоиз режаларда  тенглик, ўринли бўлса,  I, III масалаларнинг,  III, IV  масалаларнинг оптимал режалари бўлади.
Теорема 1. (Иккиламчиликнинг 1-теоремаси)
	Агар I (III) ёки  II (IV) масалаларнинг бирортаси ечимга эга бўлса, қолган иккинчиси ҳам ечимга эга, ҳамда мақсад функцияларининг экстремал қийматлари устма-уст тушади.
	Агар I (III) ва  II (IV) масалаларнинг бирортасини мақсад функциялари мос равишда юқоридан ёки қуйидан чегараланмаган бўлса қолган иккилмачи масаланинг жоиз режалар тўплами бўшдир.
Теорема 2. (Иккиламчиликнинг 2-теоремаси). 
	I (III) ва II (IV) масалаларни мос равишда  жоиз режалари, мос масалаларнинг оптимал режалари бўлиши учун
                                          (16)
тенгликларни бажарилиши зарур ва етарлидир.
	Иккиламчи масалаларнинг иқтисодий талқинига тўхталиб ўтайлик. Биринчи теореманинг биринчи қисмига асосан маҳсулот ишлаб чиқаришнинг оптимал режаси мавжуд бўлишлиги учун ҳар бир хом-ашёнинг нархини ўрнатиш мумкин бўлишлиги зарур ва етарлидир. Лекин, умуман олганда маҳсулот ишлаб чиқаришни оптимал режалари ҳам, хом-ашё нархлари ҳам бир қийматли аниқланмаган бўлади. Бу теореманинг  2-қисмига кўра оптимал режа асосида ишлаб чиқарилган маҳсулотларнинг умумий баҳоси иккиламчи масаланинг ечимига мос келган нарх бўйича сотиб олинган мавжуд хом-ашёлар харажатига тенг бўлиши керак. Агар, маҳсулот ишлаб чиқаришга оптимал режа қўлланилмаса ишлаб чиқилган маҳсулотлар баҳоси мавжуд хом-ашёларнинг  нарихидан кичик бўлади, бу эса режани рентабел эмаслигини билдиради, яъни маҳсулот ишлаб чиқариш зиён бўлади. Худди шундай, агар хом ашёлар нархи шундай танлаб олинсаки,  натижада мавжуд хом-ашёларнинг умумий нархи минимал бўлмаса, у ҳолда, ихтиёрий (шу жумладан оптимал) ишлаб чиқариш режада ишлаб чиқарилган маҳсулотлар баҳолари кетган харажатдан кам бўлади. Бу эса, албатта мақсадга мувофиқ эмас. Энди иккинчи жараённинг иқтисодий маъносини текширамиз.
	Агар I ва II иккиламчи жуфт масалалар кўрилаётган бўлса, теоремага асосан, бирор хом-ашё оптимал режа бўйича ишлатилиши учун унга сарфланган ҳаражат билан ишлаб чиқарилган маҳсулот баҳоси бир хил бўлиши зарур ва етарли. Бу мантиққа ҳам мос тушади-бирор хом-ашё ишлатиш чиқими, агар киримидан ошиб кетса, бундай хом-ашёни ишлатиш зарардир. Энди III ва  IV масалаларни кўрайлик.
	Агар бирор хом-ашё тўла фойдаланилмаган бўлса, уни нархи нолга тенг, ва аксинча, бирор хом-ашё нархи нол бўлса, шундай оптимал ишлаб чиқариш режаси борки, унда бу хом-ашё тўла фойдаланилмайди.
Ҳақиқатдан агар бирор хом-ашёни мавжуд миқдори сарфланган миқдоридан кўп бўлса, бундай хом-ашё қийматга эга эмас, чунки уни умумий миқдорини маълум бир қисмигача камайтириш билан умумий баҳо (мақсад функция қиймати) ўзгармайди. 
Лекин, маълум бир миқдорга етиб келганда у қийматга эга бўлиб қолади, чунки унинг миқдорини яна камайтириш ишлаб чиқарилган маҳсулотларнинг умумий баҳосини камайишига олиб келади. Демак, хулоса қилиб айтиладиган бўлса, бирор  хом-ашё мусбат қийматга эга бўлишлиги учун уни мавжуд миқдори маҳсулот ишлаб чиқаришга тўла сарфланиши керак экан.

IV боб

Чизиқли программалашнинг умумий ва асосий масалалари

+уйидаги

кўринишидаги масала чизиқли программалашнинг умумий масаласи деб аталади. Бу  ерда  лар ихтиёрий ўзгармас хақиқий сонлардир ва функция, масалаларининг мақсад функцияси; (2)-(4) лар чегаралари деб аталади. 
Таъриф 1. Агар (1)-(4) масалада  ва   бўлса, масала стандарт ёки симметрик кўринишда берилган бўлади. 
Таъриф 2. Агар (1)-(4) масалада   ва   бўлса, масала кононик ёки асосий кўринишда берилган дейилади.
Таъриф 3. (2)-(4) шартларни қаноатлантирувчи ихтиёрий  вектор (1)-(4) масаланинг жоиз режаси деб аталади.
Таъриф 4. Агар  (1)-(4) масаланинг   жоиз режаси (1)-мақсад функцияга жоиз режага тўпламдаги қийматларига нисбатан энг катта эга қиймат берса, у масаланинг ечими ёки оптимал режаси деб аталади. 
Демак,  - оптимал режа, агар  барча  жоиз режалар учун бажарилса, бу ерда билан (1) мақсад функциянинг жоиз режадаги қиймати белгиланган. 
Бу ерда, шуни таъкидлаб ўтиш керакки, умумий кўринишдаги (1)-(4) масалани ҳар вақт каноник кўринишга келтириш мумкин ва бу масаланинг ечимидан бошлан\ич масала ечимини (агар ечими мавжуд бўлса) аниқлаш мумкин. Бунинг учун қуйидагилар амалга оширилади: 
а) манфий эмаслик талаби йўқ бўлган ўзгарувчилар  лар икки манфий бўлмаган ўзгарувчиларни айирмасига алмаштирилади, яъни . Шундан, сўнг барча ўзгарувчиларга манфиймаслик шарти қўйилган бўлади;
б. (2)-тенгсизликлар системасини тенглик ҳолга ўтказиш учун қўшимча  та   манфий бўлмаган ўзгарувчилар киритилади. Яъни, улар мос равишда (2)-тенгсизликларни чап томонига қўшилиб, тенгсизлик белгиси тенгликка алмаштирилади.
Шундан сўнг (1)-(4) масала каноник ёки асосий масала бўлиб қолади. Шунинг учун, бундан кейин биз, умумийликка зарар келтирмаган ҳолда, масала каноник ҳолда берилган деб оламиз (бундан  мустасно, чунки бу  ҳол алоҳида ўрганилади). Яна шуни қўшимча қиламизки, агар (1)-мақсад  функция максимум ўрнига минимумга текширилаётган бўлса, уни , яъни ишорасини ўзгартириб, максимумга текшириш, кейин топилган максимум қийматини тескари ишора билан олиб бошлан\ич минимумга текшириш масаласидаги мақсад функциянинг энг кичик қийматини аниқлаш мумкин.

V-боб

+авариқ программалаштириш

1. +авариқ программалаштириш деб математиканинг чекли ўлчовли  фазонинг қавариқ Х тўпламида қавариқ функциянинг минимумини топиш ҳақидаги
,                            (1)
масалаларни ўрганадиган бўлимига айтилади. +авариқ программалаштириш чизиқли программалаштиришнинг бевосита умумлашмасидан иборат бўлиб, унинг вужудига келиши ва ривожланишига чизиқли программалаштиришнинг усул ва \оялари катта таъсир кўрсатди. +авариқ программалаштириш масалаларини текшириш қавариқ функциялар ва қавариқ тўпламларнинг хоссалари батафсил ўрганиладиган қавариқ анализнинг яратилишига олиб келди. 
	+авариқ программалаштиришнинг асосий масаласи бўлган (1) ни ифодалашда Х тўпламни   кўринишида бериш қабул қилинган бўлиб, бу ерда Q тўплам, m-вектор функция  нинг компонентлари қавариқ функциялардан иборатдир.
2. Агар Rn дан олинган Х тўплам ўзининг ихтиёрий иккита нуқтаси билан бирга уларни туташтирувчи кесмани ҳам ўз ичига олса (1-расм), бундай тўплам қавариқ дейилади.

Бош=ача =илиб айтганда, агар  былса, барча  лар учун   былади

                               1-расм

+авариқ тўпламларга  фазо ва 2-расмда  кўрсатилган тўпламлар мисол бўла олади.

                                2-расим

3-расмда қавариқ бўлмаган тўпламларга  мисоллар келтирилган

                                3-расм

	Агар ихтиёрий  ва барча   лар учун 
 тенгсизлик бажарилса, қавариқ Х тўпламда  аниқланган ва чекли бўлган  функция қавариқ дейилади (4-расм).

4-расм

Масалан, силлиқ бўлмаган  функция қавариқдир, чунки барча  лар учун  тенгсизлик ўринли.
	+авариқ функциянинг таърифи сифатида  қуйидаги   аломатни олиш  мумкин:  Х тўпламда  функциянинг қавариқ бўлиши учун унинг уст графиги (5-расм)   қавариқ тўплам бўлиши зарур ва етарлидир (бу ерда ).

+уйидаги соддаро= таърифлардан щам фойдаланиш мумкин.
	Агар ихтиёрий  учун скаляр  аргументли  функция =авари= былса ва фа=ат шунда   скаляр функция =авари= былади.

                 5-расм
Силлиқ  функциялар учун  тенгсизлик бажарилса ва фақат шунда  қавариқ бўлади.
3. +авариқ тўпламларнинг хоссалари. Ихтиёрий сондаги қавариқ тўпламларнинг  кесишмаси қавариқ тўпламдир. Уларнинг тўплам маъносидаги йи\индиси эса қавариқ бўлиши шарт эмас (6-расм).

 
             6-расм                                                7-расм

+авариқ тўпламларнинг ихтиёрий   элементларининг қавариқ комбинацияси  шу тўпламга тегишли бўлади. Фараз қилайлик  X, Y-қавариқ тўпламлар бўлиб улардан бири чегараланган бўлсин. Агар уларнинг ёпилмалари   ўзаро кесишмаса қаттий ажралувчан (7-расм) бўлади, яъни қандайдир n-вектор   ва  сони учун барча  ва  лар  тенгсизликларни қаноатлантиришади ( ажратувчи текислик).
	Агар  қавариқ Х тўпламнинг чегаравий нуқтаси бўлса, бу нуқ-тада Х тўпламга  таянч текислик мавжуд бўлади, яъни қандайдир

  да барча  лар  учун  тенгсизлик бажарилади.

          8-расм

4. +авариқ функцияларнинг хоссалари. +авариқ  функциянинг сатҳ тўплами ёки  бўш, ёки қавариқ тўплам бўлади.
Агар  қавариқ функциялар бўлса,  ва   функциялар ҳам қавариқ бўлади.
+авариқ   функция ҳар бир  нуқтада узлуксиздир.  ( Агар  қавариқ функция бўлиб,  бўлса,   фақат Х нинг ички нуқтасида узлуксиз  бўлади деб айта оламиз; Х нинг чегаравий нуқталарида  узилишга эга бўлиши мумкин. Мисол:  ва  ).
+авариқ функция   ҳар бир  нуқтада ихтиёрий  йўналиш  бўйича ҳосилага эга:

Масалан,  
Агар ихтиёрий   ларда  нуқта Х тўпламнинг (нисбатан) ички нуқтаси бўлса, Х тўплам  қаътий қавариқ тўплам дейилади. Масалан, доира қаътий, квадрат эса қаътий қовариқ бўлмаган тўпламлардир.
5. Кун-Таккер теоремаси. +авариқ программалашда асосий масала деб, Q-қавариқ тўплам,  ва m-вектор функция   нинг  компонентлари  қавариқ функциялар бўлганда, қуйидаги
                          (22)
масалага айтилади.
(22)-масаланинг  шартларини қаноатлантирувчи ҳар бир n-вектор режа деб аталади, (22)-масаланинг ечими эса оптимал режа дейилади.
+авариқ тўпламлар ва функцияларнинг  хоссаларига асосан режалар тўплами

ва оптимал режалар тўплами
  барча   лар учун 
қавариқ бўлади.
Демак, (22)-масалада иккита оптимал  режа мавжуд бўлса, уларни туташтирувчи кесманинг ихтиёрий нуқтаси ҳам оптимал режадир, яъни бу ҳолда оптимал режалар чексиз  кўп бўлади.
Агар мақсад функция  қаътий қавариқ бўлса, оптимал режа ягона бўлади. (22)-масаланинг  ва  элементлари бўйича
                 (23)
Лагранж функциясини тузамиз.
Агар бирор  жуфтлик мавжуд бўлиб, барча  лар учун
                 (24)
тенгсизликлар бажарилса, Лагранж функцияси  F ((23)) эгар нуқтага эга дейилади,    эса унинг эгар нуқтаси деб аталади.
Теорема 1 [8] Агар   Лагранж функциясининг эгар нуқтаси бўлса,  нуқта (22)-масаланинг ечими бўлади ва
                                 (25)
шарт бажарилади.
Бу теоремага асосан (22) масаланинг ечимини топиш учун Лагранж функцияси / нинг эгар нуқтасини топиш керак экан. Равшанки, ихтиёрий F функция учун эгар нуқта  бўлиши шарт эмас.
Силлиқ масалалар учун Лагранжни функцияси эгар нуқтасининг  мавжудлик теоремаларига эквивалент бўлган натижалар Г Кун ва А. Таккер томонидан олинган.
б. Силлиқ масалалар. +авариқ программалашнинг силлиқ масаласини, яъни  ва  функциялар силлиқ, қавариқ ҳамда Q тўплам
                                    (26)
кўринишга эга бўлган (22)-масалани қараймиз.
Агар бирор  режа учун
                                        (27)

тенгсизлик бажарилса, қавариқ программалаш асосий масаласининг режалар тўплами равон (ёки Слейтер шартини қаноатлантиради) дейилади.
Теорема 2 [8]. Режалар тўплами  равон бўлган силлиқ масаланинг  режаси оптимал бўлиши учун шундай манфий бўлмаган m-вектор   ва n-вектор  мавжуд бўлиши зарурки, улар учун қуйидаги шартлар бажарилади:
1. Стационарлик шарти

                 28)

2.                                   (29)

Лагранж функцияси F нинг тузилишига асосан (28)-шарт қуйидаги
                               (30)
шаклда ёзилиши мумкин.
Теорема 3 (Кун-Таккер теоремаси). Режалар тўплами равон бўлган қавариқ программалашнинг асосий  масаласини  оптимал режаси мавжуд бўлиши учун шундай  вектор мавжуд бўлиб,  жуфтлик Лагранж функциясининг эгар нуқтаси бўлиши зарур ва  етарлидир. Шу билан бирга

шарти ҳам бажарилади.
 +уйидаги
                         (11)
чизиқли шартлар билан берилган (худди чизиқли программалаш-тиришдагидек) масалани кўрайлик. 
Бу ерда  матрица,  вектор. (31)-масалага Кун-Таккер теоремасини қўллаш мумкин [8].

VI-боб

Чизиқсиз программалаштириш.

1. Чизиқсиз программалаштириш деб чекли ўлчовли фазо тўпламида функцияларнинг оптималлаштириш масаласи ўрганиладиган бўлимга айтилади. Мазкур қисмда чизиқсиз программалаштиришнинг назарияси баён қилинади.
	Чизиқсиз программалаштириш масаласида умумий қоида ўта содда кўринишга эга бўлишлигига қарамасдан унга доир тўлиқ натижалар маълум эмас. Мавжудлик теоремалари масаланинг элементларидан маълум аниқ хоссаларга эга бўлиш талаб қилади. Шу сабабли  чизиқсиз программалаштиришнинг умумий масаласи фақат аниқ масалалар кўринишда  текширилади.
2. Ечимнинг мавжудлиги. Х n-ўлчовли   фазодан олинган тўплам бўлсин. Бу тўпламнинг элементларини одатдагидек режалар деб атаймиз. Х тўпламда мақсад функцияси деб аталувчи  функция аниқланган бўлсин. Чизиқсиз программалаштиришнинг умумий масаласи , (1) яъни Х режалар тўпламида  мақсад функциясини минималлаштиришдан иборатдир. (1)-масаланинг  ечими:

оптимал режа деб аталади.
	Ҳар қандай (1)-кўринишдаги масала  ечимга эга бўлавермайди.
	(1)-масаланинг ечимлари мавжудлиги ҳақидаги теоремаларни ифодалаш учун қуйидан ярим узлуксиз функциялардан фойдаланилади.
Агар Х да аниқланган  функция учун қуйидаги шарт
  
бажарилса, бу функция  да  қуйидан ярим узлуксиз дейилади. Агар  функция Х нинг ҳар бир нуқтасида қуйидан ярим узлуксиз бўлса, у Х тўпламда қуйидан ярим узлуксиз функциялар дейилади.
                                                                     (2)
тўплам  нинг (с қийматли) сатҳ тўплами дейилади
	 да аниқланган  нинг сатҳ тўплами  бўш ва ёки ёпиқ  тўплам бўлганда ва фақат шунда бу функция қуйидаги ярим узлуксиз бўлади.  тўплам минимал сатҳ тўплами дейилади.
Теорема 1. (чизиқсиз программалаштириш масаласи ечимларининг мавжудлик аломати). (1)-масаланинг ечими мавжуд бўлиши учун бирор  да  мақсад функциянинг сатҳ тўплами минимал сатҳ тўпламдан ёки бўш  бўлмаган  компактдан (унда  қуйидан ярим узлуксиз) иборат бўлиши  зарур ва етарлидир.
	Кўпинча (2)-тўпламнинг компактлигини текшириш учун қуйидаги фактдан фойдаланилади:  қуйидаги ярим узлуксиз бўлган                                             
                                 да ,                            (3)
функциянинг сатҳ тўплами ихтиёрий  с  учун компакт.
	Хусусан, кучли қавариқ функциялар (3)-шартни қаноатлантиради. Мазкур қисмда (1)-масаланинг тўртта асосий тури ўрганилади:   1.   бўлган шартсиз минимум масаласи;  
2. вектор-функция бўлган шартли масаласи;  3.   шартлар билан  берилган тенгсизликлар типидаги:  4. -вектор функция бўлган,  векторли оптималлаштириш масаласи. 
Чизиқсиз  программалаштиришнинг  дискрет масалалари ва юқорида келтирилган  4.-масалани  ўрганмаймиз.
Шартсиз минимум масаласи. Ушбу 

                                                       (4)   

шартсиз минимум масаласини   функция ҳар бир  нуқтада  ўзгарувчилар  бўйига барча хусусий хосилалари билан бирга узлуксиз, яъни  бўлган ҳолда қараймиз.
	Агар  бўлса,  нуқта оптимал режа ( (1)-масаланинг ечими, абсалют ёки глобал минимум нуқтаси)деб аталади. Бирор  учун  муносабатлар бажарилса,  режа локал оптимал режа (нисбий ёки локал минимум нуқтаси) дейилади.
	Равшанки, ҳар бир оптимал режа локал оптимал режа ҳамдир лекин, аксинча тасдиқ ўринли эмас.
	Теорема 2. Ҳар бир локал оптимал режа  да стационарлик шарти 
                                                                   (5)
яъни  бажарилади.
	Ушбу 
                                                                    (6)
тенгламанинг ечимлари  нинг стационар нуқталари дейилади.
Равшанки (теорема 2), оптимал режалар (агар улар мавжуд бўлса) мақсад  функциянинг  стационар нуқталар орасида ётади.
Энди  бўлсин.
Теорема 2. Ҳар  бир  оптимал режада иккинчи тартибли ҳосилалардан тузилган матрица «манфий» бўлмайди:
                                                                   (7)
Теорема 4. Агар  стационар нуқтада 

                                                                  (8)
бўлса, бу  нуқта локал оптимал режа бўлади. 
	Агар  бўлса, 2,3-теоремалар самарали умумлашмага эга (математик анализ курсини қаранг).
3. Шартли минимум масаласи.    Ушбу 
                                                                 (9)
шартли минимум масаласини унинг элементлари  ва   ларнинг  га тегишли бўлган ҳолда қараймиз.
	Агар  режа  муносабатларни қаноатлантирса, у (глобал) оптимал режа дейилади. Агар, бирор    учун  режа  шартларни қаноатлантирса, у нисбий оптимал режа деб аталади. 
	Энди (9)-масаланинг элементларидан фойдаланиб,  ўлчовли вектор (Лагранж вектори) скаляр,  ёрдамида
                              (10) 
умумлашган Лагранж функциясини тузамиз.
	Теорема 5. Агар  оптимал режа бўлса, шундай ноль бўлмаган Лагранж вектори  мавжудки, унинг учун 
                                                                    (11)
бўлади, яъни (10)-умумлашган Лагранж функцияси учун  бўлганда,  режа стационар нуқта бўлади.
Шартли минимум масалаларининг текширишда (10)-дан бўлганда ҳосил бўладиган
                                                          12)
(одатдаги классик) Лагранж функциясидан фойдаланилади. Юқоридаги теорема киритилган (12) Лагранж функцияси учун, умуман олганда, ўринли эмас. (Мисол. ).
Энди (9)-масалани текширишда Лагранж функциясидан фойдаланиш мумкинлиги билан шу\улланамиз.
	Агар  режага мос келган умумлашган  Лагранж векторлари ичида  кабилари бўлмаса, (9)-масала ва  оптимал режа нормал деб аталади. 
Агар  режада 
         	              (13)
векторлар чизиқли эркли бўлса,   оддий режа деб аталади. 
Теорема 6. Агар (19)-масаланинг  оптимал режасида (13) векторлар чизиқли эркли бўлса, шундай Лагранж вектори  топиладики,  жуфтликда
                                               (14)
тенгликлар (стационарлик шартлари) бажарилади.
4. Шартлари  тенгсизликлар типида бўлган ҳолда функцияларни минималлаштириш.  Биз қуйида  деб фараз қиламиз ва 
                                                                   (15)
масалани кўрамиз. Агар  режа учун  бўлса,  (глобал, абсолют) оптимал режа деб аталади. Агар  режада қандайдир  учун  шартлар бажарилса,  нисбий оптимал режа дейилади.
	Агар  бўлса  шарт  режада актив (пассив) деб аталади. Актив шартлар индекслари тўпламини  орқали белгилайлик.
	Теорема 7. Агар  режа (15)-масаланинг локал  оптимал режаси бўлса, қуйидаги  тенгсизликлар системаси биргаликда бўлмайди.
	Теорема 8. (умумлашган Лагранж кўпайтувчилари қоидаси). (15)-масаланинг ҳар бир  локал оптимал режаси учун шундай ноль бўлмаган умумлашган  Лагранж вектори  мос келадики, қуйидаги шартлар бажарилади:
1. манфиймаслик:  
2. стационарлик:   
3. 

Агар
                                                       (16)
векторлар чизиқли эркли бўлса,  режа оддий режа деб аталади.
	Равшанки, агар  оддий режа бўлса, у ҳолда , бўлади 
	Агар  бўлганда   бўлса, ва  бўлганда  ихтиёрий n-вектор бўлса,  векторни  нуқтада тенгсизлик типидаги    шарт бўйича ички йўналиш деб атаймиз.
	 векторни   режада  (9)-масаланинг шартлари бўйича ички йўналиш дейилади, агар у  нуқтада ички йўналиш бўлса. Шундай қилиб,  режада (9)-масаланинг шартлари бўйича ички йўналишлар  тегсизликлар орқали ифодаланади, агар уларда  векторни  га алмаштирилса. Агар  оддий  режа бўлса, улар ҳамиша мавжуд бўлади.
Теорема 9. (одатдаги (классик) Лагранж кўпайтувчилари қоидаси). (9)-масаланинг ҳар бир оддий локал оптимал режаси учун шундай ягона Лагранж  вектори топиладики, унда қуйидаги шартлар бажарилади:
1. Манфиймаслик:    
2. Стационарлик:      
3.  
	 оптимал режага мос  векторнинг  ягоналиги режанинг оддийлиги натижасидир.
5. Минимумнинг иккинчи тартибли етарли шарти. (9)-масалани қараймиз, ва    деб оламиз.
9-теоремага асосан (9)-масаланинг оддий оптимал режаси  га ягона  Лагранж вектори мос келади. 
	Агар  бўлса,  режада актив бўлган  шарт қаттиқ (юмшоқ) дейилади.  режада қаттиқ (юмшоқ) шартларнинг индекслар тўпламини

орқали белгилаймиз
Теорема 10.  Фараз қилайлик,  режа (9)-масаланинг оддий оптимал режаси, -унга мос Лагранж вектори бўлсин. У ҳолда 
           (17)
системани қаноатлантирувчи  векторлар тўпламида қуйидаги  квадратик шакл манфий бўлмайди:
        
6. Локал оптималлашнинг етарли шарти. Фараз қилайлик, (9)-асалада  бўлсин.
	Агар  режа учун шундай  m-вектор топилиб,  муносабатлар бажарилса, -шартли-стационар режа дейилади.
Теорема 11.  шартли-стационар режанинг локал оптимал бўлиши учун 
                                                               (18)
тенгсизликнинг 

системани қаноатлантирувчи барча   векторда бажарилиши етарлидир.
7. Силлиқ бўлмаган масалалар. Кейинги йилларда чизиқсиз программалашда амалиёт талаблари асосида силлиқ бўлмаган оптималлаштириш масалалари назарияси ривожлана бошлади.
	Агар 
                      (19)
чекли лимит мавжуд бўлса,  функция  нуқтада  йўналиш бўйича  ҳосилага эга дейилади.
	Агар  функция х нуқтанинг атрофида Липҳиц шартини қаноатлантирса,   нинг функцияси узлуксиз ҳамда Липҳиц шартини қаноатлантиради.
	Энди ушбу минимум масаласини кўрайлик:
                                                              (20)
бу ерда   ни  атрофида йўналишлар бўйича дифференциалланувчи деб ҳисоблаймиз.
Теорема 12.  режанинг оптимал бўлиши учун 
 
тенгсизликнинг бажарилиши зарур,  қавариқ бўлганда эса, етарли ҳамдир.
Теорема 13. Фараз қилайлик,  функция  нуқтанинг атрофида Липҳиц шартини қаноатлантирсин. Агар

бўлса, -локал оптимал режадир.
8. Энди умумийроқ бўлган
                                             (21)
масалани қараймиз.  режа (21)-нинг ечими бўлсин.
	Бунда  ва  ларни  нуқтада барча йўналишлар бўйича дифференциалланувчи деб ҳисоблаймиз.
 да актив шартларни қаноатлантирувчи индекслар тўпламини  деб белгилаймиз. Агар  бўлса,  вектор  шарт  бўйича муносиб йўналиш деб аталади. (21)-масаланинг  да барча шартлари бўйича муносиб йўналишлари тўпламини  деб белгилаймиз. 
Теорема 14. Фараз қилайлик,  бўлсин.  режа оптимал бўлиши учун  шартли бажа-рилиши зарур:  лар қавариқ бўлганда етарли ҳамдир.

VII-БОБ

Транспорт масаласи
	
Халқ хўжалигининг кўп масалаларини транспорт масаласига келтириш мумкин. Бу эса қўйилган масалани математик, қолаверса иқтисодий томондан тўла ечишга имкон беради, яъни оптимал режа ва ундан келадиган самарадорлик кўрсатиб берилади. Транспорт масаласи умуман олганда чизиқли программалаш масаласи бўлиб, айрим махсусликлари ҳисобга олинган ҳолда, уни ечиш учун бошқа қулай усуллар топилган.
	Потенциаллар усули, дифференциалланган рента усули, дельта-усул ва бошқалар шулар жумласидандир. Албатта, барча усулларда ҳам бошлан\ич режани танлаб олиш муҳим роль ўйнайди, чунки, агар у оптимал режага яқинроқ қилиб олинадиган бўлса, кейинги ҳисоблар камроқ бажарилади. Шунинг учун, бошлан\ич режани аниқлаш ҳам алоҳида масала деб қаралиши мумкин. Уни ечиш учун бир қанча усуллар таклиф этилган, булар: шимолий-\арб бурчак усули, минимал баҳоли усули, икки ҳисса афзалроқ усули ва бошқалар.
Транспорт масаласининг умумий қўйилиши қуйидагича:
 бир хил турдаги маҳсулот билан савдо қилувчи таъминот пунктлари бўлиб, -пунктдаги маҳсулот миқдори  бирликка тенг бўлсин. Шу маҳсулотларни  истеъмол пунктларига тўла тарқатиш талаб қилинсин. Бунда -истеъмол пунктига олиб келиниши керак бўлган маҳсулот миқдори  бирликка тенг бўлсин. 
	-таъминотчидан  -истеъмолчига бирлик маҳсулотни олиб келиш ҳаражати  сўмга тенг бўлсин. Таъминот пунктдаги маҳсулотларни  истеъмолчиларга энг кам ҳаражат билан тўла ташиб кетилиши талаб этилсин. У ҳолда -билан -таъминотчидан -истеъмолчига  ташиб кетилиши мўлжалланган маҳсулот миқдори белгиланиб, масаланинг математик модели тузилади, яъни:
                                              (1)
                                       (2)
                                       (3)
.                             (4)
Бу ерда (2)-ҳар бир таъминотчидан олиб кетиладиган маҳсулот миқдорига, (3)-эса ҳар бир истеъмолчига олиб келинадиган маҳсулот миқдорига бўлган чегарани билдиради, (1)- мақсад функцияни ҳаражат минимум қилиш кераклигини билдиради.
Таъриф. Агар   тенглик бажарилса, мос транспорт масаласи ёпиқ, акс ҳолда очиқ масала деб аталади.
	Теорема. Ихтиёрий ёпиқ транспорт масаласи ечимга эга.
Исбот. Теорема шартига кўра
 . У ҳолда ,  режа бўлади, ҳақиқатан, 
, .
Кўрсатамизки, (2), (3), (4) режалар тўпламида  - чизиқли мақсад функция чегараланган. +уйидаги белгилашларни киритайлик:
, у ҳолда бир томондан  , иккинчи томондан  , демак, . Шундай қилиб, бўш бўлмаган режалар тўпламида мақсад функция чегараланган экан, бундан келиб чиқадики, масала ечимга эга. Теорема исбот бўлди.
	Очиқ транспорт масаласида иккита ҳол бўлиши мумкин: 
а. - таъминот истеъмолдан ортиқ; б. - истеъмол таъминотдан ортиқ. Иккала ҳолда ҳам мақсад функция кўриниши ўзгармайди. Биринчи-а. ҳолда соҳта -истеъмолчи пункт, унинг маҳсулот миқдори-; иккинчи б. ҳолда соҳта -таъминотчи пункт киритилиб, унинг маҳсулот миқдори-  деб олинади.
	Бунда соҳта таъминотчидан барча истеъмолчиларга олиб бориш ҳаражатлари нол деб олинади. Ҳақиқатдан, бу йўналишлар бўйича маҳсулот ташилмайди. Соҳта истеъмолчи бўлган б. ҳолда ҳам, унга маҳсулот ташиш ҳаражати нолга тенг деб олинади. Бу билан унга оптимал режада энг кам ҳаражатга эга бўлган йўл тў\ри келади. Демак, очиқ транспорт масаласини ҳар вақт ёпиқ ҳолга келтириш мумкин экан. Шунинг учун қуйида келтирилган ечиш усуллари фақат ёпиқ (1)-(4) кўринишдаги транспорт масаласи учун берилган. (1)-(4) транспорт масаласини қуйидаги жадвал
   1-жадвал
Таъминот	Истеъмолчилар	мавжуд маҳсулот 	
чилар	B1	B2	.  .  .	Bj	.  .  .	Bn	миқдори	
A1	c11	c12	.  .  .	c1j	.  .  .	c1n		
A2	c21	c22	.  .  .	c2j	.  .  .	c2n		
								
Ai	ci1	ci2	.  .  .	cij	.  .  .	cin		
								
Am	cm1	cm2	.  .  .	cmj	.  .  .	cmn		

талаб	
b1	
b2	
.  .  .	
bj	
.  .  .	
bn		

кўринишда бериш, усулларни баён қилишни осонлаштиради. Бунда ҳаражатни билдирувчи  сонлари катакларнинг ўнг юқори бурчагига ёзилади. Охирги устун ва сатрларга мос равишда таъминот пунктларида бўлган маҳсулот ва истеъмолчиларга керак бўлган талаб-маҳсулот миқдорлари ёзилади. Энди бошлан\ич режа (бошлан\ич тақсимот) ни топиш усуллари билан танишиб чиқамиз.

I. Шимолий-\арб бурчак усули

	Бу усул -истеъмолчининг талабини -таъминотчини маҳсулоти билан қондиришдан бошланади. Агар талаб тўла қондирилса (бунинг учун  бўлиши керак), унда ни ортиб қолган маҳсулоти билан нинг талабини қондиришга ўтилади ва ҳоказо. Агар  таъминотчи нинг талабини қондира олмаса, у ҳолда  таъминотчига ўтилади ва унинг ёрдамида  талаби қондирилади. Бу жараён давомида тақсимланган маҳсулотлар миқдори мос катакларда кўрсатиб (ёзиб) борилади. Бу жараён барча маҳсулотларни истеъмолчиларга тўла тарқатиб бўлгунга қадар давом эттирилади. Бу жараённинг ҳар бир қадамида, ёки мос таъминотчи маҳсулоти тугайди, ёки мос истеъмолчи талаби тўла қондирилади. Агар иккала ҳол бир пайтда рўй берса, бу катакнинг ўнг томонидаги ёки пастидаги катагига нол ёзиб қўйилади. Бошлан\ич режани хосмас (бу ҳақда қуйига қаранг) қилиш учун шундай қилинади.
	Бу усулни қуйидаги мисолда баён этамиз. -таъминотчилар бўлиб, уларнинг маҳсулот миқдорлари мос равишда  га тенг бўлсин. Шу маҳсулотларга эҳтиёжи бўлган -истеъмолчилар бўлиб, уларнинг маҳсулотга бўлган талаблари мос равишда  ,  га тенг бўлсин.  таъминотчидан -истеъмолчига бирлик маҳсулот ташиш ҳаражати  қуйидаги:  , , ,  , , ,   сонлар билан аниқланган бўлсин. Бу масалани 1-жадвал каби,  қуйидаги кўринишда ёзамиз:                                                          

                                                                      2-жадвал.
Таъминот	Истеъмолчилар	мавжуд маҳсулот миқдори	
чилар	B1	B2	B3	B4	B5		
A1	        5
80	       6
20	    9	         8	       3	
100	
A2	         9
	      4
40	         3
110	        4
0	       5	
150	
A3	          8	        7	        9	         2
180	       5
20	
200	
A4	          3	        4	         5	         4	        8
150	
150	
талаб	80	60	110	180	170	600	

-таъминотчининг маҳсулоти-100 ёрдамида энг кичик тартиб рақамли истеъмолчи бўлган нинг талабини қондиришдан бошлаймиз: 100 нинг 80 бирлигини га ажратамиз, қолган 100-80қ20 бирлик маҳсулотни  истеъмолчига берамиз, етмаган 60-20қ40 маҳсулот миқдорини  таъминотчи маҳсулоти билан тўлдирамиз.  нинг қолган маҳсулоти 150-40қ110  истеъмолчини талаби 110 учун етарли. Шундай қилиб, бу қадамда таъминотчининг ҳам маҳсулоти тугади, истеъмолчи талаби ҳам тўла қондирилди. Шунинг учун кейинги катакка нол сони ёзиб қўйилган (2-жадвал).
Бу жараённи охиригача давом эттирсак бошлан\ич режа (тақсимот)га эга бўламиз: ,  ,                  , . Бунда ҳисоблаш мумкинки, мақсад функциянинг қиймати 2670 бирликка тенг бўлади. 

II. 	Минимал бащоли усул

	Бу усулнинг моҳияти шундан иборатки, аввал энг кам ҳаражатли йўл танлаб олиниб, шу йўл орқали иложи борича кўп маҳсулот жўнатилади. Бунда, албатта, ёки истеъмолчи талаби тўла қондирилган бўлади, ёки таъминотчининг маҳсулоти тўла сарф бўлади. Шундан сўнг, мос ҳолда ёки, истеъмолчи, ёки таъминотчи кейинги ҳисоблашларда иштирок этишмайди. Сўнг, қолган харажатлардан энг кам бўлгани танлаб олиниб, олдинги жараён такрорланади ва бу жараён барча маҳсулотлар тақсимланиб бўлгунча давом эттирилади. Бу усулни юқорида кўрилган мисолда баён қиламиз.
                                                    3-жадвал.
Таъминот	Истеъмолчилар	мавжуд маҳсулот миқдори	
чилар	B1	B2	B3	B4	B5		
A1	          5
	        6
	          9	         8
	        3
100	
100	
A2	          9
	        4
40	          3
110	          4
	        5	
150	
A3	          8	        7
	          9	         2
180	        5
20	
200	
A4	          3
80	        4
20	          5	         4	        8
50	
150	
талаб	80	60	110	180	170	600	

3-жадвалдан кўриниб турибдики, энг кам ҳаражат 2 га тенг бўлиб, у  катакда жойлашган. Унга мос келган талаб 180, бериш мумкин бўлган маҳсулот эса 200 га тенг. Шунинг учун, бу катакка 180 ёзилган. Кейинги, энг кичик элемент 3 бўлиб, у  катакларида жойлашган.  катакка мос келган талаб билан, бор маҳсулот миқдорининг энг кичиги 100, демак, у катакка 100 ёзилган бўлиши керак. Худди шундай  катакка 110,  га 80 ёзилган. Ундан кейинги, энг кичик ҳаражат 4 га тенг бўлиб, у  катакларида жойлашган, бунда  устунига тў\ри келган  ва  катаклари ҳисобга олинмайди, чунки  истеъмолчи талаби қондирилган. Шунинг учун  га 40 (чунки  таъминотчида 40 маҳсулот миқдори қолган эди),  га 20 (чунки  истеъмолчига яна 20 маҳсулот миқдори керак эди) ёзилган. Маҳсулотлари тугаган таъминотчиларга ва талаблари қондирилган истеъмолчиларга мос келган сатр ва устунлар ҳисобга олинмаган ҳолда, энг кичик ҳаражатни топамиз, у 5 га тенг ва  катакда жойлашган. Унга қолган 20 маҳсулот миқдорини ёзамиз. Охирги тўлдирилмаган, битта  катак қолди, унга 50 ёзилиши кераклиги тушунарли. 
Шундай қилиб 3-жадвалда бошлан\ич тақсимотни ҳосил қилдик, унга мос келган ҳаражат 1970 га тенг, яъни олдинги усулдаги харажатга қараганда кичик, демак, ҳосил қилинган режа- оптимал режага яқинроқ экан, чунки, бунда ҳаражатни ҳисобга олган ҳолда бошлан\ич тақсимот аниқланди.

III. 	Икки щисса афзалроқ усул

	Бу усулнинг моҳияти қуйидагича: Аввал ҳар бир сатрда энг кичик ҳаражатли катак (катаклар) танлаб олиниб V-билан белгиланади. Кейинги ҳар бир устунда энг кичик ҳаражатли катак (катаклар) ҳам V-билан белгиланади. Шундан сўнг, VV белгили катакларга мос равишда тақсимланган маҳсулот миқдори ёзилади. Икки белгили катакларга тақсимланган маҳсулот миқдорлари ёзиб бўлингандан кейин, бир белгили катакларга ўтилади. Ундан сўнг, қолган катаклардан энг кичик ҳаражатлиси танлаб олинади ва бундан кейин минимал баҳоли усул қўлланилади.
                                                   4-жадвал.
Таъминот	Истеъмолчилар	бор маҳсулот	
чилар	B1	B2	B3	B4	B5	миқдори	
A1	         5
	        6
	          9	          8
	VV    3
100	
100	
A2	          9
	V      4
40	VV      3
110	         4
	         5	
150	
A3	          8	        7
	         9	VV      2
180	       5
20	
200	
A4	VV      3
80	V      4
20	          5	          4	        8
50	
150	
талаб	80	60	110	180	170	600	

Бу ерда ҳам, аввалги усулдагидек мақсад функциянинг қиймати 1970 чиқади.  (Лекин, бу, умуман ҳар вақт ҳам тенг чиқади, дегани эмас). Энди, бошлан\ич режа ёрдамида оптимал режани топиш усулларидан айримларини кўриб чиқамиз.

2. Потенциаллар усули

	Теорема 1. Агар,  режа транспорт масаласининг оптимал ечими бўлса, у ҳолда унга мос шундай  та ,  сонлари мавжудки, улар қуйидаги
, агар ,
, агар ,
.
шартларни қанотлантиради. Бунда  ва  лар мос равишда таъминотчи ва истеъмолчиларнинг потенциаллари дейилади.
	Чизиқли программалаш назариясида кўрсатиладики; тў\ри ва унга иккиламчи бўлган масалаларнинг мақсад функцияларининг оптимал режадаги қийматлари бир-бирига тенг ва шу билан бирга қуйидаги теорема ўринли бўлади (унинг исботини келтирмаймиз).
	Теорема 2. Агар тў\ри масаланинг -шарти оптимал режада тенгсизлик кўринишда бўлса, унга мос иккиламчи масаланинг оптимал режасининг -компонентаси нолга тенг бўлади. Агар иккиламчи масаланинг оптимал режаси -компонентаси мусбат бўлса, унга мос тў\ри масаланинг -чегараси оптимал режада тенглик ҳолда бўлади.
Бу теоремадан келиб чиқадики: а. маҳсулот сони () ёзилган катаклар учун потенциаллар йи\индиси шу катакка мос келган ҳаражатга тенг бўлиши керак, яъни 
;
б. маҳсулот сони ёзилмаган () катаклар учун потенциаллар йи\индиси шу катакка мос келган ҳаражатдан кичик ёки тенг бўлиши керак, яъни 
                                      (7).
	Энди, бевосита топилган бошлан\ич режаларни яхшилаш- оптимал ечимни аниқлашни кўриб чиқамиз. 
Агар бирор тўлдирилмаган катак (7)-шартни қаноатлантирмаса, топилган режа оптимал эмас, уни яхшилаш керак бўлади.
Потенциаллар усули бир нечта этапдан иборат:
1. 	Потенциалларни аниқлаш.
Потенциаллар- хосмас режалар учун тузилади ва бунинг учун 
                                                             (8)
тенгламалар системасидан фойдаланилади. Режа хосмас бўлганлиги учун  та катак тўлдирилган бўлиб, уларга мос келган (8) -тенгламалар системаси ҳам  та, ўзгарувчилар сони эса  та. Шунинг учун, бирор ўзгарувчига аниқ қиймат берилади, одатда , Шундан кейин, қолган потенциаллар (8)-тенгламалар системасидан бир қийматли топилади. Масалан, 4-жадвалда келтирилган бошлан\ич режага мос потенциалларни топиш керак бўлсин. Бунинг учун 4-жадвалга шу потенциаллар қийматларини кўрсатадиган қўшимча биттадан устун ва сатр киритамиз. Тўлдирилган катаклар  , , , , ,  бўлиб, уларнинг сони  га тенг бўлганлиги учун, берилган бошлан\ич режа хосмас бўлади. Шу тўлдирилган катаклар учун (8) тенгламалар системасини тузамиз

, .               (9)
Бу-тенгламалар системасида 8 та тенглама, 9 та номаълум бор. Агар  деб олсак,   қийматларни (9)-тенгламалар системасидан топамиз. Уларни қўшимча устун ва сатр катакларига мос равишда ёзиб қўямиз. Булар бошлан\ич режанинг потенциаллари бўлиб хизмат ҳилади. Тўлдирилмаган катаклар учун оптималлик шарти-(7) текширилади, агар (7)-тенгсизлик барча катаклар учун ўринли бўлса, мос режа оптимал бўлиб, масала ечилган бўлади, акс ҳолда (7)-шарт бажарилмаган катакка мос равишда мусбат -сони катакнинг чап томони пастки бурчагига ёзиб қўйилади, улар 5-жадвалда кўрсатилган. -сатр учун 0-2<5, 0-1<6, 0-2<9, 0+0<8, - сатр учун 5-2<9, 5+0>4, 5+3>5. Демак,  ва  катакларда оптималлик шарти бузилар экан. Шунинг учун, уларга мос равишда ,  сонлари ёзилган; - сатр учун 2-2<8, 2-1<7, 2-2<9; -сатр учун 5-2<5, 5+0>4. Демак,  катакда ҳам оптималлик шарти бузилади, шунинг учун, у катакка  сони ёзилган. Шундай қилиб, учта ,  ва  катакларда оптималлик шартлари бузилиб, уларга мос сонлар ёзиб қўйилди.

                                                                  5-жадвал.
Таъминот	Истеъмолчилар	мавжуд 	
чилар		B1	B2	B3	B4	B5	маҳсулот миқдори	
	      Vj
ui	-2	-1	-2	0	3		
A1	0	       5
	        6
	       9	        8
	    3
      100	
100	
A2	5	       9
	    - 4
        40	     3
      110	     4
1	      + 5
3	
150	
A3	2	       8	        7
	       9	      2
       180	        5
         20	
200	
A4	5	     3
      80	       +4
        20	       5	      4
1	    -8
        50	
150	
талаб		80	60	110	180	170	600	
2. Ёпиқ занжир тузиш ва маҳсулотларни қайта тақсимлаш.
1-пунктда катакларнинг чап пастки бурчагига ёзилган сонлар ичидан энг каттасига мос келган катак ажратиб олинади ва кейинчалик бу катак тўлдирилади (шу билан янги битта тўлдирилган катак пайдо бўлади).
	Бизнинг мисолда бундай катак  дир. Шу катакни «+» билан белгилаймиз ва бир учи шу катакда, қолган учлари бошқа тўлдирилган катакларда бўлган кўпбурчак ясаймиз. Бу кўпбурчак учларини кетма-кет «+» ва «-» билан белгилаб чиқамиз. Кейин «-» учдаги маҳсулот миқдорларининг энг кичигини аниқлаймиз. Кўрилаётган сонли мисолда кўпбурчак учлари , ,  ва  катаклардан иборат бўлиб,  «-» учлардаги минимал маҳсулот миқдори  катакда жойлашган бўлиб- 40 га тенг. Шу минимал маҳсулот миқдорини кўпбурчакнинг «+» учидаги сонлар устига қўшамиз, «-»  учдаги сонлардан айириб ташлаймиз ва тўлдирилмаган учга шу сонни ёзиб қўямиз. Бунда энг кам маҳсулотли катаклар сони бир нечта бўлиб қолиши мумкин, у ҳолда айримларида нол сони сақлаб қолиниши керак, чунки тўлдирилган катаклар сони  та бўлиши шарт.
	Кўрилаётган мисолда  катакдаги энг кам маҳсулот 40 бўлиб, уни  катакка ёзамиз ва  катак «+» белгили бўлганлиги учун, ундаги 20 сонига 40 ни қўшиб 60 ни ёзамиз,  да «-» бўлгани учун, ундаги 50 сонидан 40 ни айириб, ўрнига 10 сонини ёзиб қўямиз, натижада қуйидаги- 6-жадвалга эга бўламиз.
	 катак тўлдирилган бўлиб қолди, шунинг учун потенциаллар ҳам ўзгариши керак.

                                                                      6-жадвал.
Таъминот	Истеъмолчилар	мавжуд 	
чилар		B1	B2	B3	B4	B5	маҳсулот	
	      Vj
ui	-2	-1	1	0	3	миқдори	
A1	
0	       5
	         6
	        9	         8
	       3
100	
100	
A2	2	       9
	        4
	      3
- 110	       4
	        5
+   40	
150	
A3	
2	       8	        7
	         9	        2
180	      5
20	
200	
A4	       5	       3
      80	       4
        60	       +5	         4
	-8
        10	
150	
талаб		80	60	110	180	170	600	
	3. Потенциалларни ўзгартириш
Юқорида кўрилган мисолда, янги тўлдирилган  катак учун  тенглик бажарилган бўлиши керак, демак, ё , ё  ни камайтириш керак бўлади. Бунда, шундай ўзгартиришни танлаб олиш керакки, натижада қолган потенциаллар ичида энг кам ўзгариш рўй берсин.
	6-жадвалдан кўриниб турибдики, бунинг учун  ни камайтириш мақсадга мувофиқ, чунки бунда, фақат  ни ўзгартиришга тў\ри келади. Аксинча агар  ни камайтирсак, унда  ларни ҳам ўзгартиришга тў\ри келар эди.
	, бундан  эканлиги   дан эса,  эканлиги келиб чиқади. Юқоридаги 6-жадвалда, янги режага мос келган янги потенциаллар кўрсатилган.
Юқоридаги жараён натижасида янги тўлдирилмаган катак ҳосил бўлиб қолади, демак бу катак учун оптималлик шарти (8)-тенглик бажарилиши керак. Бу эса потенциалларни ўзгартиришга олиб келади. Бунда, шунга ҳаракат қилиш керакки, натижада ўзгарадиган потенциаллар сони иложи борича энг кам бўлсин (аслида, бу ерда иккита йўл бор, ё таъминотчи потенциалини, ё истеъмолчи потенциалини камайтириш). Кейин 2-пункт қайтарилади. Агар тўлдирилмаган катаклар учун оптималлик шарти (8) текшириладиган бўлса, уни фақат потенциаллари ўзгарган сатр ва устунлар учун олиб бориш етарли. Бизнинг мисолда бу  сатр ва  устунлардир. Оптималлик шарти эса фақат  катак учун бузилган- 5+1>5. 	Бир учи шу катакда, қолган учлари тўлдирилган катакларда бўлган кўпбурчак (хусусан тўртбурчак) 6-жадвалда кўрсатилган. Бунда «-» белгили катаклардаги энг кам маҳсулот миқдори 10 га тенг. У ёрдамида янги режани тузамиз (7-жадвал).
                                                              7-жадвал.
Таъминот	Истеъмолчилар	мавжуд 	
чилар		B1	B2	B3	B4	B5	маҳсулот миқдори	
	      Vj
ui	-1	0	1	0	3		
A1	
0	       5
	        6
	         9	          8
	         3
      100	
100	
A2	
2	      9
	        4
	        3
100	          4
	          5
          50	
150	
A3	
2	      8	        7
	        9	        2
       180	5
20	
200	
A4	
4	     3
      80	      4
       60	       5
      10	          4
	     8
	
150	
талаб		80	60	110	180	170	600	

	Бу жадвалдан кўриниб турибдики,  тенгликда  ни ўзгартириш мақсадга мувофиқ, чунки бунда фақат  ва