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

物流系統(tǒng)優(yōu)化線性規(guī)劃第一頁，共六十九頁，2022年，8月28日“線性規(guī)劃能做什么？第二頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法例：某工廠生產(chǎn)兩種新產(chǎn)品：門和窗。經(jīng)測算，每生產(chǎn)一扇門需要在車間1加工1小時、在車間3加工3小時；每生產(chǎn)一扇窗需要在車間2和車間3各加工2小時。而車間1每周可用于生產(chǎn)這兩種新產(chǎn)品的時間為4小時、車間2為12小時、車間3為18小時。已知每扇門的利潤為300元，每扇窗的利潤為500元。根據(jù)市場調(diào)查得到的這兩種新產(chǎn)品的市場需求狀況可以確定，按當(dāng)前的定價可確保所有的新產(chǎn)品均能銷售出去。第三頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法車間單位產(chǎn)品的生產(chǎn)時間（小時）每周可獲得的生產(chǎn)時間（小時）門窗11042021233218單位利潤（元）300500問題：?該工廠如何安排這兩種新產(chǎn)品的每周生產(chǎn)計劃，才能使總利潤最大？?如果要增加資源，首先應(yīng)該增加哪種資源？?這些資源出租或出售，應(yīng)如何定價？?如果產(chǎn)品市場價格發(fā)生變化、產(chǎn)品加工工藝發(fā)生改變，原生產(chǎn)方案是否需要調(diào)整？第四頁，共六十九頁，2022年，8月28日主要內(nèi)容線性規(guī)劃問題基本理論及方法應(yīng)用EXCEL工具求解線性規(guī)劃問題線性規(guī)劃問題建模求解實例分析線性規(guī)劃問題的影子價格及靈敏度分析第五頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法線性規(guī)劃（LinearProgramming）:運籌學(xué)中理論最完善、方法最成熟、應(yīng)用最廣泛的一個分支。1939年，前蘇聯(lián)數(shù)學(xué)家康脫洛維奇（L.V.Kantorovich)提出，1947年，美國數(shù)學(xué)家丹捷格（G.B.Dantring)提出線性規(guī)劃的求解方法—單純形法。主要研究兩類問題：現(xiàn)有資源有限，如何合理安排，使以最少的人力、物力完成任務(wù)？任務(wù)確定后，如何計劃、安排，使在完成任務(wù)的前提下，資源消耗最低？可解決生產(chǎn)調(diào)度、合理下料、配料問題、產(chǎn)品配套問題、運輸問題等問題。第六頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法數(shù)學(xué)模型：有三個要素組成：決策變量：一組定值代表所給問題的一個具體解決方案。一般要求其非負(fù)。約束條件：反映所給問題的客觀限制及完成任務(wù)的具體要求，一般表示為一組決策變量的線性等式或不等式。目標(biāo)函數(shù)：問題所要達到的目標(biāo)。一般表示為決策變量的線性函數(shù)，取最大值或最小值。第七頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法建模步驟：確定決策變量：根據(jù)決策問題，確定x=(x1,x2,x3,…,xn)找出約束條件：找出所有的限制條件，寫出其表達式。明確目標(biāo)函數(shù)：寫出目標(biāo)函數(shù)的最大值（或最小值）。第八頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法…S.t第九頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法假設(shè)：每周各生產(chǎn)門和窗x1、x2個。建立線性規(guī)劃模型如下：

MaxZ=300x1+500x2x1≤42x2≤123x1+2x2≤18x1、x2≥0S.t第十頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法例1：紅星重型機械廠的產(chǎn)品組合問題：紅星機械廠開發(fā)出產(chǎn)品甲與產(chǎn)品乙。管理層決定近期安排生產(chǎn)這兩種產(chǎn)品。已知產(chǎn)品甲需要原料A，產(chǎn)品乙需要原料B。由于兩種產(chǎn)品都在一個設(shè)備上生產(chǎn)，且設(shè)備工時有限，管理者必須合理安排兩種產(chǎn)品的產(chǎn)量，使得在資源有限的條件下獲得最大利潤。甲乙資源限制原料A（噸）106原料B（噸）028設(shè)備（單位設(shè)備工時）2318單位利潤（萬元）43第十一頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法例2：美克制造公司的勞動力分配問題：美克制造公司生產(chǎn)三種產(chǎn)品，每單位產(chǎn)品的利潤分別為100元、90元和95元。每個產(chǎn)品都要經(jīng)過4個車間加工。假定每個車間的工人總工時是給定的，每單位產(chǎn)品在各車間需要的工時見表。決定三種產(chǎn)品的生產(chǎn)數(shù)量。車間單位產(chǎn)品需要工時（小時）總可用工時（小時）產(chǎn)品1產(chǎn)品2產(chǎn)品311.00.81.2280020.30.40.4180030.91.20.6390040.80.40.32800單位利潤（元）1009095第十二頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法例3：新農(nóng)飼料公司飼料配制問題：新農(nóng)飼料公司希望用玉米和紅薯兩種原料配制一種混合飼料。由于玉米和紅薯包含的營養(yǎng)成分和采購成本都不相同，公司管理層希望能夠確定混合飼料中玉米和紅薯的數(shù)量，使得飼料能夠以最低的成本達到給定的營養(yǎng)要求。收集資料如下：營養(yǎng)成分每千克玉米每千克紅薯最低要求量碳水化合物（克）8420蛋白質(zhì)（克）3618維生素（克）1516采購成本（元）0.80.5第十三頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法求解步驟：找出初始基本可行解（一般選擇原點）；檢驗初始基本可行解是否為最優(yōu)解；如果不是，尋找新的基本可行解；再次進行檢驗，直到找出最優(yōu)解為止。對于兩個變量的線性規(guī)劃問題，可用圖解法；對于兩個以上變量問題，采用單純形法求解。圖解法、單純形法例。第十四頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法圖解法求解步驟：建立x1Ox2平面直角坐標(biāo)系。將所有約束條件的臨界值（直線）標(biāo)于坐標(biāo)系中，得出可行域（所有可行解的集合）。給目標(biāo)函數(shù)賦一值，在坐標(biāo)系中劃出相應(yīng)直線，在可行域中移動，找出其極值方向的交點，即為該問題的最優(yōu)解。第十五頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法解的性質(zhì):線性規(guī)劃問題的可行域都是凸多邊形（可能無界）；可行域的頂點為基本可行解，若存在最優(yōu)解，一定在頂點上達到；如果同時在兩個頂點達到最優(yōu)解，該直線上任意一點均為最優(yōu)解，此時為無窮多最優(yōu)解。求解原理：從可行域中的某一頂點開始，逐一進行比較，使目標(biāo)函數(shù)最優(yōu)的頂點即為最優(yōu)解。第十六頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法線性規(guī)劃的基本原理（以例圖解法說明）：解的類型：一定無解解的結(jié)果有可行域無可行域可行域有界可行域無界唯一解無窮解唯一解無窮解無解第十七頁，共六十九頁，2022年，8月28日線性規(guī)劃問題基本理論及方法單純形法求解步驟：將線性規(guī)劃模型轉(zhuǎn)化為標(biāo)準(zhǔn)型（目標(biāo)函數(shù)求極大、約束條件為等式、決策變量大于0）；找出初始基本可行解（即：m個約束條件中存在m個單位列向量，組成單位矩陣）；檢驗初始基本可行解是否為最優(yōu)解？（若所有非基變量的檢驗數(shù)σj≤0，則基本可行解為最優(yōu)解）；如果不是最優(yōu)解，進行迭代，求出新的基本可行解。（根據(jù)最小比值原則選擇出基變量和進基變量）單純形法計算過程在單純形表中具體實現(xiàn)。第十八頁，共六十九頁，2022年，8月28日應(yīng)用EXCEL工具求解線性規(guī)劃問題一、在EXCEL電子表格中建立線性規(guī)劃模型1、把相關(guān)數(shù)據(jù)輸入到EXCEL電子表格中第十九頁，共六十九頁，2022年，8月28日應(yīng)用EXCEL工具求解線性規(guī)劃問題2、主要求解結(jié)果■兩種新產(chǎn)品x1、x2每周的產(chǎn)量；■兩種新產(chǎn)品每周各實際使用的工時（不能超過計劃工時）；■兩種新產(chǎn)品的總利潤z。第二十頁，共六十九頁，2022年，8月28日應(yīng)用EXCEL工具求解線性規(guī)劃問題3、主要結(jié)果的計算方法（1）兩種新產(chǎn)品的每周產(chǎn)量：C12、D12，試驗解為0。（2）實際使用工時計算（三種方法）●分別在E7、E8、E9中輸入相應(yīng)的計算公式：

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第二十一頁，共六十九頁，2022年，8月28日應(yīng)用EXCEL工具求解線性規(guī)劃問題（3）總利潤計算：

在G12單元格輸入公式：

=C4*C12+D4*D12

或：

=SUMPRODUCT（C4：D4，C12：D12）第二十二頁，共六十九頁，2022年，8月28日應(yīng)用EXCEL工具求解線性規(guī)劃問題收集問題數(shù)據(jù)；在EXCEL表格中輸入數(shù)據(jù)（數(shù)據(jù)單元格）；確定決策變量單元格（可變單元格）；輸入約束條件左邊的公式（輸出單元格）,使用SUMPRODUCT函數(shù)簡化輸入；輸入目標(biāo)函數(shù)公式（目標(biāo)單元格）。使用SUMPRODUCT函數(shù)簡化輸入。在EXCEL中建立線性規(guī)劃模型步驟總結(jié)第二十三頁，共六十九頁，2022年，8月28日應(yīng)用EXCEL工具求解線性規(guī)劃問題二、在EXCEL電子表格中求解線性規(guī)劃模型1、求解參數(shù)設(shè)置：

“工具”——”規(guī)劃求解“，彈出“規(guī)劃求解參數(shù)”對話框，設(shè)置求解相關(guān)參數(shù)。第二十四頁，共六十九頁，2022年，8月28日應(yīng)用EXCEL工具求解線性規(guī)劃問題2、約束的設(shè)置：單擊“添加”，彈出“添加約束”，添加約束條件。第二十五頁，共六十九頁，2022年，8月28日應(yīng)用EXCEL工具求解線性規(guī)劃問題3、求解選項設(shè)置：單擊“選項”，彈出“規(guī)劃求解選項”對話框。選擇“采用線性模型”和“假定非負(fù)”。第二十六頁，共六十九頁，2022年，8月28日應(yīng)用EXCEL工具求解線性規(guī)劃問題4、求解及結(jié)果單擊“求解”，開始規(guī)劃求解。彈出“規(guī)劃求解結(jié)果”對話框。選擇“保存規(guī)劃求解結(jié)果”。第二十七頁，共六十九頁，2022年，8月28日應(yīng)用EXCEL工具求解線性規(guī)劃問題5、電子表格顯示結(jié)果：單擊“確定”，在電子表格的可變單元格、輸出單元格及目標(biāo)單元格出現(xiàn)求解結(jié)果。第二十八頁，共六十九頁，2022年，8月28日輸入數(shù)據(jù)標(biāo)識數(shù)據(jù)每個數(shù)據(jù)對應(yīng)唯一單元格在電子表格中顯示完整模型數(shù)據(jù)、公式分離保持簡單化使用相對和絕對地址簡化公式并復(fù)制使用邊框、底色區(qū)分單元格類型例1-3建模求解要點回顧第二十九頁，共六十九頁，2022年，8月28日應(yīng)用EXCEL工具求解線性規(guī)劃問題四、線性規(guī)劃問題解的表現(xiàn)

EXCEL建模求解，其解的結(jié)果在“規(guī)劃求解結(jié)果”對話框中提示：

1、唯一最優(yōu)解為”找到一個解“

2、無窮多最優(yōu)解為”滿足條件有多個解“

3、無解為”未找到可行解“第三十頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析一、生產(chǎn)計劃問題例1：某工廠生產(chǎn)甲、乙、丙三種產(chǎn)品，都要經(jīng)過鑄造、機加工和裝配三個車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，也可自行生產(chǎn)，但產(chǎn)品丙必須在本廠鑄造才能保證質(zhì)量。數(shù)據(jù)見表。問：公司為了獲得最大利潤，甲、乙、丙三種產(chǎn)品應(yīng)各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄件應(yīng)由本公司鑄造和由外包協(xié)作各多少件?第三十一頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙工時限制單件鑄造工時（小時）51078000單件機加工工時（小時）64812000單件裝配工時（小時）32210000自產(chǎn)鑄件成本（元/件）354外協(xié)鑄件成本（元/件）56-機加工成本（元/件）213裝配成本（元/件）322產(chǎn)品售價（元/件）231816第三十二頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析例2：某工廠生產(chǎn)A、B種產(chǎn)品，均需經(jīng)過兩道工序，每生產(chǎn)1噸A產(chǎn)品需要經(jīng)過第一道工序加工2小時，第二道工序加工3小時；每生產(chǎn)1噸B產(chǎn)品需要經(jīng)過第一道工序加工3小時，第二道工序加工4小時。可供利用的第一道工序工時為15小時；第二道工序工時為25小時。生產(chǎn)產(chǎn)品B的同時可產(chǎn)出副產(chǎn)品C，每生產(chǎn)1噸產(chǎn)品B，可同時得到2噸產(chǎn)品C而不需要外加任何費用。副產(chǎn)品C一部分可以贏利，但剩下的只能報廢，報廢需要有一定的費用。出售產(chǎn)品A每噸能贏利400元；出售產(chǎn)品B每噸能贏利800元；出售副產(chǎn)品C每噸能贏利300元；當(dāng)剩余的產(chǎn)品C報廢時，每噸損失費為200元。經(jīng)市場預(yù)測，在計劃期內(nèi)產(chǎn)品C的最大銷售量為5噸。問：如何安排A、B兩種產(chǎn)品的產(chǎn)量可使工廠總盈利最大？第三十三頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析二、生產(chǎn)存儲問題

某公司根據(jù)訂單生產(chǎn)。已知半年內(nèi)對某產(chǎn)品的需求量、單位生產(chǎn)費用和單位存儲費用見表。已知公司每月的生產(chǎn)能力為100，每月倉庫容量為50.問：如何確定產(chǎn)品未來半年內(nèi)每月最佳生產(chǎn)量和存儲量，才能使總費用最少？

月份123456需求量504050455530單位生產(chǎn)費用825775850850775825單位存儲費用403035204040第三十四頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析三、項目投資問題1、某公司有100萬元的資金可供投資,該公司有六個可選的投資項目,其各種數(shù)據(jù)見下表.該公司的目標(biāo):投資風(fēng)險最小,每年紅利至少6.5萬元,最低平均增長率為12%,最低平均信用度為7.投資項目風(fēng)險(%)紅利(%)增長率(%)信用度11842242657103109122447810512615468886第三十五頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析假設(shè)：xi為每種投資項目投資額。建立線性規(guī)劃模型如下：

MinZ=0.18x1+0.06x2+0.10x3+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.50.22x1+0.07x2+0.12x3+0.08x4+0.15x5+0.08x6≥124x1+10x2+2x3+10x4+4x5+6x6≥700x1、x2、x3、x4、x5、x6≥0第三十六頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析2、證券投資問題：一證券投資者將1000萬元資金用于證券投資。已知各種證券（A、B、C、D、E、F）的評級、到期年限、每年稅后收益見表。管理者對投資者提出下列要求（1）國債投資額不能少于300萬元；（2）投資證券的平均評級不超過1.5；（3）投資證券的平均到期年限不超過5年。問：每種證券投資多少可以使得稅后收益最大？

證券名稱證券類型評級到期年限（年）每年稅后收益（%）A地方債券294.3B基金2124.4C國債153.2D國債143.0E地方債券433.2F基金544.5第三十七頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析3、連續(xù)投資優(yōu)化

某部門在今后五年內(nèi)考慮給下列項目投資：項目A：從第一年到第四年每年年初都可以投資，并于次年年末收回本利115%；項目B：第三年初可以投資，到第五年末能收回本利125%，但規(guī)定最大投資額不超過4萬元；項目C：第二年年初可以投資，到第五年末能收回本利

140%，但規(guī)定最大投資額不超過3萬元；項目D：五年內(nèi)每年年初都可以購買公債，于當(dāng)年年末歸還并加利息6%；該部門現(xiàn)有資金10萬元，問應(yīng)該如何確定這些項目的每年投資額，使得第五年末擁有的資金本利總額最大？第三十八頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析四、背包問題1、有一艘貨輪，它的容積為5400m3，其最大允許載重量3000t，現(xiàn)有三種大批量的貨物待運，已知有關(guān)數(shù)據(jù)如下。問：該貨輪應(yīng)裝載商品1、2、3個多少件，其運費收入為最大？商品每件體積（m3/件）每件重量（t/件）運價（元/件）11081000256700375600第三十九頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析2、某航運公司有一條三個艙口的貨輪，它們的載容量和載重量見表。待運貨物的品種、數(shù)量、體積、重量見表。為了保證航行的安全，要求各船按照確定的載重量裝貨，2號艙對1號艙的載重量比值、2號艙對3號艙的載重量比值允許在10%的范圍內(nèi)變動，3號艙對1號艙的載重量比值允許在5%的范圍內(nèi)變動。問：如何合理配載，才能使總的運費收入達到最大？第四十頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析2、

艙號載容量（m3）載重量（t）136002800242003200330002400貨物種類數(shù)量（件）體積（m3/件）重量（t/件）運費（元/件）15008615002100043800360054900第四十一頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析五、套裁下料問題:

某工廠要做100套鋼架，每套鋼架分別需要長度為2.9米、2.1米和1.5米得圓鋼各一套。已知原料每根長7.4米，問應(yīng)如何下料，可使所用原料最??？

第四十二頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析六、營養(yǎng)配餐問題:

假設(shè)一個成年人每周需要從食物中獲取2500卡路里熱量、100g蛋白質(zhì)、1000mg維生素和400mg鈣。如果市場上只有四種食品可供選擇，它們每千克所含熱量和營養(yǎng)成分以及市場價格見表。問如果每人每周四種食品總食用量限制在4.5kg，如何選擇才能使在滿足營養(yǎng)的前提下使購買食品的總費用最??？

食品名稱熱量（卡路里）蛋白質(zhì)（g）維生素（mg）鈣（mg）價格（元/kg）豬肉（kg)150010018020020雞蛋（kg)1000120501008大米（kg)60025501503.5蔬菜水果（kg求量25001001000400第四十三頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析七、人力資源分配例1：話務(wù)員排班問題：某急救中心雇傭多名話務(wù)員工作，他們每天工作3節(jié)，每節(jié)3小時。每節(jié)開始時間為午夜、凌晨3點、凌晨6點、上午9點、中午12點、下午3點、下午6點和晚上9點。為方便話務(wù)員上下班，管理層安排每位話務(wù)員每天連續(xù)工作3節(jié)。不同時間，由于業(yè)務(wù)量不同，需要的話務(wù)員人數(shù)也不相同，公司付得薪水也不相同。問：如何安排話務(wù)員才能保證服務(wù)人數(shù)又使總成本最低？

工作時間0-3點3-6點6-9點9-12點12-15點15-18點18-21點21-24點最低需求人數(shù)（人）86152025231810薪水（元）2630282220202224第四十四頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析例2：某快餐店坐落在一個遠(yuǎn)離市區(qū)的旅游點中，平時游客不多，而在除冬季外每個雙休日游客都比較多。該快餐店有兩名正式職工，正式職工每天工作8小時，且每個時間段都至少有一名正式職工在上班，其余工作有臨時工來承擔(dān)，臨時工每班工作4小時。在雙休日每天上午10時開始營業(yè)到下午10時關(guān)門。根據(jù)游客就餐情況，在雙休日每個營業(yè)時間段所需職工數(shù)（包括正式工和臨時工）見表。已知一名正式職工10點開始上班，工作4小時后休息1小時，而后再工作4小時；另一名正式職工13點開始上班，工作4小時后休息1小時，而后再工作4小時。臨時工每小時的工資為4元。第四十五頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析時間段所需職工數(shù)時間段所需職工數(shù)10:00—11:00916:00—17:00311:00—12:001017:00—18:00612:00—13:001018:00—19:001213:00—14:00919:00—20:001214:00—15:00320:00—21:00715:00—16:00321:00—22:007在滿足對職工需求的條件下，如何安排臨時工的班次，使得使用臨時工的成本為最?。窟@時付給臨時工的工資總額是多少？一共需要安排多少個班次的臨時工？如果可以安排每班工作3小時的臨時工班次，是否可使總成本更小。第四十六頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析八、其它例1：某市場調(diào)查公司受某公司委托，調(diào)查消費者對某種新產(chǎn)品的了解和反應(yīng)情況。該公司對調(diào)查公司提出如下要求：（1）共對500個家庭進行調(diào)查；（2）在被調(diào)查家庭中，至少有200個是沒有孩子的家庭，同時至少有200個是有孩子的家庭；（3）至少對300個被調(diào)查家庭采用問卷式書面調(diào)查，對其余家庭可采用口頭調(diào)查；（4）在有孩子的被調(diào)查家庭中，至少對50%的家庭采用問卷式書面調(diào)查；（5）在沒有孩子的被調(diào)查家庭中，至少對60%的家庭采用問卷式書面調(diào)查。調(diào)查費用見表。問：市場調(diào)查公司應(yīng)如何進行調(diào)查，使得在滿足公司要求的條件下，使得總調(diào)查費用最少？家庭類型調(diào)查費用（元）問卷式書面調(diào)查口頭調(diào)查有孩子家庭5030沒有孩子家庭4025第四十七頁，共六十九頁，2022年，8月28日線性規(guī)劃問題建模求解實例分析例2：巨斯特石油公司混合問題：

巨斯特石油公司要生產(chǎn)兩種汽油產(chǎn)品。一種是一般汽油，另一種是特殊汽油。公司來煉油廠希望通過合成4類石油成分來生產(chǎn)這兩種汽油產(chǎn)品。兩種汽油的售價、4類石油成分成本均不同。公司希望確定一種混合這4類石油成分以生產(chǎn)兩種汽油產(chǎn)品的方案來獲得最大利潤。石油成分單位成本（$）最大供應(yīng)量（加侖）一般汽油產(chǎn)品要求特殊汽油產(chǎn)品要求成分10.856000最多30%最少25%成分21.1512000最少35%最多40%成分31.3611000最多20%最少30%成分41.201300025%18%第四十八頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析對偶問題：線性規(guī)劃的一個有趣現(xiàn)象。任何一個線性規(guī)劃問題都有一個與之相對應(yīng)的對偶問題，在求出一個問題的最優(yōu)解的同時，也得出其對偶問題的最優(yōu)解。…S.tS.t…第四十九頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析

原問題對偶問題MaxZ=300x1+500x2x1≤42x2≤123x1+2x2≤18x1、x2≥0S.tMinW=4y1+12y2+18y3y1+3y3≥3002y2+2y3≥500y1、y2、y3≥0S.t第五十頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析影子價格：經(jīng)濟學(xué)的一個重要概念，又稱預(yù)測價格。指某種產(chǎn)品或資源增加一個單位所帶來的總收益的增加量（反映一種資源在最優(yōu)方案條件下單位資源提供的目標(biāo)函數(shù)值的增量）。是一種資源效用價值的估價。對偶問題的第i個對偶變量就是原問題第i個約束條件的影子價格。如前例：x*=(2,6)；y*=(0,150,100)。車間2的總工時由12變?yōu)?3時，可使所獲總利潤增加150元。實際意義：當(dāng)考慮通過增加資源以增加收益，應(yīng)選擇影子價格最大的資源；當(dāng)某種資源的影子價格高于（或低于）該資源的市場價格時，公司應(yīng)考慮對該種資源進行購買（或出售、租）；影子價格幫助管理人員判斷某種產(chǎn)品是否值得生產(chǎn)（或制定新產(chǎn)品價格）；第五十一頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析靈敏度分析：在用線性規(guī)劃方法解決實際問題時，把cj、aij、bi均當(dāng)成確定的常量系數(shù)是不符合實際的。因此所得出的最優(yōu)解和最優(yōu)值也不是一塵不變的。其原因：這些數(shù)據(jù)是通過統(tǒng)計、預(yù)測或經(jīng)驗得出；受政策因素、市場條件、科技進步、資源供應(yīng)狀況等因素影響。因此，線性規(guī)劃還需考慮：當(dāng)上述系數(shù)中的一個或幾個因素發(fā)生變化，原來的最優(yōu)解是否發(fā)生變化？這些系數(shù)在什么范圍內(nèi)變化，原來的最優(yōu)解或最優(yōu)值不變？如果系數(shù)發(fā)生變化引起最優(yōu)解發(fā)生變化，新的最優(yōu)解和最優(yōu)值如何得到？第五十二頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析線性規(guī)劃問題的靈敏度分析是在求出最優(yōu)解的基礎(chǔ)上，進一步討論當(dāng)cj、bi、aij發(fā)生變化時，對最優(yōu)解的影響。

●

判斷某一系數(shù)發(fā)生變化，原最優(yōu)解是否發(fā)生變化？

●怎樣得出使原最優(yōu)解不變的系數(shù)變化范圍。

●當(dāng)最優(yōu)解發(fā)生變化時，怎樣求出新的最優(yōu)解。第五十三頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析1、單個cj變動例：如果門的單位利潤由原來的300元提升到500元，最優(yōu)解是否會改變？對總利潤會產(chǎn)生怎樣的影響？方法1：應(yīng)用電子表格進行分析改變電子表格模型中相應(yīng)的參數(shù)，再運行EXCEL”規(guī)劃求解”功能，得出結(jié)果，看其是否對原最優(yōu)解有影響。第五十四頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析方法2：應(yīng)用敏感性報告尋找允許變化范圍

對原電子表格模型運行EXCEL”規(guī)劃求解”功能，得出“規(guī)劃求解結(jié)果”對話框，選擇右端“敏感性報告”選項，得出相應(yīng)結(jié)果。第五十五頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析比較兩種方法的區(qū)別？第五十六頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析2、多個cj變動例：如果把門的單位利潤由300元提高到450元，同時把窗的單位利潤由500元減少到400元，原來的最優(yōu)解和最優(yōu)值是否會發(fā)生變化？方法1：應(yīng)用電子表格進行分析改變EXCEL模型中相應(yīng)的參數(shù)，再運行EXCEL”規(guī)劃求解”功能，得出結(jié)果，看其是否對原最優(yōu)解、最優(yōu)值有影響。第五十七頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析方法2：應(yīng)用敏感性報告及百分之百法則進行分析對原電子表格模型，運行EXCEL”規(guī)劃求解”功能，得出“規(guī)劃求解結(jié)果”對話框，選擇右端“敏感性報告”選項，得出相應(yīng)結(jié)果。運用百分之百法則進行判斷。百分之一百法則：對于所有變化的目標(biāo)函數(shù)決策變量系數(shù)（或約束條件右邊常數(shù)），當(dāng)其所有允許增加百分比和允許減少百分比之和不超過百分之一百時，最優(yōu)解不變。第五十八頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析允許增加量百分比=

實際增加量（上限-現(xiàn)在值）/允許增加量允許減少量百分比=

實際減少量（現(xiàn)在值-下限）/允許減少量例：門300——450；窗500——400例：門300——600；窗500——300如果超過100%，用電子表格模型重新求解思考：當(dāng)結(jié)果剛好為100%時，最優(yōu)解變嗎？第五十九頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析應(yīng)用規(guī)則：當(dāng)允許增加量（減少量）為無窮大時，則對于任一個增加量（減少量），其允許增加（或減少）的百分比都看成零。百分之一百法則是判斷最優(yōu)解變與不變的充分條件，但不是必要條件。不能應(yīng)用于目標(biāo)函數(shù)決策變量系數(shù)和約束條件右端常數(shù)同時變化的情況。第六十頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析3、單個bi變動例：如果車間2的可用工時由12小時增加到13小時，原來的最優(yōu)解和最優(yōu)值是否發(fā)生變化？方法1：應(yīng)用電子表格進行分析改變電子表格模型中相應(yīng)的參數(shù)，再運行EXCEL”規(guī)劃求解”功能，得出結(jié)果，看其是否對原最優(yōu)解、最優(yōu)值有影響。

分析：2—10—18—20的不同結(jié)果？第六十一頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析方法2：應(yīng)用敏感性報告尋找允許變化范圍對原電子表格模型運行EXCEL”規(guī)劃求解”功能，得出“規(guī)劃求解結(jié)果”對話框，選擇右端“敏感性報告”選項，得出相應(yīng)結(jié)果。第六十二頁，共六十九頁，2022年，8月28日線性規(guī)劃問題的影子價格及靈敏度分析4、多個bi變動例：如果車間2的可用工時由12小時增加到13小時，車間3的可用工時由18小時減少到17小時，原來的最優(yōu)解和最優(yōu)值是否發(fā)生變化？方法1：應(yīng)用電子表格進行分析