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

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