運(yùn)籌學(xué)《第五章 整數(shù)規(guī)劃》

第五章整數(shù)規(guī)劃整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)割平面法分支定界法0-1型整數(shù)規(guī)劃指派問題1運(yùn)籌學(xué)-整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)1.1整數(shù)規(guī)劃數(shù)學(xué)模型的一般形式要求一部分或全部決策變量必須取整數(shù)值的規(guī)劃問題稱為整數(shù)規(guī)劃.不考慮整數(shù)條件,由余下的目標(biāo)函數(shù)和約束條件構(gòu)成的規(guī)劃問題稱為該整數(shù)問題的松弛問題。特別的:由目標(biāo)函數(shù)(1)和約束條件(2),(3),(4)構(gòu)成的模型稱為整數(shù)線性規(guī)劃;由目標(biāo)函數(shù)(1)和約束條件(2),(3)構(gòu)成的模型稱為該整數(shù)線性規(guī)劃問題的松弛問題.松弛問題2運(yùn)籌學(xué)-整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)1.2整數(shù)線性規(guī)劃問題的類型純整數(shù)線性規(guī)劃:指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃.混合整數(shù)線性規(guī)劃:指決策變量中有一部分必須取整數(shù)值,另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃.0-1型整數(shù)線性規(guī)劃:指決策變量只能取值0或1整數(shù)線性規(guī)劃.3運(yùn)籌學(xué)-整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)1.2整數(shù)線性規(guī)劃問題的類型純整數(shù)線性規(guī)劃:指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃.混合整數(shù)線性規(guī)劃:指決策變量中有一部分必須取整數(shù)值,另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃.0-1型整數(shù)線性規(guī)劃:指決策變量只能取值0或1整數(shù)線性規(guī)劃.4運(yùn)籌學(xué)-整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)1.2整數(shù)線性規(guī)劃問題的類型純整數(shù)線性規(guī)劃:指全部決策變量都必須取整數(shù)值的整數(shù)線性規(guī)劃.混合整數(shù)線性規(guī)劃:指決策變量中有一部分必須取整數(shù)值,另一部分可以不取整數(shù)值的整數(shù)線性規(guī)劃.0-1型整數(shù)線性規(guī)劃:指決策變量只能取值0或1整數(shù)線性規(guī)劃.5運(yùn)籌學(xué)-整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)1.3整數(shù)規(guī)劃的例子例1某廠生產(chǎn)A、B兩種產(chǎn)品，這兩種產(chǎn)品的單位利潤分別為25元和40元。生產(chǎn)每種產(chǎn)品都需要三道工序，其各種產(chǎn)品的工時(h)，每一工序每周可供使用的時間如下表，問工廠如何安排生產(chǎn)，使其獲利最大？解：假設(shè)工廠每周應(yīng)生產(chǎn)A種產(chǎn)品x1件，B種產(chǎn)品x2件，得到下面的數(shù)學(xué)模型純整數(shù)規(guī)劃問題6運(yùn)籌學(xué)-整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)1.3整數(shù)規(guī)劃的例子例2某服務(wù)部門各時段(2小時一個時段)需要的服務(wù)人員見下表，按規(guī)定服務(wù)員連續(xù)工作8小時為一班,問在滿足工作需要的條件下，如何安排使總服務(wù)員最少？解：假設(shè)xj表示j時段開始工作的服務(wù)員數(shù),則有如下模型時段12345678最少人數(shù)10891113853純整數(shù)規(guī)劃問題7運(yùn)籌學(xué)-整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)1.3整數(shù)規(guī)劃的例子例3現(xiàn)有資金總額為B,可供選擇的投資項目有n個,項目j所需投資額和預(yù)期收益分別為aj和cj.此外,由于種種原因，有三個附加條件:1)若選擇項目1,就必須同時選擇項目2,反之不一定;2)項目3和4至少選擇1個;3)項目5,6,7中恰好選擇兩個.應(yīng)當(dāng)怎樣選擇投資項目,才能使總預(yù)期收益最大？解:假設(shè)xj={1表示投資j項目;0表示不投資j項目}8運(yùn)籌學(xué)-整數(shù)規(guī)劃X1=1,x2=1X1=0,x2=1X1=0,x2=0第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)1.3整數(shù)規(guī)劃的例子例3現(xiàn)有資金總額為B,可供選擇的投資項目有n個,項目j所需投資額和預(yù)期收益分別為aj和cj.此外,由于種種原因，有三個附加條件:1若選擇項目1,就必須同時選擇項目2,反之不一定;2項目3和4至少選擇1個;3項目5,6,7中恰好選擇兩個.應(yīng)當(dāng)怎樣選擇投資項目,才能使總預(yù)期收益最大？解:假設(shè)xj={1表示投資j項目;0表示不投資j項目}9運(yùn)籌學(xué)-整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)1.3整數(shù)規(guī)劃的例子例3現(xiàn)有資金總額為B,可供選擇的投資項目有n個,項目j所需投資額和預(yù)期收益分別為aj和cj.此外,由于種種原因，有三個附加條件:1若選擇項目1,就必須同時選擇項目2,反之不一定;2項目3和4至少選擇1個;3項目5,6,7中恰好選擇兩個.應(yīng)當(dāng)怎樣選擇投資項目,才能使總預(yù)期收益最大？解:假設(shè)xj={1表示投資j項目;0表示不投資j項目}X3=1,x4=1X3=1,x4=0X3=0,x4=110運(yùn)籌學(xué)-整數(shù)規(guī)劃X5=0,x6=1,x7=1X5=1,x6=1,x7=0X5=1,x6=0,x7=1第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)1.3整數(shù)規(guī)劃的例子例3現(xiàn)有資金總額為B,可供選擇的投資項目有n個,項目j所需投資額和預(yù)期收益分別為aj和cj.此外,由于種種原因，有三個附加條件:1若選擇項目1,就必須同時選擇項目2,反之不一定;2項目3和4至少選擇1個;3項目5,6,7中恰好選擇兩個.應(yīng)當(dāng)怎樣選擇投資項目,才能使總預(yù)期收益最大？解:假設(shè)xj={1表示投資j項目;0表示不投資j項目}0-1整數(shù)規(guī)劃問題11運(yùn)籌學(xué)-整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)1.3整數(shù)規(guī)劃的例子例4工廠A1和A2生產(chǎn)某種物資.由于該物資供不應(yīng)求,需要再建一家工廠,相應(yīng)的建廠方案有A3和A4.該物資需求地有B1,B2,B3,B4.各廠年生產(chǎn)能力,各地需求量及各廠到各地的單位運(yùn)費(fèi)如下表,另外,工廠A3或A4開工后,每年的生產(chǎn)費(fèi)用估計為1200萬或1500萬,問建工廠A3還是A4所需的年總費(fèi)用最少？B1B2B3B4產(chǎn)能A12934400A28357600A37612200A44525200需求量350400300150或12運(yùn)籌學(xué)-整數(shù)規(guī)劃B1B2B3B4產(chǎn)能A12x119x123

x134

x14400A28x213x225

x237

x24600A37

x316

x321x332x34200A44

x415

x422x435x44200需求量350400300150解:設(shè)xij表示從Ai運(yùn)到Bj的物資量若用A3方案,則模型為或13運(yùn)籌學(xué)-整數(shù)規(guī)劃B1B2B3B4產(chǎn)能A12x119x123

x134

x14400A28x213x225

x237

x24600A37

x316

x321x332x34200A44

x415

x422x435x44200需求量350400300150解:設(shè)xij表示從Ai運(yùn)到Bj的物資量若用A3方案,則模型為若用A4方案,則模型為或14運(yùn)籌學(xué)-整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)解:將兩模型合并為一個模型,設(shè)y={1表示建A3;0表示建A4}當(dāng)y=1時0+0+0+0=200*0000011000015運(yùn)籌學(xué)-整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)解:將兩模型合并為一個模型,設(shè)y={1表示建A3;0表示建A4}混和整數(shù)規(guī)劃問題當(dāng)y=0時0+0+0+0=200*0000011000016運(yùn)籌學(xué)-整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及其解的特點(diǎn)1.4整數(shù)規(guī)劃解的特點(diǎn)能否對松弛問題最優(yōu)解取整得到其對應(yīng)的整數(shù)規(guī)劃問題的最優(yōu)解？例5考慮下面的整數(shù)規(guī)劃：用圖解法得松弛問題最優(yōu)解為P(18/7,19/7)，取整有A1，A2，A3，A4四種結(jié)果。顯然A1，A2非可行解，而A3，A4經(jīng)計算不是最優(yōu)解，事實(shí)上最優(yōu)解是A*（4，2）。A*17運(yùn)籌學(xué)-整數(shù)規(guī)劃第一節(jié)目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型能否用枚舉法求整數(shù)規(guī)劃最優(yōu)解？0123456784567891010111218運(yùn)籌學(xué)-整數(shù)規(guī)劃第一節(jié)目標(biāo)規(guī)劃問題及其數(shù)學(xué)模型比如對于有n項任務(wù)的指派問題，不同得指派方案為n!種。n=10,有3628800種方案。n=20,有2×1018種方案。用每秒百萬次的計算機(jī)，需要上萬年時間計算出結(jié)果。能否用枚舉法求整數(shù)規(guī)劃最優(yōu)解？目前采用的思路：將完全枚舉法變成部分枚舉法。分枝定界法------混合整數(shù)規(guī)劃割平面法------純整數(shù)規(guī)劃隱枚舉法------0-1規(guī)劃匈牙利法------0-1規(guī)劃19運(yùn)籌學(xué)-整數(shù)規(guī)劃第二節(jié)割平面法思路：針對整數(shù)規(guī)劃問題的松弛問題，增加線性約束條件（割平面）使得由原可行域中切割掉一部分，這部分只包含非整數(shù)解，但沒有切割掉任何整數(shù)可行解，該方法的核心在于如何找到合適的割平面（并非一次就能找到），使切割后最終得到這樣的可行域：它的一個有整數(shù)坐標(biāo)的頂點(diǎn)恰好就是問題的最優(yōu)解。20運(yùn)籌學(xué)-整數(shù)規(guī)劃第二節(jié)割平面法思路：針對整數(shù)規(guī)劃問題的松弛問題，增加線性約束條件（割平面）使得由原可行域中切割掉一部分，這部分只包含非整數(shù)解，但沒有切割掉任何整數(shù)可行解，該方法的核心在于如何找到合適的割平面（并非一次就能找到），使切割后最終得到這樣的可行域：它的一個有整數(shù)坐標(biāo)的頂點(diǎn)恰好就是問題的最優(yōu)解。割平面21運(yùn)籌學(xué)-整數(shù)規(guī)劃第二節(jié)割平面法割平面構(gòu)造方法：對于純整數(shù)規(guī)劃問題設(shè)aij,bi均為整數(shù),用單純形法求其松弛問題的最優(yōu)解,得到最終單純形表,記Q為基變量下標(biāo)的集合，K為非基變量下標(biāo)集合,最終單純形表中的約束可以表示為：22運(yùn)籌學(xué)-整數(shù)規(guī)劃cj21000θ0x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2cj-zj000-1/4-1/223運(yùn)籌學(xué)-整數(shù)規(guī)劃第二節(jié)割平面法割平面構(gòu)造方法：分解ai0j,bi為兩部分.一部分為不超過該數(shù)的最大整數(shù)，另一部分為余下的小數(shù)：若b不為整數(shù)，其方程如下:代入上式移項得:24運(yùn)籌學(xué)-整數(shù)規(guī)劃第二節(jié)割平面法割平面構(gòu)造方法：對于由于左邊是整數(shù),右邊必然也是整數(shù).而若必為小數(shù),故必然有即割平面方程1958R.E.Gomory25運(yùn)籌學(xué)-整數(shù)規(guī)劃26運(yùn)籌學(xué)-整數(shù)規(guī)劃第二節(jié)割平面法例6用割平面法求解純整數(shù)規(guī)劃解：引入松弛變量x3,x4,x5,用單純形法解其松弛問題，得最優(yōu)單純形表27運(yùn)籌學(xué)-整數(shù)規(guī)劃cj3-1000θCBXBbx1x2x3x4x53x113/7101/702/7-1X29/701-2/703/70X431/700-3/7122/7cj-zj00-5/70-3/7構(gòu)造割平面約束：引入松弛變量x6,得割平面方程：將該式代入上表為：28運(yùn)籌學(xué)-整數(shù)規(guī)劃cj3-1000θCBXBbx1x2x3x4x53x113/7101/702/7-1X29/701-2/703/70X431/700-3/7122/7cj-zj00-5/70-3/7構(gòu)造割平面約束：引入松弛變量x6,得割平面方程：將該式代入上表為：29運(yùn)籌學(xué)-整數(shù)規(guī)劃cj3-1000θCBXBbx1x2x3x4x53x113/7101/702/7-1X29/701-2/703/70X431/700-3/7122/7cj-zj00-5/70-3/7構(gòu)造割平面約束：引入松弛變量x6,得割平面方程：將該式代入上表為：30運(yùn)籌學(xué)-整數(shù)規(guī)劃cj3-10000θCBXBbx1x2x3x4x5x63x113/7101/702/70-1X29/701-2/703/700X431/700-3/7122/700x6-6/700-1/70-2/71cj-zj00-5/70-3/70用對偶單純形法求解得：31運(yùn)籌學(xué)-整數(shù)規(guī)劃cj3-10000θCBXBbx1x2x3x4x5x63x11100001-1X25/4010-1/40-5/40X35/2001-1/20-11/20x57/40001/41-3/4cj-zj000-1/40-17/4構(gòu)造割平面約束：引入松弛變量x7,得割平面方程：將該式代入上表為：32運(yùn)籌學(xué)-整數(shù)規(guī)劃cj3-10000θCBXBbx1x2x3x4x5x63x11100001-1X25/4010-1/40-5/40X35/2001-1/20-11/20x57/40001/41-3/4cj-zj000-1/40-17/4構(gòu)造割平面約束：引入松弛變量x7,得割平面方程：將該式代入上表為：33運(yùn)籌學(xué)-整數(shù)規(guī)劃cj3-100000θCBXBbx1x2x3x4x5x6x73x111000010-1X25/4010-1/40-5/400X35/2001-1/20-11/200x57/40001/41-3/400x7-3/4000-1/40-1/41cj-zj000-1/40-17/40用對偶單純形法求解得：34運(yùn)籌學(xué)-整數(shù)規(guī)劃cj3-100000θCBXBbx1x2x3x4x5x6x73x111000010-1X2201000-100X3400100-5-20X5100001-110X43000101-4cj-zj00000-4-1得最優(yōu)解x=(1,2,4,3,1,0,0)T,最優(yōu)值為3-2=135運(yùn)籌學(xué)-整數(shù)規(guī)劃36運(yùn)籌學(xué)-整數(shù)規(guī)劃37運(yùn)籌學(xué)-整數(shù)規(guī)劃x1=1,x2=238運(yùn)籌學(xué)-整數(shù)規(guī)劃第三節(jié)分支定界法思路：設(shè)有最大化的整數(shù)規(guī)劃問題I，與它相應(yīng)的線性規(guī)劃問題為S。從解問題S開始，若其最優(yōu)解不符合I的整數(shù)條件，那么S的最優(yōu)目標(biāo)函數(shù)是I的最優(yōu)目標(biāo)函數(shù)的上界，而I的任意可行解的目標(biāo)函數(shù)值是I最優(yōu)值得下界，通過將S的可行域分成子區(qū)域的方法，逐步增加下界值，減小上界值，從而求出最優(yōu)值。39運(yùn)籌學(xué)-整數(shù)規(guī)劃第三節(jié)分支定界法································松弛問題S0整數(shù)規(guī)劃問題I0若S0最優(yōu)解為整數(shù),則該解也是I0的最優(yōu)解.否則S0最優(yōu)解為I0的最優(yōu)解的上界.可以進(jìn)行分支.40運(yùn)籌學(xué)-整數(shù)規(guī)劃第三節(jié)分支定界法································S1I1S2I2若S1的最優(yōu)解不是整數(shù),對S1進(jìn)行分支,否則可以把該最優(yōu)解作為I0的一個下界.z0z141運(yùn)籌學(xué)-整數(shù)規(guī)劃第三節(jié)分支定界法································S1I1S2I2z0z1若S2的最優(yōu)解不是整數(shù),對S2進(jìn)行分支,否則可以把該最優(yōu)解作為I0的一個下界.42運(yùn)籌學(xué)-整數(shù)規(guī)劃例7求解第三節(jié)分支定界法(I)(S)43運(yùn)籌學(xué)-整數(shù)規(guī)劃第三節(jié)分支定界法Sx1=3/2x2=10/3z=29/6Ax1≦1x1≧2s44運(yùn)籌學(xué)-整數(shù)規(guī)劃第三節(jié)分支定界法Sx1=3/2x2=10/3z=29/6Ax1≦1x1≧2s1s245運(yùn)籌學(xué)-整數(shù)規(guī)劃第三節(jié)分支定界法Sx1=3/2x2=10/3z=29/6Ax1≦1x1≧2s1s2S146運(yùn)籌學(xué)-整數(shù)規(guī)劃第三節(jié)分支定界法Sx1=3/2x2=10/3z=29/6Ax1≦1x1≧2s1s2S1x1=1x2=7/3z=10/3C47運(yùn)籌學(xué)-整數(shù)規(guī)劃第三節(jié)分支定界法Sx1=3/2x2=10/3z=29/6Ax1≦1x1≧2s1s2S1x1=1x2=7/3z=10/3CS248運(yùn)籌學(xué)-整數(shù)規(guī)劃第三節(jié)分支定界法Sx1=3/2x2=10/3z=29/6Ax1≦1x1≧2s1s2S1x1=1x2=7/3z=10/3CS2x1=2x2=23/9z=41/9B49運(yùn)籌學(xué)-整數(shù)規(guī)劃Sx1=3/2x2=3/10z=29/6Ax1≦1x1≧2s1s21S1x1=1x2=7/3z=10/3CS2x1=2x2=23/9z=41/9Bx2≦2x2≧3S2150運(yùn)籌學(xué)-整數(shù)規(guī)劃Sx1=3/2x2=3/10z=29/6Ax1≦1x1≧2s1s21S1x1=1x2=7/3z=10/3CS2x1=2x2=23/9z=41/9Bx2≦2x2≧3S21x1=33/14x2=2z=61/1451運(yùn)籌學(xué)-整數(shù)規(guī)劃Sx1=3/2x2=3/10z=29/6Ax1≦1x1≧2s1s21S1x1=1x2=7/3z=10/3CS2x1=2x2=23/9z=41/9Bx2≦2x2≧3S21x1=33/14x2=2z=61/14S22無解52運(yùn)籌學(xué)-整數(shù)規(guī)劃Sx1=3/2x2=3/10z=29/6Ax1≦1x1≧2s1s21CS2x1=2x2=23/9z=41/9Bx2≦2S21x1=33/14x2=2z=61/14S1x1=1x2=7/3z=10/353運(yùn)籌學(xué)-整數(shù)規(guī)劃As1s211CBx2≦2S21x1=33/14x2=2z=61/14Sx1=3/2x2=3/10z=29/6x1≦1x1≧2S1x1=1x2=7/3z=10/3S2x1=2x2=23/9z=41/9x1≦2S21154運(yùn)籌學(xué)-整數(shù)規(guī)劃As1s211CBx2≦2S21x1=33/14x2=2z=61/14Sx1=3/2x2=3/10z=29/6x1≦1x1≧2S1x1=1x2=7/3z=10/3S2x1=2x2=23/9z=41/9x1≦2S211x1=2x2=2z=4D55運(yùn)籌學(xué)-整數(shù)規(guī)劃As1s211CBx2≦2S21x1=33/14x2=2z=61/14Sx1=3/2x2=3/10z=29/6x1≦1x1≧2S1x1=1x2=7/3z=10/3S2x1=2x2=23/9z=41/9x1≦2S211x1=2x2=2z=4Dx1≧3S21256運(yùn)籌學(xué)-整數(shù)規(guī)劃As1s211CBx2≦2S21x1=33/14x2=2z=61/14Sx1=3/2x2=3/10z=29/6x1≦1x1≧2S1x1=1x2=7/3z=10/3S2x1=2x2=23/9z=41/9x1≦2S211x1=2x2=2z=4Dx1≧3S212x1=3x2=1z=4s212E求最小化的例子s1的松弛問題最優(yōu)解小于整數(shù)問題解得下限457運(yùn)籌學(xué)-整數(shù)規(guī)劃解：首先不考慮整數(shù)約束，相應(yīng)的問題稱為原問題的松馳問題松馳問題（0）用單純形法求得其最優(yōu)解為x1=2.5，x2=2.5，z=87.5其求解框圖如下：例58運(yùn)籌學(xué)-整數(shù)規(guī)劃問題（0）x1=2.5，x2=2.5z=87.5問題（1）x1=2，x2=2.67z=83.3問題（2）x1=3，x2=1.75z=80問題（3）x1=2，x2=2z=70問題（4）x1=1，x2=3z=75問題（5）x1=3.5，x2=1z=72.5問題（6）無可行解59運(yùn)籌學(xué)-整數(shù)規(guī)劃分支定界法的步驟將要求解的整數(shù)規(guī)劃問題稱為A問題，將與它相應(yīng)的線性規(guī)劃問題稱為B問題60運(yùn)籌學(xué)-整數(shù)規(guī)劃分支定界法的步驟將要求解的整數(shù)規(guī)劃問題稱為A問題，將與它相應(yīng)的線性規(guī)劃問題稱為B問題61運(yùn)籌學(xué)-整數(shù)規(guī)劃例8廠址選擇問題

。在5個地點(diǎn)中選3處建生產(chǎn)同一產(chǎn)品的工廠，在這5個地點(diǎn)建廠所需投資，占用農(nóng)田，建成以后的生產(chǎn)能力等數(shù)據(jù)如下表所示，現(xiàn)在有總投資800萬元，占用農(nóng)田指標(biāo)60畝，應(yīng)如何選擇廠址，使建成后總生產(chǎn)能力最大。第四節(jié)0-1型整數(shù)規(guī)劃一、0-1變量及其應(yīng)用地點(diǎn)12345所需投資（萬元）320280240210180占用農(nóng)田（畝）201815118生產(chǎn)能力（萬噸）7055422811解：設(shè)五個0—1變量x1，x2，x3，x4，x5，其中i=1,2,3,4,562運(yùn)籌學(xué)-整數(shù)規(guī)劃第四節(jié)0-1型整數(shù)規(guī)劃地點(diǎn)12345所需投資（萬元）320280240210180占用農(nóng)田（畝）201815118生產(chǎn)能力（萬噸）70554228118006063運(yùn)籌學(xué)-整數(shù)規(guī)劃例9含有相互排斥的約束條件的問題

。某廠生產(chǎn)A1，A2兩種產(chǎn)品，需要經(jīng)過B1，B2，B3三道工序加工。單件工時和利潤以及各個工序每周工時限額見下表，問工廠應(yīng)如何安排生產(chǎn)，才能使總利潤最大？第四節(jié)0-1型整數(shù)規(guī)劃一、0-1變量及其應(yīng)用B1B2B31B32利潤A10.30.20.30.225A20.70.10.50.440工時限額(h/周)250100150120

解：設(shè)該工廠分別生產(chǎn)A1,A2產(chǎn)品x1,x2件，當(dāng)分別采用工序B31,B32時，所得線性規(guī)劃模型為：64運(yùn)籌學(xué)-整數(shù)規(guī)劃B1B2B31B32利潤A10.30.20.30.225A20.70.10.50.440工時限額(h/周)250100150120

x1x2B31B3265運(yùn)籌學(xué)-整數(shù)規(guī)劃B31B3266運(yùn)籌學(xué)-整數(shù)規(guī)劃若y1=067運(yùn)籌學(xué)-整數(shù)規(guī)劃若y1=068運(yùn)籌學(xué)-整數(shù)規(guī)劃若y2=069運(yùn)籌學(xué)-整數(shù)規(guī)劃若y2=070運(yùn)籌學(xué)-整數(shù)規(guī)劃例10固定費(fèi)用問題有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單價可變費(fèi)用售價、資源單耗量及組織三種產(chǎn)品生產(chǎn)的固定費(fèi)用見下表,要求制定一個生產(chǎn)計劃使總收益最大.第四節(jié)0-1型整數(shù)規(guī)劃一、0-1變量及其應(yīng)用IIIIII資源量A248500B234300C123100單件可變費(fèi)用456固定費(fèi)用100150200單件售價8101271運(yùn)籌學(xué)-整數(shù)規(guī)劃IIIIII資源量A248500B234300C123100單件可變費(fèi)用456固定費(fèi)用100150200單件售價81012若設(shè)生產(chǎn)產(chǎn)品I,II,III分別x1,x2,x3件72運(yùn)籌學(xué)-整數(shù)規(guī)劃IIIIII資源量A248500B234300C123100單件可變費(fèi)用456固定費(fèi)用100150200單件售價81012若x1>0,x2>0,x3>0設(shè)生產(chǎn)產(chǎn)品I,II,III分別x1,x2,x3件若x1=0,x2>0,x3>073運(yùn)籌學(xué)-整數(shù)規(guī)劃IIIIII資源量A248500B234300C123100單件可變費(fèi)用456固定費(fèi)用100150200單件售價81012若x1>0,x2=0,x3>0設(shè)生產(chǎn)產(chǎn)品I,II,III分別x1,x2,x3件若x1>0,x2>0,x3=074運(yùn)籌學(xué)-整數(shù)規(guī)劃設(shè)生產(chǎn)產(chǎn)品I,II,III分別x1,x2,x3件75運(yùn)籌學(xué)-整數(shù)規(guī)劃例11變量之間需要滿足一定的邏輯關(guān)系的問題

一個工廠用三種設(shè)備生產(chǎn)5種產(chǎn)品，三種設(shè)備的總能力（小時），生產(chǎn)每種產(chǎn)品需要占用的各種設(shè)備的能力（小時/件）以及三種產(chǎn)品的利潤（元/件）如下表所示第四節(jié)0-1型整數(shù)規(guī)劃一、0-1變量及其應(yīng)用產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4產(chǎn)品5設(shè)備能力（小時）設(shè)備A513241,800設(shè)備B－34152,500設(shè)備C321322,200利潤（元/件）2418211722求使利潤最大的生產(chǎn)方案(產(chǎn)品為整數(shù))76運(yùn)籌學(xué)-整數(shù)規(guī)劃產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4產(chǎn)品5設(shè)備能力（小時）設(shè)備A513241,800設(shè)備B－34152,500設(shè)備C321322,200利潤（元/件）2418211722解:設(shè)生產(chǎn)產(chǎn)品1-5分別為xi(i=1-5)件.77運(yùn)籌學(xué)-整數(shù)規(guī)劃產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4產(chǎn)品5設(shè)備能力（小時）設(shè)備A513241,800設(shè)備B－34152,500設(shè)備C321322,200利潤（元/件）2418211722五種產(chǎn)品中，安排生產(chǎn)的產(chǎn)品不能超過三種78運(yùn)籌學(xué)-整數(shù)規(guī)劃產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4產(chǎn)品5設(shè)備能力（小時）設(shè)備A513241,800設(shè)備B－34152,500設(shè)備C321322,200利潤（元/件）2418211722每一種產(chǎn)品如果生產(chǎn)，最小批量為50件

79運(yùn)籌學(xué)-整數(shù)規(guī)劃產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4產(chǎn)品5設(shè)備能力（小時）設(shè)備A513241,800設(shè)備B－34152,500設(shè)備C321322,200利潤（元/件）2418211722如果產(chǎn)品1安排生產(chǎn)，產(chǎn)品2就不能生產(chǎn)

80運(yùn)籌學(xué)-整數(shù)規(guī)劃產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4產(chǎn)品5設(shè)備能力（小時）設(shè)備A513241,800設(shè)備B－34152,500設(shè)備C321322,200利潤（元/件）2418211722如果產(chǎn)品4安排生產(chǎn)，產(chǎn)品5必須生產(chǎn)，而且至少生產(chǎn)50件81運(yùn)籌學(xué)-整數(shù)規(guī)劃練習(xí)：說明如何用0-1整數(shù)變量將下列條件表示為線性約束1）或者x1+x2≤2或者2x1+3x2≥8x1+x2-2≤My8-2x1-3x2≤M(1-y)y=0,1M為充分大的正數(shù)2）變量x3只能取0，5，9，12x3=5y1+9y2+12y3y1+y2+y3≤1yi=0,182運(yùn)籌學(xué)-整數(shù)規(guī)劃練習(xí)：說明如何用0-1整數(shù)變量將下列條件表示為線性約束3）若x4≤4,則x5≥6，否則x5≤3本題相當(dāng)于x4≤4,x5≥6

或x4>4,則x5≤3x4-4≤My6-x5≤My4-x4<M(1-y)x5-3≤M(1-y)4）下列四個約束至少必須滿足兩個x6+x7≤2,x6≤1,x7≤5,x6+x7≥3x6+x7-2≤My1x6-1≤My2x7-5≤My33-x6-x7≤My4y1+y2+y3+y4≤2yi=0表示滿足該約束83運(yùn)籌學(xué)-整數(shù)規(guī)劃例12求解0-1整數(shù)規(guī)劃

第四節(jié)0-1型整數(shù)規(guī)劃二、0-1整數(shù)規(guī)劃的解法隱枚舉法84運(yùn)籌學(xué)-整數(shù)規(guī)劃(x1,x2,x3)Z約束條件1234過濾條件0,0,00,0,10,1,00,1,11,0,01,0,11,1,01,1,1(1)(2)(3)(4)任意取一組可行解(x1,x2,x3)=(0,0,1),Z=5,將z≥5作為過濾條件z≥585運(yùn)籌學(xué)-整數(shù)規(guī)劃(x1,x2,x3)Z約束條件1234過濾條件0,0,000,0,10,1,00,1,11,0,01,0,11,1,01,1,1(1)(2)(3)(4)任意取一組可行解(x1,x2,x3)=(0,0,1),Z=5,將z≥5作為過濾條件z≥55√√√√-2338√√√√z≥816最優(yōu)解為(x1,x2,x3)=(1,0,1),最優(yōu)值z=886運(yùn)籌學(xué)-整數(shù)規(guī)劃例

求解0-1整數(shù)規(guī)劃

87運(yùn)籌學(xué)-整數(shù)規(guī)劃(x2,x1,x4,x3)Z約束條件123過濾條件0,0,0,000,0,0,1-10,0,1,010,0,1,100,1,0,030,1,0,120,1,1,040,1,1,131,0,0,071,0,0,161,0,1,081,0,1,171,1,0,0101,1,0,191,1,1,0111,1,1,110(1)(2)(3)任意取一組可行解(x1,x2,x3,x4)=(1,0,1,1),Z=3,將z≤3作為過濾條件z≤

3×√√√√×××√×√×88運(yùn)籌學(xué)-整數(shù)規(guī)劃(x2,x1,x3)Z約束條件1234過濾條件0,0,000,0,10,1,00,1,11,0,01,0,11,1,01,1,1(1)(2)(3)(4)任意取一組可行解(x1,x2,x3)=(0,0,1),Z=5,將z≥5作為過濾條件z≥55√√√√38-23√√√√z≥816最優(yōu)解為(x1,x2,x3)=(1,0,1),最優(yōu)值z=889運(yùn)籌學(xué)-整數(shù)規(guī)劃第五節(jié)指派問題一、指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型指派問題的定義:n個人來完成n件事,每個人必須完成一件事情,每件事情必須有一個人來完成.已知第i人做第j事的費(fèi)用為cij(i,j=1,2,…n),要求確定人和事之間的一一對應(yīng)的指派方案，使完成這n件事情的總費(fèi)用最少.稱C為指派問題的效率(價值)系數(shù)矩陣.90運(yùn)籌學(xué)-整數(shù)規(guī)劃第五節(jié)指派問題指派問題的模型指派問題解矩陣每行有且只有一個1每列有且只有一個191運(yùn)籌學(xué)-整數(shù)規(guī)劃第五節(jié)指派問題例13某商業(yè)公司計劃開辦5家商店.為了盡早建成營業(yè),商業(yè)公司決定由5家建筑公司分別承建.已知建筑公司Ai(i=1,2,…,5)對新商店Bj(j=1,2,…,5)的建造費(fèi)用的報價為cij(i,j=1,2,…,5),問商業(yè)公司應(yīng)當(dāng)對5家建筑公司怎樣分配建造任務(wù)才能使總的建造費(fèi)用最少.B1B2B3B4B5A14871512A279171410A3691287A46714610A5691210692運(yùn)籌學(xué)-整數(shù)規(guī)劃第五節(jié)指派問題例13某商業(yè)公司計劃開辦5家商店.為了盡早建成營業(yè),商業(yè)公司決定由5家建筑公司分別承建.已知建筑公司Ai(i=1,2,…,5)對新商店Bj(j=1,2,…,5)的建造費(fèi)用的報價為cij(i,j=1,2,…,5),問商業(yè)公司應(yīng)當(dāng)對5家建筑公司怎樣分配建造任務(wù)才能使總的建造費(fèi)用最少.該問題模型為:93運(yùn)籌學(xué)-整數(shù)規(guī)劃第五節(jié)指派問題二、匈牙利解法

1955年,庫恩(W.W.Kuhn)利用匈牙利數(shù)學(xué)家康尼格(D.Konig)的關(guān)于矩陣中獨(dú)立零元素的定理，提出了解指派問題的一種算法，習(xí)慣上稱之為匈牙利算法.步驟1

變換系數(shù)矩陣.先對各行元素分別減去本行中的最小元素,再對各列元素減去本列中的最小元素。-4-7-6-6-694運(yùn)籌學(xué)-整數(shù)規(guī)劃第五節(jié)指派問題二、匈牙利解法

1955年,庫恩(W.W.Kuhn)利用匈牙利數(shù)學(xué)家康尼格(D.Konig)的關(guān)于矩陣中獨(dú)立零元素的定理，提出了解指派問題的一種算法，習(xí)慣上稱之為匈牙利算法.步驟1

變換系數(shù)矩陣.先對各行元素分別減去本行中的最小元素,再對各列元素減去本列中的最小元素。-1-395運(yùn)籌學(xué)-整數(shù)規(guī)劃第五節(jié)指派問題二、匈牙利解法

1955年,庫恩(W.W.Kuhn)利用匈牙利數(shù)學(xué)家康尼格(D.Konig)的關(guān)于矩陣中獨(dú)立零元素的定理，提出了解指派問題的一種算法，習(xí)慣上稱之為匈牙利算法.步驟1

變換系數(shù)矩陣.先對各行元素分別減去本行中的最小元素,再對各列元素減去本列中的最小元素。96運(yùn)籌學(xué)-整數(shù)規(guī)劃第五節(jié)指派問題二、匈牙利解法

1955年,庫恩(W.W.Kuhn)利用匈牙利數(shù)學(xué)家康尼格(D.Konig)的關(guān)于矩陣中獨(dú)立零元素的定理，提出了解指派問題的一種算法，習(xí)慣上稱之為匈牙利算法.步驟2

在變換后的系數(shù)矩陣中確定獨(dú)立零元素。若獨(dú)立零元素有n個,則已得出最優(yōu)解;若少于n個,則作能覆蓋所有零元素的最少直線數(shù)目的直線集合.定義：在效率矩陣C中，有一組在不同行不同列的零元素，稱為獨(dú)立零元素組，此時每個元素稱為獨(dú)立零元素。97運(yùn)籌學(xué)-整數(shù)規(guī)劃第五節(jié)指派問題二、匈牙利解法

1955年,庫恩(W.W.Kuhn)利用匈牙利數(shù)學(xué)家康尼格(D.Konig)的關(guān)于矩陣中獨(dú)立零元素的定理，提出了解指派問題的一種算法，習(xí)慣上稱之為匈牙利算法.作能覆蓋所有零元素的最少直線數(shù)目的直線集合.1對沒有的行打√√2在已打√的行中對所在列打√.0√3在已打√的列中對所在行打√.重復(fù)2和3直到再也找不到可以打√的行或列.√4對沒有打√的行畫一橫線,對打√的列畫一豎線,得到覆蓋所有零元素的最少直線數(shù)目。98運(yùn)籌學(xué)-整數(shù)規(guī)劃第五節(jié)指派問題二、匈牙利解法

1955年,庫恩(W.W.Kuhn)利用匈牙利數(shù)學(xué)家康尼格(D.Konig)的關(guān)于矩陣中獨(dú)立零元素的定理，提出了解指派問題的一種算法，習(xí)慣上稱之為匈牙利算法.步驟3

繼續(xù)變換系數(shù)矩陣.在未被直線覆蓋的元素中找出一個最小元素,對未被直線覆蓋的行均減去該元素,被直線覆蓋的列均加上該元素。(未被直線覆蓋的數(shù)字減去最小值，交叉數(shù)字加最小值)√√√066212101001199運(yùn)籌學(xué)-整數(shù)規(guī)劃第五節(jié)指派問題二、匈牙利解法

1955年,庫恩(W.W.Kuhn)利用匈牙利數(shù)學(xué)家康尼格(D.Konig)的關(guān)于矩陣中獨(dú)立零元素的定理，提出了解指派問題的一種算法，習(xí)慣上稱之為匈牙利算法.步驟3

繼續(xù)變換系數(shù)矩陣.在未被直線覆蓋的元素中找出一個最小元素,對未被直線覆蓋的行均減去該元素,被直線覆蓋的列均加上該元素。返回步驟2100運(yùn)籌學(xué)-整數(shù)