運籌學講義-整數(shù)規(guī)劃.ppt

1、第四章 整數(shù)規(guī)劃,整數(shù)規(guī)劃的難度遠大于一般線性規(guī)劃,管理與人文學院 忻展紅 1999，4,2,4.1 整數(shù)規(guī)劃簡介,要求所有 xj 的解為整數(shù)，稱為純整數(shù)規(guī)劃 要求部分 xj 的解為整數(shù)，稱為混合整數(shù)規(guī)劃 對應沒有整數(shù)解要求的線性規(guī)劃稱之為松弛問題 整數(shù)規(guī)劃的解是可數(shù)個的，最優(yōu)解不一定發(fā)生在極點 整數(shù)規(guī)劃的最優(yōu)解不會優(yōu)于其松弛問題的最優(yōu)解,3,4.2 整數(shù)規(guī)劃的分枝定解法,4.2.1 思路與解題步驟 只解松弛問題 1、在全部可行性域上解松弛問題 若松弛問題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最優(yōu)解 2、分枝過程 若松弛問題最優(yōu)解中某個 xk=bk 不是整數(shù)，令 bk 為 bk 的整數(shù)部分 構(gòu)造兩

2、個新的約束條件 xk bk 和 xk bk +1，分別加于原松弛問題，形成兩個新的整數(shù)規(guī)劃 3、求解分枝的松弛問題 定界過程 設兩個分枝的松弛問題分別為問題 1 和問題 2 ，它們的最優(yōu)解有如下情況,4,表4.2.1 分枝問題解可能出現(xiàn)的情況,情況 2, 4, 5 找到最優(yōu)解 情況 3 在縮減的域上繼續(xù)分枝定界法 情況 6 問題 1 的整數(shù)解作為界被保留，用于以后與問題 2 的后續(xù)分枝所得到的整數(shù)解進行比較，結(jié)論如情況 4,5,4.2.2 分枝定界法舉例,例4.1.1,解：松弛問題的最優(yōu)解為 x1=2.5, x2=2, OBJ=23 由 x1=2.5 得到兩個分枝如下：,6,表4.2.3 分枝

3、問題的松弛解,問題II的解即原整數(shù)問題的最優(yōu)解,可能存在兩個分枝都是非整數(shù)解的情況，則需要兩邊同時繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進行定界過程 當有很多變量有整數(shù)約束時，分枝即廣又深，在最壞情況下相當于組合所有可能的整數(shù)解 一般整數(shù)規(guī)劃問題屬于一類未解決的難題，NP-complete，只有少數(shù)特殊問題有好的算法，如任務分配問題、匹配問題,7,4.6 任務分配問題,例4.6.1 有四個熟練工人，他們都是多面手，有四項任務要他們完成。若規(guī)定每人必須完成且只完成一項任務，而每人完成每項任務的工時耗費如表4.6.1，問如何分配任務使完成四項任務的總工時耗費最少？,8,任務分配問題的數(shù)學模型,模型中：

4、xij 為第 i 個工人分配去做第 j 項任務； aij 為第 i 個工人為完成第 j 項任務時的工時消耗； aijmm 稱為效率矩陣,運輸問題是任務分配問題的松弛問題 任務分配問題不但是整數(shù)規(guī)劃，而且是01規(guī)劃 任務分配問題有2m個約束條件，但有且只有m個非零解，是自然高度退化的 任務分配是兩部圖的匹配問題，有著名的匈牙利算法 下面介紹一種適合手算的算法(出自清華教科書),9,4.6.1 清華算法,定理 1 如果從效率矩陣aijmm中每行元素分別減去一個常數(shù) ui，從每列元素分別減去一個常數(shù) vj ，所得新的效率矩陣bijmm的任務分配問題的最優(yōu)解等價于原問題的最優(yōu)解。 證明：略 定理 2

5、若方陣中一部分元素為零，一部分元素非零，則覆蓋方陣內(nèi)所有零元素的最少直線數(shù)等于位于不同行、不同列的零元素的最多個數(shù)。 證明：略 清華算法的基本思路： 根據(jù)定理 1 變換效率矩陣，使矩陣中有足夠多的零。若矩陣中存在 m 個不同行不同列的零，就找到了最優(yōu)解 若覆蓋變換后的效率矩陣零元素的直線少于m 條，就尚未找到最優(yōu)解，設法進一步變換矩陣，增加新的零,10,清華算法的步驟：例4.6.1,第一步：變換效率矩陣，使每行每列至少有一個零 行變換：找出每行最小元素，從該行各元素中減去之 列變換：找出每列最小元素，從該列各元素中減去之,第二步：檢查覆蓋所有零元素的直線是否為m條 劃線規(guī)則 1、逐行檢查，若該

6、行只有一個未標記的零，對其加( )標記，將 ( )標記元素同行同列上其它的零打上*標記。若該行有二個以上未標記的零，暫不標記，轉(zhuǎn)下一行檢查，直到所有行檢查完；,11,清華算法的步驟：例4.6.1,2、逐列檢查，若該列只有一個未標記的零，對其加( )標記，將( )標記元素同行同列上其它的零打上*標記。若該列有二個以上未標記的零，暫不標記，轉(zhuǎn)下一列檢查，直到所有列檢查完；,3、重復1、2后，可能出現(xiàn)三種情況； a. 每行都有一個 (0)，顯然已找到最優(yōu)解，令對應(0)位置的 xij=1； b. 仍有零元素未標記，此時，一定存在某些行和列同時有多個零，稱為僵局狀態(tài)，因為無法采用 1. 2 中的方法繼

7、續(xù)標記。 4、打破僵局。令未標記零對應的同行同列上其它未標記零的個數(shù)為該零的指數(shù)，選指數(shù)最小的先標記 ( )；采用這種方法直至所有零都被標記，或出現(xiàn) 情況 a，或 情況 c 。,12,清華算法的步驟：例4.6.1,c. 所有零都已標記，但標有( )的零的個數(shù)少于m； 開始劃線過程： 對沒有標記 ( ) 的行打 對打 行上所有其它零元素對應的列打 再對打 列上有 ( ) 標記的零元素對應的行打 重復 ，直至無法繼續(xù) 對沒有打 的行劃橫線，對所有打 的列劃垂線,劃線后會出現(xiàn)兩種情況： (1) 標記( )的零少于m個，但劃有 m條直線，說明矩陣中已存在 m 個不同行不同列的零，但打破僵局時選擇不合理

8、，沒能找到?；氐?b 重新標記； (2) 少于m條直線，到第三步；,13,清華算法的步驟：例4.6.1,第三步：進一步變換； 在未劃線的元素中找最小者，設為 對未被直線覆蓋的各元素減去 對兩條直線交叉點覆蓋的元素加上 只有一條直線覆蓋的元素保持不變 以上步驟實際上仍是利用 定理 1,第四步：抹除所有標記，回到第二步，重新標記；,14,清華算法的步驟：例4.6.1,答：最優(yōu)分配方案為 x13= x21= x34 = x42 =1，其余為0， 即甲C，乙A，丙D，丁B，OBJ=20,15,4.6.2 關(guān)于清華算法的適用條件,要求所有aij 0 若某些 aij 0 ，則利用定理 1 進行變換，使所有

9、 bij 0 目標函數(shù)為min型 對于max型目標函數(shù)，將效率矩陣中所有 aij 反號，則等效于求min型問題；再利用定理 1 進行變換，使所有 bij 0，則可采用清華算法,打破僵局時選擇不當?shù)慕Y(jié)果：,結(jié)果僅出現(xiàn) 3 個標記 ( )，但卻劃出 4 條線， 說明什么？！,16,線性規(guī)劃有關(guān)的英文詞匯,Operational/operations research 運籌學 Linear programming 線性規(guī)劃 Feasible domain 可行域 Convex set 凸集 Basic feasible solutions 基礎(chǔ)可行解 Simplex algorithm 單純型法 Pivot 主元 Pivoting 主元變換 Revised, dual simplex algorithm 修正、對偶單純型法 Relative cost 相對成本(機會成本) Shadow price 影子價格 Slack, Surplus, Artificial variable 松弛，剩余，人工變量 Unbounded, Infeasible, Degenerate solution 無界解, 無可行解, 退化解 Duality 對偶性 Primal, dual problem 原問題，對偶問題 Complemen