【正文】 都是x1=0，x2=14，x3=17但他們最優(yōu)解的目標(biāo)函數(shù)值卻相差一個符號，即 max z＝141 min z’=141 約束條件不是等式的問題設(shè)約束條件為 引進(jìn)一個新的變量xn+i，使它等于約束右邊與左邊之差 顯然xn+I也具有非負(fù)約束，即xn+i≥0，這時新的約束條件成為 當(dāng)約束條件為 時，類似地令 則同樣有xn+i≥0，新的約束條件成為 為了使約束由不等式成為等式而引進(jìn)的變量xn+i稱為“松弛變量(Slack Variable)”。如果原問題中有若干個非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時，必須對各個約束引進(jìn)不同的松弛變量。 將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式maxz=3x12x2+x3.x1+2x2x3≤5(1)4x1+3x3≥8(2)x1+x2+x3=6(3)x1,x2,x3≥0將目標(biāo)函數(shù)轉(zhuǎn)換成極小化，并分別對約束（1）、（2）引進(jìn)松弛變量x4，x5，得到以下標(biāo)準(zhǔn)形式的線性規(guī)劃問題minz’=3x1+2x2x3.x1+2x2x3+x4=54x1+3x3x5=8x1+x2+x3=6x1,x2,x3,x4,x5≥0 變量無符號限制的問題在標(biāo)準(zhǔn)形式中，每一個變量都有非負(fù)約束。當(dāng)一個變量xj沒有非負(fù)約束時，可以令 xj=xj’xj”其中 xj’≥0，xj”≥0即用兩個非負(fù)變量之差來表示一個無符號限制的變量，當(dāng)xj的符號取決于xj’和xj”的大小。 將以下線性規(guī)劃問題轉(zhuǎn)化為標(biāo)準(zhǔn)形式maxz=2x13x2+x3.x1x2+2x3≤32x1+3x2x3≥5x1+x2+x3=4 x1,x3≥0, x2無符號限制令z’=z，引進(jìn)松弛變量x4，x5≥0，并令 x2=x239。x239。39。其中x239?！?，x239。39?！?得到以下等價的標(biāo)準(zhǔn)形式minz’=2x1+3x239。3x239。39。x3.x1x239。+x239。39。+2x3+x4=32x1+3x239。3x239。39。x3x5=5x1+x239。x239。39。+x3=4x1,x239。,x239。39。,x3,x4,x5≥0 變量小于等于零的問題在一些實(shí)際問題中，變量不允許為正數(shù)，這樣的問題也不是標(biāo)準(zhǔn)問題。例如：minz=3x15x2+x3.2x1+4x2+x3≤15x13x2+2x3≥ 6x1≥0x2≤0x3≥0令x2=x39。2，x39。2≥0，原問題成為：minz=3x1+5x39。2+x3.2x14x39。2+x3≤15x1+3x39。2+2x3≥ 6x1≥0x39。2≥0x3≥0然后引進(jìn)松弛變量x4，x5，成為標(biāo)準(zhǔn)問題：minz=3x1+5x39。2+x3.2x14x39。2+x3+x4=15x1+3x39。2+2x3x5= 6x1x39。2x3x4x5≥0這樣，我們就能夠?qū)⑷魏畏菢?biāo)準(zhǔn)形式的線性規(guī)劃問題轉(zhuǎn)化為等價的標(biāo)準(zhǔn)形式問題。167。 線性規(guī)劃問題的幾何解釋對于只有兩個變量的線性規(guī)劃問題，可以在二維直角坐標(biāo)平面上表示線性規(guī)劃問題。maxz=x1+3x2.x1+x2≤6(1)x1+2x2≤8(2)x1,x2≥0其中滿足約束(1)的點(diǎn)位于坐標(biāo)平面上直線x1+x2=6靠近原點(diǎn)的一側(cè)。同樣，滿足約束(2)的點(diǎn)位于坐標(biāo)平面上直線 x1+2x2=8的靠近原點(diǎn)的一側(cè)。而變量x1，x2的非負(fù)約束表明滿足約束條件的點(diǎn)同時應(yīng)位于第一象限內(nèi)。這樣，以上幾個區(qū)域的交集就是滿足以上所有約束條件的點(diǎn)的全體。我們稱滿足線性規(guī)劃問題所有約束條件（包括變量非負(fù)約束）的向量 X=(x1，x2，…，xn)T為線性規(guī)劃的可行解（Feasible Solution），稱可行解的集合為可行域（Feasible Region）。圖 z=0z=3z=6z=9z=12z=0 1 2 3 4 5 68 7 6 5 4 3 2 1654321x1x2。為了在圖上表示目標(biāo)函數(shù)，令z=z0為某一確定的目標(biāo)函數(shù)值，取一組不同的z0值，在圖上得到一組相應(yīng)的平行線，稱為目標(biāo)函數(shù)等值線。在同一條等值線上的點(diǎn)，相應(yīng)的可行解的目標(biāo)函數(shù)值相等。，給出了z=0，z=3，z=6，…，z=，對于目標(biāo)函數(shù)極大化問題，這一組目標(biāo)函數(shù)等值線沿目標(biāo)函數(shù)增大而平行移動的方向（即目標(biāo)函數(shù)梯度方向）就是目標(biāo)函數(shù)的系數(shù)向量C=(c1,c2,…,…,)T；對于極小化問題，目標(biāo)函數(shù)則沿C方向平行移動。在以上問題中，目標(biāo)函數(shù)等值線在平行移動過程中與可行域的最后一個交點(diǎn)是B點(diǎn)，這就是線性規(guī)劃問題的最優(yōu)解，這個最優(yōu)解可以由兩直線 x1+ x2=6 x1+2x2=8的交點(diǎn)求得 最優(yōu)解的目標(biāo)函數(shù)值為 為了將以上概念推廣到一般情況，我們給出以下定義： 在n維空間中，滿足條件 ai1x1+ai2x2+…+ainxn=bi的點(diǎn)集 X=(x1，x2，…，xn)T稱為一個超平面。 滿足條件 ai1x1+ai2x2+…+ainxn≤（或≥）bi的點(diǎn)集 X=(x1，x2，…，xn)T稱為n維空間中的一個半空間。 有限個半空間的交集，即同時滿足以下條件的非空點(diǎn)集 a11x1+a12x2+…+a1nxn≤（或≥）b1 a21x1+a22x2+…+a2nxn≤（或≥）b2 ……… am1x1+am2x2+…+amnxn≤（或≥）bm稱為n維空間中的一個多面體。運(yùn)用矩陣記號，n維空間中的多面體也可記為 AX≤（或≥）b每一個變量非負(fù)約束xi≥0（i=1，2，…，n）也都是半空間，其相應(yīng)的超平面就是相應(yīng)的坐標(biāo)平面xi=0。，我們看到，線性規(guī)劃問題的可行域是一個凸多邊形。容易想象，在一般的n維空間中，n個變量，m個約束的線性規(guī)劃問題的可行域也應(yīng)具備這一性質(zhì)。為此我們引進(jìn)如下的定義。 設(shè)S是n維空間中的一個點(diǎn)集。若對任意n維向量X1206。S，X2206。S，且X1185。X2，以及任意實(shí)數(shù)l（0163。l163。1），有 X=lX1+(1l)X2206。S則稱S為n維空間中的一個凸集（Convex Set）。點(diǎn)X稱為點(diǎn)X1和X2的凸組合。以上定義有明顯的幾何意義，它表示凸集S中的任意兩個不相同的點(diǎn)連線上的點(diǎn)（包括這兩個端點(diǎn)），都位于凸集S之中。x1x2x2x1x1x2x1x2x1x2x1x2 (a)凸集 (b)凸集 (c)凸集 (d)非凸集 (e)非凸集 (f)非凸集，線性規(guī)劃如果有最優(yōu)解，其最優(yōu)解必定位于可行域邊界的某些點(diǎn)上。在平面多邊形中，這些點(diǎn)就是多邊形的頂點(diǎn)。在n維空間中，我們稱這樣的點(diǎn)為極點(diǎn)（Extreme Point）。在凸集中，不能表為不同點(diǎn)的凸組合的點(diǎn)稱為凸集的極點(diǎn)。 設(shè)S為一凸集，且X206。S，X1206。S，X2206。S。對于0l1，若 X=lX1+(1l)X2則必定有X=X1=X2，則稱X為S的一個極點(diǎn)。運(yùn)用以上的定義，線性規(guī)劃的可行域以及最優(yōu)解有以下性質(zhì)：若線性規(guī)劃的可行域非空，則可行域必定為一凸集。若線性規(guī)劃有最優(yōu)解，則最優(yōu)解至少位于一個極點(diǎn)上。這樣，求線性規(guī)劃最優(yōu)解的問題，從在可行域內(nèi)無限個可行解中搜索的問題轉(zhuǎn)化為在其可行域的有限個極點(diǎn)上搜索的問題。最后，來討論線性規(guī)劃的可行域和最優(yōu)解的幾種可能的情況?？尚杏?yàn)榉忾]的有界區(qū)域 (a)有唯一的最優(yōu)解； (b)有一個以上的最優(yōu)解；可行域?yàn)榉欠忾]的無界區(qū)域 (a)有唯一的最優(yōu)解； (b)有一個以上的最優(yōu)解； (c)目標(biāo)函數(shù)無界（即雖有可行解，但在可行域中，目標(biāo)函數(shù)可以無限增大或無限減?。?，因而沒有最優(yōu)解?？尚杏?yàn)榭占?，因而沒有可行解。以上幾種情況的圖示如下：(a)可行域封閉，唯一最優(yōu)解 (b)可行域封閉，多個最優(yōu)解 (c)可行域開放，唯一最優(yōu)解(d)可行域開放，多個最優(yōu)解 (e)可行域開放，目標(biāo)函數(shù)無界 (f) 可行域?yàn)榭占?67。 線性規(guī)劃的基、基礎(chǔ)可行解由于圖解法無法解決三個變量以上的線性規(guī)劃問題，我們必須用代數(shù)方法來求得可行域的極點(diǎn)。先從以下的例子來看。maxz=x1+2x2.x1+x2≤3(1)x2≤1(2)x1,x2≥0。引進(jìn)松弛變量x3，x4179。0，問題變成為標(biāo)準(zhǔn)形式maxz=x1+2x2.x1+x2+x3=3(1)x2+x4=1(2)x1x2x3x4179。0圖 OABCDx1x23210123x3=0x4=0x1=0x2=0由上圖可以看出，直線AD對應(yīng)于約束條件(1)，位于AD左下側(cè)半平面上的點(diǎn)滿足約束條件x1+x23，即該半平面上的點(diǎn)，滿足x30。直線AD右上側(cè)半平面上的點(diǎn)滿足約束條件x1+x23，即該半平面上的點(diǎn)，滿足x30，而直線AD上的點(diǎn)，相應(yīng)的x3=0。同樣，直線BC上的點(diǎn)滿足x4=0，BC以下半平面中的點(diǎn)，滿足x40。BC以上半平面中的點(diǎn)，滿足x40。另外，OA上的點(diǎn)滿足x2=0，OD上的點(diǎn)滿足x1=0。由此可見，上圖中約束直線的交點(diǎn)O，A，B，C和D可以由以下方法得到：在標(biāo)準(zhǔn)化的等式約束中，令其中某兩個變量為零，得到其他變量的唯一解，這個解就是相應(yīng)交點(diǎn)的坐標(biāo)，如果某一交點(diǎn)的坐標(biāo)（x1，x2，x3，x4）全為非負(fù)，則該交點(diǎn)就對應(yīng)于線性規(guī)劃可行域的一個極點(diǎn)（如點(diǎn)A，B，C和O）；如果某一交點(diǎn)的坐標(biāo)中至少有一個分量為負(fù)值（如點(diǎn)D），則該交點(diǎn)不是可行域的極點(diǎn)。，O點(diǎn)對應(yīng)于x1=0，x2=0，在等式約束中令x1=0，x2=0，得到x3=3，x4=1。即O點(diǎn)對應(yīng)于極點(diǎn)X=(x1，x2，x3，x4)T=(0，0，3，1)T。由于所有分量都為非負(fù)，因此O點(diǎn)是一可行域的極點(diǎn)。同樣，A點(diǎn)對應(yīng)于x2=0，x3=0，x1=3，x4=1；B點(diǎn)對應(yīng)于x3=0，x4=0，x1=2，x2=1；C點(diǎn)對應(yīng)于x1=0，x4=0，x2=1，x3=2。以上都是極點(diǎn)。而D點(diǎn)對應(yīng)于x1=0，x3=0，x2=3，x4=2，x4的值小于0，因而不是極點(diǎn)。同時，我們也注意到，如在等式約束中令x2=0，x4=0，由于線性方程組的系數(shù)行列式等于0，因而xx3無解。，這是由于對應(yīng)的直線x2=0和x4=0平行，沒有交點(diǎn)的緣故。對于一般的問題，獲得線性規(guī)劃可行域極點(diǎn)的方法可描述如下：設(shè)線性規(guī)劃的約束條件為 其中系數(shù)矩陣為mn的矩陣，設(shè)nm，并假設(shè)系數(shù)矩陣的秩為m，即系數(shù)矩陣的m個行向量是線性無關(guān)的。在約束等式中，令X=(x1，x2，…，xn)T中nm個變量為零，如果剩下的m個變量在線性方程組中的系數(shù)矩陣是非奇異的，這m個變量有唯一解。這n個變量的值組成的向量X就對應(yīng)于n維空間中若干個超平面的一個交點(diǎn)。當(dāng)這n個變量的值都是非負(fù)時，這個交點(diǎn)就是線性規(guī)劃可行域的一個極點(diǎn)。根據(jù)以上分析，得到以下定義： 線性規(guī)劃的基、基變量、非基變量標(biāo)準(zhǔn)化的線性規(guī)劃問題的約束系數(shù)為mn階矩陣，mn，矩陣的秩為m。矩陣中的一個非奇異的mm子矩陣稱為線性規(guī)劃的一個基。與基矩陣對應(yīng)的變量稱為基變量，其余的變量稱為非基變量。 線性規(guī)劃問題的基礎(chǔ)解、基礎(chǔ)可行解和可行基對于線性規(guī)劃的一個基（mm階矩陣），n個變量劃分為m個基變量、nm個非基變量。令nm個非基變量全等于0，m個基變量有唯一解。這樣得到的n個變量的一個解成為基礎(chǔ)解。如果基礎(chǔ)解中所有的變量都是非負(fù)的，這個解稱為基礎(chǔ)可行解。如果一個基對應(yīng)的基礎(chǔ)解是可行解，這個基稱為可行基。根據(jù)以上的分析，我們不加證明地給出以下定理： 線性規(guī)劃的基礎(chǔ)可行解就是可行域的極點(diǎn)。這個定理是線性規(guī)劃的基本定理，它的重要性在于把可行域的極點(diǎn)這一幾何概念與基礎(chǔ)可行解這一代數(shù)概念聯(lián)系起來，因而可以通