目標規(guī)劃運籌學講義

1、 運籌學運籌學 熊中楷教授熊中楷教授目標規(guī)劃（目標規(guī)劃（1 1） 運籌學運籌學 熊中楷教授熊中楷教授復習上節(jié)課內容復習上節(jié)課內容：產銷不平衡運輸問題產銷不平衡運輸問題上節(jié)課難點：上節(jié)課難點：產銷不平衡運輸問題建立模型，造假產銷不平衡運輸問題建立模型，造假本節(jié)課內容本節(jié)課內容：目標規(guī)劃和圖解法目標規(guī)劃和圖解法本節(jié)課難點三個本節(jié)課難點三個難點難點1. 1.建立模型中：目標函數(shù)偏差是正或者負建立模型中：目標函數(shù)偏差是正或者負難點難點2.2.圖解法中：方向偏差是正或者負圖解法中：方向偏差是正或者負 難點難點3. 3.圖解法中：判斷解圖解法中：判斷解第四章：目標規(guī)劃（第四章：目標規(guī)劃（1 1） 運籌學運

2、籌學 熊中楷教授熊中楷教授第四章：目標規(guī)劃（第四章：目標規(guī)劃（1 1）Chapter 4: objective programming(1)example and model of objective programminggraphic method of objective programming第四章：目標規(guī)劃（第四章：目標規(guī)劃（13）目標規(guī)劃（目標規(guī)劃（1） 目標規(guī)劃的引例與模型，圖解法目標規(guī)劃的引例與模型，圖解法目標規(guī)劃（目標規(guī)劃（2）目標規(guī)劃的單純形法，靈敏度分）目標規(guī)劃的單純形法，靈敏度分 析析目標規(guī)劃（目標規(guī)劃（3）目標規(guī)劃的應用）目標規(guī)劃的應用 運籌學運籌學 熊中楷教授熊中楷

3、教授線性規(guī)劃-單目標決策： 利潤最大或 成本最小第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1）事實上，企業(yè)面臨的多目標決策 我們人生面臨的多目標決策 運籌學運籌學 熊中楷教授熊中楷教授一個國有企業(yè)面臨的多目標決策 1 穩(wěn)定指標（完不成第1把手下崗） 今年下崗不超過現(xiàn)有人數(shù)的 1 員工參加法能功上北京人數(shù)=253萬3 新產品開發(fā)任務=2項第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1） 運籌學運籌學 熊中楷教授熊中楷教授目標函數(shù)目標函數(shù)：Min多個目標的正負偏差多個目標的正負偏差 約束條件約束條件： 第一目標穩(wěn)定正負偏差下崗第一目標穩(wěn)定正負偏差下崗2 第二目標利潤正

4、負偏差第二目標利潤正負偏差5000萬萬 第三目標成本正負偏差第三目標成本正負偏差3000萬萬 第四目標新產品開發(fā)費用正負偏差第四目標新產品開發(fā)費用正負偏差250萬萬第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1） 運籌學運籌學 熊中楷教授熊中楷教授 產品產品A 產品產品B擁有量擁有量原 材 料原 材 料（公斤）（公斤）2111設備設備（小時）（小時）1212利潤利潤（萬元（萬元/件）件）810 書上引例：書上引例： 某工廠生產某工廠生產A、B兩種產品，有關數(shù)據(jù)如下兩種產品，有關數(shù)據(jù)如下, 用線性規(guī)劃求解：用線性規(guī)劃求解： 第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1

5、1） 運籌學運籌學 熊中楷教授熊中楷教授求利潤最大的決策是求利潤最大的決策是 產品產品A生產生產4 產品產品B生產生產3利用線性規(guī)劃求出利用線性規(guī)劃求出 ：總利潤為：總利潤為62萬元萬元 這時原材料用完這時原材料用完 設備剩余設備剩余2小時小時實際中，決策時不只考慮利潤最大，還要考慮市場等一系列條件，例如實際中，決策時不只考慮利潤最大，還要考慮市場等一系列條件，例如 （1) 根據(jù)市場信息，產品根據(jù)市場信息，產品A的需求有下降的趨勢，因此考慮產品的需求有下降的趨勢，因此考慮產品A的的 產量不大于產品產量不大于產品B的產量的產量 （2） 超過計劃供應的原材料時，需要用高價采購，使成本增加超過計劃供

6、應的原材料時，需要用高價采購，使成本增加 （3） 盡可能利用設備，但不希望加班盡可能利用設備，但不希望加班 （4） 盡可能達到并且超過利潤指標盡可能達到并且超過利潤指標56萬元萬元 求：決策方案。求：決策方案。 第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1） 運籌學運籌學 熊中楷教授熊中楷教授例例1. 線性規(guī)劃模型線性規(guī)劃模型 相關目標規(guī)劃模型相關目標規(guī)劃模型 利潤最大利潤最大 Max Z= 8x1+10 x2 8x1+ 10 x2+ d1- -d1+ =56 決策目標不是利潤最大，而是有多個，重要性有先后之分：決策目標不是利潤最大，而是有多個，重要性有先后之分： 假設：第一目

7、標假設：第一目標 利潤不小于利潤不小于56元元 (利潤小于利潤小于56-d1-0) 第二目標第二目標 充分利用臺時，不加班充分利用臺時，不加班 第三目標第三目標 產品產品1產量不大于產品產量不大于產品2產量產量 目標偏差最小：目標偏差最?。篗inP1 d1- + P2( d2- -d2+ ) + P3d3+ 第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1）原材料約束原材料約束 2x1+ x2 =11 2x1+ x2 =11設備約束設備約束 x1+ 2x2 =0 x1 - x2 +d3_d3+ =0 xi =0, di- , d+I=0 難點難點1. 1.建立建立模型中：目模型中：

8、目標函數(shù)偏差標函數(shù)偏差是正或者負是正或者負 運籌學運籌學 熊中楷教授熊中楷教授 知識要點知識要點 1概念概念（1）偏差變量：實際值與目標值之間差距的變量表示，通常以）偏差變量：實際值與目標值之間差距的變量表示，通常以di-、di+表示，表示， 分別稱為正偏差變量、負偏差變量、且有分別稱為正偏差變量、負偏差變量、且有di-0,di+0。（2）優(yōu)先級系數(shù)：又稱優(yōu)先級因子，描述問題中目標重要性程度的優(yōu)先級系數(shù)：又稱優(yōu)先級因子，描述問題中目標重要性程度的 差別，一般用差別，一般用pi表示。通常，表示。通常，i值越小，代表的優(yōu)先程度越高。值越小，代表的優(yōu)先程度越高。 （3）目標約束與系統(tǒng)約束：描述問題中

9、兩類不同性質的限制條件。）目標約束與系統(tǒng)約束：描述問題中兩類不同性質的限制條件。 一般目標約束用來描述允許對給定目標值有一定偏離程度的限制條件。一般目標約束用來描述允許對給定目標值有一定偏離程度的限制條件。 而系統(tǒng)約束表示的意義同線性規(guī)劃模型的約束條件。而系統(tǒng)約束表示的意義同線性規(guī)劃模型的約束條件。 2模型特點模型特點（1）引進正負偏差變量，對所有目標下的正負偏差變量，均有）引進正負偏差變量，對所有目標下的正負偏差變量，均有 di-di+=0；（2）模型中必順存在目標約束，而系統(tǒng)約束可以不存在；模型中必順存在目標約束，而系統(tǒng)約束可以不存在；（3）目標函數(shù)為偏差變量表述式；）目標函數(shù)為偏差變量表

10、述式；（4）以優(yōu)先級系數(shù)描述目標的重要性程度。目標規(guī)劃問題的滿意解可）以優(yōu)先級系數(shù)描述目標的重要性程度。目標規(guī)劃問題的滿意解可 是一個是一個 點，點， 一條線段或者為一個區(qū)域。一條線段或者為一個區(qū)域。第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1） 運籌學運籌學 熊中楷教授熊中楷教授d1-d1+X1-X2 +1=0X1X2d1- =1X1 - X2 =0第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1）難點難點2.2.圖解方法中：圖解方法中：方向偏差是正或者方向偏差是正或者負負X1 - X2 =02X1-X2 +1=0判斷判斷d1-方向方向判斷判斷d1+方向方向 運籌

11、學運籌學 熊中楷教授熊中楷教授d2+ =1X1+2X2 =10X1X2510X1+2X2 -1=10第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1）d2+d1- 運籌學運籌學 熊中楷教授熊中楷教授P104 例例3 電視生產電視生產第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1）Min z= MinP1 d1- + P2 d2+ + P3 ) (2d3- + d4- ) x1+ x2 + d1- -d1+ = 40 x1 + x2 +d2_d2+ =50 x1 +d3_d3+ =24 x2 +d4_d4+ =30 xi =0, di- , d+I=0 運籌學運籌學 熊

12、中楷教授熊中楷教授d3- 03024d4- ？d4+P104 例例3 電視生產電視生產d3d2+ 0d1- 0彩電彩電X1X2黑白黑白5004040第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1）難點難點3. 3.圖解方法中：圖解方法中：判斷解判斷解MinP1 d1- + P2 d2+ + P3 ) (2d3- + d4- ) 運籌學運籌學 熊中楷教授熊中楷教授d3- 0彩電彩電X1X2黑白黑白3024D4 - ？d4+P104 例例3 優(yōu)先權改變優(yōu)先權改變 改為黑白優(yōu)先改為黑白優(yōu)先D3d2+ 0d1- 0第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1）MinP1

13、d1- + P2 d2+ + P3 d4- + P4 d3- 運籌學運籌學 熊中楷教授熊中楷教授 靈敏度分析靈敏度分析 目標規(guī)劃問題的靈敏度分析，一般只對約束右端項的目標規(guī)劃問題的靈敏度分析，一般只對約束右端項的 變化以及優(yōu)先級系數(shù)的變化進行。變化以及優(yōu)先級系數(shù)的變化進行?！纠纠?】判斷下述說法是否正確】判斷下述說法是否正確? (a)線性規(guī)劃模型是目標規(guī)劃模型的一種特殊形式線性規(guī)劃模型是目標規(guī)劃模型的一種特殊形式; (b)正偏差變量應取正值、負偏差變量應取負值；正偏差變量應取正值、負偏差變量應取負值； (c)目標規(guī)劃模型中，若不含系統(tǒng)約束，則一定有解；目標規(guī)劃模型中，若不含系統(tǒng)約束，則一定有

14、解； (d)目標規(guī)劃的數(shù)學模型應同時包括系統(tǒng)約束和目標約束。目標規(guī)劃的數(shù)學模型應同時包括系統(tǒng)約束和目標約束。答：（答：（a）正確。模型結構完全一致，可以將線性規(guī)劃模型改寫成單正確。模型結構完全一致，可以將線性規(guī)劃模型改寫成單 一目標形式的目標規(guī)劃。一目標形式的目標規(guī)劃。 （b）錯誤。正負變量都定義取非負的值。錯誤。正負變量都定義取非負的值。 (c)正確。目標規(guī)劃的解是一種相對滿意的解。正確。目標規(guī)劃的解是一種相對滿意的解。 (d)錯誤?？梢詻]有系統(tǒng)的束。錯誤。可以沒有系統(tǒng)的束。 第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1） 運籌學運籌學 熊中楷教授熊中楷教授目標規(guī)劃圖解法：例

15、2 （p103）. 2d1d1d2d3d3d01d002d02d3d0第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1）第第2目標約束目標約束 MinP2( d2- -d2+ ) d2- =0，d2+ =0第第1目標約束目標約束 MinP1 d1+ d1+ = 0第第3目標約束目標約束 MinP3 d3- d3- = 01dd1+ = 0 運籌學運籌學 熊中楷教授熊中楷教授例例3.（p104） 1d1d2d2d3d3d3d4d4d04dMin4dMin0021dd第二目標約束第一目標約束絕對約束第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1） 運籌學運籌學 熊中楷教授

16、熊中楷教授總結本節(jié)課：目標規(guī)劃難點三個總結本節(jié)課：目標規(guī)劃難點三個難點難點1. 1.建立模型中：目標函數(shù)偏差是正或者負建立模型中：目標函數(shù)偏差是正或者負難點難點2.2.圖解方法中：方向偏差是正或者負圖解方法中：方向偏差是正或者負 難點難點3. 3.圖解方法中：判斷解圖解方法中：判斷解第四章：目標規(guī)劃及其圖解法第四章：目標規(guī)劃及其圖解法（1 1） 運籌學運籌學 熊中楷教授熊中楷教授目標規(guī)劃（目標規(guī)劃（2 2） 運籌學運籌學 熊中楷教授熊中楷教授本節(jié)課任務：本節(jié)課任務：目標規(guī)劃單純形法目目標規(guī)劃單純形法目標規(guī)劃靈敏度標規(guī)劃靈敏度第四章：目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2

17、 2）復習上節(jié)課內容復習上節(jié)課內容：目標規(guī)劃和圖解法目標規(guī)劃和圖解法上節(jié)課難點三個上節(jié)課難點三個難點難點1. 1.建立模型中：目標函數(shù)偏差是正或者負建立模型中：目標函數(shù)偏差是正或者負難點難點2.2.圖解法中：方向偏差是正或者負圖解法中：方向偏差是正或者負 難點難點3. 3.圖解法中：判斷解圖解法中：判斷解本節(jié)課要點三個本節(jié)課要點三個 要點要點1 1 初試單純形表初試單純形表要點要點2 2 檢驗數(shù)的計算檢驗數(shù)的計算要點要點3 3 檢驗數(shù)正負的判別檢驗數(shù)正負的判別 運籌學運籌學 熊中楷教授熊中楷教授P103 例例 2 目標規(guī)劃單純形法目標規(guī)劃單純形法第四章：目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)

18、劃單純形法和靈敏度（2 2）原材料嚴格限制原材料嚴格限制目標目標1：產品：產品2產量不低于產品產量不低于產品1的產量的產量目標目標2：充分利用設備臺時，不加班：充分利用設備臺時，不加班目標目標3：利潤不小于利潤不小于56萬元萬元求決策方案求決策方案 運籌學運籌學 熊中楷教授熊中楷教授Min z=p1d1+p2(d2-+d2+)+ p3d3- 2x1+ x2+ Xs =11 x1 x2 + d1- -d1+ = 0 x1 + 2x2 +d2_d2+ =10 8x1 + 10 x2 +d3_d3+ =56 xi =0, di- , d+I=0P106 例例 目標規(guī)劃單純形法目標規(guī)劃單純形法第四章：

19、目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2 2）要點要點1 1 初試單純形表初試單純形表: :有一個單位矩陣有一個單位矩陣 檢驗數(shù)檢驗數(shù) 運籌學運籌學 熊中楷教授熊中楷教授第四章：目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2 2）解目標規(guī)劃的單純形法解目標規(guī)劃的單純形法(P106)0000P1P2P2P30CBXB X1X2Xsd1-d1+d2-d2+d3-d3+B-1 b0XS2111111/10d1-1-11 -10P2d2-1轉轉21 -11010/2P3d3-8101 - 15656/10檢檢驗驗數(shù)數(shù)P11P2122P38101根據(jù)目標函數(shù)根據(jù)目標

20、函數(shù)C2 - CB B-1 P2 = 0 （0 0 P2 P3） (1 1 2 10 )T = - 2P2 - 10P3 單純形法：降成本，負中取小單純形法：降成本，負中取小相除后正中取小相除后正中取小B-1 =I直直接接找找到到單單位位矩陣轉元所在列化為單位向量轉元所在列化為單位向量 運籌學運籌學 熊中楷教授熊中楷教授第四章：目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2 2）0000P1P2P2P30CBXB X1X2Xsd1-d1+d2-d2+d3-d3+B-1 b0XS0d1-0X21/211/2-1/255/1.5P3d3-檢檢驗驗數(shù)數(shù)P11P2122P38101把這

21、把這一行所有數(shù)乘以（一行所有數(shù)乘以（2P2+10P3）加到加到檢驗數(shù)這一行：檢驗數(shù)這一行：（- P2 - 8P3）+ (1/2) （2P2+10P3）= - 3P3轉元所在列化為單位向量轉元所在列化為單位向量要點要點2 2 檢驗數(shù)的計算檢驗數(shù)的計算 運籌學運籌學 熊中楷教授熊中楷教授第四章：目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2 2）0000P1P2P2P30CBXB X1X2Xsd1-d1+d2-d2+d3-d3+B-1 b0XS0d1-0X21/211/2-1/255/1.5P3d3-檢檢驗驗數(shù)數(shù)P1P2P3-3 把這把這一行所有數(shù)乘以（一行所有數(shù)乘以（2P2+10

22、P3）加到加到檢驗數(shù)這一行：檢驗數(shù)這一行：（- P2 - 8P3）+ (1/2) （2P2+10P3）= - 3P3 運籌學運籌學 熊中楷教授熊中楷教授第四章：目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2 2）解目標規(guī)劃的單純形法解目標規(guī)劃的單純形法 (P105)0000P1P2P2P30CBXBX1X2Xsd1-d1+d2-d2+d3-d3+B-1 b0XS3/21-1/21/266/1.50d1-3/21 -11/2-1/250X21/211/2-1/255/1.5P3d3-轉轉3-551 - 166/3檢檢驗驗數(shù)數(shù)P11P211P335 51C7 CB B-1 P7 =

23、 P2 （0 0 0 P3） (1/2 1/2 1/2 5 )T = P2 5P3單純形法：降成本，負中取小單純形法：降成本，負中取小 ( 注：注：d2+ 的的檢驗數(shù)為正檢驗數(shù)為正 )相除后正中取小相除后正中取小CB轉元所在列化為單位向量轉元所在列化為單位向量 運籌學運籌學 熊中楷教授熊中楷教授解目標規(guī)劃的單純形法解目標規(guī)劃的單純形法 (P107)0000P1P2P2P30CBXBX1X2Xsd1-d1+d2-d2+d3-d3+B-1 b0Xs12-2-1/21/2 30d1-1-13-3-1/21/2 20X214/3-4/3-1/61/64P3X11-5/35/31/3-1/32檢檢驗驗數(shù)

24、數(shù)P11P211P310非基變量檢驗數(shù)為零非基變量檢驗數(shù)為零 對應無數(shù)最優(yōu)解對應無數(shù)最優(yōu)解單純形法：最優(yōu)解：單純形法：最優(yōu)解： X1 2 ， X24， Xs 3，d1- 2第四章：目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2 2） 運籌學運籌學 熊中楷教授熊中楷教授第四章：目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2 2）解目標規(guī)劃的單純形法解目標規(guī)劃的單純形法 (P107)0000P1P2P2P30CBX1X2Xsd1-d1+d2-d2+d3-d3+B-1 b0Xs1-1-1110d3+1 26-6-1140X21-1/31/3-1/310/3P3X11-

25、2/31/3-1/3 10/3檢檢驗驗數(shù)數(shù)P101P211P31單純形法：最優(yōu)解單純形法：最優(yōu)解X1 10/3 ， X210/3，Xs 1，d3+ 4非基變量檢驗數(shù)為零非基變量檢驗數(shù)為零 對應無數(shù)最優(yōu)解對應無數(shù)最優(yōu)解d1-d3+對對換換 運籌學運籌學 熊中楷教授熊中楷教授解目標規(guī)劃的單純形法(P105)0NXbB100bB1NX0321PPP9 5 38 3 21 0 0NBCCBNN1bB1NX0321PPP9 5 38 3 21 0 0已達到最優(yōu)解0第四章：目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2 2）?bB10bB10檢驗數(shù)檢驗數(shù) 2P2 -3 P3為正為正 檢驗數(shù)

26、檢驗數(shù) -3P2 + 5 P3為負為負檢驗數(shù)檢驗數(shù) P1 - 8P2 -9 P3為正為正 運籌學運籌學 熊中楷教授熊中楷教授要點要點3 3 檢驗數(shù)正負的判別檢驗數(shù)正負的判別檢驗數(shù)中檢驗數(shù)中優(yōu)先權大的系數(shù)符號為準優(yōu)先權大的系數(shù)符號為準 檢驗數(shù)檢驗數(shù) -3P2 + 5 P3為負為負 檢驗數(shù)檢驗數(shù) 2P2 -3 P3為正為正 檢驗數(shù)檢驗數(shù) P1 - 8P2 -9 P3為正為正第四章：目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2 2） 運籌學運籌學 熊中楷教授熊中楷教授靈敏度分析-優(yōu)先級改變(107)：優(yōu)先彩電 優(yōu)先黑白NX01bB321PPPNBCCBNN1第四章：目標規(guī)劃單純形法

27、和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2 2）優(yōu)先級改變優(yōu)先級改變 目標函數(shù)改變，目標函數(shù)改變， C改變改變 CB改變，改變， 單純形表中單純形表中 檢驗數(shù)檢驗數(shù)CN CB B-1 N改變改變優(yōu)先級改變優(yōu)先級改變單純形表中單純形表中 檢驗數(shù)改變檢驗數(shù)改變 運籌學運籌學 熊中楷教授熊中楷教授靈敏度分析靈敏度分析-優(yōu)先級改變優(yōu)先級改變(107)：Min z=p1 (2d1-+3d1+) +p2 d3- + p3d4 優(yōu)先級優(yōu)先級改變?yōu)楦淖優(yōu)镸in z=p1 d3- + p2 (2d1+3d2+) + p3d4 x1+ x2+ d1- -d1+ =10 x1 + d2- -d2+ = 4 5x

28、1 + 3x2 +d3_d3+ =56 x1 + x2 +d4_d4+ =12 xi =0, di- , d+I=0 系數(shù)矩陣中有一個矩陣單位系數(shù)矩陣中有一個矩陣單位優(yōu)先級改變優(yōu)先級改變 目標函數(shù)改變目標函數(shù)改變 C改變改變 CB改變，改變， 單純形表中單純形表中 檢驗數(shù)檢驗數(shù)CN CB B-1 N改變改變第四章：目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2 2） 運籌學運籌學 熊中楷教授熊中楷教授第四章：目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2 2）0002P203P2P100P3CBX1X2d1-d1+d2-d2+d3-d3+d4-d4+0X2111

29、-1160X110 1114P1d3-33-2211180d4-轉轉1 112檢檢驗驗數(shù)數(shù)P11322P2231P31C4 CB B-1 P4 = 2P2 （0 0 P1 0 ） (1 0 3 1 )T = 3P1 2P2單純形法：降成本，負中取小單純形法：降成本，負中取小 ( 注：注：d1+ 的的檢驗數(shù)負檢驗數(shù)負)相除后正中取小相除后正中取小轉元所在列化為單位向量轉元所在列化為單位向量 運籌學運籌學 熊中楷教授熊中楷教授0002P203P2P100P3CBX1X2d1-d1+d2-d2+d3-d3+d4-d4+0X211-5/35/31/3-1/3120X11 114P1d4+-2/32/3

30、1/3-1/3-140d1+-11-2/32/31/316檢檢驗驗數(shù)數(shù)P11P223P3 2/3-2/3-2/31/3單純形法：最優(yōu)解：單純形法：最優(yōu)解： X1 4 ， X212第四章：目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2 2）轉元所在列化為單位向量轉元所在列化為單位向量 運籌學運籌學 熊中楷教授熊中楷教授總結本節(jié)課任務：總結本節(jié)課任務：目標規(guī)劃單純形法目目標規(guī)劃單純形法目標規(guī)劃靈敏度標規(guī)劃靈敏度第四章：目標規(guī)劃單純形法和靈敏度（第四章：目標規(guī)劃單純形法和靈敏度（2 2）總結本節(jié)課要點三個總結本節(jié)課要點三個 1 1 初試單純形表初試單純形表2 2 檢驗數(shù)的計算檢驗數(shù)的

31、計算3 3 檢驗數(shù)正負的判別檢驗數(shù)正負的判別 運籌學運籌學 熊中楷教授熊中楷教授第四章：目標規(guī)劃應用（第四章：目標規(guī)劃應用（3 3）目標規(guī)劃應用舉例目標規(guī)劃應用舉例 (P109) 例例6.調工資方案目標調工資方案目標1 不超過年工資總額不超過年工資總額60000元元2 每級人數(shù)不超過定編人數(shù)每級人數(shù)不超過定編人數(shù)3二三級升級面盡可能達到現(xiàn)有人數(shù)的二三級升級面盡可能達到現(xiàn)有人數(shù)的2044 三級不足人數(shù)可以錄取新工人，一級有三級不足人數(shù)可以錄取新工人，一級有10要退要退休休年年工資工資現(xiàn)有人數(shù)現(xiàn)有人數(shù)定編人數(shù)定編人數(shù)一級一級20001012二級二級15001215三級三級10001515合計合計3

32、742 運籌學運籌學 熊中楷教授熊中楷教授第四章：目標規(guī)劃應用（第四章：目標規(guī)劃應用（3 3）解：設解：設 X1，X2，X3表示提升到一二級和錄取到三級的新表示提升到一二級和錄取到三級的新 工人人數(shù)工人人數(shù)第第1目標：目標：不超過年工資總額不超過年工資總額60000元元 提問題：同學說明下式提問題：同學說明下式 Min P1 d1 2000（10100.1+ X1 ） 1500(12- X1 X2 ) 1000 (15- X2 X3 ) + d1- d1 60000d1- 不足工資總額的數(shù)量不足工資總額的數(shù)量d1 超過工資總額的數(shù)量超過工資總額的數(shù)量 運籌學運籌學 熊中楷教授熊中楷教授第四章：

33、目標規(guī)劃應用（第四章：目標規(guī)劃應用（3 3）第第2目標：目標：每級人數(shù)不超過定編人數(shù)每級人數(shù)不超過定編人數(shù) 提問題：同學說明下式提問題：同學說明下式 Min P2 (d2 )+ (d3 )+(d4 )10（10.1） X1 + d2- d2 1212 - X1 X2 + d3- d3 1515 - X2 X3 + d4- d4 1516 d2 一級超過定編人數(shù)一級超過定編人數(shù) 的數(shù)量的數(shù)量17 D2- 一級一級不足不足定編人數(shù)定編人數(shù) 的數(shù)量的數(shù)量 運籌學運籌學 熊中楷教授熊中楷教授第四章：目標規(guī)劃應用（第四章：目標規(guī)劃應用（3 3）第第3目標：目標：二三級升級面盡可能達到現(xiàn)有人數(shù)的二三級升級

34、面盡可能達到現(xiàn)有人數(shù)的20提問題：同學說明下式提問題：同學說明下式 Min P3 (d5 )+ (d6 ) X1 + d5- d5 120. 2 X2 + d6- d6 15 0. 2 d5- 二級升級面不足規(guī)定的數(shù)量二級升級面不足規(guī)定的數(shù)量 d5 二級升級面超過規(guī)定的數(shù)量二級升級面超過規(guī)定的數(shù)量答案答案 P110 注意偏差變量的經(jīng)濟含意注意偏差變量的經(jīng)濟含意 運籌學運籌學 熊中楷教授熊中楷教授例6.調工資方案討論：幾種理解各級別級別的工資額）級別的人數(shù)）（工資總額ii）級人數(shù)級上升到（級現(xiàn)有人數(shù)人數(shù)級）級上升到由（級別的人數(shù)11iiiiii)(653 ddMinP)(653 ddMinP)(

35、66553ddddMinP第四章：目標規(guī)劃應用（第四章：目標規(guī)劃應用（3 3） 運籌學運籌學 熊中楷教授熊中楷教授1） B4 是重點保證單位，必須滿足全部需求是重點保證單位，必須滿足全部需求2） A3向向B1提供產量不少于提供產量不少于1003） 每個銷地的供應量不少于需求的每個銷地的供應量不少于需求的804） 總運費不超過最小運費的總運費不超過最小運費的1105） 因為路問題，因為路問題，A2盡量不運到盡量不運到B46） B1， B3的供應率要相同的供應率要相同7） 總運輸費用盡量少總運輸費用盡量少第四章：目標規(guī)劃應用（第四章：目標規(guī)劃應用（3 3）(p110例例7) 目標規(guī)劃應用案例目標規(guī)

36、劃應用案例 運輸問題運輸問題 一個物流企業(yè)的老板正在考慮如下問題：一個物流企業(yè)的老板正在考慮如下問題： 有三個產地有三個產地A1,A2,A3給四個銷地給四個銷地B1,B2,B3,B4供應某種產品，已經(jīng)知道供應某種產品，已經(jīng)知道需求量和運輸價格，需求量和運輸價格， 要考慮以下要考慮以下7個目標：個目標： 運籌學運籌學 熊中楷教授熊中楷教授 銷地銷地B1銷地銷地B2銷地銷地B3銷地銷地B4產產 量量產地產地A15元元/公斤公斤 2元元/公斤公斤6元元/公斤公斤7元元/公斤公斤300產地產地A23元元/公斤公斤5元元/公斤公斤4元元/公斤公斤6元元/公斤公斤200產地產地A34元元/公斤公斤5元元/

37、公斤公斤2元元/公斤公斤3元元/公斤公斤400銷銷 量量200100450250 第四章：目標規(guī)劃應用（第四章：目標規(guī)劃應用（3 3）已知已知 運籌學運籌學 熊中楷教授熊中楷教授 銷地銷地B1銷地銷地B2銷地銷地B3銷地銷地B4產產 量量產地產地A1200100300產地產地A20200200產地產地A3虛虛產地產地400100銷銷 量量200100450250 第四章：目標規(guī)劃應用（第四章：目標規(guī)劃應用（3 3）首先把首先把 產銷不平衡化為產銷平衡，產銷不平衡化為產銷平衡， 求解如下：求解如下：250150100 運籌學運籌學 熊中楷教授熊中楷教授 .目標規(guī)劃應用 運輸問題運輸問題（P110 例例7） 本例中本例中 供供需需 供供 + 虛產地虛產地 = 需需 七個要求目標規(guī)劃表達如下：七個要求目標規(guī)劃表達如下：第第1目標：目標：B4是重點單位，必須滿足是重點單位，必須滿足 提問題：同學說明下式提問題：同學說明下式第第2目標：目標：A3向向B1提供產量不少于提供產量不少于100 提問題：同學說明下式提問題：同學說明下式 Min P2 d5- X31 d51- d51 1