Чизиқли дастурлаш масалалари. Чизиқли дастурлаш масалаларини ечишнинг симплекс усулини С++ да бажариш



Download 24,88 Kb.
bet1/2
Sana24.02.2022
Hajmi24,88 Kb.
#224806
TuriПрограмма
  1   2
Bog'liq
×èçè ëè ïðîãðàììàëàø ìàñàëàñèíè å÷èøíèíã Ñèìïëåêñ óñóëè


Чизиқли дастурлаш масалалари. Чизиқли дастурлаш масалаларини ечишнинг симплекс усулини С++ да бажариш (аниқ битта мисолда кўрсатиш).
Чизиқли программалаш соҳасини илк принциплари Л.В. Конторовични “Математические методы организации и планирования производства” номли ишларида учрайди(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,) оптимал режа бўлади.



Download 24,88 Kb.

Do'stlaringiz bilan baham:
  1   2




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish