Транспорт есебінің моделі

Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 16 бет
Таңдаулыға:

Қазақстан Республикасының білім және ғылым министрлігі
БҚОББ Орал газ, мұнай және салалық технологиялар колледжі МКҚК

Математика және информатика
ПЦК-сы

Курстық жұмыс
Пәні: Өндірістік және экономикалық процестерді модельдеу
Тақырыбы: Транспорттық есеп

Орындаған: СТ– 441 топ оқушысы
Нуртазина Н.Н
Тексерген: жетекші
Лукпанова Д.М

Орал 2007

Мазмұны
І. Кіріспе
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... ... ... ... 3
ІІ. Негізгі бөлім
2.1. Транспорт есебінің моделі
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .5

2.2. Алғашқы таяныш жоспарларды анықтау
... ... ... ... ... ... ... ... ... ... ... ... ... 7
2.3. Транспорт есебінің оптимал шешімі.
Потенциалдар әдісі
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ...9
2.4. Excel программасының көмегімен транспорттық
есептің шешімін табу
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... 16
ІІІ. Қорытынды
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
... ... ... ... ... ... 20
ІV. Қолданылған әдебиеттер
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
..21

Кіріспе

Қазіргі қоғамда болып жатқан ақпараттық дамудың өңделу, жеткізілу,
сақталу заңдарының негізін ұғыну және дұрыс болжамдау үшін болашақ маманға
компьютерлік модельдеу, ақпаратты өңдеу аса қажет.
Модельдеу – қазіргі заманғы ғылыми танымның басқарушы принципі. Адам
таным затын оның барлық процестерінде толық көре алмайды. Сондықтан ол
объектінің өзінің алдында тұрған мәселені шешуге қажетті жағын тануға
ұмтылады.
Компьютерлік математикалық модельдеу информатика пәнімен
технологиялық жағынан байланысады.
Сондай-ақ, ЭММ пәнін оқып үйрену кезінде математикалық программалау
тақырыбының алатын орны ерекше.
Математикалық программалау шектеулі ресурстарды барынша тиімді
пайдаланып, қойылған мақсатқа қол жеткізуді үйрететін математиканың саласы.
Әдетте математикалық программалау есебі екі бөліктен атап айтсақ,
мақсатты функциядан f(х1, х2, х3, ... , хn) және есеп шарттарынан gi ([х1,
х2, х3, ... , хn]) ≤bi тұрады. Мұнда i=1...m, ал j=1...n дейін өзгереді,
ал bi – i-ші өндіріс ресурстарынның көлемін сипаттайтын шама.
Математикалық программалаудың 2 түрі бар: сызықтық программалау және
сызықтық емес программалау.
Математикалық программалаудың қазіргі кезде көбінесе сызықтық
теңсіздіктер немесе теңдеулер түрінде шарт қойылған, сызықтық функцияның ең
үлкен немесе ең кіші мәнін табу.

Сызықтық программалаудың транспорт есептері экономикалық процестерді
зерттеулер мен теориялық ізденістерде кеңінен қолданылады. Әсіресе
өнеркәсіп және ауылшаруашылық өнімдерін тасымалдаудың ұтымды жоспарларын
анықтап, әр түрі транспорттың тиімді жұмыс істеуін қамтамасыз етеді.

2.1. Транспорт есебінің моделі
Транспорт есебінің математикалық қойылуы:
m жабдықтаушыда біркелкі өнім (жүк) жинақталған және оның әр
жабдықтаушыдағы мөлшері аі – ге (і=1, m) тең делік. Осы өнімдерді n –
тұтынушылардың әрқайсысына bj – ге (j=1, n) мөлшерінде жеткізу керек. Әр
жабдықтаушыдан тұтынушыларға жүктің жеке бір бөлігін тасымалдау шығыны сij
– ге тең. Олай болса, әр тұтынушының қажетін толық қанағаттандыратын әрі
толық транспорт шығыны ең аз болатын жүк тасымалдаудың жоспарын табу қажет.
Егер xij деп і жабдықтаушысынан j – тұтынушысына тасымалданатын
жүктің мөлшерін белгілесек, онда есептің берілгенін төмендегі кесте
түрінде бейнелеуге болады.

Жабдықтау-шыТұтынушылар Жабдықтау-
лар шылар
В1 В2 ... Вn
А1 С11 С12 ... C1n a1
Х11 Х12 X1n
А2 С21 C22 ... C2n a2
Х21 X22 X2n
... ... ... ... ... ...
Аm Сm1 Cm2 ... Сmn am
Xm1 Xm2 Хmn
b1 b2 ... bm

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

шарт орындалатын болса, онда бұндай есепті транспорт есебінің жабық
моделі деп, ал орындалмаса ашық моделі деп атайды.
Транспорт есебінің моделінің жалпы түрі төмендегідей жазылады:

мақсат функциясына минимал мән әперетін және мына:
i =1, 2, ... , m
, j = 1, 2, ... , n
xij = 0, i = 1, 2, ... , m; j = 1, 2, ... , n
шарттарын қанағаттаныратын Х = (Хij)mxn жүк тасымалдау жоспарын табу қажет.
Мысалы. Кестеде берілген транспорт есебінің моделін құру
аi bj 20 30 40
60 5 6 3
50 2 4 8

Шешуі: і – ші жабдықтаушыдан j – ші тұтынушыға жеткізілетін жүк
мөлшерін хij≥0 (i=1, 2); (j=1, 2, 3) деп белгілеп, алты айнымалы енгізіп,
келесі математикалық модельді аламыз:

тұтыну мөлшері бойынша,
хij ≥ 0 (i=1, 2, 3)
теріс еместік шарты.
Мақсат функциясы:
Ғ(х) = 5х11 + 6х12 + 3х13 + 2х21 + 4х22 + 8х23 → min

Ескерту: Жабдықтаушылар қоры бойынша шектеулер теңсіздіктер түрінде
берілген, себебі ∑аі = 110 ∑bj = 90 , сондықтан жүктің артық 20 бірлігі
жабдықтаушыларда қалады.

2.2. Алғашқы таяныш жоспарларды анықтау

Транспорт есебінің алғашқы таяныш жоспарын табудың бірнеше қарапайым
әдістері бар. Солардың арасында жиі қолданатыны солтүстік-батыс бұрышы
әдісі мен минимал элемент әдісі. Транспорт есебінің жалпы теңдеулер
жүйесі өзара сызықтық тәуелді болады да, ал сызықтық тәуелсіз теңдеулерінің
саны m + n -1 –ге тең болады. Сондықтан транспорт есебінің айнымаған
алғашқы таяныш жоспарында m + n -1 оң құрамы боп, қалған компоненттері 0-ге
тең болады.
Келесі транспорт есебінің алғашқы таяныш шешімін солтүстік-батыс
бұрышы және минимал элемент әдістерімен тауып, ол шешімдердің сызықтық
функционалының мәндерін салыстырамыз.

аi bj 90 40 50 70
bj
7 3 4 5
100 90 10
5 7 3 6
70 30 40
1 6 5 3
80 10 70

Шешуі: 1. Солтүстік – батыс бұрышы әдісінде кестені толтыру сол
жақтағы ең жоғарғы клеткадан басталады. (Географиялық картадағы солтүстік –
батысқа сәйкес). Х11 – дің мәнін мына қатынастан табамыз: х11=min {a1, b1}.
Егер а1 b1 болса, онда х11=а1, ал а1 b1 болса, х11= b1 тең, қалған
жүкті ары қарай үлестіре отырып, ең соңғы клетка толтырылған соң алғашқы
таяныш жоспарын аламыз.Алынған таяныш айнымаған, себебі толтырылған
клеткалар саны m + n – 1 = 3 + 4 – 1 = 6 – ға тең.

Осы таяныш жоспарға сәйкес сызықтық функционалдың мәнін немесе жалпы
шығынын есептейік:
Ғ(x'T) = 90*7 + 10*3 + 30*7 + 40*3 + 10*5 + 70*3 = 630 + 30 + 210 + 50
+ 210 = 1250
Шешуі: 2. Минимал элемент әдісінде транспорт тарифы ескеріледі.
Кестені толтыру ең кіші элементтен басталады. Минимал элемент әдісін
пайдаланып хij – дің мәнін табу үшін, транспорт тарифін көрсететін сij
матрицасынан ең кіші элемент табылып, сол клеткаға аі мен bj – дің кішісі
жазылады. Содан соң, бұдан кейінгі зерттеуден і - ші қатар (егер хij = ai ,
болса) немесе j – баған (егер xij = bj болса) шығарылады және тұтынушының

Қажеті немесе жабдықтаушыдағы жүктің қоры xij = ai = bj болса, онда бұдан
кейінгі зерттеуден і – ші қатар мен j – ші баған шығарылады. Содан соң,
матрицаның қалған эелементтерінен де минимал элемент анықталып, жоғарыда
келтірілген амалдар қайталанады. Бұл процесс барлық жүктің қоры үлестіріліп
және тұтынушылардың қажеті толық қанағаттандырылғанға дейін жалғанады.
Алдыңғы қарастырған кестені осы әдіспен толтырайық.

аi bj 90 40 50 70
bj
7 3 4 5
100 40 60
5 7 3 6
70 10 50 10
1 6 5 3
80 80

Нәтижесінде айнымаған келесі жоспарды аламыз:

Сәйкес сызықтық функционалының мәні:
Ғ(х''т) = 40*3 + 60*5 + 10*5 + 50*3 + 10*6 + 80*1 = 760
Сызықтық функционалдың екі әдіс бойынша табылған мәндерін салыстырып,
соңғы әдіс бойынша табылған таяныш жоспарға транспорт шығыны аз жұмсалғанын
көреміз.
Ғ(х'т) =125, Ғ(х''т) =760.
Әрине, бұдан барлық уақытта минимал элемент әдісі бойынша жақсы
жоспар табылады деп жорамалдауға болмайды.

2.3. Транспорт есебінің оптимал шешімі.
Потенциалдар әдісі

Алғашқы таяныш жоспар табылғаннан соң потенциалдар әдісінің көмегімен
есептің оптимал шешімін табуға болады. Потенциалдар әдісінің негізгі
алгоритмін келтірейік:
1. Жоғарыда келтірілген әдістердің бірімен алғашқы таяныш жоспар
алынады.
2. Табылған жоспардың оптимал екенін тексеру үшін потенциалдар
системасы құрылады. ui – қатар, vj- баған потенциалдары деп
есептесек, онда әрбір жабық клетка үшін ui + vj = cij теңдеуі
құрылады. Нәтижесінде m+n белгісіздері бар m+n-1 теңдеулер жүйесін
аламыз. Бұл жүйенің белгісіздерінің саны теңдеулерінің санынан көп
болғандықтан, оның көп шешімі болады. Сондықтан осы системаның кез
келген бір шешімін алу үшін ui-дің біреуін нөлге тең деп алып,
қалған потенциалдарды анықтаймыз. Мысалы: ui-дің мәні белгілі десек,
онда ui + vj = cij теңдеуінен vj = cij - ui табылады.
3. Әрбір бос клетка үшін ui + vj cij шарты орындалуын тексереміз.
Егер осы шарт барлық бос клетка үшін орындалса, онда алынған жоспар
оптимал болғаны.
4. Егер кемінде бір бос клетка үшін ∆ij=(ui + vj) - cij 0 болса, онда
жоспар жаңа жоспармен алмастырылады. Ол үшін ∆ij0 клеткалар
арасынан клеткасы таңдалып алынып, оған үлестіретін λ – жүк
мөлшері жазылады.
5. λ –санын табу үшін жоғарыда анықталған (1, k) клеткасына (+)
таңбасын жазып, сол клеткадан бастап төбелері жабық клеткаларда
жататындай етіп, тік бұрышты тұйық контур саламыз. Осы контурдың
қалған төбелеріне (+) және (-) таңбаларын алмастыра отырып, жазып
шығамыз.
6. Үлестіруге тиісті жүк мөлшерін (-) таңбасы бар клеткаларда
орналасқан хij-дің ең кішісіне тең деп аламыз.

k - - контурдың (-) пен белгіленген белгілеген төбелері. Содан соң λ –
санын (-) таңбасы бар клеткалардағы жүк мөлшерінен алып тастаймыз, ал (+)
таңбасы бар клеткадағы жүк мөлшеріне қосып жазып жаңа жоспар аламыз.
Табылған жаңа жоспар қайтадан тексеріледі. Ол үшін 2-6 қадамдарды
орындаймыз.
2-есеп. Бірінші есептегі Солтүстік-батыс бұрышы әдісімен алынған
таяныш жоспарды потенциалдар әдісімен оптимал мәніне тексерейік.

аі bj 90 40 50 70 ui
7 3 4 5
100 90 10 u1= 0
+
5 7 3 6
70 30 40 u2 = 4
- +
1 8 5 3
ui + 10 70 u3 = 6
-

vj v1 = 7 v2 = 3 v3 = -1 v4 = -3

Шешуі: Алынған таяныш жоспар айнымаған. u1= 0 деп алып, қалған
потенциалдарды анықтаймыз.
u1 + v1 = 7 v1 = 7
u1 + v2 = 3 v2 = 3
u2 + v2 = 7 u2 = 4
u2 + v3 = 3 v3 = -1
u3 + v3 = 5 u3 = 6
u3 + v4 = 3 v4 = -3
Потенциалдар жүйесі құрылды:
U = (0; 4; 6); V = (7; 3; -1; -3)
Барлық бос клеткалар үшін ∆ij= (ui + vj) - cij мәндерін анықтаймыз.
1. ∆13 = u1 + v3 – c13 = 0-1-4=-5 0
2. ∆14 = u1 ... жалғасы

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