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

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

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

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

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

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

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

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

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

##### Հյուսիս-արևմտյան անկյան մեթոդ (հորիզոնական կամ բարելավված)
Յուրաքանչյուր փուլում հնարավոր առավելագույն թվով լրացնում են աղյուսակի մնացած մասի վերին ձախ վանդակը։ Նման կերպ լրացումն այն է, որ ամբողջովին հանվում է բեռը ~A_i-ից կամ ամբողջովին բավարարվում է ~B_j պահանջարկը։

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

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

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

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

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

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

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

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

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

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

Կատեգորիա:Մաթեմատիկական մոդելավորում