4. Оптимал ечимни топиш.
Базисга кирмай колган каторга нолга тенг булган айрим узгарувчилар оптимал режада булиши мумкин. Бундай холларда оддий усуллар ёрдамида шу узгарувчини базисга киритиб янги режани хосил килиш мумкин. Агар иккита ёки бир нечта оптимал режалар мавжуд булса, улардан хохлаган биттасини оптимал режа деб кабул килиш мумкин.
Шуни эслатиб утиш керакки, агар нисбатларнинг энг кичиги бир нечта булса, у холда уларнинг ичидан уз хал килувчи элементига кура кейинги устун элементлари энг кичиг нисбатда булган катор танланади. Агар яна бир хил энг кичиг нисбатлар мавжуд булса, унда ларнинг энг кичигидан факат биттасини олиб, шу жараенни яна такрорлаш керак.
Чизикли дастурлаштириш масаласини ечимини Симплекс усули билан топиш бир неча боскичдан иборат эканлигини биз юкорида куриб утдик. Бу усулнинг асосий кийинчилиги хар бир боскичда янги базисга нисбатан максад функция ва чекланиш шартларини кайтадан езиб чикишдан иборатдир. Агар шу боскичларнинг хаммаси Симплекс жадваллар ердамида бажарилса чизикли дастурлаштириш масаласини симплекс усулда ечиш анча осонлашади.
Мисол. Ушбу
х1+х2-2х5=1
х2-2х4+х5=2 (1)
х3+3х4+х5=3
Системанинг манфий булмаган ечимлари орасидан Z=0+х4-х5 (2) функ-цияга минимум киймат берувчи ечимини топинг.
Ечиш. Жадвал тузиш учун (1) ва (2) ни
x1+x4-2x5=1
x2-2x4+x5=2
x3+3x4+x5=3
z-x4+x5=0 куринишда езиб оламиз.
(1) системани х1,х2,х3 га нисбатан осонгина ечиш мумкин. Шунинг учун бу номаълумларни системанинг базис номаълумлари деб кабул киламиз.
Базис номаълумлар х1,х2,х3 ва z ларни жадвалнинг 1 чи устунига, озод хадларни 2 чи устунига, х1 нинг коэффициентларини 3 чи устунга ва хо,х5 нинг коэффициентларини охирги устунга езиб куйидаги 1 жадвалга эга булади.
Базис номаълум.
|
Эркли
-х4
|
Номаълумлар
-х5
|
Озод хадлар
|
Х1
|
1
|
-2
|
1
|
Х2
|
-2
|
1
|
2
|
Х3
|
3
|
1
|
3
|
Z
|
-1
|
1
|
0
|
Минимумни (максимумни) топиш талаб этилаетганлиги учун Z сатрдаги мусбат (манфий) коэффициентлардан абсолют киймат жихатидан энг каттасини танлаб оламиз. Бизнинг мисолимизда х5 устундаги 1 сони булади. Озод хадлар устунидаги коэффициентлари шу устундаги мос мусбат коэффициентлар булган нисбатини энг кичигини танлаб оламиз.
min { 2/1;3/1} =2
Шу устунни хал килувчи устун килиб оламиз. Хал килувчи устун ва сатр кесишмасида турган элемент бош элемент дейилади. Кейинги жадвал куйидаги тартибда тулдирилади.
1). х2 ва х5 ларнинг урни алмаштириб езилади.
2). Бош элемент узига тескари микдор билан алмаштирилади.
3). Хал килувчи устун бош элементга булиниб тескари ишора билан езилади.
4). Хал килувчи сатр элементлари бош элементга булиб езилади.
5). Колган барча элементлар туртбурчак формуласи билан топилади.
2 - жадвал.
Базис номаълумлар
|
Эркли
-х4
|
Номаълумлар
-х2
|
Озод хадлар
|
Х1
|
-3
|
2
|
5
|
Х5
|
-2
|
1
|
2
|
Х3
|
5
|
-1
|
1
|
Z
|
1
|
-1
|
-2
|
Z сатрдаги барча коэффициентлар манфий (мусбат) чикса оптимал ечим топилган булади, аммо жадвалнинг бу сатрида 1 мусбат коэффициент бор.
min {1/5} =1/5
3 - жадвал.
Базис номаъ-лумлар
|
Эркли
-х3
|
Номаълумлар
-х2
|
Озод хадлар
|
Х1
|
-0,6
|
2,6
|
4,4
|
Х5
|
0,4
|
0,6
|
2,4
|
Х4
|
0,2
|
-0,2
|
0,2
|
Z
|
0,2
|
0,8
|
-2,2
|
Бу жадвалда оптимал режа топилди. х1=4,4, х5=2,4, х4=0,2, х3=х2=0 да
Zmin= -2,2 булади.
Саволлар.
1.Бош элемент кандай танлаб олинади?
2.Хал килувчи устун кандай танлаб олинади?
3.Хал килувчи сатр элементлари кандай топилади?
4.Симплекс жадвал усулида качон масала оптимал ечимга эришган дейилади?
5. Качон масаланинг max(min) киймати йук деб айтилади?
6. Жадвалда озод хад манфий булиши мумкинми?
7. Эркли номаълумлар кандай кийматга эга булади?
8. Базис номаълумлар киймати кандай топилади?
9. Максад функциянинг киймати нимага тенг булади?
|
