《管理運(yùn)籌學(xué)》案例演示(混合整數(shù)規(guī)劃)

1、使用計(jì)算機(jī)軟件包求解(附件1)總目錄A Linear Programming 1 2 3 4 5 6 7 8 9 10 11B Integer Programming 1 2 3 4 5 6 7C Zero One Programming 1 2 3 4 5 6 7D Goal Programming 1 2 3 4 5 6 7 8E Transportation Programming 1 2 3 4 5 6 7F Assignment 1 2 3 4 5 6 8 9 10 11 12G Break-Even AnalysisH Decision TheoryI Network Models

2、 J CPM/PERT K Inventory Models L Queueing Theory M Dynamic Programming N Simulation 1 2 3 O Forecasting P Markov Analysis Q Game TheoryESC Exit to Dos例1.(投資問(wèn)題)某廠要制訂一個(gè)產(chǎn)品宣傳計(jì)劃，可利用的廣告渠道有三種：電視、廣播、雜志。市場(chǎng)調(diào)研的結(jié)果如下表所示。該廠計(jì)劃用于廣告費(fèi)用不超過(guò)16萬(wàn)元。此外還要求：（1）受到廣告影響的婦女至少要有200千人；（2）電視廣告費(fèi)用不超過(guò)10萬(wàn)元；（3）白晝電視至少要訂3個(gè)廣告，熱門(mén)時(shí)間至少2個(gè)廣告；（4）

3、廣播和雜志上的廣告數(shù)都應(yīng)在5到10之間。該廠如何制訂一個(gè)廣告計(jì)劃使受到影響的總?cè)藬?shù)最多。電 視白晝時(shí)間熱門(mén)時(shí)間廣播雜志每個(gè)廣告的費(fèi)用（千元）每個(gè)廣告影響總?cè)藬?shù)（千人）每個(gè)廣告影響婦女?dāng)?shù)（千人）8403015904065020321解：設(shè)電視白晝時(shí)間的廣告?zhèn)€數(shù)為 x1、電視熱門(mén)時(shí)間的廣告?zhèn)€數(shù)為 x2、廣播的廣告?zhèn)€數(shù)為 x3、雜志的廣告?zhèn)€數(shù)為 x4。該廣告計(jì)劃模型為：用QM軟件求解結(jié)果如下：, 整數(shù)最優(yōu)方案:電視白晝時(shí)間的廣告?zhèn)€數(shù)為3、電視熱門(mén)時(shí)間的廣告?zhèn)€數(shù)為 5、廣播的廣告?zhèn)€數(shù)為 10、雜志的廣告?zhèn)€數(shù)為10。例2.（生產(chǎn)計(jì)劃問(wèn)題）某該廠有4條裝配線可以生產(chǎn)同一種產(chǎn)品，已知每條裝配線的開(kāi)工費(fèi)，生產(chǎn)

4、1件生產(chǎn)的成本以及最大生產(chǎn)能力如表所示。該廠已接受訂貨4000件，應(yīng)如何安排生產(chǎn)？裝配線A裝配線B裝配線C裝配線D開(kāi)工費(fèi)100200300200每件產(chǎn)品成本10425最大生產(chǎn)能力（件）800140010001500解：有兩類決策變量，一類，設(shè) xi 為第 i 條裝配線上生產(chǎn)的產(chǎn)品，i = 1,2,3,4;另一類，引入01變量，設(shè) yj =1表示第 j 條裝配線啟用， yj =0表示第 j 條裝配線不啟用。用QM軟件求解結(jié)果如下：最優(yōu)方案:裝配線A生產(chǎn)100件,裝配線B生產(chǎn)1400件,裝配線C生產(chǎn)1000件,裝配線D生產(chǎn)1500件;例3.(固定成本問(wèn)題)高壓容器公司制造小、中、大三種尺寸的金屬容

5、器，所用資源為金屬板、勞動(dòng)力和機(jī)器設(shè)備，制造一個(gè)容器所需所需的各種資源的數(shù)量如下表：資 源金屬板（噸）勞動(dòng)力（人月）機(jī)器設(shè)備（臺(tái)月）小號(hào)容器中號(hào)容器大號(hào)容器221432843不考慮固定費(fèi)用，每種容器售出一只所得的利潤(rùn)分別為4萬(wàn)元、5萬(wàn)元、6萬(wàn)元，可使用的金屬板有500噸，勞動(dòng)力有300人月，機(jī)器有100臺(tái)月，此外，不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號(hào)是100萬(wàn)元，中號(hào)為150萬(wàn)元，大號(hào)為200萬(wàn)元。現(xiàn)在要制訂一個(gè)生產(chǎn)計(jì)劃，使獲得利潤(rùn)為最大？解：設(shè)小號(hào)容器、中號(hào)容器和大號(hào)容器的生產(chǎn)產(chǎn)量分別為x1、x2、x3；對(duì)各種容器的固定費(fèi)用可引入01變量 y1、y2、y3，即：當(dāng)生產(chǎn)第

6、 i 種 容 器，當(dāng)不生產(chǎn)第 i 種 容 器；約束條件: 三種資源金屬板、勞動(dòng)力和機(jī)器設(shè)備的限制條件； 為了避免出現(xiàn)某種容器不投入固定費(fèi)用就生產(chǎn)這樣一種不合理的情況，必須加上以下約束條件：目標(biāo)函數(shù)： 為扣除固定費(fèi)用的利潤(rùn)最大化，即：0 或 1該生產(chǎn)計(jì)劃整數(shù)規(guī)劃模型為：用QM軟件包求解如下：最優(yōu)方案：小號(hào)容器生產(chǎn)100臺(tái)，中號(hào)和大號(hào)容器不生產(chǎn)，最大利潤(rùn)為300萬(wàn)元。例4.(生產(chǎn)計(jì)劃問(wèn)題)某汽車廠生產(chǎn)三種汽車：微型轎車、中級(jí)轎車和高級(jí)轎車。每種轎車需要的資源和銷售利潤(rùn)如下表：微型車中級(jí)車高級(jí)車鋼材（噸）1.522.5人工（小時(shí)）304050利潤(rùn)（萬(wàn)元）234該廠每月可使用的資源為鋼材6000噸，人

7、工工時(shí)55000小時(shí)。為達(dá)到經(jīng)濟(jì)規(guī)模，每種汽車的月產(chǎn)量必須達(dá)到一定的數(shù)量時(shí)才可以進(jìn)行生產(chǎn)。工廠規(guī)定的經(jīng)濟(jì)規(guī)模為：微型車1500輛，中級(jí)車1200輛，高級(jí)車1000輛。請(qǐng)構(gòu)造一個(gè)整數(shù)規(guī)劃使該廠的利潤(rùn)最大。解：設(shè)微型轎車、中級(jí)轎車和高級(jí)轎車的月產(chǎn)量分別為x1、x2、x3，對(duì)每種車型引入01變量y1、y2、y3, 即當(dāng)生產(chǎn)該 種 車型，當(dāng)不生產(chǎn)該 種車型。約束條件: 鋼材和人工工時(shí)的限制條件； 當(dāng)不生產(chǎn)某一車型時(shí)，該車型的產(chǎn)量應(yīng)為零，所以，需要加上以下約束條件：目標(biāo)函數(shù)： 三種車型的總利潤(rùn)最大化，即：某汽車廠的生產(chǎn)計(jì)劃模型為：例5.(場(chǎng)址選擇問(wèn)題)某企業(yè)在A1地已有一個(gè)工廠,其產(chǎn)品的生產(chǎn)能力為30千

8、箱，為了擴(kuò)大生產(chǎn)，打算在A2、 A3、 A4、 A5地中再選擇幾個(gè)地方建廠。已知在A2地建廠的固定成本175千元，在A3地建廠的固定成本300千元，在A4地建廠的固定成本375千元，在A5地建廠的固定成本500千元，另外，A1的產(chǎn)量， A2、 A3、 A4、 A5建成廠的產(chǎn)量，那時(shí)銷地的銷量以及產(chǎn)地到銷地的單位運(yùn)價(jià)如下表所示。銷地運(yùn)輸單價(jià)產(chǎn)地A1A2A3A4A5銷量（千箱）產(chǎn)量（千箱）85491030423742033452203010203040B1B2B3（1）應(yīng)該在哪幾個(gè)地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運(yùn)費(fèi)之和最??；（2）如果由于政策要求必須在A2、 A3地建一個(gè)廠

9、，應(yīng)該在哪幾個(gè)地方建廠？解:（1）設(shè)從Ai運(yùn)往Bj的運(yùn)輸量為 xij ,并引入0-1變量,即:當(dāng) 選 擇 Ai 地 建 廠 時(shí);當(dāng) 不 選 擇 Ai 地 建 廠 時(shí) 。約束條件: A1產(chǎn)量限制條件;及A2、 A3、 A4、 A5準(zhǔn)備建設(shè)的新廠,其產(chǎn)量約束條件； 滿足銷量的約束條件；目標(biāo)函數(shù): 總的固定成本和總的運(yùn)費(fèi)之和最小。 （2）在上述模型的基礎(chǔ)上加上一個(gè)約束條件，即：（1）最優(yōu)方案 : x11 = 30、x52 = 20、x53 = 20，其余變量為0；最優(yōu)值為860。（2）最優(yōu)方案 : x12 = 10 、x13 = 20、 x22 = 10、x41 = 30，其余變量為0 、 y2 =

10、 1 、 y4 = 1 ；最優(yōu)值為940。例6.(電力發(fā)展問(wèn)題)某地區(qū)要制訂十年電力發(fā)展規(guī)劃,根據(jù)電力需求預(yù)測(cè)得知,該地區(qū)在十年后發(fā)電機(jī)裝機(jī)容量需要增加180萬(wàn)千瓦,到時(shí)的年發(fā)電量需要增加100億千瓦小時(shí).根據(jù)調(diào)查和討論,電力規(guī)劃的方案有三個(gè):擴(kuò)建原有的火電站,但最多只能再安裝5臺(tái)10萬(wàn)千瓦的發(fā)電機(jī)組;新建水電站,但最多只能安裝4臺(tái)25萬(wàn)千瓦的發(fā)電機(jī)組;或再新建一個(gè)火電站,最多只能安裝4臺(tái)30萬(wàn)千瓦的發(fā)電機(jī)組.通過(guò)調(diào)研和計(jì)算,獲得有關(guān)的參數(shù)如下表所示。規(guī)劃要求在滿足上述要求的前提下，選取經(jīng)濟(jì)效果最優(yōu)的建設(shè)方案。備選方案擴(kuò)建火電站新建水電站新建火電站工程投資前期工程(百萬(wàn)元）單機(jī)設(shè)備(百萬(wàn)元）單

11、機(jī)容量(萬(wàn)千瓦）允許裝機(jī)臺(tái) 數(shù)資本回收因 子年運(yùn)行成本(百萬(wàn)元/億千瓦小時(shí))負(fù)荷因子5042402170651025305440.1030.05780.1034.112.283.650.660.40.7解：擴(kuò)建火電站、新建水電站和新建火電站的裝機(jī)臺(tái)數(shù)分別為 x1、 x2、 x3，它們的年發(fā)電量分別為 x4、 x5、 x6億千瓦小時(shí)；由于擴(kuò)建火電站無(wú)前期土建工程施工，而新建水電站和火電站都需要進(jìn)行前期土建工程施工，這兩項(xiàng)前期工程是否施工，可引入01變量 yi。約束條件： 滿足裝機(jī)容量的要求； 滿足年發(fā)電量的需求； 各種電站裝機(jī)容量與發(fā)電量的平衡要求：擴(kuò)建火電站： x40.66876010 x1/

12、10000 ,即 5.782 x1 x4= 0類似，新建水電站、火電站： 8.76 x2 x5= 0; 8.76 x2 x5= 0; 每個(gè)備選方案最多裝機(jī)臺(tái)數(shù)的約束；目標(biāo)函數(shù)：目標(biāo)函數(shù)設(shè)計(jì)為年運(yùn)行費(fèi)用最低?；?1最優(yōu)方案: 擴(kuò)建火電站2臺(tái),新建水電站4臺(tái),新建火電站2臺(tái),年運(yùn)行費(fèi)最少為423.31百萬(wàn)元。例7.（庫(kù)房選址問(wèn)題）某公司考慮在四個(gè)城市：北京、上海、廣州和武漢設(shè)立庫(kù)房。這些庫(kù)房負(fù)責(zé)向三個(gè)地區(qū)：華北、華中和華南地區(qū)發(fā)運(yùn)貨物，每個(gè)庫(kù)房每月可處理貨物1000件。在北京設(shè)庫(kù)房每月的成本為4.5萬(wàn)元，上海為5萬(wàn)元，廣州為7萬(wàn)元，武漢為4萬(wàn)元。每個(gè)地區(qū)的月平均需求量為：華北每月600件、華中每月

13、700件、華南每月800件。發(fā)運(yùn)貨物的費(fèi)用（元/件）如下表。公司希望在滿足地區(qū)需求的前提下使平均月成本最小，且還要滿足以下條件： 如果在上海設(shè)庫(kù)房，則必須也在武漢設(shè)庫(kù)房； 最多設(shè)立兩個(gè)庫(kù)房； 武漢和廣州不能同時(shí)設(shè)立庫(kù)房。350150300武漢250400600廣州450250300上海500400200北京華南華中華北 各個(gè)庫(kù)房向各地區(qū)發(fā)運(yùn)的貨物量的限制； 滿足各個(gè)地區(qū)的需求量； 如果在上海設(shè)庫(kù)房，則必須也在武漢設(shè)庫(kù)房； 最多設(shè)立兩個(gè)庫(kù)房； 武漢和廣州不能同時(shí)設(shè)立庫(kù)房。解:（1）設(shè)從第i 個(gè)庫(kù)房發(fā)往第j 地區(qū)的貨物量為 xij ,并引入0-1變量 yj，即（2）約束條件（3）約束條件 OBJE

14、CTIVE FUNCTION VALUE 1) 425011.5 VARIABLE VALUE REDUCED COST Y1 1.000000 4.500000 Y2 0.000000 5.000000 Y3 1.000000 7.000000 Y4 0.000000 4.000000 X11 600.000000 200.000000 X12 0.000000 400.000000 X13 0.000000 500.000000 X21 0.000000 300.000000 X22 0.000000 250.000000 X23 0.000000 450.000000 X31 0.000000 600.000000 X32 0.000000 400.000000 X33 800.000000 250.000000 X41 0.000000 300.000000 X42 700.000000 150.000000 X43 0.000000 350.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 400.000000