第3章特殊類型的線性規(guī)劃22

第三章特殊類型的線性規(guī)劃一般意義的線性規(guī)劃問題==第一節(jié)運輸問題先看一個具體的例子——例3-1

某廠下屬三個加工廠同生產(chǎn)一種產(chǎn)品，每天的生產(chǎn)量分別是A1=8噸，A2=7噸，A3=10噸；該工廠把這些產(chǎn)品分別運往四個地區(qū)的門市部銷售，各門市部的銷售量分別為B1=3噸，B2=4噸，B3=9噸，B4=9噸。已知從各加工廠到各門市部的每噸運費如下表所示。問該工廠如何制定調(diào)運產(chǎn)品的方案，在滿足各門市部銷售量的情況下，使總的費用為最少？B1B2B3B4A122316A211623A347108先建立數(shù)學(xué)模型假設(shè)從工廠到門市部的運輸量為則有Cij為工廠到門市部單位物資的運價ai為第i個工廠的產(chǎn)量bj為第j個門市部的銷售量該問題數(shù)學(xué)模型的特點工廠有3(m)個，門市部有4(n)個有3×4(

m×n)個變量有3+4(m+n)個約束方程用單純形法求解需添加7個人工變量變量數(shù)增加為19個，求解計算量大本例中所建立的數(shù)學(xué)模型一般意義上的系數(shù)矩陣系數(shù)矩陣的每一列元素中均只有兩個元素為1，其余元素均為零本例中，工廠的產(chǎn)量與門市部的銷量相等，稱為產(chǎn)銷平衡的運輸問題。某廠下屬三個加工廠同生產(chǎn)一種產(chǎn)品，每天的生產(chǎn)量分別是A1=8噸，A2=7噸，A3=10噸；該工廠把這些產(chǎn)品分別運往四個地區(qū)的門市部銷售，各門市部的銷售量分別為B1=3噸，B2=4噸，B3=9噸，B4=9噸。產(chǎn)銷平衡的運輸問題一定有最優(yōu)解例3-2為了簡化計算過程，利用運輸問題系數(shù)矩陣的特點，在單純形法的基礎(chǔ)上，創(chuàng)造了一種專門求解運輸問題的方法，稱為表上作業(yè)法。表上作業(yè)法的求解過程也包含如下三個關(guān)鍵步驟：（1）初始基可行解（也稱初始運輸方案）的確定；（2）基可行解檢驗數(shù)的計算與最優(yōu)判別；（3）非最優(yōu)基可行解的改進（迭代）。

例3-3

假設(shè)某地區(qū)有三個交通發(fā)生點和四個交通吸引點，交通發(fā)生點的出行產(chǎn)生量ai、交通吸引點的出行吸引量bj以及各交通發(fā)生點與吸引點之間的運輸費用如下表所示。問如何組織交通，才能使總的運輸費用最少？

交通吸引點交通發(fā)生點D1D2D3D4aiO144325O2103475O399845bj162615求解該問題分三個步驟確定初始方案檢驗該方案是否為最優(yōu)方案調(diào)整方案計算停止是否確定初始方案的方法之一

西北角法

西北角法的基本思想是優(yōu)先產(chǎn)銷平衡表的左上角（西北角）的供應(yīng)關(guān)系。步驟一確定初始方案在逐步確定初始運輸方案時，一般每步要經(jīng)過兩個過程，先是根據(jù)運輸費用確定供應(yīng)關(guān)系，然后根據(jù)供需要求進行運量分配。為了方便，將產(chǎn)銷平衡與運輸費用表拆成運輸費用與運量分配表。

交通吸引點交通發(fā)生點D1D2D3D4aiO144325O2103475O399845bj162615產(chǎn)銷平衡與出行費用表步驟一確定初始方案

交通吸引點交通發(fā)生點D1D2D3D4O14432O210347O39984運輸費用表

交通吸引點交通發(fā)生點D1D2D3D4aiO15O25O35bj162615運量分配表從運量分配表的最左上角（西北角）的格子開始。讓發(fā)生點O1的物資盡可能多地運往吸引點D1。由于吸引點D1需要的物資總量只有1，而發(fā)生地O1要求運出的物資總量為5，所以O(shè)1要運出的物資總量中1個單位運至D1，即x11=1，將此運量１填入運量分配表的（O1,D1）格子。這時吸引點D1物資需求量已經(jīng)滿足，不再需要其他任何發(fā)生地運來物資，由平衡條件得x21=0，x31=0。１步驟一確定初始方案

交通吸引點交通發(fā)生點D1D2D3D4O14432O210347O39984出行費用表

交通吸引點交通發(fā)生點D1D2D3D4aiO1１5O25O35bj162615運量分配表從運量分配表當(dāng)前的最左上角（西北角）的格子（O1,D２

）開始。讓發(fā)生點O1的物資盡可能多地運往吸引點D２。由于吸引點D２需要的物資總量為６，而發(fā)生地O1當(dāng)前能運出的物資總量為４，所以O(shè)1能運出的物資總量中４個單位運至D２，即x1２=4，將此運量４填入運量分配表的（O1,D２）格子。這時發(fā)生地O1物資運出量已經(jīng)滿足，不能再向其他任何吸引點運送物資，由平衡條件得x1３=0，x1４=0。４步驟一確定初始方案

交通吸引點交通發(fā)生點D1D2D3D4O14432O210347O39984出行費用表

交通吸引點交通發(fā)生點D1D2D3D4aiO1１４5O25O35bj162615運量分配表從運量分配表當(dāng)前的最左上角（西北角）的格子（O２,D２）開始。讓發(fā)生點O２的物資盡可能多地運往吸引點D２。由于當(dāng)前吸引點D２需要的物資總量只有２，而發(fā)生地O２要求運出的物資總量為5，所以O(shè)２要運出的物資總量中２個單位運至D２，即x２２=２，將此運量２填入運量分配表的（O２,D２）格子。這時吸引點D２物資需求量已經(jīng)滿足，不再需要其他任何發(fā)生地運來物資，由平衡條件得x３２=0。２步驟一確定初始方案

交通吸引點交通發(fā)生點D1D2D3D4O14432O210347O39984出行費用表

交通吸引點交通發(fā)生點D1D2D3D4aiO1１４5O2２5O35bj162615運量分配表從運量分配表當(dāng)前的最左上角（西北角）的格子（O２,D３）開始。讓發(fā)生點O２的物資盡可能多地運往吸引點D３。由于吸引點D３需要的物資總量只有２，而發(fā)生地O２當(dāng)前能運出的物資總量為３，所以O(shè)２運出的物資總量中２個單位運至D３，即x２３=２，將此運量２填入運量分配表的（O２,D３）格子。這時吸引點D３物資需求量已經(jīng)滿足，不再需要其他任何發(fā)生地運來物資，由平衡條件得x３３=0。２步驟一確定初始方案

交通吸引點交通發(fā)生點D1D2D3D4O14432O210347O39984出行費用表

交通吸引點交通發(fā)生點D1D2D3D4aiO1１４5O2２２5O35bj162615運量分配表從運量分配表當(dāng)前的最左上角（西北角）的格子（O２,D４）開始。讓發(fā)生點O２的物資盡可能多地運往吸引點D４。由于吸引點D４需要的物資總量為６，而發(fā)生地O２當(dāng)前能運出的物資總量為１，所以O(shè)２運出的物資總量中１個單位運至D４，即x２４=１，將此運量１填入運量分配表的（O２,D４）格子。這時發(fā)生地D２物資需求量已經(jīng)滿足，不能再向其他任何吸引點運來物資。１步驟一確定初始方案

交通吸引點交通發(fā)生點D1D2D3D4O14432O210347O39984出行費用表

交通吸引點交通發(fā)生點D1D2D3D4aiO1１４5O2２２１5O35bj162615運量分配表從運量分配表當(dāng)前的最左上角（西北角）的格子（O３,D４）開始。讓發(fā)生點O３的物資盡可能多地運往吸引點D４。由于當(dāng)前吸引點D４需要的物資總量為５，而發(fā)生地O３當(dāng)前能運出的物資總量為５，所以O(shè)３運出的物資總量中５個單位運至D４，即x３４=５，將此運量５填入運量分配表的（O３,D４）格子。５步驟一確定初始方案

交通吸引點交通發(fā)生點D1D2D3D4O14432O210347O39984出行費用表

交通吸引點交通發(fā)生點D1D2D3D4aiO1１４5O2２２１5O3５5bj162615運量分配表已經(jīng)找到了一個初始方案＝６１步驟一確定初始方案最小元素法的基本思想是就近供應(yīng)，即依據(jù)單位運價表中最小的運價來確定供需關(guān)系。

確定初始方案的方法之二

最小元素法步驟一確定初始方案

交通吸引點交通發(fā)生點D1D2D3D4O14432O210347O39984運輸費用表

交通吸引點交通發(fā)生點D1D2D3D4aiO15O25O35bj162615運量分配表551121從出行費用表中選擇最小費用項，確定相應(yīng)的運量，并使其滿足出行總量平衡條件。初始方案的費用為63步驟一確定初始方案最優(yōu)方案的判別

運輸方案的最優(yōu)性判別，實質(zhì)上與單純形法是一樣的。首先，計算運量分配表中每個空格（即非基變量）的檢驗數(shù)，然后判別每個檢驗數(shù)的正負(fù)。因為運輸問題是求目標(biāo)函數(shù)極小化的問題，所以，當(dāng)所有≥0時，此時的運輸方案即為最優(yōu)運輸方案，否則，再改進當(dāng)前的運輸方案。求檢驗數(shù)的方法很多。常用方法有兩種：閉回路法和位勢法。步驟二最優(yōu)方案的判別

在原方案的分配表中，從一個空格開始作一條閉回路，這個閉回路的邊只能是水平或垂直的；而它的轉(zhuǎn)角，除了開始這個空格之外，其余的都是填有數(shù)字的格（有交通量的格）。判別最優(yōu)方案的方法之一

閉回路法步驟二最優(yōu)方案的判別

交通吸引點交通發(fā)生點D1D2D3D4aiO1１４5O2２２１5O3５5bj162615運量分配表可以證明，運量分配表中的任意一個空格與所有的數(shù)字格組成的格子中，一定有且僅有一個閉回路步驟二最優(yōu)方案的判別根據(jù)閉回路求檢驗數(shù)每一個空格對應(yīng)一個檢驗數(shù)每一個空格的檢驗數(shù)根據(jù)該空格的閉回路確定檢驗數(shù)的計算起點空格的運費為正第一個轉(zhuǎn)角的運費為負(fù)第二個轉(zhuǎn)角的運費為正第三個轉(zhuǎn)角的運費為負(fù)

…

…

…

…

…

…如此正負(fù)交替直至回到起點空格將這些數(shù)字相加，得到該空格的檢驗數(shù)步驟二最優(yōu)方案的判別偶數(shù)轉(zhuǎn)角運費為正奇數(shù)轉(zhuǎn)角運費為負(fù)

交通吸引點交通發(fā)生點D1D2D3D4aiO1１４5O2２２１5O3５5bj162615運量分配表

交通吸引點交通發(fā)生點D1D2D3D4O14432O210347O39984出行費用表檢驗數(shù)λ31=9-4+7-3+4-4=9檢驗數(shù)的含義若存在某檢驗數(shù)小于0，則對應(yīng)于該檢驗數(shù)的出行量增大，總出行費用將減少。若所有的檢驗數(shù)都為非負(fù)，則總的出行費用將不可能減少。步驟二最優(yōu)方案的判別得到如下的檢驗數(shù)表：

D1D2D3D4O1-2-6O27O3997

交通吸引點交通發(fā)生點D1D2D3D4aiO1１４5O2２２１5O3５5bj162615運量分配表步驟二最優(yōu)方案的判別判別最優(yōu)方案的方法之二

勢位法步驟二最優(yōu)方案的判別方案的調(diào)整若存在檢驗數(shù)小于0，則對應(yīng)于該檢驗數(shù)的出行量增大，總出行費用將減少，說明可能存在總費用更小的運輸方案。步驟三方案的調(diào)整步驟三方案的調(diào)整選擇一個負(fù)檢驗數(shù)找出該負(fù)檢驗數(shù)對應(yīng)的閉回路從空格出發(fā)，沿閉合回路前進，在各奇數(shù)次轉(zhuǎn)角點數(shù)字（即出行交通量）中，選擇最小值K在閉合回路中，在各奇數(shù)次轉(zhuǎn)角點的數(shù)字都減K，在各偶數(shù)次轉(zhuǎn)角點的數(shù)字都加K步驟三方案的調(diào)整檢驗數(shù)D1D2D3D4O1-2-6O27O3997選擇一個負(fù)檢驗數(shù)

交通吸引點交通發(fā)生點D1D2D3D4O1１４O2２２１O(jiān)3找出該負(fù)檢驗數(shù)對應(yīng)的閉回路從空格出發(fā)，沿閉合回路前進，在各奇數(shù)次轉(zhuǎn)角點數(shù)字（即出行交通量）中，選擇最小值Kmin（4，1）=1在閉合回路中，在各奇數(shù)次轉(zhuǎn)角點的數(shù)字都減K，在各偶數(shù)次轉(zhuǎn)角點的數(shù)字都加K

交通吸引點交通發(fā)生點D1D2D3D4O1１31O23２0O3對新得到的分配方案，繼續(xù)進行檢驗。檢驗數(shù)D1D2D3D4O1-2O276O33310

交通吸引點交通發(fā)生點點D1D2D3D4O1１31O23２O3５存在負(fù)檢驗數(shù)，目前的方案沒有達到最優(yōu)步驟三方案的調(diào)整檢驗數(shù)D1D2D3D4O1-2O276O3331選擇一個負(fù)檢驗數(shù)

交通吸引點交通發(fā)生點D1D2D3D4O1１31O23２O3５找出該負(fù)檢驗數(shù)對應(yīng)的閉回路從空格出發(fā)，沿閉合回路前進，在各奇數(shù)次轉(zhuǎn)角點數(shù)字（即出行交通量）中，選擇最小值Kmin（3，2）=2在閉合回路中，在各奇數(shù)次轉(zhuǎn)角點的數(shù)字都減K，在各偶數(shù)次轉(zhuǎn)角點的數(shù)字都加K

交通吸引點交通發(fā)生點D1D2D3D4O1１121O2500O3５對新得到的分配方案，繼續(xù)進行檢驗。

交通吸引點交通發(fā)生點D1D2D3D4O1１121O25O3５檢驗數(shù)D1D2D3D4O1O2726O3333所有的檢驗數(shù)都為非負(fù)，則總的出行費用將不可能減少，目前得到的方案為最優(yōu)的運輸方案。運輸問題的作業(yè)教材習(xí)題3-2工程中有些線性規(guī)劃問題要求解為整數(shù)如：

以人員、車輛等規(guī)劃對象原有的計算方法得到的解存在非整數(shù)的可能第二節(jié)

整數(shù)規(guī)劃

求解整數(shù)規(guī)劃的方法—分枝定界法先看一個實例先不考慮整數(shù)約束，解相應(yīng)的線性規(guī)劃問題為了討論方便，將原線性規(guī)劃問題稱為L1。L1的最優(yōu)解為x1=2.25，x2=3.75，Z=41.25例3-4L1的最優(yōu)解為x1=2.25，x2=3.75不滿足整數(shù)條件劃分可行域取x2≤3，x2≥4L2L3任取一個沒有滿足整數(shù)條件的變量L2的最優(yōu)解為x1=1.8，x2=4，Z=41L3的最優(yōu)解為x1=3，x2=3，Z=39L2L3已經(jīng)得到整數(shù)解L2的最優(yōu)解為x1=1.8，x2=4不滿足整數(shù)條件劃分可行域取x1≤1，x1≥2L4L5L4的最優(yōu)解為x1=1，x2=4.44，Z=40.444L5無最優(yōu)解L4的最優(yōu)解為x1=1，x2=4.44不滿足整數(shù)條件劃分可行域取x2≤4，x2≥5L6L7L6的最優(yōu)解為x1=1，x2=4，Z=37L7的最優(yōu)解為x1=0，x2=5，Z=40原問題LP1新問題LP2新問題LP3新問題LP5新問題LP4新問題LP7新問題LP6直到找到最優(yōu)整數(shù)解或無最優(yōu)解匯總整數(shù)解非整數(shù)解非整數(shù)解無最優(yōu)解整數(shù)解整數(shù)解非整數(shù)解總結(jié)：分枝定界法思路：首先不考慮解為整數(shù)的要求，用單純形法求最優(yōu)解，以此作為目標(biāo)函數(shù)值的上限或下限；其次，選擇其中一個非整數(shù)的變量，根據(jù)與兩側(cè)相近的整數(shù)劃分可行域，在縮小的可行域內(nèi)尋求最優(yōu)整數(shù)解，以此作為目標(biāo)函數(shù)值的上限或下限；不斷重復(fù)以上過程，直到每一個可能進一步分解的非整數(shù)都找到整數(shù)解時為止，整數(shù)規(guī)劃作業(yè)教材習(xí)題3-70-1整數(shù)規(guī)劃0-1規(guī)劃是指變量只能取0或1的線性規(guī)劃，是一種特殊的整數(shù)規(guī)劃。在進行實際問題最優(yōu)決策和處理問題時常常會碰到這樣的0-1規(guī)劃。例3-5

某道橋公司在同一時間內(nèi)可參加A1、A2、A3、A4四項工程的投標(biāo)。這些項目要求的工期相同。公司根據(jù)招標(biāo)文件和本公司的技術(shù)水平對每項工程進行了仔細的研究和計算，將各項工程的預(yù)期利潤，主要工序的工程量及本企業(yè)的施工能力見下表。問該公司對哪幾種項目投標(biāo)可能獲得的總利潤最大？試建立這個問題的數(shù)學(xué)模型。工程項目預(yù)期利潤（萬元）土石方量（m3）混凝土量（m3）其他材料（m3）A1542002802500A282300880480A37.548003001500A4923009005200施工能力1200016009000建立模型設(shè)則建立的數(shù)學(xué)模型0-1規(guī)劃的一般形式0-1規(guī)劃的求解方法——窮舉法每個變量都只取0，1兩個值，變量取值的0-1組合是有限的。先列出各變量分別取0或1值的每一種組合，然后在滿足約束條件的變量的0-1組合中找出使目標(biāo)函數(shù)達到最優(yōu)值的組合即是該0-1規(guī)劃的最優(yōu)解。用這種方法求解變量個數(shù)為n的0-1規(guī)劃，通常需檢查2n個組合計算量大，隨變量數(shù)量的增加呈集合級數(shù)增長設(shè)計一種方法，只要檢查變量取值的一部分就能得到原問題的最優(yōu)解。這種方法稱為隱枚舉法。例3-6解：首先，通過試探的方法找到一個可行解。容易看出,(x1,x2,x3)=(1,0,0)是滿足約束條件的可行解。相應(yīng)的目標(biāo)函數(shù)值為S=3。對于最大化問題，希望S≥3，因此，增加一個約束條件過濾條件新的0-1規(guī)劃問題為（0）全部枚舉的方法，3個變量有8種組合原先4個約束方程，需要32次計算增加過濾條件后，可減少計算次數(shù)解約束條件是否滿足條件？S值（0）（1）（2）（3）（4）（0，0，0）0（0，0，1）5-11015（0，1，0）-2（0，1，1）315（1，0，0）311103（1，0，1）802118（1，1，0）1（1，1，1）626（0）0-1規(guī)劃作業(yè)教材習(xí)題3-5第三節(jié)資源分配問題

有n項任務(wù)，分配給n個人去完成，要求每個人完成其中一項任務(wù)，每項任務(wù)只交給其中一個人完成，已知每個人完成各項任務(wù)的成本（或效率），求使總成本最少的分配方案。

目的地車輛編號D1D2D3D4D5D6146665559202822481256225913282239502786446314547545856544644331606322434243364設(shè)某運輸隊有6輛卡車，需分派駛往6個不同的目的地，由于各輛卡車的性能、消耗和效率不同，因而駛往各目的地的運輸成本也不同，如下表所示。試求能使總成本最低的車輛分派方案。例3-7效率矩陣建立數(shù)學(xué)模型資源分配問題的一般模型minZ=s.t.運輸問題整數(shù)規(guī)劃資源分配問題資源分配問題的求解方法—匈牙利法定理

效率矩陣的任意一行（列）各元素中分別減去同一常數(shù)，得一變換了的矩陣，則以之為效率矩陣的分派問題最優(yōu)解與原問題的最優(yōu)解相同。

匈牙利法的指導(dǎo)思想設(shè)法對效率矩陣進行變換，使變換后的效率矩陣中有n個位于不同行不同列的零元素（以下稱為獨立零元素），沒有負(fù)元素。令n個獨立零元素對應(yīng)的n個xij＝１，其余的xij＝0匈牙利法的解題步驟——例3-8

有5輛公交車可以在5條公交線路上行駛。不同車輛在不同的路線上發(fā)生的年平均交通事故數(shù)如下表所示。這5輛公交車如何分配，才能使全年的總事故數(shù)最少？匈牙利法的解題步驟

線路編號車輛R1R2R3R4R5D173328D2108697D392706D460835D553427使費用矩陣每行中出現(xiàn)零元素在各行中減去各行的最小元素使費用矩陣出現(xiàn)0元素332886972706083553427110620312706083531205初始的費用矩陣110620312706083531205第一列、第五列中無0元素。在第一列、第五列中分別減該列的最小元素。使費用矩陣出現(xiàn)0元素2110512030627053083401204費用矩陣每行、每列中都出現(xiàn)了0元素檢驗是否存在位于

不同行不同列的n個0元素檢驗是否存在不同行列的0元素2110512030627053083401204行檢驗：若某行只有一個零元素，則給這零元素加“Δ”，該零元素為獨立零元素。若某行零元素多于一個，則暫不標(biāo)號。每行、每列只能有一個獨立零元素檢驗是否存在不同行列的0元素2110512030627053083401204列檢驗：若某列只有一個零元素，則給這零元素加“Δ”，該零元素為獨立零元素。若某列零元素多于一個，則暫不標(biāo)號。沒有得到位于不同行不同列的n個0元素方案的變換方案變換在所有沒有被分配的行打上“”號。2110512030627053083401204在已打“”號的行中找出打“”的列，并打“”。在已打“”號的列中找出打“Δ”的行，并打“”。重復(fù)以上過程，直到無法打“”時為止。方案變換2110512030627053083401204對所有打“”號的列和未打“”號的行劃線。這些線可以將所有的0元素至少覆蓋一次。如果是MM矩陣，而又要使最優(yōu)解分配在0元素位置上，劃線數(shù)量應(yīng)為M。本例還沒有達到最優(yōu)解。方案變換在未劃線的元素中找出最小元素2110512030627053083401204未劃線的各行元素減去這個最小元素已劃線的各列元素加上這個最小元素1000412040516043084401214對新的費用矩陣進行行檢驗與列檢驗1000412040516043084401214行檢驗：若某行只有一個零元素，則給這零元素加“Δ”，該零元素為獨立零元素。若某行零元素多于一個，則暫不標(biāo)號。1000412040516043084401