Маъруза - 6.
Мавзу. Чизикли дастурлаштиришни симплекс жадвал усули.
РЕЖА
1. Симплекс усулда ечиш мумкин булган масалалар синфи
2. Симплекс жадвални тузиб олиш.
3. Кейинги жадвалга утиш.
4. Оптимал ечимни топиш.
5. Мисол.
Адабиётлар 1,3,5,6,7,8
Таянч иборалар. Базис, бош элемент, хал килувчи устун, хал килувчи сатр, эркли номаълум, кушимча номаълум, максимум, минимум, оптимал режа.
1. Симплекс усулда ечиш мумкин булган масалалар синфи.
Чизикли дастурлаштиришнинг умумий масаласи берилган булсин. x1,...,x2,…,xn узгарувчиларнинг шундай кийматларини топайликки,
F =c1x1+c2 x2 + ... +cn xn = (1)
функция энг катта (максимум ёки минимум) кийматга эга ва бунда куйидаги шартлар бажарилсин:
a11x1+a12x2+ ... +a1nxn ≤b1
a21x1+a22x2+ ... +a2nxn ≤b2
…………………………. (2)
am1x1+am2x2+ ... +Qmnxn≤bm
x1≥ 0, x2≥ 0, ... , xn≥ 0. (3)
Маълумки, чизикли дастурлаштиришнинг умумий масаласи тенгламалар системаси оркали ифодаланган эди. Шунинг учун (2) ни янги узгарувчилар киритиш йули билан тенглик шаклида ифодалаймиз:
a11x1+a12x2 + ... + a1nxn+ xn+1=b1
(4) тенгламалар системасини (1) ва (3) шартлар бажарилганда ечим-ларини топиш учун дастлабки симплекс жадвални (1-жадвал) тузамиз.
2. Симплекс жадвални тузиб олиш.
Бу жадвал куйидаги кетма-кетликка буйсунади.
1.Дастлабки симплекс жадвал vуйидагича тузилади:
а) "базис" устунида факатгина бирлик матрицани ташкил этувчи узгарувчилар ёзилади;
б) мос равишда узгарувчилардан олдин ёзилган cj сони шартли равишда максад функциясидаги xj узгарувчиларнинг коэффицентлари дейилади;
в) "режа" устунидаги элементлар (4) тенгламалар системасининг озод хадлари билан мос тушади. Шунинг учун базисга кирмаган узгарувчилар x1=x2 = ... xn= 0 булиб, xn+1=b1, xn+2=b2,…, xn+m=bm , каби булади.
Булар базисга кирмаган ечимдаги хар бир х нинг кийматлари оркали аникланади;
г) жадвалнинг колган элементлари (4) тенгламалар системасининг коэффициентларига тенг булади;
д) режа устунининг (m+1) - каторига чизикли формадаги максад функциясининг киймати ёзилади. Бу киймат берилган таянч режа оркали топилади.
Z0 нинг киймати куйидагича топилади:
Z0= (13)
Ci= 0 булганда z0 = 0 булади.
Zj нинг киймати с векторнинг xj га скаляр купайтмаси оркали топилади:
zj= aij, (j = ) (14)
е) (m+1) каторнинг 1 дан бошлаб k гача хамма j элементлари куйидагича топилади:
zj-cj=(cn+1a1j+cn+2a2j+...+cn+2aij+...+cn+mamj) –cj (15)
zj=0 Агар xm+1, xm+2, …,xn+m узгарувчилар максад функциясида "нол" коэффициентлар билан катнашса булса, zj-cj=-cj тенглик хамма j = лар учун уринли булади.
|
