Сунъий базис киритиш ёрдамида масала шартиларни тенглик кўринишига келтирамиз



Download 239,75 Kb.
Sana24.02.2022
Hajmi239,75 Kb.
#224819
TuriПрограмма
Bog'liq
ЧПМ 2 topshiriq


Чизиқли программалаш масалалари (ЧПМ) ларни ечишда Симплекс усул моҳияти ва чизиқли программалаш масалалар бўйича топшириқ вариантларини тузиш бўйича услубий кўрсатмалар.
Мулохазаларимиз содда бўлиши учун уч ўлчовли чизиқли программалаш масалалари мисолида тахлил қиламиз.
(1)

Сунъий базис киритиш ёрдамида масала шартиларни тенглик кўринишига келтирамиз.
Мулохазаларимиз содда бўлиши учун уч ўлчовли чизиқли программалаш масалалари мисолида тахлил қиламиз.
(2)

(2) масала ечими (1) масала учун ҳам ечим бўлиши кўриниб турибди.
Бунда лар қандай бўлишидан қатъий назар, улар мақсад функциясига хеч қандай таъсир ўтказмайди.
Симплекс усулнинг моҳияти-базисни шундай танлаш керакки, бунда базис ўзгарувчилар қийматларини берсин. (2) масалада базис ўзгарувчилар бўлиб, бу базисда ўзгарувчилар қийматлари , бўлади.
Бу қийматлар (2) масала шартларини тўла қаноатлантиради, лекин мақсад функцияси эса бунда L=0 бўлади. Бу эса (1) масала ечими сифатида қабул қилиниши мумкин эмас. Симплекс усул (2) масала базисини қадамба қадам ўзгартириб айнан оптимал базис ва оптимал ечимга бориш алгоритмидан иборат.
Албатта бу йўлни бир йўла, мураккаб бўлсада, тескари матрица ёрдамида амалга ошириш мумкин. Мантиқан ўйлаганда базис сифатида асосий (1) масала ўзгарувчиларини олган маъқуллиги кўриниб турибди. Аксарият холларда шундай бўлади ҳам. Буни берилган мисол намунасида текшириб кўрамиз.

  1. Масала нормативлар матрицаси


Учун тескари матрицани топамиз


  1. Масалани матрица кўринишида ифодалаб икки тарафдан га кўпайтириб юборамиз. Бу холда

(3)
кўринишни олади. (3) Масала ҳам (1), (2) масалага эквивалент бўлиб унинг ечимлари
бўлади.
Бунда мақсад функцияси максимал қийматиLmax=15*10+20*13+24*15=770 эканлигини кўрамиз.
Айнан шу масалани Симплекс усулида ечиш жараёнини кўриб чиқайлик. Биринчи Симплекс жадвал (2) масала асосида тузилади:



Базис

Сi

15

20

24

0

0

0

bi



A1

A2

A3

A4

A5

A6

A4

0

3

7

5

1

0

0

196

39,2

A5

0

6

4

3

0

1

0

157

52,3

A6

0

2

3

8++

0

0

1

179

22,38






-15

-20

-24

0

0

0

0
















---------
















2- Симплекс жадвал




Базис

Сi

15

20

24

0

0

0

bi



A1

A2

A3

A4

A5

A6

A4

0

1,75

5,125++

0

1

0

-0,625

84,1

16,41

A5

0

5,25

2,875

0

0

1

-0,375

89,86

31,25

A3

24

0,25

0,375

1

0

0

0,125

22,38

59,68






-9

-11

0

0

0

3

537,12













----------




















3- Симплекс жадвал

Базис

Сi

15

20

24

0

0

0

bi



A1

A2

A3

A4

A5

A6

A2

20

0,341

1

0

0,195

0

-0,122

16,41

48,1

A5

0

4,27++

0

0

-0,561

1

-0,024

42,681

9,996

A3

24

0,122

0

1

-0,073

0

0,171

16,226

133






-5,252

0

0

2,148

0

14,6

717,624










-------------























4- Симплекс жадвал

Базис

Сi

15

20

24

0

0

0

bi



A1

A2

A3

A4

A5

A6

A2

20

0

1

0

0,24

-0,08

-0,12

13,001




A1

15

1

0

0

-0,132

0,234

-0,006

9,936




A3

24

0

0

1

-0,057

-0,028

0,172

15,006









0

0

0

1,452

1,238

1,638

770,111

































Бу жадвалда барча бўлгани учун унга мос ечим


Оптимал ечим бўлади. Мақсад функцияси қиймати бу холда ўз максимал қиймати Lmax=770,111 га эришади.
4- Симплекс жадвалқийматларини (3) масала коэффицентлари билан солиштирсак улар бир хил эканлигини кўрамиз (фарқ ҳисоблашдаги яхлитлаш хатолиги ҳисобига).
Бундан албатта 1- усул маъқул экан деган хулосага бориш керак эмас. Тескари матрица топиш жараёни анча меҳнат талаб қилади. Ундан ташқари танланган базис оптимал бўлмай қолса барчасини башқатдан бажаришга тўғри келади.
Агар масала
(4)
Кўринишда берилган бўлса, мумкин бўлган базислар сони
формула бўйича ҳисобланади. Хаттоки биз кўрган (2) масалада ҳам n=6; m=3 та вариант бор. Симплекс усул эса хар қадамда аввалгисидан самаралироқ базисни танлаш йўлидан боради. Шунинг учун бу усулда барча базисларни кўриб чиқишга зарурат қолмайди.
Симплекс усули афзалликларидан яна бири, бу усулда бир йўла эгизак масала ечимлари ҳам хосил бўлар экан. Берилган (1) масала учун эгизак масала тузамиз:
(5)

Чизиқли программалаш масалаларучун иккиланганлик теоремасига кўра (1) масала ечими мавжуд бўлса эгизак масала (5) нинг ҳам ечими мавжуд бўлади ва Lmax = Qmin бўлади. Агар масала симплекс усулида ишланса сўнгги жадвал охирги қаторга сунъий базис усулларида эгизак масала ечимлари келиб чиқар экан. Бизнинг мисолда
эканини кўрамиз.
Бу қийматларда Q ни ҳисоблансин. келиб чиқади, яъни Lmax = Qmin орадаги фарқ, яна яхлитлаш хатоликлари ҳисобига пайдо бўлган дейиш мумкин.
Яна бир турдаги чизиқли программалаш масалаларини ечиш жараёнини таҳлил қиламиз. Бунда барча шартлар тенглик кўринишда берилган бўлиб, бошланғич базис танлаш ва масала шартларини ана шу танланган базисга мослаштириш жараёнини ҳам киритишга тўғри келади. Буни қуйидаги масалада намойиш қиламиз.
(2)

Бу масалада n=4; m=3 бўлиб базис ўзгарувчилар сони 3 га тенг бўлади. Базис танлаш вариантлар сони эса га тенг. Базис танлашда тавсиялардан бири нисбатан арзонроқ махсулотга мос ўзгарувчини базисга киритмаслик йўлидан борган маъқул. Бизда С4= 10 энг арзони, демак х4 ни базисга киритмаганлик маъқул. Демак базис сифатида ларни олиш мумкин. Масала шартларини шу танланган базисга мослаштириш учун нормативлар матрицасидан ана шу ўзгарувчиларга мос қисмини базис матрица сифатида олиб унга тескари матрицани топамиз.

Унга тескари матрицани топамиз:

Матрица шартлари кенгайтирилган матрицасини ана шу тескари матрицага кўпайтирамиз


Натижада берилган масала қуйидаги эквивалент кўринишга ўтади.

Бу масала учун биринчи Симплекс жадвал қуйидаги кўринишда бўлади.


Базис

Сi

25

22

24

10

bi



A1

A2

A3

A4

A4

25

1

0

0

0,7452

11




A2

22

0

1

0

0,7452

15




A3

24

0

0

1

0,4038

12









0

0

0

34,7156

893



Бу жадвалда барча . Шунинг учун бу жадвалга мос ечим оптимал ечим бўлади. Бунда Lmax=893 даромад бўлар экан.


Эслатма. Агар 1- Симплекс жадвалда бирорта < 0 бўлиб қолса базисни алмаштиришга тўғри келган бўлар эди. Унда 2- Симплекс жадвал тузишга тўғри келар эди.
Бизда танланган базис омадли бўлиб биринчи қадамнинг ўзиёқ оптимал ечимга эришишдик.
Чизиқли программалаш масалалари бўйича топшириқ вариантларини тузиш бўйича услубий кўрсатмалар.
Учта турдаги уч хил ҳом ашё асосида тайёрланадиган уч ҳил махсулот учун ҳом ашё сарфлари нормативлари матрицасини тузамиз. Бунда имкон даражасидан матрица устун элементлари йиғиндиси бир бирига яқинроқ танлагани маъқул. Сўнгра ишлаб чиқариладиган махсулотларнинг сонларини ихтиёрий танлаймиз. Ҳом ашё захираларини эса ана шу қийматлар ва норматив матрицаси асосида ҳисоблаб аниқлаймиз.Мақсад функциясини эса махсулот сонларига қараб танлаш мумкин. Бунда аксарият холларда оптимал ечим биз белгиланган махсулотлар сонига мос келади. Намуна сифатида қуйидаги мисолни кўрамиз. Нормативлар матрицаси:


Махсулотлар сонини эса деб белгиласак ҳом ашё захиралари эса мос равишда:

Қийматларга тенг бўлади. Маҳсулот нархларини эса мос равишда пул бирлиги қилиб белгилаймиз (нархлар махсулот сонига мутаносиб тарзда олинди).
Шундай қилиб берилган масала математик модели чизиқли программалаш масалаларини ҳосил қиламиз.


Бу масала ечимини юқорида тўла таҳлил қилдик. Келтирилган мулохазалар асосида ишончли, ечимлари аввалдан маълум бўлган топшириқ вариантларини тузиш мумкин.

1-

2-

3-

4-

5-

6-

7-

8-

9-

10-


Қуйидаги чизиқли программалаш масалалар учун бошланғич базисни танланг, масала шартларини танланган базисга мослаштиринг, Симплекс усули асосида оптимал ечимини топинг.

11-

12-

13-

14-

15-

16-

17-
( ).
.
18-

19-

20-

21-

22-

23-

24-

25-

26-

27-


28-


29-


30-




Вариант жавоблари:

1. Lmax=717
2. Lmax=857
3. Lmax=464
4. Lmax=1327
5. Lmax=1073
6. Lmax=841
7. Lmax=729
8. Lmax=1169
9. Lmax=776
10. Lmax=741
11. Lmax=889
12. Lmax=1552
13. Lmax=1210
14. Lmax=1467
15. Lmax=1129
16. Lmax=889
17.
20. Lmax=741
21. Lmax=870
22. Lmax=728
23. Lmax=737
24. Lmax=870
25. Lmax=741
26. Lmax=728
27. Lmax=729
28. Lmax=1169
29. Lmax=1210
30. Lmax=1467

Download 239,75 Kb.

Do'stlaringiz bilan baham:




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