生產(chǎn)中的線性規(guī)劃問題

1、實際生產(chǎn)中的線性規(guī)劃問題【摘要】線性規(guī)劃是運籌學(xué)中的一個基本分支，它廣泛應(yīng)用現(xiàn)有的科學(xué)技術(shù)和數(shù)學(xué)方法，解決實際中的問題，幫助決策人員選擇最優(yōu)方針和決策。本文主要 研究如何把線性規(guī)劃的知識運用到企業(yè)、生活生產(chǎn)中，是企業(yè)提高生產(chǎn)效率，生 活生產(chǎn)更加合理。通過建立模型并利用相關(guān)軟件，對生活中有限的資源進(jìn)行合理 分配，從而獲得最佳經(jīng)濟(jì)效益。關(guān)鍵詞線性規(guī)劃數(shù)學(xué)方法合理分配最佳效益【引言】隨著經(jīng)濟(jì)全球化的不斷發(fā)展，企業(yè)面臨更加激烈的市場競爭。企業(yè)必須不斷提高盈利水平，增強(qiáng)其獲利的能力，在成本、生產(chǎn)、運輸、銷售等環(huán)節(jié) 中提高效率，形成企業(yè)的核心競爭力，才能在激烈的市場競爭中立于不敗之地。 在各類經(jīng)濟(jì)活動中，

2、經(jīng)常遇到這樣的問題：在生產(chǎn)條件不變的情況下，如何通過 統(tǒng)籌安排，改進(jìn)生產(chǎn)組織或計劃，合理安排人力、物力資源，組織生產(chǎn)過程，使 總的經(jīng)濟(jì)效益最好。這樣的問題常?？梢曰苫蚪频鼗伤^的“線性規(guī)劃”（Linear Programming，簡記為LP）問題。線性規(guī)劃是應(yīng)用分析、量化的方法，對 經(jīng)濟(jì)管理系統(tǒng)中的人、財、物等有限資源進(jìn)行統(tǒng)籌安排，為決策者提供有依據(jù)的 最優(yōu)方案，以實現(xiàn)有效管理。利用線性規(guī)劃我們可以解決很多問題。如：在不違 反一定資源限制下，組織安排生產(chǎn)，獲得最好的經(jīng)濟(jì)效益（產(chǎn)量最多、利潤最大、 效用最高）。也可以在滿足一定需求條件下，進(jìn)行合理配置，使成本最小。同時 還可以在任務(wù)或目標(biāo)確

3、定后，統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè) 備、原材料、人工、時間等）去完成任務(wù)。下面我們用線性規(guī)劃方法對企業(yè)在生 產(chǎn)中的具體問題進(jìn)行探討。二、線性規(guī)劃的模型線性規(guī)劃是運籌學(xué)的一個重要分支，自1947年丹捷格提出了一般線性規(guī)劃 問題求解的方法-單純形法之后，線性規(guī)劃在理論上趨向成熟，在實際中日益廣 泛與深入。特別是在電子計算機(jī)能處理成千上萬個約束條件和決策的線性規(guī)劃問 題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了。以前人們在用這個模型求解時計算非常麻煩，而近幾十多年來，由于電子計 算機(jī)應(yīng)用的飛速發(fā)展，應(yīng)用計算機(jī)處理線性規(guī)劃問題使人們求解變得越來越容易 了。LINDO軟件是解決線性規(guī)劃問題的有力

4、工具，它可用于解決50000個約束 條件，20000個變量的線性規(guī)劃問題，所以線性規(guī)劃的具體運用也越來越受管理 者的重視了。一、線性規(guī)劃在企業(yè)中的應(yīng)用下面我們從企業(yè)在進(jìn)行制定生產(chǎn)計劃、設(shè)備使用、材料的使用、配料分配、 運輸、廣告促銷、企業(yè)決策等幾方面看看如何運用線性規(guī)劃使企業(yè)得到最優(yōu)方案。 例1（生產(chǎn)計劃問題）假設(shè)某廠計劃生產(chǎn)甲、乙兩種產(chǎn)品，其主要原材料有鋼材 3600kg，銅材 2000kg及專用設(shè)備能力3000臺時，己原材料和設(shè)備的單間消耗定額以及單位產(chǎn) 品所獲利潤如下表所示（表1-1）。問如何安排生產(chǎn)方使該廠所獲利潤最大？表1-1消耗定頷、產(chǎn)品甲（件）乙 （件）現(xiàn)有材料及設(shè)備能力鋼材94

5、3600 (kg)銅材4520CO (kg)設(shè)備能力31030C0 (臺時)單位產(chǎn)品利潤（元）70120為了求解這一問題，設(shè)甲、乙兩種產(chǎn)品的計劃產(chǎn)量分別為X ,X件。生產(chǎn)這兩種 產(chǎn)品所消耗的鋼材總數(shù)量為9氣+ 4，但現(xiàn)在只有鋼材3600kg，因此，應(yīng)有19x +4x 3600類似地，可以得到124號 + 5x2 20003x1 + 10j:2 3000顯然，由于各種產(chǎn)品的數(shù)量不能為負(fù)數(shù)，我們還有并且，總利潤為z 二 70沔 +1202綜合起來，可以把這個問題的數(shù)學(xué)形式表達(dá)成maz 古=7。西 +120+4叱 3600;4al + 5a2 2000,I 3況十54勺 40;斗八乏口-二、線性規(guī)劃

6、在企業(yè)中的決策應(yīng)用、確定型決策確定型決策是指面對的問題的相關(guān)因素是確定的，從而建立的決策模型的各種參 數(shù)是確定的。解決確定型決策問題的方法有線性規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃等 等，而我要介紹的是線性規(guī)劃。線性規(guī)劃是最基本也是最常用的一種數(shù)學(xué)模型。 為了把一個實際問題用線性規(guī)劃的方法求解，需要建立數(shù)學(xué)模型。線性規(guī)劃問題 的標(biāo)準(zhǔn)為：目標(biāo)函數(shù)maxZ= U cjx.=1 jj一 一 aijx=bl約束條件 s.t. j=1（i=1,2,，m;j=1,2,，n）宇。b z 0建立標(biāo)準(zhǔn)型的好處在于：我們可以只針對這種標(biāo)準(zhǔn)形式來研究它的求解方法。至 于其它各種形式的線性規(guī)劃問題，可以先將非標(biāo)準(zhǔn)型變成標(biāo)準(zhǔn)型，

7、然后在用標(biāo)準(zhǔn) 型的求解方法求解。線性規(guī)劃問題的求解方法有圖解法，單純形法，表解式的單 純形法。其中單純形法的計算步驟為：(1)找出初始可行基(或用增加新變量 的方法創(chuàng)造初始可行基)建立初始單純形表。檢查所有的zj-cj。如果全部的zj-cjNO,則改解為最優(yōu)解。反之，說明改 解不是最優(yōu)解。選擇具有最小檢驗數(shù)的非基變量為換入變量。它所對應(yīng)的那一列稱為主列。用主列元素中的每一個大于0的系數(shù)去除同行的限定系數(shù)(或稱右項)， 取比值最小的那一行所對應(yīng)的基變量為換出變量。把換出變量的那一行，除以該行主列元素的系數(shù)。進(jìn)行行變換，使換出變量那一行之外的全部主列元素變成0.重復(fù)第二步，直到?jīng)]有新的非基變量可以

8、改善目標(biāo)函數(shù)為止。案例：在企業(yè)投資決策中，經(jīng)常需要用到線性規(guī)劃。例如：隨著人們經(jīng)濟(jì) 水平的不斷提高，某投資商決定投資建汽車廠生產(chǎn)大轎車和載重汽車兩種型號的 的汽車，已知生產(chǎn)每輛汽車所用的鋼材都是2噸/輛，該工廠每年的供應(yīng)的鋼材 為1600噸，工廠的生產(chǎn)能力是載重汽車2.5小時/輛，大轎車5小時/輛，工 廠全年的有效工時為2500小時；已知供應(yīng)給該廠的大轎車用的座椅400輛/年。 據(jù)市場調(diào)查，出售一輛大轎車可獲利4千元，出售一輛載重汽車可獲利3千元. 問在這些條件下，該投資商如何安排生產(chǎn)才能使工廠獲利最大？1、分析與建模：該問題是在有限資源約束下求利潤最大化的問題，設(shè)x1為生產(chǎn)大汽車的數(shù)量，x2

9、為生產(chǎn)載重汽車的數(shù)量.模型：maxZ=4x1+3x2ST: 2x1+2x2W16005x1+2.5x2W2500 x1W400 x1N0, x2N01、模型求解(表解式單純形法)增加三個變量x3,x4,x5,先將該問題化成標(biāo)準(zhǔn)型：maxZ=4x1+3x2ST: 2x1+2x2+x3=16005x1+2.5x2+x4=2500 x1+x5=400 x1,x2, x3,x4,x5N0表解形式如表:c1X302X403X50 x1600250040080050040012345X X X X X12210052.5010 0001300014z.5z.-c.X3X4X1400-4-3002102.5

10、01000-21-501800500400400200zj z.-c.400041600000041X0001-0.824002002330100.4-2200324100014004004z.z.-c.4301.2-2220050001.2-21X0000.5-0.41200253011-0.406003乂2410-0.50.402004zj z-c.4310.402600最優(yōu)50010.40解從表中可得，該工廠生產(chǎn)200輛大汽車，600輛載重汽車所得到的利潤最大為maxZ=4x1+3x2=2600 （千元） 、不確定型決策如果決策問題涉及的條件中有些是未知的，對一些隨機(jī)變量，連它們的概率分

11、布 也不知道，這類問題被稱為不確定型決策。不確定型決策的基本準(zhǔn)則有：1.樂觀法（又稱最大最大準(zhǔn)則）：采用這種方法的基本出發(fā)點是對未來的客觀情 況總是抱樂觀態(tài)度。其基本步驟是:找出個方案在不同自然狀態(tài)下的最大益損值; 取各方案最大益損值的最大者為決策方案。例如：某企業(yè)打算生產(chǎn)某產(chǎn)品。據(jù)市場預(yù)測分析，產(chǎn)品銷路有三種可能性：銷路 好、一般和差。生產(chǎn)該產(chǎn)品有三種方案：改進(jìn)生產(chǎn)線、新建生產(chǎn)線、外包生產(chǎn)。 各種方案的收益值如表：項目銷路好銷路一般銷路差改進(jìn)生產(chǎn)線180120-40新建生產(chǎn)線240100-80外包生產(chǎn)1007016在本例中，三種方案的最大收益依次為180、240、100，其中第二種方案對應(yīng)的

12、 值最大，所以選擇新建生產(chǎn)線的方案。悲觀法（又稱最大最小準(zhǔn)則）：采用這種方法的基本出發(fā)點是對未來的客觀 情況總是抱悲觀態(tài)度，然后在最壞的情況下有爭取最好的可能。其基本步驟是： 找出各行動的方案在不同自然狀態(tài)下的最小益損值；找各方案最小益損值的最大 者。仍以上個案例為例：三種方案的最低收益依次為40，-80，16,其中第三種 方案對應(yīng)的值最大，所以選外包生產(chǎn)的方案。3、后悔值法（又稱最小最大原則）：決策者在選擇了某方案后，若事后發(fā)現(xiàn)客 觀情況并未按自己預(yù)想的發(fā)生，會為自己事前的決策而后悔。由此，產(chǎn)生了最小 最大后悔值決策方法，其步驟是：（1）計算每個方案在每種情況下的后悔值，定 義為：后悔值二該

13、情況下的各方案的最大收益-該方案在該情況下的是收益（2）找出各方案的最大后悔值；（3）選擇最大后悔值中最小的方案。仍以上例為例，得到關(guān)于后悔值的表格為：項目銷路好銷路一般銷路差最大后悔值改進(jìn)生產(chǎn)線180120-4060新建生產(chǎn)線240100-8096外包生產(chǎn)1007016140從表格中可以看出，其中第一方案對應(yīng)的最大后悔值最小，所以選擇改進(jìn)生產(chǎn)線 的方案。、風(fēng)險型決策方法如果決策問題涉及的條件中有些是隨機(jī)因素，它雖然是不確定型的，但是知道它 的概率分布，這類決策被稱為風(fēng)險型決策。解決風(fēng)險型決策問題常用的決策原則 有最大可能原則、渴望水平原則和期望值最大原則。1、最大可能原則：按最大概率的自然狀

14、態(tài)進(jìn)行決策。這種原則適用于在一組自 然狀態(tài)中某種狀態(tài)出現(xiàn)的概率特別大，而其它狀態(tài)下各行動方案的益損值差別不 大的情況。2、渴望水平原則：預(yù)先給出收益的一個渴望水平A,對每一個行動，都求出其收 益達(dá)到渴望水平A的概率。使這個概率最大的行動就是渴望水平原則下的最優(yōu)行 動.3、期望值最大原則：用期望值法進(jìn)行決策是把每個行動方案的期望值求出來， 加以比較，然后選擇期望值最大（當(dāng)目標(biāo)是利潤時）或期望值最?。ó?dāng)目標(biāo)是損 失時）的行動方案。在很多情況下，利用決策樹來表示決策過程是很方便的。決策樹中，口表示決 策點，從它引出的分支叫方案分支，分支數(shù)反映可能的行動方案數(shù)；。一表示機(jī) 會節(jié)，從它引出的分支叫事件分

15、支或概率分支，每條分支上寫明自然狀態(tài)及其出 現(xiàn)的概率，分支數(shù)反映可能的自然狀態(tài)數(shù)。一表示結(jié)果節(jié)點，它旁邊的數(shù)值是 每個方案在相應(yīng)的自然狀態(tài)下的效益值。在機(jī)會節(jié)點上方的數(shù)字是各機(jī)會或方案 的期望值，在決策點，經(jīng)過比較將期望值最大的一支保留，其它各支去掉，稱為 剪枝。最后決策點上方的數(shù)字就是最優(yōu)方案的期望值。下面舉例說明利用決策樹 來進(jìn)行決策的方法。例如：為生產(chǎn)某種產(chǎn)品，設(shè)計了兩個基建方案：一是建大廠， 二是建小廠。大廠需要投資300萬元，小廠需要投資160萬元，兩者的使用期都 是10年。估計在此期間，產(chǎn)品銷路好的可能性是0.7，兩個方案的年度損益值 如表：自然狀態(tài)概率建大廠建小廠銷路好0.710040銷路差0.3-2010解決該問題的步驟:（1）畫決策樹（2）計算各點的益損期望值：點2： 0.7X100X10年+0.3X （-20） X10