【正文】 1 x1 + c2 x2 + … + c n xn 約束條件： . 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ù)： Max z = c1 x1 + c2 x2 + … + c n xn 約束條件： . 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 13 167。 解的性質(zhì)： 1） 線性規(guī)劃的最優(yōu)解如果存在，則必定有一個頂點（極點）是最優(yōu)解； 2） 有的線性規(guī)劃問題存在無窮多個最優(yōu)解的情況； 3） 有的線性規(guī)劃問題存在無有限最優(yōu)解的情況，也稱無解； 4） 有的線性規(guī)劃問題存在無可行解的情況 。 3圖解法的靈敏度分析 ? 靈敏度分析： 建立數(shù)學模型和求得最優(yōu)解后，研究線性規(guī)劃的一個或多個參數(shù)（系數(shù)） ci , aij , bj 變化時，對最優(yōu)解產(chǎn)生的影響。 ? 一般情況： z = c1 x1 + c2 x2 寫成斜截式 x2 = (c1 / c2 ) x1 + z / c2 目標函數(shù)等值線的斜率為 (c1 / c2 ) 當 1 ? (c1 / c2 ) ? 0 （ *） 時，原最優(yōu)解仍是最優(yōu)解 ? 假設產(chǎn)品乙的利潤 100元不變，即 c2 = 100，代到式 （ *） 并整理得 0 ? c1 ? 100 ? 假設產(chǎn)品甲的利潤 50 元不變，即 c1 = 50 ，代到式 （ *） 并整理得 50 ? c2 ? + ? ? 假若產(chǎn)品甲、乙的利潤均改變，則可直接用式 （ *） 來判斷。 16 約束條件中右邊系數(shù) bj 的靈敏度分析 ? 當約束條件中右邊系數(shù) bj 變化時，線性規(guī)劃的可行域發(fā)生變化，可能引起最優(yōu)解的變化。 變化后的總利潤 變化前的總利潤 = 增加的利潤 (50*60+100*250) (50*50+100*250) = 500 ， 500 / 10 = 50 元 說明在一定范圍內(nèi)每增加（減少） 1個臺時的設備能力就可增加（減少） 50元利潤，稱為該約束條件的對偶價格。 此變化對總利潤無影響，該約束條件的對偶價格為 0 。 ? 在一定范圍內(nèi)，當約束條件右邊常數(shù)增加 1個單位時 1）若約束條件的對偶價格大于 0，則其最優(yōu)目標函數(shù)值得到改善（變好）； 2）若約束條件的對偶價格小于 0，則其最優(yōu)目標函數(shù)值受到影響（變壞）； 3）若約束條件的對偶價格等于 0，則其最優(yōu)目標函數(shù)值不變。 退出系統(tǒng)的方法可以在主菜單中選退出項，也可按 Ctrl+Break鍵直接退出。具體方法是：在非全屏界面下點擊菜單的“屬性”選項，再選擇“窗口”選項，然后選中其中的“窗口”項，并取消“啟動時恢復設置”項，這樣就可保證每次運行軟件時以非全屏方式顯示。如（ x1+x2x3=0，不能輸為 x2x3+x1=0； x1x2+x3=0，不能輸為x1+x3=x2） 輸入的約束中不包括 =或 =，而是用 或 代替，這不會影響求解。 18 第三章 線性規(guī)劃問題的計算機求解 (2) ? 結果考察：（演示例 1） 當目標函數(shù)的系數(shù) ci 單一變化時，只要不超過其上、下限，最優(yōu)解不變； 當約束條件中右邊系數(shù) bj 變化時，當其不超過上、下限，對偶價格不變（最優(yōu)解仍是原來幾個線性方程的解）； 當有多個系數(shù)變化時，需要進一步討論。 b1 變?yōu)? 315 , b3 變?yōu)? 240, 則 (315 50) / 25 + (250 240 ) / 50 = 80%，故對偶價格不變（最優(yōu)解仍是原來幾個線性方程的解）。這種情況下，只有重新求解。 目標函數(shù)： Min x1 + x2 + x3 + x4 + x5 + x6 約束條件： . x1 + x6 ≥ 60 x1 + x2 ≥ 70 x2 + x3 ≥ 60 x3 + x4 ≥ 50 x4 + x5 ≥ 20 x5 + x6 ≥ 30 x1,x2,x3,x4,x5,x6 ≥ 0 21 第四章 線性規(guī)劃在工商管理中的應用 (2) 一、人力資源分配的問題 例 2．福安商場是個中型的百貨商場，它 對售貨員的需求經(jīng)過統(tǒng)計分析如右表： 為了保證售貨人員充分休息，售貨人員 每周工作 5天，休息兩天，并要求休息的兩 天是連續(xù)的。 目標函數(shù)： Min x1 + x2 + x3 + x4 + x5 + x6 + x7 約束條件： . x1 + x2 + x3 + x4 + x5 ≥ 28 x2 + x3 + x4 + x5 + x6 ≥ 15 x3 + x4 + x5 + x6 + x7 ≥ 24 x4 + x5 + x6 + x7 + x1 ≥ 25 x5 + x6 + x7 + x1 + x2 ≥ 19 x6 + x7 + x1 + x2 + x3 ≥ 31 x7 + x1 + x2 + x3 + x4 ≥ 28 x1,x2,x3,x4,x5,x6,x7 ≥ 0 22 第四章 線性規(guī)劃在工商管理中的應用 (3) 二、生產(chǎn)計劃的問題 例 3．明興公司生產(chǎn)甲、乙、 丙三種產(chǎn)品，都需要經(jīng)過鑄造、 機加工和裝配三個車間。數(shù)據(jù)如 右表。 求 xi 的利潤：利潤 = 售價 各成本之和 可得到 xi （ i = 1,2,3,4,5） 的利潤分別為 1 1 9 元。 目標函數(shù)： Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5 約束條件： . 5x1 + 10x2 + 7x3 ≤ 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 ≤ 12020 3x1 + 2x2 + 2x3 + 3x4 + 2x5 ≤ 10000 x1,x2,x3,x4,x5 ≥ 0 23 第四章 線性規(guī)劃在工商管理中的應用 (4) 二、生產(chǎn)計劃的問題 例 4．永久機械廠生產(chǎn) Ⅰ 、 Ⅱ 、 Ⅲ 三種產(chǎn)品，均要經(jīng)過 A、 B兩道工 序加工。 Ⅰ 可在 A、 B的任何規(guī)格的設備上加工； Ⅱ 可在 任意規(guī)格的 A設備上加工，但對 B工序， 只能在 B1設備上加工； Ⅲ 只能在 A2與 B2設備上加工；數(shù)據(jù)如右上表。 利潤 = [（銷售單價 原料單價） * 產(chǎn)品件數(shù) ]之和 （每臺時的設備費用 *設備實際使用的總臺時數(shù)）之和。 j = 1,2。已知原料每根長 m，問：應如何下料，可使所用原料最??？ 解： 設計下列 5 種下料方案 方案 1 方案 2 方案 3 方案 4 方案 5 方案 6 方案 7 方案 82. 9 m 1 2 0 1 0 1 0 02. 1 m 0 0 2 2 1 1 3 01. 5 m 3 1 2 0 3 1 0 4合計 7. 4 7. 3 7. 2 7. 1 6. 6 6. 5 6. 3 6. 0剩余料頭 0 0. 1 0. 2 0. 3 0. 8 0. 9 1. 1 1 . 4 設 x1,x2,x3,x4,x5 分別為上面前 5 種方案下料的原材料根數(shù)。 目標函數(shù)： Min x1 + x2 + x3 + x4 + x5 約束條件： . x1 + 2x2 + x4 ≥ 100 2x3 + 2x4 + x5 ≥ 100 3x1 + x2 + 2x3 + 3x5 ≥ 100 x1,x2,x3,x4,x5 ≥ 0 25 第四章 線性規(guī)劃在工商管理中的應用 (6) 四、配料問題 例 6．某工廠要用三種原料 3混合調(diào)配出三種不同規(guī)格的 產(chǎn)品甲、乙、丙，數(shù)據(jù)如