Жүк тасымалдау есебін потенциалдар әдісімен шешу

Жоспар

КІРІСПЕ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...3

НЕГІЗГІ БӨЛІМ
1. ЖҮК ТАСЫМАЛЫН ТИІМДЕУДІ МОДЕЛЬДЕУ
1.1 Желілік программалаудың транспорттық тапсырмасының берілуі және математикалық моделі ... ... 5
1.2 Транспорттық тапсырма моделінің ерекшеліктері ... ... ... ... ... ... ... .7
1.3 Бастапқы тірек жоспарды анықтау ... ... ... ... ... ... ... ... ... ... ... ...9
1.4 Транспорттық тапсырманың тірек жоспарының оңтайлылық өлшемі ... ... ... ... .14

2. ЖҮК ТАСЫМАЛДАУ ЕСЕБІН ПОТЕНЦИАЛДАР ӘДІСІМЕН ШЕШУ
2.1 Алғашқы таяныш шешімді анықтау тәсілдері ... ... ... ... ... ... ... ...16
2.2 Ең кіші элемент тәсілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 18
2.3 Тиімді шарттарын тексеру ... ... ... ... ... ... ... ... ... ... ... ... ... ...19
2.4 Бір жоспардан екіншісіне ауысу ... ... ... ... ... ... ... ... ... ... ... ...20

ПРАКТИКАЛЫҚ БӨЛІМ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .23
ҚОРЫТЫНДЫ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..33 ПАЙДАЛАНЫЛҒАН ДЕРЕК КӨЗДЕРІ ТІЗІМІ ... ... ... ... ... ... ... ... ... ... ... ... ...35

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

МАЗМҰНЫ

КІРІСПЕ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...3
НЕГІЗГІ БӨЛІМ
1. ЖҮК ТАСЫМАЛЫН ТИІМДЕУДІ МОДЕЛЬДЕУ
1.1 Желілік программалаудың транспорттық тапсырмасының
берілуі және математикалық моделі ... ... ... ... ... ... ... ... ... ... ... 5
1.2 Транспорттық тапсырма моделінің ерекшеліктері ... ... ... ... ... ... ... .7
1.3 Бастапқы тірек жоспарды анықтау ... ... ... ... ... ... ... ... ... ... ... ...9
1.4 Транспорттық тапсырманың тірек жоспарының
оңтайлылық өлшемі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..14
2. ЖҮК ТАСЫМАЛДАУ ЕСЕБІН ПОТЕНЦИАЛДАР ӘДІСІМЕН ШЕШУ

2.1 Алғашқы таяныш шешімді анықтау тәсілдері ... ... ... ... ... ... ... ...16
2.2 Ең кіші элемент тәсілі ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 18
2.3 Тиімді шарттарын тексеру ... ... ... ... ... ... ... ... ... ... ... ... ... ...19
2.4 Бір жоспардан екіншісіне ауысу ... ... ... ... ... ... ... ... ... ... ... ...20
ПРАКТИКАЛЫҚ
БӨЛІМ ... ... ... ... ... ... ... .. ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ..23
ҚОРЫТЫНДЫ ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... 33

ПАЙДАЛАНЫЛҒАН ДЕРЕК КӨЗДЕРІ
ТІЗІМІ ... ... ... ... ... ... ... . ... ... ... ... ... ..35

КІРІСПЕ

Экономикалық модельдеу ғылымы ертеректен зерттеліп келді және кейін
бірте-бірте құрылыс және сәулет, астрономия, физика, химия, биология
ғылымдарымен терең байланысты болды. Осы ғылымдардың барлығында
экономикалық модельдеу іс жүзінде үлкен жетістіктерге жетті. Бірақ бұл жүйе
ұзақ уақыт жеке ғылымдарда дамыды. Ұғымдардың бірыңғай жүйелері және
терминдері болмады. Модельдеу ұғымы бірте-бірте ғылыми танудың әмбебап
әдісі сияқты ұғындырыла бастады.
Модель термині әр түрлі адамдық қызмет сфераларында қолданылады және
көпеген ұғымдардың жиынына ие.
Модельдеу – бұл басқару жүйелерін синтездеу және талдау үшін
қолданылатын ғылымның ең басты ерекше әдісі. Бұл ерекше тәсіл ұқсастықты
тану орнына зерттейтін объектінің субъектісін таңдайды немесе оған қосалқы
объекті бейнесін немесе үлгісін жасайды, оны зерттейді және жаңадан алынған
білімді түпнұсқаға жинақтайды.
Өзінің мүмкіндіктерін тиімді пайдалану арқылы жоғары нәтижеге жету
кез келген адамның негізгі мақсаттарының бірі. Экономикалық жүйелердің әр
түрлі деңгейлерінде кездесетін жоспарлау, басқару, шектелген ресурстарды
тиімді бөлу, өндірістік процестерді талдау, күрделі объектілерді жобалау
сияқты есептердің ұтымды және оптималды шешімдерін табу табиғи және ғылыми-
техникалық прогресс қажеттіліктерінен туған мәселелер.
Оптимизациялық есептерде математикалық әдістерді пайдалану үшін, ең
алдымен, тиімді шешімін табу қажет және есептің өзінің математикалық
қойылымын жазуымыз қажет. Математикалық қойылымда берілген ресурстар,
өндірістік технология, жақсы немесе жаман шешім деген сияқты
түсініктердің сан шамалары және олардың арасындағы байланыстар,
математикалық өректер, теңсіздіктер арқылы көрсетілулері тиіс. Шарттары
нақты берілген есептің математика тіліндегі формалды жазылымын сол есептің
математикалық моделі деп атайды.
Математикалық модель құру үшін, ең алдымен, зерттейтін объектінің ең
басты қасиеттерін немесе заңдылықтарын бөліп алып, оларды математикалық
өрнектер арқылы өзара байланыстырып сипаттайды. Математикалық модель
құрғаннан кейін ғана есепті шешіп, зерттеу үшін математикалық әдістерді
қолдануға болады.
Экономикалық процестердің математикалық модельдерін құрастыру өте
күрделі мәселе, себебі ол үшін математикалық және экономикалық білгірлікті
өзара ұштастыра білу қажет.
Оптимизациялау теориясында мүмкін болатын шешімдердің ішінен мақсат
функциясы деп аталатын функцияға ең үлкен немесе ең кіші мән беретін ең
жақсы шешімді табу әдістерін зерттеу мәселелері қарастырылады. Мысалы, кез
келген өндіріс фирмасының негізгі мақсаты – көбірек пайда табу.
Осы экономикалық математикалық есептерді шешудің тиімді тәсілдерін
пайдаланып, оларды зерттеуге байланысты мен курстық жұмысымның тақырыбын
Экономикалық өндірісте жүк тасымалының тиімділігін модельдеу деп алдым.
Бұл курстық жұмыс екі бөлімнен тұрады. Бірінші бөлімде транспорттық
есептердің ішіндегі жүк тасымалын тиімдеу есептерінің моделін құруды,
олардың тапсырмаларының берілуі қарастырылды. Есепті шешу барысында
модельдің ерекшеліктері мен оңтайлы шешімдерін табуды жоспарлау жолдары
бар. Екінші бөлімде есепті шешуде нақты жауап алу үшін түрлі экономикалық
әдістерді пайдалануды жаздым.
Курстық жұмысымның өзектілігі: экономикалық процестердің математикалық
модельдерін құрастыруда математикалық және экономикалық білгірлікті өзара
ұштастыру. Транспорттық есептерді тиімді әдіспен шығарып, ең аз шығынмен ең
көп пайдаға жетуді жоспарлау.
Курстық жұмысымның мақсаты: транспорттық есептерді шешуде өзінің
мүмкіндіктерін тиімді пайдалану арқылы жоғары нәтижеге қол жеткізу.
Экономикалық процестердің әр түрлі деңгейлерінде кездесетін
жоспарлау, басқару, шектелген ресурстарды тиімді бөлу, өндірістік
процестерді талдау, күрделі объектілерді жобалау сияқты есептердің ұтымды
және оптималды шешімдерін табу. Есепті түрлі тиімдеу әдістерін пайдалана
отырып шығарып, олардан алынған нәтижелерді салыстырып, нақты және тиімді
шешім алу.
Курстық жұмысымның мазмұны: Кіріспеден, екі тараудан, практикалық
бөлімнен, қорытындыдан және дерек көздер тізімінен тұрады.
Зерттеу міндеттері:
• Жүк тасымалын тиімдеудің моделін құру;
• Математикалық моделін анықтау;
• Жүк тасымалының тиімділігін шешу әдістері;
Ғылыми болжамы: Жүйелік программалаудың жалпы тапсырмаларын шешудегі
секілді, транспорттық тапсырманың оңтайлы жоспарын іздестіру және оның
қандай да бір тірек жоспарын табу.
Зерттеу объектісі: Delphi программалау ортасы.

1. ЖҮК ТАСЫМАЛЫН ТИІМДЕУДІ МОДЕЛЬДЕУ

1.1 Желілік программалаудың транспорттық тапсырмасының берілуі және
математикалық моделі

Желілік программалаудың (ЖП) көптегеп тапсырмаларының ішінен арнайы
тапсырмалардың кейбір топтары бөлініп көрсетілді. Оларды жалпы тәсілдермен
шешу есептік сипаттағы бірқатар қиыншылықтармен бірге жүреді. Осыған
байланысты арнайы, едәуір қарапайым шешу тәсілдері әзірленді.
Тапсырмалардың осындай топтарының бірі транспорттық тапсырмалар болып
табылады.
Тапсырманың берілуі. А1, А2, ..., Аm-нің m жіберілу пункттерінде
біртекті жүктің, сәйкес а1, а2, ..., аm бірлігі бар, ол В1, В2, ..., Вn-нің
n тұтыну пункттеріне жеткізілуі керек (1 – кестеде көрсетілген). Ал оларға
сұраныс сәйкесінше в1, в2,..., вn бірлігін құрайды. Мұнда А пунктінен В
пунктіне (і=, j=) жүк бірлігін тасымалдауға жұмсалатын
транспорттық шығындар С берілген. Барлық жүк жіберілу пунктінен толығымен
шығарылатын, барлық тұтыну пункттеріндегі сұраныс қамтамасыз етілетін және
транспорттық шығындар сомасы минималды болатын тасымалдау жоспарын анықтау
керек.

b b ... b ... b
b
a
a C ... C ... C
C X X X
X
a C C ... C ... C
X X X X
... ... ... ... ... ... ...
a C C ... C ... C
X X X X
... ... ... ... ... ... ...
a C C ... C ... C
X X X X

1 – кесте. Тапсырманың бастапқы мәліметтерін бөлуші
Тапсырманың математикалық моделі. Тапсырманъң математикалық моделін
құру үшін А(і=) пунктінен В(j=) пунктіне тасымалданатын
жүк бірлігінің көлемін білдіретін Х0 (і=, j=)
айнымалыларын енгіземіз. Бұл ауыспалылар келесі шарттарды қанағаттаңдыруы
керек:

а) барлық өнім жіберілу пунктінен шығарылуы керек:

b) Барлық тұтыну пунктеріндегі сұраныс толығымен
қанағаттандырылуы керек:

с) Тасымалдау тек бір бағытта, яғни
A пунктінен B пунктіне X жүреді.

d) Транспорттық шығындар сомасы минималды болуы қажет:

- тасымалдау жоспары

Осылайша, тансырманың математикалық моделі мынадай түрге ие болады:

(1)
(2)
(3)
(4)

2. Транспорттық тапсырма моделінің ерекшеліктері

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

А матрицасының барлық элементтері 1 және 0-ден тұрады және мұндағы
әрбір бағанда тек екі бірлік (1) қана бодады.
Шектеу жүйесін векторлық түрде жазалық:

Осылайша, векторлық түрдегі транспорттық тапсырма моделі мынадай түрге
ие болады:

(1)
(5)
(4)

1-анықтама: Х= mxn матрицасымен анықталатын (2)-(4) жүйесінің
теріс емес әрбір шешімі (1)-(4) транспорттық тапсырмасының жоспары деп
аталады.
2-анықтама: Х= mxn жоспары егер нольдік емес коэффициентті (5)
теңдікке кіретін векторлар желілік тәуелсіз болса, тірек жоспары деп
аталады.
3-анықтама: (1) мақсатты функциясы минималды мәнге ие болатын X=
mxn жоспары оңтайлы жоспар деп аталады.
1-теорема. (1)-(4) тапсырмалары шешімді болу үшін
(6)
шартының орындалуы қажет және ол жеткілікті.
Мұнда транспторттық тапсырма моделі жабық деп аталады.
2-теорема. (2)-(3) шектеулер жүйесінің А матрицасының рангі шектеулер
санынан 1-ге кіші, яғни r(A)=m+n-1.
Теоремадан желілік тәуелсіз векторларының барынша жоғары саны тек
(m+n-1) бола алатындығы, ізінше, транспорттық тапсырманың X= mxn тірек
жоспарында (m+n-1)-ден аспайтын нөлдік емес компоненттердің бола алатындығы
айқындалады. Кері жағдайда ол тудырылған деп аталады.

1.3 Бастапқы тірек жоспарды анықтау

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

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

Мысал:

Солтүстік-батыс әдісімен бастапқы тірек жоспарды анықтаймыз
(2 - кесте). Әуелі тапсырманың шешімділігін тексерейік:

тапсырма шешімді.
Бөлуші кесте құрайық:

0 0 0 0
b 11 8 4 13
a 12 12
0 4
15 8 4 6 3
11 4
0 8
16 7 4 5 6
8 8
0 13
17 3 7 4 6
4 13

2 – кесте. Солтүстік-батыс әдісімен бөлу

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

Көріп тұрғанымыздай, екінші тұтьшушының сұранысы толығымен
қанағаттандырылды, сондықтан да үшінші жабдықтаушыдан оған ештеңе жіберудің
керегі жоқ, яғни , бөлуші кестенің екініші бағаны жабылады, ал екінші
жабдықтаушыда а21 = а2 -Х22 = 16-8=8 көлемінде жүк қалады.
4-қадам. Екінші бағаны аныкталғаннан кейін қалған матрица-жоспарда
элементті анықтаймыз:

Екінші жабдықтаушы толығымен босады, сондықтан да тұтынудың, 4-ші
пунктіне бұл жабдыктаушыдан жүк келмейді, яғни ,сөйтіп бөлуші кестенің
екінші жолы жабылады, сұраныс .
5-кадам. Х-ті анықтаймыз:

6-қадам. Жоспардың соңғы элементін анықтаймыз:

Осылайша, m+n-1=3+4-1=6 қадам арқылы бастапқы тірек жоспар анықталды:

Алынған жоспарға сәйкес келетін транспорттық шығындарды анықтаймыз.
Оларды бөлуші кесте бойынша оңай есептеп шығаруға болады:
L(Х)=11*8+4*4+8*4+8*5+4*4+13*6=88+1 6+32+40+16+78=270
Солтүстік-батыс бұрыi әдісімен құрылған тірек жоспарда транспорттық
шығындар көрсетілмейді, сондықтан алынуы мүмкін шешім оңтайлы шешімнен
алшақ болады. Оңтайлы шешімге минималды элемент тәсілімен анықталған жоспар
жақынырақ.
Минималды элемент әдісі. Бұл әдістің де алгоритмі қадамдардың соңғы
санынан тұрады.
1-кадам. Шығындар матрицасынан минималды элемент табылады:

жоспарының сәйкес элементі анықталады:

2 жағдай болуы мүмкін:
А) онда бұл жағдайда А пункті толығымен босаған,
сондықтан басқа тұтынушыларға бұл пункттен жүк жіберілмейді, яғни
және бөлуші кестенің жолы жабылады, ал 2-қадамға өтелік.
В) бұл жағдайда яғни тұтынушының сұранысы толығымен
қанағаттандырылды, демек басқа жабдықтаушылардан оған жүк жеткізу қажет
емес, сондықтан яғни бастапқы тірек жоспардың -ші бағаны
аныкталды. Мұнда бөлуші кестедегі -ші баған жабылады, ал 2-
қадамға өтелік.
2-қадам. 1-қадамда бастапқы тірек жоспардың жолын немесе бағанын
анықтағаннан кейін, сәйкес жол немесе баған сызылғаннан кейін қалған бөлуші
кестеде тағы да транспорттық шығындардың минималды элементін іздейміз
1-қадамдағы секілді жоспардың сәйкес элементі анықталады және т.б. Осы
процесті жалғастыра отырып, қадамдардың соңғы санына карай бастапқы
жоспарды анықтай аламыз.
Теорема. Минималды элемент әдісімен алынған жоспар тірек жоспар болып
табылады. (3 - кесте). Мысалы: a=15, a=16, a=17

b=11, b=12, b=12, b=13

Тапсырманың шешімділігі алдын ала анытқталған. Тірек жоспарды
минималды элемент әдісімен анықталық. Бөлуші кесте құрамыз:

0 10 0 0
b 11 6 13
a 12 12
0 2 8
15 4 6 3
2 13
0 6
16 7 4 5 6
10 6
0 6
17 3 7 4 6
11 6

3 – кесте. Минималды элемент әдісімен алынған тірек жоспар

1-қадам. Транспорттық шығындар арасынан минималды элементті табамыз:
min
Х жоспарының бөлуші кестенің бірінші жолында және соңғы бағанында
орналасқан сәйкес элементін анықтаймыз:
X
Көріп тұрғанымыздай, 4-ші тұтынушының сұранысы толығымен
қанағаттандырылды, сондықтан , ал және бөлуші кестенің 4-ші
бағаны жабылады, мұнда a 2-қадамға өтелік.
2-қадам. 4-ші бағанды сызып тастағаннан кейін қалған бөлуші кестеде
транспорттық шығындардың минималды элементін іздейміз - С31 = 3. Жоспардың
сәйкес элементін анықтаймыз: сонда және бөлуші кестенің бірінші
бағаны жабылады, ал 3-кадамға өтеміз.
3-қадам. Сызылғаннан кейін қалған бөлуші кестеде тағы да транспорттық
шығыңдардың минималды элементі анықталады. Олар бірнешеу бодғандықтан, кез
келгенін таңдаймыз, мысалы, . Жоспар элементін табайық , мұнда
және бөлуші кестенің бірінші жолы жабылады, ал .
4-қадам. Бөлуші кестеде 4 торша қалды, оларда транспорттық шығындардың
минималды элементін табамыз - С22 = 4. Х12 = min (а2,) = min (16,
10)=10= анықтаймыз, мұнда және бөлуші кестенің 2-ші бағаны
жабылады, ал а21 = а2- х22=16-10=6.
5-қадам. Транспорттық шығындардың келесі минималды элементі - С33=4.
aнықтаймыз, 3-ші жолдың барлық элементтері анықталған, яғни бөлуші
кестенің 3-ші жолы жабылады, мұнда тек 3-ші тұгынушы ғана
қанағаттандырылмай қалды, оған жүктің 6 бірлігі жетпейді, мұны ол жүктің 6
бірлігі қалған 2-ші жабдықтаушыдан алады.
6-қадам.

Сонымен, тірек жоспарын аламыз:

Алынған тасымалдау жоспарына сәйкес келетін шығындарды анықтаймыз.
Оларды бөлуші кесте бойынша оңай есептеуге болады:
L(X)=2*4+13*3*+10*4+6*5+11*3+6*4=8+ 39+40+30+33+24=174
Егер енді минималды элемент және солтүстік-батыс бұрыш әдістерімен
алынған жоспарлардың транспорттық шығындарын салыстырып көрер болсақ, онда
минималды элемент тәсілі арқылы үздік тірек жоспары алынғандығын көруге
болады.

1.4 Транспорттық тапсырманың тірек жоспарының оңтайлылық өлшемі.

Әрбір А жіберу пунктіне сәйкесінше шамаларын қоямыз, ал
әрбір тұтыну пунктіне - . Потенциалдар деп аталатын бұл шамаларда
мынадай шарттар орындалады:
жоспардың нөлдік емес компоненттері үшін

Шамаларды анықтаймыз:

Бұлардан матрицасын құрамыз.

Матрица

X= жоспарының бағалаушы матрицасы деп аталады.
Сонда транспорттык, тапсырма жоспарының оңтайлылық
өлшемі төмендегі теорема түрінде беріледі.
Теорема. X= жоспары оңтайлы болу үшін оның бағалаушы
матрицасының барлық элементтері теріс емес болуы қажет және жеткілікті,
яғни:

2. ЖҮК ТАСЫМАЛДАУ ЕСЕБІН ПОТЕНЦИАЛДАР ӘДІСІМЕН ШЕШУ

2.1 Алғашқы таяныш шешімді анықтау тәсілдері

Тасымалдау есебі де сызықты бағдарламалау есебіне жатады, оны шешу үшін
кәдімгі симплекс әдісін пайдалануға болады. Бірақ бұл есепті шешу үшін
арнайы потенциалдар әдісі қолданылады.
Потенциалдар әдісін қолдану үшін тасымалдау есебінің тек жабық моделі
қарастырылады.
Сондықтан тасымалдау есебінің төмендегі моделін қарастырамыз:
жүк тасымалдау есебінің мағнасы - А1, А2,...,Аm қоймаларындағы жүкті
В1, В2,..., Вn тұтынушыларға апарудың тиімді жоспарын құруда.
Бұл есептерді оның құндық белгісі және уақыт белгісіне байланысты екі
түрге бөлуге болады. Бірінші жағдайда оның тиімді жоспары - орындалуына
минималды қаржы жұмсауда, ал екінші жағдайда – оған аз уақыт жұмсау.
а1, а2,..., аm әріптерімен саны m-ге тең А1, А2, ..., Аm қоймаларындағы
сәйкес жүктердің мөлшерін, ал а әрпімен жүктің жалпы мөлшерін

а1 + а2 +...+ аm = а
(11)
белгілейік.
В1, В2, ..., Вn тұтынушыларына қажетті жүк мөлшерлерін в1, в2, ..., вn,
ал барлық қажетті жүк мөлшерін в әрпімен

в1 + в2 + ... + вn = в
(12)
белгілейік.
Егер де қоймалардағы жүктердің жалпы мөлшері тұтынушыларға қажетті
жүктің мөлшеріне тең болса, яғни
а = в,
(13)
онда бүл жүк тасымалдау есебінің жабық моделі деп аталады. Ал а ≠ в
жағдайда есеп ашық модель болып табылады.
(11) және (12) шарттарға қосымша тарифтер матрицасы Сi j берілген,
олар бірлік жүкті Аi пунктінен Вә пунктіне апаруға кететін жол ақысын
көрсетеді. Жүк тасудың ең аз шығын жұмсалатындай жоспарын құру қажет.
xij арқылы Аi пунктінен Вj тұтынушыға тасылатын жүктің мөлшерін
белгілейміз. Бұл шамалар жиыны тасу матрицасын көрсетеді.
Қойылған есептің экономика-математикалық моделі төмендегідей болады:
(14)
(15)
(16)
(17)
(18)

Тасымалдау есебінің алғашқы таяныш шешімін анықтау әртүрлі жолмен
орындалуы мүмкін. Олардың ең көп тараған түрлері:
а) диогональды
және
в) ең кіші элемент
тәсілдері.
Диогональды тәсіл боцынша тасымалдау есебінің үлестіру кестесі оның
жоғарғы сол жақ бұрышынан бастап толтырылады (4 - кесте). Мұндағы негізгі
ереже (15) және (16) теңдіктерінің орындалуында.

тұтынушылар жүк
қоры
Қоймалар В1 В2 В3 В4 В5
А1 8 2 8 3 6 150
0 110 0 40 0
А2 2 8 4 7 6 240
0 10 0 130
100
А3 4 3 2 4 8 140
0 0 80 60 0
қажеттілік100 110 90 100 130
530

4 – кесте. Тасымал кестесі

Бұл тасымалдау кестесінің толтырылу тәртібі төмендегідей:
алдымен ең жоғарғы сол жақтағы бұрыштағы кереге көзге 100 деген сан
жазылады; оның себебі А1 қоймасында 150 мөлшерінде жүк қоры болса, ал В1
пайдалануға қажеті 100; сондықтан х11=100. Одан артылған 50 мөлшердегі жүк
екінші тұтынушыға жіберіледі, немесе х12=50, ал қалғандары бірінші қоймадан
жүк алмайды, немесе х13=х14=х15=0. Сонымен бірінші тұтынушы В1 өз
қажеттілігін толық қамтамасыз еткендіктен басқа қоймадан жүк алмайды,
немесе х21=х31=0.
Осыдан кейін келесі толтырылатын кереге көз екінші жатық жол мен екінші
тік жолдың қиылысында орналасқан.Мұнда екінші тұтынушы В2-ге қажетті 60
мөлшердегі жүк берілуге жиіс немесе х22=60. Сонда ол өз қажетілігін түгел
қамтамасыз етеді, немесе х32=0.
Осылайша қайталана отырып, кестенің барлық торларын толтыруға болады.
Сонымен (15)-(18) шарттарын қанағаттандыратын мынандай шешім немесе
тасымалдау жоспарын құрастыруға болады:
х11 = 100; х12=50; х13=0; х14=0; х15 = 0;
х21 = 0; х22 = 60; х23 = 90; х24 = 90; х25 = 0;
х31 = 0; х32 = 0; х33 = 0; х34 = 10; х35 = 130;
Бұл жоспарды орындауға жұмсалатын қаржы мөлшері былайша анықталады:
F= 8*100 + 2*50+ 8*60+ 4*90+ 7*90+ 4*10+ 8*130=3450

2.2 Ең кіші элемент тәсілі

Жоғарыда қарастырылған тәсіл бойынша үлестіру кезінде тасымалдауға
жұмсалатын қаржы есепке алынбайды. Ол үшін ең кіші элемент тәсілін
пайдалануға болады. Ең кіші элемент тәсілі бойынша кестені ең кіші элемент
орналасқан тор көзін толтырудан бастаймыз (5 - кесте). Ал қалғандары
жоғарыда көрсетілген тәсілдегі (15)-(18) шарттарының орындалуын қамтамасыз
етуге тиіс.
Жоғарыдағы мысалды қарастырайық.

Тұтынушылар жүк
қоймалар В1 В2 В3 В4 В5 қоры
А1 8 2 8 3 6 150
0 110 0 40 0
А2 2 8 4 7 6 240
0 10 0 130
100
А3 4 3 2 4 8 140
0 0 80 60 0
қажеттілік 100 110 90 100 130
530

5 – кесте. Ең кіші элемент тәсілі
Бұл есептегі ең кіші элемент 2-ге тең; ол үш рет кездеседі; олардың кез-
келгенінен бастауға болады. Біз бірінші жолда орналасқанынан бастайық.
Кестенің осы кереге көзіне 110 санын жазамыз, немесе екінші тұтынушы В2
өзіне қажетті барлық жүкті бірінші қоймадан ең арзан қаржы жұмсап алады,
немесе х12=110; ол басқа қоймадан жүк алмайды:
х21 = х32 = 0
Бірінші қоймадан қалған 40 мөлшердегі жүк төртінші тұтынушыға беріледі,
себебі оның жұмсайтын қаржысы басқасынан аз. Осылайша кестенің барлық
кереге көздерін толтыруға болады. Сонымен жаңа жоспар:

х11 = 0; х12 = 110; х13 = 0; х14 = 40; х15
= 0;
х21 = 0; х22 = 0; х23 = 10; х24 = 0; х25 = 130;
х31 = 0; х32 = 0; х33 = 0; х34 = 60;
х35 = 0;

Бұл жоспарды іске асыруға жұмсалатын қаржы мөлшері:
F= 2*110 + 3*40+ 2*100+ 4*10+ 2*80+ 4*60+ 6*130=1760
Осы тәсіл бойынша анықталған жоспар диагональды тәсілінен пайдалырақ
екендігін көруге болады.
Ескерту. Тасымалдау кестесін толтыру кезінде толтырылған (хij = 0)
кереге көздер саны n+m -1 –ге тең болуы керек.

2.3 Тиімді шарттарын тексеру

Табылған шешімнің тиімді екендігін тексеру үшін төмендегі амалдарды
орындау қажет:
а) Жүк қоймалары мен тұтынушылардың потенциалдарын енгіземіз:
U1 ,U2 , ... ,Un және V1 , V2 , ... ,Vm .
б) Тасымалдау есеп кестесінің әрбір толтырылған кереге көзі үшін
Ui (i=1,n) және Vj (j=1,m ) белгісіздері бойынша n+m -1 теңдеулер
жүйесін құрастыру керек:
Vj - Ui - Сi j = 0 (19)
в) Осы құрастырылған теңдеулер жүйесін шешу арқылы Vj және Ui
белгісіздерінің мәндері анықталады.
г) Кестенің толтырылмаған кереге көздері үшін келесі шарттың
орындалуы тексеріледі:
Vj - Ui - Сi j ≤ 0 (20)
Егер осы (20) шарттары барлық кереге көздер үшін орындалса, онда
есептің шешімі тиімді болғаны; ал керісінше жағдайда тиімді болмайды.
Осы айтылған амалдардың іс жүзінде орындалуын көрсету үшін жоғарыда
келтірілген есептің диагональ тәсілі бойынша табылған шешімін қарастырайық.
Бұл кесте үшін қарастырылатын теңдеулер жүйесі былайша жазылады:

V1 - U1 - 8 ... жалғасы

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