Транспорттық есеп

Мазмұны:

Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..4

1 Қарапайым актілерді белгілеп көрсету ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .5
2 Жалпы математикалық модельді құру, мақсатты функцияны таңдау және негіздеу ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5
3 Алгоритмнің маңызды ойын баяндау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...5
3.1 Солтүстік.батыс және минималдау әдісі ... ... ... ... ... ... ... ... ... ... ... ... ...6
3.2 Потенциалдау әдісі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..6
4 Оңтайландыру есебінің айқын математикалық өрнегінің өңделіп, жетілдіруі, оның сандық түрдегі шешімі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...7
5 Программа листингісі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...12
Программаны баяндау бөлімі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...22

Қорытынды ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 23

Қолданылған әдебиеттер ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..24

Қосымшалар ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...25

Кіріспе

Электронды есептеуіш машинаның шығуымен байланысты жаңа ғылыми-техникалық революция ғылымның жаңа даму бағытын орнатты. Осындай бағыттардың бірі – операцияны зерттеу ғылымы.
Операция дегеніміз – белгілі мақсатқа жеткізетін және нақты ниетпен біріктірілген шаралар жиынтығы. Операциялар: басқарылатын және басқарылмайтын болады.
Операцияны зерттеу дегеніміз – автоматтандырылған басқару жүйесіндегі басқару есептерін шешуге қолданатын ғылыми тәсіл. Операцияны зерттеу методологиясы негізгі мына топтарға бөлінеді:
- анықтамалар, кезеңдер, принциптер, есептер;
- операцияны зерттеудің математикалық әдістері. Оған сызықтық бағдарламалау, транспорттық, дискреттік бағдарламалау, бейсызықтық бағдарламалау, динамикалық бағдарламалау, ойындар теориясы кіреді;
- АБЖ жобалау кезіндегі операцияларды зерттеудің әдістерін қолдану. Онда АБЖ-ң алгоритмін қамтамасыз ету, информациямен АБЖ-ны қамтамасыз ету, техникалық қамтамасыз ету керек.
Сызықтық программалау, практикаға маңызды сызықтық функцияның, сызықтық теңсіздіктер немесе теңдеулер түріндегі шектеулердің бар болу кезіндегі максимумын (минимумын) табу, экстремумдық есептерді шешудің классикалық әдістері қажет болмай қалған есебін зерттейді.
Қазіргі уақытқа дейін сызықтық программалаудың ең қарапайым есептерінің бірі, кең тарағаны – транспорттық есеп. Яғни, жүктердің жіберу пункттерінен олардың бару пункттеріне біріктірудің, жүкті тасымалдаудың шығын бағасы минимиза-цияланатын есеп. Оны шешу үшін сызықтық программалау есептерінің барлығына ортақ симплекс әдісінен кішірек болатын сызықтық программалаудың арнайы әдістері қолданылады. Транспорттық есепті шешудің ең танымал әдістеріне потен-циал, солтүстік-батыс, минимал элемент әдістері жатады.

Қолданылған әдебиеттер:

Калихман И.Л. «Сборник задач по математическому программированию»,М,ВШ,75
Таха Х. «Введение в исследование операций»,М,МИР,85

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 23 бет
Таңдаулыға:

ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ

Техникалық кибернетика кафедрасы

Курстық жұмыс

ТРАНСПОРТТЫҚ ЕСЕП

Тексерген:
Орындаған:

Мазмұны:

Кіріспе ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... ... ... ... ... ... ..4
1 Қарапайым актілерді белгілеп
көрсету ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
5
2 Жалпы математикалық модельді құру, мақсатты функцияны таңдау және
негіздеу ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... ... ... ... ... ... .5
3 Алгоритмнің маңызды ойын
баяндау ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
..5
3.1 Солтүстік-батыс және минималдау
әдісі ... ... ... ... ... ... ... .. ... ... ... ... ... .6
3.2 Потенциалдау
әдісі ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ...6
4 Оңтайландыру есебінің айқын математикалық өрнегінің өңделіп, жетілдіруі,
оның сандық түрдегі
шешімі ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... .7
5 Программа
листингісі ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... .12
Программаны баяндау
бөлімі ... ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... .22
Қорытынды ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... ... ... ... ..23
Қолданылған
әдебиеттер ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... 24
Қосымшалар ... ... ... ... ... ... . ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... ... ... ... ..25

Есептің қойлымы

Үш А1,А2,А3 теміржол станцияларында 120,110,және 130 жүк тиелген
вагондар
тұрып қалды. Бұл вагондар міндетті түрде В1,В2,В3,В4,В5 темір жол
бекеттерінежіберу керек.

2 4 1 6 7
С= 3 3 5 4 2
8 9 6 3 4
Бекеттерге әр вагонның қажеттілігі 80,60,70,100 және 50. А2 теміржол
бекетінен В2 және В4 бекеттеріне вагондарды жеткізу мүмкін еместігін
ескеріп және бір вагонның жеткізу тарифы С матрицасымен анықталатынын
біле тұра, тасымалдаудың жалпы құны сіз болатын жоспарды құру керек.

Кіріспе

Электронды есептеуіш машинаның шығуымен байланысты жаңа ғылыми-
техникалық революция ғылымның жаңа даму бағытын орнатты. Осындай
бағыттардың бірі – операцияны зерттеу ғылымы.
Операция дегеніміз – белгілі мақсатқа жеткізетін және нақты ниетпен
біріктірілген шаралар жиынтығы. Операциялар: басқарылатын және
басқарылмайтын болады.
Операцияны зерттеу дегеніміз – автоматтандырылған басқару жүйесіндегі
басқару есептерін шешуге қолданатын ғылыми тәсіл. Операцияны зерттеу
методологиясы негізгі мына топтарға бөлінеді:
- анықтамалар, кезеңдер, принциптер, есептер;
- операцияны зерттеудің математикалық әдістері. Оған сызықтық
бағдарламалау, транспорттық, дискреттік бағдарламалау, бейсызықтық
бағдарламалау, динамикалық бағдарламалау, ойындар теориясы кіреді;
- АБЖ жобалау кезіндегі операцияларды зерттеудің әдістерін қолдану. Онда
АБЖ-ң алгоритмін қамтамасыз ету, информациямен АБЖ-ны қамтамасыз ету,
техникалық қамтамасыз ету керек.
Сызықтық программалау, практикаға маңызды сызықтық функцияның, сызықтық
теңсіздіктер немесе теңдеулер түріндегі шектеулердің бар болу кезіндегі
максимумын (минимумын) табу, экстремумдық есептерді шешудің классикалық
әдістері қажет болмай қалған есебін зерттейді.
Қазіргі уақытқа дейін сызықтық программалаудың ең қарапайым есептерінің
бірі, кең тарағаны – транспорттық есеп. Яғни, жүктердің жіберу пункттерінен
олардың бару пункттеріне біріктірудің, жүкті тасымалдаудың шығын бағасы
минимиза-цияланатын есеп. Оны шешу үшін сызықтық программалау есептерінің
барлығына ортақ симплекс әдісінен кішірек болатын сызықтық программалаудың
арнайы әдістері қолданылады. Транспорттық есепті шешудің ең танымал
әдістеріне потен-циал, солтүстік-батыс, минимал элемент әдістері жатады.

1 Қарапайым актілерді белгілеп көрсету

• а) Үш теміржол станцияларындағы жүктердің шектілігі ескеру (A1,A2,A3).
• ә) В1,В2,В3,В4,В5 темір жол бекеттеріне қажетті жүктермен қамтамасыз ету.
• б) А2 темір жол бекетінен В2,В4 темір жол бекетіне жүкті жеткізу мүмкін
еместігін ескеру.
• в) Тасымалдау құныныңаз болуын қамтамасыз ету.

2 Жалпы математикалық
модельді құру, мақсатты функцияны таңдау және негіздеу

Келесі белгілеуді енгізейік:
- i карьерінен j құрылыс алаңына жіберілетін құмның мөлшері.
- карьердің номері;
- құрылыс алаңның номері;
- i-ші карьерден жіберілетін құмның мөлшері;
- j-ші құрылыс алаңына қажет құмның мөлшері;
Мақсатты функция келесі түрде болады:

Карьердегі құм толығымен тасылуы керек:

Құрылыс алаңы толығымен қамтамасыз етілуі керек:

3 Алгоритмнің маңызды ойын баяндау

Транспорттық есеп дегеніміз – тасымалдау құны ең аз болатын жүктерді
жіберу пунктерінен қабылдау пунктеріне тасымалдау.
(1)
(2)
(3)
(4)
Есепті қарастырсақ, онда (1) мақсатты функция транспорт шығынының
минимумын көрсетеді. (2) шектеулер жіберу пунктерінің өндіріс қуатының
шектілігін ескертеді. (3) шектеулер тұтынушылардың сұраныстарын толық
қамтамасыз етуді көрсетеді. Егер болса, онда (1)-(4) есеп жабық
транспорт есебі деп аталады, қарсы жағдайда ашық транспорт есебі деп
аталады. Ашық транспорт есебін жабық қылуға болады, ол үшін жалған
пунктілер енгізу керек. Жалған пунктінің тасымалдау құны нольге тең.

Бұл есепті шешудің көптеген әдістері бар: солтүстік-батыс, минималды
элемент, потенциалдар әдісі.

3.1 Солтүстік-батыс және минималды
элемент әдісі

Солтүстік-батыс әдісі деп аталатын себебі, үлестіруді солтүстік-батыс
жағынан бастайды.
Минималды элемент әдісі деп аталатын себебі, кестенің ең кіші
тасымалдау құны () тұрған тордан бастайды.
Бұл екі әдіс транспорттық есептің тіректі жоспарын табу үшін қолданады.
Есеп әрі қарай потенциалдау әдісімен есептеледі.

3.2 Потенциалдау әдісі

Транспорт есебін потенциалдар әдісімен шығаруға болады. Потенциалдар
әдісі тек қана жабық транспорт есебінде қолданылады. Потенциалдар әдісін
қолдану үшін тіке транспорт есебіне қосмағыналы есебін құру керек.
Потенциалдар әдісінің алгоритмі:
Алғашқы қадам.
1. Басты жоспарды құру.
2. Жоспары бар торлар үшін жүйесін жасау.
3. Жоспары жоқ торлардың потенциалдығын зерттеу -
Алғашқы қадам бір-рет орындалады.
Жалпы қадам.
1. Жоспарды одан да жақсарту.
2. Жүйені түзету.
3. Түзетілген жүйенің потенциалдығын зерттеу.
Алғашқы жоспар не солтүстік-батыс бұрыш әдісімен, не минималды элемент
әдісімен жасалады.
Жоспары бар торларға жүйесі жасалады. Жоспары жоқ торларға
теңсіздіктер жүйесі құралады. Егер бұл шарттар орындалмаса, онда
ізделінеді. Табылған барлық -лардың ішінен ең үлкені болып
алынады.
тордан бастап, жоспары бар торларды сағат тіліне қарсы бағыт
бойынша цикл құрылады. Сонымен бірге тордан бастап, цикл бұрылатын
жерде алма кезек +, - белгілері қойылады. - (минуста) тұрған барлық
ішінен ең кішісі алынады
Жаңа жоспар келесідей құрылады:

Содан соң жоспары бар торларға жаңа теңдеулер жүйесін жасамыз:
Ал жоспары жоқ торладың потенциалдығын зерттейиіз: .

4 Оңтайландыру есебінің айқын математикалық өрнегінің өңделіп,
жетілдіруі, оның сандық түрдегі шешімі

Z=2x11+4X12+X13+6X14+7X15+
+3X21+3X22+5X23+4X24+2X25+
+8X31+9X32+6X33+3X34+4X35

X11+X12+X13+X14+X15=120
X21+X22+X23+X24+X25=110
X31+X32+X33+X34+X35=130

X11+X21+X31=80
X12+X22+X32=60
X13+X23+X33=70
X14+X24+X34=100
X15+X25+X35=50

Сипаттамалық кесте

B1 B2 B3 B4 B5
50
0 2 4 1 6 7
120 50 0 70 0 0
80 3 3
20 0 30 60 5 4 2
110 0 20 0
80
0 8 9 6 3 4
130 8 0 0 80 50

80+60+70+100+50=360
120+110+130=360
∑AI=∑BJ=80+60+70+100+50=120+110+130
ZMIN ЭЛЕМ=2*50+70*1+3*30+60*3+4*20+80*3+ 4*50=100+70+90+180+80+240+200=960

Солтүстік-батыс әдіспен жаңа жоспар

0 80 80 45
Vj 1 20 0 3 0 0
Ui
80 60 70 100 50
0 2 1 6 7 7
40 80 4 0 0 0
120 40
0 3
50 20 3 20 5 4 2
115 0 70 20
0
0 8 9 6
50 0 0 0 3 4
3 130 80 50

2*80+4*40+3*20+5*70+4*20+3*80+4*50= 160+160+60+350+80+240+200=1250
uj-ui=cig
vj-ui=cjg
v1-u1=2
u1=0 v1=2 v3-u1=1
α13=5
v2-u2=4 u1=0 v2=4 v4-u1=6
v2-u2=3 v2=4,u2=1 v5-u1=7
v3-u2=5 v3=6 u2=1 v1-u2=3
v4-u2=4 v4=5 u2=1 v5-u2=2
α25=4
v4-u3=3 u3=2 v4=5 u1-u3=8
v5-u3=4 v5=6 u3=2 v2-u3=9
v3-
u3=6

Vj V1=2 V2=4 V3=6 V4=5 V5=6

Ui
+ _
U2=1 3 5 4
20 70 20

U3=2 3 4
80 50

J(-)min{40;70}=40

Vj V1=2 V2=-1 V3=1 V4=0 V5=1
Ui
6 6
U1=0 2 4 1 7
80 40
3 _ 4 + 2
U2=4 3 60 5 20
30
6 4 4
U3=-3 8 9 3 _ 50
+ 80

2*80+1*40+3*60+5*30+4*20+3*80+4*50= 160+40+180+150+80+240+200=1050

vj-ui=cii vj-ui=cij
v1-u5=8
v1-u1=cij v2-u1=4
v2-u5=9
v1-u1=2 v4-u1=6
v3-u3=6
v2-u2=3 v5-u1=7
v3-u1=1 v1-u2=3
v3-u2=5 v5-u2=2
v4-u2=4
v4-u3=3
v5-u3=4

v1-u1=2 v2-u1=4
u1=0,v1=2 v4-u1=6
v3-u1=1 v5-u7=7
u1=0,v3=1 v2-u2=3
v2-u2=3 v5-u2=2
v2=-1,u2=-4 v1-u3=8
v3-u1=1 v2-u3=9
v3=1,u1=0 v3-u3=6
v-u2=5
v2=1, u2=4
v4-u2=4
v2=-4, v4=0
v4=0, u3=3
v5-u3=u
v3=-3, v5=1

uj-ui=cij vj-ui=cij

v1-u1=2 v2-u1=4
v3-u1=3 v4-u1=6
v2-u2=3 v5-u1=7
v3-u1=1 v2-u2=3
v3-u2=5 v5-u2=2
v4-u2=4 v1-u3=8
v4-u3=3 v2-u3=9
v5-u3=4 v3-u3=6

Vj
Ui V1=2 V2=-1 V3=1 V4=-3 V5=-2
+
U2=-4 3 3 5 4 2
60 _ 30 20
9
U3=-6 8 6 3 4
100 30

vj-ui=cij vj-ui≤4
v1-u1=2 v1=2 v2-u1≤4
v3-u1=1 v3=1 v4-u1≤ 6
v1-u2=3 v3=-1 v5-u1≤7
v3-u2=5 u2=-4 v1-u2≤ 3
α 21=3
v5-u2=2 v5=-2 v4-u2 ≤4
v4-u2=3 v4=-3 v1-u2 ≤8
v5-u3=4 u3=-6 v2-u3 ≤9
v3-u3 ≤6
α33=1

Vij V1=2 V2=2 V3=1 V4=0 V5=1
Ui
30 5 20
U2=-1 3 60 3 4 2
100 30
U3=-3 8 7 6 3 4

Vj-ui=cij
V1-u1= 2 v1=2
V3-u2=1 v3=1
V1-u2=3 u2=-1
V2-u2=3 v2=2
V5-u2=2 v5=1 z*=100+70+90+180+40+300+120=900
V4-u3=3 v4=0
V5-u3=4 u3=-3

5 Программа листингісі

Program transportnaj_zadatsha;
Uses Crt;
Label l1;
Const N=6;
n1=7; n2=7;
Sa:longint=0;
Sb:longint=0;
Type predpr=Array [1..N] of longint;
rasp=Array [1..N,1..N] of longint;
Var A,B,alfa,betta,B_d,x:predpr;
c,p:rasp;
... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.