ch08_整数规划与目标规划

1、Chapter 8整數規劃與目標規劃整數規劃與目標規劃管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-2整數規劃線性規劃模式混合整數規劃純整數規劃0-1 整數規劃管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-3njxmibxatsxcjnjijijnjjj, 2 , 1, 10, 2 , 1, . .max11或0-1 整數規劃整數規劃管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-4m,1,i , 1

2、0y)i(n,1,jm;,1,i , 0 xm,1,i 0,ybx)(n,1,j, dxs.t.yfxcMinjixi 0i 1yiijn1jiiijm1ijijm1in1jm1iiiijijiji或地點生產產能限制第市場的市場需求第個地點的數量個地點生產運輸到第第個地點決定不設廠若第個地點決定設廠若第j混合整數規劃混合整數規劃管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-5為整數2121212121x,x0 x,x45x9x56xx. t . sx8x5zmax純整數規劃純整數規劃管理科學：作業研究與電腦應用管理科學：作業研究

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

4、)和最佳和最佳解就差很大。解就差很大。 0-1 變數四捨五入，沒有意義。變數四捨五入，沒有意義。管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-8求極大整數規劃分限法流程圖求極大整數規劃分限法流程圖管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-9例題例題1求解求解(一一)管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-10例題例題1求解求解(二二)管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用

5、 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-11例題例題1求解求解(三三)管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-12例題例題1求解求解(四四)管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-13例題例題1求解求解(五五)管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-14切面法切面法1/2n第第1步：解沒有整數限制的步：解沒有整數限制的LP問題，令為最佳解，令問題，令為最佳解，令p

6、= 1。n第第2步：若步：若 全為整數，則為整數規劃最佳解，停止。全為整數，則為整數規劃最佳解，停止。n第第3步：令步：令 ， 是最佳解右是最佳解右手常數，手常數， 是小於等於的最大整數。是小於等於的最大整數。 0e,bbe|emineiiiiiqib ibx管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-15切面法切面法2/2n第第4步：令步：令 ，增加一個限制式，增加一個限制式(切面切面)： yp 是新的虛變數，是新的虛變數， 是最佳解非基變數是最佳解非基變數 xj 的第的第 q 列的係數。列的係數。n第第5步：增加以上限制條

7、件到目前的步：增加以上限制條件到目前的LP問題，求其最佳解。或問題，求其最佳解。或者將上列限制條件加到目前最佳解表中，再利用對偶單形法。者將上列限制條件加到目前最佳解表中，再利用對偶單形法。n第第6步：若以上步：若以上LP問題，無可行解，則整數規劃無解，停止。問題，無可行解，則整數規劃無解，停止。 若若 p M，停止。否則，停止。否則 為為LP最佳解，令最佳解，令 p = p+1，回到第，回到第2步。步。qjqjqjaadqe 是非基變數jXjqjpxdyqjax管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-16,41,i ,0

8、 x45xx9x56xxx. t . sx8x5zmaxi42132121且為整數例題例題3管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-17,41,i , 04154145494149. .41414345max43243143ixxxxxxxtsxxz例題例題3-解解1/8例題例題3-解解2/8管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】841 x43 4332xxx43x41412x 2xx041434304341414343xxxx

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

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

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

12、數量最小化運送成本與最大化運送數量最大化製程輸出與最小化製程時間最大化製程輸出與最小化製程時間最小化存貨與最大化銷售最小化存貨與最大化銷售管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-26線性規劃模式兩大假設線性規劃模式兩大假設:(II) n當線性規劃模式或整數規劃模式無解時，無法當線性規劃模式或整數規劃模式無解時，無法知道是那些限制式造成此無解的狀況。當線性知道是那些限制式造成此無解的狀況。當線性規劃模式或整數規劃模式規模非常大規劃模式或整數規劃模式規模非常大(千或萬條千或萬條限制式限制式)，但仍有無解的狀況時，從中找出是那，

13、但仍有無解的狀況時，從中找出是那些限制式造成此無解的狀況是非常困難且常常些限制式造成此無解的狀況是非常困難且常常是不可能的任務。是不可能的任務。管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-27目標規劃目標規劃n目標規劃模式就是為解決上述兩個造成線性規目標規劃模式就是為解決上述兩個造成線性規劃模式或整數規劃模式使用限制上的重大假設劃模式或整數規劃模式使用限制上的重大假設的方法的方法 n目標規劃模式是線性規劃模式或整數規劃模式目標規劃模式是線性規劃模式或整數規劃模式的變型，以重複執行的線性規劃方法指令來解的變型，以重複執行的線性規

14、劃方法指令來解決多目標線性規劃模式，同時將所有限制式改決多目標線性規劃模式，同時將所有限制式改成目標限制式，解決線性規劃模式或整數規劃成目標限制式，解決線性規劃模式或整數規劃模式無解的問題。模式無解的問題。管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-28離差變數離差變數(Deviational Variables)n在建構目標規劃模式的過程中，除了一般線性在建構目標規劃模式的過程中，除了一般線性規劃模式或整數規劃模式的變數外，會運用兩規劃模式或整數規劃模式的變數外，會運用兩種特殊的變數種特殊的變數(離差變數離差變數)，將原限制

15、式轉換成，將原限制式轉換成目標限制式。這兩種離差變數目標限制式。這兩種離差變數(Deviational Variables)定義如下：定義如下：di+：過多離差變數：過多離差變數(Amount Over Deviational Variable)，為超過目標，為超過目標i的數量的數量di-：不足離差變數：不足離差變數(Amount Under Deviational Variable)，為低於目標，為低於目標i的數量的數量 管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-29目標規劃模式之變數目標規劃模式之變數 n在建構目標規劃模

16、式的過程中，除了一般線性在建構目標規劃模式的過程中，除了一般線性規劃模式或整數規劃模式的變數外，會運用兩規劃模式或整數規劃模式的變數外，會運用兩種特殊的變數種特殊的變數(離差變數離差變數)，將原限制式轉換成，將原限制式轉換成目標限制式目標限制式 。管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-30例題例題4 n某製造商生產兩種商品某製造商生產兩種商品(商品商品1與商品與商品2)，每單位商品，每單位商品1需使用需使用5小時人工製造時間、小時人工製造時間、8元的生產成本、可獲得元的生產成本、可獲得3元的利潤；每元的利潤；每單位商品單

17、位商品2需使用需使用2小時製造時間、小時製造時間、10元的生產成本、可獲得元的生產成本、可獲得2元的利潤。此製造商每週共有元的利潤。此製造商每週共有900小時可用的人工製造時間、小時可用的人工製造時間、共有共有2800元可用的製造資金。我們再討論一下這個製造商的元可用的製造資金。我們再討論一下這個製造商的目標。這些目標依其對此製造商的重要性排列包括：目標。這些目標依其對此製造商的重要性排列包括：為避免裁員的狀況發生，此製造商希望將所有可用的人工製造時為避免裁員的狀況發生，此製造商希望將所有可用的人工製造時間用完。間用完。若假設所有生產的商品都可銷售出去，此製造商希望能獲得每週若假設所有生產的商

18、品都可銷售出去，此製造商希望能獲得每週$650的利潤。的利潤。為避免資金缺口，此製造商希望每週的製造資金不超過為避免資金缺口，此製造商希望每週的製造資金不超過2800元。元。1.若人工製造時間不夠用可啟動加班機制，但是此製造商希望加班若人工製造時間不夠用可啟動加班機制，但是此製造商希望加班小時最少。小時最少。管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-31目標規劃模式建構目標規劃模式建構:建構模式建構模式 n在建構目標規劃模式前，若先不考量四的目標，可將在建構目標規劃模式前，若先不考量四的目標，可將原產品組合問題的線性規劃模式

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

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

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

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

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

24、 , , P4 d1 ，其中，其中P4為第四目標的意思。為第四目標的意思。管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-36模式模式8-1 Min P1 d1 , , P2 d2 , , P3 d3 , , P4 d1 s.t. 5x + 2y + d1 d1+ = 9003x + 2y + d2 d2+ = 6508x + 10y + d3 d3+ = 2800 x 0, y 0, d1 0, d1+ 0, d2 0, d2+ 0, d3 0, d3+ 0 管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8

25、整數規劃與目標規劃整數規劃與目標規劃】8-37目標規劃模式之解題目標規劃模式之解題 n解決目標規劃模式的步驟，是以解決目標規劃模式的步驟，是以重複執行的重複執行的線線性規劃或整數規劃方法性規劃或整數規劃方法指令指令來解決多目標線性來解決多目標線性規劃模式，其演算方法與步驟如下：規劃模式，其演算方法與步驟如下：將目標將目標1定為目前的目標，解決最小化線性規劃或定為目前的目標，解決最小化線性規劃或整數規劃問題。整數規劃問題。將所得到之最佳解，列為一條限制式。將所得到之最佳解，列為一條限制式。若已經沒有其他的目標，則停止解題輸出最後之若已經沒有其他的目標，則停止解題輸出最後之解。若還有其他目標則進入

26、步驟解。若還有其他目標則進入步驟41.將下一目標定為目前的目標，解決最小化線性規將下一目標定為目前的目標，解決最小化線性規劃或整數規劃問題，並到步驟劃或整數規劃問題，並到步驟2。管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-38步驟步驟1： 最小化目標最小化目標1 n將目標將目標1定為目前的目標，解決最小化線性規劃問題如下：定為目前的目標，解決最小化線性規劃問題如下：Min Z1 = d1 s.t. 5x + 2y + d1 d1+ = 900 3x + 2y + d2 d2+ = 650 8x + 10y + d3 d3+ =

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

28、1所得到之最佳解，列為一條限制式，並將目標所得到之最佳解，列為一條限制式，並將目標2定為目前的目標，解決最小化定為目前的目標，解決最小化線性規劃問題如下：線性規劃問題如下：Min Z2 = d2 s.t. 5x + 2y + d1 d1+ = 9003x + 2y + d2 d2+ = 6508x + 10y + d3 d3+ = 2800Z1 = d1 = 0 x 0, y 0, d1 0, d1+ 0, d2 0, d2+ 0, d3 0, d3+ 0 n運用運用Excel解決此最小化線性規劃問題解決此最小化線性規劃問題(目標位置為目標位置為F2)，結果如下：，結果如下：n所得到的結果為所

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

30、9003x + 2y + d2 d2+ = 6508x + 10y + d3 d3+ = 2800Z1 = d1 = 0, Z2 = d2 = 0 x 0, y 0, d1 0, d1+ 0, d2 0, d2+ 0, d3 0, d3+ 0 n運用運用Excel解決此最小化線性規劃問題解決此最小化線性規劃問題(目標位置為目標位置為I2)，結果如下：，結果如下：n所得到的結果為所得到的結果為 x = 100, y = 200, d1 = 0, d1+ = 0, d2 = 0, d2+ = 50, d3 = 0, d3+ = 0 而目標而目標 Z3 = d3 = 0。管理科學：作業研究與電腦應用

31、管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-41步驟步驟4： 最小化目標最小化目標4 n將目標將目標3所得到之最佳解，列為一條限制式，並將目標所得到之最佳解，列為一條限制式，並將目標4定為目前的目標，解決最小化定為目前的目標，解決最小化線性規劃問題如下：線性規劃問題如下：Min Z4 = d1 s.t. 5x + 2y + d1 d1+ = 9003x + 2y + d2 d2+ = 6508x + 10y + d3 d3+ = 2800Z1 = d1 = 0, Z2 = d2 = 0, Z3 = d3 = 0 x 0, y 0, d1 0, d1+ 0

32、, d2 0, d2+ 0, d3 0, d3+ 0 n運用運用Excel解決此最小化線性規劃問題解決此最小化線性規劃問題(目標位置為目標位置為E2)，結果如下：，結果如下：n所得到的結果為所得到的結果為 x = 100, y = 200, d1 = 0, d1+ = 0, d2 = 0, d2+ = 50, d3 = 0, d3+ = 0 而目標而目標 Z4 = d1 = 0管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-42目標規劃模式之解答目標規劃模式之解答n全部全部4個步驟都做完總結這個問題用個步驟都做完總結這個問題用目標

33、規劃模式求解之後所得到的目標規劃模式求解之後所得到的最佳解為：此製造商應生產最佳解為：此製造商應生產100單位的商品單位的商品1與與200單位的商品單位的商品2；總總得利潤為得利潤為700元元；每週共每週共900小時的人工製造時間且無加工小時的人工製造時間且無加工；共使用共使用2800元的製造資金。元的製造資金。根據上述最佳解，四個目標的達成狀況為：根據上述最佳解，四個目標的達成狀況為：目標目標1. 為避免裁員的狀況發生，此製造商希望將所有可用的人工製造時為避免裁員的狀況發生，此製造商希望將所有可用的人工製造時間用完。因為間用完。因為d1 = 0表示所有表示所有可用的人工製造時間都用完，所以目

34、標可用的人工製造時間都用完，所以目標1達成。達成。目標目標2. 若假設所有生產的商品都可銷售出去，此製造商希望能獲得每週若假設所有生產的商品都可銷售出去，此製造商希望能獲得每週$650的利潤。因為的利潤。因為d2 = 0表示表示每週有至少每週有至少$650的利潤，且的利潤，且d2+ = 50表示表示每週有每週有$50多於多於$650的利潤，總利潤為的利潤，總利潤為$700，所以目標，所以目標2達成。達成。目標目標3. 為避免資金缺口，此製造商希望每週的製造資金不超過為避免資金缺口，此製造商希望每週的製造資金不超過2800元。元。因為因為d3+ = 0表示表示每週使用的製造資金並未超過每週使用的

35、製造資金並未超過2800元，所以目標元，所以目標3達成。達成。目標目標4. 若人工製造時間不夠用可啟動加班機制，但是此製造商希望加班若人工製造時間不夠用可啟動加班機制，但是此製造商希望加班小時最少。因為小時最少。因為d1+ = 0表示表示每週使用的人工製造時間並未超過每週使用的人工製造時間並未超過900小時，小時，所以目標所以目標4達成。達成。管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-43特殊目標規劃模式之問題特殊目標規劃模式之問題 n以以8.8節中之產品組合問題為例，若除了上述節中之產品組合問題為例，若除了上述的三個目標之

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

37、標規劃模式建構:目標目標4n若人工製造時間不夠用可啟動加班機制，但是若人工製造時間不夠用可啟動加班機制，但是此製造商希望加班小時少於此製造商希望加班小時少於100小時小時假設：假設：d4+：為超過目標為超過目標4的數量的過多離差變數。的數量的過多離差變數。d4 ：為低於目標為低於目標4的數量的不足離差變數。的數量的不足離差變數。則限制式則限制式5x + 2y + d1 d1+ = 900，應加入一新的限應加入一新的限制式制式d1 + d4 d4+ = 100，且目標函式為，且目標函式為Min P1 d1 , , P2 d2 , , P3 d3 , , P4 d4 ，其中，其中P4為第四目標的意

38、為第四目標的意思。思。管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-45目標規劃模式建構目標規劃模式建構:目標目標5n為此製造商已與某零售商簽約，必須製造至少為此製造商已與某零售商簽約，必須製造至少120單位的單位的商品商品1與與200單位的商品單位的商品2，以免毀約，以免毀約假設：假設：d5+：為超過目標為超過目標5商品商品1數量的過多離差變數。數量的過多離差變數。d5 ：為低於目標為低於目標5商品商品1數量的不足離差變數。數量的不足離差變數。d6+：為超過目標為超過目標5商品商品2數量的過多離差變數。數量的過多離差變數。d6

39、 ：為低於目標為低於目標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為第五目標的意思，為第五目標的意思，在這個目標中總共有兩種商品，但是因為此二商品的單位利潤不在這個目標中總共有兩種商品，但是因為此二商品的單位利潤不同，因此在目標中應將此單位利潤當成權數。同，因此

40、在目標中應將此單位利潤當成權數。管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】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+

41、 0, d3 0, d3+ 0, d4 0, d4+ 0, d5 0, d5+ 0, d6 0, d6+ 0 管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-47步驟步驟4： 最小化目標最小化目標4 n將目標將目標3所得到之最佳解，列為一條限制式，並將目標所得到之最佳解，列為一條限制式，並將目標4定為目前的目標，解決最小化線性規劃問題如定為目前的目標，解決最小化線性規劃問題如下：下：Min Z4 = d4 s.t. 5x + 2y + d1 d1+ = 9003x + 2y + d2 d2+ = 6508x + 10y + d3

42、d3+ = 2800d1 + d4 d4+ = 100 x + d5 d5+ = 120y + d6 d6+ = 200Z1 = 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 n所得到的結果為所得到的結果為 x = 120, y = 184, d1 = 0, d1+ = 68, d2 = 0, d2+ = 78, d3 = 0, d3+ = 0, d4 = 32, d4+ = 0, d5 = 0, d5

43、+ = 0, d6 = 16, d6+ = 0 而目標而目標 Z4 = d4 = 0。運用運用Excel解決此最小化線解決此最小化線性規劃問題性規劃問題(目標位置為目標位置為K2)的結果：的結果：管理科學：作業研究與電腦應用管理科學：作業研究與電腦應用 【Ch.8 整數規劃與目標規劃整數規劃與目標規劃】8-48步驟步驟5： 最小化目標最小化目標5 n將目標將目標4所得到之最佳解，列為一條限制式，並將目標所得到之最佳解，列為一條限制式，並將目標5定為目前的目標，解決最小化線性規劃問題如定為目前的目標，解決最小化線性規劃問題如下：下：Min Z5 = 3d5 +2d6 s.t. 5x + 2y +

44、 d1 d1+ = 9003x + 2y + d2 d2+ = 6508x + 10y + d3 d3+ = 2800d1 + d4 d4+ = 100 x + d5 d5+ = 120y + d6 d6+ = 200Z1 = 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 n所得到的結果為所得到的結果為 x = 120, y = 184, d1 = 0, d1+ = 68, d

45、2 = 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 整數規劃與目標規劃整數規劃與目標規劃】8-49目標規劃模式之解答目標規劃模式之解答1/2n全部全部5個步驟都做完總結這個問題用目標規劃模式求解之後所個步驟都做完總結這個問題用目標規劃模式求解之後

46、所得到的最佳解為：此製造商應生產得到的最佳解為：此製造商應生產120單位的商品單位的商品1與與184單位單位的商品的商品2；總得利潤為；總得利潤為728元；每週共用元；每週共用968小時的人工製造時小時的人工製造時間且無加工；共使用間且無加工；共使用2800元的製造資金。根據上述最佳解，五元的製造資金。根據上述最佳解，五個目標的達成狀況為：個目標的達成狀況為： 目標目標1. 為避免裁員的狀況發生，此製造商希望將所有可用的人工製造時為避免裁員的狀況發生，此製造商希望將所有可用的人工製造時間用完。因為間用完。因為d1 = 0表示所有表示所有可用的人工製造時間都用完，所以目標可用的人工製造時間都用完，所以目標1達成。達成。目標目標2. 若假設所有生產的商品都可銷售出去，此製造商希望能獲得每週若假設所有生產的商品都可銷售出去，此製造商希望能獲得每週$650的利潤。因為的利潤。因為d2 = 0表示表示每週有至少每週有至少$650的利潤，且的利潤，且d2+ = 78表示表示每週有每週有$78多於多於$650的利潤，總利潤為的