1、5.1規(guī)劃論基礎(chǔ)規(guī)劃論是運(yùn)籌學(xué)中應(yīng)用最為廣泛的一個(gè)分支，本小節(jié)重點(diǎn)介紹在軍事通信網(wǎng)分析和規(guī) 劃中常用的兩類模型一一線性規(guī)劃和目標(biāo)規(guī)劃。5.1.1線性規(guī)劃問(wèn)題和模型線性規(guī)劃問(wèn)題主要有以下2種：一是如何有效利用現(xiàn)有的人力、物力完成更多的任務(wù); 二是在預(yù)定的任務(wù)目標(biāo)下，如何耗用最少的人力、物力去實(shí)現(xiàn)目標(biāo)。這些規(guī)劃問(wèn)題的數(shù)學(xué)模 型都是由3個(gè)要素組成：一是變量，或稱決策變量，是需要確定的未知量，用來(lái)表明規(guī)劃 中的用數(shù)量表示的方案；二是目標(biāo)函數(shù)，它是決策變量的線性函數(shù)，按優(yōu)化目標(biāo)在該函數(shù)前 加上max或min；三是約束條件，它是含決策變量的線性等式或不等式。下面，以一個(gè)具 體的例子來(lái)說(shuō)明問(wèn)題。例5.1某通

2、信連計(jì)劃用兩種通信設(shè)備A和B進(jìn)行通信聯(lián)絡(luò)，建網(wǎng)方式有甲、乙兩種， 有關(guān)數(shù)據(jù)見(jiàn)表5.1。問(wèn)：兩種方式的組網(wǎng)數(shù)各為多少時(shí)，能在規(guī)定的條件下，使得提供的話 路總數(shù)z達(dá)到最大？表5.1有關(guān)數(shù)據(jù)表單網(wǎng)所需 組網(wǎng)方式 設(shè)備數(shù)方式 設(shè)備甲乙設(shè)備數(shù)量A3124B2220單網(wǎng)能提供的話路數(shù)1815解：設(shè)x1，x2分別為甲、乙兩種方式的組網(wǎng)數(shù)，則由已知條件，容易得到該問(wèn)題的線 性規(guī)劃模型為：目標(biāo)函數(shù)：max z = 18x +15x123氣 + x2 J 24約束條件： 012一般地，規(guī)定線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式如下：max z =乙 c xj=1 a x - b(i = 1,2, , m)s.t i j ij=1

3、a.x. = b , j =1 j jxj 0 (j = 1,2,., n)其中(Xj(j = 1,2,n)是決策變量,max z =c x為目標(biāo)函數(shù)，j jj=1i = 1,2, ,m，x 0 (j = 1,2,n)為約束條件，s.t (subject to 的縮寫)為約束于。.j.約束條件右端的常數(shù)項(xiàng)b全為非負(fù)。對(duì)于非標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題可以通過(guò)引入松弛 i變量等轉(zhuǎn)化為標(biāo)準(zhǔn)形式。所謂松弛變量，是指在化為標(biāo)準(zhǔn)形式時(shí)，使約束不等式變?yōu)榈仁綍r(shí) 所加入的變量。對(duì)不符合標(biāo)準(zhǔn)形式(或稱非標(biāo)準(zhǔn)形式)的線性規(guī)劃問(wèn)題，可分別通過(guò)下列方 法化為標(biāo)準(zhǔn)形式。目標(biāo)函數(shù)為求極小值，即為：m i n =乙 c xj=

4、1因?yàn)榍髆in z等價(jià)于求max(-z)，令z = -z，即化為max z = -8 c xjj j=1約束條件的右端項(xiàng)b 0時(shí)，只需將等式或不等式兩端同乘一1,則等式右端項(xiàng)必 大于零。約束條件為不等式。當(dāng)約束條件為“ ”時(shí)，如5氣+ x2 0 ；當(dāng)約束條件為“ ”時(shí)，如31212334x + 3x 25，可令 x = 4x + 3x - 25，得 4x + 3x -x = 25 ，顯然 x 0 ；式中的變量x3, x4 0，即為引入的松弛變量，引進(jìn)模型后它們?cè)谀繕?biāo)函數(shù)中的系數(shù)均為零。取值無(wú)約束的變量。如果變量x代表某產(chǎn)品當(dāng)年計(jì)劃數(shù)之差，顯然x的取值可能是正也可能是負(fù)，這時(shí)可令x = x-x，

5、其中x 0, x 0，將其代入線性規(guī)劃模型即可。對(duì)x 0。滿足約束條件的解X = (x ,x , ,x )稱為問(wèn)題的可行解，可行解的全體稱為可行域；12 . . . n使目標(biāo)函數(shù)達(dá)到最大值的可行解稱為最優(yōu)解?？尚杏蚴且粋€(gè)凸多邊形，最優(yōu)解若存在一定在其某個(gè)頂點(diǎn)上取得。所謂凸集C，是指對(duì)任何X1，X渣C，有a% + (l-a)X2M (。a 1)。頂點(diǎn) X 仁 C):不存在 , X? M ,使得X =a % + （1-。） X 2 e C （0 a 1）。所謂凸多邊形，就是把一個(gè)多邊形任意一邊向兩方無(wú)限延長(zhǎng)成為一條直線，如果多邊形 的其它各邊均在此直線的同旁，那么這個(gè)多邊形就叫做凸多邊形。如圖5.

6、1,多邊形ABCDEF，把線段AF向兩方無(wú)限延長(zhǎng)，此多邊形的其它各邊AB、BC、CD、DE、EF均 在此直線的同旁，所以多邊形ABCDEF是凸多邊形。圖5.1凸多邊形值得注意的是，在凸多邊形的定義中，延長(zhǎng)的這一邊是凸多邊形的任意一邊。圖5.2中 的多邊形ABCDEF，若分別把AB、BC、CD、DE各邊延長(zhǎng)為直線，這時(shí)均滿足凸多邊形 的定義，但這時(shí)并不能說(shuō)多邊形是凸多邊形。因?yàn)?，延長(zhǎng)線段AF為直線后，多邊形其它各 邊并不在此直線的同旁。同樣，把線段FE延長(zhǎng)為直線后，又有類似的情況出現(xiàn)。B DC圖5.2凹多邊形在二維情況下可用圖解法或計(jì)算頂點(diǎn)的枚舉法求解，但在決策變量較多時(shí)，圖解法失 效，枚舉法計(jì)

7、算量較大，通常用基于線性方程組變換的單純形法進(jìn)行求解。圖解法（又稱幾何法）圖解法是對(duì)于只是兩個(gè)決策變量的線性規(guī)劃問(wèn)題，在平面內(nèi)建立直角坐標(biāo)系，使每個(gè) 決策變量的取值在一個(gè)數(shù)軸上表示出來(lái)，可行解就成為平面上的點(diǎn)，可行域就是平面上的 一個(gè)共域，從而最優(yōu)解必定是在這個(gè)平面區(qū)域內(nèi)（包括邊界上）的點(diǎn)。根據(jù)目標(biāo)函數(shù)在這 個(gè)平面區(qū)域內(nèi)的取值找出使目標(biāo)函數(shù)取得最優(yōu)值的點(diǎn)（即最優(yōu)解）。圖解法便于我們理解和了解線性規(guī)劃問(wèn)題的一些概念、理論及解的一些特性，也為我 們進(jìn)一步學(xué)習(xí)單純方法提供一個(gè)直觀圖形。1例5.2求解線性問(wèn)題7 x +5x =106min S = 7 x + 5 x12+ 2 x2 = 287氣 +

8、5x2 = 50 x + 2x 28S .t Mx + x 0虹12圖5.3線性規(guī)劃圖解法解：第一步，在平面直角坐標(biāo)系Oxix2上繪出約束條件圖，如圖5.3所示。畫出這條直線氣+ 2x2= 28，再定出氣+ 2x2 28區(qū)域。把（0, 0 ）代入不等式得0 + 20 V28,所以，原點(diǎn)所在半平面及直線本身就是 氣+ 2x2 28代表的區(qū)域。畫出4氣+ x2= 42這條直線，定出4氣+ x2 42代表的區(qū)域，有（0，0）代入不等式得04+0V42所以，4氣+ x2 0, x2 0的區(qū)域，它就是第一象限。從圖5.3看出，滿足全部約束條件的 點(diǎn)所構(gòu)成的區(qū)域（即可行域），就是凸多邊形OABC。第二步，

9、繪制目標(biāo)函數(shù)圖形。對(duì)于目標(biāo)函數(shù)S = 7氣+ 5x2將S看作參數(shù)，即得到一簇 平行直線（圖5.3中虛線所示），直線上每一點(diǎn)的目標(biāo)函數(shù)值為S。由圖可見(jiàn)，直線離原點(diǎn) 越遠(yuǎn)，S值越大，我們尋找的是在可行域內(nèi)使S值最大點(diǎn)?？梢?jiàn)，B點(diǎn)即為可行域內(nèi)使目 標(biāo)函數(shù)最大的點(diǎn)，即為最優(yōu)解。第三步，確定最優(yōu)解。B點(diǎn)是直線氣+2x2= 28與4x+x2=42交點(diǎn)，所以解方程組J x + 2 x = 284 x + x = 42得到x廣8, x2 = 10這就是最優(yōu)解。將其代入目標(biāo)函數(shù)，得最優(yōu)解maxS = 7x8 + 5 x 10=106例中有可行解且有唯一最優(yōu)解將目標(biāo)函數(shù)改為S =氣+ 2x2或S = 4氣+ x2

10、仍求其最大 值，則BC或AB上每一點(diǎn)的坐標(biāo)均為最優(yōu)解，最優(yōu)解有無(wú)窮多個(gè)，而它們對(duì)應(yīng)的目標(biāo)函數(shù) 數(shù)值是28或42。單純形法線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式用矩陣可表示為:max z = ctx（LP） 0, x e Rn其中，c為n維列向量，A為mxn矩陣，b為m維列向量。設(shè)m 01212單純形表0 （原始表）X1X2y1y2z右端項(xiàng)3110024 ( y)12201020 ( y2)18)-150010 ( z)相關(guān)變量：3， y， z；獨(dú)立變量：X X 0 ；頂點(diǎn)：（X ,X ）=（。,。）；目標(biāo)函數(shù)121212值：z 0最優(yōu)化檢驗(yàn)進(jìn)入變量是X （對(duì)應(yīng)于最后一行的系數(shù)）1可行性檢驗(yàn)用右端項(xiàng)除以X1所在

11、列的系數(shù)，計(jì)算相應(yīng)的比值，并確定正的最小比值。X1X2y1y2z右端項(xiàng)比值31100248(=24/3)220102010(=20/2)-18-150010*退出變量正的最小比值為8,選擇對(duì)應(yīng)的變量y1為退出變量。旋轉(zhuǎn)將退出變量所在的行（這里是第1彳?。┏栽撔兄羞M(jìn)入變量的系數(shù)（這里是X1的系數(shù)）， 使得進(jìn)入變量在本行中的系數(shù)變?yōu)?,用消元法消去其它行的進(jìn)入變量X1，這些行中不含 有退出變量（對(duì)應(yīng)的系數(shù)為0）。結(jié)果表示見(jiàn)單純形表1。單純形表1相關(guān)變量：x， y， z；獨(dú)立變量：X = y = 0；頂點(diǎn)：（x ,X ） = （8，0）；目標(biāo)函數(shù)122112xxJJz右端項(xiàng)121211/31/30

12、08 （=氣）04/3-2/3104 (= y2)0601144(= z)值：z = 144最優(yōu)化檢驗(yàn)進(jìn)入變量是x （對(duì)應(yīng)于最后一行的系數(shù)-9）2最小正比值為3,可行性檢驗(yàn)xxyiy2z右端項(xiàng)比值11/31/30082404/3-2/310430-96010*用右端項(xiàng)除以X2所在列的系數(shù)，計(jì)算相應(yīng)的比值，并確定正的最小比值。進(jìn)入變量選擇對(duì)應(yīng)的J為退出變量。退出變量旋轉(zhuǎn)類似于前面，得到結(jié)果見(jiàn)下表:單純形表2x1x2y12z右端項(xiàng)101/2-1/40701-1/23/403003/227/41171由單純形法計(jì)算結(jié)果可以知道，甲、乙兩種方式組網(wǎng)數(shù)分別為7和3時(shí)，能在規(guī)定的 條件下，使得提供的話路總

13、數(shù)z達(dá)到最大，其值為171。5.1.2目標(biāo)規(guī)劃前面所述的線性規(guī)劃問(wèn)題在實(shí)際中有很多局限性，如：目標(biāo)單一，局限于某個(gè)方案的 最優(yōu)性；各約束條件必須相容；線性規(guī)劃解的可行性和最優(yōu)性是針對(duì)特定的數(shù)學(xué)模型的， 而這種數(shù)學(xué)模型只是對(duì)實(shí)際問(wèn)題的某種近似，在設(shè)計(jì)和規(guī)劃過(guò)程中，還需考慮新的情況。 由于目標(biāo)規(guī)劃能在一定程度上彌補(bǔ)線性規(guī)劃的上述局限性，因而被認(rèn)為是較為接近于實(shí)際 決策過(guò)程的決策工具。目標(biāo)規(guī)劃問(wèn)題的建模目標(biāo)規(guī)劃解決的是多目標(biāo)決策問(wèn)題。這些目標(biāo)很多時(shí)候是互不相容且有輕重緩急之分 的，如在軍事通信網(wǎng)的組建中，通常要考慮這樣一些決策目標(biāo)：通信網(wǎng)的可靠性、抗毀性、 安全保密性、抗干擾性、機(jī)動(dòng)性、組網(wǎng)投入少等

14、，這些決策目標(biāo)有的沖突，有的相容，且 針對(duì)不同的作戰(zhàn)方式，所要考慮的目標(biāo)達(dá)成的優(yōu)先順序和側(cè)重點(diǎn)是不同的。目標(biāo)規(guī)劃就是 在處理這類決策問(wèn)題時(shí)，承認(rèn)各項(xiàng)決策目標(biāo)的合理性，而不強(qiáng)調(diào)其絕對(duì)意義的最優(yōu)性，按 優(yōu)先等級(jí)兼顧各個(gè)目標(biāo)，盡量滿足某些約束條件。下面以一個(gè)具體的目標(biāo)規(guī)劃問(wèn)題為例來(lái) 說(shuō)明目標(biāo)規(guī)劃問(wèn)題的模型建立和求解。例5.4對(duì)例5.3的單目標(biāo)規(guī)劃問(wèn)題，再提出以下目標(biāo)要求：甲方式的組網(wǎng)數(shù)盡可能 不超過(guò)乙方式的組網(wǎng)數(shù)；設(shè)備B盡量用完；總話路數(shù)不低于156；設(shè)備A的總量絕 對(duì)不允許突破。問(wèn)：如何確定甲、乙兩種方式的組網(wǎng)數(shù)量，才能滿足以上要求？要建立該目標(biāo)規(guī)劃問(wèn)題的數(shù)學(xué)模型，還需要引入與建模有關(guān)的一些概念。

15、與線性規(guī)劃 模型不同，目標(biāo)規(guī)劃模型的每個(gè)約束關(guān)系式對(duì)應(yīng)一個(gè)決策目標(biāo)，對(duì)每一個(gè)決策目標(biāo)，引入正、負(fù)偏差變量d +和d-，分別表示決策值超過(guò)或不足目標(biāo)值的部分。使約束條件嚴(yán)格滿 足的約束稱為硬約束，硬約束無(wú)偏差變量；使約束條件盡量滿足的約束稱為軟約束，其決 策值和目標(biāo)值之間的差異用偏差變量表示。不同目標(biāo)的主次輕重的描述可以用優(yōu)先因子和 權(quán)系數(shù)來(lái)表示。將軟約束對(duì)應(yīng)的目標(biāo)分為若干優(yōu)先等級(jí)，用優(yōu)先因子馬(/ =1,2, .，k)來(lái)表示。優(yōu)先因子之間的關(guān)系為pP ，表示P對(duì)應(yīng)的目標(biāo)比P對(duì)應(yīng)的目標(biāo)有絕對(duì)的優(yōu)先ll+1ll+1性，若不同的目標(biāo)有相同的優(yōu)先因子，則可以用權(quán)系數(shù)的不同來(lái)表示其重要程度的差異。 目標(biāo)

16、規(guī)劃的目標(biāo)函數(shù)由各目標(biāo)約束的偏差變量、相應(yīng)的優(yōu)先因子的權(quán)系數(shù)構(gòu)成因目標(biāo)函數(shù) 追求的是盡可能地接近目標(biāo)值，故其目標(biāo)函數(shù)是使得各約束關(guān)系式的偏差變量之和構(gòu)成的 偏差變量和函數(shù)最小化。應(yīng)用中，有3種基本形式。要求恰好達(dá)到目標(biāo)值：minf(d + d-)；要求不超過(guò)目標(biāo)值：minf(d+)；要求不低于目標(biāo)值：minf(d-)。設(shè)P，P，P分別是的優(yōu)先因子，d+，d-(i = 1,2,3)是相應(yīng)的正、負(fù)偏差變量，z為123i i偏差總和，則例5.3的目標(biāo)規(guī)劃問(wèn)題數(shù)學(xué)模型可建立為：min z = p d+，p (d - + d+)，p d -)1 12223 33 尤+ x 24 TOC o 1-5 h

17、z HYPERLINK l bookmark110 o Current Document x - x + d - - d + = 0 1211 0, d-, d + 0, i = 1,2,31211目標(biāo)規(guī)劃數(shù)學(xué)模型的一般形式為 HYPERLINK l bookmark122 o Current Document minp (f (W-d-+ W+d+),l = 1,2, ,L) lIk k Ik k k=1 HYPERLINK l bookmark125 o Current Document f c x + d- - d + = g k = 1,2, , K kj j k k kj=1st a

18、 x ) = b i = 1,2, , mij jij=1x. 0 j = 1,2,.,n HYPERLINK l bookmark134 o Current Document d-, d + 0 k = 1,2, , K k k.其中，g為第k個(gè)目標(biāo)約束的預(yù)期目標(biāo)值，W-和W +為p優(yōu)先因子對(duì)應(yīng)各目標(biāo)的權(quán) klk lk l系數(shù)。目標(biāo)規(guī)劃問(wèn)題的求解目標(biāo)規(guī)劃的圖解法對(duì)于只有兩個(gè)決策變量的目標(biāo)規(guī)劃問(wèn)題，可以用圖解法來(lái)求解。例5.5用圖解法解例5.4的目標(biāo)規(guī)劃模型。解：解題過(guò)程見(jiàn)圖5.4。圖5.4中，AOAB區(qū)域是硬約束的解空間，去掉偏差變量，畫出所有軟約束的邊界直 線，然后標(biāo)出偏差變量變化時(shí)直線的平移方向。按優(yōu)先級(jí)高低，首先考慮P，得解