運(yùn)籌學(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)解，那么整個(gè)計(jì)算過程即告結(jié)束；否則，便轉(zhuǎn)入第二步。第一步放寬3ppt課件具體作法是：從相應(yīng)線性規(guī)劃的最優(yōu)解中，任意選擇一個(gè)不滿足原整數(shù)規(guī)劃整數(shù)條件的決策變量xj=bj。以使相應(yīng)線性規(guī)劃增加一個(gè)約束條件；xj小于bj的最大整數(shù)（或xj大于bj的最小整數(shù)），因而得到兩枝新的線性規(guī)劃，然后計(jì)算每枝的最優(yōu)解和最優(yōu)值。第二步

分枝4ppt課件

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

例9

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

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

利用隱枚舉法求解例9。試探的方法這是一個(gè)求y的最大值問題，當(dāng)然可以認(rèn)為ymax≥6這個(gè)新的約束條件具有濾掉非最優(yōu)解的功能，稱為過濾條件。解：（1）找出一個(gè)可行解并計(jì)算出相應(yīng)的目標(biāo)函數(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個(gè)決策變量。所以（x1，x2，x3，x4）共有24種不同的取值。見表2-12。其中：（x1，x2，x3，x4）是24種取值；（0）′和（1）′是將（x1，x2，x3，x4）取值代入后的計(jì)算結(jié)果。考查它們是否滿足（0）和（1）：當(dāng)不滿足某個(gè)約束條件時(shí)，同行以下的各項(xiàng)就不再考慮，這表明（x1，x2，x3，x4）不是可行解；當(dāng)滿足全部約束條件時(shí)，這表明（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×

小于上面的目標(biāo)值8，所以此解非最優(yōu)。最優(yōu)解?14ppt課件求出這些可行解對(duì)應(yīng)的目標(biāo)函數(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ī)劃時(shí)，若遇到y(tǒng)值大（?。┯冢?）的右邊，應(yīng)隨即讓（0）的右邊改取這個(gè)y值。求解0-1規(guī)劃，不要墨守成規(guī)，應(yīng)視具體情況選擇適當(dāng)?shù)慕夥?，以期收到事半功倍的效果?6ppt課件例3-3

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

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

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

例11

某醫(yī)院的四名化驗(yàn)員（甲、乙、丙、?。┩瓿伤捻?xiàng)化驗(yàn)工作（A、B、C、D）所消耗的時(shí)間見表2-13。哪個(gè)化驗(yàn)員擔(dān)當(dāng)哪項(xiàng)化驗(yàn)工作，可使他們總的消耗時(shí)間最短？二、

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

ABCD

消耗時(shí)間（分）

甲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的消耗時(shí)間；23ppt課件

y表示四名化驗(yàn)員總的消耗時(shí)間，于是數(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最少的行，并且把其中的一個(gè)0括起來，即（0）；然后劃掉與前提下，相繼完成其它各行。（0）同行或同列的0，即。在不得再括的()()()28ppt課件第三步：在矩陣[Cij]中，若不能得到m個(gè)（0），則進(jìn)行第四步；若能得到m個(gè)（0），則令[Cij]中與（0）相對(duì)應(yīng)的xij=1，其余的決策變量等于0。這時(shí)，[xij]便是最優(yōu)解。將最優(yōu)解代入目標(biāo)函數(shù)y的表達(dá)式，即得最優(yōu)值。()()()沒有得到4個(gè)(0)轉(zhuǎn)入第四步29ppt課件第四步：遵循下列程序，在[Cij]中畫出直線：（一）在沒有（0）的行，標(biāo)上“√”；（三）在標(biāo)上“√”的列中（0）所在的行，標(biāo)上“√”；（四）在沒有標(biāo)上“√”的行或已經(jīng)標(biāo)上“√”的列，都畫上一條直線；（二）在標(biāo)上“√”的行中所在的列，標(biāo)上“√”；（五）去掉“√”，而且將（0）和重新寫成0。√

√

√

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

最大化指派問題

例12

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

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

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

aij

表示i

擔(dān)任j

科長(zhǎng)的工作能力；y表示三名科長(zhǎng)總的工作能力。于是所求數(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)解代入最大化指派問題的目標(biāo)函數(shù)的表達(dá)式，求出最優(yōu)解。定理2.2

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

第二步：因?yàn)?811