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

2024/11/51運籌學

OPERATIONSRESEARCH

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

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

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

應用舉例

§2.1

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

則原問題可表示為2024/11/511§2.2應用舉例例1

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

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

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

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

指派問題及匈牙利解法

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

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

分枝定界法

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

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

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

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

割平面法

§5.1

基本思想

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