線性規(guī)劃應(yīng)用

1、線性規(guī)劃應(yīng)用信息管理與信息系統(tǒng)(財(cái)會(huì))孫燕2 摘要：線性規(guī)劃就是運(yùn)籌學(xué)中應(yīng)用最廣泛得方法之一，也就是運(yùn)務(wù)學(xué)中得最基本得方法之一, 網(wǎng)絡(luò)規(guī)劃、整數(shù)規(guī)劃.目標(biāo)規(guī)劃與多目標(biāo)規(guī)劃都就是以線性規(guī)劃為基礎(chǔ)得。線性規(guī)劃就是解 決稀缺資源置優(yōu)分配得有效方法，使付出得孌用最少或獲得得利益最大。它得研究對(duì)象就是 有一定得人力、財(cái)力、資源條件下，如何合理安排使用，效益最高；某項(xiàng)任務(wù)確定后，如何安排 人、財(cái)、揚(yáng)，使之最省。它要解決得問(wèn)題得目標(biāo)可以用數(shù)值指標(biāo)反映，對(duì)于要實(shí)現(xiàn)得目標(biāo)有多 種方案可以選擇，有影響決罠得若千約束條件。通過(guò)該課題得設(shè)計(jì)，可以加深對(duì)運(yùn)務(wù)學(xué)、最優(yōu) 化方法、線性規(guī)劃.非線性規(guī)劃等得認(rèn)識(shí)，提離對(duì)這些知識(shí)

2、得綜合運(yùn)用，提高利用靈敏度分析 解決各種實(shí)際問(wèn)題得能力。本文幸主要介紹了線性規(guī)劃模型在實(shí)際生活中得應(yīng)用，其中包括 解線性方程紐得各種方法，如圖解法、單純形法以及對(duì)偶單純形法等等，以及簡(jiǎn)單介紹了有關(guān) 靈敏度分析得方法。由于許多問(wèn)題僅僅利用線性規(guī)劃得方法還不足以解決，因此用到了對(duì)偶 理論，也因此引出了對(duì)偶單純形法。對(duì)偶規(guī)劃就是線性規(guī)劃問(wèn)題從另一個(gè)角度進(jìn)行研究，就是 線性規(guī)劃理論得進(jìn)一步深化，也就是線性規(guī)劃理論整體得一個(gè)不可分割得組成部分。靈敏度 分析就是對(duì)線性規(guī)劃結(jié)果得再發(fā)掘，就是對(duì)線性規(guī)劃理論得充要應(yīng)用。由于知識(shí)儲(chǔ)備與資料 查閱得有限性，線性規(guī)劃得重要作用及應(yīng)用不能一一分析，還存在許多不足之處有

3、待進(jìn)一步 改進(jìn)與提爲(wèi)。關(guān)鍵詞：線性規(guī)劃 單純型表法 對(duì)偶單純型法 靈敏度分析 圖解法 數(shù)學(xué)模型線性規(guī)劃主要在兩類問(wèn)題中得到應(yīng)用：一就是在人力、物力、財(cái)力等資源一定得條件下， 如何使用它們完成最多得任務(wù)；二就是做一項(xiàng)任務(wù)，如何合理安排與規(guī)劃，能以最少得人力、 物力、資金等資源來(lái)完成該項(xiàng)任務(wù)(即少投入，多產(chǎn)出)。在這里，重要得就是建立線性規(guī)劃得數(shù)學(xué)模型，一個(gè)實(shí)際問(wèn)題得數(shù)學(xué)模型，就是依據(jù)客觀 規(guī)律對(duì)該問(wèn)題中我們所關(guān)心得那些董進(jìn)行科學(xué)得分析后所得出反映這些量之間本質(zhì)聯(lián)系得 數(shù)學(xué)關(guān)系式。線性規(guī)劃問(wèn)題得數(shù)學(xué)摸型得一般形式為：min(max) Z = C1X1 + C2X2 + CnXn角1%1 + 冋Mn

4、( * 1+ aZZX2 + 勺機(jī) O T(|),amlXl + a,n2X2 + /丿刑(H)(*)0 j = (l,2.n).其中呦心,CjjQ二l,2n；i= 1,2九)均為已知常數(shù)，(*)表示“王”“”或“ =”,xr耳，九稱為決策變量,Z為目標(biāo)函數(shù)。(I )與(11)稱為約束條件，(I )中得每一個(gè)式子均稱為線性約束，(II)中若要求變量 二0得條件稱為非負(fù)條件。這說(shuō)明，線性規(guī)劃模型由三部分構(gòu)成：(1) -組決我變量X2/ -通常要求它們非負(fù)，但在菜些實(shí)際問(wèn)題中也會(huì)出現(xiàn)變 量為負(fù)數(shù)得情況(2) 表示所給問(wèn)題炭?jī)?yōu)化指標(biāo)得目標(biāo)函數(shù)Z(3) -組約束條件正因?yàn)槟繕?biāo)函數(shù)與約束條件都就是關(guān)于決

5、策變量得線性表示式，所以，這種數(shù)學(xué)模型稱 為線性規(guī)劃模型，相應(yīng)得問(wèn)題叫做線性規(guī)劃問(wèn)題。若(I )中得不等式都為等式且(II)中得變 量為非負(fù)，則叫做線性規(guī)劃模型得標(biāo)準(zhǔn)型。解任一線性規(guī)劃問(wèn)題通用得方法就是單純形法， 但對(duì)于菜些特殊得線性規(guī)劃問(wèn)題也有特殊得解法，這樣更加簡(jiǎn)便。一、單純形法、對(duì)偶理論與靈敏度分析得應(yīng)用問(wèn)題提出在生產(chǎn)管理與經(jīng)營(yíng)活動(dòng)中經(jīng)常提出一類問(wèn)題，即如何合埋利用有限得人力物力財(cái)力等資源， 以便得到最好得經(jīng)濟(jì)效果。菜工廠在計(jì)劃期內(nèi)要安排生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位 產(chǎn)品所需得A、B兩種原材料得消耗童，見(jiàn)下表，試回答下面問(wèn)題：屮乙資源限量(kg)原材料得成本(/kg)原材料A2416

6、01原材料B321802單價(jià)/元1316(1) 應(yīng)如何安排生產(chǎn)計(jì)劃使該工廠獲得得利潤(rùn)最大？(2) 原料A、B得影子價(jià)格各就是多少？那一種更珍貴？(3) 如果乙產(chǎn)品價(jià)格達(dá)到20元/每件，方案會(huì)發(fā)生什么變化？(4) 現(xiàn)有新產(chǎn)品丙可投入開(kāi)發(fā)，一直對(duì)兩種原材料得消耗量分別為3與4,問(wèn)該產(chǎn)品得價(jià)格至 少應(yīng)為多少才值得生產(chǎn)？問(wèn)題分析1、問(wèn)題一：應(yīng)如何安排生產(chǎn)計(jì)劃使該工廠獲得得利潤(rùn)最大？該問(wèn)題為合理利用有限得人力、物力、財(cái)力等資源，以便得到最好得經(jīng)濟(jì)效果得問(wèn)題， 應(yīng)該運(yùn)用線性規(guī)劃原理，建立數(shù)學(xué)模型，再運(yùn)用單純型法或圖解法求解。2、問(wèn)題二：原料A、B得影子價(jià)格各就是多少？那一種更珍貴？影子價(jià)格得經(jīng)濟(jì)意茨就是指

7、在其她條件不變得情況下，單位資源變化所引起得目標(biāo)函數(shù) 得最優(yōu)值得變化，代表A、B這兩種資源得經(jīng)濟(jì)估價(jià)，影子價(jià)格可運(yùn)用對(duì)偶單純型法可求得。3、問(wèn)題三:如果乙產(chǎn)品價(jià)格達(dá)到20元/每件，方案會(huì)發(fā)生什么變化？乙產(chǎn)品價(jià)格變化，表示乙產(chǎn)品得價(jià)值系數(shù)變化，運(yùn)用靈敏度分析，判斷置終經(jīng)濟(jì)效益就是 否會(huì)發(fā)生變化。4、問(wèn)題四：現(xiàn)有新產(chǎn)品丙可投入開(kāi)發(fā)，一直對(duì)兩種原材料得消耗量分別為3與4,問(wèn)該產(chǎn)品 得價(jià)格至少應(yīng)為多少才值得生產(chǎn)？分析在原計(jì)劃中就是否安排一種新產(chǎn)品，運(yùn)用靈敏度分析，通過(guò)單純型表法，求得新產(chǎn)品 得價(jià)格，使總得經(jīng)濟(jì)效益會(huì)增擁。符號(hào)說(shuō)明兀1工廠在計(jì)劃期內(nèi)安排生產(chǎn)甲產(chǎn)品得數(shù)量。X2X廠在計(jì)劃期內(nèi)安排生產(chǎn)乙產(chǎn)品得

8、數(shù)量。Z工廠總得經(jīng)濟(jì)收益。模型建立建立線性規(guī)劃模型目赫函數(shù) max Z = = 13X + 16X., -(2Xj + 4、XJ 2 x(3X】+ 2X.J即:max Z2. X j + 4兀 160+2X 0條件約束：L 2模型求解1 .問(wèn)題一：應(yīng)如何安排生產(chǎn)計(jì)劃使該工廠獲得得利潤(rùn)最大？運(yùn)用單純型表法求解，(1) 寫(xiě)出原模型得標(biāo)準(zhǔn)型：max Z = 5.X + 8X.? + 0X3 + 0.%X.X2尢+ 4X2 + 0兀 3 = 160 3兀 +2尤；+ 0尤4=180得到原始單純形表:C)5800CBXbbx2尤3乙0尤3160241001803201表1對(duì)原始單純形表進(jìn)行迭代計(jì)算得:C

9、j5800CBXbbx2尤3X40X31602410400180320190z05800表2c.5800CBXbb兀x2尤38x2400、510、250800兀100200、5150z3201020表3CjS800CBXbb兀x2尤3駐8x215010、3750、25550100、250. 5Z37000-1 750、5表4（4）計(jì)算結(jié)果就是：工廠在計(jì)劃日期內(nèi)安排生產(chǎn)甲產(chǎn)品得量為50,生產(chǎn)乙產(chǎn)品得量為15。所獲 得得最大利潤(rùn)為370元。2.問(wèn)題二:原料從B得影子價(jià)格各就是多少？那一種更珍貴？由表1得最終結(jié)果表4得:原料A得影子價(jià)格就是厶25、B得影子價(jià)格就是0、5,所以原料 A更珍貴。3問(wèn)題三

10、:如果乙產(chǎn)品價(jià)格達(dá)到20元/每件，方案會(huì)發(fā)生什么變化？乙產(chǎn)品價(jià)格達(dá)到20元/每件；即目標(biāo)函數(shù)中乙產(chǎn)品得價(jià)值系數(shù)改變。maxZ = 5Xj + 12Xn目標(biāo)函數(shù)變?yōu)椋簃axZ =13X1 + 202 +（歐】+ 4-X2） - 2 X（3兀 + ZX2）ci51200CBXbbx2尤3駐x215010、3750、25-X150100、250、5100z370003、250、5即：所以最終單純形表變?yōu)?表5c.51200CBXbbXx2%3X412x2400、510、2500100200、51Z370-1030表6由表6可得如果乙產(chǎn)品價(jià)格達(dá)到20元/每件，工廠得生產(chǎn)方案為生產(chǎn)甲產(chǎn)品得量為0,生產(chǎn)乙

11、 產(chǎn)品得量為40。4問(wèn)題四：現(xiàn)有新產(chǎn)品丙可投入開(kāi)發(fā)，一直對(duì)兩種原材料得消耗量分別為3與4,問(wèn)該產(chǎn)品得 價(jià)格至少應(yīng)為多少才值得生產(chǎn)？假設(shè)新產(chǎn)品丙得價(jià)格為則目標(biāo)函數(shù)變?yōu)椋簃ax Z = 13 + 20X? + C3X3 -+ 4X2 + 3X3) - 2 x(3%, + 2X2 + 4X3)即.msxZ =+(C3 - 11)X3f2X1 + 4X2 + 3X3160 尢 3X + 2XZ + 4.X3 0 條件約束：1123T所以產(chǎn)品得技術(shù)向量為P3 =，然后計(jì)算最終表中對(duì)應(yīng)3得檢系數(shù)為a3 = C3 - CJ3 一*3 =(C3 -11)- (1.75,0.5)(3,4)T = C3- 18.

12、25當(dāng)n30時(shí)，說(shuō)明新產(chǎn)品丙值得生產(chǎn)。即C3 1825,所以新產(chǎn)品丙得價(jià)格至少應(yīng)為18、25o分析結(jié)果1. 問(wèn)題一：應(yīng)如何安排生產(chǎn)計(jì)劃使該工廠獲得得利潤(rùn)最大？工廠在計(jì)劃日期內(nèi)安排生產(chǎn)甲產(chǎn)品得童為50,生產(chǎn)乙產(chǎn)品得量為15o所獲得得最大利潤(rùn)為 370 元。2. 問(wèn)題二：原料A、B得影子價(jià)格冬就是多少？那一種更珍貴？原料A得影子價(jià)格就是2、25, B得影子價(jià)格就是0、5,所以原料A更珍貴。3. 問(wèn)題三:如果乙產(chǎn)品價(jià)格達(dá)到20元/每件，方案會(huì)發(fā)生什么變化？工廠得生產(chǎn)方案為生產(chǎn)甲產(chǎn)品得量為0,生產(chǎn)乙產(chǎn)品得董為40o4問(wèn)題四：現(xiàn)有新產(chǎn)品丙可投入開(kāi)發(fā)，一直對(duì)兩種原材料得消耗量分別為3與4,問(wèn)該產(chǎn)品得 價(jià)格

13、至少應(yīng)為多少才值得生產(chǎn)？新產(chǎn)品丙得價(jià)格至少應(yīng)為18、25。二、圖解法得應(yīng)用問(wèn)題提出某養(yǎng)雞場(chǎng)有1萬(wàn)只雞，用動(dòng)物飼料與谷物飼料混合喂養(yǎng)。每天每只雞平均吃混合飼料0.5kg,1其中動(dòng)物飼料不能少于谷揚(yáng)飼料得乩 動(dòng)物飼料每千克0、9元，谷物飼料每千克0、28元, 飼料公司毎周僅保證供應(yīng)谷物飼料50000kg,問(wèn)飼料怎樣混合，才就是成本最低。符號(hào)說(shuō)明尤為每周需用谷物飼料數(shù)量為動(dòng)物飼料數(shù)童z元?dú)爸芸偟蔑暳腺M(fèi)用模型建立由已知條件得到得線性規(guī)劃模型為：minZ = 0.28JC+0.97/X +7/ 350001Xo, yfo模型求解這就是二維線性規(guī)劃問(wèn)題，可用圖解法求解，先作出滿足約束條件得平面區(qū)域，即可行

14、域S, 如下圖所示：Y、：再作直線0.28X +0：直線 + ?/ = 350鴻盛纟龍丈可行城且離原點(diǎn)最近得直線就是經(jīng)過(guò)1y=亍工6得到飼料混合得最佳喂辱料 =盲趙料得混合既能達(dá)到飼養(yǎng)得要求又就就是i兌，谷物飼料泡莎物飼料455:1得比例混合就是最佳方案。養(yǎng)方案,即當(dāng)谷物伍能使費(fèi)用置閔三、總細(xì)桂L通過(guò)上例分巾來(lái)完成任務(wù)得重#意義。對(duì)線丈 + .?/= 35000了菱汾得了解.能夠熟練掌握這一類問(wèn)題得 解決思路及方法。1. 運(yùn)用用數(shù)學(xué)模型解決現(xiàn)實(shí)中得問(wèn)題，簡(jiǎn)羊合理，清晰明了。2. 在靈敏度分析中，有時(shí)需要用對(duì)偶單純型法，這樣得可使問(wèn)題得處理簡(jiǎn)單化。對(duì)偶單純型-,Q.淸楚地了繆線性規(guī)劃、沆建乘、X得進(jìn)一步分析廿合理安排與規(guī)劃資源,同時(shí)，在餌題分析中也得出了一些認(rèn)識(shí):法得局限主要就是，對(duì)大多數(shù)線性規(guī)劃問(wèn)題，很難找到一個(gè)初始可行基，因而這個(gè)方法在求解 線性規(guī)劃問(wèn)題時(shí)很少單獨(dú)應(yīng)用。3. 用建立線性規(guī)劃得模型解決現(xiàn)實(shí)問(wèn)題必須滿足：(1) 要求解得目標(biāo)函數(shù)能用數(shù)值指標(biāo)來(lái)反映，且為線性函數(shù)；(2) 存在多種方案及有關(guān)數(shù)據(jù)；(3) 要求達(dá)到目標(biāo)就是在一定約束條件下實(shí)現(xiàn)得，這些約束條件可以用線性式或不等式表 示；(4)