運(yùn)籌學(xué)-第二三章-運(yùn)輸問題

2023/2/71第二章運(yùn)輸問題

(TransportationProblem,TP)運(yùn)輸問題的數(shù)學(xué)模型運(yùn)輸問題的求解產(chǎn)銷平衡的運(yùn)輸問題求解產(chǎn)銷不平衡的運(yùn)輸問題求解應(yīng)用舉例軟件應(yīng)用2023/2/722.1運(yùn)輸問題的數(shù)學(xué)模型例1

現(xiàn)需將三個(gè)供應(yīng)地KansasCity、Omaha、DesMoines的物品運(yùn)往三個(gè)貨物需求地Chicago、St.Louis、Cincinnati，各供應(yīng)地的供應(yīng)量、各需求地的需求量和各供應(yīng)地運(yùn)往各需求地的每單位物品的運(yùn)費(fèi)如表。如何安排運(yùn)輸，可使得總費(fèi)用最??？ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112200100300600275175150產(chǎn)銷平衡2023/2/73設(shè)為從供應(yīng)地i調(diào)往需求地j

的運(yùn)輸量

2023/2/74產(chǎn)銷平衡模型的一般形式這是一個(gè)線性規(guī)劃滿足2023/2/752.2運(yùn)輸問題的求解2.2.1產(chǎn)銷平衡的運(yùn)輸問題求解求初始基本可行解西北角法最小元素法伏格爾法求最優(yōu)解 閉合回路法（略）位勢法2023/2/76產(chǎn)銷平衡的運(yùn)輸問題2023/2/77求初始基本可行解---“西北角法”5025ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112200(50)0

100300275175

125

150(0)150100275特點(diǎn)：數(shù)字格數(shù)=行數(shù)+列數(shù)-1，其余為空格基解：x11=150,x21=50,x22=100,x23=25,x33=2752023/2/78求初始基本可行解---“最小元素法”175125ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112200(0)10025300275(75)01751502575200特點(diǎn)：數(shù)字格數(shù)=行數(shù)+列數(shù)-1，其余為空格基解：x12=25,x23=125,x23=175,x31=200,x32=752023/2/79求初始基本可行解---“伏格爾法”ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112200(25)10030027517515017510025150150特點(diǎn)：數(shù)字格數(shù)=行數(shù)+列數(shù)-1，其余為空格基解：x13=150,x21=175,x31=25,x32=100,x33=150西北角法最簡單，伏格爾法效果較好2023/2/710求最優(yōu)解

閉合回路法（略）位勢法2023/2/711DLP互補(bǔ)松弛條件：2023/2/712位勢法步驟：Step1：確定初始基本可行解

（西北角法，最小元素法，伏格爾法）Step2：檢驗(yàn)計(jì)算各點(diǎn)位勢值計(jì)算非基變量（空格）的檢驗(yàn)數(shù)檢驗(yàn)非基變量的檢驗(yàn)數(shù)是否0。若是，得到最優(yōu)解；若不是，轉(zhuǎn)入Step32023/2/713Step3：選擇進(jìn)基變量在小于0的非基變量的檢驗(yàn)數(shù)中，選擇最小的，它所對應(yīng)的變量進(jìn)基，也即它從空格變?yōu)閿?shù)字格Step4：選擇出基變量尋找進(jìn)基變量的閉合回路選擇負(fù)號格最小的運(yùn)量為調(diào)整運(yùn)量它對應(yīng)的變量出基，也即它從數(shù)字格變?yōu)榭崭馭tep5：修正表格，得到新的基本可行解。轉(zhuǎn)入Step22023/2/714以例1的最小元素法得到的初始基本可行解開始175125ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply67481151011122001003006002751751502575200Step12023/2/715

ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply674811510111220010030027517515020001-378107517512525Step2計(jì)算各點(diǎn)位勢值

2023/2/716ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply674811510111220010030027517515001-37810-152-1Step3計(jì)算各個(gè)空格的檢驗(yàn)數(shù)，判斷是否最優(yōu)？2023/2/717175125ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply67481151011122001003006002751751502575200（+）（+）（-）（-）Step4確定格子（1，1）的閉合回路（也即確定了進(jìn)基變量）；確定該閉合回路的負(fù)號格，得到負(fù)號格的最小運(yùn)量；確定出基變量

2023/2/718175125ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply674811510111220010030060027517515025100175Step5修正表格再轉(zhuǎn)入Step2

2023/2/719175125ToFromKansasCityOmahaDesMoinesvjChicagoSt.LouisCincinnatiui67481151011126710600-210251001750431轉(zhuǎn)入Step2計(jì)算各個(gè)空格的檢驗(yàn)數(shù)，判斷是否最優(yōu)？--最優(yōu)2023/2/72023/2/721課堂練習(xí)如何安排運(yùn)輸，可使總運(yùn)費(fèi)最??？2023/2/7222.2.2產(chǎn)銷不平衡的運(yùn)輸問題求解產(chǎn)量大于銷量（供大于求）的運(yùn)輸問題銷量大于產(chǎn)量（供不應(yīng)求）的運(yùn)輸問題

轉(zhuǎn)化為產(chǎn)銷平衡的運(yùn)輸問題2023/2/723對例1做些修改ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112200100300275175200產(chǎn)量大于銷量（供大于求）的情形2023/2/724增加一個(gè)虛擬需求地Virtualcity，設(shè)其需求量為50，單位運(yùn)費(fèi)為0，從而把產(chǎn)銷不平衡問題轉(zhuǎn)化為產(chǎn)銷平衡問題

ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply674811510111220010030027517520050000650Virtualcity模型沒有改變！2023/2/725對例1做些修改ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112280100300275175150銷量大于產(chǎn)量（供不應(yīng)求）的情形2023/2/726增加一個(gè)虛擬供應(yīng)地Virtualcity，設(shè)其供應(yīng)量為80，單位運(yùn)費(fèi)為0，從而把產(chǎn)銷不平衡問題轉(zhuǎn)化為產(chǎn)銷平衡問題ToFromKansasCityOmahaDesMoinesDemandChicagoSt.LouisCincinnatiSupply6748115101112280100300680275175150Virtualcity00080模型沒有改變！2023/2/727課堂練習(xí)如何安排運(yùn)輸，可使總運(yùn)費(fèi)最??？2023/2/728轉(zhuǎn)化為產(chǎn)銷平衡問題如下：2023/2/729課堂練習(xí)如何安排運(yùn)輸，可使總運(yùn)費(fèi)最??？2023/2/730轉(zhuǎn)化為產(chǎn)銷平衡問題如下：2023/2/731注意：有相同的運(yùn)價(jià)，如何選擇？有相同的需求量和供應(yīng)量，如何處理？進(jìn)基變量有相同的檢驗(yàn)數(shù)，如何處理？有相同的調(diào)整運(yùn)量，如何處理？對最大化的問題，如何處理？2023/2/732（1）帶罰款的運(yùn)輸問題設(shè)有運(yùn)輸問題：From\ToB1 B2 B3供應(yīng)量A1 5 1 7 10A2 6 4 6 80 A3 5 2 515需求量707050供不應(yīng)求的情形！若銷地B1、B2、B3的需求沒有滿足，則單位罰款成本分別為4、3、2，求總費(fèi)用最小的運(yùn)輸方案2.3應(yīng)用舉例2023/2/733設(shè)為從工廠Ai運(yùn)到銷售點(diǎn)Bj

的運(yùn)輸量

如何化為供需平衡的運(yùn)輸問題呢？2023/2/734求解過程見教科書銷售點(diǎn)工廠A1A2A3需求量B1B2B3供應(yīng)量565142765707050158010A443285轉(zhuǎn)化為供需平衡的運(yùn)輸問題2023/2/735（2）指派問題

現(xiàn)由四人負(fù)責(zé)承擔(dān)四家公司的稅務(wù)工作，規(guī)定每個(gè)工作人員只能負(fù)責(zé)一家公司，已知各費(fèi)用如下：

問如何安排，可使總費(fèi)用最??？2023/2/736轉(zhuǎn)化為供需平衡的運(yùn)輸問題2023/2/737求解過程見教科書2023/2/738（3）生產(chǎn)計(jì)劃問題

某企業(yè)和用戶簽定了設(shè)備交貨合同，已知該企業(yè)各季度的生產(chǎn)能力、每臺設(shè)備的生產(chǎn)成本和每季度末的交貨量如表。若生產(chǎn)出的設(shè)備當(dāng)季度不交貨，每臺設(shè)備每季度需支付保管費(fèi)用0.5萬元，試問在遵守合同的條件下，企業(yè)應(yīng)當(dāng)如何安排生產(chǎn)計(jì)劃，才能使年消耗費(fèi)用最低？2023/2/739問題轉(zhuǎn)化為2023/2/740設(shè)xij是i季度生產(chǎn)用于j季度銷售的量如何化為供需平衡的運(yùn)輸問題呢？2023/2/741轉(zhuǎn)化為供需平衡的運(yùn)輸問題M為充分大的數(shù)2023/2/742(4)特殊要求的運(yùn)輸問題有A、B、C三個(gè)工廠生產(chǎn)同一種玩具，供應(yīng)給Ⅰ、Ⅱ、Ⅲ、Ⅳ四個(gè)地區(qū)進(jìn)行銷售。各工廠的產(chǎn)量，各地區(qū)的需求量以及運(yùn)輸價(jià)格如表。試求總費(fèi)用最省的運(yùn)輸方案2023/2/743設(shè)xij是第i工廠運(yùn)往第j地區(qū)的運(yùn)量如何化為供需平衡的運(yùn)輸問題呢？2023/2/744轉(zhuǎn)化為供需平衡的運(yùn)輸問題M為充分大的數(shù)2023/2/7452.4軟件應(yīng)用

對例1，輸入到LINDO的主界面從Solve菜單中選擇Solve命令，或者單擊按鈕

同理其他例題2023/2/746對例1，輸入到LINGO

的主界面同理其他例題2023/2/72023/2/748第三章整數(shù)規(guī)劃引論整數(shù)規(guī)劃模型純0-1模型混合0-1模型整數(shù)規(guī)劃的求解指派問題軟件應(yīng)用2023/2/7493.1引論定義整數(shù)規(guī)劃：部分或全部變量限制為整數(shù)的規(guī)劃問題整數(shù)線性規(guī)劃：變量限制為整數(shù)的線性規(guī)劃問題整數(shù)規(guī)劃分類如不加特殊說明，一般指整數(shù)線性規(guī)劃對于整數(shù)線性規(guī)劃模型大致可分為兩類：純（完全）整數(shù)規(guī)劃：變量全限制為整數(shù)混合整數(shù)規(guī)劃：部分變量限制為整數(shù)整數(shù)規(guī)劃的求解比線性規(guī)劃要困難得多！2023/2/750考慮

其最優(yōu)解為

若要求x1,x2為整數(shù)，則最優(yōu)解為

無論“四舍五入”，還是“只舍不入”、“只入不舍”，都不能通過求解上面的線性規(guī)劃得到最優(yōu)解

2023/2/751背包問題（投資問題）某公司現(xiàn)有資金100萬，有5個(gè)項(xiàng)目可以投資，每個(gè)項(xiàng)目的投資成本和利潤如下：

如何安排投資，可使總利潤最大？3.2整數(shù)規(guī)劃模型2023/2/752令表示項(xiàng)目j

被采納表示項(xiàng)目j

不被采納則模型為

，2023/2/753附加條件項(xiàng)目1和項(xiàng)目3至少采納一個(gè)：項(xiàng)目2和項(xiàng)目5不能同時(shí)采納：項(xiàng)目1僅在項(xiàng)目2采納后才可考慮是否采納：項(xiàng)目1僅在項(xiàng)目2和3同時(shí)采納后才可考慮是否采納：項(xiàng)目1，2，3不能同時(shí)采納：或者選擇項(xiàng)目1和2，或者選擇項(xiàng)目3：2023/2/754集合覆蓋問題某部門準(zhǔn)備建消防隊(duì)，有五個(gè)候選隊(duì)址。將其管轄地區(qū)劃分為七個(gè)區(qū)域，每個(gè)候選隊(duì)址可覆蓋若干不同區(qū)域（覆蓋指規(guī)定時(shí)間內(nèi)可達(dá)到），如下表。已知候選隊(duì)址1、2、3、4、5建設(shè)消防隊(duì)的建設(shè)費(fèi)用分別為3.1、2.3、3.7、2.6、1.8（百萬元）。問應(yīng)選哪幾個(gè)隊(duì)址可覆蓋七個(gè)區(qū)域，且建設(shè)費(fèi)最小?2023/2/755則模型為2023/2/756運(yùn)輸問題工廠A1和A2生產(chǎn)某種產(chǎn)品，由于這種產(chǎn)品供不應(yīng)求，故需要再建一家工廠，可供選擇的建廠方案有A3、A4、A5，生產(chǎn)的產(chǎn)品運(yùn)往B1,B2,B3,B4。已知單位運(yùn)價(jià)、需求量和年生產(chǎn)能力如表所示。若工廠A3、A4、A5開工后，每年的生產(chǎn)費(fèi)用分別為1200、1500、2000元。問如何決定，可使總費(fèi)用最小？2023/2/757設(shè)xij為Ai

工廠運(yùn)到Bj倉庫的數(shù)量(i

＝1,…,5，

j＝1,2,3,4)，要在A3,A4,

A5

中選擇一家建廠，所以設(shè)2023/2/758生產(chǎn)計(jì)劃問題

某機(jī)器制造廠可生產(chǎn)四種產(chǎn)品，對于三種主要資源（鋼材，人力，能源）的單位消耗及單位利潤見表。問如何安排生產(chǎn)，可使總利潤最大？2023/2/759設(shè)xj表示第j種產(chǎn)品的生產(chǎn)量(j=1，2，3，4)，則模型為最優(yōu)解為最大利潤為

z=6660

增加其他要求后如何建模？

2023/2/760（1）固定成本增加假設(shè)：產(chǎn)品3的生產(chǎn)需要用某一特定機(jī)器，固定成本為3000；產(chǎn)品2和4的生產(chǎn)需要用同一特定機(jī)器，固定成本為1000試建立最佳生產(chǎn)計(jì)劃模型2023/2/761

目標(biāo)函數(shù)修正為

增加約束

其中M為充分大的正數(shù)(本例)若x3>0，則顯然有y3=1若x3=0，由于目標(biāo)函數(shù)中-3000y3的存在，必有y3=0.另一部分同理

2023/2/762得到數(shù)學(xué)模型2023/2/763（2）批量生產(chǎn)增加假設(shè)：產(chǎn)品4要求批量生產(chǎn)，批量為不少于500件試建立最佳生產(chǎn)計(jì)劃模型增加約束2023/2/764得到數(shù)學(xué)模型2023/2/765（3）銷售政策：增加假設(shè)：市場上要求4種產(chǎn)品中至少3種的供應(yīng)量不少于100件試建立最佳生產(chǎn)計(jì)劃模型2023/2/766定義四個(gè)0-1變量yj

(j=1，2，3，4)

增加約束2023/2/767得到數(shù)學(xué)模型2023/2/768（4）規(guī)模經(jīng)濟(jì)增加假設(shè)：產(chǎn)品3售價(jià)20，成本如下：試建立最佳生產(chǎn)計(jì)劃模型2023/2/7692023/2/770得模型為產(chǎn)品3的單位銷售價(jià)為20，則相應(yīng)利潤為2023/2/72023/2/772選址問題

有m

個(gè)地方可建廠，預(yù)計(jì)產(chǎn)量分別為ai(i=1,…,m)，建設(shè)費(fèi)用分別為

fi(i=1,…,m)

。現(xiàn)在有n

個(gè)銷點(diǎn)，各銷點(diǎn)的需求量分別為bj(j=1,…,n)，廠址i

到銷點(diǎn)j

的運(yùn)價(jià)為cij?，F(xiàn)要求從m個(gè)廠址中選擇Ｍ個(gè)建廠。問如何選擇，可使建設(shè)費(fèi)用和運(yùn)輸費(fèi)用之和最??？（要求滿足需要）2023/2/773設(shè)xij為廠址i向銷點(diǎn)j的運(yùn)送量(i=1,2,…,m,j=1,2,…,n)，并設(shè)則模型為2023/2/774排序問題

三種產(chǎn)品A,B,C各要在三臺機(jī)器上加工，加工順序是1-2-3，其他數(shù)據(jù)如表。每臺機(jī)器同時(shí)只能加工一種產(chǎn)品。問如何安排，可以在最短的時(shí)間內(nèi)完成三種產(chǎn)品的加工？2023/2/775設(shè)xij為產(chǎn)品i在機(jī)器j上開始加工的時(shí)間(i=A,B,C，

j=1,2,3)；z為從開始到所有產(chǎn)品加工完所用的時(shí)間；yj為0-1變量，表示j

機(jī)器加工產(chǎn)品的順序(j=1,2,3)

2023/2/776得模型為其中M是充分大的正數(shù)2023/2/7770-1變量使用技巧條件

等價(jià)于其中M為充分大的正數(shù)2023/2/778ai1

x1+ai2

x2

+…+ainxn

bi(i=1,…,m)為互相獨(dú)立m

個(gè)約束，但只有一個(gè)起作用ai1

x1+…+ainxn

bi+(1-yi)M

(i=1,…,m)y1

+…+ym=1yi=0或1，M>0條件

其中M是充分大的正數(shù)

等價(jià)于2023/2/779條件等價(jià)于

2023/2/7803.3整數(shù)規(guī)劃的求解含0-1變量的整數(shù)規(guī)劃純0-1規(guī)劃：枚舉法，隱枚舉法（過濾隱枚舉法；分枝隱枚舉法）混合0-1規(guī)劃：特別處理不含0-1變量的整數(shù)規(guī)劃：分枝定界法，割平面法2023/2/781純0-1規(guī)劃求解之枚舉法：考慮變量的每一種可能取值（總數(shù)有限），通過比較得到最優(yōu)解枚舉法只適用于變量個(gè)數(shù)較少的情形！國際象棋的例子2023/2/78251234678f1=0x3=0x2=0f2=15x3=1x1=0f3=-(不可行)x3=0x2=1f4=-(不可行)x3=1f5=20x3=0x2=0x3=1f6=35x1=1f7=-(不可行)x2=1x3=0f8=-（不可行)x3=12023/2/783純0-1規(guī)劃求解之隱枚舉法：只選擇性檢查一部分變量取值，就可能得到最優(yōu)解2023/2/784√√√√√√√√√√

2023/2/7850-1規(guī)劃的隱枚舉法的具體步驟第一步：將模型標(biāo)準(zhǔn)化：1.目標(biāo)函數(shù)為最小優(yōu)化2.目標(biāo)函數(shù)中變量的系數(shù)都為正（x

1-x）3.目標(biāo)函數(shù)中變量按系數(shù)值從小到大排列，約束函數(shù)中變量的排列次序也做相應(yīng)改變第二步：在標(biāo)準(zhǔn)化后的模型中，令所有的變量為0，以此作為母方案。檢驗(yàn)?zāi)阜桨甘欠駶M足所有約束條件，如果滿足即為問題的最優(yōu)解，否則進(jìn)入第三步第三步：分枝與擇優(yōu)2023/2/72023/2/786不含0-1變量的整數(shù)規(guī)劃之分枝定界法

2023/2/7872023/2/788maxz=2x1

+x2

s.t.

x2

3

3x1

+x2

12

x1+x2

5

x1，x2

0

且為整數(shù)例

2023/2/789z=02023/2/790分枝定界法2023/2/791B1問題2023/2/792B1問題2023/2/793B1問題2023/2/794B2問題2023/2/795B2問題2023/2/796B2問題2023/2/797不含0-1變量的整數(shù)規(guī)劃之割平面法：求得線性規(guī)劃的最優(yōu)解后，通過增加“割約束”割掉最優(yōu)解，但不割掉任何整數(shù)可行解，逐步求得原問題的最優(yōu)解割約束2023/2/798maxz=2x1

+x2

s.t.x2

3

3x1

+x2

12

x1

+x2

5

x1，x2

0

且為整數(shù)例2023/2/799相當(dāng)于增加約束：2023/2/7100增加割約束之后的單純形表2023/2/7101得到最優(yōu)解：2023/2/7102變換一下還可以得到另一個(gè)最優(yōu)解：2023/2/7103整數(shù)規(guī)劃模型舉例：選擇/是非問題、大型設(shè)備問題等整數(shù)規(guī)劃求解純0-1規(guī)劃：枚舉法、隱枚舉法不含0-1變量的整數(shù)規(guī)劃：分枝定界法、割平面法指派問題：匈牙利法2023/2/71043.4指派問題指派問題的數(shù)學(xué)模型

現(xiàn)要安排四位工作人員完成四種工作，每人只完成一種。記工作種類分別為A、B、C、D，工作人員分別為甲、乙、丙、丁，已知工作人員完成各工作所需要的費(fèi)用如表所示。應(yīng)指派何人去完成何項(xiàng)工作，可使所需的總費(fèi)用最少？

2023/2/7105設(shè)

指派問題模型為2023/2/7106練習(xí)1

現(xiàn)由五家建筑公司完成建造五家新商店，規(guī)定每家建筑公司只能建造一家商店，已知各費(fèi)用如表。問如何安排，可使總費(fèi)用最小?

2023/2/7107Ex3.1-(7)

分配甲、乙、丙、丁四個(gè)人去完成五項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)時(shí)間如下表。由于任務(wù)數(shù)多于人數(shù)，故規(guī)定其中有一個(gè)人可兼完成兩項(xiàng)任務(wù)，其余三人每人完成一項(xiàng)。試確定總花費(fèi)時(shí)間為最少的指派方案2023/2/71082023/2/72023/2/7109指派問題的求解之“匈牙利算法”

Step1：對矩陣(cij)做如下變換，使其在各行各列中都出現(xiàn)0每行元素減去該行的最小元素（若該行已有0則不必變換）再將每列減去該列的最小元素（若該列已有0則不必變換）2023/2/72023/2/7110Step2：進(jìn)行試指派以尋求最優(yōu)解。為此按如下五個(gè)分步驟進(jìn)行從只有一個(gè)0的行/列開始，給這個(gè)0加圈（下記為），然后劃去所在的列/行的其它0（下記為?）。這表示該列/行所代表的任務(wù)已被指派在剩余的行列中，給只有一個(gè)0的行/列的0加圈，然后劃去所在列/行的0重復(fù)進(jìn)行上述步驟，直到所有0都被圈出或劃掉為止若同行/列不止一個(gè)0（表示對這個(gè)人可以從幾項(xiàng)任務(wù)中指派其一），則可用不同的方案去試探。從所剩0最少的行/列開始，比較該行/列0所在列/行中0的數(shù)目，選擇0少的列/行的0加圈（表示選擇性多的要“禮讓”選擇性少的）。然后劃掉同行/列的其它0。反復(fù)進(jìn)行直到所有0都已被圈出或劃掉若的數(shù)目m

等于矩陣階數(shù)

n

，則得到指派問題的最優(yōu)解。若m<n

，則轉(zhuǎn)入Step32023/2/72023/2/7111例2023/2/7112找到了4個(gè)不同行不同列的元素，所以該問題的最優(yōu)解矩陣是

意即：指定甲完成工作A乙完成工作C丙完成工作B丁完成工作D所需最少總費(fèi)用為322023/2/7113例：求如下系數(shù)矩陣所對應(yīng)的指派問題由于獨(dú)立

元素的個(gè)數(shù)m=4<5，所以解題沒有完成，應(yīng)按下面的步驟繼續(xù)進(jìn)行2023/2/7114Step3：作最少的直線覆蓋所有的0元素，以確定該系數(shù)矩陣中能找到最多的獨(dú)立元素。為此按以下步驟進(jìn)行：對沒有的行打

對已打的行中包含有?

元素的列打

再對有打的列中含有的行打

重復(fù)上述步驟直到得不出新的打的行、列為止對沒有打的行畫橫線，對打的列畫縱線，這就得到了能夠覆蓋所有0元素的最少直線數(shù)。令直線數(shù)為l。若l<n，則說明必須再變換當(dāng)前的系數(shù)矩陣，才能找到n

個(gè)獨(dú)立的

元素，為此轉(zhuǎn)入Step4。若l=n，應(yīng)回到