運籌學(xué)第講線性規(guī)劃

運籌學(xué)第講線性規(guī)劃線性規(guī)劃問題的幾何意義

凸集:設(shè)K是n維歐氏空間的一點集，若任意兩點X(1)∈K，X(2)∈K的連線上的所有點αX(1)+(1-α)X(2)∈K，(0≤α≤1)則稱K為凸集。

注：實心圓，實心球體，實心立方體等都是凸集，圓環(huán)不是凸集。從直觀上講，凸集沒有凹入部分，其內(nèi)部沒有空洞。圖中的(a)(b)是凸集，(c)不是凸集。任何兩個凸集的交集仍為凸集，如圖(d)。第2頁,共52頁，2024年2月25日，星期天線性規(guī)劃問題的幾何意義結(jié)論：任何兩個凸集的交集仍為凸集。

證明：設(shè)A，B為凸集，則因此同理從而所以A與B的交集為凸集。第3頁,共52頁，2024年2月25日，星期天線性規(guī)劃問題的幾何意義

凸組合：設(shè)X(1)，X(2)，…，X(k)是n維歐氏空間En中的k個點，若存在μ1，μ2，…，μk，且0≤μi≤1,i=1,2,…，k，使X=μ1X(1)+μ2X(2)+…+μkX(k)，則稱X為X(1)，X(2)，…，X(k)的凸組合。（當(dāng)0＜μi＜1時，稱為嚴(yán)格凸組合）。

頂點：設(shè)K是凸集，X∈K；若X不能用不同的兩點X(1)∈K和X(2)∈K的線性組合表示為X=αX(1)+(1-α)X(2)，(0＜α＜1)，則稱X為K的一個頂點(或極點)。注

右圖中0,Q1,Q2,Q3,Q4都是頂點。第4頁,共52頁，2024年2月25日，星期天線性規(guī)劃問題的幾何意義關(guān)于線性規(guī)劃問題的幾個定理：定理1：若線性規(guī)劃問題存在可行解，則該問題的可行域是凸集。定理2：線性規(guī)劃問題的基可行解X對應(yīng)可行域(凸集)的頂點。定理3：若問題存在最優(yōu)解，一定存在一個基可行解是最優(yōu)解。（或在某個頂點取得）

以上證明過程見P16-20.第5頁,共52頁，2024年2月25日，星期天

單純形法

盡管若線性規(guī)劃問題有最優(yōu)解，必可以在某頂點上得到，雖然頂點數(shù)目是有限的(它不大于個)，若采用“枚舉法”找所有基可行解，然后一一比較，最終可能找到最優(yōu)解。但當(dāng)n,m的數(shù)較大時，這種辦法是行不通的。（m=20，n=40時，頂點的個數(shù)有個）。

如何有效地找到最優(yōu)解，有多種方法，這里僅介紹單純形法(SimplexMethod)。第6頁,共52頁，2024年2月25日，星期天單純形法

單純形：單純形或者n-單純形是和三角形類似的n維幾何體。精確的講，單純形是某個n維以上的歐幾里得空間中的（n+1）個仿射無關(guān)（也就是沒有m維平面包含m+1個點；這樣的點集被稱為處于一般位置）的點的集合的凸包。0-單純形就是點，1-單純形就是線段，2-單純形就是三角形，3-單純形就是四面體，而4-單純形是一個五胞體（每種情況都包含內(nèi)部）。標(biāo)準(zhǔn)n-單純形：是Rn+1的子集：第7頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本思路：根據(jù)前述定理，如果線性規(guī)劃問題存在最優(yōu)解，則可以在基本可行解中找最優(yōu)解。由于基本可行解的個數(shù)是有限的，所以通過建立一種最優(yōu)性判別準(zhǔn)則，將基本可行解逐一進行檢查，就可以在有限次檢查后得到最優(yōu)解。但是，在有些情況下，要找出所有的基本可行解是非常麻煩的，單純形法的優(yōu)越性就在于不用找出全部的基本可行解。第8頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本思路：在得到一個基本可行解X1后，判斷X1是否是最優(yōu)解，或者判斷此問題沒有最優(yōu)解。如果X1是最優(yōu)解，或者此問題沒有最優(yōu)解，則求解到此為止；若不然，則依據(jù)這個解X1求出下一個基本可行解X2，并且X2要比X1對應(yīng)的目標(biāo)函數(shù)值有所改善。對X2重復(fù)剛才的判斷，直到得到問題的解答為止。X1X2X3第9頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：(1)確定初始基本可行解X1；(2)記Xk為求出的第k個基本可行解，根據(jù)建立的最優(yōu)性準(zhǔn)則，對Xk進行檢驗，若Xk是最優(yōu)解，則計算終止;若不然，則轉(zhuǎn)第(3)步；(3)若根據(jù)建立的無最優(yōu)解準(zhǔn)則判斷此問題沒有最優(yōu)解，則計算終止；若不能判定沒有最優(yōu)解，則轉(zhuǎn)第(4)步；(4)依據(jù)Xk求基本可行解Xk+1，使Z(Xk+1)≥Z(Xk)，令k=k+1，轉(zhuǎn)回第(2)步。第10頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：是否最優(yōu)轉(zhuǎn)移到另一個基本可行解（找出更大的目標(biāo)函數(shù)值）最優(yōu)解是否核心是：變量迭代結(jié)束找出一個初始可行解循環(huán)第11頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：(1)確定初始的基本可行解X1；-假設(shè)在約束系數(shù)矩陣中含有單位陣并且bi≥0，i=1,2,……,m，則令單位陣所在列對應(yīng)的變量為基變量，其他變量為非基變量，并令非基變量取零值，可得到初始基本可行解。-對于所有行約束條件為“≤”不等式，在每行引入松弛變量化為標(biāo)準(zhǔn)形后，所有松弛變量的系數(shù)矩陣正好為單位矩陣。-當(dāng)化為標(biāo)準(zhǔn)形后系數(shù)矩陣中不含有單位陣時，確定初始基本可行解的方法可采用人工變量法。-首先假設(shè)系數(shù)矩陣含單位陣的情況。第12頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：(2)確定最優(yōu)性判別準(zhǔn)則；設(shè)線性規(guī)劃問題(LP)約束系數(shù)矩陣中的前m列為一個單位陣，其模型有如下形式，其中bi

≥0，i=1,2,……,m。目標(biāo)函數(shù)：

maxz=c1x1+c2

x2+…+cnxn

約束條件：

s.t.x1+a1m+1

x

m+1+…+a1n

xn=b1

x2+a2m+1

x

m+1+…+a2n

xn

=b2

(LP)

…………

xm+amm+1

x

m+1+…+amnxn=bm

x1，x2，…，xn≥0.第13頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：(2)確定最優(yōu)性判別準(zhǔn)則；取x1，…，xm為基變量，xm+1，…，xn為非基變量。基本解為X1=（b1，b2，……，bm，0，……，0）T。將上式約束方程組變?yōu)椋?/p>

x1=b1-（a1m+1

x

m+1+…+a1n

xn）

x2=b2-（a2m+1

x

m+1+…+a2n

xn）…………

xm=bm-（amm+1

x

m+1+…+amnxn）代入目標(biāo)函數(shù)中：

Z=c1

x1+c2

x2+…+cnxn第14頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：(2)確定最優(yōu)性判別準(zhǔn)則；記得到目標(biāo)函數(shù)由當(dāng)前解X1的非基變量的線性表示：其中Z1即為X1對應(yīng)的目標(biāo)函數(shù)值。第15頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：(2)確定最優(yōu)性判別準(zhǔn)則；將上面結(jié)果整理后，可得到與原線性規(guī)劃等價的模型定義：稱此等價模型為基本可行解X1對應(yīng)的典式。第16頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：(2)確定最優(yōu)性判別準(zhǔn)則；定理4：設(shè)X1=（b1，b2，……，bm，0，……，0）T為線性規(guī)劃(LP)的基本可行解，如果在其對應(yīng)的典式中則X1為最優(yōu)解。注：此定理就是單純形法中的最優(yōu)性判別準(zhǔn)則。第17頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：(2)確定最優(yōu)性判別準(zhǔn)則；證明：設(shè)為任一可行解,Z0為其目標(biāo)函數(shù)值。將X0代入基本可行解X1對應(yīng)的典式的目標(biāo)函數(shù)中，有由式，則有說明Z1為最大值，X1為最優(yōu)解，定理得證。第18頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：(2)確定最優(yōu)性判別準(zhǔn)則；注：典式中的稱為基本可行解的檢驗數(shù)，確切地說，是X1的非基變量的檢驗數(shù)。為了統(tǒng)一起見，對X1的基變量也規(guī)定檢驗數(shù)，顯然，應(yīng)有(因為典式中不含基變量，實際通過公式計算也為零)，即基變量的檢驗數(shù)為零。第19頁,共52頁，2024年2月25日，星期天單純形法例3.1

為下面線性規(guī)劃問題的一個基本可行解，試判斷其是否為最優(yōu)解。解:將模型化為基本可行解X1對應(yīng)的典式，X1=(6,2,15,0,0)T

可知，x4,x5為非基變量，約束條件已具有典式形式，只需要將目標(biāo)函數(shù)由非基變量x4,x5線性表示即可：

Z=-(6-x4-6x5)+(2+x4-x5)+2(15-6x4-2x5)+2x4+x5=26-8x4+2x5由此可知，其中不滿足最優(yōu)性準(zhǔn)則，因此不能判斷X1為最優(yōu)解。第20頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：(3)確定無最優(yōu)解判別準(zhǔn)則；定理5

設(shè)X1為線性規(guī)劃問題的基本可行解，如果在X1對應(yīng)的典式中存在檢驗數(shù)，并且的約束系數(shù)

皆小于等于零，則該線性規(guī)劃問題的目標(biāo)函數(shù)在可行域上沒有上界，即沒有最優(yōu)解（無界解）。例3.2判斷下面的問題是否沒有最優(yōu)解。第21頁,共52頁，2024年2月25日，星期天單純形法解:取為基本可行解，對于X1此模型已經(jīng)為典式形式。其中檢驗數(shù)，并且皆小于等于零，由定理判斷無最優(yōu)解。怎么理解？？分析：由約束條件可知，對于x3取任何非負(fù)值，此問題都存在可行解，目標(biāo)函數(shù)值為。故而可知當(dāng)M逐漸增大時，Z也相應(yīng)增大，當(dāng)時，

因此Z為最大值，規(guī)劃無最優(yōu)解。第22頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：(4)基本可行解的迭代；定義:根據(jù)已有的基本可行解求新的基本可行解稱為迭代。定義:將原基本可行解X1中的某個非基變量變?yōu)榛兞?，稱為進基變量；將X1的某個基變量變?yōu)榉腔兞浚Q為出基變量。注:迭代的過程實際就是要實現(xiàn)進基變量和出基變量之間的轉(zhuǎn)換。第23頁,共52頁，2024年2月25日，星期天單純形法迭代方法:設(shè)為基變量，并且存在檢驗數(shù)，由X1的典式形式的目標(biāo)函數(shù)的表達式可知其中Z1為X1對應(yīng)的目標(biāo)函數(shù)值。由于，故若選xk為進基變量時(一般基變量的取值大于零)，可使目標(biāo)函數(shù)值進一步增加。因此確定xk為進基變量?；究尚薪釾1的典式形式的約束方程組為在基本可行解中，基變量的個數(shù)是固定的m個,xk進基，則必有一個基變量轉(zhuǎn)換為非基變量。第24頁,共52頁，2024年2月25日，星期天單純形法為了確定出基變量，首先在典式的約束中，令除xm以外的其余非基變量仍取零值，得到:根據(jù)這個關(guān)系式，又考慮到每個決策變量的可行性，從而選取xk，使其滿足如下的關(guān)系式:第25頁,共52頁，2024年2月25日，星期天單純形法當(dāng)時，因為bi非負(fù)，故只需要即可;當(dāng)時，則需。綜合上面兩種情況，因此，應(yīng)使xk滿足注:因為最優(yōu)性判別準(zhǔn)則和無最優(yōu)解判別定理不成立，故可以保證的存在性，以及。按照上面的規(guī)則確定的變量xk，當(dāng)時，使得原第l個基變量的值變?yōu)?即基變量xl

成為出基變量。第26頁,共52頁，2024年2月25日，星期天單純形法可以證明，矩陣仍為可行基，因此得到新的基本可行解，其中各分量的值為:根據(jù)X1的典式的表達式中的目標(biāo)函數(shù)，將X2代入計算得:新解比原解有所改善，增量為至此，完成了基本可行解的迭代。第27頁,共52頁，2024年2月25日，星期天單純形法

定義:一般稱

為最小比值規(guī)則，或稱為規(guī)則，其中的稱為中心元素（主元）?，F(xiàn)將基本可行解的迭代過程歸納如下：設(shè)已得到基本可行解對應(yīng)的典式形式。(1)取對應(yīng)的xk為進基變量。（主要是提高收斂效率，使得每次的增量最大。）(2)按最小比值規(guī)則確定xk的值，并確定出基變量。(3)按右式確定新的基本可行解。第28頁,共52頁，2024年2月25日，星期天單純形法例3.3

根據(jù)基本可行解X1以及典式，迭代求新的基本可行解，并指出目標(biāo)函數(shù)值的增量。其典式為X1的目標(biāo)函數(shù)值為Z1=26解:由于，所以確定x5為進基變量。按最小比值規(guī)則計算出

因此，同時確定xl為出基變量，取零值，另外x4為非基變量仍取零值。第29頁,共52頁，2024年2月25日，星期天單純形法將這些取值代入X2計算公式中，得到新的基本可行解為其目標(biāo)函數(shù)值為目標(biāo)函數(shù)值的增量為。對X2還應(yīng)繼續(xù)判斷其是否是最優(yōu)解。則問題轉(zhuǎn)化為如何確定新的基本可行解X2的檢驗數(shù)。第30頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：(5)新的基本可行解的檢驗數(shù)的確定。不失一般性，考慮下面的線性規(guī)劃模型:假設(shè)已得到的基本可行解不是最優(yōu)解。并假設(shè)經(jīng)過計算，確定x5為進基變量，x1為出基變量，a15為中心元素，得到新的基本可行解,第31頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：(5)新的基本可行解的檢驗數(shù)的確定。為了判斷X2是否最優(yōu)解，需要對約束方程組進行適當(dāng)變換，找出X2對應(yīng)的典式形式。為此，首先要在約束方程組中將新基變量x2,x3,x5顯式表示出來，然后代入目標(biāo)函數(shù)，得到目標(biāo)函數(shù)由新的非基變量的線性表示，從而得到X2對應(yīng)的檢驗數(shù)。這些變換可以經(jīng)過下面的矩陣變換實現(xiàn)，即根據(jù)約束方程組構(gòu)造矩陣式，對其進行初等行變換，變?yōu)榫仃囀降?2頁,共52頁，2024年2月25日，星期天單純形法

單純形法的基本步驟：(5)新的基本可行解的檢驗數(shù)的確定。即：將進基變量x5對應(yīng)的第5列向量化為單位向量，其中將中心元素a15化為1。由上面得到轉(zhuǎn)化后的矩陣式，得到新的基本可行解X2對應(yīng)的典式形式：其中即為新解X2的檢驗數(shù)，根據(jù)他們的正負(fù)，可以判斷X2是否最優(yōu)解。第33頁,共52頁，2024年2月25日，星期天單純形法例3.4

對例3.3中得到的基本可行解X2，判斷其是否是最優(yōu)解。由此可得到在求X2的檢驗數(shù)時用到的矩陣解:是根據(jù)得到的，而X1對應(yīng)的典式為將進基變量x5對應(yīng)的第5列向量化為單位向量，將中心元素a15=6化為1，得到:第34頁,共52頁，2024年2月25日，星期天單純形法由此矩陣可知，的檢驗數(shù)，全部小于等于零，因此X2就是最優(yōu)解。第35頁,共52頁，2024年2月25日，星期天單純形法小結(jié)單純形法的主要步驟：Step1

確定初始的基本可行解X1，求出X1對應(yīng)的典式；Step2

根據(jù)最優(yōu)性準(zhǔn)則判別定理判斷X1是否是最優(yōu)解，若是，算法停止，X1即為最優(yōu)解。否則，根據(jù)無最優(yōu)解判別準(zhǔn)則判斷此線性規(guī)劃是否無最優(yōu)解，若是，算法停止，此規(guī)劃無最優(yōu)解；否則，轉(zhuǎn)Step3；Step3

由確定xk為進基變量，根據(jù)最小比值規(guī)則確定xk的值，確定中心元素和出基變量；Step4

采用初等行變換將中心元素化為1，并將中心元素所在列化為單位列向量確定新的基本可行解X2，以及X2對應(yīng)的檢驗數(shù)，轉(zhuǎn)Step2。第36頁,共52頁，2024年2月25日，星期天單純形法單純形法的求解過程，實際上是在一系列表格上進行的。從這些表格上可以得到基本解、檢驗數(shù)等信息，這些表格稱為單純形表。每一個單純形表相當(dāng)于一個矩陣，每次迭代就是對矩陣進行初等行變換。例3.5

求解下面的線性規(guī)劃問題第37頁,共52頁，2024年2月25日，星期天單純形法解:單純形表的主要步驟1：構(gòu)造初始單純形表；單純形表是根據(jù)線性規(guī)劃問題的基本可行解對應(yīng)的典式形式得到的?，F(xiàn)在取X1=(5,0,0,6,24)T求作為初始基本可行解，顯然，模型中目標(biāo)函數(shù)不是典式形式，因此需要將x4=6-x2+4x3代入目標(biāo)函數(shù)Z，經(jīng)整理得到Z=6+x2+2x3。第38頁,共52頁，2024年2月25日，星期天單純形法構(gòu)造初始單純形表cj02-210CBXBbx1x2x3x4x50x15111000x4601-4100x52402601cj-zj01200CB表示基變量的系數(shù)，XB表示當(dāng)前基變量，b表示當(dāng)前基變量的取值，cj行為基變量的價值系數(shù)，為待填入的按最小比值規(guī)則計算的值。第39頁,共52頁，2024年2月25日，星期天單純形法解:單純形表的主要步驟2：迭代求新的基本可行解及其檢驗數(shù)；在上面的單純形表中，x2,x3檢驗數(shù)大于零，不滿足最優(yōu)性準(zhǔn)則，需要進行迭代。確定中心元素以及進、出基變量，將中心元素化為1，中心元素所在列化為單位向量。cj02-210CBXBbx1x2x3x4x50x151110050x4601-410-0x524026014cj-zj01200第40頁,共52頁，2024年2月25日，星期天單純形法解:單純形表的主要步驟2：迭代求新的基本可行解及其檢驗數(shù)；cj02-210CBXBbx1x2x3x4x50x1112/300-1/63/20x42207/3012/366/7-2x3401/3101/612cj-zj01/320-1/3第41頁,共52頁，2024年2月25日，星期天單純形法解:單純形表的主要步驟3：繼續(xù)迭代；cj02-210CBXBbx1x2x3x4x52x23/23/2100-1/40x437/2-7/20015/4-2x37/2-1/20101/4cj-zj-1/2000-1/4此表格中全部檢驗數(shù)均小于等于零，故得到最優(yōu)解X*=(0,3/2,7/2,37/2,0)T,其對應(yīng)的目標(biāo)函數(shù)值為29/2。最優(yōu)單純形表第42頁,共52頁，2024年2月25日，星期天單純形法例3.5用單純形法求解解:初始基本可行解為X1=(7,0,0,12,0,10)T,所給模型即為典式，可直接建立單純形表進行計算。第43頁,共52頁，2024年2月25日，星期天單純形法cj0-130-20CBXBbx1x2x3x4x5x60x1713-102070x4120-2410030x6100-4308110/3cj-zj00-130-20第44頁,共52頁，2024年2月25日，星期天單純形法cj0-130-20CBXBbx1x2x3x4x5x60x11015/201/4203x330-1/211/4000x610-5/20-3/481cj-zj-901/20-3/4-20第45頁,共52頁，2024年2月25日，星期天單純形法cj0-130-20CBXBbx1x2x3x4x5x6-1x245/2101/104/503x351/5013/102/500x611100-1/2101cj-zj-11-1/500-4/5-12/50由上表得知，最優(yōu)解為X*=(0,4,5,0,0,11)T,最優(yōu)值為11。第46頁,共52頁，2024年2月25日，星期天軟件實現(xiàn)例3.6求解Max2x1+3x2St.4x1+3x2<=103x1+5x2<=12x1≥0x2≥0model:m