【正文】 2013屆畢業(yè)生外文文獻(xiàn)翻譯學(xué) 院 理學(xué)院 　　　專 業(yè) 信息與計(jì)算科學(xué) 姓 名 李存正 　　　　學(xué) 號(hào) 200901120224 指導(dǎo)教師 盧福良 　　　線性規(guī)劃在企業(yè)決策中的應(yīng)用第一章 線性規(guī)劃理論1. 線性規(guī)劃簡(jiǎn)介 線性規(guī)劃是運(yùn)籌學(xué)中研究較早、發(fā)展較快、應(yīng)用廣泛、方法較成熟的一個(gè)重要分支,、交通運(yùn)輸、工農(nóng)業(yè)生產(chǎn)等經(jīng)濟(jì)活動(dòng)中，提高經(jīng)濟(jì)效果是人們不可缺少的要求，而提高經(jīng)濟(jì)效果一般通過(guò)兩種途徑：一是技術(shù)方面的改進(jìn)，例如改善生產(chǎn)工藝，：在一定條件下，合理安排人力物力等資源，求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問(wèn)題，統(tǒng)稱為線性規(guī)劃問(wèn)題[1]。滿足線性約束條件的解叫做可行解，由所有可行解組成的集合叫做可行域[2]。決策變量、約束條件、目標(biāo)函數(shù)是線性規(guī)劃的三要素。2. 線性規(guī)劃的發(fā)展歷程 法國(guó)數(shù)學(xué)家 －普森分別于1832和1911年獨(dú)立地提出線性規(guī)劃的想法，但未引起注意。 　　《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》一書(shū)中提出線性規(guī)劃問(wèn)題，也未引起重視。 　　──單純形法，為這門(mén)學(xué)科奠定了基礎(chǔ)。 　　,開(kāi)創(chuàng)了線性規(guī)劃的許多新的研究領(lǐng)域，擴(kuò)大了它的應(yīng)用范圍和解題能力。 　　，為此與康托羅維奇一起獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。 　　50年代后對(duì)線性規(guī)劃進(jìn)行大量的理論研究，并涌現(xiàn)出一大批新的算法。例如，。 　　線性規(guī)劃的研究成果還直接推動(dòng)了其他數(shù)學(xué)規(guī)劃問(wèn)題包括整數(shù)規(guī)劃、隨機(jī)規(guī)劃和非線性規(guī)劃的算法研究。由于數(shù)字電子計(jì)算機(jī)的發(fā)展，出現(xiàn)了許多線性規(guī)劃軟件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解幾千個(gè)變量的線性規(guī)劃問(wèn)題[3]。 　　1979年蘇聯(lián)數(shù)學(xué)家L. G. Khachian提出解線性規(guī)劃問(wèn)題的橢球算法，并證明它是多項(xiàng)式時(shí)間算法?！　　Ｓ眠@種方法求解線性規(guī)劃問(wèn)題在變量個(gè)數(shù)為5000時(shí)只要單純形法所用時(shí)間的1/50?，F(xiàn)已形成線性規(guī)劃多項(xiàng)式算法理論。50年代后線性規(guī)劃的應(yīng)用范圍不斷擴(kuò)大。建立線性規(guī)劃模型的方法。3. 線性規(guī)劃的數(shù)學(xué)模型及其標(biāo)準(zhǔn)形式 線性規(guī)劃問(wèn)題的提出在生產(chǎn)管理和經(jīng)營(yíng)活動(dòng)中經(jīng)常提出一類問(wèn)題，即如何合理地利用有限的人力、物力、財(cái)力等資源，以便得到最好的經(jīng)濟(jì)效果。線性規(guī)劃主要解決兩類問(wèn)題：（1）資源有限，要求生產(chǎn)的產(chǎn)品（或利潤(rùn)）最多。（2）任務(wù)（或產(chǎn)品）一定，要求消耗的資源（或成本）最少。 線性規(guī)劃問(wèn)題的特征（1）每一個(gè)問(wèn)題都用一組決策變量表示某一方案；這組決策變量的值就有代表一過(guò)具體方案。 （2）一般這些變量取值是非負(fù)的。 （3）存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來(lái)表示。 （4）都有一個(gè)要求達(dá)到的目標(biāo)，它可用決策變量的線性函數(shù)（稱為目標(biāo)函數(shù)）來(lái)表示。按問(wèn)題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。滿足以上四個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型。 從實(shí)際問(wèn)題中建立數(shù)學(xué)模型的步驟；（1）根據(jù)影響所要達(dá)到目的的因素找到?jīng)Q策變量；（2）由決策變量和所在達(dá)到目的之間的函數(shù)關(guān)系確定目標(biāo)函數(shù)；（3）由決策變量所受的限制條件確定決策變量所要滿足的約束條件。 所建立的線性規(guī)劃模型的特點(diǎn)；（1）每個(gè)模型都有若干個(gè)決策變量，其中為決策變量個(gè)數(shù)。決策變量的一組值表示一種方案，同時(shí)決策變量一般是非負(fù)的。（2）目標(biāo)函數(shù)是決策變量的線性函數(shù)，根據(jù)具體問(wèn)題可以是最大化或最小化，二者統(tǒng)稱為最優(yōu)化[3]。（3）約束條件也是決策變量的線性函數(shù)。 線性規(guī)劃模型的一般形式目標(biāo)函數(shù)： (11)約束條件： (12)在線性規(guī)劃的數(shù)學(xué)模型中，方程（31）稱為目標(biāo)函數(shù)；（32）稱為約束條件。 線性規(guī)劃模型的標(biāo)準(zhǔn)形式 (13) (14)其中.簡(jiǎn)寫(xiě)形式為： (15) (16)向量和矩陣表示： (17) (18)其中 ，4. 線性規(guī)劃的解法求解線性規(guī)劃問(wèn)題的基本方法有圖解法和單純形法，但實(shí)際運(yùn)用的主要是是單純形法，現(xiàn)在已有單純形法的標(biāo)準(zhǔn)軟件，可在電子計(jì)算機(jī)上求解約束條件和決策變量數(shù)達(dá) 10000個(gè)以上的線性規(guī)劃問(wèn)題。為了提高解題速度，又有改進(jìn)單純形法、對(duì)偶單純形法、原始對(duì)偶方法、分解算法和各種多項(xiàng)式時(shí)間算法。對(duì)于只有兩個(gè)變量的簡(jiǎn)單的線性規(guī)劃問(wèn)題，也可采用圖解法求解。這種方法僅適用于只有兩個(gè)變量的線性規(guī)劃問(wèn)題[5]。它的特點(diǎn)是直觀而易于理解，但實(shí)用價(jià)值不大。不過(guò)通過(guò)圖解法求解可以理解線性規(guī)劃的一些基本概念。下面著重介紹單純形法。 一般線性規(guī)劃問(wèn)題的單純形解法 建立初始基本可行解在線性規(guī)劃問(wèn)題中，約束條件多為不等式，所以首先要將其化為標(biāo)準(zhǔn)型，同時(shí)建立一個(gè)初始基本可行基。 最優(yōu)解檢驗(yàn)找到一個(gè)可行判斷它是不是最優(yōu)解。判斷方法是檢驗(yàn)?zāi)繕?biāo)函數(shù)中是否還有正的系數(shù)，若有正的系數(shù)，則說(shuō)明還有更好的解。只有當(dāng)目標(biāo)函數(shù)中的全部系數(shù)為負(fù)值或0時(shí)，說(shuō)明改解才是最優(yōu)解。 基變換從一個(gè)基可行解到另一個(gè)基可行解的變換就是進(jìn)行一次基變換。 迭代（旋轉(zhuǎn)運(yùn)算）將約束條件的增廣矩陣中新基變量的系數(shù)通過(guò)矩陣的行變換或Gauss變換變?yōu)閱挝痪仃嘯6]。 非標(biāo)準(zhǔn)型線性規(guī)劃問(wèn)題的解法 大法在一個(gè)線性規(guī)劃問(wèn)題的約束條件中加入人工變量后，要求人工變量對(duì)目標(biāo)函數(shù)的取值無(wú)影響，為此可取人工變量在目標(biāo)函數(shù)中的系數(shù)為(為非常大的正數(shù))[7]，這樣目標(biāo)函數(shù)要實(shí)現(xiàn)最大化，人工變量只能取零，因此必須把人工變量從基變量中換出，否則目標(biāo)函數(shù)就不可能實(shí)現(xiàn)最大化。 兩階段法第一階段：不考慮原問(wèn)題是否存在基可行解，給原線性規(guī)劃問(wèn)題加上人工變量，構(gòu)造僅含人工變量的目標(biāo)函數(shù)和要求實(shí)現(xiàn)最小化。第二階段：將第一階段得到的最優(yōu)單純形表，除去人工變量，將原目標(biāo)函數(shù)的系數(shù)換掉該表的目標(biāo)函數(shù)的系數(shù)行，作為第二階段計(jì)算的初始表。 對(duì)偶分析 對(duì)偶問(wèn)題的基本概念在線性規(guī)劃問(wèn)題中，如果把一個(gè)求最大值的線性規(guī)劃定義為“原”問(wèn)題，那么與其同時(shí)存在一個(gè)求最小值的所謂對(duì)偶問(wèn)題，并且原線性規(guī)劃的最優(yōu)解對(duì)應(yīng)著對(duì)偶線性規(guī)劃問(wèn)題的最優(yōu)解。 對(duì)偶問(wèn)題的性質(zhì)（1）對(duì)稱性 對(duì)偶問(wèn)題的對(duì)偶是原問(wèn)題。（2）弱對(duì)偶性 若是原問(wèn)題的可行解，是對(duì)偶問(wèn)題的可行解。則存在。（3）無(wú)界性 若原問(wèn)題（對(duì)偶問(wèn)題）為無(wú)界解，則其對(duì)偶問(wèn)題（原問(wèn)題）無(wú)可行解。（4）可行解是最優(yōu)解時(shí)的性質(zhì) 設(shè)是原問(wèn)題的可行解，是對(duì)偶問(wèn)題的可行解，當(dāng)時(shí)，,是最優(yōu)解。 （5）對(duì)偶定理 若原問(wèn)題有最優(yōu)解，那么對(duì)偶問(wèn)題也有最優(yōu)解且最優(yōu)值相同。 （6）互補(bǔ)松馳性 若,分別是對(duì)偶問(wèn)題和原問(wèn)題的可行解。那么和,當(dāng)且僅當(dāng),為最優(yōu)解。靈敏度分析主要有以下幾種情況[8]： （1）資源數(shù)量變化的分析； （2）目標(biāo)函數(shù)中價(jià)值系數(shù)的變化分析； （3）技術(shù)系數(shù)的變化； （4）約束條件增減的變化分析。第二章 企業(yè)決策理論1. 企業(yè)決策概述 隨著企業(yè)計(jì)算機(jī)應(yīng)用和信息化程度的不斷深入，企業(yè)已經(jīng)積累了大量的業(yè)務(wù)和財(cái)務(wù)數(shù)據(jù)，并繼續(xù)隨著時(shí)間和業(yè)務(wù)的發(fā)展而呈幾何級(jí)膨脹趨勢(shì)。企業(yè)信息處理部門(mén)的工作重點(diǎn)已逐漸超越了簡(jiǎn)單的數(shù)據(jù)收集，企業(yè)內(nèi)的各級(jí)人員都希望能夠快速、準(zhǔn)確并方便有效地從這些大量雜亂無(wú)章的數(shù)據(jù)中獲取有意義的信息，決策者也希望能夠充分利用現(xiàn)有的數(shù)據(jù)指導(dǎo)企業(yè)決策和發(fā)掘企業(yè)的競(jìng)爭(zhēng)優(yōu)勢(shì)[9]。決策效率和決策質(zhì)量的高低將直接影響企業(yè)的運(yùn)營(yíng)績(jī)效和市場(chǎng)競(jìng)爭(zhēng)力。由于集團(tuán)企業(yè)具有分布、異構(gòu)、自治等特點(diǎn)，集團(tuán)企業(yè)運(yùn)營(yíng)過(guò)程中的決策將是一個(gè)復(fù)雜的過(guò)程，對(duì)于不同的決策問(wèn)題需要采用不同的決策方法。同時(shí)，在集團(tuán)企業(yè)運(yùn)營(yíng)過(guò)程中，決策的形式也是多種多樣的，它在一定的階段表現(xiàn)為個(gè)體的行為，在一定的階段又表現(xiàn)為群體的活動(dòng)，從而給集團(tuán)企業(yè)管理中的決策分析提出了高要求。2. 企業(yè)決策分類 按重要程度分類在企業(yè)的決策中，我們按重要程度分類一般把決策分為三個(gè)層次，即戰(zhàn)略決策、戰(zhàn)術(shù)決策和業(yè)務(wù)決策[10]。 戰(zhàn)略決策第一類戰(zhàn)略決策是與管理總的方針和開(kāi)發(fā)企業(yè)所需要的資源有關(guān)的決策，它屬于長(zhǎng)遠(yuǎn)規(guī)劃，對(duì)企業(yè)的發(fā)展具有深遠(yuǎn)影響，決策過(guò)程中要考慮很多不確定和冒風(fēng)險(xiǎn)的因素。是集團(tuán)企業(yè)決策信息模型中的最高層，負(fù)責(zé)管理、控制、協(xié)調(diào)整個(gè)集團(tuán)企業(yè)網(wǎng)絡(luò)的正常運(yùn)行。其控制范圍包括涉及集團(tuán)企業(yè)全體成員整體利益的事務(wù)和對(duì)整個(gè)企業(yè)集團(tuán)運(yùn)營(yíng)活動(dòng)的調(diào)控與制約。在這一層次，可以設(shè)定集團(tuán)企業(yè)決策模型的范圍和內(nèi)容、集團(tuán)企業(yè)的合作機(jī)制和行為準(zhǔn)則的設(shè)定、運(yùn)營(yíng)過(guò)程的績(jī)效評(píng)價(jià)、利益分配機(jī)制和風(fēng)險(xiǎn)控制機(jī)制等任務(wù)，為集團(tuán)企業(yè)正常運(yùn)營(yíng)提供了戰(zhàn)略決策框架和行動(dòng)指南。根據(jù)集團(tuán)企業(yè)實(shí)際情況進(jìn)行群體決策，擔(dān)負(fù)著全局優(yōu)化以及在新機(jī)遇下的集團(tuán)企業(yè)組建過(guò)程中的決策工作。 戰(zhàn)術(shù)決策第二類決策稱為戰(zhàn)術(shù)決策，是在物資資源、設(shè)備等決策之后，規(guī)劃如何最有效的分配所獲得的資源（如生產(chǎn)能力、資金、材料、勞力等），以便獲得最大效益。定義集團(tuán)企業(yè)各成員企業(yè)的各種基本決策活動(dòng)過(guò)程。雖然由于集團(tuán)企業(yè)的動(dòng)態(tài)特性，各企業(yè)的實(shí)際情況和操作流程會(huì)有所不同，但我們總能找到一些存在于企業(yè)業(yè)務(wù)活動(dòng)中相對(duì)穩(wěn)定且有相同或類似行為特征的實(shí)體。同時(shí)也能找出系統(tǒng)中不能再分的最小粒度的原子過(guò)程，利用技術(shù)，我們將企業(yè)中的各類實(shí)體和原子過(guò)程封裝成對(duì)象，根據(jù)產(chǎn)品結(jié)構(gòu)信息和集團(tuán)企業(yè)實(shí)際運(yùn)行狀態(tài)信息，將客戶的訂單分解到集團(tuán)企業(yè)的各成員企業(yè)，并派生出由不同的原子過(guò)程組成的工作流，對(duì)資源進(jìn)行分配，并完成對(duì)工作流監(jiān)督、控制的任務(wù)。 業(yè)務(wù)決策第三類叫業(yè)務(wù)決策，完成集團(tuán)企業(yè)具體任務(wù)的執(zhí)行工作，包括物流在各企業(yè)間的合理流動(dòng)以及從原材料到成品的物理加工過(guò)程，如原材料的運(yùn)輸、零件加工、部件裝配、檢測(cè)、倉(cāng)儲(chǔ)等過(guò)程。在本層中，完成制造、銷售、供應(yīng)、運(yùn)輸?shù)热蝿?wù)的同時(shí)，還要對(duì)第一線的信息進(jìn)行采集、整理、反饋以供上層決策時(shí)使用。是在資源合理分配后，進(jìn)行日常業(yè)務(wù)和計(jì)劃的決策，線性規(guī)劃模型最適合進(jìn)行戰(zhàn)術(shù)決策，解決諸如勞動(dòng)力和生產(chǎn)能力等資源的合理分配，運(yùn)輸和指派方案的最優(yōu)選擇、廣告和推銷費(fèi)用的預(yù)算等問(wèn)題，同時(shí)它也在投資方案選擇、配料、選址、生產(chǎn)計(jì)劃、環(huán)境（如空氣、水）污染控制、下料等優(yōu)化方面有廣泛的應(yīng)用。 按企業(yè)決策的環(huán)境分類在企業(yè)的決策中，我們按企業(yè)決策的環(huán)境可分為確定性決策、風(fēng)險(xiǎn)決策和不確定性決策。 確定性決策確定性決策是指未來(lái)環(huán)境完全可預(yù)測(cè)，而且在此確定的未來(lái)環(huán)境下待選擇的決策方案的后果也是可以確定的。簡(jiǎn)單講，就是一種方案只有一種確定的結(jié)果。 風(fēng)險(xiǎn)決策風(fēng)險(xiǎn)決策是指未來(lái)環(huán)境有幾種可能的狀態(tài)和相應(yīng)的后果，人們無(wú)法得到關(guān)于未來(lái)環(huán)境的充分可靠的信息，但可以預(yù)測(cè)每一種狀態(tài)和后果出現(xiàn)的概率。對(duì)利潤(rùn)、效益等問(wèn)題的決策一般都是風(fēng)險(xiǎn)型決策 不確定性決策不確定性決策是指未來(lái)環(huán)境出現(xiàn)某種狀態(tài)的概率難以估計(jì)，甚至連可能出現(xiàn)的狀態(tài)和相應(yīng)的后果都是未知的。這類決策，主要依靠決策者的經(jīng)驗(yàn)和主觀判斷。 按企業(yè)決策的主體分類在企業(yè)的決策中，我們按企業(yè)決策的主體可分為個(gè)人決策和群體決策。 個(gè)人決策個(gè)人決策是指決策的主體是一個(gè)人，即最終方案的選擇僅僅