第1章線性規劃1.1線性規劃問題與模型1.2圖解法1.3普通單純形法1.4大M法和兩階段法1.1線性規劃問題與模型線性規劃((LinearProgramming,LP)是運籌學的重要分支之一，應用非常廣泛。由于線性規劃是學習其他運籌學分支內容的重要基礎，其方法也較為成熟，因此在各類教材中都是最先學習的內容。線性規劃通常研究資源的最優利用、設備最佳運行以及費用最低等問題，一般可以解決兩大類問題:①已知資源求利潤最大化;②已知任務求成本最小化。1.1.1問題舉例(1)生產計劃問題。生產計劃問題是典型的已知資源求利潤最大化的問題，對于此類問題通常有三個假設:①在某一計劃期內對生產做出的安排;②生產過程的損失忽略不計;③市場需求無限制，即假設生產的產品全部賣出。下一頁返回例1用一塊連長為a的正方形鐵皮做一個容器，應如何裁剪，使做成的窗口的容積為最大？要使容積最大，就是要確定X的值，使V達到最大。1.一般線性規劃問題的數學模型例2生產計劃問題產品1產品2資源限量原材料A/kg4016原材料B/kg0412設備/臺128單位產品利潤2元3元練習：某煤油廠每季度需供應給合同單位汽油15萬噸、煤油12萬噸、重油12萬噸.該廠計劃從A，B兩處運回原油提煉，已知兩處的原油成分含量見下表，又已知從A處采購的原油價格（包括運費）為每噸200元，B處采購的原油價格（包括運費）為每噸290元，問：該煉油廠該如何從A,B兩處采購原油，在滿足供應合同的條件下，使購買成本最小？AB汽油15%50%煤油20%30%重油50%15%其他15%5%解：設分別表示從A,B兩處采購的原油量（單位：噸），則所有的采購方案的最優方案為：1.1線性規劃問題與模型1.1.2一般模型(1)模型要素。線性規劃問題的數學模型包括三大要素:①一組決策變量(x1，x2，…xn)，即模型中需要確定的未知量。②一組約束條件，即資源限制條件以及決策變量受到的約束限制，包括兩個部分:不等式組或方程組;決策變量的取值范圍。③一個目標函數，是關于決策變量的最優函數，求max或min。(2)模型的一般形式。假設模型有n個決策變量，m個約束條件，則線性規劃問題模型的一般形式為下一頁返回上一頁1.1線性規劃問題與模型max(min)Z=c1x1+c2x2+…+cnxn下一頁返回上一頁1.1線性規劃問題與模型可簡寫為下一頁返回上一頁1.1線性規劃問題與模型進一步化簡為線性規劃模型也經常寫成矩陣或向量形式:下一頁返回上一頁1.1線性規劃問題與模型其中，X=(x1，x2，…xn)T;C=(c1，c2，…cn)為價值向量,Cj為價值系數;A為技術矩陣，aij為技術系數(或工藝系數)。價值向量b=(x1，x2，…xn)T。A也可寫成A=(P1，P2，…Pn)，其中P1=(a11，a21，…am1)T,P2=(a12，a22，…am2)T,…Pn=(a1n，a2n，…amn)T。下一頁返回上一頁1.1線性規劃問題與模型在實際問題中決策變量的取值范圍通常為非負，但對于模型本身來說，可以是xj≤0。或xj無符號限制(取值無約束)。模型(1-2)之所以是線性規劃問題模型，是因為它具有以下特征:①解決的問題是規劃問題;②目標函數是關于決策變量的線性表達式(求最大值或最小值);③約束條件是關于決策變量的線性不等式或等式。返回上一頁1.2圖解法圖解法就是利用幾何圖形求解兩個變量線性規劃問題的方法，具有簡單、直觀的特點，但只適用于兩個變量的線性規劃((LP)問題，這是圖解法的局限性。圖解法雖然不能解決三個以上變量的線性規劃問題，但通過學習圖解法，可以幫助我們掌握求解線性規劃問題的思路以及線性規劃問題解的類型(可能性)。下一頁返回圖解法步驟：（1）建立坐標系；（2）將約束條件在圖上表示；（3）確立滿足約束條件的解的范圍；（4）繪制出目標函數的圖形（5）確定最優解用圖解法求解下列線性規劃問題圖1一1返回圖1一2返回圖1-3返回1.2圖解法1.2.2線性規劃解的特性學習圖解法的主要目的之一就是掌握線性規劃問題解的特性，主要包括以下三點:①線性規劃問題若有可行域，則可行域必是一個凸多邊形，對應于凸集(集合內部任意兩點連線上的點都屬于這個集合)。例如，在圖1-4中，只有圖(a)可以用來表示凸集。凸集的數學定義:設K為n維歐氏空間的一個點集，若K中任意兩個點X1和X2連線上的所有點都屬于K，即“X=αX1+(1-α)X2

∈K(0≤a≤1)”，則稱K為凸集。設X(x1，x2，…，xn)，X1(u1，u2，...，un)，X2(v1，v2，…，vn)，如圖1一5所示，“X=αX1+(1-α)X2

∈K(0≤a≤1)”的證明思路如下:下一頁返回上一頁1.2圖解法(vi-xi)=α(vi-ui)＝＞xi=αui+(1-α)vi＝＞X=αX1+(1-α)X2(i=1，2，…，n)②凸多邊形(可行域)的頂點是有限的，每個頂點對應的解為基本可行解。③對于某一線性規劃問題，如果有最優解，則最優解一定在可行域的某個頂點獲得。下一頁返回上一頁1.2圖解法為此，可以得到線性規劃問題求解的思路:找出并比較凸多邊形(可行域)的頂點，目標函數值最大(或最小)的頂點對應于最優解。可見，在求解線性規劃問題的時候只需要考慮凸多邊形的頂點，并比較這些頂點對應的目標函數值，就能獲得最優解。1.2.3線性規劃解的可能性線性規劃問題解的可能性有四種，即唯一最優解(如圖1-3所示)、無窮多最優解(又稱多重最優解)、無界解和無可行解，如圖1-6、圖1-7、圖1-8和圖1-9。下一頁返回上一頁1.2圖解法圖解法的解題思路和幾何上的直觀表示，對求解線性規劃問題具有重要啟示:①線性規劃問題的解有唯一最優解、無窮多最優解、無界解和無可行解四種情況。②線性規劃問題的可行域一般為無界或有界凸多邊形(無可行解除外)。③若線性規劃問題的最優解存在，即有唯一最優解或無窮多最優解，則必在可行域的某個頂點上獲得。④若可行域中有兩個點對應于最優解，則該兩點連線上的任意一點都對應于最優解。返回上一頁1.3普通單純形法1.3.1線性規劃模型的標準形式在使用單純形法求解時，第一步就是尋找基本可行解，前提是先將原模型標準化。(1)標準型的表達方式。線性規劃模型的標準形式定義為下一頁返回1.3普通單純形法也可以寫成模型(1-6)和模型(1-7)的形式，其中模型(1-7)較為常用。線性規劃模型的標準形式有如下特征:①目標函數求最大值，即maxZ。下一頁返回上一頁1.3普通單純形法②資源限量非負，即b≥0。③決策變量非負，表示所有決策變量取值均大于或等于零，即X≥0。④約束條件為等式，即AX=b。(2)一般形式與標準形式的轉換方法。①“決策變量非負”。若某決策變量xk為“取值無約束”(無符號限制)，令xk=x′k-x″k(x′k≥0，x″k≥0)；若xk≤0，令xk=-x′k，則x′k≥0②“目標函數求最大值”。對于極小化原問題minZ=CX，則令Z′=-Z，原問題則轉為求maxZ′=-CX，即當Z′達到最大值時，Z達到最小值，求解后應注意還原，即Z=-Z′。下一頁返回上一頁1.3普通單純形法③“約束條件為等式”。對于“≤”型約束，則在“≤”左端加上一個非負松弛變量(SlackVariable)，使其變為等式。對于“≥”型約束，則在“≥”左端減去一個非負剩余變量(SurplusVariable)，使其變為等式。。④“資源限量非負”。若某個bi＜0，則將該約束兩端同乘“-1”，以滿足非負性的要求。1.3.2幾個重要概念(1)基。下一頁返回上一頁1.3普通單純形法假設線性規劃問題模型的系數矩陣為m行n列，則系數矩陣中秩為m的m行和m列子矩陣稱為基矩陣，簡稱為基，一般用B來表示。已知線性規劃標準化模型(1-8)的系數矩陣A為2行4列，見矩陣(1-9)，其中2行2列的子矩陣有6(C21)個，如表1一9所示。容易判斷，B4中兩個行(或列)向量線性相關，即對應元素成比例，其余子矩陣均為滿秩矩陣，因此該線性規劃模型存在5個基:B1

，B2，B3，B5和B6。下一頁返回上一頁1.3普通單純形法(2)基變量和非基變量。基中的列向量對應的變量稱為基變量，決策變量中除基變量以外的變量稱為非基變量。如B1中的兩個列向量分別對應于決策變量x1和x2，則x1和x2為基變量，x3和x4為非基變量，其他情況見表1-9。(3)基本解。對于某一確定的基，令所有非基變量為0，通過約束方程組AX=b可解出m個基變量的唯一解，稱之為基本解。基矩陣B1，B2，B3，B5和B6。對應的基本解如表1-10所示。下一頁返回上一頁1.3普通單純形法(4)基本可行解。變量取值滿足非負條件的基本解稱為基本可行解，基本可行解對應于凸多邊形(凸集)的頂點。如表1-10所示，X1，X2，X5和X6。為基本可行解，分別對應于該問題可行域(凸多邊形)的四個頂點。1.3.3求解步驟(1)普通單純形法求解思路。掌握了上述概念以后，根據圖解法帶來的啟示，可以確定線性規劃問題的解題思路，如圖1一10所示。下一頁返回上一頁1.3普通單純形法首先，確定一個初始基可行解，即找到一個初始可行基；想辦法判斷這個基可行解是不是最優解，如果是最優解，就得到這個線性規劃問題的最優解;如果判斷出這個可行解不是最優解，就將這個可行基按一定規則變化到下一個可行基，然后再判斷新得到的基可行解是不是最優解；如果還不是，再接著進行下一個可行基變化，直至找到最優解。(2)單純形法原理。對于公式(1-7)，可令A=(P1，P2，…，Pm，Pm+1，…，Pn)，其中P1，P2，…，Pm為基變量對應的列向量;Pm+1，Pm+2，…，Pn

為非基變量對應的列向量，因此，A可寫成A=(B,N)，相應地，X=(XB，XN)T，C=(CB，CN)。下一頁返回上一頁1.3普通單純形法對于約束條件AX=(B,N)(XB，XN)T=BXB+NXN=b，在等式兩端左乘B-1，有XB+B-1NXN=B-1b，即XB=B-1b-B-1NXN。若令XN=0,XB=B-1b。對于目標函數Z=CX=(CB，CN)(XB，XN)T=CBXB+CNXN，將“B-1b-B-1NXN”代人后，有Z=CB(B-1b-B-1NXN)+CNXN=CBB-1b+(CN一CBB-1N)XN，令XN=0,Z=CBB-1b。其中“CN-CBB-1N”為非基變量檢驗數，通常用“σN=CN-CBB-1N”表示。對于某一非基變量的檢驗數，也可表示為“σj=cj-Zj。同理，基變量檢驗數為“σB=CB-CBB-1B”，因此基變量的檢驗數為零。所有檢驗數可表示為“σ=C-CBB-1A”。上述推導過程可用表1一11和表1一12表示(其中，E為單位矩陣，即B-1B=E)，稱為單純形表。下一頁返回上一頁1.3普通單純形法(3)單純形法求解步驟。①求出初始基本可行解。先將模型標準化，找到單位基，令非基變量為零，確定初始基本可行解。②最優性檢驗。利用公式“σn=CN-CBB-1N”求出非基變量檢驗數，若所有非基變量檢驗數小于或等于零，說明已得到最優解，否則進人步驟③。③換基和迭代。(a)確定入基變量σk=max{σj|σj>0}(入基變量確定法則)；下一頁返回上一頁1.3普通單純形法(b)確定出基變量θl=min{bi/aik|aik＞0}(出基變量確定法則或最小比值法則);(c)確定主元素，考查入基變量對應的列向量和出基變量對應的行向量，交叉元素即為“主元素”；(d)先將主元素變為“1”，再利用初等變換方法求出新的基本可行解。④重復步驟②和③，直到求出最優解。(4)退化解與Bland法則。一般稱基變量取值為零的解為退化解。在確定出基變量時，有時存在兩個以上相同的最小比值，這樣在下一次迭代中就有一個或幾個基變量等于零，這就出現了退化解，當出現退化時，進行多次迭代，而基從B1,B2,…又返回到B1，計算過程陷人循環，無法得到最優解。下一頁返回上一頁1.3普通單純形法Bland法則:①在確定入基變量時，若存在兩個或兩個以上的最大檢驗數(大于零)，選擇下標號最小的變量入基。②在確定出基變量時，若存在兩個或兩個以上的最小比值，同樣選擇比值對應下標號小的變量出基。1.3.4最優解判定定理判定定理1:在單純形表中，若所有非基變量的檢驗數小于零，且B-1b均為非負，則線性規劃問題具有唯一最優解。見表1-17或表1-18，非基變量x3和x5的檢驗數(-1/8和-3/2)均小于零，則線性規劃問題只有一個最優解，通常稱作“唯一最優解”。下一頁返回上一頁1.3普通單純形法判別定理2:在單純形表中，若所有非基變量的檢驗數小于或等于零，且B-1b均為非負，其中某個檢驗數等于零，則線性規劃問題具有無窮多個最優解(多重最優解)。判定定理