運(yùn)籌整數(shù)規(guī)劃素材

2024/11/51運(yùn)籌學(xué)

OPERATIONSRESEARCH

2024/11/52第四章整數(shù)規(guī)劃與分配問(wèn)題

整數(shù)規(guī)劃的有關(guān)概念及特點(diǎn)整數(shù)規(guī)劃的應(yīng)用指派問(wèn)題及匈牙利解法整數(shù)規(guī)劃的求解方法：分枝定界法、割平面法2024/11/53純整數(shù)規(guī)劃：在整數(shù)規(guī)劃中，如果所有的變量都為非負(fù)整數(shù)，則稱(chēng)為純整數(shù)規(guī)劃問(wèn)題；混合整數(shù)規(guī)劃：如果有一部分變量為非負(fù)整數(shù)，則稱(chēng)之為混合整數(shù)規(guī)劃問(wèn)題。0-1變量：在整數(shù)規(guī)劃中，如果變量的取值只限于0和1，這樣的變量我們稱(chēng)之為0-1變量。0-1規(guī)劃：在整數(shù)規(guī)劃問(wèn)題中，如果所有的變量都為0-1變量，則稱(chēng)之為0-1規(guī)劃?！?整數(shù)規(guī)劃的有關(guān)概念及特點(diǎn)§1.1概念整數(shù)規(guī)劃：要求決策變量取整數(shù)值的規(guī)劃問(wèn)題。（線性整數(shù)規(guī)劃、非線性整數(shù)規(guī)劃等）2024/11/54求整數(shù)解的線性規(guī)劃問(wèn)題，不是用四舍五入法或去尾法對(duì)性規(guī)劃的非整數(shù)解加以處理就能解決的，用枚舉法又往往會(huì)計(jì)算量太大，所以要用整數(shù)規(guī)劃的特定方法加以解決。例：求解下列整數(shù)規(guī)劃：§1.2整數(shù)規(guī)劃的求解特點(diǎn)2024/11/55分析：

若當(dāng)作一般線性規(guī)劃求解，圖解法的結(jié)果如下。1、非整數(shù)規(guī)劃最優(yōu)解顯然不是整數(shù)規(guī)劃的可行解。2、四舍五入后的結(jié)果也不是整數(shù)規(guī)劃的可行解。3、可行解是陰影區(qū)域交叉點(diǎn)，可比較這些點(diǎn)對(duì)應(yīng)的函數(shù)值，找出最優(yōu)。2024/11/56§2

應(yīng)用舉例

§2.1

邏輯變量在數(shù)學(xué)模型中的應(yīng)用1、m個(gè)約束條件中只有k個(gè)起作用設(shè)有m個(gè)約束條件定義0-1整型變量：第i個(gè)約束起作用第i個(gè)約束不起作用2024/11/57設(shè)M是任意大正數(shù)，則原約束中只有k個(gè)真正起作用的情況可表示為：2024/11/582、約束條件右端項(xiàng)是r個(gè)可能值中的一個(gè)則通過(guò)定義約束條件右端項(xiàng)不是bi約束條件右端項(xiàng)是bi可將上述條件表示為2024/11/593、兩組條件中滿足其中一組例如表示條件：若，則；否則時(shí)則通過(guò)定義第i組條件起作用，i=1，2第i組條件不起作用可將上述條件表示為其中：M是任意大正數(shù)2024/11/510定義4、表示含有固定費(fèi)用的函數(shù)例如：表示產(chǎn)品的生產(chǎn)數(shù)量，其生產(chǎn)費(fèi)用函數(shù)為：目標(biāo)函數(shù)：其中是與產(chǎn)量無(wú)關(guān)的生產(chǎn)準(zhǔn)備費(fèi)用

則原問(wèn)題可表示為2024/11/511§2.2應(yīng)用舉例例1

東方大學(xué)計(jì)算機(jī)實(shí)驗(yàn)室聘用4名大學(xué)生（代號(hào)1,2,3,4）和2名研究生（代號(hào)5,6）值班。已知各學(xué)生從周一至周五每天可安排的值班時(shí)間及每人每小時(shí)報(bào)酬見(jiàn)下表所示。學(xué)生代號(hào)酬金(元/h)每天可安排的值班時(shí)間(h)周一周二周三周四周五110.060607210.00606339.94830549.855640510.830460611.3062442024/11/512實(shí)驗(yàn)室每天開(kāi)放時(shí)間為8:00AM—10:00PM,共14小時(shí)。開(kāi)放時(shí)間內(nèi)需要有一名學(xué)生值班。規(guī)定大學(xué)生每周值班時(shí)間是8—15小時(shí)，研究生是7—12小時(shí)，每次值班不小于2小時(shí)。又每名學(xué)生每周值班次數(shù)不得多于三次，每天值班人員中至少有一名研究生，每天值班人數(shù)不超過(guò)3人。試為該實(shí)驗(yàn)室安排一張人員值班表，使得總酬金支出為最少。解：設(shè)表示學(xué)生i在周j的值班時(shí)間。學(xué)生i在周j不值班學(xué)生i在周j值班

表示學(xué)生i在周j的最多可值班時(shí)間。則目標(biāo)函數(shù)：2024/11/513研究生值班7-12小時(shí)每周不超過(guò)3次每天不超過(guò)3人每天有一研究生值班不超過(guò)每人可安排的時(shí)間每天開(kāi)放14小時(shí)大學(xué)生值班8-15小時(shí)約束條件2024/11/514例2紅星日用化工廠為發(fā)運(yùn)產(chǎn)品，下一年度需要6種不同容積的包裝箱，每種包裝箱的需求量及生產(chǎn)一個(gè)的可變費(fèi)用如下表所示。包裝箱代號(hào)123456容積（m3）0.080.100.120.150.200.25需求量（個(gè)）500550700900450400可變費(fèi)用（元/個(gè)）5.08.010.012.116.318.2由于生產(chǎn)不同容積包裝箱時(shí)需進(jìn)行專(zhuān)門(mén)的準(zhǔn)備、下料等，生產(chǎn)每一種包裝箱的固定費(fèi)用都是1200元。又若某容積的包裝箱數(shù)量不夠時(shí)，可用比它大的代替。試問(wèn)該廠應(yīng)訂做哪幾種代號(hào)的包裝箱各多少個(gè)，可使得費(fèi)用最省？2024/11/515解：設(shè)表示代號(hào)為j的包裝箱的訂做數(shù)量。不訂j包裝箱訂j包裝箱目標(biāo)函數(shù)約束條件2024/11/5162024/11/517例3（固定成本問(wèn)題）高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需的各種資源的數(shù)量如表所示。每種容器售出一只所得的利潤(rùn)分別為4萬(wàn)元、5萬(wàn)元、6萬(wàn)元，可使用的金屬板有500噸，勞動(dòng)力有300人/月，機(jī)器有100臺(tái)/月，此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號(hào)是l00萬(wàn)元，中號(hào)為150萬(wàn)元，大號(hào)為200萬(wàn)元?，F(xiàn)在要制定一個(gè)生產(chǎn)計(jì)劃，使獲得的利潤(rùn)為最大。

2024/11/518解：設(shè)分別為小號(hào)容器、中號(hào)容器和大號(hào)容器的生產(chǎn)數(shù)量。

建立如下的數(shù)學(xué)模型：資源小號(hào)容器中號(hào)容器大號(hào)容器金屬板（噸）248勞動(dòng)力（人月）234機(jī)器設(shè)備（臺(tái)月）123不生產(chǎn)j型號(hào)容器生產(chǎn)j型號(hào)容器2024/11/5192024/11/520§3

指派問(wèn)題及匈牙利解法

§3.1指派問(wèn)題與模型m項(xiàng)任務(wù)分配給m個(gè)人去完成，每人只能完成其中一項(xiàng)，每項(xiàng)任務(wù)只能分給一人完成，應(yīng)如何分配使得效率最高？aij是第j個(gè)人完成第i項(xiàng)任務(wù)的效率(如時(shí)間）。人任務(wù)12…m1a11a12…a1m2a21a22…a2m……………mam1am2amm2024/11/521設(shè)于是建立模型如下：2024/11/522§3.1指派問(wèn)題的匈牙利解法該指派問(wèn)題可當(dāng)作運(yùn)輸問(wèn)題解決，但匈牙利解法更有效。解法思想：效率矩陣的元素，若有一組位于不同行不同列的零元素，則令這些位置的決策變量取值為1，其余均為0，這顯然就是最優(yōu)解。2024/11/523定理2：若矩陣A的元素可分為“0”元和“非0”元，則覆蓋“0”元的最少直線數(shù)等于位于不同行、不同列的“0”元的最大個(gè)數(shù)。定理1：效率矩陣的每一行元素分別減去（加上）一個(gè)常數(shù)，每一列元素分別減去（加上）一個(gè)元素，得新效率矩陣，，則的最優(yōu)解等價(jià)于的最優(yōu)解。2024/11/524例：有一份說(shuō)明書(shū)，要分別譯成英、日、德、俄四種語(yǔ)言，交給甲、乙、丙、丁四人去完成，各人的效率不同，如何分配任務(wù)，可使總效率最高。表中數(shù)據(jù)為完成任務(wù)所需時(shí)間（單位：小時(shí)）。人任務(wù)甲乙丙丁英文21097日文154148德文13141611俄文4151392024/11/525匈牙利解法步驟：1、在效率矩陣每行減去該行最小元素；2、在效率矩陣每列減去該列最小元素；2024/11/5263、尋找獨(dú)立“0”元素(不同行不同列）（1）從第一行開(kāi)始，若該行只有一個(gè)“0”元素，則對(duì)該“0”元素打括號(hào)（）（表示這一行的人只有這一個(gè)任務(wù)可指派），并劃去該“0”元素所在的列（表示該項(xiàng)任務(wù)不能再指派給別人）；若該行無(wú)“0”元素或有兩個(gè)以上的“0”元素（不含劃去的0），則轉(zhuǎn)下一行；（2）從第一列開(kāi)始，若該列只有一個(gè)“0”元素，則對(duì)該“0”元素打括號(hào)（），并劃去該“0”元素所在的行；若該列無(wú)“0”元素或有兩個(gè)以上的“0”元素（不含劃去的0），則轉(zhuǎn)下一列；2024/11/527（0）82511（0）5423（0）001145完成上述步驟后可能出現(xiàn)下列情況：?。┬示仃嚨拿恳恍卸加幸粋€(gè)打括號(hào)的0元素，則按照打括號(hào)的0元素位置指派任務(wù)，即是最優(yōu)解；2024/11/528ⅱ）打括號(hào)的0元素個(gè)數(shù)小于m，但未被劃去的0元素之間存在閉回路，則沿此閉回路，每隔一個(gè)0元打一括號(hào)，然后對(duì)打括號(hào)的0元素所在行或所在列畫(huà)直線；ⅲ）矩陣中所有0元素或被打括號(hào)，或被劃去，但打括號(hào)的0元素個(gè)數(shù)，則進(jìn)入下一步；2024/11/529（3）設(shè)法使每一行都有一個(gè)打括號(hào)的“0”元素。按定理1繼續(xù)對(duì)矩陣進(jìn)行變換：?。木仃囄幢恢本€覆蓋的元素中找出最小者k，ⅱ）對(duì)矩陣中無(wú)直線覆蓋的行，令，有直線覆蓋的列，令。其余為0。ⅲ）對(duì)矩陣的每個(gè)元素計(jì)算，得到一個(gè)新矩陣，轉(zhuǎn)第三步重復(fù)進(jìn)行，直至每一行都有一打括號(hào)的0元素。2024/11/530（0）82511（0）5423（0）001145根據(jù)上圖，k=2，最優(yōu)解：2024/11/531兩點(diǎn)說(shuō)明：1、任務(wù)數(shù)人數(shù)時(shí)如何處理增加虛擬的人或虛擬的任務(wù)

2、指派問(wèn)題中目標(biāo)函數(shù)變?yōu)镸AX時(shí)如何處理。每行每列找最大者，用此最大元素減去相應(yīng)各行各列的元素，得到同解矩陣。2024/11/532§4

分枝定界法

分枝定界法是求解整數(shù)規(guī)劃的一種常用的有效的方法，它既能解決純整數(shù)規(guī)劃的問(wèn)題，又能解決混合整數(shù)規(guī)劃的問(wèn)題。大多數(shù)求解整數(shù)規(guī)劃的商用軟件就是基于分枝定界法編制而成的。下面舉例來(lái)說(shuō)明分枝定界法的思想和步驟。2024/11/5331、求解整數(shù)規(guī)劃相應(yīng)的一般線性規(guī)劃問(wèn)題（即先去掉整數(shù)約束）。易知：整數(shù)規(guī)劃的可行域（?。┌诰€性規(guī)劃的可行域(大）。若線性規(guī)劃的最優(yōu)解恰是整數(shù)解，則其就是整數(shù)規(guī)劃的最優(yōu)解。否則該最優(yōu)解，是整數(shù)規(guī)劃最優(yōu)解的上界或下界。例求解下列整數(shù)規(guī)劃：2024/11/534解：1、解對(duì)應(yīng)的線性規(guī)劃：其最優(yōu)解為，顯然不是整數(shù)規(guī)劃的可行解。L0：2024/11/535性質(zhì)

求MAX的問(wèn)題：整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值小于或等于相應(yīng)的線性規(guī)劃的最優(yōu)目標(biāo)函數(shù)值；

求MIN的問(wèn)題：整數(shù)規(guī)劃的最優(yōu)目標(biāo)函數(shù)值大于或等于相應(yīng)的線性規(guī)劃的最優(yōu)目標(biāo)函數(shù)值。2、分枝與定界：將對(duì)應(yīng)的線性規(guī)劃問(wèn)題分解成幾個(gè)子問(wèn)題，每個(gè)子問(wèn)題就是一分枝，而所有子問(wèn)題的解集之和要包含原整數(shù)規(guī)劃的解集。2024/11/536求解每一分枝子問(wèn)題：若其最優(yōu)解滿足整數(shù)約束，則它就是原問(wèn)題的一個(gè)可行解（不一定是最優(yōu)）；否則，就是該枝的上界或下界。

若所有分支的最優(yōu)解都不滿足整數(shù)條件（即不是原問(wèn)題的可行解），則選取一個(gè)邊界值最優(yōu)的分支繼續(xù)分解，直至找到一個(gè)原問(wèn)題的可行解。若在同一級(jí)分枝中同時(shí)出現(xiàn)兩個(gè)以上的原問(wèn)題可行解，則保留目標(biāo)值最優(yōu)的一個(gè)，其余不再考慮。從各分枝中找原問(wèn)題可行解的目的是為下一步的比較與剪枝。2024/11/537將上述線性規(guī)劃問(wèn)題分為兩枝，并求解。解得解得L1：L2：顯然兩個(gè)分枝均非整數(shù)可行解，選邊界值較大的L1繼續(xù)分枝。2024/11/538將L1分為兩枝，并求解。解得解得L11：L12：兩個(gè)分枝均是整數(shù)可行解，保留目標(biāo)值較大的L12。2024/11/5393、比較與剪枝將各子問(wèn)題的邊界值與保留下的整數(shù)可行解對(duì)應(yīng)的目標(biāo)值比較，將邊界值劣于可行行解的分支減剪去。若比較剪枝后，只剩下所保留的整數(shù)可行解，則該解就是原整數(shù)規(guī)劃的最優(yōu)解；否則選取邊界值最大的一個(gè)分枝繼續(xù)分解，在其后的過(guò)程中出現(xiàn)新的整數(shù)可行解時(shí)，則與原可行解比較，保留較優(yōu)的一個(gè)，重復(fù)第三步。2024/11/540L0：X2≤2X2≥3X1≤3X1≥4用圖表示上例的求解過(guò)程與求解結(jié)果2024/11/541§5

割平面法

§5.1

基本思想

在整數(shù)規(guī)劃的松弛問(wèn)題中，依次引進(jìn)新的約束條件（割平面），使問(wèn)題的可行域逐步減小，但每次割去的只是部分非整數(shù)解，直到使問(wèn)題的目標(biāo)函數(shù)值達(dá)到最優(yōu)的整數(shù)點(diǎn)成為縮小后的可行域的一個(gè)頂點(diǎn)，這樣就可以用線性規(guī)劃的方法求得整數(shù)最優(yōu)解。2024/11/542例求解下列整數(shù)規(guī)劃：解：1、解對(duì)應(yīng)的線性規(guī)劃（松弛問(wèn)題），并將約束條件的系數(shù)均化為整數(shù)：2024/11/543加入松弛變量后求解，得最終單純形表：25/2011/2-1/2313/410-1/43/400-1/4-5/4如果上述求解結(jié)果是整數(shù)解，則結(jié)束；否則轉(zhuǎn)下一步；2、找出非整數(shù)解中分?jǐn)?shù)部分最大的一個(gè)基變量，并將該行對(duì)應(yīng)的約束方程所有常數(shù)（系數(shù)及常數(shù)項(xiàng)）分解成一個(gè)整數(shù)與一個(gè)正分?jǐn)?shù)之和；將所有分式項(xiàng)移到等式右端。例如上例，取第一行約束.2024/11/544易知，左端為整數(shù)，要是等式成立，右端也必為整數(shù)，且將代入上式，得2024/11/545這就是一個(gè)割平面。將其添加到原約束中，得到新的可行域如圖所示。割去的只是部分非整數(shù)解。2024/11/5463、將新的約束添加到原問(wèn)題中，得到一個(gè)新的線性規(guī)劃問(wèn)題，求解此問(wèn)題，可用靈敏度分析