O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XOZAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
Chiziqli algebra KAFEDRASI
2-Mustaqil ish
Bajardi: 810-20 guruh talabasi
Abdullayev Bahriddin
Tekshirdi:Xudazarov Ravshan
TOSHKENT 2021
Мавзу: Чизиқли программалаш масаласини
ечишнинг Симплекс усули.
Режа
Симплекс усул хакида кискача умумий маълумот
Симплекс усулнинг алгоритми
Баъзи иктисодий масалаларни симплекс усул ёрдамида ечиш
Мустакил ечиш учун тавсия килинган мисоллар
1.Чизиқли программалаш соҳасини илк принциплари Л.В. Конторовични “Математические методы организации и планирования производства” номли ишларида учрайди(1939й), 1947 йлда эса америка олими Данциг томонидан чизиқли программалаш масаласини умумий қўйилган.
Биз биламизки чизиқли программалаш масаласи бу чизикли функционални кўп ўлчовли фазода чизиқли чекловларни қаноатлантирган ҳолда минимум ёки максимум қийматини топишдан иборат. Бу масаладаги хар бир чизиқли чекловлар n- ўлчовли фазони (n-1)- ўлчовли ярим фазоси бўлади, демак бундан чикадики барча чизиқли чекловларни умумий ечими (мумкин бўлган режалар тўплами) n- ўлчовли фазода қавариқ кўпёқ бўлади.
Симплекс усул чизиқли программалаш масаласини мумкин бўлган режалар тўплами бўлган кўпёқни учлари орасидан оптимал ечимни топиш усулидир. Агар масалани ўзгарувчилар сони n-та чекловлар сони m-та бўлса у ҳолда кўпёқнинг учлари сони Сnm –га тенг бўлади, бу еса катта сон бўлиб, бурчакларни бирма-бир текшириб чиқиш мақсадга муофиқ эмас.
2. Умумий ҳолда берилган куйидаги чизиқли программалаш масаласини кўрайлик:
a11x1+a12x2+…+a1nxn≤b1
a21x1+a22x2+…+a2nxn≤b2
. . . . . . . . . . . . . (1)
am1x1+am2x2+…+amnxn≤bm,
x1, x2, . . . , xn≥0 шартларни қаноатлантирган ҳолда F=c1x1+c2x2+…+cnxn (2) мақсад функцияга максимал қиймат берувчи x1, x2, . . . , xn ларни топиш керак.
1-қадам. Берилган (1) тенгсизликлар системасида янги xn+1, xn+2, . . . , xn+m, мусбат ўзгарувчилар киритиб барча тенгсизликларни тенгликларга айлантириб оламиз. Бу ерда янги киритилган ўзгарувчиларни иктисодий маъноси: шу ўзгарувчи катнашган тенгсизликга мос келувчи хом ашёни ортиб қолган миқдоридир. Демак n+m- ўзгарувчили m-та чизиқли тенгламалар системасини хосил қилдик ва бу системада xn+1, xn+2, . . . , xn+m – ўзгарувчилар фақат биттадан тенгламада бир коэффициет билан иштирок этади.
2-қадам. Хосил бўлган тенгламалар системада xn+1, xn+2, . . . , xn+m – ўзгарувчиларни базис ўзгарувчилар, x1, x2, . . . , xn –ўзгарувчиларни эса эркин ўзгарувчилар деб оламиз ва базис ўзгарувчиларни эркин ўзгарувчилар орқали ифодалаймиз.
xn+1 = b1 -a11x1-a12x2-…-a1nxn
xn+2 = b2 -a21x1-a22x2-…-a2nxn
. . . . . . . . . . . . . (3)
xn+m = bm-am1x1-am2x2-…-amnxn,
бу ерда x1, x2, . . . , xn –ўзгарувчиларни барчасига 0 қиймат берсак
xn+1, xn+2, . . . , xn+m – ўзгарувчилар мос равишда b1, b2, ..., bm –қийматларни қабул қилади ва (0,0,...,0, b1, b2, ..., bm,) биринчи таянч режа бўлади.
3-қадам. Тузилган (3) системани ва (2) мақсад функцияни
қуйидаги симплекс жадвалга киритамиз.
Базис ўзгарувчилар
|
Озод ҳад
|
Эркин ўзгарувчилар
|
-x1
|
-x2
|
...
|
-xn
|
xn+1
|
b1
|
a11
|
a12
|
...
|
a1n
|
xn+2
|
b2
|
a21
|
a22
|
...
|
a2n
|
....
|
....
|
...
|
...
|
...
|
...
|
xn+m
|
bm
|
am1
|
am2
|
...
|
amn
|
F
|
0
|
-c1
|
-c2
|
...
|
-cn
|
Агар бу жадвлда F сатрдаги барча эркин ўзгарувчиларга мос келувчи элементлар, яъни -c1, -c2, ...,-cn лар мусбат бўлса бу жадвалга мос келувчи режа (0,0,...,0, b1, b2, ..., bm,) оптимал режа бўлади.
4-қадам. Агар F сатрда манфий элементлар мавжуд бўлса, у ҳолда бу режа оптимал бўлмайди ва биз бошка таянч режага ўтамиз, яъни мумкин бўлган режалар кўпёқиниг бошқа учига.бу ишни куйидагича амалга оширамиз: F сатрдаги энг кичик манфий сон жойлашган устун хал қилувчи устун бўлади ва бу устун элементлари учун ( F сатрдаги элементдан ташкари) симплекс нисбатларни ҳисоблаймиз (хар бир озод ҳадни унга мос келувчи ҳал килувчи устун элементига нисбати). Ҳосил бўлган нисбатлардан энг кичигига мос келувчи элемент ҳал қилувчи элемент бўлади.
5-қадам. Ҳал қилувчи элемент ёрдамида симплекс жадвални ўзгартирамиз. Бу ишдан мақсад ҳал элементга мос келувчи сатрдаги базис ўзгарувчи ва устунда турган эркин ўзгарувчилар алмашади. (жадвални алмаштириш алгоритми мисолда тушунтирилади).
3. Ҳалқ хўжалигининг кўп сохаларини айрим масалалари (ишлаб чикаришни режалаштириш, чорва моллари учун оптимал озуқа тайёрлаш, екин ерлага минерал ўғитлар солиш масалалари ва ҳ.қ.,) айнан чизиқли программалаш масаласига келтирилиб шу симплекс усул билан ечилади. Қуйидаги масалани кўрайлик.
Do'stlaringiz bilan baham: |