1.模型約束矩陣m

行n

行性質(zhì)1.運輸問題的m

+

n個約束只有m

+

n

-

1個是獨立的。且任意m

+

n

-

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

*

****

獨立格子集**

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

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

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

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

的產(chǎn)量皆為15噸，銷地B1,B2

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

可作為轉(zhuǎn)運點，轉(zhuǎn)運量上限皆為10噸，另有轉(zhuǎn)運點T1

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

E1

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

F1

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

F2

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

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

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