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

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

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

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

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

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

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

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

8、數(shù)量。Z工廠總得經(jīng)濟收益。模型建立建立線性規(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 .問題一：應(yīng)如何安排生產(chǎn)計劃使該工廠獲得得利潤最大？運用單純型表法求解，(1) 寫出原模型得標準型：max Z = 5.X + 8X.? + 0X3 + 0.%X.X2尢+ 4X2 + 0兀 3 = 160 3兀 +2尤；+ 0尤4=180得到原始單純形表:C)5800CBXbbx2尤3乙0尤3160241001803201表1對原始單純形表進行迭代計算得: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）計算結(jié)果就是：工廠在計劃日期內(nèi)安排生產(chǎn)甲產(chǎn)品得量為50,生產(chǎn)乙產(chǎn)品得量為15。所獲 得得最大利潤為370元。2.問題二:原料從B得影子價格各就是多少？那一種更珍貴？由表1得最終結(jié)果表4得:原料A得影子價格就是厶25、B得影子價格就是0、5,所以原料 A更珍貴。3問題三

10、:如果乙產(chǎn)品價格達到20元/每件，方案會發(fā)生什么變化？乙產(chǎn)品價格達到20元/每件；即目標函數(shù)中乙產(chǎn)品得價值系數(shù)改變。maxZ = 5Xj + 12Xn目標函數(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)品價格達到20元/每件，工廠得生產(chǎn)方案為生產(chǎn)甲產(chǎn)品得量為0,生產(chǎn)乙

11、 產(chǎn)品得量為40。4問題四：現(xiàn)有新產(chǎn)品丙可投入開發(fā)，一直對兩種原材料得消耗量分別為3與4,問該產(chǎn)品得 價格至少應(yīng)為多少才值得生產(chǎn)？假設(shè)新產(chǎn)品丙得價格為則目標函數(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 =，然后計算最終表中對應(yīng)3得檢系數(shù)為a3 = C3 - CJ3 一*3 =(C3 -11)- (1.75,0.5)(3,4)T = C3- 18.

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

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

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