1.模型約束矩陣m

行n

行性質1.運輸問題的m

+

n個約束只有m

+

n

-

1個是獨立的。且任意m

+

n

-

1個約束是獨立的。性質2.運輸問題一定有可行解。銷地產地供應量需求量由于目標值有下界零，性質2表明運輸問題一定有最優解，用單純形算法求解運輸問題可以在下面的運輸表格上實現。**

*

****

獨立格子集**

*****非獨立格子集性質3.運輸問題的基對應運輸表格上含m+n-1個

格子的獨立格子集。推論：獨立格子集對應的約束矩陣列向量線性獨立。2.求初始基本可行解A.西北角法原則：優先安排編號小的發點和收點之間的運輸業務（運輸表格上西北角）。ji供應量需求量510010例.用西北角法求初始基本可行解ji供應量需求量510050520例.用西北角法求初始基本可行解ji供應量需求量5100050例.用西北角法求初始基本可行解1520ji供應量需求量5100050例.用西北角法求初始基本可行解15505ji供應量需求量5100050例.用西北角法求初始基本可行解1500555ji供應量需求量51051555西北角法求得的初始基本可行解注：事實上，在求初始基本可行解時，可從運輸表格的任何位置開始分配運量，B.最小元素法原則：優先安排單位運費最小的發點與收點之間的運輸業務。如ji供應量需求量15例.用最小元素法求初始基本可行解00500151000010ji供應量需求量15最小元素法求得的初始基本可行解5150010C.伏格爾法首先計算各行、各列最小與次小運價的差額，選出差額最大的行或列，選擇該行或列的最小運價，優先安排相應的運輸業務。（差額越大說明不按最小運費運輸時，運費增加越多，因而應優先采用最小運費運輸。）ji供應量需求量4284177500例.用伏格爾法求初始基本可行解ji供應量需求量522177500例.用伏格爾法求初始基本可行解15100ji供應量需求量513417500例.用伏格爾法求初始基本可行解1510010ji供應量需求量513417500例.用伏格爾法求初始基本可行解1501005ji供應量需求量54500例.用伏格爾法求初始基本可行解150100587510ji供應量需求量54500例.用伏格爾法求初始基本可行解15010087510010ji供應量需求量54500例.用伏格爾法求初始基本可行解150100875010000ji供應量需求量5伏格爾法求得的初始基本可行解151051003.用位勢法計算檢驗數運輸問題的對偶問題：因為運輸問題有一個約束是多余的，應刪去，相應地，對偶問題中應刪去一個變量，于是令該變量取值為0，比如u1=0。由對偶理論，有由于基變量的檢驗數為0，得m+n-1個方程：進而可計算出非基變量的檢驗數，最優性準則要求所有檢驗數大于等于0。注：由于對偶解也稱為位勢，所以上述方法稱為位勢法。ji供應量需求量5105155501061819-

14.迭代ji5105155512199*ji供應量需求量55101550121115106111878*ji供應量需求量51015001212111085611187-111已為最優解。5.不平衡運輸問題6.轉運問題產地生產的產品不一定直接運到銷地，而是先運往幾個產品集散地集中，再轉運至各銷地，這些產品集散地（轉運點）可能是專門的轉運站，也可能就是某幾個產地或銷地，這類運輸問題稱為轉運問題。轉運點將既是發點，也是收點，而純粹的產地只是發點，純粹的銷地只是收點。注：非轉運點的轉運量為零，各轉運點的轉運量是實際發生的轉運量的一個上限，由各自的倉儲設備、運輸條件等決定。由于轉運量同時計算在ai、bj

中，所以如果各產地的總產量等于各銷地的總銷量（即產銷平衡），那么否則可參照不平衡運輸問題處理。關于運價，可假設同一個轉運點間的運價為零。計算結果中發生在同一個轉運點之間的轉運實際上不發生，轉運量上限減去它之后就是實際的轉運量。例.產地A1,A2

的產量皆為15噸，銷地B1,B2

的銷量也皆為15噸，A1,B1

可作為轉運點，轉運量上限皆為10噸，另有轉運點T1

，轉運量不能超過20噸。則運輸表格為發點發量收量收點7.多品種物資運輸問題發點

E1

有某原材料一等品200單位、二等品300單位，E2有該原材料一等品100單位、三等品150單位。收點

F1

將該原材料供應三個消費部門：部門I可將三種原材料互相代用，需求量為150單位；部門II只用一等品，需求量為50單位；部門III只用二或三等品，需求量為50單位。收點

F2

將該原材料供應兩個消費部門：部門i使用一或二等品，需求量為200單位；部門ii只用一等品，需求量為300單位。單位運價：F2F1E1E25786將E1拆為兩個發點：A1輸出一等品200單位，A2輸出二等品300單位。將E2也拆為兩個發點：A3輸出一等品100單位，A4輸出三等品150單位。類似地，將F1拆為三個收點B1、B2、B3

，分別對應三個消費部門；將F2拆為兩個收點B4、B5

，對應兩個消費部門。該問題的產銷是不平衡的，如：一等品總產量300單位，而需求量至少50+300=350單位；二、三等品總產量450單位，而需求量至多150+50+200=400單位。因此引入虛發點A5和虛收點B6，它們與實際的發點、收點之間的運價很大（為M），而它們之間的運價為零，這樣，只有在實際的發點、收點之間的運輸安排不了時才考慮與A5、B6間的運輸。由于事先不知道有多少運量安排不了，因此假設A5的輸出量和B6的需求量足夠大（該問題中750已足夠）。B1B2B3B4