運(yùn)籌學(xué)之線性規(guī)劃課件

第一章線性規(guī)劃基本性質(zhì)本章主要內(nèi)容線性規(guī)劃一般模型線性規(guī)劃的圖解法(重點(diǎn)）線性規(guī)劃的標(biāo)準(zhǔn)形式(重點(diǎn)）線性規(guī)劃解的主要概念（難點(diǎn)）線性規(guī)劃應(yīng)用——建模線性規(guī)劃（Linearprogramming----LP)解決稀缺資源最優(yōu)分配的有效方法研究對(duì)象在一定的人力、財(cái)力、資源條件下，如何合理安排，使得收益最高某項(xiàng)任務(wù)確定后，如何安排人、財(cái)、物，使得費(fèi)用最省1.1.1引例

例1:某工廠擁有A、B、C三個(gè)車(chē)間，生產(chǎn)甲、乙兩種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占用生產(chǎn)能力時(shí)數(shù)，每件產(chǎn)品可以獲得的利潤(rùn)以及三個(gè)車(chē)間可利用的時(shí)數(shù)如下表所示：

產(chǎn)品甲x1產(chǎn)品乙x2

生產(chǎn)能力（工時(shí)/天）A108B0212C3436利潤(rùn)（百元/件）35

1.1線性規(guī)劃的一般模型目標(biāo)函數(shù)

Maxz=3x1+5x2

約束條件

x1

+

8s.t.

2x2

123x1+2x2

36

x1，x2

0

例2配料問(wèn)題某化工廠根據(jù)一項(xiàng)合同要為用戶(hù)生產(chǎn)一種用甲、乙兩種原材料混合配置而成的特殊產(chǎn)品。甲、乙兩種原材料都含有A、B、C三種化學(xué)成分，其含量（%）是：甲為12，2，3；乙為3，3，15，按合同規(guī)定，成品中有三種化學(xué)成分的含量不得低于4，2，5。甲、乙兩種原材料成本為每千克3，2元。廠方希望總成本達(dá)到最小，則應(yīng)如何配置該產(chǎn)品？解設(shè)每千克該產(chǎn)品用x1千克甲原料和x2

千克乙原料配置而成，每千克產(chǎn)品成本為z

元，則x1+x2=1

原成料分

成分含量甲乙

x1x2產(chǎn)品成分最低含量（%）ABC12323315425

成本（元/千克）32

例3生產(chǎn)計(jì)劃問(wèn)題（資源利用問(wèn)題）

勝利家具廠生產(chǎn)桌子和椅子兩種家具。桌子售價(jià)50元/個(gè)，椅子銷(xiāo)售價(jià)格30元/個(gè)，生產(chǎn)桌子和椅子要求需要木工和油漆工兩種工種。生產(chǎn)一個(gè)桌子需要木工4小時(shí)，油漆工2小時(shí)。生產(chǎn)一個(gè)椅子需要木工3小時(shí)，油漆工1小時(shí)。該廠每個(gè)月可用木工工時(shí)為120小時(shí)，油漆工工時(shí)為50小時(shí)。問(wèn)該廠如何組織生產(chǎn)才能使每月的銷(xiāo)售收入最大？數(shù)學(xué)模型

maxS=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20各種食物的營(yíng)養(yǎng)成分表生產(chǎn)計(jì)劃問(wèn)題AB備用資源煤1230

勞動(dòng)日3260

倉(cāng)庫(kù)0224

利潤(rùn)4050解:設(shè)產(chǎn)品A,B產(chǎn)量分別為變量x1

，x2

x1

+2x2

303x1+2x2

60

2x2

24

x1，x2

0

maxZ=40x1+50x2

原料ABＣ每單位成本

14102261253171642538

每單位添加劑中維生12148

素最低含量求：最低成本的原料混合方案解：設(shè)每單位添加劑中原料i的用量為xi(i=1,2,3,4)minZ=2x1

+5x2+6x3+8x44x1

+6x2+x3+2x412x1

+x2+7x3+5x4142x2

+x3+3x4

8

xi

0(i=1,…,4)

解：設(shè)xi

表示第i班次時(shí)開(kāi)始上班的司機(jī)和乘務(wù)人員數(shù),這樣我們建立如下的數(shù)學(xué)模型。目標(biāo)函數(shù)：Minx1+x2+x3+x4+x5+x6

約束條件：s.t.

x1+x6≥60

x1+x2≥70

x2+x3≥60

x3+x4≥50

x4+x5≥20

x5+x6≥30

x1,x2,x3,x4,x5,x6≥0

人力資源分配的問(wèn)題

“Max”是英文單詞“Maximize”的縮寫(xiě)，Min(minimize最小化）；

“s.t.”是“subjectto”的縮寫(xiě)，表示“滿(mǎn)足于……”。線性規(guī)劃（Linearprogramming----LP)

1.2線性規(guī)劃的圖解法

線性規(guī)劃的圖解法(解的幾何表示)適用于只有兩個(gè)變量的線性規(guī)劃問(wèn)題.[例1]MaxZ=3x1+5x2x1≤80x1+2x2≤123

x1+4x2

≤36x1,x2≥0最優(yōu)解為:x1=4,x2=6oD(0,6)963812X1=82x2=123x1+4x2=36x1x2C(4,6)F(8,6)B(8,3)A(8,0)Z=15Z=42Z=01.2.1圖解法的基本步驟max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0目標(biāo)函數(shù)等值線可行域x2x1最優(yōu)解064-86例題目標(biāo)函數(shù)

MINZ=3x1+2x2約束條件

12x1

+3x2

≥4s.t.2x1+

3x2

≥

23x1+15x2

≥5

x1+x2=1

x1，x2

0

1.2.2圖解法的幾點(diǎn)說(shuō)明P27約束函數(shù)是等式，則代表區(qū)域?yàn)橹本€畫(huà)目標(biāo)函數(shù)時(shí)，只需賦給Z兩個(gè)適當(dāng)?shù)闹稻湍艽_定其法線方向找出最優(yōu)點(diǎn)后，其坐標(biāo)值有兩種求法

1）觀測(cè)

2）方程組法

max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0目標(biāo)函數(shù)等值線可行域x2x1最優(yōu)解064-86a)唯一解b)多重解如果目標(biāo)函數(shù)變?yōu)椋?/p>

Maxz=3x1

+4x2s.t.x1≤8(1)2x2

≤12(2)3x1+4x2

≤36(3)

x1,x2

≥0

(4)

最優(yōu)情況下目標(biāo)函數(shù)的等值線與直線（3）重合。最優(yōu)解有無(wú)窮多個(gè)，是從點(diǎn)C(4,6)到點(diǎn)B(8,3)T線段上的所有點(diǎn)，最優(yōu)值為Z=36。

目標(biāo)函數(shù)

Maxz=3x1+2x2

約束條件

-2x1

+x2

≤

2s.t.x1_-3x2

≤

3x1，x2

0

c)無(wú)界解目標(biāo)函數(shù)MINZ=3x1+2x2約束條件12x1

+3x2

≥4s.t.2x1+

3x2

≥

23x1+15x2

≥5

x1+x2=1

x1，x2

0

若增加約束4x1+3x2

2d)可行域?yàn)榭占療o(wú)可行解（二維）線性規(guī)劃問(wèn)題圖解法：數(shù)學(xué)模型

maxS=50x1+30x2s.t.4x1+3x21202x1+x2

50x1,x2

0由4x1+3x2120x10x20圍成的區(qū)域4x1+3x2120x130402010x25040302010maxS=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20由2x1+x250x10x2

0圍成的區(qū)域2x1+x250x2504040403020101020304040x1x12x1+x250同時(shí)滿(mǎn)足：2x1+x2

504x1+3x2120x10x20的區(qū)域——可行域4x1+3x2120x250404030201010203040x1可行域是由約束條件圍成的區(qū)域，該區(qū)域內(nèi)的每一點(diǎn)都是可行解，它的全體組成問(wèn)題的解集合。該問(wèn)題的可行域是由O，Q1，Q2，Q3作為頂點(diǎn)的凸多邊形可行域Q2（15，20）Q1（25，0）O（0，0）Q3（0，40）二個(gè)重要結(jié)論：滿(mǎn)足約束條件的可行域一般都構(gòu)成凸多邊形。二個(gè)重要結(jié)論：滿(mǎn)足約束條件的可行域一般都構(gòu)成凸多邊形。這一事實(shí)可以推廣到更多變量的場(chǎng)合。二個(gè)重要結(jié)論：滿(mǎn)足約束條件的可行域一般都構(gòu)成凸多邊形。這一事實(shí)可以推廣到更多變量的場(chǎng)合。最優(yōu)解必定能在凸多邊形的某一個(gè)頂點(diǎn)上取得。1.3線性規(guī)劃的標(biāo)準(zhǔn)形式1.3.1標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：M1Maxz=c1x1+c2x2+…

+cnxn

約束條件：a11x1+a12x2+

…

+a1nxn

=

b1a21x1+a22x2+…

+a2nxn

=b2

...am1x1+am2x2+…+amnxn

=bm

x1，x2，…

，xn

≥0或簡(jiǎn)記為(M2):

maxZ=∑cjxj

∑aijxj=bii=1,2,…,m

xj≥0

j=1,2,…,n矩陣形式（M3）x1

c1

b1

a11a12..a1nx2

c2

b2

a21a22..a2nx=.C=.B=.A=.........

xn

cn

bn

am1am2..amn

LP的標(biāo)準(zhǔn)形式有如下四個(gè)特點(diǎn)：目標(biāo)最大化約束為等式?jīng)Q策變量均非負(fù)右端項(xiàng)非負(fù)

1.3.2非標(biāo)準(zhǔn)形LP問(wèn)題標(biāo)準(zhǔn)化一.極小化目標(biāo)函數(shù)的問(wèn)題：

設(shè)目標(biāo)函數(shù)為

Minz=c1x1

+c2x2

+…+cnxn

-kkZ=-Z目標(biāo)函數(shù)求極小時(shí)例如:MinZ=3x1+6x24x1+8x2=9x1,x2≥0標(biāo)準(zhǔn)形式為:MaxZ`=-3x1-6x24x1+8x2=9x1,x2≥0則可以令z’

＝-z

，該極小化問(wèn)題與下面的極大化問(wèn)題有相同的最優(yōu)解，即

Maxz’=-c1x1

-c2x2-…-cnxn

Minz

＝-Maxz’

(1)

右端項(xiàng)有負(fù)值的問(wèn)題：當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，如bi<0，則把該等式約束兩端同時(shí)乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi

。二、函數(shù)約束

(2)約束條件不是等式的問(wèn)題：

設(shè)約束條件為

ai1x1+ai2x2+…+ainxn

≤bi

引進(jìn)一個(gè)新的變量Xn+i，

Xn+i≥0，新的約束條件成為

ai1x1+ai2x2+…+ainxn+Xn+i=bi

(3)當(dāng)約束條件為ai1x1+ai2x2+

…

+ainxn

≥bi

時(shí)，引入Xn+i

Xn+i

≥0，新約束條件成為

ai1x1+ai2x2+…+ainxn-Xn+i=bi為了使約束由不等式成為等式而引進(jìn)的變量

Xn+i稱(chēng)為“松弛變量”。

三、決策變量1變量為負(fù)時(shí)：

令xj’=-xj

xj’≥0，2變量無(wú)符號(hào)限制時(shí)：當(dāng)某一個(gè)變量xj沒(méi)有非負(fù)約束時(shí)，令

xj=xj’-xj”其中

xj’≥0，xj”≥0例a將下列問(wèn)題化成標(biāo)準(zhǔn)型:Minz=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=5x1,x20x3無(wú)非負(fù)限制Maxz’=x1-2x2+3x3’-3x3”s.t.x1+x2+x3’-x3”+x4=7x1-x2+x3’-x3”-x5=2-3x1+x2+2x3’-2x3”=5x1,x2,x3’,x3”,x4,x50

例b：將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式

Minz=3.6x1

-5.2x2+1.8x3s.t.2.3x1

+5.2x2-6.1x3

≤15.74.1x1

+3.3x3

≥8.9

x1

+x2+x3

=38

x1

,x2,x3≥0

解：首先,將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令z’=-z=-3.6x1+5.2x2-1.8x3

引進(jìn)松弛變量x4，x5

≥0。得到標(biāo)準(zhǔn)形式的線性規(guī)劃問(wèn)題：Maxz’=-3.6x1

+5.2x2-1.8x3s.t.2.3x1+5.2x2-6.1x3+x4=15.74.1x1+3.3x3-x5=8.9

x1+x2+x3=38

x1,x2,x3,x4,x5

≥0例c：將以下線性規(guī)劃問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)形式Minz=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

≥396x2+2x3+3x4≤-58

x1,x3,x4

≥0解：1）將目標(biāo)函數(shù)轉(zhuǎn)換成極大化：令z’=-z=3x1–5x2–8x3+7x4

；2）引進(jìn)松弛變量x5,x6,x7

≥0；3）x2無(wú)非負(fù)限制，令x2=x2’-x2”,其中 x2’≥0，x2”≥0；

4）由于第3個(gè)約束右端項(xiàng)系數(shù)為-58，于是把該式兩端乘以-1。

標(biāo)準(zhǔn)型為：Maxz’=3x1–5x2’+5x2”–8x3+7x4s.t.2x1–3x2’+3x2”+5x3+6x4+x5=284x1+2x2’-2x2”+3x3-9x4-x6=39-6x2’+6x2”-2x3-3x4-x7

=58

x1,x2’,x2”,x3,x4,x5,x6,x7

≥0練習(xí)題將下列線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形:MinZ=x1+2x2+3x34x1+5x2+6x3=-78x1+9x2+10x3≥1112x1+13x2+14x3≤15x1≥0,x2≤0,x3取值無(wú)約束可行解、可行解集（可行域）最優(yōu)解、最優(yōu)值基、基變量、非基變量基本解、基本可行解可行基、最優(yōu)基

1.4線性規(guī)劃的解及其性質(zhì)1.4.1線性規(guī)劃的解的概念3、基本解目標(biāo)函數(shù)

Maxz=3x1+5x2

約束條件

x1

+x3=8s.t.

2x2

+x4=123x1+4x2+x5

=

36

x1，x2

，x3，x4，

x5

0

圖解法求解線性規(guī)劃基向量;基中每一個(gè)列向量,aj基變量：若B為基，則B中列所對(duì)應(yīng)的變量稱(chēng)為基變量，用XB表示，余下的其他變量稱(chēng)為非基變量，用XN表示。若B是從A中任取m個(gè)列所構(gòu)成的方陣，則稱(chēng)B是線性規(guī)劃問(wèn)題的一個(gè)基?；涸O(shè)A是m×n維線性方程組的系數(shù)矩陣，A=(a1…

amam+1…

an)=(BN)

基向量非基向量…X=(X1…

XmXm+1…

Xn)T=(XBXN)T

基變量非基變量

XB

XN…AX=b的求解A=(BN)X=(XBXN)TXBXNBXB+NXN=bBXB=b-NXNXB=B-1b-B-1NXN令XN=0(BN)=b

基本解——對(duì)應(yīng)于基B，X=為AX=b的一個(gè)解。B-1b0※基本解中最多有m個(gè)非零分量?！窘獾臄?shù)目不超過(guò)Cnm=個(gè)。n!m!(n-m)!※若基本解中有一個(gè)或更多個(gè)基變量XJ=0則稱(chēng)之為退化基本解。4.基本可行解——基B基本解X=若B-1b0，稱(chēng)基B為可行基,X為基本可行解

。最優(yōu)基本可行解對(duì)應(yīng)的基稱(chēng)為最優(yōu)基B-1b0退化的基本可行解——若基本可行解有一個(gè)或更多個(gè)基變量為零則稱(chēng)為退化的基本可行解。注意兩點(diǎn)：1)B在A中是任意取的。故A中有很多基B。2)基變量是針對(duì)B而言的，不同的B，其對(duì)應(yīng)的基變量和非基變量是不同的。例、X1+X3=82X2+X4=123

X1+4X2+X5=36X1…X50101000201034001a1a2a3a4a5A=X1X2X3X4X5X=b=81236B=(a3a4a5)=I可逆

N=(a1a2)X3=8-X1X4=12-2X2X5=36-3X1-4X2令X1=

X2=0,X3=8,X4=12,X5=36X0===XN0XBB-1b0081236010又：Ｂ1=(

a2a3a4)=201400|B1|=4≠0,B可逆X2=(36-3X1-X5)/4X3=8-X1X4=3/2X1+1/2X5-6令X1=X5=0X=(0,9,8,-6,0)T101若取Ｂ2=(a1a2a3)=020340X*=（4，6，4，0，0）T|B2|=-6≠0,B可逆例：給定約束條件

-X3+X4=0X2+X3+X4=3-X1+X2+X3+X4=2Xj0(j=1,2,3,4)求出基變量是X1,X3,X4的基本解，是不是可行解？

0-11解：B=(a1a3a4)=011-111

01-10B-1=-1/21/2031/21/202b=X1

X3=B-1b

X4

XB=

01-101

=-1/21/203=3/2

1/21/2023/2∴X=(1,0,3/2,3/2)T

是線性規(guī)劃的基矩陣、基變量、非基變量目標(biāo)函數(shù)約束條件行列式≠0基矩陣右邊常數(shù)=可行解非可行解解的集合：解的集合：基本解基本可行解可行解基本解解的集合：解的集合：可行解基本可行解基本最優(yōu)解基本解1.4.2凸性的幾個(gè)基本概念1.凸集——S是n維歐氏空間的一個(gè)集合

X,

Y∈S,若任一個(gè)滿(mǎn)足0μ1的一切實(shí)數(shù)μ

，有

Z=

μX+(1-μ)Y

(0μ1)有Z∈S則稱(chēng)S為凸集。2.極點(diǎn)——S是n維歐氏空間的一個(gè)集合,X∈S如果X不能用S中不同的兩點(diǎn)Y和Z表示為X=λ

Y+(1-λ)Z

(0<

λ

<1)則稱(chēng)X為S的一個(gè)極點(diǎn)。極點(diǎn)凸集凸集不是凸集凸集非凸集3.凸組合

X(1),X(2),…,X(k)

是n維歐氏空間中的k個(gè)點(diǎn)，若有一組數(shù)

μ1,μ2,…,μk

滿(mǎn)足

0μi1(i=1,…,k)有點(diǎn)x=μ1X(1)

+…+μkX(k)則稱(chēng)點(diǎn)X為X(1),X(2),…,X(k)

的凸組合。μ

i=1ki=11.4.3線性規(guī)劃解的性質(zhì)1.若(LP)問(wèn)題有可行解，則可行解集是凸集，可行域有有限個(gè)極點(diǎn)。2(LP)問(wèn)題的基本可行解可行域的極點(diǎn)。若(LP)問(wèn)題有最優(yōu)解，必可以在基本可行解(極點(diǎn))達(dá)到。※基本解中最多有m個(gè)非零分量。※基本解的數(shù)目不超過(guò)Cnm=個(gè)。n!m!(n-m)!

例線性規(guī)劃模型

Maxz=1500x1

+2500x2s.t.3x1

+2x2

+x3=652x1

+x2