Толтырылған ұяшықтар
Стохастикалық бағдарламалау модельдері сызықтық және сызықтық емес болып бөлінеді. Көбінесе сызықтық бағдарламалау есептеріне сәйкестендіріліп құрылатын сызықтық модельдер қолданылады. Мұндай модельдерде мақсатты функциядағы белгісіздердің коэффициенттері, шектеулердегі A матрицасының коэффициенттері және шектеулердің бос мүшелері кездейсоқ шамалар болуы мүмкін.
Кездейсоқтықтың екі жағдайы
- Тәуекел жағдайы: кездейсоқ шамалардың үлестірілуі алдын ала белгілі.
- Анықталмағандық: үлестірілуі белгісіз.
Есептерді стохастикалық тәсілмен шешу оптималды жоспарды бірмәнді анықтамайды: ықтималдылықтарға байланысты бірнеше баламаның кез келгені оптималды болуы мүмкін. Жалпы математикалық бағдарламалау есептерінде айнымалыларға қойылған шектеулерді сақтай отырып, мақсатты функцияның экстремумын табу қажет.
Бұған дейін мақсатты функциясы мен шектеулері сызықтық болатын есептер қарастырылды. Алайда нақты қолданбалы есептерде сызықтық емес тәуелділіктер жиі кездесетіндіктен, сызықтық емес бағдарламалау теориясын дамыту қажеттілігі туындады. Қазіргі уақытта бұл бағыт қарқынды дамып келеді: мақсатты функция мен/немесе шектеулер сызықтық емес болса, мұндай есептер сызықтық емес бағдарламалау есептері деп аталады.
Тасымалдау есебіндегі тиімділік және потенциалдар әдісі
Қарастырылып отырған тасымалдау жоспарының тиімділігі барлық ұяшықтар үшін орындалатын тиімділік шартымен анықталады. Әдістемеде бұл шарт, әдетте, потенциалдар арқылы жазылады: жол потенциалы ai және баған потенциалы bj енгізіледі.
Негізгі идея
Толтырылған (базистік) ұяшықтар үшін потенциалдар теңдік түріндегі шарттардан табылады, ал толтырылмаған ұяшықтар үшін тиімділік тексеріледі.
Базистік ұяшықтар
Теңдік орындалады: ai + bj = cij.
Базистік емес ұяшықтар
Тиімділік белгісі тексеріледі: ai + bj − cij ≤ 0.
Толтырылған ұяшықтар саны әдетте (m + n − 1)-ге тең, ал белгісіз потенциалдар саны (m + n). Сондықтан жүйені бірмәнді жабу үшін потенциалдардың біреуін еркін таңдап (мысалы, a1=0), қалғандарын теңдеулерден табады.
Потенциалдарды есептеу ережесі
Белгісіз потенциал толтырылған ұяшықтағы тасымалдау құнынан белгілі потенциалды азайту арқылы табылады. Басқаша айтқанда, бір потенциал белгілі болса, сәйкес базистік ұяшықтың құны арқылы екіншісі есептеледі.
Потенциалдар табылғаннан кейін тиімділік шартын тек толтырылмаған ұяшықтар үшін тексеру жеткілікті. Егер барлық есептелген мәндер теріс немесе нөлге тең болса, жоспар тиімді. Егер кемінде бір ұяшықта оң мән шықса, жоспар тиімді емес және оны жақсартуға болады.
Жоспарды жақсарту қадамы (потенциалдар әдісі)
Егер тиімділік шарты бұзылатын ұяшық табылса, сол ұяшыққа θ > 0 көлемінде тасымал енгізу арқылы жоспар жетілдіріледі. Бірақ бұл әрекет бір ғана ұяшықты өзгертіп қоймайды: жіберуші қоры мен тұтынушы сұранысының балансы сақталуы үшін сәйкес ұяшықтар бойынша қайта тарату (цикл) жасалады.
Неге цикл қажет?
Бір ұяшыққа оң тасымал қосу бір жіберушінің жіберетін көлемін арттырады және бір тұтынушының алатын көлемін де арттырады. Сондықтан балансты сақтау үшін базистік ұяшықтар бойымен «+θ/−θ» түріндегі өзгерістер тізбегі құрылады: бір жерде қосылады, бір жерде азаяды, нәтижесінде жолдар мен бағандардың қосындылары өзгермейді.
Ашық тасымалдау есебін жабық есепке келтіру
Ашық көлік қатынасы есебінде жалпы қорлар қосындысы мен жалпы сұраныс қосындысы тең болмауы мүмкін. Мұндайда есепті стандартты әдістермен шешу үшін оны жабық есепке келтіреді: артық/кем мөлшерді теңестіретін жалған тұтынушы немесе жалған жіберуші енгізіледі. Жалған бағыттар үшін тасымалдау құны әдетте 0 деп алынады.
Қор артық болса
Егер ∑ai > ∑bj болса, онда K = ∑ai − ∑bj айырымына тең қажеттілігі бар жалған тұтынушы қосылады және жаңа баған енгізіледі.
Жалған тұтынушыға тасымалдау құны: ci, new = 0.
Сұраныс артық болса
Егер ∑ai < ∑bj болса, онда K = ∑bj − ∑ai айырымына тең қоры бар жалған жіберуші қосылады және жаңа жол енгізіледі.
Жалған жіберушіден тасымалдау құны: cnew, j = 0.
Қысқаша алгоритм
- 1 Жіберушілер қорларының қосындысын есептеңіз: ∑ai.
- 2 Тұтынушылар сұраныстарының қосындысын есептеңіз: ∑bj.
- 3 Салыстырыңыз және теңестіру мөлшерін табыңыз: K.
- 4 Қажет болса жалған тұтынушы/жіберушіні енгізіп, жаңа баған/жол қосыңыз.
- 5 Жалған бағыттардың шығындарын нөлге тең деп алыңыз: c = 0.
Алғашқы базистік таралымды анықтау әдістері
Тасымалдау есебін шешуде алғашқы базистік таралымды (алғашқы жоспарды) құру маңызды қадам. Көбіне мына әдістер қолданылады: солтүстік-батыс бұрышы әдісі, ең кіші элементтер (ең аз шығын) әдісі, Фогель әдісі және т.б. Солтүстік-батыс бұрышы әдісі қарапайым, бірақ оның басты кемшілігі — шығын коэффициенттерін елемеуі.
Солтүстік-батыс бұрышы әдісі
Бұл әдісте тарату кестенің (1,1) ұяшығынан басталады да, әр қадамда жол/баған қор-сұраныс теңестірілгенше жылжиды. Әр ұяшыққа мүмкін болатын ең үлкен көлем беріледі: xij = min(қор, сұраныс).
Кемшілігі: таңдау тасымалдау құнына емес, кестедегі орналасуға тәуелді.
Ең кіші элементтер (ең аз шығын) әдісі
Бұл әдіс солтүстік-батыс бұрышы тәсілінің кемшілігін азайтады: жүк ең алдымен шығын коэффициенті ең кіші ұяшықтарға жіберіледі. Сондықтан алынған алғашқы жоспар әдетте тиімді шешімге жақынырақ болады.
Нәтижені салыстыру логикасы
Бірдей есеп үшін солтүстік-батыс бұрышы әдісімен алынған қосынды шығын көбіне жоғары болады, ал ең аз шығын әдісі қосынды шығынды төмендетуге бейім.
Келесі кезең — тиімді шешімді іздеу. Бұл үшін потенциалдар әдісі қолданылады. Ал алғашқы жоспарды сапалырақ құруға бағытталған кең тараған тәсілдердің бірі — американ математигі У. Фогель ұсынған әдіс.
Көлік қатынасы есебінің экономика-математикалық моделі
Көлік қатынасы есебінің моделі әдетте канондық түрде жазылады және мына құрамдас бөліктерден тұрады: (1) жіберушілер қорларын толық тарату теңдеулері, (2) тұтынушылар сұраныстарын қанағаттандыру теңдеулері, (3) теріс еместік шарттары, (4) қосынды шығынды минималдау мақсатты функциясы.
Модельдің негізгі ерекшеліктері
- Шектеулер теңдеулер жүйесі түрінде беріледі (канондық түр).
- Шектеулер жүйесінің коэффициенттері 0 немесе 1 болады.
- Әр айнымалы шектеулер жүйесіне екі рет кіреді: бір рет жіберуші теңдеуіне, бір рет тұтынушы теңдеуіне.