云南農(nóng)業(yè)大學(xué)經(jīng)管學(xué)院《運籌學(xué)》第一章課件

運籌學(xué)

OperationsResearch

0第1章線性規(guī)劃1.1

數(shù)學(xué)模型MathematicalModelofLP1.2

圖解法GraphicalMethod1.5

單純形法

SimplexMethod1.3

線性規(guī)劃的標(biāo)準(zhǔn)型StandardformofLP1.4

線性規(guī)劃的基本概念

BasicConcepts1第1章線性規(guī)劃創(chuàng)始人

線性規(guī)劃(LinearProgramming，縮寫LP）是運籌學(xué)的一個重要分支，產(chǎn)生于上世紀(jì)30年代末。許多人把線性規(guī)劃的發(fā)現(xiàn)列為20世紀(jì)中期最重要的科學(xué)成就之一。解決有限資源的最佳分配問題。

前蘇聯(lián)經(jīng)濟學(xué)家康脫諾維奇（LeonidVitaliyevichKantorovich）

1.1數(shù)學(xué)模型2第1章線性規(guī)劃線性規(guī)劃研究的問題有兩類已知一定量的人力、物力資源，研究如何合理地使用這些資源，才能使完成的任務(wù)量最大；已確定了任務(wù)量，研究如何合理安排生產(chǎn)，才能使完成此項任務(wù)所消耗的資源量最少。1.1數(shù)學(xué)模型3第1章線性規(guī)劃

產(chǎn)品資源

甲

乙現(xiàn)有資源(kg)材料A(kg)2140材料B(kg)11.530利潤（元/件）300400【例1-1】生產(chǎn)計劃問題。1.1

數(shù)學(xué)模型1.1.1

應(yīng)用模型舉例表1-14第1章線性規(guī)劃【解】設(shè)生產(chǎn)甲、乙產(chǎn)品的產(chǎn)量分別為x1、x2件，數(shù)學(xué)模型為1.1.1

應(yīng)用模型舉例約束條件目標(biāo)函數(shù)s.t.決策變量5第1章線性規(guī)劃怎樣辨別一個模型是線性規(guī)劃模型線性規(guī)劃數(shù)學(xué)模型的三要素：決策變量目標(biāo)函數(shù)約束條件

1．解決問題的目標(biāo)函數(shù)是多個決策變量的線性

函數(shù)，通常是求最大值或最小值；2．解決問題的約束條件是一組多個決策變量的

線性不等式或等式。1.1.1應(yīng)用模型舉例6第1章線性規(guī)劃

【例1-2】表1-2營業(yè)員需要量統(tǒng)計表星期需要人數(shù)星期需要人數(shù)一300五480二300六600三350日550四4001.1.1應(yīng)用模型舉例7第1章線性規(guī)劃【解】

設(shè)xj

(j=1，2，…，7)為休息2天后星期一到星期日開始上班的營業(yè)員人數(shù)，則這個問題的線性規(guī)劃模型為

1.1.1應(yīng)用模型舉例1234567x1√√√√√x2√√√√√x3√√√√√x4√√√√√x5√√√√√x6√√√√√x7√√√√√8第1章線性規(guī)劃1X10C1404>=3001042X267C2301>=30013X3146C3350>=35004X4170C4400>=40005X597C5480>=48006X6120C6600>=60007X717C7550>=5500最優(yōu)解：Z＝617（人）1.1.1應(yīng)用模型舉例9第1章線性規(guī)劃【例1-3】下料問題

【解】一根圓鋼切割成甲、乙、丙三種軸共有10種不同的切割方式，也就是有10種下料方案，如表1-3所示。表1-3下料方案

方案規(guī)格12345678910需求量甲(1.5m)22111000001000乙(1m)10210432101000丙(0.7m)01023012451000余料(m)00.30.50.10.400.30.60.20.51.1.1應(yīng)用模型舉例10第1章線性規(guī)劃

設(shè)xj（j=1,2…,10）為第j種下料方案所用圓鋼的根數(shù)。則用料最少的數(shù)學(xué)模型為:

方案規(guī)格12345678910需求量甲(1.5m)22111000001000乙(1m)10210432101000丙(0.7m)01023012451000余料(m)00.30.50.10.400.30.60.20.51.1.1應(yīng)用模型舉例說明

求下料方案時應(yīng)注意，余料不能超過最短毛坯的長度；最好將毛坯長度按降序排列，即先切割長度最長的毛坯，再切割次長的，最后切割最短的，不能遺漏了方案。如果方案較多，用計算機編排方案，去掉余料較長的方案，進(jìn)行初選。11第1章線性規(guī)劃1X15002X203X304X405X506X662.57X708X809X925010X100Z＝812.51.1.1應(yīng)用模型舉例12第1章線性規(guī)劃【例1-4】配料問題表1-4礦石的金屬含量

合金礦石錫%鋅%鉛%鎳%雜質(zhì)%費用(元/t)1251010253034024000303026030155206018042020040202305851517551901.1.1

應(yīng)用模型舉例13第1章線性規(guī)劃【解】:

設(shè)xj（j=1,2，…，5）為生產(chǎn)1噸合金所用第j種礦石的數(shù)量，得到下列線性規(guī)劃模型

錫%鋅%鉛%鎳%雜質(zhì)%費用（元/t）125101025303402400030302603015520601804202004020230585151755190金屬總含量%7070408045141X102X20.33333X304X40.58335X50.6667最優(yōu)解：Z=347.51.1.1應(yīng)用模型舉例15第1章線性規(guī)劃【例1-5】投資問題。表1－5證券投資方案1.1.1

應(yīng)用模型舉例序號

證券類型評級到期年限

每年稅后收益率(%)1

國債1183.22

國債21103.83

地方債券1244.34

地方債券2364.75

基金1434.26

基金2544.616第1章線性規(guī)劃【解】

設(shè)xj(j=1,2,…，6)為第j

種證券的投資額，目標(biāo)函數(shù)是稅后總收益資金約束：國債投資額約束：平均評級約束：平均到期年限約束：17整理后得到線性規(guī)劃模型1.1.1應(yīng)用模型舉例18第1章線性規(guī)劃【另解】設(shè)xj

(j=1,2,…，6)為第j種證券占投資總額的比例，目標(biāo)函數(shù)是稅后總收益（%）1.1.1應(yīng)用模型舉例19第1章線性規(guī)劃1.1.1應(yīng)用模型舉例LPOPTIMUMFOUNDATSTEP4OBJECTIVEFUNCTIONVALUE1)20.28000（總收益Z=20.28/100*5000=1014)VARIABLEVALUEREDUCEDCOSTX10.050000(250)0.000000X20.150000(750)0.000000X30.700000(3500)0.000000X40.0000002.199999X50.100000(500)0.000000X60.0000001.200000ROWSLACKORSURPLUSDUALPRICES2)0.000000-9.2000003)0.000000-15.6000004)0.0000000.8000005)0.0000006.20000020第1章線性規(guī)劃【補充例】運輸問題

有A1、A2、A3三家工廠生產(chǎn)同一種產(chǎn)品，日產(chǎn)量分別是6、4、12萬噸；有B1、B2、B3、B4四個門市部，其日銷量分別為6、2、7、7萬噸。每個工廠到各門市部的單位運費（萬元/萬噸）如下表。問如何組織調(diào)運可使總運費最少？

（單位：萬元/萬噸）

銷地產(chǎn)地B1B2B3B4日產(chǎn)量A148846A295634A33114212日銷量6277221.1.1應(yīng)用模型舉例21第1章線性規(guī)劃

【解】

設(shè)從Ai到Bj的運輸量為xij（i=1,2,3;j=1,2,3,4）萬噸minZ=4x11+8x12+8x13+4x14+9x21+5x22+6x23+3x24+3x31+11x32+4x33+2x34

銷地產(chǎn)地B1B2B3B4日產(chǎn)量A1x11

x12x13x146A2x21x22x23x244A3x31x32x33x3412日銷量6277221.1.1應(yīng)用模型舉例

銷地產(chǎn)地B1B2B3B4日產(chǎn)量A148846A295634A33114212日銷量62772222第1章線性規(guī)劃1.1.2

線性規(guī)劃的一般模型線性規(guī)劃模型的一般形式cj——價值系數(shù)（利益系數(shù)）aij——消耗系數(shù)（工藝系數(shù)）bi——資源限量23第1章線性規(guī)劃什么是線性規(guī)劃，掌握線性規(guī)劃在管理中的幾個應(yīng)用例子。2.線性規(guī)劃數(shù)學(xué)模型的組成及其特征。3.線性規(guī)劃數(shù)學(xué)模型的一般表達(dá)式。下一節(jié)圖解法1.1數(shù)學(xué)模型本節(jié)學(xué)習(xí)要點24第1章線性規(guī)劃1.2圖解法

圖解法即是用圖示的方法來求解線性規(guī)劃問題。一個二維的線性規(guī)劃問題，可以在平面圖上求解，三維的線性規(guī)劃則要在立體圖上求解，這就比較麻煩，而維數(shù)再高就不能圖示了。25第1章線性規(guī)劃圖解法的步驟：1.求可行解集合。分別求出滿足每個約束包括變量非負(fù)要求的區(qū)域，其交集就是可行解集合，或稱為可行域。

2.繪制目標(biāo)函數(shù)圖形。先過原點作一條矢量指向點（c1,c2)，矢量的方向就是目標(biāo)函數(shù)增加的方向，稱為梯度方向，再作一條與矢量垂直的直線，這條直線就是目標(biāo)函數(shù)等值線；3.求最優(yōu)解。依據(jù)目標(biāo)函數(shù)求最大或最小移動目標(biāo)函數(shù)等值線，等值線與可行域邊界相交的點對應(yīng)的坐標(biāo)就是最優(yōu)解。

一般地，將目標(biāo)函數(shù)等值線放在可行域中,求最大值時等值線沿著梯度方向移動,求最小值時等值線沿著梯度方向的反方向移動。1.2圖解法26第1章線性規(guī)劃x1x2O1020304010203040(300,400)最優(yōu)解x1=15,x2=10X=(15,10)最優(yōu)值Z=8500【例1-7】1.2圖解法(15,10)可行域27第1章線性規(guī)劃x1x2O1020304010203040(-300,400)1.2圖解法最優(yōu)解X=(0,20)最優(yōu)值Z=8000【補充】將例1-7模型改為28第1章線性規(guī)劃B246x1x2246最優(yōu)解X=(3,1)最優(yōu)值Z=5【例1-8】(1,2)1.2圖解法A可行域是無界區(qū)域(3,1)29第1章線性規(guī)劃246x1x2246(1,2)無界解(無最優(yōu)解)【例1-10】1.1圖解法30第1章線性規(guī)劃246x1x2246(5,5)【例1-9】有無窮多個最優(yōu)解，通解為:最優(yōu)值Z=201.2圖解法ABBX(1)=(1,3)X(2)＝(3,1)其中X(1)=(1,3),X(2)=(3,1)31第1章線性規(guī)劃x1x2O10203040102030405050可行域為Φ，無可行解，故無最優(yōu)解【例1-11】1.1圖解法32第1章線性規(guī)劃由以上例題可知，線性規(guī)劃的解有3種情況：1.有唯一最優(yōu)解（例1-7例1-8）2.有多重解（例1-9）1.2圖解法3.無解33第1章線性規(guī)劃1.通過圖解法了解線性規(guī)劃有幾種解的情況。2.

作圖的關(guān)鍵有三點

(1)可行解區(qū)域要畫正確

(2)梯度方向（目標(biāo)函數(shù)增加的方向）不能畫錯

(3)目標(biāo)函數(shù)的等值線怎樣平行移動1.2圖解法下一節(jié)：線性規(guī)劃的標(biāo)準(zhǔn)型本節(jié)學(xué)習(xí)要點34第1章線性規(guī)劃1.3線性規(guī)劃的標(biāo)準(zhǔn)型特征：

1．目標(biāo)函數(shù)求最大值

2．約束條件都為等式

3．變量xj非負(fù)

4．常數(shù)bi非負(fù)35第1章線性規(guī)劃縮寫形式1.3線性規(guī)劃的標(biāo)準(zhǔn)型36第1章線性規(guī)劃一般情況m≤n，且r(Ａ)＝m。1.3線性規(guī)劃的標(biāo)準(zhǔn)型矩陣形式37第1章線性規(guī)劃1.3

線性規(guī)劃的標(biāo)準(zhǔn)型非標(biāo)準(zhǔn)型向標(biāo)準(zhǔn)型轉(zhuǎn)化

目標(biāo)函數(shù)為極小化問題

minZ=CX，只需將等式兩端乘以-1即變?yōu)闃O大化問題。因為minZ=-max(-Z)=CX，令Z′=-Z，則maxZ′=-CX約束右端常數(shù)項非正兩端同乘以-1約束條件為不等式當(dāng)約束條件為“≤”時，不等式左端加入一個非負(fù)的松弛變量，就把不等式變成了等式；當(dāng)約束條件為“≥”時，不等式左端減去一個非負(fù)的剩余變量(也可稱松弛變量)即可。

決策變量xk沒有非負(fù)性要求令xk=xk′-xk〃，xk′，xk〃

≥0，用xk′，xk〃取代模型中xk38第1章線性規(guī)劃1.3線性規(guī)劃的標(biāo)準(zhǔn)型

【補充】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型

松弛變量的經(jīng)濟意義：

x3,x4

分別表示A、B兩種材料的剩余量化標(biāo)39第1章線性規(guī)劃【例1-12】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型

【解】令1.3線性規(guī)劃的標(biāo)準(zhǔn)型40第1章線性規(guī)劃

當(dāng)某個變量xj≤0時,令x/j=－xj,x/j≥0

當(dāng)某個約束是絕對值不等式時，將絕對值不等式化為兩個不等式，再化為等式，例如將其化為兩個不等式

1.3線性規(guī)劃的標(biāo)準(zhǔn)型41第1章線性規(guī)劃

1.如何化標(biāo)準(zhǔn)形式？

2.用WinQSB軟件求解，或用圖解法時不必化成標(biāo)準(zhǔn)型。

3.用單純形法求解時一定要化為標(biāo)準(zhǔn)型。1.3線性規(guī)劃的標(biāo)準(zhǔn)型下一節(jié)：線性規(guī)劃的基本概念本節(jié)學(xué)習(xí)要點42第1章線性規(guī)劃

設(shè)線性規(guī)劃的標(biāo)準(zhǔn)型

式中A是m×n矩陣，m≤n，并且r(A)=m，則A中至少有一個m×m子矩陣B，使得r(B)=m,即|B|≠0。1.4線性規(guī)劃的基本概念基：若B是矩陣A中m階可逆矩陣，則稱B是LP的一個基。

當(dāng)m=n時，基矩陣唯一，當(dāng)m<n時，基矩陣就可能有多個，但數(shù)目不超過

43第1章線性規(guī)劃

基向量、非基向量：組成基矩陣的m個列向量稱為基向量，其余的n-m個向量稱為非基向量。

基變量、非基變量：基向量對應(yīng)的變量稱為基變量，其余的變量稱為非基變量。

1.4

線性規(guī)劃的基本概念

設(shè)基B=(P1,P2,…，Pm)，N=(Pm+1，…，Pn）

變量XB=(x1,x2,…,xm)T

為基變量，其余變量XN=(xm+1,…,xn)T為非基變量?；蛄?4第1章線性規(guī)劃可行解(feasiblesolution)：滿足所有約束條件的解X=(x1,x2…，xn)T稱為可行解。

（對于標(biāo)準(zhǔn)型，應(yīng)滿足AX=b，X≥0）。最優(yōu)解(optimalsolution)：使得目標(biāo)函數(shù)達(dá)到最大值或最小值的可行解稱為最優(yōu)解。

（對于標(biāo)準(zhǔn)型，應(yīng)使目標(biāo)函數(shù)達(dá)到最大）

。1.4

線性規(guī)劃的基本概念45第1章線性規(guī)劃

基本解(basissolution)：對某一確定的基B，令非基變量等于零，利用式（1.2）解出基變量，則這組解稱為基B的基本解。基本可行解(basisfeasiblesolution)：若基本解是可行解則稱為是基本可行解。基本可行解對應(yīng)的基稱為可行基?；咀顑?yōu)解：使目標(biāo)函數(shù)達(dá)到最大的基本可行解稱為基本最優(yōu)解?；咀顑?yōu)解對應(yīng)的基稱為最優(yōu)基。無界解(unboundsolution)：有可行解，但目標(biāo)函數(shù)無上界或無下界。1.4

線性規(guī)劃的基本概念46第1章線性規(guī)劃例如右圖中線段Q1Q2上的點為最優(yōu)解時，Q1點及Q2點是基本最優(yōu)解,線段Q1Q2的內(nèi)點是最優(yōu)解而不是基本最優(yōu)解。

1.4

線性規(guī)劃的基本概念說明：

可行解不一定是基本可行解。當(dāng)最優(yōu)解唯一時，最優(yōu)解亦是基本最優(yōu)解，當(dāng)最優(yōu)解不唯一時，則最優(yōu)解不一定是基本最優(yōu)解。47第1章線性規(guī)劃【補充】已知線性規(guī)劃

求所有的基、基本解，并指出哪些是基本可行解。

約束方程的系數(shù)矩陣為容易看出r(A)=2，2階子矩陣共有C42=6個，且都是可逆矩陣，即基矩陣有6個化標(biāo)【解】48基基向量基變量非基變量對應(yīng)的基本解(P1,P2)(x1,x2)(x3,x4)X(1)=(15,10,0,0)T(P1,P3)(x1,x3)(x2,x4)X(2)=(30,0,-20,0)T(P1,P4)(x1,x4)(x2,x3)X(3)=(20,0,0,10)T(P2,P3)(x2,x3)(x1,x4)X(4)=(0,20,20,0)T(P2,P4)(x2,x4)(x1,x3)X(5)=(0,40,0,-30)T(P3,P4)(x3,x4)(x1,x2)X(6)=(0,0,30,40)T49X(1),X(3),X(4),X(6)是基本可行解問題：1.哪些是基本最優(yōu)解呢？2.X=(10,10,10,5)T是可行解嗎？是基本可行解嗎？

1.4線性規(guī)劃的基本概念50第1章線性規(guī)劃EFG51

基本解是各約束方程及坐標(biāo)軸兩兩間的交點。即A、G、E、C、F、O共6個點。

基本可行解是可行域的頂點。即點O、C、A、E。

最優(yōu)解是可行域的一個頂點坐標(biāo)。即點A。E(20,0)FG52

基本解、可行解、基本可行解、基本最優(yōu)解、最優(yōu)解的關(guān)系如左圖所示：

例如,B點和D點是可行解,不是基本解;C點是基本可行解;A點是基本最優(yōu)解,同時也是最優(yōu)解、基本可行解、基本解和可行解。E(20,0)FG基本解可行解基本可行解最優(yōu)解基本最優(yōu)解53【例1-14】已知線性規(guī)劃

求所有基矩陣、基本解，并指出哪些是基本可行解?！窘狻考s束方程的系數(shù)矩陣為2×5矩陣容易看出r(A)=2，2階子矩陣共有C52=10個，其中第1列與第3列構(gòu)成的2階矩陣不是基，因此基矩陣只有9個，即541.4

線性規(guī)劃的基本概念基向量基變量非基變量對應(yīng)的基本解(P1,P2)(x1,x2)(x3,x4,x5)X(1)=(2/5,1,0,0,0)T(P1,P4)(x1,x4)(x2,x3,x5)X(2)=(-1/5,0,0,4,0)T(P1,P5)(x1,x5)(x2,x3,x4)X(3)=(3/5,0,0,0,8)T(P2,P3)(x2,x3)(x1,x4,x5)X(4)=(0,1,-2,0,0)T(P2,P4)(x2,x4)(x1,x3,x5)X(5)=(0,1/3,0,8/3,0)T55第1章線性規(guī)劃1.4

線性規(guī)劃的基本概念基向量基變量非基變量對應(yīng)的基本解(P2,P5)(x2,x5)(x1,x3,x4)X(6)=(0,3,0,0,-16)(P3,P4)(x3,x4)(x1,x2,x5)X(8)=(0,0,1,4,0)(P3,P5)(x3,x5)(x1,x2,x4)X(7)=(0,0,-3,0,8)(P4,P5)(x4,x5)(x1,x2,x3)X(9)=(0,0,0,3,2)56第1章線性規(guī)劃X(1),X(3),X(5),X(8),X(9)是基本可行解問題：哪些是基本最優(yōu)解呢？

1.4線性規(guī)劃的基本概念57第1章線性規(guī)劃凸集(Convexset)：設(shè)K是n維空間的一個點集，對任意兩點

時，則稱K為凸集。凸組合(Convexcombination)：設(shè)是Rn中的點，若存在，使得成立，則稱X為的凸組合。1.4

線性規(guī)劃的基本概念58第1章線性規(guī)劃X是凸集K的極點即X不可能是K中某一線段的內(nèi)點，只能是K中某一線段的端點。

右圖中，點O、Q1、Q2、Q3、Q4是凸五邊形OQ1Q2Q3Q4的頂點，即極點。O1.4

線性規(guī)劃的基本概念極點(Extremepoint)

：設(shè)K是凸集，，若X不能用K中兩個不同的點的凸組合表示為則稱X是K的一個極點（或頂點）。

59第1章線性規(guī)劃【定理1.1】若線性規(guī)劃可行解集K非空，則K是凸集?！径ɡ?.2】線性規(guī)劃的可行解集合K的點X是極點的充要條件為X是基本可行解。線性規(guī)劃的基本定理

1.4

線性規(guī)劃的基本概念

定理1.2刻劃了可行解集的極點與基本可行解的對應(yīng)關(guān)系，極點是基本可行解，反之，基本可行解在極點上。一般它們是一一對應(yīng)的。（但有可能兩個或幾個基本可行解對應(yīng)于同一極點。出現(xiàn)退化基本可行解時）

60第1章線性規(guī)劃【定理1.3】若線性規(guī)劃有最優(yōu)解,則最優(yōu)解一定可以在可行解集合的某個極點上得到。

1.4

線性規(guī)劃的基本概念

定理1.3描述了最優(yōu)解在可行解集中的位置，若最優(yōu)解唯一，則最優(yōu)解只能在某一極點上達(dá)到，若具有多重最優(yōu)解，則最優(yōu)解是某些極點的凸組合（即可行域的邊界：線段或射線），從而最優(yōu)解是可行解集的極點或界點，不可能是可行解集的內(nèi)點。61第1章線性規(guī)劃

重要結(jié)論若線性規(guī)劃的可行解集非空且有界，則一定有最優(yōu)解。若可行解集無界，則線性規(guī)劃可能有最優(yōu)解，也可能沒有最優(yōu)解。若線性規(guī)劃具有無界解，則可行域一定無界。1.4

線性規(guī)劃的基本概念

定理1.2及1.3還給了我們一個啟示，尋求最優(yōu)解不是在無限個可行解中去找，而是在有限個基本可行解中去尋求。下一節(jié)將介紹一種有效地尋找最優(yōu)解的方法——單純形法。定理1.3還給出了圖解法的另一種方法：窮舉法62第1章線性規(guī)劃1、線性規(guī)劃常用的概念：可行解、基本解、基本可行解、最優(yōu)解、基本最優(yōu)解、基、可行基、最優(yōu)基、凸集、極點（頂點）、凸組合2.線性規(guī)劃的三個基本定理。下一節(jié)：單純形法1.4

線性規(guī)劃的基本概念本節(jié)學(xué)習(xí)要點63第1章線性規(guī)劃

單純形方法的基本思路：先求出一個初始基可行解并判斷它是否最優(yōu)，若不是最優(yōu)，再換一個基可行解并判斷，直到得出最優(yōu)解或無最優(yōu)解。它是一種逐步逼近最優(yōu)解的迭代方法。1.5

單純形法

1.5.1普通單純形法

通常，當(dāng)系數(shù)矩陣A中可以觀察得到一個可行基時（一般是一個單位矩陣或m個線性無關(guān)的單位向量組成的矩陣），可以通過解線性方程組求得基本可行解。

單純形法(SimplexMethod)是美國人丹捷格.Dantzig)1947年創(chuàng)建的。這種方法簡捷、規(guī)范，易于在計算機上實現(xiàn)，是舉世公認(rèn)的解決線性規(guī)劃問題行之有效的方法。64第1章線性規(guī)劃【例1-15】用單純形法求例1-1的最優(yōu)解【解】加入松馳變量x3、x4，化為標(biāo)準(zhǔn)型B1是一個初始基,x3、x4為基變量，x1、x2為非基變量，令x1=0、x2=0，得到初始基本可行解X(1)=(0,0,40,30)T

1.5.1普通單純形法

65第1章線性規(guī)劃X(1)=(0,0,40,30)T是否為最優(yōu)解，可以從目標(biāo)函數(shù)

Z=300x1+400x2中的系數(shù)看出檢驗數(shù)：

目標(biāo)函數(shù)用非基變量表示，其變量的系數(shù)稱為檢驗數(shù)。記作λj（j=1,2,…,n）本例中λ1=300,λ2=400,λ3=0,λ4=0。最優(yōu)解判斷標(biāo)準(zhǔn)：當(dāng)所有檢驗數(shù)λj≤0（j=1，…，n)時，基本可行解為最優(yōu)解。1.5.1普通單純形法

當(dāng)目標(biāo)函數(shù)中有基變量xi時，利用約束條件將目標(biāo)函數(shù)中的xi消去即可求出檢驗數(shù)。66第1章線性規(guī)劃1.5.1普通單純形法

線性規(guī)劃的典則形式：（1）約束條件系數(shù)矩陣存在m個不相關(guān)的單位列向量；（2）目標(biāo)函數(shù)中不含基變量。以x3、x4為基變量的典式以x3、x2為基變量的典式67第1章線性規(guī)劃(a)XBx1x2x3x4bx3211040x413/20130λj30040000

(b)λj

(c)

λj

進(jìn)基列出基行bi/ai2，ai2>0θi基變量120002/302/3204/31-2/340100/30-800/330103/4-1/21501-1/211000-25-250將3/2化為12015最優(yōu)解X(3)=(15,10,0,0)T最優(yōu)值Z=8500檢驗數(shù)0-8500-8000-Zx3x2x1x268最優(yōu)解X=(15,10,0,0)T最優(yōu)值Z=8500X(1)=(0,0)x1x2O1020304010203040X(2)=(0,20)X(3)=(15,10)單純形法的幾何意義69單純形法的計算步驟：1.將模型化為標(biāo)準(zhǔn)形式。求初始基本可行解：將模型化成典式列出初始單純形表。2.判斷：

（a）若λj≤０（j＝１，２，…，n）得到最優(yōu)解；（b）若某個λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃無解（無界解）。（c）若存在λk>0，且這些正檢驗數(shù)所對應(yīng)的列中都有正分量，則要進(jìn)行換基迭代。1.5.1普通單純形法

70第1章線性規(guī)劃第Ｌ個比值最小，選最小比值對應(yīng)行（稱為主行）的基變量為出基變量，若有相同最小比值，則任選一個。主行與主列交叉處的元素aLk為主元素。

（c）求新的基可行解：用初等行變換將主列化為單位列向量，主元素aLk為１,其它元素為零（包括檢驗數(shù)），得到新的基本可行解。

4.重復(fù)2、3，直到得出最優(yōu)解，或判斷無最優(yōu)解。（b）選出基變量。求最小比值：3.換基迭代：（a）選進(jìn)基變量設(shè)λk=max｛λj|λj>0｝,xk為進(jìn)基變量，第k列為主列。1.5.1普通單純形法

71第1章線性規(guī)劃【例1-16】用單純形法求解【解】將數(shù)學(xué)模型化為標(biāo)準(zhǔn)形式：

以x4、x5可作為初始基變量1.5.1普通單純形法

72第1章線性規(guī)劃Cj12100bθCBXBx1x2x3x4x50x42-3210150x51/350120λj12100

0x42x2λj

1x1

2x2

λj

表1－71/3150120301713751/30-90-22025601017/31/31250128/9-1/92/335/300-98/9-1/9-7/3最優(yōu)解X=(25，35/3，0，0，0)T，最優(yōu)值Z=145/3173【例1-17】用單純形法求解

【解】這是一個極小化的線性規(guī)劃問題,應(yīng)將其化為極大化問題求解。以x3、x4、x5為基變量。由第二個約束得到x4=6+x1-x2，代入目標(biāo)函數(shù)消去x41.5.1普通單純形法

也可以直接求解,這時最優(yōu)判斷標(biāo)準(zhǔn)是：

λj≥0(j=1，…，n)

時得到最優(yōu)解74第1章線性規(guī)劃

最優(yōu)解為X=(0,5,0,1,11)T

最優(yōu)值Z=2x1-2x2-x4=-2×5-1=-111.5.1普通單純形法

表1-8XBx1x2x3x4x5bθx3x4x51-161121000100015→6215621/2λj-11↑000

x2x4x51-241001-1-20100015111

λj-20-100

也可以直接求解,這時最優(yōu)判斷標(biāo)準(zhǔn)是：

λj≥0(j=1，…，n)

時得到最優(yōu)解75第1章線性規(guī)劃【例1-18】求解線性規(guī)劃【解】化為標(biāo)準(zhǔn)型1.5.1普通單純形法

76第1章線性規(guī)劃初始單純形表為XBx1x2x3x4bx3x432－2－1100114λj－1100

λ2=1>0,x2進(jìn)基，而a12<0，a22<0，從而線性規(guī)劃無最優(yōu)解（無界解）。1.5.1普通單純形法77第1章線性規(guī)劃【例1-19】求解線性規(guī)劃【解】化為標(biāo)準(zhǔn)型后用單純形法計算如下表所示1.5.1普通單純形法78第1章線性規(guī)劃14—10/3XBx1x2x3x4x5bθ(1)x3x4x5－111[2]2－11000100014→10225—λj24↑000(2)x2x4x5－1/2[2]1/21001/2－11/201000126→4—38λj4↑0－200(3)x2x1x50101001/4－1/23/41/41/2－1/40017/235/2λj000－20(4)x2x1x30101000011/31/3－1/3－1/32/34/38/314/310/3λj000－20該線性規(guī)劃問題有多重最優(yōu)解，通解為：79用單純形法求解時解的判斷唯一最優(yōu)解的判斷：最優(yōu)表中所有非基變量的檢驗數(shù)為負(fù),則線性規(guī)劃具有唯一最優(yōu)解。多重最優(yōu)解的判斷:

最優(yōu)表中存在非基變量的檢驗數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解。無界解的判斷:

某個λk>0且aik≤０（i=1，2,…,m）則線性規(guī)劃具有無界解。退化基本可行解的判斷:

存在某個基變量為零的基本可行解。1.5.1普通單純形法80第1章線性規(guī)劃

在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初始可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加入的變量稱為人工變量，構(gòu)成的可行基稱為人造基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。1.5.2大M和兩階段單純形法【引例】81第1章線性規(guī)劃1.大M單純形法

對于標(biāo)準(zhǔn)形式的LP問題，引入人工變量得到輔助問題人工變量最終必須等于0才能保持原問題性質(zhì)不變。為保證人工變量為0，在目標(biāo)函數(shù)中令其系數(shù)為-M，M為無限大的正數(shù)，這是一個懲罰項，倘若人工變量不為零，則目標(biāo)函數(shù)就永遠(yuǎn)達(dá)不到最優(yōu)。如若在最終表中人工變量仍沒有迭代出去，那么這個問題就沒有可行解，當(dāng)然亦無最優(yōu)解。1.5.2大M和兩階段單純形法82第1章線性規(guī)劃【例1-20】用大M法解下列線性規(guī)劃【解】化為標(biāo)準(zhǔn)形式引入人工變量y1，y2,得到輔助問題化標(biāo)83

利用公式計算，如初始表中的檢驗數(shù)有三種算法：利用第一、三約束將y1,y2的表達(dá)式代入目標(biāo)函數(shù)消去y1和y2

，得到用非基變量表達(dá)的目標(biāo)函數(shù)，其系數(shù)就是檢驗數(shù)；1.5.2大M和兩階段單純形法

用初等行變換將目標(biāo)函數(shù)中基變量的系數(shù)化為零，便得到檢驗數(shù)。84第1章線性規(guī)劃Cj32－100－M－MbCBXBx1x2x3x4x5y1y2－M

0－My1x5y2－4123－1－212[1]－1000101000014101→λj3-2M2+M-1+2M↑－M000－M0－1y1x5x3－6－32[5]3－2001－1000101003→81λj5-6M5M↑0－M0020－1x2x5x3－6/5[3/5]－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑000023－1x2x1x301010000111025/32/31331/319/3λj000－5-25/3最優(yōu)解X＝（31/3，13，19/3，0，0)T最優(yōu)值Z＝152/385【例1-21】求解線性規(guī)劃

【解】

加入松馳變量x3、x4化為標(biāo)準(zhǔn)型。在第二個方程中加入人工變量y，得到輔助問題1.5.2大M和兩階段單純形法

化標(biāo)86第1章線性規(guī)劃Cj5－800MbCBXBx1x2x3x4y0Mx3y[3]11－2100－1016→4λj5－M↑－8+2M0M0

5Mx1y101/3－7/31/3－1/30－10122λj0－29/3+7/3M－5/3+1/3MM0

表中λj≥0，j=1，2，…，5，從而得到輔助問題的最優(yōu)解X=(2,0,0,0,2)T,Z=10+2M。但最優(yōu)解中含有人工變量y≠0說明這個解是偽最優(yōu)解，是不可行的，因此原問題無可行解。87

兩階段單純形法與大M單純形法的目的類似，將人工變量從基變量中換出，以求出原問題的初始基本可行解。將問題分成兩個階段求解，第一階段的目標(biāo)函數(shù)是約束條件是加入人工變量后的約束方程。當(dāng)?shù)谝浑A段的最優(yōu)解中沒有人工變量作基變量時，得到原線性規(guī)劃的一個基本可行解。第二階段就以此為基礎(chǔ)對原目標(biāo)函數(shù)求最優(yōu)解。

當(dāng)?shù)谝浑A段的最優(yōu)解w≠0時，說明還有不為零的人工變量是基變量，則原問題無可行解。2.兩階段單純形法1.5.2大M和兩階段單純形法88第1章線性規(guī)劃【例1-22】用兩階段單純形法求解例19的線性規(guī)劃。【解】化為標(biāo)準(zhǔn)型，在第一、三約束方程中加入人工變量y1、

y2后，第一階段問題為用單純形法求解，得到第一階段問題的計算表如下：1.5.2大M和兩階段單純形法89第1章線性規(guī)劃Cj0000011bCBXBx1x2x3x4x5y1y2101y1x5y2－4123－1－212[1]－1000101000014101→λj2－1－2↑1000

100y1x5x3－6－32[5]3－2001－100010100

3→81λj6－5↑0100

000x2x5x3－6/53/5－2/5100001－1/53/5－2/5010

3/531/511/5λj00000

1.5.2大M和兩階段單純形法90第1章線性規(guī)劃最優(yōu)解為，最優(yōu)值w=0

第一階段最后一張最優(yōu)表說明找到了原問題的一組基可行解，將它作為初始基可行解，求原問題的最優(yōu)解，即第二階段問題為1.5.2大M和兩階段單純形法91第1章線性規(guī)劃Cj32-100bCBXBx1x2x3x4x5

2

0

－1

x2

x5

x3

1

0

0

0

0

1

0

1

0λj5↑0000

2

3

－1x2

x1

x30

1

01

0

0

0

0

11

1

0213λj000－5

Cj32－100bCBXBx1x2x3x4x520－1x2x5x3－6/5[3/5]－2/5100001－1/53/5－2/50103/531/5→11/5λj5↑0000

23－1x2x1x301010000111025/32/31331/319/3λj000－5－25/3

用單純形法計算得到下表最優(yōu)解X＝（31/3，13，19/3，0，0)T最優(yōu)值Z＝152/31.5.2大M和兩階段單純形法92第1章線性規(guī)劃【例1-23】用兩階段法求解例1-21的線性規(guī)劃?！窘狻康谝浑A段問題為用單純形法計算如下表：1.5.2大M和兩階段單純形法93第1章線性規(guī)劃Cj00001bCBXBx1x2x3x4x501x3x5[3]11－2100－1016→4λj

－1↑2010

01x1x5101/3－7/31/3－1/30－10122λj

07/31/310

λj≥0,得到第一階段的最優(yōu)解X=(2,0,0,0,2)T,最優(yōu)目標(biāo)值w=2≠0,x5仍在基變量中,從而原問題無可行解。1.5.2大M和兩階段單純形法94第1章線性規(guī)劃若r(A)=m設(shè)基B=(P1,P2,…，Pm),則N=(Pm+1,Pm+2,…，Pn)A=(B,N)C=(c1,c2,…cm,cm+1,…，cn)=(CB,CN)1.5.3單純形法計算公式95第1章線性規(guī)劃

XB+B-1NXN=B-1b(2)

XB=B-1b-B-1NXN

令非基變量XN=0，則XB=B-1b

若B-1b≥0，則是基本可行解，B是可行基1.5.3單純形法計算公式

相應(yīng)的目標(biāo)函數(shù)值

目標(biāo)函數(shù)Z=CX

化為96第1章線性規(guī)劃約束條件AX=b

化為1.5.3單純形法計算公式典則形式的矩陣形式XBXNbXBEB-1NB-1bλOCN-CBB-1N-CBB-1b97第1章線性規(guī)劃五個計算公式：

(令XN=0)

1.5.3單純形法計算公式基變量的值約束方程組中的非基向量非基變量的檢驗數(shù)全體檢驗數(shù)目標(biāo)函數(shù)值98第1章線性規(guī)劃cjc1

c2

…cn

b比值

CB

XB

x1

x2

…xn

a11a12…a1nb1θ1

a21a22…a2nb2θ2

┇┇┇┇┇am1am2…amnbmθm

檢驗數(shù)λj

λ1

λ2

…λn

單純形表T(B)基變量的值XbXBAbC0AbC1.5.3單純形法計算公式┇┇99第1章線性規(guī)劃XBXNbXBEB-1NB-1bCBCN0XBXNbXBBNbCBCN0表1－16表1－171.5.3單純形法計算公式表1－18XBXNbXBEB-1NB-1bλOCN-CBB-1N-CBB-1b100第1章線性規(guī)劃1.5.3單純形法計算公式XbXBB-1AB-1bλC-CBB-1A-CBB-1b單純形表的矩陣形式XBXNbXBEB-1NB-1bλOCN-CBB-1N-CBB-1b101第1章線性規(guī)劃【例1-24】已知線性規(guī)劃，用公式計算有關(guān)結(jié)果已知可行基

求：（1）單純形乘子π;

（2）基可行解及目標(biāo)值;

（3）求λ3;

（4）B1是否是最優(yōu)基,為什么;（5）當(dāng)可行基為時求λ1及λ3。1.5.3單純形法計算公式102第1章線性規(guī)劃【解】(1)因為B1由A中第一列、第二列組成,故x1、x2為基變量，x3、x4、x5為非基變量,有關(guān)矩陣為CB=(c1,c2)=(1,2)CN=(c3,c4,c5)=(1,0,0)故單純形乘子1.5.3單純形法計算公式103第1章線性規(guī)劃(2)基變量的值為故基本可行解為目標(biāo)函數(shù)值為1.5.3單純形法計算公式104第1章線性規(guī)劃(3)求λ31.5.3單純形法計算公式105第1章線性規(guī)劃(4)要判斷B1是不是最優(yōu)基，就要求出所有檢驗數(shù)，看是否滿足λj≤0，j=1…,5。x1,x2是基變量,故λ1=0,λ2=0,而剩下來求λ4,λ5，由λN計算公式得λ4=-1/9,

λ5=-7/3因λj≤0,j=1,…,5,故B1是最優(yōu)基。1.5.3單純形法計算公式106第1章線性規(guī)劃(5)因B2是A中第四列與第二列組成的,x4、x2是基變量,x1、x3、x5是非基變量,這時有即1.5.3單純形法計算公式107第1章線性規(guī)劃

退化解

基本可行解中存在基變量等于零，這種現(xiàn)象稱為退化，此時的解稱為退化解。退化的原因：LP可行域上的極點一般是由n個n-1維超平面相交而成，若通過某個極點的超平面超過n個，該點即為一個退化極點。

循環(huán)當(dāng)存在