物流系統(tǒng)優(yōu)化線性規(guī)劃.ppt

1、線 性 規(guī) 劃 模 型,“線性規(guī)劃能做什么？,線性規(guī)劃的概念和研究的問題 線性規(guī)劃是在一定的限制條件下使其規(guī)劃問題的某個(gè)整體指標(biāo)達(dá)到最優(yōu)的方法。 線性規(guī)劃在財(cái)貿(mào)金融、工農(nóng)業(yè)生產(chǎn)、交通運(yùn)輸?shù)阮I(lǐng)域的管理決策分析中均可幫助管理人員解決具體的實(shí)際問題。 用線性規(guī)劃解決的比較簡單的問題： 1、產(chǎn)品生產(chǎn)的組合安排 2、原料搭配及下料 3、物資運(yùn)輸 4、投資問題等,線性規(guī)劃問題基本理論及方法,例：某工廠生產(chǎn)兩種新產(chǎn)品：門和窗。經(jīng)測算，每生產(chǎn)一扇門需要在車間1加工1小時(shí)、在車間3加工3小時(shí)；每生產(chǎn)一扇窗需要在車間2和車間3各加工2小時(shí)。而車間1每周可用于生產(chǎn)這兩種新產(chǎn)品的時(shí)間為4小時(shí)、車間2為12小時(shí)、車間3

2、為18小時(shí)。已知每扇門的利潤為300元，每扇窗的利潤為500元。根據(jù)市場調(diào)查得到的這兩種新產(chǎn)品的市場需求狀況可以確定，按當(dāng)前的定價(jià)可確保所有的新產(chǎn)品均能銷售出去。,線性規(guī)劃問題基本理論及方法,問題： 該工廠如何安排這兩種新產(chǎn)品的每周生產(chǎn)計(jì)劃，才能使總利潤最大？ 如果要增加資源，首先應(yīng)該增加哪種資源？ 這些資源出租或出售，應(yīng)如何定價(jià)？ 如果產(chǎn)品市場價(jià)格發(fā)生變化、產(chǎn)品加工工藝發(fā)生改變，原 生產(chǎn)方案是否需要調(diào)整？,主要內(nèi)容,線性規(guī)劃問題基本理論及方法 應(yīng)用EXCEL工具求解線性規(guī)劃問題 線性規(guī)劃問題建模求解實(shí)例分析 線性規(guī)劃問題的影子價(jià)格及靈敏度分析,線性規(guī)劃問題基本理論及方法,線性規(guī)劃（Linea

3、r Programming）:運(yùn)籌學(xué)中理論最完善、方法最成熟、應(yīng)用最廣泛的一個(gè)分支。 1939年，前蘇聯(lián)數(shù)學(xué)家康脫洛維奇（L.V.Kantorovich)提出，1947年，美國數(shù)學(xué)家丹捷格（G.B.Dantring)提出線性規(guī)劃的求解方法單純形法。 主要研究兩類問題： 現(xiàn)有資源有限，如何合理安排，使以最少的人力、物力完成任務(wù)？ 任務(wù)確定后，如何計(jì)劃、安排，使在完成任務(wù)的前提下，資源消耗最低？ 可解決生產(chǎn)調(diào)度、合理下料、配料問題、產(chǎn)品配套問題、運(yùn)輸問題等問題。,線性規(guī)劃問題基本理論及方法,數(shù)學(xué)模型：有三個(gè)要素組成： 決策變量：一組定值代表所給問題的一個(gè)具體解決方案。一般要求其非負(fù)。 約束條件：反

4、映所給問題的客觀限制及完成任務(wù)的具體要求，一般表示為一組決策變量的線性等式或不等式。 目標(biāo)函數(shù)：問題所要達(dá)到的目標(biāo)。一般表示為決策變量的線性函數(shù)，取最大值或最小值。,線性規(guī)劃問題基本理論及方法,建模步驟： 確定決策變量：根據(jù)決策問題，確定x=(x1,x2,x3,xn) 找出約束條件：找出所有的限制條件，寫出其表達(dá)式。 明確目標(biāo)函數(shù)：寫出目標(biāo)函數(shù)的最大值（或最小值）。,線性規(guī)劃問題基本理論及方法,線性規(guī)劃問題基本理論及方法,假設(shè)：每周各生產(chǎn)門和窗x1、x2個(gè)。 建立線性規(guī)劃模型如下： Max Z=300 x1+500 x2 x14 2x212 3x1+2x218 x1、x20,S.t,線性規(guī)劃問

5、題基本理論及方法,例1：紅星重型機(jī)械廠的產(chǎn)品組合問題： 紅星機(jī)械廠開發(fā)出產(chǎn)品甲與產(chǎn)品乙。管理層決定近期安排生產(chǎn)這兩種產(chǎn)品。已知產(chǎn)品甲需要原料A，產(chǎn)品乙需要原料B。由于兩種產(chǎn)品都在一個(gè)設(shè)備上生產(chǎn)，且設(shè)備工時(shí)有限，管理者必須合理安排兩種產(chǎn)品的產(chǎn)量，使得在資源有限的條件下獲得最大利潤。,線性規(guī)劃問題基本理論及方法,例2：美克制造公司的勞動力分配問題： 美克制造公司生產(chǎn)三種產(chǎn)品，每單位產(chǎn)品的利潤分別為100元、90元和95元。每個(gè)產(chǎn)品都要經(jīng)過4個(gè)車間加工。假定每個(gè)車間的工人總工時(shí)是給定的，每單位產(chǎn)品在各車間需要的工時(shí)見表。決定三種產(chǎn)品的生產(chǎn)數(shù)量。,線性規(guī)劃問題基本理論及方法,例3：新農(nóng)飼料公司飼料配制

6、問題： 新農(nóng)飼料公司希望用玉米和紅薯兩種原料配制一種混合飼料。由于玉米和紅薯包含的營養(yǎng)成分和采購成本都不相同，公司管理層希望能夠確定混合飼料中玉米和紅薯的數(shù)量，使得飼料能夠以最低的成本達(dá)到給定的營養(yǎng)要求。收集資料如下：,線性規(guī)劃問題基本理論及方法,求解步驟： 找出初始基本可行解（一般選擇原點(diǎn)）； 檢驗(yàn)初始基本可行解是否為最優(yōu)解； 如果不是，尋找新的基本可行解； 再次進(jìn)行檢驗(yàn)，直到找出最優(yōu)解為止。 對于兩個(gè)變量的線性規(guī)劃問題，可用圖解法；對于兩個(gè)以上變量問題，采用單純形法求解。 圖解法、單純形法例。,線性規(guī)劃問題基本理論及方法,圖解法求解步驟： 建立x1Ox2平面直角坐標(biāo)系。 將所有約束條件的臨

7、界值（直線）標(biāo)于坐標(biāo)系中，得出可行域（所有可行解的集合）。 給目標(biāo)函數(shù)賦一值，在坐標(biāo)系中劃出相應(yīng)直線，在可行域中移動，找出其極值方向的交點(diǎn)，即為該問題的最優(yōu)解。,線性規(guī)劃問題基本理論及方法,解的性質(zhì): 線性規(guī)劃問題的可行域都是凸多邊形（可能無界）； 可行域的頂點(diǎn)為基本可行解，若存在最優(yōu)解，一定在頂點(diǎn)上達(dá)到； 如果同時(shí)在兩個(gè)頂點(diǎn)達(dá)到最優(yōu)解，該直線上任意一點(diǎn)均為最優(yōu)解，此時(shí)為無窮多最優(yōu)解。 求解原理：從可行域中的某一頂點(diǎn)開始，逐一進(jìn)行比較，使目標(biāo)函數(shù)最優(yōu)的頂點(diǎn)即為最優(yōu)解。,線性規(guī)劃問題基本理論及方法,線性規(guī)劃的基本原理（以例圖解法說明）： 解的類型：,線性規(guī)劃問題基本理論及方法,單純形法求解步驟：

8、 將線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)型（目標(biāo)函數(shù)求極大、約束條件為等式、決策變量大于0）； 找出初始基本可行解（即：m個(gè)約束條件中存在m個(gè)單位列向量，組成單位矩陣）； 檢驗(yàn)初始基本可行解是否為最優(yōu)解？（若所有非基變量的檢驗(yàn)數(shù)j0，則基本可行解為最優(yōu)解）； 如果不是最優(yōu)解，進(jìn)行迭代，求出新的基本可行解。（根據(jù)最小比值原則選擇出基變量和進(jìn)基變量） 單純形法計(jì)算過程在單純形表中具體實(shí)現(xiàn)。,應(yīng)用EXCEL工具求解線性規(guī)劃問題,一、在EXCEL電子表格中建立線性規(guī)劃模型 1、把相關(guān)數(shù)據(jù)輸入到EXCEL電子表格中,應(yīng)用EXCEL工具求解線性規(guī)劃問題,2、主要求解結(jié)果 兩種新產(chǎn)品x1、x2每周的產(chǎn)量； 兩種新產(chǎn)品每周

9、各實(shí)際使用的工時(shí)（不能 超過計(jì)劃工時(shí)）； 兩種新產(chǎn)品的總利潤z。,應(yīng)用EXCEL工具求解線性規(guī)劃問題,3、主要結(jié)果的計(jì)算方法 （1）兩種新產(chǎn)品的每周產(chǎn)量：C12、D12，試驗(yàn)解為0。 （2）實(shí)際使用工時(shí)計(jì)算（三種方法） 分別在E7、E8、E9中輸入相應(yīng)的計(jì)算公式： E7：C7*C12+D7*D12； E8：C8*C12+D8*D12； E9：C9*C12+D9*D12 復(fù)制、粘貼方法： 在E7中輸入：C7*$C$12+D7*$D$12，然后復(fù)制E7單元格到E8、E9 公式法： 在E7中輸入：=SUMPRODUCT（C7：D7，$C$12，$D$12） 復(fù)制E7單元格到E8、E9,應(yīng)用EXCEL

10、工具求解線性規(guī)劃問題,（3）總利潤計(jì)算： 在G12單元格輸入公式： =C4*C12+D4*D12 或： =SUMPRODUCT（C4：D4，C12：D12）,應(yīng)用EXCEL工具求解線性規(guī)劃問題,收集問題數(shù)據(jù)； 在EXCEL表格中輸入數(shù)據(jù)（數(shù)據(jù)單元格）； 確定決策變量單元格（可變單元格）； 輸入約束條件左邊的公式（輸出單元格）,使用SUMPRODUCT函數(shù)簡化輸入； 輸入目標(biāo)函數(shù)公式（目標(biāo)單元格）。使用SUMPRODUCT函數(shù)簡化輸入。,在EXCEL中建立線性規(guī)劃模型步驟總結(jié),應(yīng)用EXCEL工具求解線性規(guī)劃問題,二、在EXCEL電子表格中求解線性規(guī)劃模型 1、求解參數(shù)設(shè)置： “工具”規(guī)劃求解“，

11、彈出“規(guī)劃求解參數(shù)”對話框，設(shè)置求解相關(guān)參數(shù)。,應(yīng)用EXCEL工具求解線性規(guī)劃問題,2、約束的設(shè)置： 單擊 “添加”，彈出“添加約束”，添加約束條件。,應(yīng)用EXCEL工具求解線性規(guī)劃問題,3、求解選項(xiàng)設(shè)置： 單擊“選項(xiàng)”，彈出“規(guī)劃求解選項(xiàng)”對話框。選擇“采用線性模型”和“假定非負(fù)”。,應(yīng)用EXCEL工具求解線性規(guī)劃問題,4、求解及結(jié)果 單擊“求解”，開始規(guī)劃求解。彈出“規(guī)劃求解結(jié)果”對話框。選擇“保存規(guī)劃求解結(jié)果”。,應(yīng)用EXCEL工具求解線性規(guī)劃問題,5、電子表格顯示結(jié)果： 單擊“確定”，在電子表格的可變單元格、輸出單元格及目標(biāo)單元格出現(xiàn)求解結(jié)果。,輸入數(shù)據(jù) 標(biāo)識數(shù)據(jù) 每個(gè)數(shù)據(jù)對應(yīng)唯一單元

12、格 在電子表格中顯示完整模型 數(shù)據(jù)、公式分離 保持簡單化 使用相對和絕對地址簡化公式并復(fù)制 使用邊框、底色區(qū)分單元格類型 例1-3,建模求解要點(diǎn)回顧,應(yīng)用EXCEL工具求解線性規(guī)劃問題,四、線性規(guī)劃問題解的表現(xiàn) EXCEL建模求解，其解的結(jié)果在“規(guī)劃求解結(jié)果”對話框中提示： 1、唯一最優(yōu)解為”找到一個(gè)解“ 2、無窮多最優(yōu)解為”滿足條件有多個(gè)解“ 3、無解為”未找到可行解“,線性規(guī)劃問題建模求解實(shí)例分析,一、生產(chǎn)計(jì)劃問題 例1：某工廠生產(chǎn)甲、乙、丙三種產(chǎn)品，都要經(jīng)過鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，也可自行生產(chǎn)，但產(chǎn)品丙必須在本廠鑄造才能保證質(zhì)量。數(shù)據(jù)見表。問：公司為

13、了獲得最大利潤，甲、乙、丙三種產(chǎn)品應(yīng)各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄件應(yīng)由本公司鑄造和由外包協(xié)作各多少件?,線性規(guī)劃問題建模求解實(shí)例分析,線性規(guī)劃問題建模求解實(shí)例分析,例2：某工廠生產(chǎn)A、B種產(chǎn)品，均需經(jīng)過兩道工序，每生產(chǎn)1噸A產(chǎn)品需要經(jīng)過第一道工序加工2小時(shí)，第二道工序加工3小時(shí)；每生產(chǎn)1噸B產(chǎn)品需要經(jīng)過第一道工序加工3小時(shí)，第二道工序加工4小時(shí)?？晒├玫牡谝坏拦ば蚬r(shí)為15小時(shí)；第二道工序工時(shí)為25小時(shí)。 生產(chǎn)產(chǎn)品B的同時(shí)可產(chǎn)出副產(chǎn)品C，每生產(chǎn)1噸產(chǎn)品B，可同時(shí)得到2噸產(chǎn)品C而不需要外加任何費(fèi)用。副產(chǎn)品C一部分可以贏利，但剩下的只能報(bào)廢，報(bào)廢需要有一定的費(fèi)用。 出售產(chǎn)品A每噸能贏利400

14、元；出售產(chǎn)品B每噸能贏利800元；出售副產(chǎn)品C每噸能贏利300元；當(dāng)剩余的產(chǎn)品C報(bào)廢時(shí)，每噸損失費(fèi)為200元。經(jīng)市場預(yù)測，在計(jì)劃期內(nèi)產(chǎn)品C的最大銷售量為5噸。 問：如何安排A、B兩種產(chǎn)品的產(chǎn)量可使工廠總盈利最大？,線性規(guī)劃問題建模求解實(shí)例分析,二、生產(chǎn)存儲問題 某公司根據(jù)訂單生產(chǎn)。已知半年內(nèi)對某產(chǎn)品的需求量、單位生產(chǎn)費(fèi)用和單位存儲費(fèi)用見表。已知公司每月的生產(chǎn)能力為100，每月倉庫容量為50.問：如何確定產(chǎn)品未來半年內(nèi)每月最佳生產(chǎn)量和存儲量，才能使總費(fèi)用最少？,線性規(guī)劃問題建模求解實(shí)例分析,三、項(xiàng)目投資問題 1、某公司有100萬元的資金可供投資,該公司有六個(gè)可選的投資項(xiàng)目,其各種數(shù)據(jù)見下表.該公

15、司的目標(biāo):投資風(fēng)險(xiǎn)最小,每年紅利至少6.5萬元,最低平均增長率為12%,最低平均信用度為7.,線性規(guī)劃問題建模求解實(shí)例分析,假設(shè)：xi為每種投資項(xiàng)目投資額。建立線性規(guī)劃模型如下： MinZ=0.18x1+0.06x2+0.10 x3+0.04x4+0.12x5+0.08x6 x1+x2 +x3 +x4 +x5 +x6 =100 0.04x1+0.05x2+0.09x3+0.07x4+0.06x5+0.08x6 6.5 0.22x1+0.07x2+0.12x3+0.08x4+0.15x5+0.08x6 12 4x1+10 x2 +2x3 +10 x4 +4x5 +6x6 700 x1、x2 、x

16、3 、x4 、x5 、x6 0,線性規(guī)劃問題建模求解實(shí)例分析,2、證券投資問題： 一證券投資者將1000萬元資金用于證券投資。已知各種證券（A、B、C、D、E、F）的評級、到期年限、每年稅后收益見表。管理者對投資者提出下列要求（1）國債投資額不能少于300萬元；（2）投資證券的平均評級不超過1.5；（3）投資證券的平均到期年限不超過5年。問：每種證券投資多少可以使得稅后收益最大？,線性規(guī)劃問題建模求解實(shí)例分析,3、連續(xù)投資優(yōu)化 某部門在今后五年內(nèi)考慮給下列項(xiàng)目投資： 項(xiàng)目A：從第一年到第四年每年年初都可以投資，并于次年年 末收回本利115%； 項(xiàng)目B：第三年初可以投資，到第五年末能收回本利12

17、5%， 但規(guī)定最大投資額不超過4萬元； 項(xiàng)目C：第二年年初可以投資，到第五年末能收回本利 140%，但規(guī)定最大投資額不超過3萬元； 項(xiàng)目D：五年內(nèi)每年年初都可以購買公債，于當(dāng)年年末歸還 并加利息6%； 該部門現(xiàn)有資金10萬元，問應(yīng)該如何確定這些項(xiàng)目的每年投資額，使得第五年末擁有的資金本利總額最大？,線性規(guī)劃問題建模求解實(shí)例分析,四、背包問題 1、有一艘貨輪，它的容積為5400m3，其最大允許載重量3000t，現(xiàn)有三種大批量的貨物待運(yùn)，已知有關(guān)數(shù)據(jù)如下。問：該貨輪應(yīng)裝載商品1、2、3個(gè)多少件，其運(yùn)費(fèi)收入為最大？,線性規(guī)劃問題建模求解實(shí)例分析,2、某航運(yùn)公司有一條三個(gè)艙口的貨輪，它們的載容量和載重

18、量見表。待運(yùn)貨物的品種、數(shù)量、體積、重量見表。為了保證航行的安全，要求各船按照確定的載重量裝貨，2號艙對1號艙的載重量比值、 2號艙對3號艙的載重量比值允許在10%的范圍內(nèi)變動， 3號艙對1號艙的載重量比值允許在5%的范圍內(nèi)變動。問：如何合理配載，才能使總的運(yùn)費(fèi)收入達(dá)到最大？,線性規(guī)劃問題建模求解實(shí)例分析,2、,線性規(guī)劃問題建模求解實(shí)例分析,五、套裁下料問題: 某工廠要做100套鋼架，每套鋼架分別需要長度為2.9米、2.1米和1.5米得圓鋼各一套。已知原料每根長7.4米，問應(yīng)如何下料，可使所用原料最省？,線性規(guī)劃問題建模求解實(shí)例分析,六、營養(yǎng)配餐問題: 假設(shè)一個(gè)成年人每周需要從食物中獲取250

19、0卡路里熱量、100g蛋白質(zhì)、1000mg維生素和400mg鈣。如果市場上只有四種食品可供選擇，它們每千克所含熱量和營養(yǎng)成分以及市場價(jià)格見表。問如果每人每周四種食品總食用量限制在4.5kg，如何選擇才能使在滿足營養(yǎng)的前提下使購買食品的總費(fèi)用最??？,線性規(guī)劃問題建模求解實(shí)例分析,七、人力資源分配 例1：話務(wù)員排班問題： 某急救中心雇傭多名話務(wù)員工作，他們每天工作3節(jié)，每節(jié)3小時(shí)。每節(jié)開始時(shí)間為午夜、凌晨3點(diǎn)、凌晨6點(diǎn)、上午9點(diǎn)、中午12點(diǎn)、下午3點(diǎn)、下午6點(diǎn)和晚上9點(diǎn)。為方便話務(wù)員上下班，管理層安排每位話務(wù)員每天連續(xù)工作3節(jié)。不同時(shí)間，由于業(yè)務(wù)量不同，需要的話務(wù)員人數(shù)也不相同，公司付得薪水也不相

20、同。問：如何安排話務(wù)員才能保證服務(wù)人數(shù)又使總成本最低？,線性規(guī)劃問題建模求解實(shí)例分析,例2：某快餐店坐落在一個(gè)遠(yuǎn)離市區(qū)的旅游點(diǎn)中，平時(shí)游客不多，而在除冬季外每個(gè)雙休日游客都比較多。該快餐店有兩名正式職工，正式職工每天工作8小時(shí)，且每個(gè)時(shí)間段都至少有一名正式職工在上班，其余工作有臨時(shí)工來承擔(dān)，臨時(shí)工每班工作4小時(shí)。在雙休日每天上午10時(shí)開始營業(yè)到下午10時(shí)關(guān)門。根據(jù)游客就餐情況，在雙休日每個(gè)營業(yè)時(shí)間段所需職工數(shù)（包括正式工和臨時(shí)工）見表。 已知一名正式職工10點(diǎn)開始上班，工作4小時(shí)后休息1小時(shí)，而后再工作4小時(shí)；另一名正式職工13點(diǎn)開始上班，工作4小時(shí)后休息1小時(shí)，而后再工作4小時(shí)。臨時(shí)工每小時(shí)

21、的工資為4元。,線性規(guī)劃問題建模求解實(shí)例分析,在滿足對職工需求的條件下，如何安排臨時(shí)工的班次，使得使用臨時(shí)工的成本為最?。窟@時(shí)付給臨時(shí)工的工資總額是多少？一共需要安排多少個(gè)班次的臨時(shí)工？如果可以安排每班工作3小時(shí)的臨時(shí)工班次，是否可使總成本更小。,線性規(guī)劃問題建模求解實(shí)例分析,八、其它 例1：某市場調(diào)查公司受某公司委托，調(diào)查消費(fèi)者對某種新產(chǎn)品的了解和反應(yīng)情況。該公司對調(diào)查公司提出如下要求： （1）共對500個(gè)家庭進(jìn)行調(diào)查； （2）在被調(diào)查家庭中，至少有200個(gè)是沒有孩子的家庭，同時(shí)至少有200個(gè)是有孩子的家庭； （3）至少對300個(gè)被調(diào)查家庭采用問卷式書面調(diào)查，對其余家庭可采用口頭調(diào)查； （4

22、）在有孩子的被調(diào)查家庭中，至少對50%的家庭采用問卷式書面調(diào)查； （5）在沒有孩子的被調(diào)查家庭中，至少對60%的家庭采用問卷式書面調(diào)查。 調(diào)查費(fèi)用見表。問：市場調(diào)查公司應(yīng)如何進(jìn)行調(diào)查，使得在滿足公司要求的條件下， 使得總調(diào)查費(fèi)用 最少？,線性規(guī)劃問題建模求解實(shí)例分析,例2：巨斯特石油公司混合問題： 巨斯特石油公司要生產(chǎn)兩種汽油產(chǎn)品。一種是一般汽油，另一種是特殊汽油。公司來煉油廠希望通過合成4類石油成分來生產(chǎn)這兩種汽油產(chǎn)品。兩種汽油的售價(jià)、4類石油成分成本均不同。公司希望確定一種混合這4類石油成分以生產(chǎn)兩種汽油產(chǎn)品的方案來獲得最大利潤。,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,對偶問題： 線性規(guī)劃的

23、一個(gè)有趣現(xiàn)象。任何一個(gè)線性規(guī)劃問題都有一個(gè)與之相對應(yīng)的對偶問題，在求出一個(gè)問題的最優(yōu)解的同時(shí)，也得出其對偶問題的最優(yōu)解。,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,原問題 對偶問題,Max Z=300 x1+500 x2 x14 2x212 3x1+2x218 x1、x20,S.t,Min W=4y1+12y2+18y3 y1+3y3300 2y2+2y3500 y1、 y2 、y30,S.t,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,影子價(jià)格：經(jīng)濟(jì)學(xué)的一個(gè)重要概念，又稱預(yù)測價(jià)格。指某種產(chǎn)品或資源增加一個(gè)單位所帶來的總收益的增加量（反映一種資源在最優(yōu)方案條件下單位資源提供的目標(biāo)函數(shù)值的增量）。是一種資源效

24、用價(jià)值的估價(jià)。 對偶問題的第i個(gè)對偶變量就是原問題第i個(gè)約束條件的影子價(jià)格。如前例：x*=( 2,6)；y*=( 0,150,100)。車間2的總工時(shí)由12變?yōu)?3時(shí)，可使所獲總利潤增加150元。 實(shí)際意義： 當(dāng)考慮通過增加資源以增加收益，應(yīng)選擇影子價(jià)格最大的資源； 當(dāng)某種資源的影子價(jià)格高于（或低于）該資源的市場價(jià)格時(shí)，公司應(yīng)考慮對該種資源進(jìn)行購買（或出售、租）； 影子價(jià)格幫助管理人員判斷某種產(chǎn)品是否值得生產(chǎn)（或制定新產(chǎn)品價(jià)格）；,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,靈敏度分析： 在用線性規(guī)劃方法解決實(shí)際問題時(shí)，把cj、aij、bi均當(dāng)成確定的常量系數(shù)是不符合實(shí)際的。因此所得出的最優(yōu)解和最優(yōu)值

25、也不是一塵不變的。其原因： 這些數(shù)據(jù)是通過統(tǒng)計(jì)、預(yù)測或經(jīng)驗(yàn)得出； 受政策因素、市場條件、科技進(jìn)步、資源供應(yīng)狀況等因素影響。 因此，線性規(guī)劃還需考慮： 當(dāng)上述系數(shù)中的一個(gè)或幾個(gè)因素發(fā)生變化，原來的最優(yōu)解是否發(fā)生變化？ 這些系數(shù)在什么范圍內(nèi)變化，原來的最優(yōu)解或最優(yōu)值不變？ 如果系數(shù)發(fā)生變化引起最優(yōu)解發(fā)生變化，新的最優(yōu)解和最優(yōu)值如何得到？,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,線性規(guī)劃問題的靈敏度分析是在求出最優(yōu)解的基礎(chǔ)上，進(jìn)一步討論當(dāng)cj、bi、aij發(fā)生變化時(shí)，對最優(yōu)解的影響。 判斷某一系數(shù)發(fā)生變化，原最優(yōu)解是否發(fā)生變化？ 怎樣得出使原最優(yōu)解不變的系數(shù)變化范圍。 當(dāng)最優(yōu)解發(fā)生變化時(shí)，怎樣求出新的最

26、優(yōu)解。,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,1、單個(gè)cj變動 例：如果門的單位利潤由原來的300元提升到500元，最優(yōu)解是否會改變？對總利潤會產(chǎn)生怎樣的影響？ 方法1：應(yīng)用電子表格進(jìn)行分析 改變電子表格模型中相應(yīng)的參數(shù)，再運(yùn)行EXCEL”規(guī)劃求解”功能，得出結(jié)果，看其是否對原最優(yōu)解有影響。,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,方法2：應(yīng)用敏感性報(bào)告尋找允許變化范圍 對原電子表格模型運(yùn)行EXCEL”規(guī)劃求解”功能，得出“規(guī)劃求解結(jié)果”對話框，選擇右端“敏感性報(bào)告”選項(xiàng)，得出相應(yīng)結(jié)果。,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,比較兩種方法的區(qū)別？,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,2、多個(gè)cj變動

27、例：如果把門的單位利潤由300元提高到450元，同時(shí)把窗的單位利潤由500元減少到400元，原來的最優(yōu)解和最優(yōu)值是否會發(fā)生變化？ 方法1：應(yīng)用電子表格進(jìn)行分析 改變EXCEL模型中相應(yīng)的參數(shù)，再運(yùn)行EXCEL”規(guī)劃求解”功能，得出結(jié)果，看其是否對原最優(yōu)解、最優(yōu)值有影響。,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,方法2：應(yīng)用敏感性報(bào)告及百分之百法則進(jìn)行分析 對原電子表格模型，運(yùn)行EXCEL”規(guī)劃求解”功能，得出“規(guī)劃求解結(jié)果”對話框，選擇右端“敏感性報(bào)告”選項(xiàng)，得出相應(yīng)結(jié)果。運(yùn)用百分之百法則進(jìn)行判斷。 百分之一百法則： 對于所有變化的目標(biāo)函數(shù)決策變量系數(shù)（或約束條件右邊常數(shù)），當(dāng)其所有允許增加百分比

28、和允許減少百分比之和不超過百分之一百時(shí)，最優(yōu)解不變。,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,允許增加量百分比= 實(shí)際增加量（上限-現(xiàn)在值）/允許增加量 允許減少量百分比= 實(shí)際減少量（現(xiàn)在值-下限）/允許減少量 例：門300450；窗500400 例：門300600；窗500300 如果超過100%，用電子表格模型重新求解 思考：當(dāng)結(jié)果剛好為100%時(shí)，最優(yōu)解變嗎？,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,應(yīng)用規(guī)則： 當(dāng)允許增加量（減少量）為無窮大時(shí)，則對于任一個(gè)增加量（減少量），其允許增加（或減少）的百分比都看成零。 百分之一百法則是判斷最優(yōu)解變與不變的充分條件，但不是必要條件。 不能應(yīng)用于目標(biāo)函

29、數(shù)決策變量系數(shù)和約束條件右端常數(shù)同時(shí)變化的情況。,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,3、單個(gè)bi變動 例：如果車間2的可用工時(shí)由12小時(shí)增加到13小時(shí)，原來的最優(yōu)解和最優(yōu)值是否發(fā)生變化？ 方法1：應(yīng)用電子表格進(jìn)行分析 改變電子表格模型中相應(yīng)的參數(shù)，再運(yùn)行EXCEL”規(guī)劃求解”功能，得出結(jié)果，看其是否對原最優(yōu)解、最優(yōu)值有影響。 分析：2101820的不同結(jié)果？,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,方法2：應(yīng)用敏感性報(bào)告尋找允許變化范圍 對原電子表格模型運(yùn)行EXCEL”規(guī)劃求解”功能，得出“規(guī)劃求解結(jié)果”對話框，選擇右端“敏感性報(bào)告”選項(xiàng)，得出相應(yīng)結(jié)果。,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,4、多個(gè)bi變動 例：如果車間2的可用工時(shí)由12小時(shí)增加到13小時(shí)，車間3的可用工時(shí)由18小時(shí)減少到17小時(shí)，原來的最優(yōu)解和最優(yōu)值是否發(fā)生變化？ 方法1：應(yīng)用電子表格進(jìn)行分析 改變電子表格模型中相應(yīng)的參數(shù)，再運(yùn)行EXCEL”規(guī)劃求解”功能，得出結(jié)果，看其是否對原最優(yōu)解、最優(yōu)值有影響。,線性規(guī)劃問題的影子價(jià)格及靈敏度分析,方法2：應(yīng)用敏感性報(bào)告及百分之百法則進(jìn)行分析 對原電子表格模型，運(yùn)行E