Chapter 8 整數規劃與目標規劃.

Presentation on theme: "Chapter 8 整數規劃與目標規劃."— Presentation transcript:

1 Chapter 8 整數規劃與目標規劃

2 線性規劃模式 整數規劃 混合整數規劃 純整數規劃 0-1 整數規劃 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

3 0-1 整數規劃 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

4 混合整數規劃 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

5 純整數規劃 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

6 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

7 為什麼 LP 最佳解，取四捨五入的整數解是不可行？
可能是非可行解 (求 Max 去掉小數位)。 太多決策變數值要四捨五入，離最佳解會很遠。 如果決策變數值比較大(如 )四捨五入可能近似最佳解；如果決策變數值較小(如 2.78)和最佳解就「差很大」。 0-1 變數四捨五入，沒有意義。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

8 求極大整數規劃分限法流程圖 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

9 例題1求解 (一) 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

10 例題1求解 (二) 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

11 例題1求解 (三) 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

12 例題1求解 (四) 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

13 例題1求解(五) 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

14 切面法1/2 第1步：解沒有整數限制的LP問題，令為最佳解，令p = 1。 第2步：若 全為整數，則為整數規劃最佳解，停止。
第2步：若 全為整數，則為整數規劃最佳解，停止。 第3步：令 ， 是最佳解右手常數， 是小於等於的最大整數。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

15 切面法2/2 第4步：令 ，增加一個限制式(切面)： yp 是新的虛變數， 是最佳解非基變數 xj 的第 q 列的係數。
第4步：令 ，增加一個限制式(切面)： yp 是新的虛變數， 是最佳解非基變數 xj 的第 q 列的係數。 第5步：增加以上限制條件到目前的LP問題，求其最佳解。或者將上列限制條件加到目前最佳解表中，再利用對偶單形法。 第6步：若以上LP問題，無可行解，則整數規劃無解，停止。 若 p > M，停止。否則 為LP最佳解，令 p = p+1，回到第2步。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

16 例題3 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

17 例題3-解1/8 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

18 例題3-解2/8 限制式可改寫為： 得到兩個切面限制式： 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

19 例題3-解3/8 C1 和 C2 兩個限制式加上 LP 限制式，得到新的最佳解 x1 = 0，x2 = 5，z = 40。
利用演算法及對偶單形法，如下 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

20 例題3-解4/8 切面法演算步驟 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

21 例題3-解5/8 切面法演算步驟 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

22 例題3-解6/8 切面法演算步驟 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

23 例題3-解7/8 切面法演算步驟 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

24 例題3-解8/8 圖8-9 切面法 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

25 線性規劃模式兩大假設:(I) 線性規劃模式或整數規劃模式都只能有一個目標函數，但是管理的問題常常是互斥的多種目標，因此無法將管理的多目標，強迫列入這個單一目標函數中。例如： 最大化利潤與最小化成本 最小化運送成本與最大化運送數量 最大化製程輸出與最小化製程時間 最小化存貨與最大化銷售 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

26 線性規劃模式兩大假設:(II) 當線性規劃模式或整數規劃模式無解時，無法知道是那些限制式造成此無解的狀況。當線性規劃模式或整數規劃模式規模非常大(千或萬條限制式)，但仍有無解的狀況時，從中找出是那些限制式造成此無解的狀況是非常困難且常常是不可能的任務。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

27 目標規劃 目標規劃模式就是為解決上述兩個造成線性規劃模式或整數規劃模式使用限制上的重大假設的方法
目標規劃模式是線性規劃模式或整數規劃模式的變型，以重複執行的線性規劃方法指令來解決多目標線性規劃模式，同時將所有限制式改成目標限制式，解決線性規劃模式或整數規劃模式無解的問題。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

28 離差變數(Deviational Variables)
di+：過多離差變數(Amount Over Deviational Variable)，為超過目標i的數量 di-：不足離差變數(Amount Under Deviational Variable)，為低於目標i的數量 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

29 目標規劃模式之變數 在建構目標規劃模式的過程中，除了一般線性規劃模式或整數規劃模式的變數外，會運用兩種特殊的變數(離差變數)，將原限制式轉換成目標限制式 。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

30 例題4 某製造商生產兩種商品(商品1與商品2)，每單位商品1需使用5小時人工製造時間、8元的生產成本、可獲得3元的利潤；每單位商品2需使用2小時製造時間、10元的生產成本、可獲得2元的利潤。此製造商每週共有900小時可用的人工製造時間、共有2800元可用的製造資金。我們再討論一下這個製造商的目標。這些目標依其對此製造商的重要性排列包括： 為避免裁員的狀況發生，此製造商希望將所有可用的人工製造時間用完。 若假設所有生產的商品都可銷售出去，此製造商希望能獲得每週$650的利潤。 為避免資金缺口，此製造商希望每週的製造資金不超過2800元。 若人工製造時間不夠用可啟動加班機制，但是此製造商希望加班小時最少。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

31 目標規劃模式建構:建構模式 在建構目標規劃模式前，若先不考量四的目標，可將原產品組合問題的線性規劃模式列出如下：
首先定義變數如下： x = 商品1每週生產的數量 y = 商品2每週生產的數量 Max 3x + 2y s.t x + 2y  900 8x + 10y  2800 x  0, y  0 此線性規劃模式的目標為最大化此製造商每週利潤，受限於製造資金人工製造時間與製造資金。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

32 目標規劃模式建構:目標1 為避免裁員的狀況發生，此製造商希望將所有可用的人工製造時間用完 假設： d1+：為超過目標1的數量的過多離差變數。
則限制式5x + 2y  900應修改為5x + 2y + d1- － d1+ = 900，且目標函式為Min P1 d1-，其中P1為第一目標的意思。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

33 目標規劃模式建構:目標2 若假設所有生產的商品都可銷售出去，此製造商希望能獲得每週$650的利潤 假設：
d2+：為超過目標2的數量的過多離差變數。 d2-：為低於目標2的數量的不足離差變數。 則目標函式3x + 2y應修改為限制式3x + 2y + d2- － d2+ = 650，且目標函式為Min P1 d1-, P2 d2-，其中P2為第二目標的意思。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

34 目標規劃模式建構:目標3 為避免資金缺口，此製造商希望每週的製造資金不超過2800元 假設： d3+：為超過目標3的數量的過多離差變數。
則限制式8x + 10y  2800應修改為8x + 10y + d3- － d3+ = 2800，且目標函式為Min P1 d1-, P2 d2-, P3 d3+，其中P3為第三目標的意思。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

35 目標規劃模式建構:目標4 若人工製造時間不夠用可啟動加班機制，但是此製造商希望加班小時最少
此目標與目標1有關，因此可沿用目標1的離差變數與修改之限制式5x + 2y + d1- － d1+ = 900，只需將目標函式修改為Min P1 d1-, P2 d2-, P3 d3+, P4 d1+，其中P4為第四目標的意思。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

36 模式8-1 Min P1 d1-, P2 d2-, P3 d3+, P4 d1+ s.t. 5x + 2y + d1- － d1+ = 900 3x + 2y + d2- － d2+ = 650 8x + 10y + d3- － d3+ = 2800 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

37 目標規劃模式之解題 解決目標規劃模式的步驟，是以重複執行的線性規劃或整數規劃方法指令來解決多目標線性規劃模式，其演算方法與步驟如下：
將目標1定為目前的目標，解決最小化線性規劃或整數規劃問題。 將所得到之最佳解，列為一條限制式。 若已經沒有其他的目標，則停止解題輸出最後之解。若還有其他目標則進入步驟4 將下一目標定為目前的目標，解決最小化線性規劃或整數規劃問題，並到步驟2。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

38 步驟1： 最小化目標1 將目標1定為目前的目標，解決最小化線性規劃問題如下： Min Z1 = d1-
s.t. 5x + 2y + d1- － d1+ = 900 3x + 2y + d2- － d2+ = 650 8x + 10y + d3- － d3+ = 2800 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0 運用Excel解決此最小化線性規劃問題(目標位置為D2)，結果如下： 所得到的結果為 x = 100, y = 200, d1- = 0, d1+ = 0, d2- = 0, d2+ = 50, d3- = 0, d3+ = 0 而目標 Z1 = d1- = 0 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

39 步驟2： 最小化目標2 將目標1所得到之最佳解，列為一條限制式，並將目標2定為目前的目標，解決最小化線性規劃問題如下：
Min Z2 = d2- s.t. 5x + 2y + d1- － d1+ = 900 3x + 2y + d2- － d2+ = 650 8x + 10y + d3- － d3+ = 2800 Z1 = d1- = 0 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0 運用Excel解決此最小化線性規劃問題(目標位置為F2)，結果如下： 所得到的結果為 x = 100, y = 200, d1- = 0, d1+ = 0, d2- = 0, d2+ = 50, d3- = 0, d3+ = 0 而目標 Z2 = d2- = 0 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

40 步驟3： 最小化目標3 將目標2所得到之最佳解，列為一條限制式，並將目標3定為目前的目標，解決最小化線性規劃問題如下：
Min Z3 = d3+ s.t. 5x + 2y + d1- － d1+ = 900 3x + 2y + d2- － d2+ = 650 8x + 10y + d3- － d3+ = 2800 Z1 = d1- = 0, Z2 = d2- = 0 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0 運用Excel解決此最小化線性規劃問題(目標位置為I2)，結果如下： 所得到的結果為 x = 100, y = 200, d1- = 0, d1+ = 0, d2- = 0, d2+ = 50, d3- = 0, d3+ = 0 而目標 Z3 = d3+ = 0。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

41 步驟4： 最小化目標4 將目標3所得到之最佳解，列為一條限制式，並將目標4定為目前的目標，解決最小化線性規劃問題如下：
Min Z4 = d1+ s.t. 5x + 2y + d1- － d1+ = 900 3x + 2y + d2- － d2+ = 650 8x + 10y + d3- － d3+ = 2800 Z1 = d1- = 0, Z2 = d2- = 0, Z3 = d3+ = 0 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0 運用Excel解決此最小化線性規劃問題(目標位置為E2)，結果如下： 所得到的結果為 x = 100, y = 200, d1- = 0, d1+ = 0, d2- = 0, d2+ = 50, d3- = 0, d3+ = 0 而目標 Z4 = d1+ = 0 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

42 目標規劃模式之解答 全部4個步驟都做完總結這個問題用目標規劃模式求解之後所得到的最佳解為：此製造商應生產100單位的商品1與200單位的商品2；總得利潤為700元；每週共900小時的人工製造時間且無加工；共使用2800元的製造資金。 根據上述最佳解，四個目標的達成狀況為： 目標1. 為避免裁員的狀況發生，此製造商希望將所有可用的人工製造時間用完。因為d1- = 0表示所有可用的人工製造時間都用完，所以目標1達成。 目標2. 若假設所有生產的商品都可銷售出去，此製造商希望能獲得每週$650的利潤。因為d2- = 0表示每週有至少$650的利潤，且d2+ = 50表示每週有$50多於$650的利潤，總利潤為$700，所以目標2達成。 目標3. 為避免資金缺口，此製造商希望每週的製造資金不超過2800元。因為d3+ = 0表示每週使用的製造資金並未超過2800元，所以目標3達成。 目標4. 若人工製造時間不夠用可啟動加班機制，但是此製造商希望加班小時最少。因為d1+ = 0表示每週使用的人工製造時間並未超過900小時，所以目標4達成。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

43 特殊目標規劃模式之問題 以8.8節中之產品組合問題為例，若除了上述的三個目標之外，將上述第4個目標換成以下目標4，再加入另一個目標5如下：
目標4. 若人工製造時間不夠用可啟動加班機制，但是此製造商希望加班小時少於100小時。 目標5. 為此製造商已與某零售商簽約，必須製造至少120單位的商品1與200單位的商品2，以免毀約。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

44 目標規劃模式建構:目標4 若人工製造時間不夠用可啟動加班機制，但是此製造商希望加班小時少於100小時 假設：
d4+：為超過目標4的數量的過多離差變數。 d4-：為低於目標4的數量的不足離差變數。 則限制式5x + 2y + d1- - d1+ = 900，應加入一新的限制式d1- + d4- - d4+ = 100，且目標函式為Min P1 d1-, P2 d2-, P3 d3+, P4 d4+，其中P4為第四目標的意思。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

45 目標規劃模式建構:目標5 為此製造商已與某零售商簽約，必須製造至少120單位的商品1與200單位的商品2，以免毀約 假設：
d5+：為超過目標5商品1數量的過多離差變數。 d5-：為低於目標5商品1數量的不足離差變數。 d6+：為超過目標5商品2數量的過多離差變數。 d6-：為低於目標5商品2數量的不足離差變數。 應加入兩個新的限制式x + d5- - d5+ = 120 (每單位利潤$3)與y + d6- - d6+ = 200 (每單位利潤$2)，且目標函式為Min P1 d1-, P2 d2-, P3 d3+, P4 d4+, P5 (3d5-+2d6-)，其中P5為第五目標的意思，在這個目標中總共有兩種商品，但是因為此二商品的單位利潤不同，因此在目標中應將此單位利潤當成權數。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

46 模式8-2 Min P1 d1-, P2 d2-, P3 d3+, P4 d4+, P5 (3d5-+2d6-)
s.t. 5x + 2y + d1- - d1+ = 900 3x + 2y + d2- - d2+ = 650 8x + 10y + d3- - d3+ = 2800 d1- + d4- - d4+ = 100 x + d5- - d5+ = 120 y + d6- - d6+ = 200 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0, d4- 0, d4+  0, d5- 0, d5+  0, d6- 0, d6+  0 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

47 步驟4： 最小化目標4 運用Excel解決此最小化線性規劃問題(目標位置為K2)的結果：
將目標3所得到之最佳解，列為一條限制式，並將目標4定為目前的目標，解決最小化線性規劃問題如下： Min Z4 = d4+ s.t. 5x + 2y + d1- - d1+ = 900 3x + 2y + d2- - d2+ = 650 8x + 10y + d3- - d3+ = 2800 d1- + d4- - d4+ = 100 x + d5- - d5+ = 120 y + d6- - d6+ = 200 Z1 = d1- = 0, Z2 = d2- = 0, Z3 = d3+ = 0 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0, d4- 0, d4+  0, d5- 0, d5+  0, d6- 0, d6+  0 所得到的結果為 x = 120, y = 184, d1- = 0, d1+ = 68, d2- = 0, d2+ = 78, d3- = 0, d3+ = 0, d4- = 32, d4+ = 0, d5- = 0, d5+ = 0, d6- = 16, d6+ = 0 而目標 Z4 = d4+ = 0。 運用Excel解決此最小化線性規劃問題(目標位置為K2)的結果： 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

48 步驟5： 最小化目標5 運用Excel解決此最小化線性規劃問題(目標位置為P2)的結果：
將目標4所得到之最佳解，列為一條限制式，並將目標5定為目前的目標，解決最小化線性規劃問題如下： Min Z5 = 3d5-+2d6- s.t. 5x + 2y + d1- - d1+ = 900 3x + 2y + d2- - d2+ = 650 8x + 10y + d3- - d3+ = 2800 d1- + d4- - d4+ = 100 x + d5- - d5+ = 120 y + d6- - d6+ = 200 Z1 = d1- = 0, Z2 = d2- = 0, Z3 = d3+ = 0, Z4 = d4+ = 0 x  0, y  0, d1-  0, d1+  0, d2- 0, d2+  0, d3- 0, d3+  0, d4- 0, d4+  0, d5- 0, d5+  0, d6- 0, d6+  0 所得到的結果為 x = 120, y = 184, d1- = 0, d1+ = 68, d2- = 0, d2+ = 78, d3- = 0, d3+ = 0, d4- = 32, d4+ = 0, d5- = 0, d5+ = 0, d6- = 16, d6+ = 0 而目標 Z5 = 3d5- + 2d6- = 32。 運用Excel解決此最小化線性規劃問題(目標位置為P2)的結果： 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

49 目標規劃模式之解答1/2 全部5個步驟都做完總結這個問題用目標規劃模式求解之後所得到的最佳解為：此製造商應生產120單位的商品1與184單位的商品2；總得利潤為728元；每週共用968小時的人工製造時間且無加工；共使用2800元的製造資金。根據上述最佳解，五個目標的達成狀況為： 目標1. 為避免裁員的狀況發生，此製造商希望將所有可用的人工製造時間用完。因為d1- = 0表示所有可用的人工製造時間都用完，所以目標1達成。 目標2. 若假設所有生產的商品都可銷售出去，此製造商希望能獲得每週$650的利潤。因為d2- = 0表示每週有至少$650的利潤，且d2+ = 78表示每週有$78多於$650的利潤，總利潤為$728，所以目標2達成。 目標3. 為避免資金缺口，此製造商希望每週的製造資金不超過2800元。因為d3+ = 0表示每週使用的製造資金並未超過2800元，所以目標3達成。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

50 目標規劃模式之解答2/2 目標4. 若人工製造時間不夠用可啟動加班機制，但是此製造商希望加班小時少於100小時。因為d4+ = 0表示每週使用的人工製造時間並未超過900小時，且d4- = 32表示每週100加班小時中仍有32小時未用完，所以目標4達成。 目標5.為此製造商已與某零售商簽約，必須製造至少120單位的商品1與200單位的商品2，以免毀約。因為d5- = 0與d6- = 16表示每週製造之商品1不足0單位與商品2不足16單位，所以目標5並未達成。此製造商必須毀約。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

51 重點結論 目標規劃模式之最佳解，會因為目標排序的順序不同，而有不同的結果，因此目標排序是目標規劃模式最重要的前置作業。以上述的例子為例，若將目標做重新的排序，則最佳解就會改變。 目標規劃模式解題最後得到之最佳解，是依順序一一將所有目標都最小化後所得到的，因此目標順序不同而會有不同的結果。若目標規劃模式中所有的限制式都依所需目標而定，則此目標規劃模式必定有可行解。若欲解決線性規劃模式中無解的問題，則可將原線性規劃模式中所有限制式都改為依目標而定之限制式，並將這些限制式之對應目標排序，以目標規劃模式一一解題。 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

52 電腦應用範例 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

53 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

54 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

55 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

56 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】

57 管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃】