Иккиланган симплекс усул

Иккиланган симплекс усул
Режа:

1. 
   Берилган масалани стандарт формага келтириш.
   
2. 
   Симплекс жадвал тузиш.
   
3. 
   Бир таянч ечимдан иккинчи ечимга утиш.
   
4. 
   Таянч ечимни оптималликка текшириш.
   
5. 
   Масаланинг ечимини оптималлик шартини бажарилиши.
   
6. 
   Масаланинг ечимини йуклик шартини бажарилиши.
   

Иккиланган симплекс усул оддий симплекс усулга нисбатан баъзи кулайликларга эга:

1. 
   Иккиланган симплекс усул буйича ечилаётган масала шартларидаги озод хадлар мусбат булмаслиги хам мумкин;
   
2. 
   Иккиланган симплекс усул билан бир вактнинг узида хам берилган масаланинг, хамда иккиланган масаланинг ечими топилади ёки иккила масаланинг ечими мавжуд эмаслиги аникланади;
   
3. 
   Берилган масаланинг чегараловчи шартлари « » белги билан богланган ёки унинг баъзи озод хадлари манфий булган масалаларни, иккиланган симплекс усул билан ечганда бажариладиган хисоблаш ишларининг сони камаяди;
   
4. 
   Иккиланган симплекс усул билан ишлаб чикаришнинг баъзи зарур тавсифларини аниклаш мумкин. Масалан, бир вактнинг узида хам ишлаб чикариш планини, хам ишлаб чикаришга сарф килинадиган хамма воситаларнинг бахосини хисоблаш мумкин.
   

Оддий симплекс усул сингари иккиланган симплекс усулнинг хар бир итерациясида (кадамида) n- улчовли X вектор таянч план алмашиб боради. Факат, шунга эътибор бериш керакки, симплекс усулдан фаркли равишда, иккиланган симплекс усул билан топилган n-улчовли X вектор таянч план булмаслиги мумкин.
Бундай планни чала таянч план деб атаймиз. Иккиланган симплекс усул буйича чала таянч планларни алмаштириш жараени таянч план топилгунча такрорланади. Топилган таянч план эса масаланинг оптимал плани булади.

1. 
   теорема. Агар чала таянч план масаланинг таянч плани булса, у оптимал план хам булади.
   

1. 
   теорема. Агар масаланинг чала таянч планининг компоненталаридан камида биттаси, масалан, булиб, барча j лар учун булса, берилган масала таянч планга эга булмайди.
   

2. 
   теорема Агар топилган чала таянч план учун булганда, булиб, камида битта булса, у холда ни янги чала таянч план га алмаштириш натижасида чизикли функциянинг киймати камаяди. векторни га алмаштириш учун базисдан вектор чикарилиб базисга куйидаги шартларни каноатлантирувчи вектор киритилади.
   

,
ва

Мисол. Куйидаги масала ва унга иккиланган масаланинг ечимини иккиланган симплекс усули ёрдами билан топинг.

Берилган масалани каноник формага келтирамиз.

(I)
Бу масалани кушимча узгарувчиларга мос келувчи векторларни базис векторларга айлантириш учун (I) масаладаги тенгламаларнинг хар бирини (-1)га купайтирамиз. Натижада куйидаги масалага эга буламиз:
(II)

Бу масалага иккиланган масала куйидаги куринишга эга булади:

(III)

2. 
   масалада векторларни базис векторлар деб кабул килиб, симплекс жадвални тулдирамиз.
   

j=1,2,3,4,5,6,7 учун

булади. Демак,

вектор (II) масаланинг чала таянч плани булади. Иккиланган масаланинг бу базисдаги ечими

Чала таянч план X нинг энг кичик манфий элементига мос келувчи векторни базисдан чикарамиз ва

шартни каноатлантирувчи векторни базисга киритамиз. - аникловчи элемент булади. Янги симплекс жадвалда барча j лар учун

Берилган масаланинг янги чала таянч плани - (8/5, 28/5, -8/5) булади. Янги базисга мос келувчи иккиланган масала (III) нинг таянч плани
= (-1,0,0)
вектордан иборат ва чизикли функциянинг унга мос келувчи киймати:



<sub>Таянч иборалар


Берилган ва иккиланган масалаларнинг ечимлари, чала таянч план, чизикли функция киймати, стандарт форма, оптимал ечим.</sub>

Адабиётлар:

1. 
   Н.Р.Бекназарова, Х.Н.Жумаев “Математик программалаштириш ва оптималлаштириш” Ўқув предмети бўйича Ўқув-услубий мажмуа (Бакалавриат босқичи талабалари учун).Ташкент 2006.
   
2.