1.模型約束矩陣m

行n

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

+

n個(gè)約束只有m

+

n

-

1個(gè)是獨(dú)立的。且任意m

+

n

-

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

*

****

獨(dú)立格子集**

*****非獨(dú)立格子集性質(zhì)3.運(yùn)輸問題的基對(duì)應(yīng)運(yùn)輸表格上含m+n-1個(gè)

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

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

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

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

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

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

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

E1

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

F1

將該原材料供應(yīng)三個(gè)消費(fèi)部門：部門I可將三種原材料互相代用，需求量為150單位；部門II只用一等品，需求量為50單位；部門III只用二或三等品，需求量為50單位。收點(diǎn)

F2

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

，分別對(duì)應(yīng)三個(gè)消費(fèi)部門；將F2拆為兩個(gè)收點(diǎn)B4、B5

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