線性規(guī)劃模型

模型簡(jiǎn)介

一種特殊形式的數(shù)學(xué)規(guī)劃模型，即目標(biāo)函數(shù)和約束條件是待求變量的線性函數(shù)、線性等式或線性不等式的數(shù)學(xué)規(guī)劃模型。它可用于解決各種領(lǐng)域內(nèi)的極值問題。它所描述的典型問題是怎樣以最優(yōu)的方式在各項(xiàng)活動(dòng)中間分配有限資源的問題。

任何一個(gè)線性規(guī)劃問題可以按下列方式表述：假設(shè)有м項(xiàng)有限的資源要在n項(xiàng)活動(dòng)中間進(jìn)行分配。給各項(xiàng)資源規(guī)定腳標(biāo)1,2,…,м,給各項(xiàng)活動(dòng)規(guī)定腳標(biāo)1,2,…,n,設(shè)xj（即決策變量,有時(shí)亦稱控制變量）為j項(xiàng)活動(dòng)的水平，j=1,2,…,n。決策變量x1,x2,…,xn的一組數(shù)值代表一個(gè)方案（或計(jì)劃）。設(shè)z為選定的某個(gè)效益量度（總效益指標(biāo)），它的數(shù)值衡量當(dāng)采取一組活動(dòng)水平（x1，x2，…，xn）時(shí)所得到的總效益。設(shè)cj為每一單位的xj所提供的效益。設(shè)bj為i項(xiàng)資源在分配時(shí)可被利用的量，最后，設(shè)aij（i=1,2,…,м；j=1,2,…,n）為i項(xiàng)資源被每單位j項(xiàng)活動(dòng)所消耗（或使用）的量。于是，將各項(xiàng)資源分配給各項(xiàng)活動(dòng)以獲得最優(yōu)化結(jié)果的規(guī)劃問題具有下列數(shù)學(xué)模型：

選擇x1，x2，…,xn的值，借以使

z=c1x1 c2x2 …… cnxn達(dá)到最大，且滿足下列各項(xiàng)限制條件：

a11x1 a12x2 ……a1nxn≤b1

a21x1 a22x2 …… a2nxn≤b2

am1x1 am2x2 …… amnxn≤bm

及x1≥0，x2≥0，…，xn≥0

這個(gè)數(shù)學(xué)模型可以等價(jià)地表述為下列更為簡(jiǎn)潔的矩陣形式：

選擇x的值，借以使z=cTx達(dá)到最大，且滿足下列條件：

AX≤b

x≥0

式中

x=（x1,x2…,xn）T（n維列向量）

cT=（c1,c2,…cn）（n維行向量）

b=（b1,b2,…bm）T（m維列向量）

（м×n矩陣）

線性規(guī)劃模型的幾何意義是：在R（n）內(nèi)給定了一個(gè)多面體Ω={x/（A x≤b,x≥0）}，同時(shí)還給定了一個(gè)向量c，要求找出向量x∈Ω，使得x與c的內(nèi)積達(dá)到最大。

線性規(guī)劃模型中z稱為目標(biāo)函數(shù)，A x≤b和x≥0稱為約束條件；x是決策變量，A、b以及c稱為模型的參數(shù)。

以上是線性規(guī)劃模型的典型形式。

然而，在實(shí)際工作中，并不是所有的線性規(guī)劃問題都能表述為典型形式的數(shù)學(xué)模型，而可能出現(xiàn)下列情形：①使目標(biāo)函數(shù)z達(dá)到最小，而不是使z達(dá)到最大；②約束條件組Ax≤b被破壞,即其中有些約束條件是“≥”的不等式；③有些約束條件是等式；④非負(fù)性約束條件x≥0被破壞。

在上述幾種情況下，只需將模型的有關(guān)部分加以改寫，便可使模型等價(jià)地變成典型形式。2100433B

線性規(guī)劃的數(shù)學(xué)模型(mathematical model oflinear programming)是線性規(guī)劃問題的一種數(shù)學(xué)表述。

即:求一組x;(j=1,2, """,n)，使?jié)M足

其中c;,b;,a;; (i=1,2,w,m;j=1,2,""",n)為常數(shù). 符號(hào)s. t.見“數(shù)學(xué)規(guī)劃”.2100433B

線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)最重要的分支，理論上最完善，實(shí)際應(yīng)用得最廣泛。主要用于研究有限資源的最佳分配問題，即如何對(duì)有限的資源作出最佳方式地調(diào)配和最有利地使用，以便最充分地發(fā)揮資源的效能去獲取最佳的經(jīng)濟(jì)效益。由于有成熟的計(jì)算機(jī)應(yīng)用軟件的支持，采用線性規(guī)劃模型安排生產(chǎn)計(jì)劃，并不是一件困難的事情。在總體計(jì)劃中，用線性規(guī)劃模型解決問題的思路是，在有限的生產(chǎn)資源和市場(chǎng)需求條件約束下，求利潤(rùn)最大的總產(chǎn)量計(jì)劃。該方法的最大優(yōu)點(diǎn)是可以處理多品種問題。

全書共分八章，分別講解了線性規(guī)劃問題的建模方法、線性規(guī)劃問題模型的標(biāo)準(zhǔn)型、用單純形算法求解線性規(guī)劃問題、靈敏度分析等內(nèi)容。