管理運(yùn)籌學(xué)-2

1、第八章第八章 整數(shù)規(guī)劃整數(shù)規(guī)劃 1 整數(shù)規(guī)劃的圖解法 2整數(shù)規(guī)劃的計(jì)算機(jī)求解 3整數(shù)規(guī)劃的應(yīng)用 4整數(shù)規(guī)劃的分枝定界法 1 1 整數(shù)規(guī)劃的圖解法整數(shù)規(guī)劃的圖解法 例例1. 某工廠在計(jì)劃期內(nèi)要安排甲、乙兩種儀器設(shè)備的生產(chǎn)，已知生產(chǎn)儀器設(shè)備 需要A、B兩種材 料的消耗以及資 源的限制，如右 表。 問題：工廠應(yīng)分 別生產(chǎn)多少件甲、乙種儀器設(shè)備才 能使工廠獲利最多？ 甲乙資源限制 材料 A3210 材料 B025 單件獲利1 萬元1 萬元 解、解、 目標(biāo)函數(shù)： Max z = x1 + x2 約束條件： s.t. 3 x1 + 2 x2 10 2 x2 5 x1，x2 0 為整數(shù) 不考慮整數(shù)約束得到最

2、優(yōu)解： x1 =1.667， x2 = 2.5；z = 4.167 考慮整數(shù)約束得到最優(yōu)解： x1 = 2， x2 = 2； z = 4 整數(shù)規(guī)劃的最優(yōu)目標(biāo)值小于相應(yīng) 線性規(guī)劃的最優(yōu)目標(biāo)值(相當(dāng)于附加一個約束) 2 2整數(shù)規(guī)劃的計(jì)算機(jī)求解整數(shù)規(guī)劃的計(jì)算機(jī)求解 例例2 2： Max z = 15x1 + 10 x2 + 7x3 s.t. 5x1 - 10 x2 + 7x3 8 6x1 + 4x2 + 8x3 12 -3x1 + 2x2 + 2x3 10 x1,x2,x3 0 為整數(shù) 例例2 2： Max z = 15x1 + 10 x2 + 7x3 s.t. 5x1 - 10 x2 + 7x3

3、8 6x1 + 4x2 + 8x3 12 -3x1 + 2x2 + 2x3 10 x1,x2,x3 0 x3 為整數(shù) x1 為0-1變量 用管理運(yùn)籌學(xué)軟件求解得： x1 = 0 x2 = 3 x3 = 0 z = 30 用管理運(yùn)籌學(xué)軟件求解得： x1 = 1 x2 = 1.5 x3 = 0 z = 30 3 3整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用(1)(1) 一、投資場所的選擇一、投資場所的選擇 例4、京成畜產(chǎn)品公司計(jì)劃在市區(qū)的東、西、南、北四區(qū)建立銷售門市部，擬議中有10個 位置 Aj (j1，2，3，10)可供選擇，考慮到各地區(qū)居民的消費(fèi)水平及居民居住密集 度，規(guī)定： 在東區(qū)由A1 ， A2 ，A

4、3 三個點(diǎn)至多選擇兩個； 在西區(qū)由A4 ， A5 兩個點(diǎn)中至少選一個； 在南區(qū)由A6 ， A7 兩個點(diǎn)中至少選一個； 在北區(qū)由A8 ， A9 ， A10 三個點(diǎn)中至少選兩個。 Aj 各點(diǎn)的設(shè)備投資及每 年可獲利潤由于地點(diǎn)不同都是 不一樣的，預(yù)測情況見右表所 示 (單位：萬元)。但投資總額不能超過720萬元，問應(yīng)選擇哪幾個銷售點(diǎn)，可使年利潤為最 大? A1A2A3A4A5A6A7A8A9A10 投資額10012015080709080140160180 利潤36405022203025485861 解：解：設(shè)：0-1變量 xi = 1 (Ai 點(diǎn)被選用）或 0 (Ai 點(diǎn)沒被選用）。 這樣我們可

5、建立如下的數(shù)學(xué)模型： Max z =36x1+40 x2+50 x3+22x4+20 x5+30 x6+25x7+48x8+58x9+61x10 s.t. 100 x1+120 x2+150 x3+80 x4+70 x5+90 x6+80 x7+140 x8+160 x9+180 x10 720 x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 x8 + x9 + x10 2 xj 0 xj 為0-1變量，i = 1,2,3,10 二、固定成本問題 例5高壓容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機(jī) 器設(shè)備，制造一個容器所需的各種資源的數(shù)量如右

6、表所示。不考慮固定費(fèi)用，每種容器售出一只所得 的利潤分別為 4萬元、5萬元、6萬元，可使用的金 屬板有500噸，勞動力有300人月，機(jī)器有100臺月， 此外不管每種容器制造的數(shù)量是多少，都要支付一筆固定的費(fèi)用：小號是l00萬元，中號為 150 萬元，大號為200萬元?，F(xiàn)在要制定一個生產(chǎn)計(jì)劃，使獲得的利潤為最大。 解：這是一個整數(shù)規(guī)劃的問題。 設(shè)x1，x2， x3 分別為小號容器、中號容器和大號容器的生產(chǎn)數(shù)量。 各種容器的固定費(fèi)用只有在生產(chǎn)該種容器時才投入，為了說明固定費(fèi)用的這種性質(zhì)，設(shè) yi = 1(當(dāng)生產(chǎn)第 i種容器, 即 xi 0 時) 或0（當(dāng)不生產(chǎn)第 i種容器即 xi = 0 時） 引

7、入約束 xi M yi ，i =1，2，3，M充分大，以保證當(dāng) yi = 0 時，xi = 0 。 這樣我們可建立如下的數(shù)學(xué)模型： Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 500 2x1 + 3x2 + 4x3 300 x1 + 2x2 + 3x3 100 xi M yi ，i =1，2，3，M充分大 xj 0 yj 為0-1變量，i = 1,2,3 3 3整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用(2)(2) 資源小號容器中號容器大號容器 金屬板（噸）248 勞動力（人月）234 機(jī)器設(shè)備（臺月）123 例6

8、有四個工人，要分別指派他們完 成四項(xiàng)不同的工作，每人做各項(xiàng)工作所消 耗的時間如右表所示，問應(yīng)如何指派工作， 才能使總的消耗時間為最少。 解解：引入01變量 xij，并令 xij = 1(當(dāng)指派第 i人去完成第j項(xiàng)工作時)或0（當(dāng)不指派第 i人去完成第j項(xiàng)工作時) 這可以表示為一個0-1整數(shù)規(guī)劃問題： Min z=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24+26x31+17x32+16x33+19x34+19x41 +21x42+23x43+17x44 s.t. x11+ x12+ x13+ x14= 1 (甲只能干一項(xiàng)工作) x21+ x22

9、+ x23+ x24= 1 (乙只能干一項(xiàng)工作) x31+ x32+ x33+ x34= 1 (丙只能干一項(xiàng)工作) x41+ x42+ x43+ x44= 1 (丁只能干一項(xiàng)工作) x11+ x21+ x31+ x41= 1 ( A工作只能一人干) x12+ x22+ x32+ x42= 1 ( B工作只能一人干) x13+ x23+ x33+ x43= 1 ( C工作只能一人干) x14+ x24+ x34+ x44= 1 ( D工作只能一人干) xij 為0-1變量，i,j = 1,2,3,4 * * * 求解可用管理運(yùn)籌學(xué)軟件中整數(shù)規(guī)劃方法。 3 3整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用(3)(3

10、) 工作 工人 ABCD 甲15182124 乙19232218 丙26171619 丁19212317 三、指派問題三、指派問題 有 n 項(xiàng)不同的任務(wù)，恰好 n 個人可分別承擔(dān)這些任務(wù)，但由于每人特長不同，完成各 項(xiàng)任務(wù)的效率等情況也不同。現(xiàn)假設(shè)必須指派每個人去完成一項(xiàng)任務(wù)，怎樣把 n 項(xiàng)任務(wù)指派 給 n 個人，使得完成 n 項(xiàng)任務(wù)的總的效率最高，這就是指派問題。 四、分布系統(tǒng)設(shè)計(jì)四、分布系統(tǒng)設(shè)計(jì) 例例7某企業(yè)在 A1 地已有一個工廠，其產(chǎn)品的生產(chǎn)能力為 30 千箱，為了擴(kuò)大生產(chǎn)，打算在 A2，A3，A4，A5地中再 選擇幾個地方建廠。已知在 A2 ， A3，A4，A5地建廠的固 定成本分別

11、為175千元、300千元、375千元、500千元，另 外， A1產(chǎn)量及A2，A3，A4，A5建成廠的產(chǎn)量，那時銷地 的銷量以及產(chǎn)地到銷地的單位運(yùn)價(每千箱運(yùn)費(fèi))如右表所示。 a) 問應(yīng)該在哪幾個地方建廠，在滿足銷量的前提下，使得其總的固定成本和總的運(yùn)輸費(fèi)用之和最小? b) 如果由于政策要求必須在A2，A3地建一個廠，應(yīng)在哪幾個地方建廠? 解：解： a) 設(shè) xij為從Ai 運(yùn)往Bj 的運(yùn)輸量(單位千箱)， yi = 1(當(dāng)Ai 被選中時)或0（當(dāng)Ai 沒被選中時) 這可以表示為一個整數(shù)規(guī)劃問題： Min z = 175y2+300y3+375y4+500y5+ 8x11+4x12+3x13+5

12、x21+2x22+3x23+4x31+3x32+4x33+9x41 +7x42+5x43+10 x51 +4x52+2x53 其中前4項(xiàng)為固定投資額，后面的項(xiàng)為運(yùn)輸費(fèi)用。 s.t. x11+ x12+ x13 30 ( A1 廠的產(chǎn)量限制) x21+ x22+ x23 10y2 ( A2 廠的產(chǎn)量限制) b）增加約束：y2+y3=1 x31+ x32+ x33 20y3 ( A3 廠的產(chǎn)量限制) x41+ x42+ x43 30y4 ( A4 廠的產(chǎn)量限制) x51+ x52+ x53 40y5 ( A5 廠的產(chǎn)量限制) x11+ x21+ x31+ x41 + x51 = 30 ( B1 銷

13、地的限制) x12+ x22+ x32+ x42 + x52 = 20 ( B2 銷地的限制) x13+ x23+ x33+ x43 + x53 = 20 ( B3 銷地的限制) xij 0 yi為0-1變量，i = 1,2,3,4,5；j = 1,2,3 * * * 求解可用管理運(yùn)籌學(xué)軟件中整數(shù)規(guī)劃方法。 3 3整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用(4)(4) 銷地 產(chǎn)地 B1B2B3產(chǎn)量(千噸) A184330 A252310 A343420 A497530 A5104240 銷量(千噸)302020 3 3整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用(5)(5) 五、投資問題五、投資問題 例例8 8某公司在今后

14、五年內(nèi)考慮給以下的項(xiàng)目投資。已知： 項(xiàng)目A：從第一年到第四年每年年初需要投資，并于次年末回收本利115%，但要求第一年投資最低金額 為4萬元，第二、三、四年不限； 項(xiàng)目B：第三年初需要投資，到第五年未能回收本利128，但規(guī)定最低投資金額為3萬元，最高金額為5 萬元； 項(xiàng)目 C：第二年初需要投資，到第五年未能回收本利140%，但規(guī)定其投資額或?yàn)?萬元或?yàn)?萬元或?yàn)? 萬元或?yàn)?萬元。 項(xiàng)目 D：五年內(nèi)每年初可購買公債，于當(dāng)年末歸還，并加利息6%，此項(xiàng)投資金額不限。 該部門現(xiàn)有資金10萬元，問它應(yīng)如何確定給這些項(xiàng)目的每年投資額，使到第五年末擁有的資金本利總額 為最大? 解：解：1) 設(shè)xiA、xi

15、B、xiC、xiD ( i 1，2，3，4，5)分別表示第 i 年年初給項(xiàng)目A，B，C，D的投資額； 設(shè)yiA， yiB，是01變量，并規(guī)定取 1 時分別表示第 i 年給A、B投資，否則取 0（ i = 1, 2, 3, 4, 5）。 設(shè)yiC 是非負(fù)整數(shù)變量，并規(guī)定：2年投資C項(xiàng)目8萬元時，取值為4； 2年投資C項(xiàng)目6萬元時，取值為3； 2年投資C項(xiàng)目4萬元時，取值為2； 2年投資C項(xiàng)目2萬元時，取值為1； 2年不投資C項(xiàng)目時， 取值為0； 這樣我們建立如下的決策變量： 第1年 第2年 第3年 第4年 第5年 A x1A x2A x3A x4A B x3B C x2C (=20000y2C)

16、 D x1D x2D x3D x4D x5D 3 3整數(shù)規(guī)劃的應(yīng)用整數(shù)規(guī)劃的應(yīng)用(6)(6) 2 2）約束條件：）約束條件： 第一年：年初有100000元，D項(xiàng)目在年末可收回投資，故第一年年初應(yīng)把全部資金投出去，于是 x1A+ x1D = 100000； 第二年：A次年末才可收回投資故第二年年初的資金為1.06x1D，于是x2A+x2C+x2D = 1.06x1D； 第三年：年初的資金為 1.15x1A+1.06x2D，于是 x3A+x3B+x3D = 1.15x1A+ 1.06x2D； 第四年：年初的資金為 1.15x2A+1.06x3D，于是 x4A + x4D = 1.15x2A+ 1.

17、06x3D； 第五年：年初的資金為 1.15x3A+1.06x4D，于是 x5D = 1.15x3A+ 1.06x4D； 關(guān)于項(xiàng)目A的投資額規(guī)定: x1A 40000y1A ，x1A 200000y1A ，200000是足夠大的數(shù)； 保證當(dāng) y1A = 0時， x1A = 0 ；當(dāng)y1A = 1時，x1A 40000 。 關(guān)于項(xiàng)目B的投資額規(guī)定: x3B 30000y3B ，x3B 50000y3B ； 保證當(dāng) y3B = 0時， x3B = 0 ；當(dāng)y3B = 1時，50000 x3B 30000 。 關(guān)于項(xiàng)目C的投資額規(guī)定: x2C = 20000y2C ，y2C = 0，1，2，3，4。

18、 3 3）目標(biāo)函數(shù)及模型：目標(biāo)函數(shù)及模型： Max z = 1.15x4A+ 1.40 x2C+ 1.28x3B + 1.06x5D s.t. x1A+ x1D = 100000； x2A+x2C+x2D = 1.06x1D； x3A+x3B+x3D = 1.15x1A+ 1.06x2D； x4A+x4D = 1.15x2A+ 1.06x3D； x5D = 1.15x3A+ 1.06x4D； x1A 40000y1A ， x1A 200000y1A ， x3B 30000y3B ， x3B 50000y3B ； x2C = 20000y2C ， yiA， yiB = 0 或 1，i = 1,2

19、,3,4,5 y2C = 0，1，2，3，4 xiA ，xiB ，xiC ，xiD 0 ( i = 1、2、3、4、5） 4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(1)(1) 問題（A） Min z = c1 x1 + c2 x2 + + cn xn 記 問題（B）為去掉整數(shù)約束的問題（A） s.t. a11 x1 + a12 x2 + + a1n xn = b1 a21 x1 + a22 x2 + + a2n xn = b2 am1 x1 + am2 x2 + + amn xn = bm x1 ，x2 ， ，xn 0 為整數(shù) 在分枝定界法過程中求解問題(B)，應(yīng)有以下情況之一： (B)

20、無可行解，則(A)亦無可行解，停止對此問題 的計(jì)算； (B)有最優(yōu)解，并滿足整數(shù)約束，即同時為(A)的最優(yōu)解，那么z*同時是當(dāng)前問題(A)最優(yōu) 目標(biāo)值的上界 和下界。停止對這個問題的計(jì)算； (B)有最優(yōu)解 x 及最優(yōu)值 z 但不符合整數(shù)條件。這時得到當(dāng)前問題(A)最優(yōu)目標(biāo)值的一個下 界 z z ,于是通過以下判斷可對此問題進(jìn)一步計(jì)算。 分枝定界法的計(jì)算過程： 1、對原問題(A)，求解松弛問題(B)。根據(jù)上面分析，若出現(xiàn)情況，則停機(jī)。若情況 發(fā)生，得到(A)問題最優(yōu)值的一個下界。我們?nèi)握?A)問題的一個可行解，那么對應(yīng)的目標(biāo) 函數(shù)值是(A)最優(yōu)值的一個上界 z 。即得到 z z* z。(注：找(

21、A)問題的可行解往往需 要較大的計(jì)算量，這時可簡單記 z+，而先不必費(fèi)很大力量去求較好的上界。從以下 分析可以看到，找到一個好的最優(yōu)目標(biāo)值上界，將對算法的快速求得目標(biāo)非常有效。)， 轉(zhuǎn)2，進(jìn)行以下一般步的迭代； 4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(2)(2) 2、對當(dāng)前問題進(jìn)行分枝和定界： 分技：無妨設(shè)當(dāng)前問題為(A)，其松弛問題(B)的最優(yōu)解不符合整數(shù)約束，任取非整數(shù)的分 量 xr 。構(gòu)造兩個附加約束： xr xr 和 xr xr+1 ，對(A)分別加入這兩個約束，可得到兩 個子問題(A1)和(A2)，顯然這兩個子問題的可行解集的并是(A)的可行解集； 定界：根據(jù)前面分析，對每個

22、當(dāng)前問題(A)可以通過求解松弛問題(B)，以及找(A)的可行解 得到當(dāng)前問題的上、下界 z和 z 。 對一般迭代步，設(shè)根據(jù)分枝定界方法得到了原問題(A)的一個同層子問題(AI )，i1，2，.， n 之和的分解。這里的同層子問題是指每個子問題(AI)都是(A)經(jīng)過相同分枝次數(shù)得到的。 3、比較與剪枝： 對當(dāng)前子問題進(jìn)行考察，若不需再進(jìn)行計(jì)算，則稱之為剪枝。一般遇到下列情況就需剪 枝： (B)無可行解； (B)的最優(yōu)解符合整數(shù)約束； (B)的最優(yōu)值 z z 。 通過比較，若子問題不剪枝則返回 2 。 分枝定界法當(dāng)所有子問題都剪枝了，即沒有需要處理的子問題時，達(dá)到當(dāng)前上界 z 的可 行解即原問題的

23、最優(yōu)解， 算法結(jié)束。 4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(3)(3) 分枝定界法是 求整數(shù)規(guī)劃的一種 常用的有效的方法， 既能解決純整數(shù)規(guī) 劃的問題，也能解 決混合整數(shù)規(guī)劃的 問題。 例：例： Min f = -5x1-4x2 s.t. 3x1+4x2 24 9x1+5x2 45 x1,x2 0 整數(shù) 4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(4)(4) 隱枚舉法是求解隱枚舉法是求解01規(guī)劃最常用的方法之一規(guī)劃最常用的方法之一 對于 n 個決策變量的完全 01 規(guī)劃，其可行點(diǎn)最多有 2n 個，當(dāng) n 較大時其 計(jì)算量大得驚人。隱枚舉法的基本思想是根據(jù)01規(guī)劃的特點(diǎn)，進(jìn)行分技逐

24、步 求解。 1、用于隱枚舉法的、用于隱枚舉法的01規(guī)劃標(biāo)準(zhǔn)形式：規(guī)劃標(biāo)準(zhǔn)形式： 為了計(jì)算的方便，需要把一般的 01規(guī)劃問題等價地化成下列標(biāo)準(zhǔn)形式 Min f = c1 x1 + c2 x2 + + cn xn cj 0 j = 1,2,n s.t. ai1 x1 + ai2 x2 + + ain xn bi i = 1,2,m x1 ，x2 ， ，xn = 0 或 1 下面說明一個完全的01規(guī)劃問題可以化為等價的標(biāo)準(zhǔn)形式： (1)若目標(biāo)函數(shù)求最大：Max z，可令 f = - z，變?yōu)榍笞钚?Min f ； (2)若目標(biāo)函數(shù)的系數(shù)有負(fù)值時，如 cj 0。那么，可以令相應(yīng)的 yj = 1- xj

25、 ； (3)當(dāng)某個約束不等式是“”時，只需兩端同乘以 -1，即變?yōu)椤啊?； (4)當(dāng)某個約束是等式約束時，可得到兩個方向相反的不等式。 4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(5)(5) 隱枚舉法的基本過程：隱枚舉法的基本過程： 1、將01規(guī)劃問題化為標(biāo)準(zhǔn)形式，設(shè)其最優(yōu)解為 x*，最優(yōu)目標(biāo)值為 f* 。顯然 x = 0 時，目標(biāo)值 f 0 是不考慮線性不等式約束的最小解，于是 f* 0。若 x = 0 是 可行解，那末 f 0是該問題的最優(yōu)解，結(jié)束計(jì)算。否則，置所有分量為自由變量。 轉(zhuǎn)2； 2、任選一自由變量 xk ，令 xk 為固定變量，分別固定為 xk = 0 與 xk 1，令所有

26、自 由變量取零值，則得到兩個分枝。對每個分枝的試探解進(jìn)行檢驗(yàn)（把自由變量逐 次定為固定變量的順序可以是任意的，在不進(jìn)行先驗(yàn)考察時，常按指標(biāo)變量從小 到大的順序進(jìn)行）。轉(zhuǎn)3； 3、檢驗(yàn)當(dāng)前試探解時，遇到下列4種情況就剪枝，即不必再向下分枝，在剪枝的子 問題下方標(biāo)記“”： 情況一：若子問題的試探解可行，即滿足所有線性不等式約束，則此問題的目標(biāo)值 是原問題最優(yōu)目標(biāo)值的一個上界記為 f 即 f* f 。把 f 的值記在子問題框的 旁邊，并在下方標(biāo)記上“”； 4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(6)(6) 情況二：若試探解不可行，且存在一個線性不等式約束，將所有固定變量值代入后， 所得到的不

27、等式中所有負(fù)系數(shù)之和大于右端項(xiàng)或若無負(fù)系數(shù)時，最小的系數(shù)大于 右端項(xiàng)，那么此問題的任何分枝都是不可行的問題。于是在此問題框的下方標(biāo)記 “”； 情況三：若試探解不可行，且它的目標(biāo)值與目標(biāo)函數(shù)中對應(yīng)當(dāng)前自由變量的任一 個系數(shù)之和大于所有已得到的上界中最小者時，說明在當(dāng)前問題的基礎(chǔ)上，固定 任何自由變量都不可能對目標(biāo)函數(shù)有改善，于是在該問題框的下方標(biāo)記“”； 情況四：若試探解不可行，但所有變量已被置為固定變量，也應(yīng)剪枝，于是在該 問題框的下方標(biāo)記“”。 把已標(biāo)記“”的子問題，稱為已探明的枝。轉(zhuǎn)4。 4、進(jìn)一步考察。如果所有的枝均為已探明的枝，則停機(jī)結(jié)束計(jì)算。找出所有子問 題框邊標(biāo)記 f 值的問題，比較得到其中最小者，其對應(yīng)的試探解即原問題的最 優(yōu)解，相應(yīng)值即原問題的最優(yōu)目標(biāo)值 f*；若沒有標(biāo)記 f 值的框，則說明原問題無 最優(yōu)解，實(shí)際上原問題無可行解。 如果仍存在尚未探明的分枝，則可任選一個未探明的分枝。轉(zhuǎn)2。 4 4整數(shù)規(guī)劃的分枝定界法整數(shù)規(guī)劃的分枝定界法(7)(7) 0-10-1規(guī)劃的隱枚舉法規(guī)劃的隱枚舉法 例：例： Max z=100 x1+30 x2+40 x3+45x4 s.t. 50 x1+30 x2+