第1章 線性規(guī)劃模型

第1章線性規(guī)劃Chapter1LinearProgramming本章內(nèi)容提要線性規(guī)劃是運(yùn)籌學(xué)的重要內(nèi)容。本章介紹線性規(guī)劃數(shù)學(xué)模型、線性規(guī)劃的基本概念以及求解線性規(guī)劃數(shù)學(xué)模型的專門軟件——Lingo。學(xué)習(xí)本章要求掌握以下內(nèi)容：線性規(guī)劃模型的結(jié)構(gòu)。包括：決策變量，目標(biāo)函數(shù)，約束條件。線性規(guī)劃的標(biāo)準(zhǔn)形式，非標(biāo)準(zhǔn)形式轉(zhuǎn)化為標(biāo)準(zhǔn)形式線性規(guī)劃的基本概念。包括：約束直線，可行域，可行解，凸集，極點(diǎn)，目標(biāo)函數(shù)等值線，最優(yōu)解線性規(guī)劃的軟件求解。包括：lingo軟件簡介，lingo軟件求解規(guī)劃問題§1.1線性規(guī)劃1.1.1線性規(guī)劃線性規(guī)劃（LinearProgramming，LP）是運(yùn)籌學(xué)中最重要的一種系統(tǒng)優(yōu)化方法。它的理論和算法已十分成熟，應(yīng)用領(lǐng)域十分廣泛，通常研究資源的最優(yōu)利用、設(shè)備最佳運(yùn)行等問題。例如，當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)；企業(yè)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤最大）。還包括生產(chǎn)計(jì)劃，物資調(diào)運(yùn)，資源優(yōu)化配置，物料配方，任務(wù)分配，經(jīng)濟(jì)規(guī)劃等問題。隨著計(jì)算機(jī)硬件和軟件技術(shù)的發(fā)展，目前用微型計(jì)算機(jī)就可以求解大規(guī)模的規(guī)劃問題。Lingo軟件就是其中的代表軟件之一。在本章中，我們將介紹線性規(guī)劃的基本概念，線性規(guī)劃在經(jīng)濟(jì)分析中的應(yīng)用?！?.2線性規(guī)劃問題線性規(guī)劃問題由目標(biāo)函數(shù)、約束條件以及變量的非負(fù)約束三部分組成。根據(jù)實(shí)際問題的條件和要求，可以建立線性規(guī)劃問題數(shù)學(xué)模型。下面列舉五種最常見的線性規(guī)劃問題的類型。1.2.1生產(chǎn)計(jì)劃問題例1.1某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙、丙、丁四種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用的設(shè)備機(jī)時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時(shí)數(shù)如下表所示：表1-1每件產(chǎn)品占用的機(jī)時(shí)數(shù)（小時(shí)/件）產(chǎn)品甲產(chǎn)品乙產(chǎn)品丙產(chǎn)品丁設(shè)備能力（小時(shí)）設(shè)備A1.51.02.41.02000設(shè)備B1.05.01.03.58000設(shè)備C1.53.03.51.05000利潤（元/件）5.247.308.344.18用線性規(guī)劃制訂使總利潤最大的生產(chǎn)計(jì)劃。設(shè)變量xi為第i種產(chǎn)品的生產(chǎn)件數(shù)（i=1,2,3,4）,目標(biāo)函數(shù)z為相應(yīng)的生產(chǎn)計(jì)劃可以獲得的總利潤。在加工時(shí)間以及利潤與產(chǎn)品產(chǎn)量成線性關(guān)系的假設(shè)下，可以建立如下的線性規(guī)劃模型：maxz=5.24x1+7.30x2+8.34x3+4.18x4目標(biāo)函數(shù)s.t.1.5x1+1.0x2+2.4x3+1.0x<200041.0x1+5.0x2+1.0x3+3.5x<80004約束條件1.5x1+3.0x2+3.5x3+1.0x<50004xi,x2,x3,x N04變量非負(fù)約束這是一個(gè)典型的利潤最大化的生產(chǎn)計(jì)劃問題。其中max表示極大化（maximize），s.t.是subjectto的縮寫。求解這個(gè)線性規(guī)劃，可以得到最優(yōu)解為：x1=294.12 x2=1500 x3=0 x4=58.82 （件）最大利潤為z=12737.06（元）請(qǐng)注意最優(yōu)解中利潤率最高的產(chǎn)品丙在最優(yōu)生產(chǎn)計(jì)劃中不安排生產(chǎn)。說明按產(chǎn)品利潤率大小為優(yōu)先次序來安排生產(chǎn)計(jì)劃的方法有很大局限性。尤其當(dāng)產(chǎn)品品種很多，設(shè)備類型很多的情況下，用手工方法安排生產(chǎn)計(jì)劃很難獲得滿意的結(jié)果。

1.2.2配料問題例1?2某工廠要用四種合金T1,T2,T3和T4為原料，經(jīng)熔煉成為一種新的不銹鋼G。這四種原料含元素格（Cr），錳（Mn）和鎳（Ni）的含量（%），這四種原料的單價(jià)以及新的不銹鋼材料G所要求的Cr，Mn和Ni的最低含量（％）如下表所示:表1-2TiT2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30單價(jià)（元/公斤）115978276設(shè)熔煉時(shí)重量沒有損耗，要熔煉成100公斤不銹鋼G，應(yīng)選用原料T「T2,T3和T4各多少公斤，使成本最小。設(shè)選用原料T］，T2，T3和T4分別為X］，x2，x3，x4公斤，根據(jù)條件，可建立相應(yīng)的線性規(guī)劃模型如下：minz= 115x1+97x2+82x3+76x4s.t. 0.0321x1+0.0453x2+0.0219xq3+0.0176x,4N3.200.0204x1+0.0112x2+0.0357x3+0.0433x4N2.100.0582x1+0.0306x2+0.0427x3+0.0273x4N4.30x1+x2+x3+x4=100xi,x2,x3,x4N0這是一個(gè)典型的成本最小化的問題。其中min表示極小化（minimize）0這個(gè)線性規(guī)劃問題的最優(yōu)解是x1=26.58 x2=31.57 x3=41.84 x4=0 （公斤）最低成本為z=9550.889（元）1.2.3背包問題例1.3一只背包最大裝載重量為50公斤?，F(xiàn)有三種物品，每種物品數(shù)量無限。每種物品每件的重量、價(jià)值如下表所示：

表1-3物品1物品2物品3重量（公斤/件）104120價(jià)值（元/件）177235要在背包中裝入這三種物品各多少件，使背包中的物品價(jià)值最高。設(shè)裝入物品1，物品2和物品3各為xi，x2，x3件，由于物品的件數(shù)必須是整數(shù)，因此背包問題的線性規(guī)劃模型是一個(gè)整數(shù)規(guī)劃問題：maxz=17x1+72xo2+35x3s.t.10x1+41x2+20x3W50x1,x2,x3N0,x1，x2,x3是整數(shù)這個(gè)問題的最優(yōu)解是：x1=1件,x2=0件,x3=2件，最高價(jià)值為：z=87元1.2.4運(yùn)輸問題例1.4設(shè)某種物資從兩個(gè)供應(yīng)地A「A2運(yùn)往三個(gè)需求地B「B2,B3。各供應(yīng)地的供應(yīng)量、各需求地的需求量、每個(gè)供應(yīng)地到每個(gè)需求地的單位物資運(yùn)價(jià)如下表所示。表1-4運(yùn)價(jià)（元/噸）B1B2B3供應(yīng)量（噸）A123535A247825需求量（噸）103020這個(gè)問題也可以用圖解表示如下，其中節(jié)點(diǎn)A.A2表示發(fā)地，節(jié)點(diǎn)B］、B2、35噸25噸1035噸25噸10噸30噸20噸B3表示收地，從每一發(fā)地到每一收地都有相應(yīng)的運(yùn)輸路線，共有6條不同的運(yùn)輸路線。設(shè)％.為從供應(yīng)地A】運(yùn)往需求地Bj的物資數(shù)量（i=l,2；j=l,2,3）,z為總運(yùn)費(fèi)，則總運(yùn)費(fèi)最小的線性規(guī)劃模型為：minz=2x11+3X12+5x13+4x21+7x22+8x23s.t.x11+x12+x13=35⑴x21+x22+x23=25(2)x11+x21=10⑶x12+x22=30⑷x13+x23=20⑸x.20ij以上約束條件（1）、（2）稱為供應(yīng)地約束，（3）、（4）、（5）稱為需求地約束。這個(gè)問題的最優(yōu)解為：X]]=0,x12=30,x13=5,x21=10,x22=0,x23=15（噸）；最小運(yùn)費(fèi)為：z=275元。1.2.5指派問題例1.5有n項(xiàng)任務(wù)由n個(gè)人去完成，每項(xiàng)任務(wù)交給一個(gè)人，每個(gè)人都有一項(xiàng)任務(wù)。由第i個(gè)人去做第j項(xiàng)任務(wù)的成本（或效益）為％。求使總成本最?。ɑ蛐б孀畲螅┑姆峙浞桨?。次 [0第i個(gè)人不從事第j項(xiàng)任務(wù)設(shè)： x..=<ij[1第i個(gè)人被指派完成第j項(xiàng)任務(wù)得到以下的線性規(guī)劃模型：min（max）z=8玲.i=1J=1s.t Ex=1J=1,2,...,niji=1Ex=1i=1,2,.,niJj=1X=0,1例如，有張、王、李、趙4位教師被分配教語文、數(shù)學(xué)、物理、化學(xué)4門課程，每位教師教一門課程，每門課程由一位老師教。根據(jù)這四位教師以往教課的情況，他們分別教這四門課程的平均成績?nèi)缦卤恚?/p>

表1-5語文數(shù)學(xué)物理化學(xué)張92688576王82917763李83907465趙93618375四位教師每人只能教一門課，每一門課只能由一個(gè)教師來教。要確定哪一位教師上哪一門課，使四門課的平均成績之和為最高。設(shè)x..（i=1,2,3,4；j=1,2,3,4）為第i個(gè)教師是否教第j門課，乂而只能取值0或1，其意義如下：x=[0第i個(gè)教師不教第.門課Xij=〔1第i個(gè)教師教第.門課變量X.J與教師i以及課程j的關(guān)系如下：表1-6X語文數(shù)學(xué)物理化學(xué)張x11x12x13x14王x21x22x23x24李x31x32x33x34趙x41x42x43x44這個(gè)指派問題的線性規(guī)劃模型為:maxz=92x+68x+85xo+76x+82x+91x+77xo+63xOJ11 12 13 14 21 22 23 24+83x+90xmaxz=92x+68x+85xo+76x+82x+91x+77xo+63xOJ11 12 13 14 21 22 23 24+83x+90xo+74xo+65x+93x,+61xo+83xo+75x^<31 32 33 34 41 42 43 44S.t. xn+x12+x13+x14=1x21+x22+x23+x24Tx31+x32+x33+x34=1x41+x42+x43+x44=1x11+x21+x31+x41=1x12+x22+x32+x42=1（1）（2）（3）（4）（5）（6）X13+X23+X33+X43=1X14+X24+X34+X44=1(7)(8)(7)(8)這個(gè)問題的最優(yōu)解為X14=1,X23=1,X32=1,X41=1,maxz=336；即張老師教化學(xué)，王老師教物理，李老師教數(shù)學(xué)，趙老師教語文，如果這樣分配教學(xué)任務(wù)，四門課的平均總分可以達(dá)到336分。在線性規(guī)劃問題中，如果所有的變量都只能取值0或1。這樣的線性規(guī)劃問題稱為(純)0—1整數(shù)規(guī)劃問題。如果一個(gè)線性規(guī)劃問題中，有的變量是連續(xù)變量，而另一些變量是0—1變量，這樣的問題稱為混合0—1規(guī)劃問題?！?.3線性規(guī)劃問題的數(shù)學(xué)模型由以上5個(gè)例子，我們可以歸納出線性規(guī)劃問題的數(shù)學(xué)模型和一般形式：上述5個(gè)例子的3個(gè)共同點(diǎn)每個(gè)問題都有一組變量 稱為決策變量都有一個(gè)關(guān)于決策變量的函數(shù)每個(gè)問題都有一組決策變量需滿足的約束條件線性規(guī)劃問題定義：將約束條件及目標(biāo)函數(shù)都是決策變量的線性函數(shù)的規(guī)劃問題稱為線性規(guī)劃問題。建立線性規(guī)劃問題的數(shù)學(xué)模型步驟確定問題的決策變量確定問題的目標(biāo)，并表示為決策變量的線性函數(shù)找出問題的所有約束條件，并表示為決策變量的線性方程或不等式線性規(guī)劃的數(shù)學(xué)模型假定線性規(guī)劃問題中含n個(gè)變量，分別用xj(j=1,...,n)表示，在目標(biāo)函數(shù)中，xj的系數(shù)為cj(通常稱為價(jià)值系數(shù))。xj的取值受m項(xiàng)資源的限制，用bi(i=1,...,m)表示第i種資源的擁有量，用aij表示變量xj的取值為一個(gè)單位時(shí)所消耗或含有的第i種資源的數(shù)量(通常稱為技術(shù)系數(shù)或工藝系數(shù))。則上述線性規(guī)劃問題的數(shù)學(xué)模型可以表示為

max(min)z=cx+cx+???+cx+? +cx1122jj nnst ax+ax+?+ax +—+ax <(=,>)b1111221jj 1nn 1ax+ax+?+ax +—+ax <(=,>)b2112222jj 2nn 2??.??? ? ? ?ax+ax+?+ax +—+ax<(=,>)bm11m22mjj mnn mxx?x… x >012jn其中max(min)z=cx+cx+?11 22??+cx+ +cxjj nn稱為目標(biāo)函數(shù)，ax +ax+—+ax+—+ax <(=>)b111 1221jj1nn 1ax +ax+—+ax+?+ax <(=>)b211 222?… ?…2jj?????-2nn 2? ? ?ax +ax+—+ax+—+ax<(=>)bm11 m22mjjnmn m稱為約束條件，x1，x2,…，xj，…，xn>0稱為變量的非負(fù)約束。在線性規(guī)劃問題中，目標(biāo)函數(shù)是變量的線性函數(shù)，約束條件是變量的線性不等式。例如以下的問題就不是線性規(guī)劃問題而是非線性規(guī)劃問題了：maxz=5x1x2+2x3s.t.2x12+3x2-—<15x3Ix1-x2l+4x3>14x1,x2，x3>0記向量和矩陣C=c1C2，X=「x[1x2，b=bb2，A=a11a21a?12a?22a1na2n:::?????????cxbaa?a1-n」n1-m」m1m2mn則線性規(guī)劃問題可由向量和矩陣表示max(min)z=CTXs.t. AXW(=,3)bX30§1.3線性規(guī)劃問題的標(biāo)準(zhǔn)形式由于目標(biāo)函數(shù)和約束條件內(nèi)容和形式上的差別，線性規(guī)劃問題有多種表達(dá)式，為了便于討論和制定統(tǒng)一的算法，規(guī)定標(biāo)準(zhǔn)形式如下：目標(biāo)函數(shù)極大化；約束條件為等式且右端項(xiàng)30；決策變量30。為了今后討論的方便，我們稱以下線性規(guī)劃的形式為標(biāo)準(zhǔn)形式：minz=CTXs.t.AX=bX30對(duì)于各種非標(biāo)準(zhǔn)形式的線性規(guī)劃問題，我們總可以通過以下的變換，將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式。*1.3.1極大化目標(biāo)函數(shù)的問題設(shè)目標(biāo)函數(shù)為maxz=cx+cxH Fcx11 22 nn令z’=—z，則以上極大化問題和極小化問題有相同的最優(yōu)解，即minz=-cx一cx cx11 22 nn但必須注意，盡管以上兩個(gè)問題的最優(yōu)解相同，但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個(gè)符號(hào)，即max z=—minz’*1.3.2約束條件不是等式的問題設(shè)約束條件為a.ixi+a.2x2+ +a.x<b. (.=1,2,...,m)可以引進(jìn)一個(gè)新的變量xn+.，使它等于約束右邊與左邊之差x=b一(ax+ax+ +ax)n+. . .11 .22 .nn顯然xn+i也具有非負(fù)約束，即xn+.30，這時(shí)新的約束條件成為a.ixi+a.2x2+ +a.x+x.=b.當(dāng)約束條件為a，ixi+a,2x2H fa.x>b,時(shí)，類似地令x.=(a，ixi+a.2x2+ +a.x)一b.則同樣有xn+.30，新的約束條件成為

a.]X]+a.2X2+ +aix-x.=bi為了使約束由不等式成為等式而引進(jìn)的變量 xn+i稱為“松弛變量（SlackVariables）"。如果原問題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量。例1.6將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式maxz=3x1-2X2+X3s.t. X]+2X2-x3W5(1)4x1+3x338(2)xi+X2+x3=6(3)xi，x2，X330將目標(biāo)函數(shù)轉(zhuǎn)換成極小化，并分別對(duì)約束（1）、（2）引進(jìn)松弛變量X4，X5，下標(biāo)準(zhǔn)形式的線性規(guī)劃問題minz’=-3x1+2X2-x3s.t. X1+2X2-x3+x4=54x1+3X3 -X5=8x1+X2+x3=6x1，x2，X3, X4，X530得到以*1.3.3變量無符號(hào)限制的問題在標(biāo)準(zhǔn)形式中，每一個(gè)變量都有非負(fù)約束。當(dāng)一個(gè)變量Xj沒有非負(fù)約束時(shí)，可以令其中注河，x”30即用兩個(gè)非負(fù)變量之差來表示一個(gè)無符號(hào)限制的變量，當(dāng)Xj的符號(hào)取決于x《和X”的大小。例1.7將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式maxz=2x1-3x2+x3s.t. X1-x2+2x3W32x1+3x2-x335X+x+x=4123x1,x3^0,x2無符號(hào)限制令z’=-z,引進(jìn)松弛變量x4,X530,并令

X2=X2-X2其中x2'30,x；30得到以下等價(jià)的標(biāo)準(zhǔn)形式minz’=-2x1+3x；-3X2”-X3s.t. X]-X2'+X；'+2X3+X4=32x1+3x；-3X2”-X3-X5=5x1+X2'-X2''+X3=4X1，x；，X2''，X3,X4，X5對(duì)*1.3.4變量小于等于零的問題在一些實(shí)際問題中，變量不允許為正數(shù)，這樣的問題也需要轉(zhuǎn)化為標(biāo)準(zhǔn)問題。例如：minz=3xi-5X2+X3s.t.2xi+4X2+X3W]5-xi-3X2+2x336X]30X2<0x330令X2=-X'2，x'230,原問題成為:minz=3xi+5x'2+X3s.t.2xi-4x'2+X3W]5-xi+3x'2+2x336x]30x'230x330然后引進(jìn)松弛變量X4,X5,成為標(biāo)準(zhǔn)問題：minz=3x +5x'1 2+X3s.t. 2x-4x'1 2+X3+X4 T5-X1 +3x'2+2x3 -X5 =6xi x'2X3 X4 X5 30這樣，我們就能夠?qū)⑷魏畏菢?biāo)準(zhǔn)形式的線性規(guī)劃問題轉(zhuǎn)化為等價(jià)的標(biāo)準(zhǔn)形式問題。*§1.4線性規(guī)劃問題的幾何解釋對(duì)于只有兩個(gè)變量的線性規(guī)劃問題，可以在二維直角坐標(biāo)平面上表示線性規(guī)劃問題。例1?8maxz=x1+3x2TOC\o"1-5"\h\z\o"CurrentDocument"s.t.x1 +x2W6 (1)\o"CurrentDocument"-x.+2x2W8 (2)x], x230 「x1 ...其中滿足約束(1)的點(diǎn)X=1位于坐標(biāo)平面上直線x+x=6靠近原點(diǎn)的一%」 1'側(cè)。同樣，滿足約束(2)的點(diǎn)位于坐標(biāo)平面上直線-x.+2x2=8的靠近原點(diǎn)的一側(cè)。而變量x.,x2的非負(fù)約束表明滿足約束條件的點(diǎn)同時(shí)應(yīng)位于第一象限內(nèi)。這樣，以上幾個(gè)區(qū)域的交集就是滿足以上所有約束條件的點(diǎn)的全體。我們稱滿足線性規(guī)劃問題所有約束條件(包括變量非負(fù)約束)的向量X=(X],x2，…，X/T為線性規(guī)劃的可行解(FeasibleSolution)，稱可行解的集合為可行域(FeasibleRegion)。例1.8的線性規(guī)劃問題的可行域如圖1.2中陰影部分所示。為了在圖上表示目標(biāo)函數(shù)，令z=z0為某一確定的目標(biāo)函數(shù)值，取一組不同的z0值，在圖上得到一組相應(yīng)的平行線，稱為目標(biāo)函數(shù)等值線。在同一條等值線上的點(diǎn)，

相應(yīng)的可行解的目標(biāo)函數(shù)值相等。在圖1.2中，給出了z=0,z=3,z=6,…，z=15.3等一組目標(biāo)函數(shù)等值線，對(duì)于目標(biāo)函數(shù)極大化問題，這一組目標(biāo)函數(shù)等值線沿目標(biāo)函數(shù)增大而平行移動(dòng)的方向（即目標(biāo)函數(shù)梯度方向）就是目標(biāo)函數(shù)的系數(shù)向量C=（C］,c2，…，…,cn）T；對(duì)于極小化問題，目標(biāo)函數(shù)則沿-C方向平行移動(dòng)。在以上問題中，目標(biāo)函數(shù)等值線在平行移動(dòng)過程中與可行域的最后一個(gè)交點(diǎn)是B點(diǎn)，這就是線性規(guī)劃問題的最優(yōu)解，這個(gè)最優(yōu)解可以由兩直線X1+X2=6-X1+2x2=8的交點(diǎn)求得143'最優(yōu)解的目標(biāo)函數(shù)值為z=Xz=X]+3x2=4+3X14=3346為了將以上概念推廣到一般情況，我們給出以下定義:定義1?1在n維空間中，滿足條件a.,x+aXc+“?+a.x=b.111 122 inni的點(diǎn)集X=（X］，x2，...，xn）T稱為一個(gè)超平面。定義1.2滿足條件a.,x+ax+.+ax《（或＞）b.111 122inn i的點(diǎn)集X=（X］，x2，...，xn）T稱為n維空間中的一個(gè)半空間。定義1.3有限個(gè)半空間的交集，即同時(shí)滿足以下條件的非空點(diǎn)集a,x+ax+.+aX《（或》）b,TOC\o"1-5"\h\z111122 1nn 1a孵x+a”x+“?+a。x《（或＞）b0211222 2nn 2a,x+ax+.+ax《（或＞）bm11m22 mnn m稱為n維空間中的一個(gè)多面體。運(yùn)用矩陣記號(hào)，n維空間中的多面體也可記為AXW（或3）b

每一個(gè)變量非負(fù)約束xi^0(i=1,2,…，n)也都是半空間，其相應(yīng)的超平面就是相應(yīng)的坐標(biāo)平面x=0。i在圖1.2中，我們看到，線性規(guī)劃問題的可行域是一個(gè)凸多邊形。容易想象，在一般的n維空間中，n個(gè)變量，m個(gè)約束的線性規(guī)劃問題的可行域也應(yīng)具備這一性質(zhì)。為此我們引進(jìn)如下的定義。定義1.4設(shè)S是n維空間中的一個(gè)點(diǎn)集。若對(duì)任意n維向量XU，X2GS，且X/X2,以及任意實(shí)數(shù)入(0<!<1)，有X=XX1+(1-X)X2gS則稱S為n維空間中的一個(gè)凸集(ConvexSet)。點(diǎn)X稱為點(diǎn)X]和X2的凸組合。以上定義有明顯的幾何意義，它表示凸集S中的任意兩個(gè)不相同的點(diǎn)連線上的點(diǎn)(包括這兩個(gè)端點(diǎn))，都位于凸集S之中。(a)凸集(d)非凸集(b)凸集(c)凸集(f)非凸集(e)非凸集(a)凸集(d)非凸集(b)凸集(c)凸集(f)非凸集(e)非凸集圖1.3從圖1.2還可以看出，線性規(guī)劃如果有最優(yōu)解，其最優(yōu)解必定位于可行域邊界的某些點(diǎn)上。在平面多邊形中，這些點(diǎn)就是多邊形的頂點(diǎn)。在n維空間中，我們稱這樣的點(diǎn)為極點(diǎn)(ExtremePoint)0在凸集中，不能表為不同點(diǎn)的凸組合的點(diǎn)稱為凸集的極點(diǎn)。定義1.5設(shè)S為一凸集，且XgS，X1GS，X2gS。對(duì)于0<入<1，若X=XX1+(1-X)X2則必定有X=X]=X2，則稱X為s的一個(gè)極點(diǎn)。運(yùn)用以上的定義，線性規(guī)劃的可行域以及最優(yōu)解有以下性質(zhì)：1、 若線性規(guī)劃的可行域非空，則可行域必定為一凸集。2、 若線性規(guī)劃有最優(yōu)解，則最優(yōu)解至少位于一個(gè)極點(diǎn)上。這樣，求線性規(guī)劃最優(yōu)解的問題，從在可行域內(nèi)無限個(gè)可行解中搜索的問題轉(zhuǎn)化為在其可行域的有限個(gè)極點(diǎn)上搜索的問題。最后，來討論線性規(guī)劃的可行域和最優(yōu)解的幾種可能的情況。1、 可行域?yàn)榉忾]的有界區(qū)域有唯一的最優(yōu)解；有一個(gè)以上的最優(yōu)解；2、 可行域?yàn)榉欠忾]的無界區(qū)域有唯一的最優(yōu)解；有一個(gè)以上的最優(yōu)解；目標(biāo)函數(shù)無界(即雖有可行解，但在可行域中，目標(biāo)函數(shù)可以無限增大或無限減小)，因而沒有最優(yōu)解。3、 可行域?yàn)榭占?，因而沒有可行解。

§1.5線性規(guī)劃的基、基礎(chǔ)可行解由于圖解法無法解決三個(gè)變量以上的線性規(guī)劃問題，我們必須用代數(shù)方法來求得可行域的極點(diǎn)。先從以下的例子來看。例1?9maxz=x1+2x2s.t.x1+x2W3(1)x2W1(2)x1,x2對(duì)這個(gè)問題的圖解如圖1.5所示。引進(jìn)松弛變量x3,x4>0，問題變成為標(biāo)準(zhǔn)形式maxz=x1+2x2s.t.x1+x2+x3=3(1)x2+x4=1(2)x1x2x3 x4>0由上圖可以看出，直線AD對(duì)應(yīng)于約束條件(1)，位于AD左下側(cè)半平面上的點(diǎn)滿足約束條件x1+x2<3，即該半平面上的點(diǎn)，滿足x3>0。直線AD右上側(cè)半平面上的點(diǎn)滿足約束條件x1+x2>3，即該半平面上的點(diǎn)，滿足x3<0，而直線AD上的點(diǎn)，相應(yīng)的x3=0。同樣，直線BC上的點(diǎn)滿足x4=0，BC以下半平面中的點(diǎn)，滿足x4>0。BC以上半平面中的點(diǎn)，滿足x4<0。另外，OA上的點(diǎn)滿足x2=0，OD上的點(diǎn)滿足x1=0o由此可見，上圖中約束直線的交點(diǎn)O,A,B,C和D可以由以下方法得到：在標(biāo)準(zhǔn)化的等式約束中，令其中某兩個(gè)變量為零，得到其他變量的唯一解，這個(gè)解就是相應(yīng)交點(diǎn)的坐標(biāo)，如果某一交點(diǎn)的坐標(biāo)（x1，x2,x3,x4）全為非負(fù)，則該交點(diǎn)就對(duì)應(yīng)于線性規(guī)劃可行域的一個(gè)極點(diǎn)（如點(diǎn)A，B，C和O）；如果某一交點(diǎn)的坐標(biāo)中至少有一個(gè)分量為負(fù)值（如點(diǎn)D），則該交點(diǎn)不是可行域的極點(diǎn)。由圖1.5可知，O點(diǎn)對(duì)應(yīng)于x1=0，x2=0，在等式約束中令乂］=0，x2=0，得到Ux3=3,x4=1。即O點(diǎn)對(duì)應(yīng)于極點(diǎn)X=（xi，x2,x3,x4）T=（0，0，3，1）T。由于所有分量都為非負(fù)，因此O點(diǎn)是一可行域的極點(diǎn)。同樣，A點(diǎn)對(duì)應(yīng)于x=0,x=0,x=3,x=1；B點(diǎn)對(duì)應(yīng)于x=0,x=0,x=2,x=1；乙 J _L J _L 乙C點(diǎn)對(duì)應(yīng)于x1=0,x4=0,x2=1,x3=20以上都是極點(diǎn)。而D點(diǎn)對(duì)應(yīng)于x1=0,x3=0,x2=3,x4=-2,乂4的值小于0,因而不是極點(diǎn)。同時(shí)，我們也注意到，如在等式約束中令x2=0,x4=0,由于線性方程組的系數(shù)行列式等于0,因而土、x3無解。這在圖1.5中也容易得到解釋，這是由于對(duì)應(yīng)的直線x2=0和x4=0平行，沒有交點(diǎn)的緣故。對(duì)于一般的問題，獲得線性規(guī)劃可行域極點(diǎn)的方法可描述如下：設(shè)線性規(guī)劃的約束條件為AX=bXN0其中A為mXn的矩陣，n>m,^A=m,b為mX1向量。在約束等式中，令n維空間的解向量X=（x1，x2,?,xn）T中n-m個(gè)變量為零，如果剩下的m個(gè)變量在線性方程組中有唯一解，則這n個(gè)變量的值組成的向量X就對(duì)應(yīng)于n維空間中若干個(gè)超平面的一個(gè)交點(diǎn)。當(dāng)這n個(gè)變量的值都是非負(fù)時(shí)，這個(gè)交點(diǎn)就是線性規(guī)劃可行域的一個(gè)極點(diǎn)。根據(jù)以上分析，自然可以得到以下定義：定義1?6線性規(guī)劃的基（Basis）對(duì)于線性規(guī)劃的約束條件AX=bX>0^B是A矩陣中的一個(gè)非奇異的mxm子矩陣，則稱B為線性規(guī)劃的一個(gè)基。設(shè)B是線性規(guī)劃的一個(gè)基，則A可以表示為A=[B,N]X也可相應(yīng)地分成

其中XB^mXl向量，稱為基變量，其分量與基B的列向量對(duì)應(yīng)；XN^(n-m)X1向量，稱為非基變量，其分量與非基矩陣N的列對(duì)應(yīng)。這時(shí)約束等式AX=b可表示為M,n]：b=bXN或BXB+NXN=b若XN取確定的值，則XB有唯一的值與之對(duì)應(yīng)X=B-Ib-B-1NX”BN特別，取XN=0，這時(shí)有XB=B-ib。對(duì)于這樣一個(gè)特別的解，我們有以下定義：定義1?7線性規(guī)劃問題的基礎(chǔ)解(BasicSolution,BS)、基礎(chǔ)可行解(BasicFeasibleSolution,BFS)和可行基(FeasibleBasis,FB)線性規(guī)劃的解「X[「B-1b-B=XLN」0稱為線性規(guī)劃與基B對(duì)應(yīng)的基礎(chǔ)解。若其中基變量的值X=B-1b>0，則稱以上的基礎(chǔ)解為一基礎(chǔ)可行解，相應(yīng)的基BB稱為可行基。根據(jù)以上的分析，我們不加證明地給出以下定理：定理1.1線性規(guī)劃的基礎(chǔ)可行解就是可行域的極點(diǎn)。這個(gè)定理是線性規(guī)劃的基本定理，它的重要性在于把可行域的極點(diǎn)這一幾何概念與基礎(chǔ)可行解這一代數(shù)概念聯(lián)系起來，因而可以通過求基礎(chǔ)可行解的線性代數(shù)的方法來得到可行域的一切極點(diǎn)，從而有可能進(jìn)一步獲得最優(yōu)極點(diǎn)。例1.10求例1.9中線性規(guī)劃可行域的所有極點(diǎn)。這個(gè)線性規(guī)劃問題的標(biāo)準(zhǔn)形式的約束條件為：X1+X2+X3=3X2+X4=1xX1+X2+X3=3X2+X4=1x1，X2,X3,X4A=k,a2,a3,a4L11A矩陣包含以下六個(gè)2A矩陣包含以下六個(gè)2X2的子矩陣：B1=[a1，%] 與=虬，財(cái)B4=[a2，財(cái) 鳥=虬，％]B3=[a1，a4]B6=[a3，a4]其中B2=^其中B2=^a]=

a3-■=其行列式detB2=0,因而82不是線性規(guī)劃的一個(gè)基。其余均為非奇異方陣，因此該問題共有5個(gè)基。對(duì)于基B1=[a對(duì)于基B1=[a1，x3xL4」a2]，2「0=0令非基變量等于0得到基變量的值為非負(fù)，因而B為非負(fù)，因而B1是可行基。「x11「2「XB——=x2—=1XN」x一30xL4」0-x一「1-1320X=1=BTb==>Bx2l_01」110為對(duì)應(yīng)于基B1的一個(gè)基礎(chǔ)解。由于X的各分量均為非負(fù)，故X是一個(gè)基礎(chǔ)可行解，因而對(duì)應(yīng)于一個(gè)極點(diǎn)。事實(shí)上，這個(gè)極點(diǎn)就是圖1.5中的極點(diǎn)B。用同樣的方法，可以驗(yàn)證b3、b4、b6都是可行基，因而相應(yīng)的基礎(chǔ)解都是可行解，各對(duì)應(yīng)于一個(gè)極點(diǎn)。但B5不是可行基，這是因?yàn)閎5對(duì)應(yīng)的基礎(chǔ)解X=（X]，x2，x3，x4）T=（0，3，0，-2）T有小于零的分量，因而對(duì)應(yīng)的點(diǎn)D不是極點(diǎn)。定理1.1指出了一種求解線性規(guī)劃問題的可能途徑，這就是先確定線性規(guī)劃問題的基，如果是可行基，則計(jì)算相應(yīng)的基礎(chǔ)可行解以及相應(yīng)解的目標(biāo)函數(shù)值。由于基的個(gè)數(shù)是有限的（最多Cm個(gè)），因此必定可以從有限個(gè)基礎(chǔ)可行解中找到使目n標(biāo)函數(shù)為最優(yōu)（極大或極?。┑慕狻２恍业氖蔷€性規(guī)劃的基的個(gè)數(shù)是隨著問題規(guī)模的增大而很快增加，以至實(shí)際上成為不可窮盡的。舉例來說，一個(gè)有50個(gè)變量，20個(gè)約束等式的線性規(guī)劃問題。其最多可能有C20=_50_=4.7x10135020!30!個(gè)基。

為了說明計(jì)算所有基礎(chǔ)可行解的計(jì)算量有多大，我們假定計(jì)算一個(gè)基礎(chǔ)可行解(即求解一個(gè)20X20的線性方程組！)只需要一秒鐘，那么計(jì)算以上所有的基礎(chǔ)可行解需要4.7x4.7x10133600x24x365=1.5x106（年）即約150萬年。很顯然，借助于定理1.1來求解線性規(guī)劃問題，那怕是規(guī)模不大的問題，也是不可能的。而線性規(guī)劃的一種算法一一單純形法，可以極為有效地解決大規(guī)模的線性規(guī)劃問題。§1.6lingo軟件簡介及使用LINGO是LinearInteractiveandGeneralOptimizer的縮寫，即—交互式的線性和通用優(yōu)化求解器”，由美國LINDO系統(tǒng)公司(LindoSystemInc.)推出的，可以用于求解非線性規(guī)劃，也可以用于一些線性和非線性方程組的求解等，功能十分強(qiáng)大，是求解優(yōu)化模型的最佳選擇。其特色在于內(nèi)置建模語言，提供十幾個(gè)內(nèi)部函數(shù)，可以允許決策變量是整數(shù)(即整數(shù)規(guī)劃，包括0-1整數(shù)規(guī)劃)，方便靈活，而且執(zhí)行速度非?？臁Ｄ芊奖闩cEXCEL，數(shù)據(jù)庫等其他軟件交換數(shù)據(jù)。一般地，使用LINGO求解運(yùn)籌學(xué)問題可以分為以下兩個(gè)步驟來完成：根據(jù)實(shí)際問題，建立數(shù)學(xué)模型，即使用數(shù)學(xué)建模的方法建立優(yōu)化模型；根據(jù)優(yōu)化模型，利用LINGO來求解模型。主要是根據(jù)LINGO軟件，把數(shù)學(xué)模型轉(zhuǎn)譯成計(jì)算機(jī)語言，借助于計(jì)算機(jī)來求解。§1.6.1LINGO快速入門LINGO求解線性規(guī)劃的過程采用單純形法，一般是首先尋求一個(gè)可行解，在有可行解情況下再尋求最優(yōu)解。用LINGO求解一個(gè)LP問題會(huì)得到如下的幾種結(jié)果：不可行(Nofeasible)或可行(Feasible)；可行時(shí)又可分為：有最優(yōu)解(OptimalSolution)和解無界(UnboundedSolution)兩種情況。當(dāng)你在windows下開始運(yùn)行LINGO系統(tǒng)時(shí)，會(huì)得到類似下面的一個(gè)窗口：外層是主框架窗口，包含了所有菜單命令和工具條，其它所有的窗口將被包含在主窗口之下。在主窗口內(nèi)的標(biāo)題為LINGOModel-LINGO1的窗口是LINGO的默認(rèn)模型窗口，建立的模型都都要在該窗口內(nèi)編碼實(shí)現(xiàn)。讓我們來解如下的LP問題：例].10max七=2尤+3》[4x+3y<10<3x+5y<12、x,y>0由于LINGO中已假設(shè)所有的變量是非負(fù)的，所以非負(fù)約束不必再輸入到計(jì)算機(jī)中，LINGO也不區(qū)分變量中的大小寫字符（任何小寫字符將被轉(zhuǎn)換為大寫字符）；約束條件中的”<=”及”>=”可用”<”及”>”代替。上面的問題編寫程序如下：Model:MAX=2*X+3*Y;4*X+3*Y<10;3*X+5*Y<12;ENDLINGO中一般稱上面這種問題（PROBLEM）的實(shí)例（INSTANCE）的輸入為模型（MODEL），簡稱為“問題模型”。要LINGO編程中輸入模型時(shí)應(yīng)注意如下事項(xiàng)：（1） 以“model:”開頭，以“end”結(jié)束。（2） 目標(biāo)函數(shù)求最大時(shí)用“max=”，求最小時(shí)用“min=”。（3） 目標(biāo)函數(shù)及約束條件各語句之間要用分號(hào)“；”，如果兩個(gè)語句之間沒有分號(hào)，LINGO把此兩個(gè)語句看成是一個(gè)語句。（重要！）

運(yùn)算符號(hào)“+,一,*,/,"”按要求書寫，不可省略。(重要！)注釋語句在前面注有“!”符號(hào)，例如：！Thisisacomment。LINGO將目標(biāo)函數(shù)所在行作為第一行，從第二行起為約束條件，行號(hào)自動(dòng)產(chǎn)生。按工具欄上的Solve按鈕◎就可求得該問題的解。計(jì)算結(jié)果表明：“Globaloptimalsolutionfound."表示全局最優(yōu)解已經(jīng)找至U。“Objectivevalue:7.454545"表示最優(yōu)目標(biāo)值為7.4545450。“Infeasibilities:0.000000”表示初始值為0。“Totalsolveriterations:2”表示用單純形算法，迭代次數(shù)為2次。“Variable”給出最優(yōu)解中各變量的值(Value)：X=1.272727，Y=1.636364?！癛educedCost”給出最優(yōu)單純形表中第1行中變量的系數(shù)(max型問題)。其中基變量的reducedcost值應(yīng)為0，對(duì)于非基變量，相應(yīng)的reducedcost值表示當(dāng)該非基變量增加一個(gè)單位時(shí)(其他變量保持不變)目標(biāo)函數(shù)減少量。本例中此值均為0?！癝lackorSurplus”給出松弛變量的值：第2，3行松弛變量均為0,說明對(duì)最優(yōu)解來講，兩個(gè)約束(第2,3行)均取等號(hào)。這樣的約束也稱為緊約束，即表示約束的右端資源要全部用完?！癉ualPrice”給出對(duì)偶價(jià)格的值：第2,3行對(duì)偶價(jià)格分別為0.090909,0.545455。例1.11DAKOTA家具公司制造書桌(DESK),桌子(TABLE)和椅子(CHAIR),所有的資源有三種：木料，木工和漆工，生產(chǎn)數(shù)據(jù)如下表所示：每個(gè)DESK每個(gè)TABLE每個(gè)CHAIR現(xiàn)有資源總數(shù)

木料8單位6單位1單位48單位漆工4單位2單位1.5單位20單位木2單1.5單0.5單8單位工位位位利60單30單20單潤位位位若要求桌子的生產(chǎn)量不超過5件，如何安排三種產(chǎn)品的生產(chǎn)可使利潤最大?編寫程序如下：Model:MAX=60*DESKS+30*TABLES+20*CHAIRS;8*DESKS+6*TABLES+CHAIRS<48;4*DESKS+2*TABLES+1.5*CHAIRS<20;2*DESKS+1.5*TABLES+0.5*CHAIRS<8;TABLES<5;END計(jì)算結(jié)果為:Globaloptimalsolutionfound.Objectivevalue:280.0000Infeasibilities:0.000000Totalsolveriterations:2VariableValueReducedCostDESKS2.0000000.000000TABLES0.0000005.000000CHAIRS8.0000000.000000RowSlackorSurplusDualPrice1280.00001.000000224.000000.00000030.00000010.0000040.00000010.0000055.0000000.000000即生產(chǎn)書桌（DESK）2件，桌子（TABLE）0件和椅子（CHAIR）