2-машғулот. Чизикли программалаштириш масаласини ечишининг симплекс–усули


Download 391.06 Kb.
bet3/3
Sana05.04.2023
Hajmi391.06 Kb.
#1274008
TuriПрограмма
1   2   3
Bog'liq
4 Amaliy mashg'ulot

Симплекс-усул алгоритми


Чизиқли программалаштириш масаласини симплекс-усул ёрдамида ечиш учун қуйидаги алгоритм ишлатилади.


1. ни топиш. A матрицани ва b векторни дастлабки базисда ёзиш, яъни , (x – вектор базис план бўлгани учун охирги формула ўринлидир).
2. Ҳар бир j (j=1,2,...,n) учун баҳолаларни ҳисоблаш:
.
Агар барча бўлса, масални ечиш жараёнини тўхтатиш: қаралаётган базис план оптималдир – zmax= . Агар бирорта j учун бўлса, у ҳолда
3. Шундай баҳони излаш керакки, барча k=1,2,...,m лар учун бўлсин. Агар шундай мавжуд бўлса, масалани ечиш жараёнини тўхтатиш. Мақсад функцияси планлар тўпламида юқоридан чегараланмаган. Агар бундай мавжуд бўлмаса, у ҳолда
4. Бирорта ни (одатда ) танлаш. Барча шартни қаноатлантирувчи k учун ни ҳисоблаш ва булар ичидан энг кичигини топиш ( бўлсин).
5. Янги базис планга ўтиш.
2- кадамга ўтиш.
Алгоритм тугади.
Ҳар бир янги базис паланга ўтиш кадам (итерация) деб аталади.

  1. Симплекс-усулни жадваллар ёрдамида қўллаш



Чизиқли программалаштириш масаласини симплекс усул ёрдамида ечишни жадвал ёрдамида ҳам бажарса бўлади. Бунинг учун ҳар бир итерацияда янги симплекс жадвал тузилади.

c\c







c1

c2

. . .

cs

. . .

cn







a\а

b

a1

a2

. . .

as

. . .

an

j





x10

x11

x12

. . .

x1s

. . .

x1n








x20

x21

x22

. . .

x2s

. . .

x2n




. . .

. . .

. .

. . .

. . .

. . .

. . .

. . .

. . .








xr0

xr1

xr2

. . .

xrs




xrn




. . .

. . .

. ..

. . .

. . .

. . .

. . .

. . .

. . .








xm0

xm1

xm2

. . .

xms

. . .

xmn









z

1

2

. . .

s

. . .

n




Янги симплекс-жадвал тузиш учун тўғри тўртбурчак қоидаси қўлланилади. Бу қоидани -баҳолар қатори учун ҳам қўллаш мумкин.


Мисол.
z=2x1-x2+3x3+2x4  max, 2x1+3x2-x3+2x4+x5=4,
x1-2x2+5x3-3x4-x6=1, 4x1+10x2+3x3+x4+x7=8,
xj0, j=1,2,...,7,
масалани қараймиз. Бу чизиқли программалаштириш масаласининг дастлабки базис плани (1;0;0;0;2;0;4) маълум бўлсин. Бу масала учун m=3, n=7,
,
c'=(2;-1;3;2;0;0;0), rankA=3. Дастлабки базис план учун базис матрица , унинг тескариси . матрицани ҳисоблаб дастлабки симплекс –жадвал тузамиз:




c







2

-1

3

2

0

0

0







a\a

b

a1

a2

a3

a4

a5

a6

a7



2

a1

1

1

-2

5

-3

0

-1

0




0

a5

2

0

7

-11

8

1

2

0

1 /4

0

a7

4

0

18

-17

13

0

4

1

4/13






2

0

-3

7

-8

0

-2

0




Бу жадвалдан дастлабки базис планинг оптимал эмаслиги кўкриниб турибди (баҳолар вектори кординаталари ичида манфийлари бор).


Максад функциясининг чегараланмаганлиги ҳақидаги теорема шартлари бажарилмайди. Шунинг учун min 4, s=4 эканлигини аниқлаб ; ни топамиз. xrs=8 – ҳал қилувчи элементдан фойдаланиб янги симплекс жадвал тузамиз.



c







2

-1

3

2

0

0

0







a\a

b

a1

a2

a3

a4

a5

a6

a7



2

a1

7/4

1

5/8

7/8

0

3/8

-1/4

0

2

2

a4

1/4

0

7/8

-11/8

1

1/8

1/4

0




0

a7

3/4

0

53/8

7/8

0

-13/8

3/4

1

6/7






4

0

4

-4

0

1

0

0




Бу жадвалдан янги базис план (7/4; 0;0;1/4; 0;0;3/4) эканлигини, мақсад функцияси қиймати 4 эканлигини, ҳамда бу базис планнинг оптимал план эмаслигини аниқлаймиз. Яна икки итерациядан сўнг қуйидаги симплекс-жадвал ҳосил қиламиз.





c







2

-1

3

2

0

0

0




a\a

b

a1

a2

a3

a4

a5

a6

a7

0

a5

1/2

1/2

-3

0

0

1

-1/2

-1/2

2

a4

37/14

17/4

4

0

1

0

3/14

5/14

3

a3

25/14

13/14

2

1

0

0

-1/14

3/14






149/14

45/14

15

0

0

0

3/14

19/14

Охириги симплекс жадвалда баҳолар манфиймас бўлгани учун қаралаётган масаланинг оптимал плани x0=(0;0;25/14;37/14;1/2;0;0) бўлиб, мақсад функциясининг оптимал қиймати zmax=149/14 га тенг.




Муаммоли масала ва топшириқлар

Қуйидаги чизиқли программалаштириш масалаларини симплекс усули ёрдамид ҳал қилинг:


1.


2.
3. ;
4.





  1. )

7) 4)

8) 6 )

9)

10)


Мустақил ишлаш учун назорат саволлари



  1. Симплекс усулнинг дастлабки қадамида қандай ишлар бажарилади?

  2. Баҳолар қандай ҳисобланади?

  3. Қаралаётган базис план оптимал бўлиши учун қандай шартлар бажарилиши керак?

  4. Қандай шартлар бажарилса мақсад функцияси чегараланмаган деган хулоса қилиш мумкин?

  5. Янги базис планга ўтиш учун қандай ишлар бажарилади?

  6. Бошланғич базис план қандай тузилади?

Download 391.06 Kb.

Do'stlaringiz bilan baham:
1   2   3




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