整數線性規劃 線性規劃中有一項假設，是決策變數是連續的，且不必為整數。如果某個問題符合線性規劃連續性等其他假設，但決策變數卻必須是整數，則成為『整數線性規劃(ILP)』。 7-1.

Presentation on theme: "整數線性規劃 線性規劃中有一項假設，是決策變數是連續的，且不必為整數。如果某個問題符合線性規劃連續性等其他假設，但決策變數卻必須是整數，則成為『整數線性規劃(ILP)』。 7-1."— Presentation transcript:

1 整數線性規劃 線性規劃中有一項假設，是決策變數是連續的，且不必為整數。如果某個問題符合線性規劃連續性等其他假設，但決策變數卻必須是整數，則成為『整數線性規劃(ILP)』。 7-1

2 整數線性規劃類型 整數線性規劃問題一般可分為三種型態 純粹整數問題 問題中所有變數都必須是整數。 混合整數線性規劃問題
問題中有某些變數必須是整數，而其他變數可 以不為整數。 0-1整數規劃問題 這類型問題的變數不僅必須是整數，還必須是 0或1；所以，這些變數也被稱之為「二位元變 數」(Binary Variables)或「0-1變數」。 7-2

3 A100型與B200型零件的每組利潤分別為2百萬與1百萬元， A100型與B200機器上的處理時間分別為3與2小時; 若此種
機器總共有40小時可用以處理此兩型零件 3.且由於政策上的考 量，此兩型零件至少各必須生產4組 7-3

4 圖解法與電腦解 題目請見課本p152 [解] 令X與Y分別為A100型與B200型零件的生產量(組) 模型： Max 2X + Y s.t.
X  4 A100型零件至少須生產4組 Y  4 B200型零件至少須生產4組 X, Y  0 且為整數 7-4

5 圖解法範例說明(1/7) 在求解過程，可先不考慮整數的限制，也就是求其放鬆線性規劃(LP Relaxation)
修正模型限制式 ：X, Y  0變數X與Y為非負實數 放鬆線性規劃(LP Relaxation)： 在求解純粹整數及混合整數問題之初期過程，可以先不考慮整數的限制，其餘限制式不變，稱之為放鬆線性規劃 7-5

6 圖解法範例說明(2/7) 先作出「放鬆線性規劃」問題。從圖7.1中知，當目標函數等斜率線往右上方移動至與可行區域仍有交點處之座標為(10.66, 4)，此為第一與第三條限制式所對應直線的交點：3X + 2Y = 40、Y = 4 ，可得X=10.66，Y=4。 此點為放鬆線性規劃問題的最佳解，代入可得最大利潤2X+Y = 2(10.666)+4 = 25.33(百萬)。 7-6

7 圖解法範例說明(3/7) 7-7

8 圖解法範例說明(4/7) 倘若取為最接近的整數，Y已是整數，維持Y=4不變；另外X=10.66為小數，則可取為10或11。顯然X=11不可行，因為將違反第一條限制式，故只能取X=10。 想要瞭解此組修正過後的整數解(10, 4)是否為原整數規劃問題的最佳解？ 答案否定的，從圖7.2中可看出最佳整數解為(10, 5)，最大利潤為2X+Y = 2(10)+5 = 25(百萬)。 7-8

9 圖解法範例說明(5/7) 7-9

10 圖解法範例說明(6/7) 發現以下的結果：整數線性規劃問題的最佳目標函數值小於其放鬆線性規劃問題的最佳目標函數值。 可得到結論：
對於最大化問題，整數線性規劃問題的最佳目標函數值小於或等於其放鬆線性規劃問題的最佳目標函數值 7-10

11 圖解法範例說明(7/7) 若我們想要快速得知某最大化整數規劃問題的上限，可求出其放鬆線性規劃問題的最佳目標函數值，因整數線性規劃的最佳目標函數值將不大於此值。 註：對於最小化的問題，整數線性規劃問題的最佳目標函數值大於或等於其放鬆線性規劃問題的最佳目標函數值 7-11

12 電腦解範例說明(1/2) 7-12

13 電腦解範例說明(2/2) 最佳解X=10，Y=5，目標值=25，此與圖解法所得結果相同 7-13

14 1. 會計師處理每家公司行號報稅事宜約需花費四小時， 處理個人報稅事宜約需花費90分鐘 .
2.每位會計師允許每週最多連續工作五天，每天最多工作10小時 3.若精燁有三位部份工時(part-time)的員工可供調度運用，每週最多工作三天(可不必連續)，每天最多工作10小時 精燁的管理部門希望發展出最佳的人力排班計畫，以滿足每天的工作需求。 7-14

15 人力排班規劃(1/3) 題目請見課本p Xi = 第i天(i =1~7)開始上班 (full-time)員工人數(連續工作五天) Yi = 第i天(i =1~7)上班 (part-time)員工人數(未必連續工作) 模型： Min X1+X2+X3+X4+X5+X6+X7 s.t. X1+X4+X5+X6+X7+Y1  !(24*1.5+18*4)/10=10.8 X1+X2+X5+X6+X7+Y2  6.1 X1+X2+X3+X6+X7+Y3  7.5 X1+X2+X3+X4+X7+Y4  8.7 7-15

16 人力排班規劃(2/3) X1+X2+X3+X4+X5+Y5  11.1 X2+X3+X4+X5+X6+Y6  9.0
Y1+Y2+Y3+Y4+Y5+Y6+Y7  9 Xi, Yi為非負整數  i (=1~7) 7-16

17 人力排班規劃(3/3) 7-17

18 每種元件均可由三型機器加工：機器A、B與C ;該公司應如何生產，以使得利潤為最大 .各元件的產能限制為各10,000個.
7-18

19 固定成本問題(1/3) 題目請見課本p157-158 Lindo輸入模型： 【解】
Xij = 元件i(=1, 2, 3)在機器j(=A, B, C) 產量 Yj = 1，若機器j(=A, B, C)有被運用來生產元件；否則為0 Lindo輸入模型： Max 12X1A+10X1B+13X1C+10X2A+12X2B+10X2C+15X3A+19X3B+16X3C YA-10000YB-15000YC 7-19

20 固定成本問題(2/3) s.t. 5X1A+6X2A+4X3A<= 6000YA !=100小時*60分/小時
2X1B+4X2B+3X3B<= 7200YB !=120小時*60分/小時 3X1C+5X2C+6X3C<= 4800YC !=80小時*60分/小時 end int YA int YB int YC 7-20

21 固定成本問題(3/3) OBJECTIVE FUNCTION VALUE 1) 43900.00
1) VARIABLE VALUE REDUCED COST YA YB YC X1A X1B X1C X2A X2B X2C X3A X3B X3C ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 4) 7-21

22 指派問題(Assignment Problems)
各種挖土機完成各個專案所需的時間估計值(日) 建築專案 挖土機 1 2 3 A 10 9 13 B 14 12 11 C 15 16 專案經理必須決定該如何指派這三部挖土機來執行這 三個專案，使得完成的時間最短。 7-22

23 Xij = 1，若機器i(=A, B, C)被分配來執行專案j(=1, 2, 3)；否則為0 模型：
決策變數： Xij = 1，若機器i(=A, B, C)被分配來執行專案j(=1, 2, 3)；否則為0 模型： Min 10XA1+9XA2+13XA3+14XB2+12XB2+11XB3+12XC1+15XC2+16XC3 s.t. XA1+XA2+XA3<=1 XB1+XB2+XB3<=1 XC1+XC2+XC3<=1 XA1+XB1+XC1=1 XA2+XB2+XC2=1 XA3+XB3+XC3=1 Xij  0 7-23

24 OBJECTIVE FUNCTION VALUE 1) 32.00000 VARIABLE VALUE REDUCED COST
1) VARIABLE VALUE REDUCED COST XA XA XA XB XB XB XC XC XB 7-24

25 發展與求解一整數規劃模型，使投資報酬的淨現值為最大。 假設最多只能執行一個倉庫擴張計畫，修正(a)部份的模型。
假如執行新產品試推活動，則必須推出促銷廣告，修正(b)部份以反映這種情況。 7-25

26 研擬最佳投資策略(1/2) 題目請見課本p162 【解答】 1. Xi = 1，假如選擇投資方案i(=1~6)；否則為0
Max 4000X1+6000X X3+4000X4+8000X5+3000X6 s.t. 3000X1+2500X2+6000X3+2000X4+5000X5+1000X6  10500 1000X1+3500X2+4000X3+1500X4+1000X5+500X6  7000 4000X1+3500X2+5000X3+1800X4+4000X5+900X6  8750 Xi = 0, 1  I 目標值： 最佳解：X3=X4=X6=1選擇方案三、 四與六 2. 須加入以下多重選擇限制式：X1 + X2  1 3. 須加入以下條件限制式：X3 – X4  0 7-26

27 研擬最佳投資策略(2/2) 7-27

28 整數規劃模型中0-1變數的運用 運用0-1整數變數來表示 選擇其一與互斥的限制（請參考課本p163）
EX: 四選一(選擇其一)-Multiple Choice EX:四最多選一(互斥的限制)-Mutually exclusive 從n種方案中選擇其中k ( n)種方案限制式 （請參考課本p165） EX: 四選二 (2 out of 4 alternatives) 有條件限制與相依限制式（請參考課本p165） Ex: 若採用方案一，則必須選擇方案二（conditional) Ex:方案一與方案二必須做相同決策（corequisite) 7-28

29 HW 1,2,3, 4, 5, 8, 9, 10 7-29

30 整數規劃問題的求解方法 在求解一般整數線性規劃時，通常使用兩種求解技術： 切面法(Cutting Plane Method)
分枝界限法(Branch and Bound Algorithm) 7-30

31 切面法 它是以ILP的放鬆線性規劃問題求解為基礎。 若放鬆問題所求出的最佳解是整數，則也將是整數規劃問題的最佳解。
若不是整數最佳解，就必須在問題中加入限制式或切面，來排出非整數解。 若加入切面後，對新線性規劃問題求出的最佳解是整數，則這必定是整數規劃問題的最佳解。 如果最佳解仍非整數，就要再加入新切面。重複以上的步驟，直到找出整數最佳解為止。 7-31

32 分枝界限法(1/14) 題目請見課本p168 步驟一：求解放鬆問題
首先，求解(P1)的放鬆問題，若幸運求得的是整數解，則我們立即得到P1的最佳解。我們以圖解法來解以下放鬆問題(LPR1)： Max X X2 (LPR1) s.t. 11X X2  66 5X1 + 50X2  225 X1, X2  0 7-32

33 分枝界限法(2/14) 7-33

34 分枝界限法(3/14) 從圖中可以看出放鬆問題的最佳解落在兩條限制線的交點，可解以下聯立方程式： 11X1 + 6X2 = 66
得到X1*=3.75，X2*=4.125。由於這兩個值都不是整數，所以我們尚未得到P1的最佳解。 7-34

35 分枝界限法(4/14) 求解放鬆問題我們可以得到以下的資訊：
令OV(‧)表示問題(‧)之最佳目標函數值，當求出OV(LPR1)，即知道OV(P1) 上限。放鬆問題的目標函數為X1 + 5X2，則可得到：OV(P1)  (4.125) = = UB 若將問題(LPR1)最佳解的小數部份去掉成為X1=3，X2=4，則得到(P1)問題可行解。求出OV(P1)的下限如下：OV(P1)  3 + 5(4) = 23 = LB 7-35

36 分枝界限法(5/14) 下限值是否等於OV(P1)，尚無法斷定，目前只知道：23  OV(P1)  24.375
其求解過程中，常用「樹狀圖」來表示，如圖 7-36

37 分枝界限法(6/14) 步驟二：分枝(Branching) 將二式分別加入(P1)形成兩個新問題(P2)與(P3)
Max X1 + 5X2 (P2) s.t. 11X1 + 6X2  66 5X1 + 50X2  225 X  3 X1, X2  0 且為整數 Max X1 + 5X2 (P3) X  4 7-37

38 分枝界限法(7/14) 因X1為整數，不可能在區間(3, 4)內，所以(P1)最佳解必包含於(P2)或(P3)可行區域內，如圖7.11
7-38

39 分枝界限法(8/14) 發展樹狀圖 先求解(P2)與(P3)的放鬆問題(LPR2)與(LPR3)，而OV(LPR2)為24.00，OV(LPR3)為22.33。因 (P1) 最佳解必定與(P2)或(P3)其中之一的最佳解相同所以OV(P1)  Max{OV(P2), OV(P3)}  Max {OV(LPR2), OV(LPR3)}=24.00 因為OV(LPR3)= 22.33小於LB=23，往下分枝將再增加限制式，則目標函數值不可能大於22.33，不可能比目前最佳目標函數值23為佳。此時，則可將此節點分枝剷除(prune)，不必再往下分枝。 7-39

40 分枝界限法(9/14) 7-40

41 分枝界限法(10/14) 因X2非整數，選它作分枝。X2須為整數，必滿足：X2  4、X1  5 Max X1 + 5X2 (P4)
s.t. 11X X2  66 5X1 + 50X2  225 X  3 X  4 X1, X2  0 且為整數 Max X1 + 5X2 (P5) s.t. 11X1 + 6X2  66 X  5 7-41

42 分枝界限法(11/14) 7-42

43 分枝界限法(12/14) P4放鬆問題最佳解為X1=3,X2=4故為P4之最佳解。此時OV(P4) = X1 + 5X2 = 3 + 5(4) = 23，並於節點4下方標示「×」表示無須繼續分枝。OV(P2)  Max{OV(P4), OV(P5)}  Max{LPR(P4), LPR(P5)}=23 故再將UB下修為23。至此，我們得到23 = LB  OV(P1)  UB = 23。亦即，P1的最佳解為X1=3，X2=4，最佳目標函數值為23。 7-43

44 分枝界限法(13/14) 將上述終結節點的三種情況彙整如下：
當其上限LB (如圖7.12中node 3) 當其代表一不可行問題，亦即無可行解 當其放鬆問題有整數解(圖7.14中node 4) 樹狀圖所有節點都無法再繼續分枝，分枝界限法終止求解步驟，此時，LB與UB之值相等，此值為原問題(P1)的最佳目標值，即LB = UB = OV(P1) 7-44

45 7-45

46 7-46

47 分枝界限法(14/14) 至於最小化問題，分枝界限法之求解流程與圖7.15類似，其差異之處為： 放鬆問題的最佳目標為原問題「下限」
步驟中之「下限」，需改為「上限」 步驟中之「最大化」改為「最小化」 步驟中之「最大的」改為「最小的」 7-47