線性目標(biāo)規(guī)劃簡(jiǎn)介

線性目標(biāo)規(guī)劃(linear goal programming)是一種目標(biāo)規(guī)劃(問題).指目標(biāo)函數(shù)和約束函數(shù)均為決策變量的線性函數(shù)的目標(biāo)規(guī)劃(間題)(參見“目標(biāo)規(guī)劃”).線性目標(biāo)規(guī)劃問題的數(shù)學(xué)模型為它的每一層次都是一個(gè)線性規(guī)劃問題。

線性目標(biāo)規(guī)劃的基本原理斷言:

1.線性目標(biāo)規(guī)劃必存在滿意解，且可用單純形法(參見“單純形法”)求解其對(duì)應(yīng)的線性規(guī)劃問題而得到.

2.若線性目標(biāo)規(guī)劃的單純形表中任一檢驗(yàn)列皆為零向量，或雖非零向量，但自上至下第一個(gè)非零分量為正數(shù)，則該單純形表對(duì)應(yīng)的基可行解為線性目 標(biāo)規(guī)劃的滿意解.2100433B

規(guī)劃論起源

非線性規(guī)劃是具有非線性約束條件或目標(biāo)函數(shù)的數(shù)學(xué)規(guī)劃，是運(yùn)籌學(xué)的一個(gè)重要分支。非線性規(guī)劃是20世紀(jì)50年代才開始形成的一門新興學(xué)科。70年代又得到進(jìn)一步的發(fā)展。非線性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方面都有廣泛的應(yīng)用，為最優(yōu)設(shè)計(jì)提供了有力的工具。非線性規(guī)劃研究一個(gè) n元實(shí)函數(shù)在一組等式或不等式的約束條件下的極值問題，且目標(biāo)函數(shù)和約束條件至少有一個(gè)是未知量的非線性函數(shù)。

非線性規(guī)劃是20世紀(jì)50年代才開始形成的一門新興學(xué)科。1951年H.W.庫(kù)恩和A.W.塔克發(fā)表的關(guān)于最優(yōu)性條件（后來(lái)稱為庫(kù)恩－塔克條件）的論文是非線性規(guī)劃正式誕生的一個(gè)重要標(biāo)志。在50年代還得出了可分離規(guī)劃和二次規(guī)劃的n種解法，它們大都是以G.B.丹齊克提出的解線性規(guī)劃的單純形法為基礎(chǔ)的。50年代末到60年代末出現(xiàn)了許多解非線性規(guī)劃問題的有效的算法，70年代又得到進(jìn)一步的發(fā)展。

非線性規(guī)劃在工程、管理、經(jīng)濟(jì)、科研、軍事等方面都有廣泛的應(yīng)用，為最優(yōu)設(shè)計(jì)提供了有力的工具。20世紀(jì)80年代以來(lái)，隨著計(jì)算機(jī)技術(shù)的快速發(fā)展，非線性規(guī)劃方法取得了長(zhǎng)足進(jìn)步，在信賴域法、稀疏擬牛頓法、并行計(jì)算、內(nèi)點(diǎn)法和有限存儲(chǔ)法等領(lǐng)域取得了豐碩的成果。

規(guī)劃論算法

對(duì)于一個(gè)實(shí)際問題，在把它歸結(jié)成非線性規(guī)劃問題時(shí)，一般要注意如下幾點(diǎn)：

（i）確定供選方案：首先要收集同問題有關(guān)的資料和數(shù)據(jù)，在全面熟悉問題的基礎(chǔ)上，確認(rèn)什么是問題的可供選擇的方案，并用一組變量來(lái)表示它們。

（ii）提出追求目標(biāo)：經(jīng)過資料分析，根據(jù)實(shí)際需要和可能，提出要追求極小化或極大化的目標(biāo)。并且，運(yùn)用各種科學(xué)和技術(shù)原理，把它表示成數(shù)學(xué)關(guān)系式。

（iii）給出價(jià)值標(biāo)準(zhǔn)：在提出要追求的目標(biāo)之后，要確立所考慮目標(biāo)的“好”或 “壞”的價(jià)值標(biāo)準(zhǔn)，并用某種數(shù)量形式來(lái)描述它。

（iv）尋求限制條件：由于所追求的目標(biāo)一般都要在一定的條件下取得極小化或極大化效果，因此還需要尋找出問題的所有限制條件，這些條件通常用變量之間的一些不等式或等式來(lái)表示。

是解決多變量最優(yōu)決策的方法，是在各種相互關(guān)聯(lián)的多變量約束條件下，解決或規(guī)劃一個(gè)對(duì)象的線性目標(biāo)函數(shù)最優(yōu)的問題，即給與一定數(shù)量的人力、物力和資源，如何應(yīng)用而能得到最大經(jīng)濟(jì)效益。當(dāng)資源限制或約束條件表現(xiàn)為線性等式或不等式，目標(biāo)函數(shù)表示為線性函數(shù)時(shí)，可運(yùn)用線性規(guī)劃法進(jìn)行決策。

線性規(guī)劃是決策系統(tǒng)的靜態(tài)最優(yōu)化數(shù)學(xué)規(guī)劃方法之一。它作為經(jīng)營(yíng)管理決策中的數(shù)學(xué)手段，在現(xiàn)代決策中的應(yīng)用是非常廣泛的，它可以用來(lái)解決科學(xué)研究、工程設(shè)計(jì)、生產(chǎn)安排、軍事指揮、經(jīng)濟(jì)規(guī)劃；經(jīng)營(yíng)管理等各方面提出的大量問題。

規(guī)劃論起源

研究線性規(guī)劃最早的是蘇聯(lián)的康脫洛維奇，1939年，他發(fā)表了《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》一書。主要討論了機(jī)床、負(fù)荷、下料運(yùn)輸?shù)葐栴}。但他提出的問題在當(dāng)時(shí)并未引起人們的注意。他自己也未能提出一個(gè)統(tǒng)一的求解方法。

在第二次世界大戰(zhàn)期間，由于軍事運(yùn)輸?shù)男枰?，提出線性問題的解法，美國(guó)的經(jīng)濟(jì)學(xué)家柯普曼（Koupman）也研究了運(yùn)輸問題。直到1947年，美國(guó)的G.B.Dantzig提出了求解線性規(guī)劃的單純形法，才使線性規(guī)劃這門學(xué)科在理論上趨于成熟，并成功地運(yùn)用到了工業(yè)、交通、農(nóng)業(yè)、軍事等各個(gè)領(lǐng)域內(nèi)，使線性規(guī)劃的理論與方法成為管理科學(xué)的重要內(nèi)容。

在當(dāng)今電子技術(shù)高度發(fā)展的信息社會(huì)中，線性規(guī)劃給人類在經(jīng)濟(jì)管理、生產(chǎn)管理、人才事務(wù)管理等方面發(fā)揮了巨大作用?，F(xiàn)在對(duì)于成千上萬(wàn)個(gè)約束條件、成千上萬(wàn)個(gè)變量的線性規(guī)劃問題在計(jì)算上已沒有任何問題。據(jù)20世紀(jì)80年代末美國(guó)一個(gè)雜志對(duì)全美500家大公司的調(diào)查，線性規(guī)劃的應(yīng)用范圍名列前茅，有85%的公司頻繁使用線性規(guī)劃。

規(guī)劃論基礎(chǔ)理論

線性規(guī)劃問題是在一組線性約束條件的限制下，求一線性目標(biāo)函數(shù)最大或最小的問題。 在解決實(shí)際問題時(shí)，把問題歸結(jié)成一個(gè)線性規(guī)劃數(shù)學(xué)模型是很重要的一步，但往往 也是困難的一步，模型建立得是否恰當(dāng)，直接影響到求解。而選適當(dāng)?shù)臎Q策變量，是我 們建立有效模型的關(guān)鍵之一。 建立數(shù)學(xué)模型的步驟：

（1）分析實(shí)際問題；（2）確定決策變量；（3）找出約束條件；（4）確定目標(biāo)函數(shù)；（5）整理寫出數(shù)學(xué)模型。

規(guī)劃論應(yīng)用

線性規(guī)劃主要應(yīng)用在以下幾個(gè)方面：

（1）在某一企業(yè)內(nèi)部，如何配合產(chǎn)品的銷售時(shí)間，在各部門的原料，產(chǎn)品的存儲(chǔ)，分配的數(shù)量等最為合理。

（2）在某一企業(yè)生產(chǎn)的產(chǎn)品數(shù)量（或產(chǎn)值），如何使現(xiàn)有的設(shè)備，人力，原料等條件限制下，合理組織生產(chǎn)，使經(jīng)濟(jì)效益最高。

（3）在某地的交通網(wǎng)中，如何合理組織運(yùn)輸，使運(yùn)費(fèi)最小。

（4）在市場(chǎng)上產(chǎn)品的（或原料）價(jià)格變動(dòng)時(shí)，對(duì)于這些變動(dòng)，企業(yè)如何做出最優(yōu)決策。

（5）合理下料問題，即利用某種原料下料時(shí)，如何達(dá)到既滿足要求，又使原料最少。

（6）配料問題，即生產(chǎn)由各種原料生產(chǎn)的的產(chǎn)品時(shí)（如混合飼料等）時(shí)，如何既滿足規(guī)定的質(zhì)量的標(biāo)準(zhǔn)，又使產(chǎn)品的成本最低。

（7）庫(kù)存問題，在倉(cāng)庫(kù)的容量及其他條件的限制下，確定庫(kù)存物資的品種，數(shù)量，期限，使庫(kù)存的效益最高。

（8）在投入產(chǎn)出問題中，引進(jìn)某一目標(biāo)函數(shù)，制定最優(yōu)的企業(yè)（或地區(qū)）經(jīng)濟(jì)計(jì)劃。