第1章線性規(guī)劃(1-2).ppt

第一章線性規(guī)劃 線性規(guī)劃廣泛應用于經濟領域 包括生產計劃 廣告媒體選擇 投資決策 資本預算 人事安排 產品配比問題等等 線性規(guī)劃是進行管理決策的最有效的方法之一 問題導入 生產優(yōu)化 產品組合問題 問題背景和風家具有限公司生產高質量特色系列的茶幾和餐桌 由于質量過硬 造型優(yōu)美時尚 部分產品不僅暢銷國內 還遠銷海外 為公司創(chuàng)造了不菲收益 最近 公司的制造總裁李文碰到了一件棘手的問題 總公司旗下有三個分廠 由于某些產品銷售量的下降 高層管理部門決定調整公司的產品線 問題導入 生產優(yōu)化 產品組合問題 如果征得管理部門的同意 不盈利的產品要停止生產并撤出生產能力來生產研發(fā)部剛開發(fā)的兩個新產品 綠色時尚系列茶幾A和餐桌B 現(xiàn)在管理部門要考慮下列兩個問題 1 公司是否應該生產這兩個新產品 2 如果生產 兩個新產品的產品生產組合如何 每周分別生產多少數(shù)量 問題導入 生產優(yōu)化 產品組合問題 為解決上述問題 我們首先要收集研究所需的信息 每家工廠的生產能力 生產每一產品各需要每家工廠多少生產能力 每一產品的單位利潤 表1 1總結了收集到的數(shù)據(jù) 兩種新產品的有關數(shù)據(jù) 問題導入 生產優(yōu)化 產品組合問題 由上述分析可建立本問題的線性規(guī)劃模型下 o b max300X 500Y 利潤最大化 s t X 4 工廠1的工時約束 2Y 12 工廠2的工時約束 3X 2Y 18 工廠3的工時約束 X Y 0 非負約束 第一節(jié)線性規(guī)劃問題及其數(shù)學模型 線性規(guī)劃是運用數(shù)學模型 對人力 設備 材料 資金等進行系統(tǒng)和定量的分析 使生產力得到最為合理的組織 以獲得最佳的經濟效益 1 1線性規(guī)劃的模型結構 規(guī)劃問題的數(shù)學模型由三個要素組成 1 變量 或稱決策變量 是問題中要確定的未知量 它用以表明規(guī)劃中的用數(shù)量表示的方案 措施 可由決策者決定 2 目標函數(shù) 它是指對問題所追求的目標的數(shù)學描述 按優(yōu)化目標分別在這個函數(shù)前加上max或min 3 約束條件 指決策變量取值時受到的各種資源條件的限制 通常表達為含決策變量的線性等式或不等式 1 1線性規(guī)劃的模型結構 實際問題中線性的含義 一是嚴格的比例性 生產某產品對資源的消耗量和可獲取的利潤 同其生產數(shù)量嚴格成比例 二是可疊加性 如生產多種產品時 可獲取的總利潤是各項產品的利潤之和 對某項資源的消耗量應等于各產品對該項資源的消耗量的和 在實際處理不符合條件的問題時 為方便可將其看作近似滿足線性條件 線性規(guī)劃的數(shù)學模型的一般形式為 目標函數(shù)max min z c1x1 c2x2 cnxn滿足約束條件 a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 1 1線性規(guī)劃的模型結構 線性規(guī)劃模型的矩陣形式 目標函數(shù)max min Z CX約束條件AX b其中 C c1 c2 cn X x1 x2 xn Tb b1 b2 bm Ta11 a12 a1nA a21 a22 a2n am1 am2 amn 1 2線性規(guī)劃問題求解的幾種可能結局 線性規(guī)劃模型解的概念1 解 給每個決策變量任意賦一個值就得到該模型的解 因此模型有無數(shù)個解 例如X 20 Y 40 是該模型的解 而X 30 Y 90也是該模型的解 等等還有很多 線性規(guī)劃模型解的概念2 可行解 是指滿足所有約束條件的解 也就是決策變量的值滿足一組等式或不等式的值 需要求解 3 可行域 是指所有可行解的集合 4 最優(yōu)解 可行域中使目標函數(shù)達到最優(yōu)的解 最優(yōu)解滿足約束條件同時又使得目標函數(shù)值達到優(yōu) 1 2線性規(guī)劃問題求解的幾種可能結局 線性規(guī)劃問題的解可能出現(xiàn)下列情況 1 有惟一解這里 線性規(guī)劃問題有惟一解是指該規(guī)劃問題有且僅有一個既在可行域內 又使目標值達到最優(yōu)的解 即只有一個最優(yōu)解 1 2線性規(guī)劃問題求解的幾種可能結局 線性規(guī)劃問題的解可能出現(xiàn)下列情況 2 有無窮多解這里 線性規(guī)劃問題有無窮多解是指該規(guī)劃問題無窮多個既在可行域內 又使目標值達到最優(yōu)的解 即有無窮多個最優(yōu)解 1 2線性規(guī)劃問題求解的幾種可能結局 線性規(guī)劃問題的解可能出現(xiàn)下列情況 3 無解這里 線性規(guī)劃問題無解是指該規(guī)劃問題的約束條件不能同時滿足 沒有可行域 不存在可行解 也就不存在最優(yōu)解 1 2線性規(guī)劃問題求解的幾種可能結局 線性規(guī)劃問題的解可能出現(xiàn)下列情況 4 可行域無界這里 線性規(guī)劃問題的可行域無界是指最大化問題的目標函數(shù)值可以無限增大 或最小化問題的目標函數(shù)值可以無限減小 1 2線性規(guī)劃問題求解的幾種可能結局 1 3應用Excel求解線性規(guī)劃問題 圖解法單純形法Excel的 規(guī)劃求解 1 3應用Excel求解線性規(guī)劃問題 首先 根據(jù)問題建立電子表格模型具體步驟如下 1 收集問題的數(shù)據(jù) 2 在電子表格的數(shù)據(jù)單元格中輸入數(shù)據(jù) 3 確定對活動水平需要作出的決策并且指定可變單元顯示這些決策 4 確定對這些決策的約束條件并引入需具體化這些約束條件的輸出單元格 5 選擇要輸入目標單元格的完全績效測度 6 使用SUMPRODUCT函數(shù)為每個輸出單元格 包括目標單元格 輸入合適的值 1 3應用Excel求解線性規(guī)劃問題 電子表格模型 1 3應用Excel求解線性規(guī)劃問題 然后 建立了起電子表格模型 就可以利用Excel中的工具Solver 規(guī)劃求解 求解 1 3應用Excel求解線性規(guī)劃問題 規(guī)劃求解的選項對話框 1 3應用Excel求解線性規(guī)劃問題 最后 保存求解結果 第二節(jié)線性規(guī)劃的靈敏度分析線性規(guī)劃模型的一般形式為 目標函數(shù)max min z c1x1 c2x2 cnxn滿足約束條件 a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 通常 假定系數(shù)aij bi cj都是常數(shù) 而實際上這些系數(shù)往往是估計值和預測值 如果市場條件一變 cj值就會變化 工藝條件發(fā)生變化會改變aij的值 同樣 由于bi是根據(jù)資源投入后的經濟效果決定的一種決策選擇 靈敏度分析就是對系統(tǒng)或事物因周圍條件變化顯示出來的敏感性程度的分析 第二節(jié)線性規(guī)劃的靈敏度分析 生產優(yōu)化問題 它的線性規(guī)劃模型為 o b max300X 500Y 利潤最大化 s t X 4 工廠1的工時約束 2Y 12 工廠2的工時約束 3X 2Y 18 工廠3的工時約束 X Y 0 非負約束 提出這樣兩個問題 當這些系數(shù)有一個或幾個發(fā)生變化時 已求得的線性規(guī)劃問題的最優(yōu)解 目標值會有什么變化 或者這些系數(shù)在什么范圍內變化時 線性規(guī)劃線性規(guī)劃問題的最優(yōu)解 目標值不變 2 1一個目標函數(shù)系數(shù)變動 本節(jié)討論在假定只有一個系數(shù)cj改變 其他系數(shù)均保持不變的情況下 目標函數(shù)系數(shù)變動對最優(yōu)解的影響 2 1一個目標函數(shù)系數(shù)變動 第一種方法可以借助電子表格互動地展開靈敏度分析 當模型參數(shù)發(fā)生改變時 只要改變電子表格模型中相應的參數(shù) 再重新運行Excel 規(guī)劃求解 功能 就可以看出改變參數(shù)對最優(yōu)解的影響 固然能達到靈敏度分析的目的 但需要一個一個地嘗試 效率低下 2 1一個目標函數(shù)系數(shù)變動 第二種方法可以利用Excel中的 規(guī)劃求解 功能可以直接到 敏感性分析 利用該報告可以很方便地進行靈敏度分析 在Excel中 敏感性分析 報告的獲得敏感性報告的內容 由兩部分組成 位于報告上部的 可變單元格 部分反映了目標函數(shù)中的系數(shù)變化對最優(yōu)解產生的影響 位于報告下部的 約束 部分反映了約束條件右端值變化目標值產生的影響 敏感性報告 敏感性報告上部的表格反映目標函數(shù)中系數(shù)的變化對最優(yōu)解的影響 表格中的前三列是該問題中決策變量的信息 單元格 是指決策變量所在單元格地址 名字 是這些決策變量的名稱 終值 是決策變量的終值 即最優(yōu)解 敏感性報告的第一部分內容 第四列是 遞減成本 它的絕對值表示目標函數(shù)中決策變量的系數(shù)必須改進多少 才能得到該決策變量的正數(shù)解 改進 在最大化問題中是指增加 在最小化問題中是指減少 第五列 目標式系數(shù) 是指目標函數(shù)中的系數(shù) 第六列與第七列分別是 允許的增量 和 允許的減量 它們表示目標函數(shù)中的系數(shù)在允許的增量和減量范圍內變化時 最優(yōu)解不變 2 2目標函數(shù)系數(shù)同時變動的影響 在目標函數(shù)中只有一個系數(shù)變動的情況下 通過靈敏度分析報告中的數(shù)據(jù)找到該變動系數(shù)的允許變化范圍 在分析多個系數(shù)同時變動的情況時 也使用同樣的這些數(shù)據(jù) 即每個系數(shù)的允許增加值和減少值 目標函數(shù)系數(shù)同時變動的使用百分之百法則進行判斷 2 2目標函數(shù)系數(shù)同時變動的影響 目標函數(shù)系數(shù)同時變動的百分之百法則的具體含義為 如果目標函數(shù)的系數(shù)同時變動 計算出每一系數(shù)變動量占該系數(shù)允許變化范圍允許變動量 允許的增量或允許的減量 的百分比 而后 將各個系數(shù)的變動百分比相加 如果所得的和不超過100 最優(yōu)解不會改變 如果超過100 則不能確定最優(yōu)解是否改變 只能通過重新進行規(guī)劃求解來判斷了 2 2目標函數(shù)系數(shù)同時變動的影響 茶幾的單位利潤P1從原來的300美元增加到450美元 而餐桌的單位利潤P2從原來的500美元下降到400美元 運用百分百法則 計算如下 P1 300美元 450美元占允許增加量的百分比 100 450 300 450 100 33 34 P2 500美元 400美元占允許增加量的百分比 100 500 400 300 100 33 34 總和 66 68 因為變動百分比之和不超過100 所以可以確定最初的 茶幾 餐桌 2 6 的最優(yōu)解沒有改變 2 2目標函數(shù)系數(shù)同時變動的影響 P1 300美元 600美元占允許增加量的百分比 100 600 300 450 100 66 67 P2 500美元 400美元占允許增加量的百分比 100 500 400 300 100 66 67 總和 133 33 通過規(guī)劃求解得到 最優(yōu)解已經變成了 4 3 2 2目標函數(shù)系數(shù)同時變動的影響 P1 300美元 525美元占允許增加量的百分比 100 525 300 450 100 50 P2 500美元 350美元占允許增加量的百分比 100 500 350 300 100 50 總和 100 變動百分比之和剛好等于100 但因沒有超過100 所以 茶幾 餐桌 2 6 還是最優(yōu)解 2 3單個約束條件變化的影響 在例1 1中 每個工廠的可用工時是約束條件的右端值 工廠1的可用工時是4 但在規(guī)劃求解得出的最優(yōu)方案中 1只用了2小時 因此如果小范圍地改變車間1的工時 不會改變最優(yōu)目標值和最優(yōu)解 但對于工廠2和工廠3來說 情況有所不同了 需要通過靈敏度分析 來分析一下改變這兩個工廠的可用工時對目標值及最優(yōu)解的影響 2 3單個約束條件變化的影響 如果管理者讓工廠2的可用工時從12小時增加到13小時 修改電子表格模型中相應的參數(shù)后 重新進行規(guī)劃求解 此時總利潤變?yōu)?750元 增加了150元 由于總利潤增加了 而目標函數(shù)系數(shù)不變 所以最優(yōu)解一定會發(fā)生改變 2 3單個約束條件變化的影響 在電子表格模型中把工廠2的可得時間繼續(xù)上調 總利潤會繼續(xù)增長 直到工廠2可得時間增加到18小時 此時再增加時間不會帶來利潤的增長 這是因為工廠3的18小時可得時間只能每周生產9個餐桌 所以工廠2相應的最多只會使用18小時的工時 因此 當其他工廠的可得時間不發(fā)生改變時 18小時是工廠2可得時間的最大值 2 3單個約束條件變化的影響 約束右端值往往體現(xiàn)了管理層的決策 在建模決策后 管理者想要知道改變這些決策是否會提高最終受益 影子價格分析就可為管理者提供這方面的信息 在給定線性規(guī)劃模型的最優(yōu)解和相應的目標函數(shù)值的條件下 影子價格是指約束右端值增加 或減少 一個單位 目標值增加 或減少 的數(shù)量 敏感性報告提供了每個約束的影子價格 2 3單個約束條件變化的影響 敏感性報告下部的表格反映約束條件右邊變化對目標值的影響 表格中的前三列是關于約束條件左邊的信息 單元格 是指約束條件左邊所在單元格地址 名字 是約束條件左邊的名稱 終值 是約束條件左邊的終值 即最優(yōu)解 第四列是 陰影價格 即影子價格 影子價格是指約束條件右邊增加 或減少 一個單位 目標值增加 或減少 的數(shù)量 第五列為 約束限制值 是指約束條件右邊的值 是已知條件 第六列與第七列分別是 允許的增量 和 允許的減量 它們表示約束條件右邊在允許的增量和減量范圍內變化時 影子價格不變 2 4約束右端值同時變動的情形 車間2 12 13總利潤變化量 影子價格 150元車間3 18 17總利潤變化量 影子價格 100元總利潤是否增加150 100 50 元 不能確定兩個約束右端值同時變動時 原先的影子價格是否依然有效 怎么處理呢 2 4約束右端值同時變動的情形 多個約束右端值同時變動的情形進行分析的方法 百分之百法則百分之百法則的具體含義為 如果約束右端值同時變動 計算每一變動占允許變動量 允許的增量或允許的減量 的百分比 如果所有的百分比之和不超過100 那么 影子價格依然有效 否則只能通過重新進行規(guī)劃求解來判斷了 2 4約束右端值同時變動的情形 利用該百分之百法則再分析上述問題 計算如下 工廠2 12 13 占允許增加量的百分比 13 12 6 100 16 67 工廠3 18 17 占允許減少量的百分比 18 17 6 100 16 67 總和 33 33 小于100 用影子價格來預測這些變動的影響是有效的 2 4約束右端值同時變動的情形 工廠2 12 15 占允許增加量的百分比 15 12 6 100 50 工廠3 18 15 占允許減少量的百分比 18 15 6 100 50 總和 100 所以影子價格仍然有效 但這一變動幅度是最大的 一旦大于這一幅