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.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
орындалған кезде максималды мәнін табу
Егер де бүтінсандық шарты кейбір айнымалыларға ғана қойылатын болса, онда есеп жартылай бүтінсанды болып есептелінеді.
Бүтінсандық программалау есептерін шешушде кең тараған әдіс – Гомори әдісі.
Гомор әдісінің алгоритмы
Бүтінсандық шартына қарамастан, есепті симплекс әдісімен шешу. Егер бүтінсанды тиімді шешім табылатын болса, есеп шешімі табылды деп санау.
Егер тиімді шешімде барлық айнымалылар бүтінсанды болмаса, қосымша шартты анықтайды (Гомори қимасы). Қима бөлшегі ең жоғары базисты айнымалы бойынша құрылады. Xt айнымалысы бөлшегі ең жоғары базисты айнымалы болсын
Xt+∑hijxj=ft, (1)
мұнда J-бос айнымалылардың индекстері. Барлық коэффициенттерді және бос айнымалыны (1) екі қосылғышқа бөлу – бүтін және бөлшек.
∑hijxj≥ft (2) теңсіздігі Гомори қимасы деп аталады. Қосымша шарт келесі түрге ие болады:
∑hijxj-xn+1≥ft (3)
(3) теңдікті алдында шешілген есепке қосып, сызықты программалау есебінің жаңа түрін анықтаймыз, оны қайта симплекс әдісімен шешеміз. Егер де оның шешімі бүтінсандық болса, осы шешім бастапқы есептің бүтінсандық шешімі болып табылады. Егер де шешім бүтінсандық болмаса, онда жаңа Гомори қимасын анықтап, әрі қарай сәйкесінше жалғастырады.
Есеп 1.
Берілген функцияның F=2X1+2X2 келесі шарттар орындалған кезде
2X1-X2≤7
-X1+2X2≤3
X1, X2≥0, X1, X2€N максимум мәнін табу.
Шешімі:
Есепті бүтінсандық шартына қарамастан, симплекс әдісімен шешеміз. Алдынала есепті негізі түріне келтіру.
2X1-X2+Х3=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)
Егер кәсіпорын көрсетілген мөлшерде құрылғыны алса, онда өнім шығарылымы мынаны құрайды
Достарыңызбен бөлісу: |