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

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


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


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


== Որոշման մեթոդներ ==
Դասական տրանսպորտային խնդիրը կարելի է որոշել սիմպլեքս մեթոդով, սակայն որոշ առանձնահատկությունների շնորհիվ՝ այն կարելի է լուծել առավել դյուրին կերպով (ավելի փոքր չափերի խնդիրների համար)։
Խնդրի պայմանները տեղակայում են աղյուսակում՝ յուրաքանչյուր վանդակում գրելով փոխադրվող բեռի քանակը 
  
    
      
         
        
          A
          
            i
          
        
      
    
    {\displaystyle ~A_{i}}
   в 
  
    
      
         
        
          B
          
            j
          
        
      
    
    {\displaystyle ~B_{j}}
   բեռից 
  
    
      
         
        
          X
          
            i
            j
          
        
        ⩾
        0
      
    
    {\displaystyle ~X_{ij}\geqslant 0}
  , իսկ փոքր վանդակներում՝ համապատասխան տարիֆները 
  
    
      
         
        
          C
          
            i
            j
          
        
      
    
    {\displaystyle ~C_{ij}}
  :


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


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


===== Հյուսիս-արևմտյան անկյան մեթոդ (հորիզոնական կամ բարելավված) =====
Յուրաքանչյուր փուլում հնարավոր առավելագույն թվով լրացնում են աղյուսակի մնացած մասի վերին ձախ վանդակը։ Նման կերպ լրացումն այն է, որ ամբողջովին հանվում է բեռը 
  
    
      
         
        
          A
          
            i
          
        
      
    
    {\displaystyle ~A_{i}}
  -ից կամ ամբողջովին բավարարվում է 
  
    
      
         
        
          B
          
            j
          
        
      
    
    {\displaystyle ~B_{j}}
   պահանջարկը։


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

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


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


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


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


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


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


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