【正文】 。 2）給只有 1個(gè) 0元素的列的 0元素加圈，記作◎，然后劃去◎所在行的其它 0元素，記作 Φ。 2）再?gòu)乃玫南禂?shù)矩陣的每列元素減去該列的最小元素?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書翻譯成不同語種的說明書所需時(shí)間如下表所示。 例 8： max z =3x12x2+5x3 x1+2x2x3≤2 x1+4x2+x3≤4 x1+x2≤3 4x1+x3≤6 x1， x2 ， x3=0或 1 第 3節(jié) 01型整數(shù)規(guī)劃 例 8： 解： max z =2x2+3x1+5x3 2x2+x1x3≤2 4x2+x1+x3≤4 x2+x1≤3 4x1+x3≤6 x1， x2 ， x3=0或 1 第 3節(jié) 01型整數(shù)規(guī)劃 例 9： min z =2x1+5x2+3x3+4x4 4x1+x2+x3+x4≥0 2x1+4x2+2x3+4x4≥4 x1+x2x3+x4≥1 x1， x2， x3， x4=0或 1 第 3節(jié) 01型整數(shù)規(guī)劃 例 9： 解： min z = 5x2+4x4+3x3+2x1 x2+x4 +x3 4x1≥0 4x2+4x4+2x32x1≥4 x2+x4x3+x1≥1 x1， x2， x3， x4=0或 1 第 3節(jié) 01型整數(shù)規(guī)劃 ?小結(jié) 采用部分枚舉法求解 01型整數(shù)規(guī)劃，可以減少計(jì)算次數(shù)，使最優(yōu)解能較快地被發(fā)現(xiàn) 第 4節(jié) 指派問題 一、指派問題的標(biāo)準(zhǔn)形式 ? 含義：將 n項(xiàng)工作交給 n個(gè)人去做，由于每個(gè)人做每一項(xiàng)工作所用的時(shí)間等成本不同，指派問題的目標(biāo)是如何安排工作，使總的時(shí)間等成本最小。 第二，在表中列出變量取值的全部組合（ 2n個(gè)），并分別計(jì)算各自的目標(biāo)函數(shù)值。各工廠年生產(chǎn)能力、各地年需求量、各廠至各需求地的單位物資運(yùn)費(fèi) cij（ i， j=1， 2， 3， 4）見下表。應(yīng)當(dāng)怎樣選擇投資項(xiàng)目，才能使總預(yù)期收益最大？ 第 3節(jié) 01型整數(shù)規(guī)劃 例 6： 解： 11 2 70j jxj j?????， 對(duì) 項(xiàng) 目 投 資設(shè) （ ， ， ， ）， 對(duì) 項(xiàng) 目 不 投 資1121345 6 7m a x120 1 1 2 7njjjnjjjjz c xa x Bxxxxx x xxj???????? ??????? ? ??? ?????或 （ = ， ， ， ）第 3節(jié) 01型整數(shù)規(guī)劃 例 7：工廠 A1和 A2生產(chǎn)某種物資。令 0 1 2 30 1 2 30 1 2 32 2 2 2 901x x x x xx x x x? ? ? ? ??其 中 ， ， ， 均 為 變 量第 3節(jié) 01型整數(shù)規(guī)劃 例 6：現(xiàn)有資金總額為 B。: 5 , ( 0 , 5 ) , 2 0 ,x ( 0 , 5 ) , 2 0zLxLxLzLxz???????????????????????無 可 行 解 第 一 次 剪 支第 三 次 剪 支。 作業(yè) 13答案 0: ( 2 .2 5 , 3 .7 5 ) , 2 0 .6 2 5L*12022, 0 2 0 .6 2 5 。 第 2節(jié) 分支定界法 例 4：用分支定界法求解 例 3。 以每個(gè)子問題的松弛問題為一分支標(biāo)明求解的結(jié)果，與其他問題的解的結(jié)果相比較： （ 1）若解滿足子問題的整數(shù)條件，則找到了一個(gè)整數(shù)規(guī)劃問題的可行解，為新的下界值 （求極大時(shí)）或上界值（求極小時(shí)） ；（若計(jì)算中同時(shí)出現(xiàn)兩個(gè)及以上整數(shù)規(guī)劃問題可行解，則選取其中最大 （求極大時(shí)）或最小（求極下時(shí)）的一個(gè)保留 ） （ 2）若解不滿足子問題的整數(shù)條件，則為新的 上界值（求極大時(shí)）或下界值（求極下時(shí)）。 （ 1）松弛問題無可行解，則整數(shù)規(guī)劃問題無可行解，計(jì)算停止； （ 2）松弛問題有最優(yōu)解，并且符合整數(shù)規(guī)劃問題的整數(shù)條件，則松弛問題的最優(yōu)解就是整數(shù)規(guī)劃問題的最優(yōu)解，計(jì)算停止； （ 3）松弛問題有最優(yōu)解，但是不符合整數(shù)規(guī)劃問題的整數(shù)條件，則松弛問題的最優(yōu)值是整數(shù)規(guī)劃問題最優(yōu)值的上界值（求極大時(shí)）或下界值（求極小時(shí)），下界值（求極大時(shí)）可暫定為 ∞ 或上界值（求極小時(shí)）可暫定為 +∞ 。 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 例 3：用完全枚舉法求解下述整數(shù)規(guī)劃問題。 1 2 3 4 51121 2 31 2 3 423453454551 2 3 4 5m in108911138530z x x x x xxxxx x xx x x xx x x xx x xxxxx x x x x? ? ? ? ???????? ? ? ??? ? ? ???? ? ? ???? ? ??? ????????， ， ， ， ， 且 均 取 整 數(shù) 值第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 二、整數(shù)規(guī)劃的解的特點(diǎn) ?整數(shù)規(guī)劃問題的可行域是它的松弛問題可行域的子集 ?整數(shù)規(guī)劃問題的可行解是它的松弛問題的可行解 ?整數(shù)規(guī)劃問題最優(yōu)解的目標(biāo)函數(shù)值不優(yōu)于它的松弛問題最優(yōu)解的目標(biāo)函數(shù)值 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 三、整數(shù)規(guī)劃的解法 例 2：某寶石加工廠最近新到 6粒大小、質(zhì)量等級(jí)相似的鉆石毛料，管理層有兩種選擇，一是切磨成一般的皇冠形，每?？色@利 ；一是切磨成雖然較難切磨但當(dāng)前市場(chǎng)較流行的心形，每?？色@利 4千元。 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) ?整數(shù)線性規(guī)劃的數(shù)學(xué)模型 1112m a x( m in)( ) 1 20 1 2njjjnij j ijjnz c xa x b i mx j nx x x????? ? ? ?????????????或或 ， 或 ， ， ， ， ， ， ， ， ， 中 部 分 或 全 部 取 整 數(shù)第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) ?整數(shù)線性規(guī)劃問題的類型 （ 1）純（全）整數(shù)線性規(guī)劃：全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃 （ 2）混合整數(shù)線性規(guī)劃：決策變量中有一部分必須取整數(shù)值，另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃 （ 3） 01型整數(shù)線性規(guī)劃：決策變量只能取值 0或 1的整數(shù)線性規(guī)劃 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 例 1：某服務(wù)部門各時(shí)段（每 2h為一時(shí)段）需要的服務(wù)員人數(shù)見下表。第五章 整數(shù)規(guī)劃 Integer Programming 第五章 整數(shù)規(guī)劃 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 第 2節(jié) 分支定界法 第 3節(jié) 01型整數(shù)規(guī)劃 第 4節(jié) 指派問題 第 1節(jié) 整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點(diǎn) 一、整數(shù)規(guī)劃的含義 要求一部分或全部決策變量必須取整數(shù)值的規(guī)劃問題。按規(guī)定，服務(wù)員連續(xù)工作 8h（即四個(gè)時(shí)段）為一班。若切磨成皇冠形則每粒需要 5個(gè)工作日，若切磨成心形則每粒需要 9個(gè)工作日，由于工廠切工師傅較忙，最多只有 45個(gè)工作日來做這批工作。 max z =x1+4x2 2x1+3x2≤3 x1+2x2≤8