《整數(shù)線性規(guī)劃》課件

運(yùn)籌帷幄之中決勝千里之外運(yùn)籌學(xué)課件整數(shù)線性規(guī)劃IntegerLinearProgramming1整數(shù)規(guī)劃整數(shù)規(guī)劃問題與模型整數(shù)規(guī)劃算法計(jì)算軟件應(yīng)用案例2整數(shù)規(guī)劃問題實(shí)例特點(diǎn)模型分類3應(yīng)用案例投資組合問題旅游售貨員問題背包問題4投資組合問題背景實(shí)例模型5背景證券投資：把一定的資金投入到合適的有價(jià)證券上以規(guī)避風(fēng)險(xiǎn)并獲得最大的利潤(rùn)。項(xiàng)目投資：財(cái)團(tuán)或銀行把資金投入到若干項(xiàng)目中以獲得中長(zhǎng)期的收益最大。6案例某財(cái)團(tuán)有萬元的資金，經(jīng)出其考察選中個(gè)投資項(xiàng)目，每個(gè)項(xiàng)目只能投資一個(gè)。其中第個(gè)項(xiàng)目需投資金額為萬元，預(yù)計(jì)5年后獲利（）萬元，問應(yīng)如何選擇項(xiàng)目使得5年后總收益最大？7模型變量—每個(gè)項(xiàng)目是否投資約束—總金額不超過限制目標(biāo)—總收益最大89旅游售貨員問題背景案例模型10背景旅游線路安排預(yù)定景點(diǎn)走且只走一次路上時(shí)間最短配送線路—貨郎擔(dān)問題送貨地到達(dá)一次總路程最短11案例有一旅行團(tuán)從出發(fā)要遍游城市，已知從到的旅費(fèi)為，問應(yīng)如何安排行程使總費(fèi)用最小？12模型變量—是否從i第個(gè)城市到第j個(gè)城市約束每個(gè)城市只能到達(dá)一次、離開一次13避免出現(xiàn)斷裂每個(gè)點(diǎn)給個(gè)位勢(shì)除了初始點(diǎn)外要求前點(diǎn)比后點(diǎn)大14目標(biāo)—總費(fèi)用最小1516背包問題背景案例模型17背景郵遞包裹把形狀可變的包裹用盡量少的車輛運(yùn)走旅行背包容量一定的背包里裝盡可能的多的物品18實(shí)例某人出國留學(xué)打點(diǎn)行李，現(xiàn)有三個(gè)旅行包，容積大小分別為1000毫升、1500毫升和2000毫升，根據(jù)需要列出需帶物品清單，其中一些物品是必帶物品共有7件，其體積大小分別為400、300、150、250、450、760、190、（單位毫升）。尚有10件可帶可不帶物品，如果不帶將在目的地購買，通過網(wǎng)絡(luò)查詢可以得知其在目的地的價(jià)格（單位美元）。這些物品的容量及價(jià)格分別見下表，試給出一個(gè)合理的安排方案把物品放在三個(gè)旅行包里。

19物品12345678910體積200350500430320120700420250100價(jià)格154510070507520090203020問題分析變量—對(duì)每個(gè)物品要確定是否帶同時(shí)要確定放在哪個(gè)包裹里，如果增加一個(gè)虛擬的包裹把不帶的物品放在里面，則問題就轉(zhuǎn)化為確定每個(gè)物品放在哪個(gè)包裹里。如果直接設(shè)變量為每個(gè)物品放在包裹的編號(hào)，則每個(gè)包裹所含物品的總?cè)萘烤秃茈y寫成變量的函數(shù)。為此我們?cè)O(shè)變量為第i個(gè)物品是否放在第j個(gè)包裹中21約束包裹容量限制必帶物品限制選帶物品限制22目標(biāo)函數(shù)—未帶物品購買費(fèi)用最小23模型24特征—變量整數(shù)性要求來源

問題本身的要求引入的邏輯變量的需要性質(zhì)—可行域是離散集合2526線性整數(shù)規(guī)劃模型一般整數(shù)規(guī)劃模型0-1整數(shù)規(guī)劃模型混合整數(shù)規(guī)劃模型27一般整數(shù)規(guī)劃模型280-1整數(shù)規(guī)劃模型29混合整數(shù)規(guī)劃模型30算法與線性規(guī)劃的關(guān)系分支定界算法割平面算法近似算法31與線性規(guī)劃的關(guān)系放松的線性規(guī)劃可行解是放松問題的可行解最優(yōu)值大于等于放松問題的最優(yōu)值整數(shù)規(guī)劃323334注釋最優(yōu)解不一定在頂點(diǎn)上達(dá)到最優(yōu)解不一定是放松問題最優(yōu)解的鄰近整數(shù)解整數(shù)可行解遠(yuǎn)多余于頂點(diǎn)，枚舉法不可取35分支定界算法算法思想算法步驟算例注釋36算法思想隱枚舉法求解放松問題最優(yōu)值比界壞最優(yōu)解為整數(shù)最優(yōu)值比界好最優(yōu)解為非整數(shù)最優(yōu)值比界好分支邊界分支舍棄37分支的方法383940定界當(dāng)前得到的最好整數(shù)解的目標(biāo)函數(shù)值分支后計(jì)算放松的線性規(guī)劃的最優(yōu)解整數(shù)解且目標(biāo)值小于原有最好解的值則替代原有最好解整數(shù)解且目標(biāo)值大于原有最好解的值則刪除該分支其中無最優(yōu)解非整數(shù)解且目標(biāo)值小于原有最好解的值則繼續(xù)分支非整數(shù)解且目標(biāo)值大于等于原有最好解的值則刪除該分支其中無最優(yōu)解41選一分支寫出并求解放松問題，同時(shí)從分支集中刪除該分支判定是否為整數(shù)解初始分支為可行解集，初始界為無窮大判定是否分支集空是停止當(dāng)前最好解為最優(yōu)解是否42判定最優(yōu)值是否小于當(dāng)前界判定最優(yōu)值是否小于當(dāng)前界是否按非整數(shù)變量分支并加入分支集否是以最優(yōu)解替代當(dāng)前最好解最優(yōu)值替代當(dāng)前界43算例44454647注釋求解混合整數(shù)規(guī)劃問題，只對(duì)整數(shù)變量分支，對(duì)非整數(shù)變量不分支。48對(duì)0-1整數(shù)規(guī)劃分支時(shí)49分枝問題解可能出現(xiàn)的情況情況2,4,5

找到最優(yōu)解情況3

在縮減的域上繼續(xù)分枝定界法情況6

問題1的整數(shù)解作為界被保留，用于以后與問題2的后續(xù)分枝所得到的解進(jìn)行比較，結(jié)論如情況4或550分枝定界法舉例

例4解：松弛問題的最優(yōu)解為x1=2.5,x2=2,OBJ=23

由x1=2.5得到兩個(gè)分枝如下：51表4.2.3分枝問題的松弛解問題II的解即原整數(shù)問題的最優(yōu)解可能存在兩個(gè)分枝都是非整數(shù)解的情況，則需要兩邊同時(shí)繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進(jìn)行定界過程當(dāng)存在很多變量有整數(shù)約束時(shí)，分枝即廣又深，在最壞情況下相當(dāng)于組合所有可能的整數(shù)解一般整數(shù)規(guī)劃問題屬于一類未解決的難題，NP-complete，只有少數(shù)特殊問題有好的算法，如任務(wù)分配問題、匹配問題52算法思想算法步驟算例割平面算法53算法思想由放松問題的可行域向整數(shù)規(guī)劃的可行域逼近方法—利用超平面切除要求整數(shù)解保留放松問題最優(yōu)值增加54割平面生成方法條件--保留整數(shù)解刪除最優(yōu)解55整數(shù)可行解最優(yōu)基可行解565758596061正則解62算法步驟求放松問題的最優(yōu)基可行解判斷是否為整數(shù)解是停止得到最優(yōu)解否在單純性表中加入一列利用對(duì)偶單純性算法求最優(yōu)解63算例(1,1.5)64656667686970計(jì)算軟件整數(shù)變量定義

LinDo

一般整數(shù)變量:GIN<Variable>0-1整數(shù)變量:INT<Variable>

LinGo

一般整數(shù)變量:@GIN(variable_name);0-1整數(shù)變量：@BIN(variable_name);算例71算例

max3x1+5x2+4x3subjectto2x1+3x2<=15002x2+4x3<=8003x1+2x2+5x3<=2000endginx1ginx3724.6任務(wù)分配問題例4.6.1有四個(gè)熟練工人，他們都是多面手，有四項(xiàng)任務(wù)要他們完成。若規(guī)定每人必須完成且只完成一項(xiàng)任務(wù)，而每人完成每項(xiàng)任務(wù)的工時(shí)耗費(fèi)如表4.6.1，問如何分配任務(wù)使完成四項(xiàng)任務(wù)的總工時(shí)耗費(fèi)最少？73任務(wù)分配問題的數(shù)學(xué)模型模型中：xij

為第i個(gè)工人分配去做第j

項(xiàng)任務(wù)；

aij

為第i

個(gè)工人為完成第j

項(xiàng)任務(wù)時(shí)的工時(shí)消耗；

{aij}m

m

稱為效率矩陣運(yùn)輸問題是任務(wù)分配問題的松弛問題任務(wù)分配問題不但是整數(shù)規(guī)劃，而且是0

1規(guī)劃任務(wù)分配問題有2m個(gè)約束條件，但有且只有m個(gè)非零解，是自然高度退化的任務(wù)分配是兩部圖的匹配問題，有著名的匈牙利算法下面介紹一種適合手算的算法(出自清華教科書)74

4.6.1清華算法定理1

如果從效率矩陣{aij}m

m中每行元素分別減去一個(gè)常數(shù)ui，從每列元素分別減去一個(gè)常數(shù)vj

，所得新的效率矩陣{bij}m

m的任務(wù)分配問題的最優(yōu)解等價(jià)于原問題的最優(yōu)解。證明：略定理2

若方陣中一部分元素為零，一部分元素非零，則覆蓋方陣內(nèi)所有零元素的最少直線數(shù)等于位于不同行、不同列的零元素的最多個(gè)數(shù)。證明：略清華算法的基本思路：根據(jù)定理1

變換效率矩陣，使矩陣中有足夠多的零。若矩陣中存在m

個(gè)不同行不同列的零，就找到了最優(yōu)解若覆蓋變換后的效率矩陣零元素的直線少于m條，就尚未找到最優(yōu)解，設(shè)法進(jìn)一步變換矩陣，增加新的零75清華算法的步驟：例4.6.1第一步：變換效率矩陣，使每行每列至少有一個(gè)零行變換：找出每行最小元素，從該行各元素中減去之列變換：找出每列最小元素，從該列各元素中減去之第二步：檢查覆蓋所有零元素的直線是否為m條劃線規(guī)則1、逐行檢查，若該行只有一個(gè)未標(biāo)記的零，對(duì)其加()標(biāo)記，將()標(biāo)記元素同行同列上其它的零打上*標(biāo)記。若該行有二個(gè)以上未標(biāo)記的零，暫不標(biāo)記，轉(zhuǎn)下一行檢查，直到所有行檢查完；76清華算法的步驟：例4.6.12、逐列檢查，若該列只有一個(gè)未標(biāo)記的零，對(duì)其加()標(biāo)記，將()標(biāo)記元素同行同列上其它的零打上*標(biāo)記。若該列有二個(gè)以上未標(biāo)記的零，暫不標(biāo)記，轉(zhuǎn)下一列檢查，直到所有列檢查完；3、重復(fù)1、2后，可能出現(xiàn)三種情況：a.

每行都有一個(gè)(0)，顯然已找到最優(yōu)解，令對(duì)應(yīng)(0)位置的xij=1；b.

仍有零元素未標(biāo)記，此時(shí)，一定存在某些行和列同時(shí)有多個(gè)零，稱為僵局狀態(tài)，因?yàn)闊o法采用1、2

中的方法繼續(xù)標(biāo)記。4、打破僵局。令未標(biāo)記零對(duì)應(yīng)的同行同列上其它未標(biāo)記零的個(gè)數(shù)為該零的指數(shù)，選指數(shù)最小的先標(biāo)記()；采用這種方法直至所有零都被標(biāo)記，或出現(xiàn)情況a，或情況c

。77清華算法的步驟：例4.6.1c.

所有零都已標(biāo)記，但標(biāo)有()的零的個(gè)數(shù)少于m；

開始劃線過程：

對(duì)沒有標(biāo)記()的行打

對(duì)打

行上所有其它零元素對(duì)應(yīng)的列打

再對(duì)打

列上有()標(biāo)記的零元素對(duì)應(yīng)的行打

重復(fù)

，直至無法繼續(xù)

對(duì)沒有打

的行劃?rùn)M線，對(duì)所有打

的列劃垂線

劃線后會(huì)出現(xiàn)兩種情況：(1)

標(biāo)記()的零少于m個(gè)，但劃有m條直線，說明矩陣中已存在m個(gè)不同行不同列的零，但打破僵局時(shí)選擇不合理，沒能找到?；氐絙

重新標(biāo)記；(2)

少于m條直線，到第三步；78清華算法的步驟：例4.6.1第三步：進(jìn)一步變換；

在未劃線的元素中找最小者，設(shè)為

對(duì)未被直線覆蓋的各元素減去

對(duì)兩條直線交叉點(diǎn)覆蓋的元素加上

只有一條直線覆蓋的元素保持不變以上步驟實(shí)際上仍是利用定理1第四步：抹除所有標(biāo)記，回到第二步，重新標(biāo)記；79清華算法的步驟：例4.6.1答：最優(yōu)分配方案為x13=x21=x34=x42=1，其余為0，即甲

C，乙

A，丙

D，丁

B，OBJ=2080

4.6.2關(guān)于清華算法的適用條件要求所有aij

0若某些aij

<0，則利用定理1進(jìn)行變換，使所有bij

0目標(biāo)函數(shù)為min型對(duì)于max型目標(biāo)函數(shù)，將效率矩陣中所有aij

反號(hào)，則等效于求min型問題；再利用定理1進(jìn)行變換，使所有bij

0，則可采用清華算法打破僵局時(shí)選擇不當(dāng)?shù)慕Y(jié)果：

結(jié)果僅出現(xiàn)3個(gè)標(biāo)記()，但卻劃出4條線，

說明什么？！81線性規(guī)劃有關(guān)的英文詞匯Operational/operationsresearch運(yùn)籌學(xué)Linearprogramming線性