【正文】 第二步 在最終表中分別檢查原問題和對(duì)偶問題是否為可行解。（2）bi的變化： 當(dāng)右端常數(shù)從b變化到b+△b時(shí)， （b+△b）180。 而實(shí)際問題中可能發(fā)生變化的還有：增加一種新產(chǎn)品或增加一道新工序等。（2）由對(duì)偶問題的基本性質(zhì)知：當(dāng)對(duì)偶問題有可行解時(shí)，原問題可能有可行解，也可能無可行解。說明：使用對(duì)偶單純形法時(shí)，初始表中檢驗(yàn)數(shù)必須全部為sj163。它是根據(jù)單純形法的原理和對(duì)偶原理設(shè)計(jì)出來的。從而可以利用影子價(jià)格為不同資源進(jìn)行評(píng)級(jí)。由于企業(yè)生產(chǎn)任務(wù)、產(chǎn)品結(jié)構(gòu)、工藝技術(shù)條件等情況發(fā)生變化，影子價(jià)格也將隨之變化，在企業(yè)內(nèi)通常是不穩(wěn)定的。于是互補(bǔ)松弛性可以敘述為，在最優(yōu)解下原問題中的松變量確定對(duì)偶問題中的緊約束，而原問題中的松約束確定對(duì)偶問題中的緊變量。 0 ∴ CB B1 A 179。證明：注意：無界性的逆命題不成立。故所有變量的檢驗(yàn)數(shù)滿足C CB B1A≤0。解：第一步 已知問題不是對(duì)稱形式的問題，先改寫為小目標(biāo)下的對(duì)稱形式，注意第三個(gè)約束是等式，等價(jià)于兩個(gè)不等式5x2+3x3≥30和5x2+3x3≤30，再寫成5x2+3x3≥30和5x23x3≥30，其它變換類似于第一章中標(biāo)準(zhǔn)化方法：第二步 根據(jù)定義寫出對(duì)偶問題：第三步 化簡為所求問題的對(duì)偶問題：觀察到結(jié)果也不是對(duì)稱形式的問題，從中得到任何一個(gè)線性規(guī)劃問題及其對(duì)偶問題互相轉(zhuǎn)化的依據(jù)，如下表22所示：表22原問題（或?qū)ε紗栴}）對(duì)偶問題（或原問題）目標(biāo)函數(shù) max 目標(biāo)函數(shù) min 約束條件m個(gè)m個(gè)變量≤≥0 ≥≤0=無約束變量n個(gè)n個(gè)約束條件≥0 ≥ ≤0≤無約束=約束條件的右端項(xiàng)目標(biāo)函數(shù)的系數(shù)目標(biāo)函數(shù)的系數(shù)約束條件的右端項(xiàng)求任意一個(gè)線性規(guī)劃問題的對(duì)偶問題的原則：若原問題對(duì)稱則對(duì)偶問題對(duì)稱，而原問題不對(duì)稱則對(duì)偶問題不對(duì)稱，且兩個(gè)問題中一個(gè)問題的變量確定另一個(gè)問題的約束條件。也可用矩陣形式表示如下：其中AT,bT,CT分別為A,b,C的轉(zhuǎn)置矩陣，且Y=(y1,y2,...,ym)T.常把原問題中的三要素簡稱為原變量，原目標(biāo)和原約束；而對(duì)偶問題的三要素相應(yīng)稱為對(duì)偶變量，對(duì)偶目標(biāo)和對(duì)偶約束。（1）不吃虧原則，即出租設(shè)備的租金收入不能低于加工兩型產(chǎn)品所獲利潤。 解 為使最終表中的基變量的系數(shù)矩陣構(gòu)成單位矩陣，在下列表中變量x1和x2之間增加了一列x4，初始單純形表和最終單純形表分別為：cj200000CBBbX1X4X2X3X4X50X3122021000X4164100100X515005001σj203000cj20000CBBbX1X4X2X3X4X52X131001/201/50X44010214/53X23001001/5σj000101/5初始表中的基變量是x3,x4,x5,它們?cè)谧罱K表的系數(shù)列P3,P4,P5構(gòu)成矩陣B1，即于是X1的系數(shù)列而這表明對(duì)線性規(guī)劃問題只要給出一個(gè)新的基，可以直接計(jì)算得到新的單純形表，而不需要進(jìn)行逐步迭代。于是最終表中XS的檢驗(yàn)數(shù)σS39。B39。第1節(jié) 單純形法的矩陣描述 在學(xué)習(xí)線性規(guī)劃的對(duì)偶理論之前，先介紹用矩陣形式來描述單純形法，這將使單純形法的原理和步驟更簡潔明了。如何下料，使消耗的鋼材最少？Ⅰ、Ⅱ、Ⅲ三種產(chǎn)品，都分別經(jīng)A、B兩道工序加工。12a+8σjH為50kg. 最大的總利潤收入Z=500元/天.（合理下料問題）現(xiàn)有一批某種型號(hào)的圓鋼長8米。當(dāng)然對(duì)實(shí)際經(jīng)濟(jì)問題能給予深刻準(zhǔn)確的數(shù)學(xué)描述以及把數(shù)學(xué)上的定理算法給予確切合理的經(jīng)濟(jì)解釋，都不是容易的事情。故此題有無窮多最優(yōu)解。當(dāng)發(fā)生退化現(xiàn)象時(shí)，從理論上講有可能出現(xiàn)計(jì)算過程的死循環(huán)，始終求不到最優(yōu)解。為此，不考慮原問題是否存在可行解，給原線性規(guī)劃問題加入人工變量，并構(gòu)造僅含人工變量的目標(biāo)函數(shù)w（通常人工變量在w中的系數(shù)一般取為1）和要求w的最小值，然后用單純型法求解。一旦人工變量取值不為0，則目標(biāo)函數(shù)無法極大化。四、關(guān)于單純形法的補(bǔ)充說明單純形法在實(shí)際應(yīng)用中非常有效，已被廣泛采用，但在理論上不是多項(xiàng)式時(shí)間算法，但這并不影響我們使用該方法解決實(shí)際中的相關(guān)問題。④在大于0的檢驗(yàn)數(shù)中，若某個(gè)sk所對(duì)應(yīng)的系數(shù)列向量Pk′≤0，則此問題是無界解，停止計(jì)算，否則轉(zhuǎn)入下一步。不難看出從表中可以方便的計(jì)算出每個(gè)非基變量的檢驗(yàn)數(shù)，即用變量的價(jià)值減去基價(jià)值與變量的系數(shù)乘積之和，即表15CjC1C2…Cj…Cn比值CBXBbx1x2…xj…xnCB1xB1b1a11a12…a1j…a1nq1CB2xB2b2a21a22…a2j…a2nq2………………………CBnxBnbmam1am2…amj…amnqm檢驗(yàn)數(shù)sjs1s2…sj…sn每一次迭代對(duì)應(yīng)一張單純形表，含初始基可行解的單純形表稱為初始單純形表，含最優(yōu)解的單純形表稱為最終單純形表。因?yàn)閄（0）是基可行解，所以滿足約束方程組：又因?yàn)镻1,P2,…,Pm是一組基向量，非基變量xj ( j≥m+1 )的系數(shù)列向量 Pj 可以用這組基向量線性表示：將上式乘以一個(gè)正數(shù)θ得到：上式與①式相加得：從而找到了滿足約束方程組的另一個(gè)解：只需要取注意：若某個(gè)基變量xi0=0，則允許θ=0 最優(yōu)性檢驗(yàn)和解的判別將基可行解X（0）和X（1）分別代入目標(biāo)函數(shù)中：又q 0，得到如下結(jié)論：(1) 若對(duì)所有j≥m+1，有sj ＜ 0 ，則z（1）＜ z （0） ，即z （0）為最優(yōu)函數(shù)值，X（0）為唯一最優(yōu)解；(2) 若對(duì)所有j ≥m+1 ，有sj ≤0，且存在某個(gè)非基變量的檢驗(yàn)數(shù)sk=0，則將Pk作為新的基向量得出新的基可行解X（1） ，滿足z（1） = z （0） ，故z（1） 也為最優(yōu)函數(shù)值，從而 X（1）也為最優(yōu)解，∴ X（0） 、X（1） 連線上所有點(diǎn)均為最優(yōu)解，因此該線性規(guī)劃模型具有無窮多最優(yōu)解；(3) 若存在某個(gè)sj ＞ 0，但對(duì)應(yīng)的第j列系數(shù)全非正，即aij≤0，則q不受限制，可以任意取值，故當(dāng) q174。若非這種情況，則需要添加人工變量，將在后面討論。 單純形法的要點(diǎn) 確定初始基可行解已知線性規(guī)劃問題形如：注意：約束條件全為≤。 因X(0)不是頂點(diǎn)，所以它可以用D的頂點(diǎn)凸組合表示為：在所有的頂點(diǎn)中必然能找到某一個(gè)頂點(diǎn)X(r),使CX(r)是所有CX(i)中的最大者。0， 則 XX2均為可行解，但 X=+()X2， ∴ X是XX2連線上的點(diǎn)，故X非凸集頂點(diǎn)。0)T X2=(x1 md1，x2 md2，,0)T，為非基可行解，∵ X為可行解，又 X是非基可行解， ∴ P1,P2,證明：（用反證法） 等價(jià)于證明 X非基可行解219。,xk,0,0,0，又 X為XX2連線上一點(diǎn)，即 X=aX1+(1a)X2206。直觀上講：凸集是沒有凹入部分，其內(nèi)部沒有空洞?？尚谢?對(duì)應(yīng)于基可行解的基稱為可行基。39。3. 若某個(gè)約束條件的右端項(xiàng)bi是負(fù)數(shù)，則可將此約束兩邊同時(shí)乘以(1)，從而(bi)成為正數(shù)。對(duì)于不符合標(biāo)準(zhǔn)形式的線性規(guī)劃問題（或稱為非標(biāo)準(zhǔn)形式），都可以分別通過下述方法轉(zhuǎn)化為標(biāo)準(zhǔn)形式。 (3) 若線性規(guī)劃問題有最優(yōu)解，則最優(yōu)解一定可以在可行域的某個(gè)頂點(diǎn)達(dá)到。這種情形的出現(xiàn)往往是由于在建立數(shù)學(xué)模型時(shí)遺漏了某些必要的資源約束條件。即常山機(jī)器廠生產(chǎn)的最佳方案為I、II型產(chǎn)品各生產(chǎn)3件，可獲得最大利潤15元。另外若某個(gè)決策變量xj表示第j種產(chǎn)品本期產(chǎn)量相對(duì)于前期產(chǎn)量的變化量，則xj的取值范圍可以是全體實(shí)數(shù)。有m個(gè)約束條件，第i個(gè)約束條件中變量xj的系數(shù)用aij表示，aij常稱為工藝系數(shù)或技術(shù)系數(shù)。因此例2可以歸結(jié)為如下的數(shù)學(xué)模型 從上面的例子可以看出，所謂規(guī)劃問題，就是求規(guī)劃目標(biāo)在若干限制條件下的極值問題。這兩型產(chǎn)品都分別要在A、B、C三種不同設(shè)備上加工。線性規(guī)劃是運(yùn)籌學(xué)創(chuàng)立初期人們重點(diǎn)研究的內(nèi)容，是生產(chǎn)、科研和企業(yè)管理中一種有效的優(yōu)化技術(shù)，其理論完善，方法簡便，應(yīng)用廣泛，成為規(guī)劃問題乃至運(yùn)籌學(xué)最基本的內(nèi)容。現(xiàn)有四種飼料可供選用，各種飼料每千克營養(yǎng)成分含量及單價(jià)如表12所示：表12 每千克飼料中各營養(yǎng)成分的含量IIIIIIIV需要量蛋白質(zhì)（克）3215700礦物質(zhì)（克）1230維生素（毫克）1100單價(jià)（元/千克）2四種飼料各采購多少，才能使總費(fèi)用最??？解 設(shè)四種飼料分別采購x1,x2,x3,x4千克.根據(jù)該動(dòng)物每天對(duì)蛋白質(zhì)的需求，有 。實(shí)際問題中線性的含義：一是嚴(yán)格的比例性，如生產(chǎn)某產(chǎn)品可獲取的利潤和產(chǎn)品的數(shù)量嚴(yán)格成比例；二是可疊加性，如生產(chǎn)多種產(chǎn)品時(shí)對(duì)某項(xiàng)資源的消耗量應(yīng)等于各產(chǎn)品對(duì)該項(xiàng)資源的消耗量之和。式()也可簡寫為()若各個(gè)約束條件左右兩端的連接符號(hào)都相同（都是“≤”，或都是“=”，或都是“≥”），則可利用向量把線性規(guī)劃問題寫成()在式()中式()還可用矩陣形式表示為 ()式()中A稱為約束條件中變量的系數(shù)矩陣，或簡稱為約束變量的系數(shù)矩陣。目標(biāo)函數(shù)z=2 x1+3 x2表示一族直線，向右上方平移目標(biāo)函數(shù)等值線將使目標(biāo)函數(shù)值增大，依此方向平移到與可行域相切為止。 用圖解法求解下列線性規(guī)劃問題。其原因是模型本身有錯(cuò)誤，出現(xiàn)了矛盾約束。重復(fù)上述過程，直到找到使目標(biāo)函數(shù)值達(dá)到最優(yōu)的頂點(diǎn)為止（如果有的話）。類似的，當(dāng)約束條件為“≥”時(shí)，例如3 x1+8 x2≥24，可令x4=3 x1+8 x224,得3 x1+8x2x4=12,顯然x4≥0。39。基解 在式（）的約束方程組中令所有非基變量xm+1=xm+2=…=xn =0 后，因?yàn)锽是可逆矩陣，根據(jù)克拉默法則，解出m個(gè)基變量的唯一值XB=(x1,x2,...,xm)T，再加上非基變量取0值得到的解 X=(x1,x2,...,xm,0,...,0)T 稱為相應(yīng)于基B的基解(或基本解)。表11列出了本例的全部基和基解，其中共有5個(gè)基可行解，表中用＊標(biāo)注的為最優(yōu)解即X=(3,3,0,4,0)T。C，X2 206。X的正分量所對(duì)應(yīng)的系數(shù)列向量線性獨(dú)立 可設(shè)X=(x1,x2,xm,0,0,xm+ mdm，0， 從而必然會(huì)找到一個(gè)基可行解為最優(yōu)解。第三節(jié) 單純形法1947年，美國學(xué)者George Dantzig（丹茨格）發(fā)明了求解線性規(guī)劃的單純形法（1951年發(fā)表），從而為線性規(guī)劃的推廣奠定了基礎(chǔ)。注意：線性規(guī)劃問題出現(xiàn)無可行解的情形將在后面進(jìn)行討論。③計(jì)算各非基變量xj的檢驗(yàn)數(shù)sj= Cj CBPj，若所有sj≤0，則問題已得到最優(yōu)解，停止計(jì)算，否則轉(zhuǎn)入下一步。.解：先標(biāo)準(zhǔn)化其約束條件的系數(shù)矩陣為A中有3階單位矩陣，選其為基B=(P3,P4,P5)。解：先標(biāo)準(zhǔn)化為但是A中沒有單位矩陣，在A中人為的增加兩列此時(shí)A有單位子矩陣，選擇該單位矩陣作為基，常稱為人工基。在這種情況下，可采用下面的兩階段法進(jìn)行計(jì)算。先修改第一階段的最終表，再繼續(xù)計(jì)算：Cj2302X121023X21011σj001因此該問題有唯一最優(yōu)解：三、關(guān)于退化解的說明 在用單純形法計(jì)算時(shí)，可能出現(xiàn)以下兩種情況： 出現(xiàn)若干正檢驗(yàn)數(shù)大小相同且都是最大。故該問題有無界解。0基變量中有非零的人工變量某非基變量檢驗(yàn)數(shù)為零且有恰當(dāng)?shù)摩葻o可行解無窮多最優(yōu)解某一бj≥0但系數(shù)列aik≤0無界解令бk=max{бj}xk為換入變量，對(duì)所有aik0計(jì)算θ 最小比值對(duì)應(yīng)的變量xl為換出變量，alk為主元素1．xk替換xl2．列出新的單純形表，用矩陣的初等行變換①將主元素化為1②將主元素列的其它系數(shù)化為0第五節(jié) 線性規(guī)劃應(yīng)用舉例學(xué)習(xí)運(yùn)籌學(xué)的目的在于應(yīng)用，而應(yīng)用的第一步就是建立與實(shí)際問題對(duì)應(yīng)的數(shù)學(xué)模型，正如緒論中曾經(jīng)講述的。已知產(chǎn)品的規(guī)格要求、單價(jià)和原材料的供應(yīng)量、單價(jià)。本章的學(xué)習(xí)重點(diǎn)是單純形法的步驟，難點(diǎn)是單純形法的原理及如何就一些簡單的實(shí)際問題建立線性規(guī)劃模型。 ：（1）R1=｛(x1,x2)|x12+2x22≤2｝（2）R2=｛(x1,x2)|x12－2x2+3≥0,x2≥0,|x1|≤1｝（3）R3=｛(x1,x2)|x1x2≥1,x1≥1,x2≥0｝。CBXBbx1x