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