Տրանսպորտային խնդիր

Տրանսպորտային խնդիր (Մոնժ-Կանտորովիչի խնդիր), գծային ծրագրավորման հատուկ ձևի մաթեմատիկական խնդիր կուտակիչից միասեռ օբյեկետների՝ տեղափոխման ծախսերը նվազագույնին հասցնելով լավագույն տեղաբաշխման որոնման մասին^[1]^[2]։ Առավել դյուրին կերպով հասկանալու համար դիտարկվում է որպես խնդիր ուղարկելու վայրից սպառման կետեր բեռների փոխադրման լավագույն ծրագրի մասին փոխադրման նվազագույն ծախսերով։ Տրանսպորտային խնդիրը մտնում է P բարդության դասի մեջ։

Երբ ուղարկման կետերում առկա բեռների ընդհանուր ծավալը հավասար չէ սպառման կետերի կողմից ցանկալի ապրանքների (բեռների) պահանջարկին, տրանսպորտային խնդիրը կոչվում է չբալանսավորված (բաց)։

Խնդրի դրվածք

Տրանսպորտային խնդիր (դասական), խնդիր է միասեռ ապրանքների առկայության միասեռ կետերից միասեռ տրանսպորտային միջոցներով (նախապես որոշված) սպառման միասեռ կետեր տեղափոխումն է հաստատուն տվյալներով և գծային մոտեցմամբ (սրանք խնդրի հիմնական պայմաններն են)։

Դասական տրանսպորտային խնդրի համար առանձնացվում են խնդիրների երկու ձևեր. արժեքի կամ տարածությունների չափանիշ (փոխադրման համար նվազագույն ծախսերի հասնելու ձև) և ժամանակի չափանիշ (փոխադրման համար ծախսվում է նվազագույն ժամանակ)։ Տրանսպորտային խնդիր անվան ներքո որոշվում է խնդիրների լայն շրջանակը մեկ մաթեմատիկական մոդելով, այդ խնդիրները վերաբերում են գծային ծրագրավորման խնդիրներին և կարող են որոշվել լավագույն մեթոդով։ Սակայն, տրանսպորտային խնդրի լուծման հատուկ մեթոդը թույլ է տալիս էապես հեշտացնել դրա որոշումը, քանի որ տրանսպորտային խնդիրը մշակվել է փոխադրումների արժեքը նվազագույնի հասցնելու համար։

Որոշման մեթոդների որոնման պատմություն

Խնդիրն առաջին անգամ ձևակերպվել է ֆրանսիացի մաթեմատիկոս Գասպար Մոնժի կողմից 1781 թվականին^[3]։ Հիմնական մշակումները կատարվել են Երկրորդ համաշխարհային պատերազմի տարիներին խորհրդային մաթեմատիկոս և տնտեսագետ Լեոնիդ Կանտորովիչի կողմից^[4]։ Այդ իսկ պատճառով այս խնդիրը երբեմն կոչում են Մոնժ-Կանտորովիչի տրանսպորտային խնդիրը։

Որոշման մեթոդներ

Դասական տրանսպորտային խնդիրը կարելի է որոշել սիմպլեքս մեթոդով, սակայն որոշ առանձնահատկությունների շնորհիվ՝ այն կարելի է լուծել առավել դյուրին կերպով (ավելի փոքր չափերի խնդիրների համար)։

Խնդրի պայմանները տեղակայում են աղյուսակում՝ յուրաքանչյուր վանդակում գրելով փոխադրվող բեռի քանակը $~A_{i}$ в $~B_{j}$ բեռից $~X_{ij}\geqslant 0$ , իսկ փոքր վանդակներում՝ համապատասխան տարիֆները $~C_{ij}$ :

Փոխադրումների ծրագրի իտերացիոն բարելավում

Հենման ծրագրի որոնում

Հարկավոր է որոշել հենման ծրագիրը և հաջորդական գործողությունների արդյունքում գտնել լավագույն լուծումը։ Հենման ծրագիրը կարելի է գտնել հետևյալ մեթոդներով. «հյուսիսարևմտյան անկյան», «փոքրագույն տարրի», կրկնակի գերադասության և Ֆոգելի ապրոքսիմացիայի։

Հյուսիս-արևմտյան անկյան մեթոդ (հորիզոնական կամ բարելավված)

Յուրաքանչյուր փուլում հնարավոր առավելագույն թվով լրացնում են աղյուսակի մնացած մասի վերին ձախ վանդակը։ Նման կերպ լրացումն այն է, որ ամբողջովին հանվում է բեռը $~A_{i}$ -ից կամ ամբողջովին բավարարվում է $~B_{j}$ պահանջարկը։

Փոքրագույն տարրի մեթոդ

Խնդրի լուծման ձևերից մեկը նվազագույն (փոքրագույն) տարրի մեթոդն է։ Վերջինիս էությունն այն է, որ ապրանքների վերաբաշխումների թիվը սպառողների միջև նվազագույնի հասցվի։

Ալգորիթմ.

Արժեքների աղյուսակից ընտրում են նվազագույն արժեքը և վանդակում, որին նա համապատասխանում է, լրացվում է թվերից առավելագույնը։
Ստուգվում են մատակարարների տողերը ծախսված պաշաների տողերի հետ և սպառողների սյուները այն սյուների հետ, որոնց սպառողները ամբողջովին բավարարված են։ Նման սուները և տողերը հետագայում չեն դիտարկվում։
Եթե ոչ բոլոր սպառողներն են բավարարված և ոչ բոլոր մատակարարներն են ծախսել իր ապրանքները, վերադարձ օր. 1, հակառակ դեպքում՝ խնդիրը լուծված է։

Ընդհանրացումներ

Տրանսպորտային խնդիր ցանցային դրվածքով

Այս տարբերակում կետերը չեն բաժանվում ուղարկման կետերի և սպառման կետերի, բոլոր կետերը հավասար են, սակայն արտադրությունը առաջդրվում է դրական թվով, իսկ սպառումը՝ բացասական։ Փոխադրումները կատարվում են ընտրված ցանցող, որտեղ ուղղությւոնները կարող են կախել ցանկացած կետ, ներառյալ՝ արտադրող-արտադրող, սպառող-սպառող։

Խնդիրը որոշվում է թեթևակիորեն փոփոխված պոտենցիալների մեթոդով, որը գործնականում գրեթե համընկնում է դասական դրվածքի հետ։

Անցնելու կարողության սահմանափակումներով տրանսպորտային խնդիր

Տրանսպորտային խնդիրը տարատեսակ, որի դեպքում առաջադրվում է որոշ ուղղությունների առավելագույն անցումային ունակություն։

Խնդիրը լուվում է թեթևակիորեն բարդացված պոտենցիալների մեթոդով։

Բազմապրանքային տրանսպորտային խնդիր

Տրանսպորտային խնդրի տարբերակ, որտեղ գոյություն ունի մի քանի ապրանք (կետերը կարող են արտադրել/սպառել մի քանի ապրանք)։ Որոշների համար սահմանափակում է տրվում անցնելու կարողության համար (առանց այդ սահմանափակման խնդիրը բաժանվում է առանձին առաջադրանքների՝ ըստ որոշակի ապրանքների)։

Խնդիրը որոշվում է սիմպլեքս մեթոդով (օգտագործվում է Դանցիգ-Վուլֆի մեթոդը. ենթաառաջադրանքների փոխարեն օգտագործվում են միապրանքային տրանսպորտային խնդիրները).

Ծանոթագրություններ

↑ А. В. Кузнецов, Н. И. Холод, Л. С. Костевич. Руководство к решению задач по математическому программированию. — Минск: Высшая школа, 1978. — С. 110.
↑ Словарь по кибернетике / Под редакцией академика В. С. Михалевича. — 2-е. — Киев: Главная редакция Украинской Советской Энциклопедии имени М. П. Бажана, 1989. — 751 с. — (С48). — 50 000 экз. — ISBN 5-88500-008-5
↑ Monge G. Mémoire sur la théorie des déblais et de remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, pages 666—704, 1781.
↑ Kantorovich L. On the translocation of masses // C. R. (Doklady) Acad. Sci. URSS (N. S.), 37:199-201, 1942.

Արտաքին հղումներ

Տրանսպորտային խնդիր
Առավելագույն բեռը գտնելու ալգորիթմ
http://kb.mista.ru/article.php?id=859 Տրանսպորտային խնդրի լուծումը 1С:Կազմակերպություն 8.2-ում

[kuzn-1] А. В. Кузнецов, Н. И. Холод, Л. С. Костевич. Руководство к решению задач по математическому программированию. — Минск: Высшая школа, 1978. — С. 110.

[2] Словарь по кибернетике / Под редакцией академика В. С. Михалевича. — 2-е. — Киев: Главная редакция Украинской Советской Энциклопедии имени М. П. Бажана, 1989. — 751 с. — (С48). — 50 000 экз. — ISBN 5-88500-008-5

[Monge-3] Monge G. Mémoire sur la théorie des déblais et de remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, pages 666—704, 1781.

[Kantorovich-4] Kantorovich L. On the translocation of masses // C. R. (Doklady) Acad. Sci. URSS (N. S.), 37:199-201, 1942.

[1]

[2]

[3]

[4]