線性規(guī)劃在企業(yè)決策中的應用

頁眉線性規(guī)劃在企業(yè)決策中的應用第一章

線性規(guī)劃理論線線性規(guī)劃是運籌學中研究較早發(fā)展較快應用廣泛方法較成熟的一個重要分支,它是輔助人們進行科學管理的一種數(shù)學方法.在濟管理、交通運輸、工農業(yè)生產(chǎn)等經(jīng)濟活動中，提高經(jīng)濟效果是人們不可缺少的要求，而提高經(jīng)濟效果一般通過兩種途徑：一是技術方面的改進，例如改善生產(chǎn)工藝，使用新設備和新型原材.是生產(chǎn)組織與計劃的改進，即合理安排人力物力資源.線性規(guī)劃所研究的是：在一定條件下，合理安排人力物力等資源，使經(jīng)濟效果達到最好.一般地，求線性目標函數(shù)在線性約束條件下的最大值或最小值的問題稱為線性規(guī)劃問題

足線性約束條件的解叫做可行解，由所有可行解組成的集合叫做可行域[2]

決策變量約束條件目標函數(shù)是線性規(guī)劃的三要素。線法國數(shù)學家J.-B.-J.傅里葉和C.瓦萊－普森分別于18321911年獨立地提出線性規(guī)劃的想法，但未引起注意。1939蘇聯(lián)數(shù)學家Л.В.康托羅維奇在《生產(chǎn)組織與計劃中的數(shù)學方法》一書中提出線性規(guī)劃問題，也未引起重視。1947年美國數(shù)學家丹齊克提出線性規(guī)劃的一般數(shù)學模型和求解線性規(guī)劃問題的通用方法──純形法，為這門學科奠定了基礎。1947年美國數(shù)學家J.von諾伊曼提出對偶理論開創(chuàng)了線性規(guī)劃的許多新的研究領域，擴大了它的應用范圍和解題能力。1951年美國經(jīng)濟學家T.C.庫普曼斯把線性規(guī)劃應用到經(jīng)濟領域，為此與康托羅維奇一起獲1975諾貝爾經(jīng)濟學獎。50代后對線性規(guī)劃進行大量的理論研究涌現(xiàn)出一大批新的算法如1954頁眉年C.萊姆基提出對偶單純形法年斯和薩迪等人解決了線性規(guī)劃的靈敏度分析和參數(shù)規(guī)劃問題1956A.塔克提出互補松弛定理1960G.B.丹齊克和P.沃夫提出分解算法等。線性規(guī)劃的研究成果還直接推動了其他數(shù)學規(guī)劃問題包括整數(shù)規(guī)劃、隨機規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計算機的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如，，可以很方便地求解幾千個變量的線性規(guī)劃問題[1979蘇聯(lián)數(shù)學家L.Khachian提出解線性規(guī)劃問題的橢球算法明它是多項式時間算法。1984年美國貝爾電話實驗室的印度數(shù)學家N.卡馬卡提出解線性規(guī)劃問題的新的多項式時間算法用這種方法求解線性規(guī)劃問題在變量個數(shù)為5000時只要單純形法所用時間的1/50。現(xiàn)已形成線性規(guī)劃多項式算法論。50年代后線性規(guī)劃的應用范圍不斷擴大。建立線性規(guī)劃模型的方法。線3.1線性規(guī)劃問題的提出在生產(chǎn)管理和經(jīng)營活動中經(jīng)常提出一類問題如何合理地利用有限的人力、財力等資源，以便得到最好的經(jīng)濟效果。線性規(guī)劃主要解決兩類問題：資源有限，要求生產(chǎn)的產(chǎn)品（或利潤）最多。任務（或產(chǎn)品）一定，要求消耗的資源（或成本）最少。3.2線性規(guī)劃問題的特征（1）一個問題都用一組決策變量就有代表一過具體方案。

(x,x...x)12

表示某一方案；這組決策變量的值一般這些變量取值是非負的。存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示。都有一個要求達到的目標，它可用決策變量的線性函數(shù)（稱為目標函數(shù)）來表示。按問題的不同，要求目標函數(shù)實現(xiàn)最大化或最小化。滿足以上四個條件的數(shù)學模型稱為線性規(guī)劃的數(shù)學模型。3.3從實際問題中建立數(shù)學模型的步驟；頁眉根據(jù)影響所要達到目的的因素找到?jīng)Q策變量；由決策變量和所在達到目的之間的函數(shù)關系確定目標函數(shù)；（3）由決策變量所受的限制條件確定決策變量所要滿足的約束條件。3.4所建立的線性規(guī)劃模型的特點；（）每個模型都有若干個決策變量

(x,x...x)12

，其中

為決策變量個數(shù)。決策變量的一組值表示一種方案，同時決策變量一般是非負的。（2）目標函數(shù)是決策變量的線性函數(shù)，根據(jù)具體問題可以是最大化max

或最小化min

，二者統(tǒng)稱為最優(yōu)化

opt

（3）約束條件也是決策變量的線性函數(shù)。3.5線性規(guī)劃模型的一般形式目標函數(shù)：

maxxx1n

約束條件：

111221nn1x21122n2x1mnnm,x,x1n

在線性規(guī)劃的數(shù)學模型中，方程（3-1稱為目標函數(shù)；（3-2）稱為約束條件。3.6線性規(guī)劃模型的標準形式x1nxx111121nnxxnxm11mnx,x,,x1n

n?

其中

b,mi

.簡寫形式為：nzcxjj

j

jb頁眉St

naxijjijxj

iLm;j1,2,L

向量和矩陣表示：其中

maxCXjjjjnj,,c)，1

X=

a,j

2線求解線性規(guī)劃問題的基本方法有圖解法和單純形法，但實際運用的主要是是單純形法，現(xiàn)在已有單純形法的標準軟件，可在電子計算機上求解約束條件和決策變量數(shù)達10000個以上的線性規(guī)劃問題。為了提高解題速度，又有改進單純形法、對偶單純形法、原始對偶方法、分解算法和各種多項式時間算法。對于只有兩個變量的簡單的線性規(guī)劃問題，也可采用圖解法求解。這種方法僅適用于只有兩個變量的線性規(guī)劃問題[的特點是直觀而易于理解但實用價值不大不過通過圖解法求解可以理解線性規(guī)劃的一些基本概念。下面著重介紹單純形法。4.1一般線性規(guī)劃問題的單純形解法4.1.1建立初始基本可行解在線性規(guī)劃問題中，約束條件多為不等式，所以首先要將其化為標準型，同時建立一個初始基本可行基。4.1.2最優(yōu)解檢驗找到一個可行判斷它是不是最優(yōu)解。判斷方法是檢驗目標函數(shù)中是否還有正的系數(shù)，若有正的系數(shù)，則說明還有更好的解。只有當目標函數(shù)中的全部系數(shù)為負值或頁眉時，說明改解才是最優(yōu)解。4.1.3基變換從一個基可行解到另一個基可行解的變換就是進行一次基變換。4.1.4迭代（旋轉運算）將約束條件的增廣矩陣中新基變量的系數(shù)通過矩陣的行變換或Gauss變換變?yōu)閱挝痪仃嘯6]

。4.2非標準型線性規(guī)劃問題的解法4.2.1大法在一個線性規(guī)劃問題的約束條件中加入人工變量后，要求人工變量對目標函數(shù)的取值無影響，為此可取人工變量在目標函數(shù)中的系數(shù)為(

M為非常大的正數(shù))[7]

，這樣目標函數(shù)要實現(xiàn)最大化，人工變量只能取零，因此必須把人工變量從基變量中換出，否則目標函數(shù)就不可能實現(xiàn)最大化。4.2.2兩階段法第一階段：不考慮原問題是否存在基可行解，給原線性規(guī)劃問題加上人工變量，構造僅含人工變量的目標函數(shù)和要求實現(xiàn)最小化。第二階段：將第一階段得到的最優(yōu)單純形表，除去人工變量，將原目標函數(shù)的系數(shù)換掉該表的目標函數(shù)的系數(shù)行，作為第二階段計算的初始表。4.3對偶分析4.3.1對偶問題的基本概念在線性規(guī)劃問題中，如果把一個求最大值的線性規(guī)劃定義為“”題，那么與其同時存在一個求最小值的所謂對偶問題，并且原線性規(guī)劃的最優(yōu)解對應著對偶線性規(guī)劃問題的最優(yōu)解。4.3.2對偶問題的性質對稱性對偶問題的對偶是原問題。弱對偶性若X*是原問題的可行解，Y*是對偶問題的可行解。則存在CX*

。（）無界性解。

若原問題（對偶問題）為無界解，則其對偶問題（原問題）無可行（4）可行解是最優(yōu)解時的性質

設X

是原問題的可行解Y

是對偶問題的可行jjij頁眉解，

時，X

,

是最優(yōu)解。（5）對偶定理若原問題有最優(yōu)解，那么對偶問題也有最優(yōu)解且最優(yōu)值相同。（）互補松馳性若X分別是對偶問題和原問題的可行解。那么,且僅當,為最優(yōu)解。4.4靈敏度分析靈敏度分析主要有以下幾種情況[資源數(shù)量變化的分析；目標函數(shù)中價值系數(shù)的變化分析；技術系數(shù)的變化；約束條件增減的變化分析。

X

和第二章

頁眉企業(yè)決策理論企隨著企業(yè)計算機應用和信息化程度的不斷深入業(yè)已經(jīng)積累了大量的業(yè)務和財務數(shù)據(jù)，并繼續(xù)隨著時間和業(yè)務的發(fā)展而呈幾何級膨脹趨勢。企業(yè)信息處理部門的工作重點已逐漸超越了簡單的數(shù)據(jù)收集，企業(yè)內的各級人員都希望能夠快速、準確并方便有效地從這些大量雜亂無章的數(shù)據(jù)中獲取有意義的信息，決策者也希望能夠充分利用現(xiàn)有的數(shù)據(jù)指導企業(yè)決策和發(fā)掘企業(yè)的競爭優(yōu)勢9]策效率和決策質量的高低將直接影響企業(yè)的運營績效和市場競爭力。由于集團企業(yè)具有分布、異構、自治等特點，集團企業(yè)運營過程中的決策將是一個復雜的過程，對于不同的決策問題需要采用不同的決策方法。同時，在集團企業(yè)運營過程中，決策的形式也是多種多樣的，它在一定的階段表現(xiàn)為個體的行為，在一定的階段又表現(xiàn)為群體的活動，從而給集團企業(yè)管理中的決策分析提出了高要求。企2.1按重要程度分類在企業(yè)的決策中，我們按重要程度分類一般把決策分為三個層次，即戰(zhàn)略決策、戰(zhàn)術決策和業(yè)務決策[10]。2.1.1戰(zhàn)略決策第一類戰(zhàn)略決策是與管理總的方針和開發(fā)企業(yè)所需要的資源有關的決策，它屬于長遠規(guī)劃，對企業(yè)的發(fā)展具有深遠影響，決策過程中要考慮很多不確定和冒風險的因素。是集團企業(yè)決策信息模型中的最高層，負責管理、控制、協(xié)調整個集團企業(yè)網(wǎng)絡的正常運行。其控制范圍包括涉及集團企業(yè)全體成員整體利益的事務和對整個企業(yè)集團運營活動的調控與制約。在這一層次，可以設定集團企業(yè)決策模型的范圍和內容、集團企業(yè)的合作機制和行為準則的設定、運營過程的績效評價、利益分配機制和風險控制機制等任務，為集團企業(yè)正常運營提供了戰(zhàn)略決策框架和行動指南。根據(jù)集團企業(yè)實際情況進行群體決策，擔負著全局優(yōu)化以及在新機遇下的集團企業(yè)組建過程中的決策工作。頁眉2.1.2戰(zhàn)術決策第二類決策稱為戰(zhàn)術決策，是在物資資源、設備等決策之后，規(guī)劃如何最有效的分配所獲得的資源（如生產(chǎn)能力、資金、材料、勞力等），以便獲得最大效益。定義集團企業(yè)各成員企業(yè)的各種基本決策活動過程。雖然由于集團企業(yè)的動態(tài)特性，各企業(yè)的實際情況和操作流程會有所不同，但我們總能找到一些存在于企業(yè)業(yè)務活動中相對穩(wěn)定且有相同或類似行為特征的實體。同時也能找出系統(tǒng)中不能再分的最小粒度的原子過程利O術我們將企業(yè)中的各類實體和原子過程封裝成對象根據(jù)產(chǎn)品結構信息和集團企業(yè)實際運行狀態(tài)信息，將客戶的訂單分解到集團企業(yè)的各成員企業(yè)，并派生出由不同的原子過程組成的工作流，對資源進行分配，并完成對工作流監(jiān)督、控制的任務。2.1.3業(yè)務決策第三類叫業(yè)務決策，完成集團企業(yè)具體任務的執(zhí)行工作，包括物流在各企業(yè)間的合理流動以及從原材料到成品的物理加工過程，如原材料的運輸、零件加工、部件裝配、檢測、倉儲等過程。在本層中，完成制造、銷售、供應、運輸?shù)热蝿盏耐瑫r，還要對第一線的信息進行采集、整理、反饋以供上層決策時使用。是在資源合理分配后，進行日常業(yè)務和計劃的決策，線性規(guī)劃模型最適合進行戰(zhàn)術決策，解決諸如勞動力和生產(chǎn)能力等資源的合理分配，運輸和指派方案的最優(yōu)選擇、廣告和推銷費用的預算等問題，同時它也在投資方案選擇、配料、選址、生產(chǎn)計劃、環(huán)境（如空氣、水）污染控制、下料等優(yōu)化方面有廣泛的應用。2.2按企業(yè)決策的環(huán)境分類在企業(yè)的決策中，我們按企業(yè)決策的環(huán)境可分為確定性決策、風險決策和不確定性決策。2.2.1確定性決策確定性決策是指未來環(huán)境完全可預測，而且在此確定的未來環(huán)境下待選擇的決策方案的后果也是可以確定的。簡單講，就是一種方案只有一種確定的結果。2.2.2風險決策風險決策是指未來環(huán)境有幾種可能的狀態(tài)和相應的后果，人們無法得到關于未來環(huán)境的充分可靠的信息，但可以預測每一種狀態(tài)和后果出現(xiàn)的概率。對利潤、效益等問題的決策一般都是風險型決策頁眉2.2.3不確定性決策不確定性決策是指未來環(huán)境出現(xiàn)某種狀態(tài)的概率難以估計甚至連可能出現(xiàn)的狀態(tài)和相應的后果都是未知的。這類決策，主要依靠決策者的經(jīng)驗和主觀判斷。2.3按企業(yè)決策的主體分類在企業(yè)的決策中，我們按企業(yè)決策的主體可分為個人決策和群體決策。個人決策個人決策是指決策的主體是一個人，即最終方案的選擇僅僅由一個人拍板決定。2.3.2群體決策群體決策是指決策的主體是兩人或兩人以上。企業(yè)中許多重要的決策都是由決策群體制定的，屬于群體決策。2.4按企業(yè)決策的目標分類在企業(yè)的決策中，我們按決策目標可分為單目標決策和多目標決策。2.4.1單目標決策單目標決策是指決策行動只要求實現(xiàn)一種目標，此種決策相對比較簡單。2.4.2多目標決策多目標決策是指一項同時需要實現(xiàn)多個目標的決策。在做出一項復雜決策時，需要妥善處理好多個目標的沖突問題。應用線性規(guī)劃方法解決企業(yè)決策問題時，求解方法已經(jīng)不存在問題，各種大型求解線性規(guī)劃問題的計算機程序到處可以找到，使用也比較方便，應用中的主要問題是根據(jù)實際情況建立合理的線性規(guī)劃模型，這是從事系統(tǒng)分析工作者的主要工作下面將介紹線性規(guī)劃模型的特點和建模的基本步驟，并列舉若干實例來說明線性規(guī)劃在企業(yè)決策中的應用。第三章

頁眉線性規(guī)劃在企業(yè)生產(chǎn)策中的應用舉例企業(yè)生產(chǎn)決策是根據(jù)企業(yè)的經(jīng)營戰(zhàn)略方案及企業(yè)內外經(jīng)營環(huán)境的狀況確定企業(yè)的生產(chǎn)方向、生產(chǎn)目標、生產(chǎn)方針及生產(chǎn)方案的過程或職能。生產(chǎn)決策的主要內容包括：工藝和設備決策（自然技術水平?jīng)Q策）、產(chǎn)品成本決策（生產(chǎn)成本決策）和生產(chǎn)類型與廠址決策。企業(yè)在生產(chǎn)產(chǎn)品的時候，往往會考慮許多的生產(chǎn)因素，如既希望其利潤大，而且又希望產(chǎn)量高、消耗低、質量好、投入少等；又如要開發(fā)一塊土地建設物流中心，既要考慮設施的配套性、先進性，還要考慮投資的大小等問題[12]介紹運用運籌學中的線性規(guī)劃的方法來解決企業(yè)實際生產(chǎn)決策問題。線

。下面將舉例在企業(yè)的各項管理活動中,例如計劃、生產(chǎn)、運輸、技術等問題，線性規(guī)劃是指從各種限制條件的組合中，選擇出最為合理的計算方法，建立線性規(guī)劃模型從而求得最佳結果。線性規(guī)劃在企業(yè)管理決策中的應用頗為廣泛，現(xiàn)在只是對其簡單進行介紹和應用。作為運籌學重要分支的線性規(guī)劃，經(jīng)歷了長期的實踐和多方面的應用。18紀線性規(guī)劃的最先提出，至今已有一百多年的歷史，在其發(fā)展的過程中不斷完善，隨著現(xiàn)代計算機、電子等技術的發(fā)展和應用，線性規(guī)劃的應用一定會越來越廣泛12]

。1.1企業(yè)決策中應用線性規(guī)劃的條件一般來講，一個企業(yè)決策問題滿足以下條件時，才能建立線性規(guī)劃模型。（1）要就求解問題的目標函數(shù)能用數(shù)值指標來反映，且為線性函數(shù)。存在多種方案及有關數(shù)據(jù)。要求達到的目標是在一定的約束條件下實現(xiàn)的，這些約束條件可用線性等式或不等式來描述。1.2線性規(guī)劃在企業(yè)決策中的應用范圍線性規(guī)劃在企業(yè)決策中的應用廣泛，主要有以下八種形式12]

：（1）產(chǎn)品生產(chǎn)計劃決策：合理利用人力、物力、財力等，是獲利最大。（2）勞動力安排決策：用最少的勞動力來滿足工作的需要。運輸問題決策：如何制定運輸方案，使總運費最少。合理利用線材問題決策：如何下料，使用料最少。頁眉配料問題決策：在原料供應的限制下如何獲得最大利潤。投資問題決策：從投資項目中選取方案，是投資回報最大。庫存問題決策：在市場需求和生產(chǎn)實際之間，如何控制庫存量從而獲得更高利益。最有經(jīng)濟計劃問題決策：在投資和生產(chǎn)計劃中如何是風險最小。1.3企業(yè)決策中應用線性規(guī)劃模型的假設條件在上文中已經(jīng)隱含著線性規(guī)劃問題的實質及建立這種模型的假設條件。為了更嬌明確起見把它們歸納為下面四條[便我們很容易判斷所遇到的某個企業(yè)決策問題能否用一個線性規(guī)劃模型去求最優(yōu)解。比例性：指對每個單獨的活動而言，“因”果”成正比關系。對于目標函數(shù)來說，如果出售一輛大轎車可獲利千元的話，那么出售兩輛就可獲利千元。對于約束條件來說如果生產(chǎn)一輛大轎車用噸鋼材的話那生產(chǎn)兩輛大轎車就要用4噸鋼材，等等?？杉有裕菏侵赶嗤摹耙蚧颉肮g的可加性。汽車廠總的利潤是出售大轎車的利潤和出售載重汽車的利潤和。同樣，全廠消耗的鋼材是生產(chǎn)兩種汽車各自用掉的鋼材數(shù)量的總和。可分性：在有些情況下，未知變量只有是整數(shù)時才有物理意義，然而用線性規(guī)劃計算得結果卻經(jīng)常是非整數(shù)。所以可以可分性是假定每個位置變量所代表的實際活動可以分成為部分，允許結果出現(xiàn)非整數(shù)的值。對于未知變量只有是整數(shù)時才有物理意義的情況，要用整數(shù)規(guī)劃才能得到滿意的最優(yōu)解。確定性：假定模型內所有的系數(shù)都是已知的常數(shù)。1.4企業(yè)決策中建立線性規(guī)劃模型的步驟確定決策變量：決策變量是指決策人可以控制的變量，也是線性規(guī)劃問題的解。確定目標函數(shù)是決策人用來評價解的優(yōu)劣的標準，它是決策變量的函數(shù)，可以預測出決策變量的取值對目標的影響。確定約束條件：約束條件是由給定問題的特點家在變量取值上面的限制。另外還規(guī)定線性規(guī)劃中所有變量都滿足非負的條件企頁眉2.1問題提出某工廠在計劃期內要安排生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需種原材料的消耗量，見下表，試回答下面問題：表原料消耗表

原材料A原材料單價/元

甲13

乙4216

資源限量(kg)160180

原材料的成本（1）應如何安排生產(chǎn)計劃使該工廠獲得的利潤最大？（2）原料,

的影子價格各是多少？那一種更珍貴？（）假定市場上有原料A

出售，企業(yè)是否應該購入以擴大生產(chǎn)？在保持原方案不變的前提下，最多應購入多少？可增加多少利潤？如果乙產(chǎn)品價格達到元/件，方案會發(fā)生什么變化？現(xiàn)有新產(chǎn)品丙可投入開發(fā)一直對兩種原材料的消耗量分別為和4問該產(chǎn)品的價格至少應為多少才值得生產(chǎn)？2.2問題分析一個過程的最優(yōu)決策具有這樣的性質，即無論其初始狀態(tài)及其初始決策如何，其以后諸決策對以第一個決策所形成的狀態(tài)作為初始狀態(tài)都必須構成最優(yōu)決策。最優(yōu)化原則描述了最優(yōu)控制決策的基本性質，它建立在不變嵌入原則的基本概念上。當求解一個特殊的最有決策問題時，可以把原來的問題嵌入一個較容易解的類似問題之中[（1）問題一：應如何安排生產(chǎn)計劃使該工廠獲得的利潤最大？該問題為合理利用有限的人力、物力、財力等資源，以便得到最好的經(jīng)濟效果的問題，應該運用線性規(guī)劃原理，建立數(shù)學模型，再運用單純型法或圖解法求解。（2）問題二：原料A,B的影子價格各是多少？那一種更珍貴？影子價格的經(jīng)濟意義是指在其他條件不變的情況下資源變化所引起的目標函數(shù)的最優(yōu)值的變化，代表

,

這兩種資源的經(jīng)濟估價，影子價格可運用對偶單純型法可求得。（3）問題三：假定市場上有原

頁眉出售，企業(yè)是否應該購入以擴大生產(chǎn)？在保持原方案不變的前提下，最多應購入多少？可增加多少利潤？假定市場上有原料A

出售，表示原料A

的數(shù)量可以增加，運用資源數(shù)量變化的分析，判斷原料

的數(shù)量在那一范圍內變化，經(jīng)濟效益會增加。（4）問題四：如果乙產(chǎn)品價格達到元/件，方案會發(fā)生什么變化？乙產(chǎn)品價格變化表示乙產(chǎn)品的價值系數(shù)變化運用靈敏度分析判斷最終經(jīng)濟效益是否會發(fā)生變化。（5）問題五；現(xiàn)有新產(chǎn)品丙可投入開發(fā)，一直對兩種原材料的消耗量分別為34，問該產(chǎn)的價格至少應為多少才值得生產(chǎn)？分析在原計劃中是否安排一種新產(chǎn)品，運用靈敏度分析[通過單純型表法，求得新產(chǎn)品的價格，使總的經(jīng)濟效益會增加。2.3符號說明

表示工廠在計劃期內安排生產(chǎn)甲產(chǎn)品的數(shù)量。

表示工廠在計劃期內安排生產(chǎn)乙產(chǎn)品的數(shù)量。Z

表示工廠總的經(jīng)濟收益。2.4模型建立建立線性規(guī)劃模型，目標函數(shù)：x(2xx)1212即Z216012條件約束x18012x,x122.5模型求解（1）問題一：應如何安排生產(chǎn)計劃使該工廠獲得的利潤最大？運用單純型表法求解，寫出原模型的標準型：maxZxx1234

頁眉xx12xx18014xxx,1

得到原始單純形表：表3-2原單純形表基變量

甲

乙

松弛變量B00

X34

B

160180

242

310

401表單純形表第一步變換基變量

甲

乙

松弛變量

檢驗數(shù)B00

X34

B

160180

2[4]2

310

401

i4090Z

0

5

8

0

0表單純形表第二步變換基變量

甲

乙

松弛變量

檢驗數(shù)B80

X24

B

40100

10.5[2]

210

30.25-0.5

401

i8050Z

320

1

0

-2

010.250T5頁眉表3-5最單純形表基變量

甲

乙

松弛變量

檢驗數(shù)B85

X21

B

1550

101

210

3

40.5

00

iZ

370

0

0

-0.5計算結果是廠在計劃日期內安排生產(chǎn)甲產(chǎn)品的量為50產(chǎn)乙產(chǎn)品的量為。所獲得的最大利潤為370。（2）問題二：原料,的影子價格是多少？那一種更珍貴？由表1最終結果表4得原料的影子價格是B的影子價格是0.5所以原料

更珍貴。（3）問題三：假定市場上有原

出售，企業(yè)是否應該購入以擴大生產(chǎn)？在保持原方案不變的前提下，最多應購入多少？可增加多少利潤？設原料

的資源數(shù)量，發(fā)生變化時，變化量為Vb，并假設規(guī)劃問題其他系數(shù)11都不變，這樣使最終表中原問題的解相應發(fā)生變化為：

(b)

，這里,0),b1

0.25

，只要X

，最終單純型表4檢驗數(shù)不變則最優(yōu)基不變?？捎嬎鉞'B

()b可V，所Vb的變化范圍[40,200]。11所以企業(yè)應該購入原料擴大再生產(chǎn)：在保持原方案不變的前提下，最多應購入200擴大再生產(chǎn)后利潤C(b所以增加的利潤Z=720350。（4）問題四：如果乙產(chǎn)品價格達到元每件，方案會發(fā)生什么變化？頁眉乙產(chǎn)品價格達到20/件；即目標函數(shù)中乙產(chǎn)品的價值系數(shù)改變。目標函數(shù)變?yōu)閙axxx))1212

即

所以最終單純型表表4-6發(fā)生變化，最終變?yōu)楸?，由表得如果乙產(chǎn)品價格達到20/每件，工廠的生產(chǎn)方案為生產(chǎn)甲產(chǎn)品的量為，生產(chǎn)乙產(chǎn)品的量為。表3-6變后的單純形表基變量

甲

乙

松弛變量

檢驗數(shù)B

X

B

x

2

3

4

i125Z

2x

1550370

010

100

[0.5]0.5

_100表3-7迭后的最終單純形表基變量

甲

乙

松弛變量

檢驗數(shù)B

X

B

2

3

4

i120Z

24

40100370

0.52-1

100

0.25-0.5-3

010

00（5）問題五；現(xiàn)有新產(chǎn)品丙可投入開發(fā)，一直對兩種原材料的消量分別和4，問該產(chǎn)的價格至少應為多少才值得生產(chǎn)？假設新產(chǎn)品丙的價格，則目標函數(shù)變?yōu)椋?maxxxx)x1313123即：11)13

條件約束：

xx160xx1803

(3-10)所以產(chǎn)品的技術向量為3

T

頁眉，然后計算最終表中對應的檢系數(shù)為

3

'3

(1.75,0.5)(3,4)33

T

3

(3-11)明新產(chǎn)品丙值得生產(chǎn)2.6分析結果

以新產(chǎn)品丙的價格至少應為。（1）題一：應如何安排生產(chǎn)計劃使該工廠獲得的利潤最大？工廠在計劃日期內安排生產(chǎn)甲產(chǎn)品的量為50，生產(chǎn)乙產(chǎn)品的量15所獲得的最大利潤為370。（2）題二：原料A

,

的影子價格各是多少？那一種更珍貴？原料A的影子價格是2.25，影子價格是，所以原料A

更珍貴。（）問題三假定市場上有原料A出售，企業(yè)是否應該購入以擴大生產(chǎn)？在保持原方案不變的前提下，最多應購入多少？可增加多少利潤？企業(yè)應該購入原料

擴大再生產(chǎn)：在保持原方案不變的前提下，最多應購入200；可增加的利潤。問題四：如果乙產(chǎn)品價格達到元每件，方案會發(fā)生什么變化？工廠的生產(chǎn)方案為生產(chǎn)甲產(chǎn)品的量為0，生產(chǎn)乙產(chǎn)品的量為40。問題五；現(xiàn)有新產(chǎn)品丙可投入開發(fā)，一直對兩種原材料的消耗量分別為和4，問產(chǎn)品的價格至少應為多少才值得生產(chǎn)？新產(chǎn)品丙的價格至少應為。企3.1問題提出某鑄造廠接到一筆訂單，要生產(chǎn)1公斤鑄件，其成分是錳至少達0，硅達到3—。鑄件的售價為元/公斤。工廠現(xiàn)存三種可利用的生鐵，存量很多，其性質如下表所示。此外，生產(chǎn)過程允許把錳直接加到熔化金屬中。頁眉表生鐵性質表元素硅錳

生鐵

生鐵B0.5%

生鐵0.6%0.4%

C各種可能的爐料費用如下：生鐵

—210元/噸，生

—250元噸，生C—150元/噸，錳元/公斤。每熔化一公斤生鐵要花費元，試問工廠在生產(chǎn)該鑄件時，應如何選擇爐料才能使利潤最大。3.2確定決策變量設：表示生鐵A的用量（噸）1

2

表示生鐵B的用量（噸）3

表示生鐵C的用量（噸）

4

表示純錳的用量（噸）3.3確定目標函數(shù)總利潤=總收入—總成本4.5150xx12333.4確定約束條件生產(chǎn)總量約束：1000x13成分約束：錳4.5x5.04.514硅40x55.02非負約束：x0124最后可以整理成下列線性規(guī)劃模型：目標函數(shù)maxZ4500x200x80013

4

(3-12)(3-13)(3-14)(3-15)(3-16)s.t.

頁眉x1000x10004140xxx55.03xx32.53xx,,4

(3-17)上述數(shù)學模型，可以用單純形法計算，計算結果是：生鐵

的用量為200噸生鐵

的用量為100，生鐵

C

的用量為50噸，純錳的用量為噸。第四章

頁眉線性規(guī)劃在企業(yè)投資策中的應用在市場經(jīng)濟體制下，進行投資活動是企業(yè)財務工作的一項重要內容。一旦投資決策失誤，就會嚴重影響企業(yè)的財務狀況和現(xiàn)金流量，制約企業(yè)經(jīng)濟效益的提高，甚至會導致企業(yè)破產(chǎn)。因而企業(yè)管理者要慎重的進行投資決策。在線性規(guī)劃應用前要建立經(jīng)濟與金融體系的評價標準及企業(yè)的計量體系，摸清企業(yè)的資源。首先通過建網(wǎng)、建庫、查詢、數(shù)據(jù)采集、文件轉換等，把整個系統(tǒng)的各有關部分的特征進行量化，建立數(shù)學模型，即把組成系統(tǒng)的有關因素與系統(tǒng)目標的關系，用數(shù)學關系和邏輯關系描述出來，然后白較好的數(shù)學模型編制成計算機語言，輸入數(shù)據(jù)，進行計算，不同參數(shù)獲取的不同結果與實際進行分析對比，進行定量，定性分析，最終作出決策[面舉例具體說明。工1.1問題提出某工廠只生產(chǎn)一種產(chǎn)品，工廠希望分六期來擴大它的生產(chǎn)力，每期一年。工廠的目標是希望在第六期末具有盡可能大的生產(chǎn)力。已知生產(chǎn)一個產(chǎn)品需用d下一期的開始時為工廠創(chuàng)r

元，耗費工廠一個單位生產(chǎn)能力，同時每個產(chǎn)品可以在元的收入。在每期擴建工程中可以采用兩種不同的方案：A方案：擴建開始時，每擴建一個單位生產(chǎn)能力需要投資元，一年后即可投入使用。

B方擴建開始時沒擴大一個單位生產(chǎn)能力需要投d

元兩年后可投入使用。該工廠在第一期期初共有資金D

元，可用于生產(chǎn)和擴建。以后每期的生產(chǎn)和擴建費用完全依靠產(chǎn)品的消費收入。已知該工廠在第一期期初的生產(chǎn)能力為R。試用性規(guī)劃進行決策。1.2確定決策變量設：X

表示第

期的生產(chǎn)量

表示第K

期用方案

擴建的生產(chǎn)能力5頁眉

表示第K

期用方

擴建的生產(chǎn)能力表示第K期剩余的能力1.3目標函數(shù)工廠的目標是在第六期期末具有盡可能大的生產(chǎn)能力。考慮到在每期按方案

擴建的生產(chǎn)能力，一年后（即第二年）才能投入使用，按方案B

擴建的生產(chǎn)能力，二年后（即第三年）才能投入使用，所以第六期期末（即第七期年初）工廠按兩種方案擴建的生產(chǎn)能力總計是RkK因為R是常數(shù)，所以目標函數(shù)可以寫成maxkKK

1.4約束條件根據(jù)題意，每一期都有兩個方面的約束。一方面是生產(chǎn)能力的限制：每期的生產(chǎn)能力應等于工廠用于生產(chǎn)產(chǎn)品的能力和剩余生產(chǎn)能力的和；另一方面是資金的限制：對于第一期來說，用于生產(chǎn)、擴建和剩余資金的總和應等于第一期期初工廠擁有的資金總額。第二期到第六期用于生產(chǎn)和擴建的資金應等于上一期產(chǎn)品的銷售總額和上一期剩余的資金總和。按每一期分別考慮，有下面的各期約束條件如表所示將他們綜合在一起，數(shù)學模型如：目標函數(shù)ZkK

[14]

(4-3)約束條件：xRK(AB)R,K2,3...,6tttd11

ABcxK

r

,

頁眉x0,B0,0,K1,2,...,6kKKkA00表各期約束條件表時期第一期

開發(fā)量A,

生產(chǎn)量1

剩余資金1

可用資金D第二期

A,

2

2

xr11第三期第四期第五期第六期

ABA,AAB

x3x4x5x6

3456

xr22xr33xr44xr55可以分別得出約束條件：

Bc11xrxA221bBxr,xA33212br,xA332123dr,xAA545313xrxAAB66534123

企2.1問題提出工廠與客戶簽訂了一項在某時刻提交一定數(shù)量產(chǎn)品的合同,在定生產(chǎn)計劃時要考慮生產(chǎn)和貯存2種費用。生產(chǎn)費用通常取決于生產(chǎn)率(單位時間的產(chǎn)量,產(chǎn)率越高費用越大;貯存費用自然由已經(jīng)生產(chǎn)出來的產(chǎn)品數(shù)量決定數(shù)量越多費用越大所謂生產(chǎn)計劃這里簡單的看作是到每一刻為止的累積產(chǎn)量。它與每單位時間（如每天）的產(chǎn)量可以互相推算。建模目的是尋求優(yōu)化的生產(chǎn)計劃使完成合同所需的總費用（生產(chǎn)與貯存費用之和）最小或盡可能的小。某廠按合同規(guī)定須于當年每個季度末分別提供臺統(tǒng)一規(guī)格的柴油機。已知該廠各季度的生產(chǎn)能力及每臺柴油機的成本如表4-9所示。又如果生產(chǎn)出來的柴頁眉油機當季不交貨，每臺每積壓一個季度，需要存儲、維護等費用萬元。要求在完成合同的情況下，作出使該廠全年生產(chǎn)（包括存儲、維護）費用最小的決策表各季度柴油機成本表季度

2.2模型建立與分析

生產(chǎn)能力（臺）25353010

單位成本（萬元）10.811.111.011.3由于每個季度生產(chǎn)出來的柴油機不一定當季交貨所以x為i度生產(chǎn)的用于第jij季度交貨的柴油機數(shù)。根據(jù)合同要求，必須滿足：

101115121323143444

又每季度用于當季度和以后各季度交貨的柴油機數(shù)不可能超過該季度的生產(chǎn)能力，故又有：

111213352223243033341044

i季度生產(chǎn)的用于j季度交貨的柴油機的實際成本上存儲、維護等費用的具體數(shù)值見表4-3.ij

ij

應該是該季度單位成本加I

表4-3各度柴油機的實際成本表IIIII

IV

810

i4i4頁眉設用表示該廠第季度生產(chǎn)能力b表示i度的合同供應量則問題可寫成：ijz

4

cijij

[15]

ij滿足

xiji

ijixij

j

(4-10)2.3模型求解顯然，這是一個產(chǎn)大于銷的運輸問題模型。注意到這個問題中ij時，ij所以應令對應的cMij

，

再加上一個假象的需求D，就可以把這個問題變成產(chǎn)銷平衡的運輸模型[13]，并寫出傳銷平衡表和單位運價表（合在一起，見表4-4表單位運價表I

IIIII

IV

D

產(chǎn)量

10.8MMM

9510MM

M

11．

0000

25353010銷量

1025

20

30表4-5經(jīng)上作業(yè)法求解后的最終結果

IIIIII10155

IV

D30

產(chǎn)量2535銷量

201010101530

3010頁眉經(jīng)用表上作業(yè)法求解，可得多個最優(yōu)方案，表中列出最優(yōu)方案之一。即I度生產(chǎn)25臺10當季交貨，臺II季度交貨；即第I