线性规划基本性质

第1章线性规划的基本性质11.1线性规划的一般模型1.2线性规划的图解法1.3线性规划的标准形式1.4线性规划的解及其性质1.5线性规划的应用模型第1章线性规划的基本性质第1章线性规划的基本性质21.1

线性规划的一般模型1.1.1

引例

例1

产品配比问题（范例）

某厂拟生产甲、乙两种产品，每件利润分别为3、5百元。甲、乙产品的部件各自在A、B两个车间分别生产，每件甲、乙产品的部件分别需要A、B车间的生产能力1、2工时。两件产品的部件最后都要在C车间装配，装配每件甲、乙产品分别需要3、4工时，三车间每天可用于生产这两种产品的工时分别为8、12、36，问应如何安排生产这两种产品才能获利最多？第1章线性规划的基本性质31.1

线性规划的一般模型z

x1

x2决策变量z=3x1

+5x2max0目标函数x1

≤8①2x2

≤12

②3x1

+4x2

≤36③函数约束x1

，x2

≥0④非负性约束s.t.甲乙10302481236ABC车间产品单耗（工时/件）最大生产能力（工时/天）单位利润（百元/件）

3

5第1章线性规划的基本性质41.1

线性规划的一般模型例2配料问题某化工厂根据一项合同要为用户生产一种用甲、乙两种原料混合配制而成的特殊产品。甲、乙两种原料都含有A，B，C三种化学成分，其含量(%)是:甲为12，2，

3；乙为3，3，15。按合同规定，产品中三种化学成分的含量(%)不得低于4，2，5。甲、乙原料成本为每千克3，2元。厂方希望总成本达到最小，则应如何配制该产品？第1章线性规划的基本性质51.1

线性规划的一般模型

成分含量(%)

原

料

化学成分

甲

乙

产品成分

最低含量(%)A

B

C

12

3

2

3

3

15

4

2

5

成本（元/千克）

3

2

x1x2min

z

=3x1+2x212x1

+3x2≥42x1

+3x2≥2s.t.

3x1+15x2≥5

x1

+x2

=

1

x1

,

x2≥0配料平衡条件z第1章线性规划的基本性质61.1

线性规划的一般模型

1.1.2

线性规划的一般模型

一般LP模型的三类参数：价值系数c

j，消耗系数a

ij，右端常数b

i.LP模型的三要素：决策变量，目标函数，约束条件.s.t.

opt

z=c1x1+c2x2+c3x3+…+cnxn

a11x1

+a12x2+…+a1nxn

b1a21x1

+a22x2+…+a2nxn

b2

…

am1x1+am2x2+…+amnxn

bm

xj≥(或≤)0,

或自由,j=1,2,…,n><><><第1章线性规划的基本性质71.2线性规划的图解法1.2.1图解法的基本步骤

X*=(4,6)Tz*=42

1°画出可行域图形

2°画出目标函数的等值线及其法线

3°确定最优点max

z=3x1+5x2

x1

≤

8

2

x2≤

123x1+

4

x2≤

36

x1,

x2

≥0s.t.x1x2O(0,0)x1=8A(8,0)2x2=12D(0,6)3x1+4x2=36O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)z=15z=30z法向z*=42边界方程第1章线性规划的基本性质81.2线性规划的图解法1.2.2

几点说明实际运用时还须注意以下几点:(1)若函数约束原型就是等式,则其代表的区域仅为一直线,而且问题的整个可行域R(若存在的话)也必然在此直线上。(2)在画目标函数等值线时只须画两条就能确定其法线方向,为此,

只须赋给z

两个适当的值。(3)在找出最优点后,关于其坐标值有两种确定方法:①

在图上观测最优点坐标值②

通过解方程组得出最优点坐标值第1章线性规划的基本性质91.2线性规划的图解法1.2.3

几种可能结果一、唯一解

如例1、例2都只有一个最优点，属于唯一解的情形。s.t.max

z=3x1+4x2

x1≤82x2≤123x1+4x2≤

36

x1，x2≥0

二、多重解z=12z*=36线段BC上无穷多个点均为最优解。O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)第1章线性规划的基本性质101.2线性规划的图解法x1x2z*三、无界解3694812x1x2R2R1∩R2=Ø四、无可行解+∞R1第1章线性规划的基本性质111.3线性规划的标准形式1.3.1

线性规划问题的标准形式max

z=c1x1+c2x2+c3x3+…+cnxns.t.a11x1

+a12x2+

…+a1nxn

=

b1(≥0)a21x1

+a22x2+

…+a2nxn

=b2(≥0)

…

…

…am1x1+am2x2+…+amnxn

=

bm(≥0)x1

,

x2,…

,xn≥0简记为：maxz

=∑cjxjj=1ns.t.∑aijxj

=bi,

i=1,2,…

,mj=1nxj

≥0,

j=1,2,…

,nmaxz=CTX

s.t.AX=bX≥0(M1):

(M2):

(M3):

(M)

第1章线性规划的基本性质121.3线性规划的标准形式

1.3.2非标准形LP问题的标准化

一、目标函数

minz=CTX令z′=

－

z

maxz′=

－

CTX

例：minz=3x1＋

2x2

maxz′=

－

3x1－

2x2

二、函数约束

⑴bi<0两边同时乘以

-1

⑵约束为≤形式加上松弛变量

⑶约束为≥形式减去剩余变量

三、决策变量

若xk

≤0,

令xk

=－

xk′,则xk′≥0

若xk为自由变量,

令xk

=xk′－

xk〞且xk′,xk〞≥0

•xx*f

(x)-f

(x)第1章线性规划的基本性质131.3线性规划的标准形式z=3x1+5x2maxx1

≤82x2

≤123x1+4x2

≤36x1

，x2

≥0s.t.x1

+x3

=82x2

+x4

=123x1+4x2

+x5

=36x1，x2，x3

，x4

，x5

≥0s.t.z=3x1+5x2max范例+0x3+0

x4+0

x5第1章线性规划的基本性质141.3线性规划的标准形式minz=

x1＋

2x2

－

3x3

x1＋

2x2

－

x3

≤52x1＋

3x2

－

x3≥6

－

x1

－

x2

＋

x3≥－

2

x1

≥0,

x3

≤

0s.t.解:max

z′=

－

x1

－

2x2

＋

3x3s.t.x1＋

2x2

－

x3

+x4

=5

2x1＋

3x2

－

x3

-

x5

=6x1＋

x2

－

x3

+x6

=2

x1

,

x4

,

x5

,

x6

≥0,

x3

≤

0例4

将下述LP问题化成标准形第1章线性规划的基本性质151.3线性规划的标准形式令x2

=

x2′－

x2〞，且

x2′，x2〞

≥0x3

=

-x3′代入上式中，得

maxz′=

－

x1－

2

x2′+

2

x2〞－

3x3′

x1+2x2′－

2x2〞+

x3′+

x4

=5

2x1+3x2′－

3x2〞+

x3′

－

x5

=6

x1

+

x2′

－

x2〞

+

x3′

+x6

=2

x1

,

x2′,

x2〞,

x3′,

x4

,

x5

,

x6

≥0s.t.第1章线性规划的基本性质161.4线性规划的解及其性质1.4.1线性规划的解的概念

一、可行解:

满足LP问题所有约束条件的X。二、最优解:

满足目标要求的可行解X。三、基本解:

只适用于标准形LP问题（M）。

(1)

基(矩阵)AX=b

设B为A的一个m阶子矩阵，若|B|≠0,则称B为约束方程组AX=b或标准形LP问题(M)的一个基（矩阵）。第1章线性规划的基本性质171.4线性规划的解及其性质范例A=10100

0201034001

x1

x2

x3

x4

x5a1

a2

a3

a4

a5

可取B0=（a3,a4,a5）为基（|B0

|≠0）,这时称a3,a4,a5为基向量，而a1

,a2为非基向量；称x3,x4,x5为基变量，而x1

,x2为非基变量。第1章线性规划的基本性质181.4线性规划的解及其性质

(2)基本解范例的标准形maxz=3x1

+5x2s.t.

x1

+x3

=82x2

+x4

=123x1

+

4x2

+x5

=36

x1,x2

,

x3

,

x4

,

x5

≥0

取B0=（a3,a4,a5）为基，令一切非基变量x1=

x2=0,可解得基变量x3

=

8

，x4

=

12

，x5

=

36则得一特解

X0=(

0，0，8，12，36)T

称为一个(关于

B0

为基的)基本解。第1章线性规划的基本性质191.4线性规划的解及其性质也可取

B1=(a2,a3,a4)为基,得

X1=

(0，9，8，-6，0)T还可取

B2=

(a1,a2,a3)为基,得

X2

=

(4，6，4，0，0)T等等。四、基本可行解

满足非负性约束的基本解。如X0，X2

；而X1

不可行。对基本(可行)解而言：在其分量中，若有一个或更多个基变量取值为0，则称其为一个退化的基本(可行)解，否则为非退化的。如设：X

=

(0，6，5，0，0)T是一个基本可行解，其中x5

=0为基变量，则该X为退化的基本可行解。第1章线性规划的基本性质201.4线性规划的解及其性质非退化的基本(可行)解，并恰有

n–m个0分量。

基本可行解对应的基，称为可行基；

最优基本解对应的基，称为最优基。如：基

B0=

(a2,a3,a4)

对应X0=

(0，0，8，12，36)T可行

基

B1=

(a2,a3,a4)

对应X1=

(0，9，8，-6，0)T不可行

基

B2

=

(a1,a2,a3)

对应X2

=

(

4，6，4，0，0)T

恰有m个非

0

分量，为可行基为非可行基为最优基x*x*B*第1章线性规划的基本性质211.4线性规划的解及其性质1.4.2

凸性的几个基本概念一、凸集

设S

En，对任意两点X∈S

，Y∈S，若对满足0

≤μ

≤1的一切实数μ

，都有

μX+(1-μ)Y∈S则称S为凸集。XYXY

凸集凸集非凸集非表示S中两点X，Y连线上的任一点凸集的几何意义：凸集S中任意两点X，Y连线上的点，都在凸集S中。第1章线性规划的基本性质221.4线性规划的解及其性质二、极点

设凸集S

En,

X∈S，如果X不能用S中不同的两点Y和Z表示为

X=λY+(1-λ)Z

(0<λ<1)则称X为S的一个极点。三、

凸组合

设Xi∈En,实数μi≥0,i

=1,2,…,s,且∑μi=1，则称

X

=

μ1X1

+

μ2X2

+…+

μsXs为点

X1，X2，…，Xs

的一个凸组合。第1章线性规划的基本性质231.4线性规划的解及其性质1.4.3线性规划的解的性质性质1：LP问题(M)的可行域R={

X︱AX=b,X≥0

}是凸集。

性质2：LP问题(M)的一个基本可行解与可行域

R

的一个极点互相对应。

性质3：线性规划的基本定理

对于一个给定的标准型LP问题(M)来说：⑴若(M)有可行解，则必有基本可行解；⑵若(M)有最优解，则必有最优基本解。

性质4：若LP问题的可行域R≠Ø,则R至少有一极点。

性质5：LP问题可行域R的极点数目必为有限个。

第1章线性规划的基本性质241.4线性规划的解及其性质仅就标准形LP问题(M)说明其合理性。因(M)是一个m阶n维的LP问题，则从其系数阵的n列中取出m列，所构成其基的个数不超过C

mn=n！

m！(n-m)！<

∞≤Cmn基本可行解的个数≤基本解的个数而问题(M)的

枚举法:

当m=50，n=100时，此时需要求解的50元50阶的线性方程组的个数为C

50100

=100！50！50！

≈1029

这是一个天文数字！故需另寻其他有效方法。第1章线性规划的基本性质251.5线性规划的应用模型

1.5.1生产计划问题

某企业拟用m种资源生产n种产品，已知第i种资源的数量为bi,其单价为pi,每生产一个单位第j种产品所提供的产值为vj,所消耗的第i种资源的数量为aij。第j种产品的合同与指令性计划的产量指标为ej,最高需求量为dj。该企业应如何拟定生产计划？第1章线性规划的基本性质26

一、决策变量

设xj为第j种产品的计划产量

二、约束条件⑴指标约束xj≥ej

,

j=1,2,…

,n⑵需求约束xj≤dj

,

j=1,2,…

,n⑶资源约束

三、目标函数⑴总产值1.5线性规划的应用模型

j=1n∑aijxj≤bi,

i=1,2,…,mj=1nm

i=1z2=∑pi(∑aij

xj)

⑵总成本z1=∑vj

xj

nj=1第1章线性规划的基本性质271.5线性规划的应用模型

i=1=∑vj

xj-∑pi(∑aij

xj)j=1nmj=1n=∑(vj-

∑piaij

)

xjj=1ni=1m令

cj

=vj-

∑piaiji=1mxj≥ej

,

j=1,2,…

,nxj≤dj∑aijxj≤bi,

i=1,2,…,mj=1nmaxz=∑cj

xjj=1ns.t.则⑶

总利润

z=z1-z2第1章线性规划的基本性质281.5.2食谱问题

有n种食品,每种食品中含有m种营养成分。食品用

j=1,2,…

,n表示，养分用

i=1,2,…

,m表示。已知第

j种食品单价为

cj,每天最大供量为

dj;

而每单位第

j种食品所含第

i种养分的数量为

aij。假定某种生物每天对第

i种养分的需求量至少为

bi,

而每天进食数量限定在

[

h1,

h2

]

范围内。试求该生物的食谱，使总成本为最小。1.5线性规划的应用模型第1章线性规划的基本性质291.5线性规划的应用模型

设xj为每天提供给该生物食用的第j种食品的数量，则该问题的数学模型为:

s.t.0

≤

xj

≤

dj

,

j=1,2,…,nminz=∑cj

xjj=1nj=1

h1

≤

∑xj

≤h2nj=1

∑aij

xj

≥

bi,

i=1,2,…,mn

某厂制造某种部件，由2个B1零件,3个B2零件配套组装而成。该厂有A1,A2,A3三种机床可加工这两种零件，每种机床的台数，以及每台机床的生产率如下表所示。求产量最大的生产方案。1.5.3

产品配套问题第1章线性规划的基本性质301.5线性规划的应用模型

一、决策变量

设以xij表示每台Ai(i=1,2,3)机床每个工作日加工Bj(j=1,2)零件的时间(单位:工作日)；

z为B1,B2零件按2:3的比例配套的数量(套/日)。机床种类机床台数每台机床生产率(件/日)零件B1零件B2A132030A223545A341018x11x12x21x22x31x32第1章线性规划的基本性质311.5线性规划的应用模型

二、约束条件

⑴工时约束

⑵配套约束机床种类总生产率(件/日)零件B1零件B2A16090A27090A34072x11x12x21x22x31x32z=min{(60x11+70x21+40x31),(90x12+90x22+72x32)}1213z≤(60x11+70x21+40x31)12z≤(90x12+90x22+72x32)13非线性，等价改写成：

或x11

+

x12

=1x21

+

x22

=1x31

+

x32

=1z-35x11-35x21-20x31≤0z-30x12-30x22-24x32≤0第1章线性规划的基本性质321.5线性规划的应用模型则该问题的数学模型为:maxz

s.t.

x11+

x12

=1

x21+

x22

=1

x31+

x32

=1z－

35x11－

35x21－

20x31≤0z－

30x12－

30x22－

24x32

≤0z,

x11,x12,x21,x22,x31,x32≥0

制造某种机床，需要

A,B,C三种轴件，其规格与数量如表所示，各类轴件都用5.5米长的同一种圆钢下料。若计划生产100台机床，最少需要用多少根圆钢？1.5.4

下料问题第1章线性规划的基本性质331.5线性规划的应用模型轴类

规格：长度（米）

每台机床所需轴件数

A

3.1

1

B

2.1

2

C

1.2

4

余料δj<1.2找出全部省料截法一根圆钢所截各类轴件数

截法轴类

轴

件

需要量

A(3.1)

100

B(2.1)

200

C(1.2)

400

余料(米)

234511100.310200210.1

0

0

1

0

2

4

1

0.7第1章线性规划的基本性质341.5线性规划的应用模型min

z=

x1

+

x2

+

x3

+

x4

+

x5s.t.x1

+x2

≥100x1

+2x3

+x4

≥2002x2

+x3

+2x4

+4x5

≥400x1，x2

，x3，