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

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