運籌學(xué)-0-1規(guī)劃-指派問題

第五章整數(shù)規(guī)劃1．整數(shù)規(guī)劃的基本概念2．分枝定界法解整數(shù)規(guī)劃3．０－１規(guī)劃4.指派問題及其解法?1ppt課件1.整數(shù)規(guī)劃的基本概念2.分枝定界法解整數(shù)規(guī)劃純整數(shù)規(guī)劃、混整數(shù)規(guī)劃分枝定界法分三步：第一步放寬第二步分枝第三步定界2ppt課件

具體作法是：首先，刪去整數(shù)條件，把原整數(shù)規(guī)劃化成相應(yīng)線性規(guī)劃。其次，求解相應(yīng)線性規(guī)劃。最后，如果相應(yīng)線性規(guī)劃的最優(yōu)解也是原整數(shù)規(guī)劃的最優(yōu)解，那么整個計算過程即告結(jié)束；否則，便轉(zhuǎn)入第二步。第一步放寬3ppt課件具體作法是：從相應(yīng)線性規(guī)劃的最優(yōu)解中，任意選擇一個不滿足原整數(shù)規(guī)劃整數(shù)條件的決策變量xj=bj。以使相應(yīng)線性規(guī)劃增加一個約束條件；xj小于bj的最大整數(shù)（或xj大于bj的最小整數(shù)），因而得到兩枝新的線性規(guī)劃，然后計算每枝的最優(yōu)解和最優(yōu)值。第二步

分枝4ppt課件

具體做法為：進行定界（由各枝的最優(yōu)值中選最大值），找出界枝。若界枝的最優(yōu)解就是原整數(shù)規(guī)劃的最優(yōu)解，則計算過程便告結(jié)束；否則，回到第二步。第三步定界返回5ppt課件第四節(jié)0-1規(guī)劃一、0-1規(guī)劃的概念二、隱枚舉法6ppt課件

例9

在暑假期間，某同學(xué)準備徒步回家探親。他把要帶的物品裝進包后，覺得還能多放5個單位重量的東西。為此，他列出了擬放物品的清單，見表2-11。他認為：應(yīng)使所增加的物品總價值為最大?；谝陨系目紤]，他到底還要帶哪些東西呢？一、0-1規(guī)劃的概念7ppt課件y為增加的物品總價值編號名稱重量價值1書籍562誘餌233電筒114食物35表2-11解：設(shè)例9的數(shù)模為：8ppt課件只取0或1的變量,稱為0-1變量。若純整數(shù)規(guī)劃的決策變量都是0-1變量，則稱為0-1規(guī)劃。在討論線性規(guī)劃時，如果研究對象可以歸結(jié)為互相對立的兩種可能情況，那么依靠引入0-1變量，就能夠?qū)⑺M一步化成0-1規(guī)劃。9ppt課件如果0-1規(guī)劃模型不是標準型，總可以通過適當(dāng)?shù)淖儞Q，使其化為標準型.稱下面形式的數(shù)學(xué)模型為0-1規(guī)劃的標準型：返回10ppt課件二、隱枚舉法

從理論上講，求解0—1規(guī)劃，可用枚舉法。這時，一旦有n個決策變量x1，x2，…，xn，就必須逐一地檢查（x1，x2，…，xn）的2n種取值（不僅僅指可行解）。但是，當(dāng)n＞10時，即使經(jīng)歷漫長的計算過程找到了最優(yōu)解，也會由于時過境遷而失去實用價值。隱枚舉法是0-1規(guī)劃的常用解法，它只須檢查（x1，x2，…，xn）取值的一部分，即可找到最優(yōu)解。11ppt課件例10

利用隱枚舉法求解例9。試探的方法這是一個求y的最大值問題，當(dāng)然可以認為ymax≥6這個新的約束條件具有濾掉非最優(yōu)解的功能，稱為過濾條件。解：（1）找出一個可行解并計算出相應(yīng)的目標函數(shù)值：（x1，x2，x3，x4）=（1，0，0，0），y=6；（2）將不等式6x1+3x2+x3+5x4≥6加到約束條件中；（3）把6x1+3x2+x3+5x4≥6和5x1+2x2+x3+3x4≤5

依次記作（0）和（1），把它們的左邊分別寫成（0）′和（1）′。12ppt課件本0-1規(guī)劃包含4個決策變量。所以（x1，x2，x3，x4）共有24種不同的取值。見表2-12。其中：（x1，x2，x3，x4）是24種取值；（0）′和（1）′是將（x1，x2，x3，x4）取值代入后的計算結(jié)果?？疾樗鼈兪欠駶M足（0）和（1）：當(dāng)不滿足某個約束條件時，同行以下的各項就不再考慮，這表明（x1，x2，x3，x4）不是可行解；當(dāng)滿足全部約束條件時，這表明（x1，x2，x3，x4）是可行解。?13ppt課件（x1，x2，

x3，

x4）(0)’(1)’是(√)否(×)y（0,0,0,0）0×

(0,0,0,1)5×

(0,0,1,0)1×

(0,0,1,1)64√6(0,1,0,0)3×

(0,1,0,1)85√8(0,1,1,0)4×

(0,1,1,1)96×

(1,0,0,0)6(5)√6(1,0,0,1)118×

(1,0,1,0)76×

(1,0,1,1)129×

(1,1,0,0)97×

(1,1,0,1)1410×

(1,1,1,0)108×

(1,1,1,1)1511×

小于上面的目標值8，所以此解非最優(yōu)。最優(yōu)解?14ppt課件求出這些可行解對應(yīng)的目標函數(shù)的最大值：Max{6,8}=8。于是，本0-1規(guī)劃的最優(yōu)值ymax=8最優(yōu)解（x1，x2，x3，x4）=（0，1，0，1）。這表明，該同學(xué)還要帶誘餌和食物。15ppt課件從提高隱枚舉法的效率著想，當(dāng)求解最大（?。┗?-1規(guī)劃時，若遇到y(tǒng)值大（?。┯冢?）的右邊，應(yīng)隨即讓（0）的右邊改取這個y值。求解0-1規(guī)劃，不要墨守成規(guī)，應(yīng)視具體情況選擇適當(dāng)?shù)慕夥ǎ云谑盏绞掳牍Ρ兜男Ч?6ppt課件例3-3

求下面0-1規(guī)劃的解.它滿足約束條件（1）到（4），且對應(yīng)的目標函數(shù)值y=3．于是過濾條件為：解

首先用試探的方法找一個可行解:17ppt課件表3-13隱枚舉法計算表(0)（1）（2）（3）（4）滿足√否則×y(0,0,0)0

×

(0,0,1)5-1101√5(0,1,0)-2

×

(0,1,1)3

×

(1,0,0)3

×

(1,0,1)80211√8(1,1,0)1

×

(1,1,1)6

×

18ppt課件用全部枚舉法，3個變量共有23=8個解，原來4個約束條件共需32次運算，現(xiàn)在用隱枚舉法，將5個約束條件按（0）~（4）順序排好（見表3-13），對每個解依次代入約束條件左側(cè)，求出數(shù)值，看是否適合不等式條件，如某一條件不適合，同行以下各條件可不必再檢查，因而就減少了運算次數(shù).本例實際只作18次運算．最優(yōu)解:返回19ppt課件第五節(jié)

指派問題一、指派問題的概念二、最小化指派問題三、最大化指派問題20ppt課件指派問題就是人員和設(shè)備的任務(wù)安排問題。但是，運籌學(xué)當(dāng)前所涉及的指派問題，并不是泛指一切指派問題，而是把它局限于某種特殊情況。這種特殊情況的一個典型事例是：有n個人分別完成n項任務(wù)中的其中一項。因工作性質(zhì)和個人專長的差異，每個人完成各項工作的時間也就有所不同。于是便提出這樣的問題：指派哪個人完成哪項工作，可使他們總的工作時間最短？指派問題有最小化和最大化之分，二者的解法大同小異。一、指派問題的概念返回21ppt課件

例11

某醫(yī)院的四名化驗員（甲、乙、丙、丁）完成四項化驗工作（A、B、C、D）所消耗的時間見表2-13。哪個化驗員擔(dān)當(dāng)哪項化驗工作，可使他們總的消耗時間最短？二、

最小化指派問題22ppt課件表1-13

ABCD

消耗時間（分）

甲37.743.433.329.2

乙32.933.128.526.4

丙33.842.238.929.6

丁37.034.730.428.5建立其數(shù)學(xué)模型。設(shè)：

i=1,2,3,4分別表示甲，乙，丙，??；

j=1,2,3,4分別表示A，B，C，D；

bij

表示i完成j的消耗時間；23ppt課件

y表示四名化驗員總的消耗時間，于是數(shù)學(xué)模型為：例11稱為最小化指派問題。24ppt課件一般地，最小化指派問題的數(shù)學(xué)模型是：其中[bij]稱為效率矩陣。25ppt課件定理2.1

若效率矩陣[bij]第i行元素的最小值為bi

,則效率矩陣分別為[bij]和[bij-bi]的最小化指派問題具有相同的最優(yōu)解。把“第i行”換成“第j列”，“bi”換成“bj”后，依然成立。最小化指派問題的求解步驟如下：第一步：在效率矩陣[bij]中，讓每行（列）元素減去該行（列）元素的最小值，從而得到矩陣[Cij]。26ppt課件每行減去該行的最小元素每列減去該列的最小元素每行每列都有零27ppt課件第二步：在矩陣[Cij]中，首先找出含0最少的行，并且把其中的一個0括起來，即（0）；然后劃掉與前提下，相繼完成其它各行。（0）同行或同列的0，即。在不得再括的()()()28ppt課件第三步：在矩陣[Cij]中，若不能得到m個（0），則進行第四步；若能得到m個（0），則令[Cij]中與（0）相對應(yīng)的xij=1，其余的決策變量等于0。這時，[xij]便是最優(yōu)解。將最優(yōu)解代入目標函數(shù)y的表達式，即得最優(yōu)值。()()()沒有得到4個(0)轉(zhuǎn)入第四步29ppt課件第四步：遵循下列程序，在[Cij]中畫出直線：（一）在沒有（0）的行，標上“√”；（三）在標上“√”的列中（0）所在的行，標上“√”；（四）在沒有標上“√”的行或已經(jīng)標上“√”的列，都畫上一條直線；（二）在標上“√”的行中所在的列，標上“√”；（五）去掉“√”，而且將（0）和重新寫成0?！?/p>

√

√

()()()30ppt課件第五步：從[Cij]未畫上直線的元素中找出最小值。讓畫上直線的列中元素都加上該最小值，未畫上直線的行中元素都減去該最小值，隨即去掉各行各列上的直線，并轉(zhuǎn)入第二步。31ppt課件最小元素0.2新產(chǎn)生的0元素32ppt課件()()()()已得到4個（0），則令[Cij]中與（0）相對應(yīng)的xij=1，其余的決策變量等于0。這時，[xij]便是最優(yōu)解。將最優(yōu)解代入目標函數(shù)y的表達式，即得最優(yōu)值ymin=126.2(分)。轉(zhuǎn)入第二步,重新括0元素:返回這表明，讓化驗員甲、乙、丙、丁分別擔(dān)當(dāng)化驗工作D、C、A、B，可使他們總的消耗時間最短，只消126.2分，就能完成四項化驗工作。33ppt課件三、

最大化指派問題

例12

某衛(wèi)生防疫站準備選拔防疫科、食品科、總務(wù)科的三名科長。幾經(jīng)篩選，僅剩下趙、錢、孫三名候選人。根據(jù)民主評議的統(tǒng)計結(jié)果,他們主持各個科的工作能力（以得分多少來衡量）如表2-14所示。試從工作能力出發(fā)，確定最優(yōu)選擇科長方案。防疫食品總務(wù)工作能力（分）趙353027錢373529孫382832表2－1434ppt課件

建立數(shù)學(xué)模型設(shè)：

i=1,2,3分別表示趙，錢，孫；j=1,2,3分別表示防疫科，食品科，總務(wù)科；

aij

表示i

擔(dān)任j

科長的工作能力；y表示三名科長總的工作能力。于是所求數(shù)學(xué)模型是：35ppt課件例12稱為最大化指派問題。

36ppt課件

一般地，最大化指派問題的數(shù)學(xué)模型是：其中[aij]稱為效率矩陣。37ppt課件最大化指派問題的求解步驟如下：第一步：將最大化指派問題的效率矩陣[aij]化成[a－aij]，a=max{aij

∣i,j=1,2,…,m}第二步：求出效率矩陣為[a－aij]的最小化指派問題的最優(yōu)解，以其作為最大化指派問題的最優(yōu)解。第三步：把最優(yōu)解代入最大化指派問題的目標函數(shù)的表達式，求出最優(yōu)解。定理2.2

若效率矩陣[aij]各元素的最大值是a,則效率矩陣為[aij]的最大化指派問題與效率矩陣為[a－aij]的最小化指派問題具有相同的最優(yōu)解。38ppt課件確定例12的最優(yōu)選拔科長方案a=max{aij｜i,j=1,2,3}=38得：第一步：由39ppt課件

第二步：因為3811