运筹学之线性规划课件

第一章线性规划基本性质本章主要内容线性规划一般模型线性规划的图解法(重点）线性规划的标准形式(重点）线性规划解的主要概念（难点）线性规划应用——建模线性规划（Linearprogramming----LP)解决稀缺资源最优分配的有效方法研究对象在一定的人力、财力、资源条件下，如何合理安排，使得收益最高某项任务确定后，如何安排人、财、物，使得费用最省1.1.1引例

例1:某工厂拥有A、B、C三个车间，生产甲、乙两种产品。每件产品在生产中需要占用生产能力时数，每件产品可以获得的利润以及三个车间可利用的时数如下表所示：

产品甲x1产品乙x2

生产能力（工时/天）A108B0212C3436利润（百元/件）35

1.1线性规划的一般模型目标函数

Maxz=3x1+5x2

约束条件

x1

+

8s.t.

2x2

123x1+2x2

36

x1，x2

0

例2配料问题某化工厂根据一项合同要为用户生产一种用甲、乙两种原材料混合配置而成的特殊产品。甲、乙两种原材料都含有A、B、C三种化学成分，其含量（%）是：甲为12，2，3；乙为3，3，15，按合同规定，成品中有三种化学成分的含量不得低于4，2，5。甲、乙两种原材料成本为每千克3，2元。厂方希望总成本达到最小，则应如何配置该产品？解设每千克该产品用x1千克甲原料和x2

千克乙原料配置而成，每千克产品成本为z

元，则x1+x2=1

原成料分

成分含量甲乙

x1x2产品成分最低含量（%）ABC12323315425

成本（元/千克）32

例3生产计划问题（资源利用问题）

胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个，椅子销售价格30元/个，生产桌子和椅子要求需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大？数学模型

maxS=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20各种食物的营养成分表生产计划问题AB备用资源煤1230

劳动日3260

仓库0224

利润4050解:设产品A,B产量分别为变量x1

，x2

x1

+2x2

303x1+2x2

60

2x2

24

x1，x2

0

maxZ=40x1+50x2

原料ABＣ每单位成本

14102261253171642538

每单位添加剂中维生12148

素最低含量求：最低成本的原料混合方案解：设每单位添加剂中原料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)

解：设xi

表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：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

人力资源分配的问题

“Max”是英文单词“Maximize”的缩写，Min(minimize最小化）；

“s.t.”是“subjectto”的缩写，表示“满足于……”。线性规划（Linearprogramming----LP)

1.2线性规划的图解法

线性规划的图解法(解的几何表示)适用于只有两个变量的线性规划问题.[例1]MaxZ=3x1+5x2x1≤80x1+2x2≤123

x1+4x2

≤36x1,x2≥0最优解为: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目标函数等值线可行域x2x1最优解064-86例题目标函数

MINZ=3x1+2x2约束条件

12x1

+3x2

≥4s.t.2x1+

3x2

≥

23x1+15x2

≥5

x1+x2=1

x1，x2

0

1.2.2图解法的几点说明P27约束函数是等式，则代表区域为直线画目标函数时，只需赋给Z两个适当的值就能确定其法线方向找出最优点后，其坐标值有两种求法

1）观测

2）方程组法

max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0目标函数等值线可行域x2x1最优解064-86a)唯一解b)多重解如果目标函数变为：

Maxz=3x1

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

≤12(2)3x1+4x2

≤36(3)

x1,x2

≥0

(4)

最优情况下目标函数的等值线与直线（3）重合。最优解有无穷多个，是从点C(4,6)到点B(8,3)T线段上的所有点，最优值为Z=36。

目标函数

Maxz=3x1+2x2

约束条件

-2x1

+x2

≤

2s.t.x1_-3x2

≤

3x1，x2

0

c)无界解目标函数MINZ=3x1+2x2约束条件12x1

+3x2

≥4s.t.2x1+

3x2

≥

23x1+15x2

≥5

x1+x2=1

x1，x2

0

若增加约束4x1+3x2

2d)可行域为空集无可行解（二维）线性规划问题图解法：数学模型

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

50x1,x2

0由4x1+3x2120x10x20围成的区域4x1+3x2120x130402010x25040302010maxS=50x1+30x2s.t.4x1+3x21202x1+x250x1,x20由2x1+x250x10x2

0围成的区域2x1+x250x2504040403020101020304040x1x12x1+x250同时满足：2x1+x2

504x1+3x2120x10x20的区域——可行域4x1+3x2120x250404030201010203040x1可行域是由约束条件围成的区域，该区域内的每一点都是可行解，它的全体组成问题的解集合。该问题的可行域是由O，Q1，Q2，Q3作为顶点的凸多边形可行域Q2（15，20）Q1（25，0）O（0，0）Q3（0，40）二个重要结论：满足约束条件的可行域一般都构成凸多边形。二个重要结论：满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。二个重要结论：满足约束条件的可行域一般都构成凸多边形。这一事实可以推广到更多变量的场合。最优解必定能在凸多边形的某一个顶点上取得。1.3线性规划的标准形式1.3.1标准形式目标函数：M1Maxz=c1x1+c2x2+…

+cnxn

约束条件：a11x1+a12x2+

…

+a1nxn

=

b1a21x1+a22x2+…

+a2nxn

=b2

...am1x1+am2x2+…+amnxn

=bm

x1，x2，…

，xn

≥0或简记为(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的标准形式有如下四个特点：目标最大化约束为等式决策变量均非负右端项非负

1.3.2非标准形LP问题标准化一.极小化目标函数的问题：

设目标函数为

Minz=c1x1

+c2x2

+…+cnxn

-kkZ=-Z目标函数求极小时例如:MinZ=3x1+6x24x1+8x2=9x1,x2≥0标准形式为:MaxZ`=-3x1-6x24x1+8x2=9x1,x2≥0则可以令z’

＝-z

，该极小化问题与下面的极大化问题有相同的最优解，即

Maxz’=-c1x1

-c2x2-…-cnxn

Minz

＝-Maxz’

(1)

右端项有负值的问题：当某一个右端项系数为负时，如bi<0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi

。二、函数约束

(2)约束条件不是等式的问题：

设约束条件为

ai1x1+ai2x2+…+ainxn

≤bi

引进一个新的变量Xn+i，

Xn+i≥0，新的约束条件成为

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

(3)当约束条件为ai1x1+ai2x2+

…

+ainxn

≥bi

时，引入Xn+i

Xn+i

≥0，新约束条件成为

ai1x1+ai2x2+…+ainxn-Xn+i=bi为了使约束由不等式成为等式而引进的变量

Xn+i称为“松弛变量”。

三、决策变量1变量为负时：

令xj’=-xj

xj’≥0，2变量无符号限制时：当某一个变量xj没有非负约束时，令

xj=xj’-xj”其中

xj’≥0，xj”≥0例a将下列问题化成标准型:Minz=-x1+2x2-3x3s.t.x1+x2+x37x1-x2+x32-3x1+x2+2x3=5x1,x20x3无非负限制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：将以下线性规划问题转化为标准形式

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

解：首先,将目标函数转换成极大化：令z’=-z=-3.6x1+5.2x2-1.8x3

引进松弛变量x4，x5

≥0。得到标准形式的线性规划问题：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：将以下线性规划问题转化为标准形式Minz=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

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

x1,x3,x4

≥0解：1）将目标函数转换成极大化：令z’=-z=3x1–5x2–8x3+7x4

；2）引进松弛变量x5,x6,x7

≥0；3）x2无非负限制，令x2=x2’-x2”,其中 x2’≥0，x2”≥0；

4）由于第3个约束右端项系数为-58，于是把该式两端乘以-1。

标准型为：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练习题将下列线性规划问题化为标准形:MinZ=x1+2x2+3x34x1+5x2+6x3=-78x1+9x2+10x3≥1112x1+13x2+14x3≤15x1≥0,x2≤0,x3取值无约束可行解、可行解集（可行域）最优解、最优值基、基变量、非基变量基本解、基本可行解可行基、最优基

1.4线性规划的解及其性质1.4.1线性规划的解的概念3、基本解目标函数

Maxz=3x1+5x2

约束条件

x1

+x3=8s.t.

2x2

+x4=123x1+4x2+x5

=

36

x1，x2

，x3，x4，

x5

0

图解法求解线性规划基向量;基中每一个列向量,aj基变量：若B为基，则B中列所对应的变量称为基变量，用XB表示，余下的其他变量称为非基变量，用XN表示。若B是从A中任取m个列所构成的方阵，则称B是线性规划问题的一个基。基：设A是m×n维线性方程组的系数矩阵，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

基本解——对应于基B，X=为AX=b的一个解。B-1b0※基本解中最多有m个非零分量。※基本解的数目不超过Cnm=个。n!m!(n-m)!※若基本解中有一个或更多个基变量XJ=0则称之为退化基本解。4.基本可行解——基B基本解X=若B-1b0，称基B为可行基,X为基本可行解

。最优基本可行解对应的基称为最优基B-1b0退化的基本可行解——若基本可行解有一个或更多个基变量为零则称为退化的基本可行解。注意两点：1)B在A中是任意取的。故A中有很多基B。2)基变量是针对B而言的，不同的B，其对应的基变量和非基变量是不同的。例、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

是线性规划的基矩阵、基变量、非基变量目标函数约束条件行列式≠0基矩阵右边常数=可行解非可行解解的集合：解的集合：基本解基本可行解可行解基本解解的集合：解的集合：可行解基本可行解基本最优解基本解1.4.2凸性的几个基本概念1.凸集——S是n维欧氏空间的一个集合

X,

Y∈S,若任一个满足0μ1的一切实数μ

，有

Z=

μX+(1-μ)Y

(0μ1)有Z∈S则称S为凸集。2.极点——S是n维欧氏空间的一个集合,X∈S如果X不能用S中不同的两点Y和Z表示为X=λ

Y+(1-λ)Z

(0<

λ

<1)则称X为S的一个极点。极点凸集凸集不是凸集凸集非凸集3.凸组合

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

是n维欧氏空间中的k个点，若有一组数

µ1,µ2,…,µk

满足

0µi1(i=1,…,k)有点x=µ1X(1)

+…+µkX(k)则称点X为X(1),X(2),…,X(k)

的凸组合。µ

i=1ki=11.4.3线性规划解的性质1.若(LP)问题有可行解，则可行解集是凸集，可行域有有限个极点。2(LP)问题的基本可行解可行域的极点。若(LP)问题有最优解，必可以在基本可行解(极点)达到。※基本解中最多有m个非零分量。※基本解的数目不超过Cnm=个。n!m!(n-m)!

例线性规划模型

Maxz=1500x1

+2500x2s.t.3x1

+2x2

+x3=652x1

+x2