Т оптимизация әдістері пәнінен практикум



бет13/40
Дата31.01.2018
өлшемі5,39 Mb.
#37032
1   ...   9   10   11   12   13   14   15   16   ...   40

8. Қорытынды

280 ақшалай бірлік мөлшерінде минималды табысты алу үшін, бірінші тасымалдаушы 60 бірлікке тең жүкті, екінші тұтынушыға жіберуі тиіс, екінші тасымалдаушы үшінші (20 бірлік) және төртінші (60 бірлік) тұтынушылар арасында жүкті бөледі, үшінші тасымалдаушы бірінші тұтынушыға – 40 бірлік, үшінші тұтынушыға – 60 бірлік қорды жібереді.


Өзіндік тапсырмалар

Тапсырма 1

Берілген жүк тасымалдау есебінің бастапқы тірек жоспарын солтүстік-батыс бұрышы әдісімен табу.





Тасымалдаушылар


Тұтынушылар

Қоры

B1

B2

B3

B4

A1

5

15

10

9

60

A2

8

10

9

7

110

A3

7

6

6

9

170

А4

11

5

7

12

160

Қажеттіліктері

210

50

90

150





Тапсырма 2

Берілген жүк тасымалдау есебінің бастапқы тірек жоспарын солтүстік-батыс бұрышы әдісімен табу.




Тасымалдаушылар


Тұтынушылар

Қоры

B1

B2

B3

B4

A1

7

12

18

19

80

A2

7

13

11

11

12

A3

19

18

12

13

38

А4

11

3

11

4

45

Қажеттіліктері

10

20

40

75





Тапсырма 3

Берілген жүк тасымалдау есебінің бастапқы тірек жоспарын кіші элементтер әдісімен табу.




Тасымалдаушылар


Тұтынушылар

Қоры

B1

B2

B3

B4

A1

4

7

10

7

50

A2

6

7

9

10

70

A3

5

12

4

3

120

А4

3

8

8

6

140

Қажеттіліктері

180

100

40

80





Тапсырма 4

Берілген жүк тасымалдау есебінің тиімді шешімін потенциалдар әдісімен табу.




Тасымалдаушылар


Тұтынушылар

Қоры

B1

B2

B3

B4

A1

5

3

12

4

180

A2

2

3

9

5

70

A3

7

5

9

6

20

Қажеттіліктері

40

130

110

50





Тапсырма 5

Берілген жүк тасымалдау есебінің тиімді шешімін потенциалдар әдісімен табу.




Тасымалдаушылар


Тұтынушылар

Қоры

B1

B2

B3

B4

A1

3

6

8

6

200

A2

4

4

9

12

150

A3

5

6

7

11

90

А4

6

7

8

2

120

Қажеттіліктері

180

320

60

110





Бақылау сұрақтары

  1. Жүк тасымалдау есебінің жалпы қойылымы неде?

  2. Жүк тасымалдау есебінің ашық және жабық түрлеріне анықтама беріңіз.

  3. Жүк тасымалдау есебінің бастапқы тірек жоспары дегеніміз не?

  4. Жүк тасымалдау есебінің бастапқы тірек жоспары қалай табылады?

  5. Цикл дегеніміз не?

  6. Циклды құрастыру ережелерін анықтаңыз.

  7. Потенциалдар әдісінің алгоритмын атап өтіңіз.


Тест тапсырмалары
1.1. Жүк тасымалдау есебі қай жағдайда ашық деп аталады?

A) егер барлық тұтынушылардың талаптары толық орындалуға тиісті болса

B) егер жабдықтаушылардың қорларының жинағы тұтынушылардың барлық қажеттілігінен көп болса

C) егер жабдықтаушылардың қорларының жинағы тұтынушылардың барлық қажеттілігінен аз болса

D) B және C жауаптары

E) дұрыс жауабы жоқ

**********
1.2. Жүк тасымалдау есебі қай жағдайда жабық деп аталады?

A) егер барлық тұтынушылардың талаптары толық орындалуға тиісті болса

B) егер жабдықтаушылардың қорларының жинағы тұтынушылардың барлық қажеттілігінен көп болса

C) егер жабдықтаушылардың қорларының жинағы тұтынушылардың барлық қажеттілігінен аз болса

D) B және C жауаптары

E) дұрыс жауабы жоқ

**********
1.3. Жүк тасымалдау есебінің бастапқы тірек жоспарын қай әдістермен табуға болады?

A) кіші элементтер әдісімен

B) солтүстік-батыс бұрышы әдісімен

C) потенциалдар әдісімен

D) А және B жауаптары

E) А, B және С жауаптары

**********
1.4. Жүк тасымалдау есебінің шешімі қай әдіспен табылады?

A) кіші элементтер әдісімен

B) солтүстік-батыс бұрышы әдісімен

C) потенциалдар әдісімен

D) А және B жауаптары

E) А, B және С жауаптары

**********
1.5. Берілген жүк тасымалдау есебінің анықталған тірек жоспарға сәйкес тасымалдау шығыны нешеге тең?





В1

В2

В3

В4

Қорлары

А1

6

5

30


4

10


3

40

А2

7

3

2

10


1

10


20

А3

2

30


3

5


4

5

35

А4

8

9

25


5

10

25

Сұранысы

30

60

20

10

120

A) 120


B) 480

C) 520


D) 500

E) 510


**********
1.6. Берілген жүк тасымалдау есебінің анықталған тірек жоспарға сәйкес тасымалдау шығыны нешеге тең?




В1

В2

В3

В4

Қорлары

А1

6

30


5

10


4


3

40

А2

7

3

20


2


1


20

А3

2


3

30


4

5


5

35

А4

8

9


5

15


10

10


25

Сұранысы

30

60

20

10

120

A) 500


B) 515

C) 575


D) 485

E) 555


**********
1.7. Жүк тасымалдау есебінің бастапқы тірек жоспары қай әдіспен анықталған?




В1

В2

В3

В4

Қорлары

А1

6

30


5

10


4


3

40

А2

7

3

20


2


1


20

А3

2


3

30


4

5


5

35

А4

8

9


5

15


10

10


25

Сұранысы

30

60

20

10

120

A) кіші элементтер әдісімен

B) солтүстік-батыс бұрышы әдісімен

C) қосалқы әдіс

D) потенциалдар әдісі

E) аппроксимация әдісі

**********
1.8. Жүк тасымалдау есебінің бастапқы тірек жоспары қай әдіспен анықталған?





В1

В2

В3

В4

Қорлары

А1

6

5

30


4

10


3

40

А2

7

3

2

10


1

10


20

А3

2

30


3

5


4

5

35

А4

8

9

25


5

10

25

Сұранысы

30

60

20

10

120

A) кіші элементтер әдісімен

B) солтүстік-батыс бұрышы әдісімен

C) қосалқы әдіс

D) потенциалдар әдісі

E) аппроксимация әдісі

**********


1.9. Жүк тасымалдау есебін шешу кезінде бос тордың бағасы қалай анықталады?

A) ij=ui+cij+vj+xij

B) ij=ui+cij-vj+xij

C) ij=ui+cij-vj

D) ij=ui+cij-xij

E) ij=ui+cij+vj-xij

**********
1.10. Жүк тасымалдау есебі берілген.





В1

В2

В3

В4

В5

Қорлары

U

А1

2

60


3

4

2

80


4

140

0

А2
















180

-4

А3
















160

-5

Сұранысы

60

70

120

130

100

480




V

2

2

-3

2

-3







(1;2) торға сәйкес келетін 12 бағаны анықтау

A) 2


B) 5

C) 1


D) 0

E) -1


**********

Тақырып 4. Бүтінсандық программалау есептері. Гомори әдісі.
Негізгі ұғымдар
Көбінесе экономикалық есептерде айнымалылар бөлінбейтін объектілерді сипаттайды, сондықтан олар нағыз түрде анықталуы жөн. Бұндай есептерде айнымалыларға бүтінсандық талабы қойылады.

Бүтінсандық есептің қойылымы келесіде: F=∑cjxj функцияның келесі шарттар

∑ajxj=bi, i=1,m

xj≥0, xj€N, j=1,n

орындалған кезде максималды мәнін табу

Егер де бүтінсандық шарты кейбір айнымалыларға ғана қойылатын болса, онда есеп жартылай бүтінсанды болып есептелінеді.

Бүтінсандық программалау есептерін шешушде кең тараған әдіс – Гомори әдісі.

Гомор әдісінің алгоритмы



  1. Бүтінсандық шартына қарамастан, есепті симплекс әдісімен шешу. Егер бүтінсанды тиімді шешім табылатын болса, есеп шешімі табылды деп санау.

  2. Егер тиімді шешімде барлық айнымалылар бүтінсанды болмаса, қосымша шартты анықтайды (Гомори қимасы). Қима бөлшегі ең жоғары базисты айнымалы бойынша құрылады. Xt айнымалысы бөлшегі ең жоғары базисты айнымалы болсын

Xt+∑hijxj=ft, (1)

мұнда J-бос айнымалылардың индекстері. Барлық коэффициенттерді және бос айнымалыны (1) екі қосылғышқа бөлу – бүтін және бөлшек.

∑hijxj≥ft (2) теңсіздігі Гомори қимасы деп аталады. Қосымша шарт келесі түрге ие болады:

∑hijxj-xn+1≥ft (3)



  1. (3) теңдікті алдында шешілген есепке қосып, сызықты программалау есебінің жаңа түрін анықтаймыз, оны қайта симплекс әдісімен шешеміз. Егер де оның шешімі бүтінсандық болса, осы шешім бастапқы есептің бүтінсандық шешімі болып табылады. Егер де шешім бүтінсандық болмаса, онда жаңа Гомори қимасын анықтап, әрі қарай сәйкесінше жалғастырады.


Есеп 1.

Берілген функцияның F=2X1+2X2 келесі шарттар орындалған кезде

2X1-X2≤7

-X1+2X2≤3

X1, X2≥0, X1, X2€N максимум мәнін табу.

Шешімі:

Есепті бүтінсандық шартына қарамастан, симплекс әдісімен шешеміз. Алдынала есепті негізі түріне келтіру.

2X1-X23=7

-X1+2X2+X4=3



X1, X2, X3, X4≥0


Базис

Сб

В

2

2

0

0

Х1

Х2

Х3

Х4

Х3

0

7

2

-1

1

0

Х4

0

3

-1

2

0

1

j

0

-2

-2

0

0

Х1

2

7/2

1

-1/2

1/2

0

Х4

0

13/2

0

3/2

1/2

1

j

7

0

-3

1

0

Х1

2

17/3

1

0

2/3

1/3

Х2

2

13/3

0

1

1/3

2/3

j

20

0

0

2

2

Хт=(17/3; 13/3; 0; 0), Fmax=20.

Шешім бүтінсандық емес, сондықтан Гомори қимасын анықтаймыз. Соңғы симплекс кестесінен бірінші теңдеуді аламыз, себебі Х1 айнымалысының бөлшегі ең жоғары (17/3=2/3, 13/3=1/3)

Х1+2/3Х3+1/3Х4=17/3

Қима келесі түрге ие болады 2/3X3+1/3X4≥2/3 немесе 2/3X3+1/3X4-X5=2/3, мұнда Х5≥0.

Осы соңғы шартты соңғы симплекс кестесінің шарттарын қосып, жаңа есепті анықтаймыз:

X1+2/3X3+1/3X4=17/3

X2+1/3X3+2/3X4=13/3

2/3X3+1/3X4-X5=2/3

Xj≥0, j=1,5

Есептің шешімін симплекс әдісімен табамыз.


Базис

Сб

В

2

2

0

0

0

Х1

Х2

Х3

Х4

Х5







17/3

1

0

2/3

1/3

0

Х1

2

13/3

0

1

1/3

2/3

0

Х2

2

2/3

0

0

2/3

1/3

-1

Х1

2

5

1

0

0

0

1

Х2

2

4

0

1

0

½

½

Х3

0

1

0

0

1

½

-3/2

j

18

0

0

0

1

3

Хт=(5; 4; 1; 0; 0), Fmax=18.

Анықталған шешім бүтінсанды, бастапқы есептің шешімі Хт=(5; 4), Fmax=18.

Есеп 2.

19/3м3 ауданды кәсіпорын цехнде қосалқы құрылғы қою үшін берілд. Екі түрлі құрылғыны сатып алу үшін кәсіпорын 10мың руб. жұмсай алады. Құрылғының I ші түрінің бір комплекті 1000 руб. Тұрады, ал II түрі 3000 руб. тұрады. Құрылғының I-ші түрінің бір комплекті бірінші ауысым екі бірлікке, ал II түрдің бір комплекі өнімнің шығаруын төрт бірлікке өсіреді. Құрылғының I-ші түрінің орнату үшін 2м2 аудан қажет, ал II-ші түрдің орнату үшін 1м2 аудан қажет екенің біле тұра, қосалқы құрылғының қайсысы өнімнің максималды өсуіне мүмкіндік туғызатының анықтау.



Шешімі.

Есептің математикалық моделін құрастырамыз. Кәсіпорын х1 комплект I-ші түрлі және х2 II-ші түрлі құрылғыны алды деп санайық. Онда х1 және х2 айнымалылары келесі теңсіздікті қанағаттандыру керек:



(1)

Егер кәсіпорын көрсетілген мөлшерде құрылғыны алса, онда өнім шығарылымы мынаны құрайды



Достарыңызбен бөлісу:
1   ...   9   10   11   12   13   14   15   16   ...   40




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет