運籌學(xué)基礎(chǔ)-整數(shù)規(guī)劃.ppt

1,三、0-1規(guī)劃的應(yīng)用舉例,1、m個約束條件只有k個起作用,m個約束條件可表示為：,增加變量定義為：,又設(shè)M為任意大的數(shù)，則,表明：m個約束條件中有m-k個的右端項為bi+Myi，不起約束作用,整數(shù)規(guī)劃,2,【實例】,maxZ= 3x1 +5 x2 x1 8 2x2 12 3x1 +4 x2 36 x1 0, x2 0,引入輔助變量,模型化為：,maxZ= 3x1 +5 x2 x1 8+My1 2x2 12+My2 3x1 +4 x2 36My3 y1+y2+y3=1 x1 0, x2 0，yi只取0或1,（1）三個約束中只有兩個起作用,（2）三個約束中至少有兩個起作用,maxZ= 3x1 +5 x2 x1 8+My1 2x2 12+My2 3x1 +4 x2 36My3 y1+y2+y31 x1 0, x2 0，yi只取0或1,整數(shù)規(guī)劃,3,2、約束條件的右端可能是b1或b2br,即：,引入變量定義為：,則原約束可表示為,【例如】某約束為 2x1+5x2-x32或3,引入輔助變量y1,y2, 約束化為,2x1+5x2-x32y1+3y2,y1+y2=1,y1，y2只取0或1,整數(shù)規(guī)劃,4,3、兩組條件滿足其中一組,若x14,則 x21；否則（即x14時）， x23,引入變量定義為：,又M為任意大的數(shù)，則問題可表達(dá)為,整數(shù)規(guī)劃,5,4、用以表示含固定費用的函數(shù),用xj代表產(chǎn)品j的生產(chǎn)量，其生產(chǎn)費用函數(shù)通?？杀硎緸椋?Kj為與生產(chǎn)量無關(guān)的生產(chǎn)準(zhǔn)備費用，生產(chǎn)才發(fā)生，不生產(chǎn)不發(fā)生。,解決方法：設(shè)置一個邏輯變量yj，當(dāng) xj=0時，yi=0，當(dāng)xj0時，yj=1,可以看出當(dāng)xj=0時，yi=0；而如果yi=1，則必有xj0,為此引進(jìn)一個特殊的約束條件，則模型設(shè)為,整數(shù)規(guī)劃,6,【應(yīng)用1】,工廠的各種產(chǎn)品所需要的機時、人工工時、原材料的資源數(shù)量及可用資源的總量、產(chǎn)品的售價和各種資源的價格等因素。有關(guān)信息在下表中給出。,產(chǎn)品A 產(chǎn)品B 資源總量 資源價格（元單位） 機器（時） 6 8 120 人工（時） 10 5 100 20 原材料(公斤) 11 8 130 1 產(chǎn)品售價（元） 600 400,設(shè) x1,x2分別為產(chǎn)品A、B的生產(chǎn)量。,整數(shù)規(guī)劃,7,如果生產(chǎn)產(chǎn)品A，工廠要花費1000元的固定成本，如果生產(chǎn)產(chǎn)品B，工廠要花費800元的固定成本。 假設(shè)其它情況不變，請你為該工廠設(shè)計一個使利潤最大化的生產(chǎn)方案。 再令y1,y2分別表示生產(chǎn)A、B和可能性（即1為生產(chǎn)，0為不生產(chǎn)）,整數(shù)規(guī)劃,8,例2,紅星日用化工廠為發(fā)運產(chǎn)品，下一年度需6種不同容積的包裝，每種包裝的需求量及生產(chǎn)一個的可變費用如下表：,由于生產(chǎn)不同容積包裝箱需進(jìn)行專門準(zhǔn)備、下料等，生產(chǎn)某一容積包裝箱的固定費用為1200元，又若某一容積包裝箱數(shù)量不夠時，可用比它容積大的代替。試問化工廠應(yīng)訂做哪幾種代號的包裝箱各多少個，使費用最節(jié)省。,整數(shù)規(guī)劃,9,設(shè)： xj為代號j包裝箱的訂做數(shù)量。,整數(shù)規(guī)劃,10,例3,東方大學(xué)計算機實驗室聘用4名大學(xué)生（代號為1、2、3、4），兩名研究生（代號為5、6）值班答疑，已經(jīng)每人周一至周五每天最多可安排時間及每人每小時的報酬如下表：,實驗室開放時間為早8：00至晚10：00，值班時須有且僅須有一名學(xué)生值班，規(guī)定大學(xué)生每周值班不少于8小時，研究生每周值班不少于7小時，每名學(xué)生值班不超過3次，每次不少于2小時，每天安排值班不超過3人，且一名為研究生。試安排一張，使總報酬最低。,整數(shù)規(guī)劃,11,【解】,設(shè)： xij為學(xué)生i在周j值班時間，aij代表學(xué)生i在周j 最多值班時間，ci代表學(xué)生i的報酬。,整數(shù)規(guī)劃,12,0-1規(guī)劃應(yīng)用舉例：,maxZ= 12 x1 + 8 x2 5x1+2 x2 150 2 x1+3 x2 100 4x1+2 x2 80或6x1+8x2 120 x1, x2 0,maxZ= 12 x1 + 8