3-мавзу: чизиљли дастурлашда иккиланмалик назарияси

Бошланђич масала
Иккиланма масала
1.	1.
2. m - чеклаш шартлари сони;	2. њзгарувчилар;
3. њзгарувчилар;	3. n чеклаш шартлари сони;
4. ;	4. j та “” књринишдаги чеклаш;
5. i та чеклаш “” књринишда;	5. књринишда;
6. бирор белги билан чегараланмаган;	6. j та “=” књринишдаги белгили шарт;
7. i та “=” књринишдаги шарт;	7. ќеч љандай шарт билан чегараланмаган;
8. Чеклаш шартларидаги озод ќадлар;	8. Маљсадли функциядаги номаълумлар (bi) коэффициентлари;
9. Маљсадли функцияда ларнинг (cj) коэффициентлари	9. Чеклаш шартларидаги (ci) озод ќадлар;
10. Чеклаш шартлари номаълумлари коэффициентлари матрицаси (А).	10. Чеклаш шартлари номаълумлари коэффициентлари матрицаси транспонирланган ( ).

ЧД нинг хусусий масалаларидан бирини умумий ќолда љараймиз ва у бошланђич масала бњлсин.

Бу масалага иккиланма масала љуйидагича бњлади:



Охирги масалага иккиланма масалани тузсак, бошланђич масалани оламиз.
Энди ЧД бошланђич масаласи хусусий ќолларининг уларга иккиланма масалаларини матрица књринишда ёзамиз:
Бошланђич масала Иккиланма масала

1. 
   , ,
   

, ,
. .

2. 
   , ,
   

, ,
. .

3. 
   , ,
   

, ,
. .

4. 
   , ,
   

, ,
. .

Бунда иккиланма масаланинг номаълумлари сатр матрица бњлади.

I ва II иккиланма масалалар жуфтига симметрик, III ва IV масалалар жуфтига эса “=” књринишдаги чеклаш шартлари бњлганлиги учун симметрик бњлмаган масалалар дейилади.
Юљоридаги књрсатилган тњртта ќол билан ЧД исталган масаласининг унга иккиланма масаласини тузиш мумкин.
Энди бир неча мисоллар љараймиз:
1-мисол.
,

масалага иккиланма масалани тузинг.
Ечиш. Бунинг учун 2-тенгсизликни (-1) књпайтириб ушбу масалани ќосил љиламиз: Бу масалани 1 књринишга келтирамиз;
,

Бу ќолда иккиланма масала љуйидагича бњлади:


2-мисол. Ушбу масалага иккиланма масалани тузинг:


Ечиш. Бунинг учун (II) ва (IV) књринишлардан фойдаланамиз.
Иккинчи тенгсизликни (-1)га књпайтириш билан њзгартирамиз:


Энди иккиланма масала љуйидагича бњлади:


Бу масала орљали њзаро иккиланма масалани тузишнинг айрим љоидаларини књрсатамиз. Бошланђич масалада чеклаш шартлари , демак унга иккиланма масалада учта њзгарувчи бњлиши керак . Бошланђич масалада њзгарувчилар сони бњлганлиги учун иккиланма масалада чеклаш шартлари сони тњртта бњлди. Бошланђич масаланинг ва њзгарувчилари бирор белги билан чегараланмаган бњлгани учун иккиланма масалада биринчи ва тњртинчи чеклашлар тенглик књринишида бњлади. Бошланђич масалада учинчи чеклаш шарти тенглик књринишда бњлганлиги учун њзгарувчи бирор белги билан чегараланмаган.
2) Њзаро иккиланма масалалар њзгарувчиларининг иљтисодий талљини. Ресурслардан оптимал фойдаланиш ќаљидаги масалада икки хил Р₁ ва Р₂ маќсулотлар ишлаб чиљариш учун R₁, R₂ ва R₃ уч хилдаги хом ашёлардан фойдаланиш керак эди, уларнинг миљдори албатта чегараланган бњлади. Бу масалада:

1. 
   ќар бир хом ашё миљдори;
   
2. 
   ќар бир ресурсдан бир-бирлик маќсулот ишлаб чиљаришга кетган сарфи;
   
3. 
   ќар бир маќсулотни реализация килишдан олинадиган фойдалар берилганида ќар бир маќсулотни ишлаб чиљаришнинг шундай миљдорини аниљлангки, корхона уларни реализация љилишдан максимал фойда олсин. Бундай бошланђич масаланинг математик модели љуйидагича бњлсин:
   

Энди фараз љилайлик, љандайдир сабаб билан корхона маќсулот ишлаб чиљаришдан воз кечади ва бор ресурсларни сотишга љарор љилади. Табиийки, корхона ресурсларни сотиб ќамда фойда олишни ва у фойда маќсулот ишлаб чиљаргандагидан кам бњлмаслигини истайди. Ресурсларни сотиб олувчи харидорни эса уни иложи борича кам баќода олиш љизиљтиради. Энди шундай савол туђилади. Ресурсларни љандай баќода сотиш керак?
Ресурсларни нисбий баќолаш учун бошланђич масалага иккиланма масалани тузамиз.
Бунинг учун љуйидаги белгилашларни киритамиз: - ресурснинг баќоси бњлсин; - , - ресурсларнинг баќоси бњлсин. Харидорни чизиљли функциянинг минимал љиймати љизиљтиради, яъни бутун ресурслар баќосини камайтириш бњлади. Чеклаш шартларида шу ифодаланиши керакки, корхона ресурсларни сотганда ќам, маќсулот ишлаб чиљаргандагига нисбатан књпрољ фойда олиниши керак, яъни

Бу системада биринчи чеклаш шартининг маъноси - бир бирлик Р₁ маќсулотни ишлаб чиљариш учун кетган ресурслар баќоси уни реализация љилишдан келадиган фойдадан кичик бњлиши мумкин эмас. Иккинчи чеклаш худди шундай Р₂ маќсулот учун бњлади. Бундан ташљари равшанки, хом ашёлар баќоси манфий бњлмайди, яъни .
Шундай љилиб, бошланђич масалага иккиланма масала љуйидагича бњлади:


.
Демак, иккиланма масала њзгарувчиларининг иљтисодий маъноси корхона ресурсларини нисбий баќолашдан иборатдир. Бу баќолар нисбийдир, чунки бир хил ресурслар ќар хил корхоналар учун ќар хил баќога эга бњлади. Бундай баќолар маиший хизмат корхоналарида књпрољ учрайди. Масалан, ошхонадан хом (гњшт, балиљ ва бошљалар) озиљ-овљатлар, књзойнакнинг ойнасини тузатиш устахонасидан, књзойнак ойнасини сотиб олиш баќоси магазиндан олинганига нисбатан баландрољ бњлади. Ќар бир корхона бу моллар учун, улардан овљатлар пишириб сотишга ва књзойнакка ойнани љњйиб беришга нисбатан кам бњлмаган фойда олишга ќаракат љилади.
Теорема: Њзаро иккиланма масалалар жуфтидан бирортаси оптимал ечимга эга бњлса, бошљаси ќам оптимал ечимга эга бњлиб, маљсадли функция экстремал љийматлари учун муносабат бажарилади. Масалаларнинг бирида маљсадли функция чегараланмаган бњлса, иккинчиси ќам ечимга эга бњлмайди.
Юљорида таъкидланганидек, њзаро иккиланма масалалардан бирининг ечимини топиш билан иккинчисининг ќам ечимини олиш мумкин. Бунинг љандай бажарилишига мисол сифатида симплекс усул билан ечилган маса-лага иккиланма масаланинг ечимини љандай олишни књрсатамиз. Маълумки, 4-жадвалда ечим оптимал эди ва . Иккиланма масала њзгарувчиларини билан белгилайлик. бњлганлиги учун чеклаш шартлари
(1)
бњлади.
Бошланђич масаланинг чеклаш шартлари “” тенгсизликлардан иборат бњлганлиги учун
(2)
(1) ва (2) шартларида
(3)
чизиљли функциянинг минимал љийматини топиш керак.
Њзаро иккиланмалик теоремасидан маълумки
.
Симплекс усул 4-жадвали (m+1) сатридан эканлигини аниљлаймиз ва
.

3. Иккиланма симплекс усул. Маълумки бошланђич (тњђри) масаланинг ечимини олиш учун иккиланма масалага њтиб, унинг оптимал ечими баќоларидан фойдаланиб бошланђич масала оптимал ечимини ќам олиш мумкин.

Љњшимча базис, бирлик матрицага эга бњлган бошланђич масала биринчи симплекс жадвалига эътибор берсак, устунлар бњйича бошланђич масала, сатрлар бњйича иккиланма масала ёзилганлиги пайљаймиз ќамда бошланђич масала баќолари бњлиб лар, иккиланма масала баќолари бњлиб, эса хизмат љилади. Бошланђич масала ёзилган симплекс жадвал бњйича иккиланма масалани ечамиз ва икиланма масала оптимал ечимини оламиз, шу билан бирга бошланђич масала оптимал ечимига ќам эга бњлади. Бундай усулга иккиланма симплекс усул деб аталади.
Каноник књринишда љњйилган ЧД нинг бошланђич масаласининг минимум љийматини топиш керак бњлсин. Бунга мос иккилан-ма масалада функциянинг шартларни љаноатлантирувчи максимум љийматини топиш керак бњлади. Фараз љилайлик, базис шундай танланганки вектор компонентларидан ќеч бњлмаганда биттаси манфий (масалан, ) бњлиб, лекин ќамма векторлар учун муносабат бажарилсин. Иккиланмалик теоремасига асосан, иккиланма масаланинг ечими бњлади. Бу ечим оптимал бњлмайди, чунки биринчидан, танланган Х базисда манфий компонент мавжуд ва бошланђич масаланинг ечими эмас, иккинчидан, иккиланма масаланинг оптимал ечими баќолари манфий бњлмаслиги керак.
Шундай љилиб, компонентга мос векторни бошланђич масала базисидан чиљариб, манфий баќога эга бњлган векторни эса иккиланма масала базисига киритиш керак бњлади.
Бошланђич масала базисига киритиладиган векторни танлаш учун ι - сатрни љараймиз: бунда ларга эга бњлмаса иккиланма масала чизиљли функцияси ечимлар књпбурчагида чегараланмаган бњлиб, бошланђич масала эса ечимга эга бњлмайди. Айрим бњлса, бу манфий љийматларга мос устунлар учун
(4)
ларни ќисоблаймиз ва га мос векторни аниљлаймиз. Масала минимумга ечилаётган бњлса, га мос векторни, масала максимумга ечилаётган бњлса, масала максимумга ечилаётган бњлса га мос векторни аниљлаймиз. Бу векторни бошланђич масала базисига киритамиз. Бошланђич масала базисидан чиљариладиган векторни йњналтирувчи сатр аниљлайди.
, яъни бњлса, очувчи элемент учун, бњлган ќолдагина олинади. Бу босљичда очувчи элементни бундай танлаш Х вектор манфий компонентларининг књпайишига олиб келмайди. Жараённи ни олгунча давом эттирамиз ва иккиланма масаланинг оптимал ечимини топамиз, демак, бошланђич масаланинг ќам оптимал ечимини оламиз.
Иккиланма симплекс усули алгоритми бњйича, жараёнида шартни ќамма ларни йукотгунча ќисобга олмаслик мумкин ва кейин оптимал ечимни оддий симплекс усул билан топамиз. Буни ќамма бњлса, ишлатиш љулай бњлиб, бошланђич масала ечимига њтишда битта итерацияни минимуми билан эмас, нисбатнинг максимуми орљали, яъни билан аниљланади.
Иккиланма симплекс усул билан ЧД масаласини мусбат базисда чеклаш шартлари системаси озод ќадлари исталган ишорали бњлганда ќам ечиш мумкин. Бундай усул, чеклаш шартлари системаси шакл алмаштиришлари сонини ва симплекс жадвал њлчами (сони)ни камайтиришга имкон беради.

3-мисол. чизиљли функциянинг

чеклаш шартларини љаноатлантирувчи минимал љийматини топинг.
Ечиш. Иккинчи тенгсизликни (-1) га књпайтирамиз, ќамда љњшимча њзгарувчилар киритиб, биринчи иккала тенгсизликни тенгламага айлантириб ушбуни ќосил љиламиз:

Биринчи симплекс жадвални тузамиз: А₄ ва А₅ векторларни базис учун љабул љиламиз. бњлганлиги учун, иккинчи сатр коэффициент-ларини љараймиз. Бу коэффициентлардан А₁ ва А₃ векторлар устунида манфий коэффициентлар мавжуд. (4) љоида бњйича ќисоблашларни бажарамиз:
,
.
Чизиљли функциянинг минимум љиймати топилаётганлиги учун

бњлиб, А₁ вектор калит устун, калит сатр А₄ вектор сатри бњлиб очувчи (калит) элемент 1 бњлади. А₄ векторни базисдан чиљариб базисга А₁ векторни киритамиз.
1-симплекс жадвал.

i

Базис

Базис коэфф.