管理运筹学021线性规划的数学模型及相关概念课件

第

1

节Linear

ProgrammingL

P线性规划的数学模型

第1节LinearProgramming1第1节线性规划的数学模型及相关概念2一、现实中的线性规划问题及数学模型二、线性规划的标准形式三、线性规划的几何解释四、线性规划的基及基本可行解第1节线性规划的数学模型及相关概念第1节线性规划的数学模型及相关概念2一、现实中的线性规划问23一

现实中的线性规划问题及模型例2-1

生产计划问题某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如表2-1所示，试用线性规划制订使总利润最大的生产计划。第1节线性规划的数学模型及相关概念产品甲产品乙产品丙产品丁1.51.01.5200080005000设备A设备B设备C单位产品消耗的机时数产品设备能力（小时）利润（元/件）

5.247.308.344.181.05.03.02.41.03.51.03.51.03一现实中的线性规划问题及模型例2-1生产计划问题第34一

现实中的线性规划问题及模型z

x1

x2x3x4决策变量z=5.24x1

+7.30x2+8.34x3+4.18x4max0目标函数1.5x1

+1.0x2+2.4x3+1.0x4

≤2000①函数约束非负性约束s.t.第1节线性规划的数学模型及相关概念1.0x1

+5.0x2+1.0x3+3.5x4

≤8000②1.5x1

+3.0x2+3.5x3+1.0x4

≤8000③x1，

x2，

x3，

x4≥0④产品甲产品乙产品丙产品丁1.51.01.5200080005000设备A设备B设备C单位产品消耗的机时数产品设备能力（小时）利润（元/件）

5.247.308.344.181.05.03.02.41.03.51.03.51.04一现实中的线性规划问题及模型zx145一

现实中的线性规划问题及模型第1节线性规划的数学模型及相关概念求解这个线性规划，可以得到最优解为：

x1=294.12（件）x2=1500（件） x3=0 （件） x4=58.82（件）

最大利润为

z=12737.06（元）

请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。5一现实中的线性规划问题及模型第1节线性规划的数学56一

现实中的线性规划问题及模型例2-2

配料问题某工厂要用四种合金T1，T2，T3和T4为原料，经熔炼成为一种新的不锈钢G。这四种原料含元素铬（Cr），锰（Mn）和镍（Ni）的含量（%），这四种原料的单价以及新的不锈钢材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示：设熔炼时重量没有损耗，要熔炼成100公斤不锈钢G，应选用原料T1，T2，T3和T4各多少公斤，使成本最小。第1节线性规划的数学模型及相关概念T1

T2

T3

T43.212.045.823.202.104.30CrMnNiG单价（元/公斤）

1159782764.531.123.062.193.574.271.764.332.73

x1

x2x3x46一现实中的线性规划问题及模型例2-2配料问题第1节67第1节线性规划的数学模型及相关概念z=115x1

+97x2+82x3+76x4min0.0321x1

+0.0453x2+0.0219x3+0.0176x4

≥3.20s.t.x1，

x2，

x3，

x4≥00.0204x1

+0.0112x2+0.0357x3+0.0433x4

≥2.100.0582x1

+0.0306x2+0.0427x3+0.0273x4

≥4.30

x1

+

x2+

x3+

x4

=100求解这个线性规划，可以得到最优解为：

x1=26.58x2=31.57x3=41.84x4=0

最大利润为

z=9549.87（元）一

现实中的线性规划问题及模型7第1节线性规划的数学模型及相关概念z=115x178一

现实中的线性规划问题及模型例2-3

背包问题一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：

要在背包中装入这三种物品各多少件，使背包中的物品价值最高。第1节线性规划的数学模型及相关概念物品1物品2物品3

1017重量（公斤/件）价值（元/件）41722035

x1

x2x38一现实中的线性规划问题及模型例2-3背包问题第1节89第1节线性规划的数学模型及相关概念z=17x1

+72x2+35x3max10x1

+41x2+20x3

≤50s.t.x1，

x2，

x3≥0且为整数求解这个线性规划，可以得到最优解为：

x1=1x2=0x3=2

最高价值为

z=87（元）一

现实中的线性规划问题及模型9第1节线性规划的数学模型及相关概念z=17x1+910一

现实中的线性规划问题及模型例2-4最小费用流问题

某公司下设两个分工厂，两个仓库及一个配送中心。其中F1和F2是两个工厂，W1和W2是两个仓库。D是一个分销中心。由工厂生产的产品经由图所示的运输网络运往仓库。每一条路线运输的单位成本在线段上给出，其中，F1→F2与D→W2路线由于受到路线中的桥梁承重上限的要求，因此有最大运输量限制。其他路线有足够的运输能力来运输两个工厂生产的货物。需要制订的决策是关于每一条路线应该运输多少，目标是总体的运输成本最小化。第1节线性规划的数学模型及相关概念10一现实中的线性规划问题及模型例2-4最小费用流问1011一

现实中的线性规划问题及模型例2-4最小费用流问题

第1节线性规划的数学模型及相关概念900元/单位x6100元/单位x7最多80单位x4x5x2x3x1300元/单位300元/单位F1需求30单位W1生产40单位F2需求60单位W2200元/单位D最多10单位200元/单位400元/单位图2-1公司的配送网络生产50单位11一现实中的线性规划问题及模型例2-4最小费用流问1112第1节线性规划的数学模型及相关概念z=200x1

+400x2+900x3+300x4+100x5+3x6+200x7minx1

+

x2+

x3=50s.t.x1，…，x7≥0-x1

+x4=40-x2-x4+x5=0-x3+

x6

–x7

=-30求解这个线性规划，可以得到最优解为：（x1

，x2，x3，x4，x5，x6，x7

）=（0，40，10，40，80，0，20）

z=49000（元）一

现实中的线性规划问题及模型-x5-

x6+x7

=-60x1

≤10，x5

≤8012第1节线性规划的数学模型及相关概念z=200x11213线性规划的一般形式

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

j，消耗系数a

ij，右端常数b

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

z=c1x1+c2x2+c3x3+…+cnxn

a11x1

+a12x2+…+a1nxn

≤(=≥)

b1a21x1

+a22x2+…+a2nxn

≤(=≥)

b2

…

am1x1+am2x2+…+amnxn

≤(=≥)

bm

xj≥(或≤)0,

或自由,j=1,2,…,n第1节线性规划的数学模型及相关概念一

现实中的线性规划问题及模型13线性规划的一般形式一般LP模型的三类参数：s.t.m1314线性规划的向量和矩阵的表达形式记向量和矩阵第1节线性规划的数学模型及相关概念一

现实中的线性规划问题及模型则线性规划问题可以表示为：max（min)z=CX

s.t.AX≤(=≥)bX≥014线性规划的向量和矩阵的表达形式记向量和矩阵第1节线性规1415二、线性规划的标准形式称以下线性规划的形式为标准形式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=CX

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

(M2):

第1节线性规划的数学模型及相关概念15二、线性规划的标准形式称以下线性规划的形式为标准形式ma1516非标准形LP问题的标准化

一、极小化目标函数的问题

minz=CX令z′=

－

z

maxz′=

－

CX

例：minz=3x1＋

2x2

maxz′=

－

3x1－

2x2

二、约束条件不是等式的问题

⑴bi<0两边同时乘以

-1

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

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

三、变量符号无限制或小于等于零的问题若xk为自由变量,

令xk

=xk′－

xk〞且xk′,xk〞≥0

若xk

≤0,

令xk

=－

xk′,则xk′≥0

第1节线性规划的数学模型及相关概念二、线性规划的标准形式xzzzminz=-zzmaxx*16非标准形LP问题的标准化第1节线性规划的数学模型及相关1617minz=2x1－

3x2＋x3

x1－

x2

＋2

x3

≤32x1＋

3x2

－

x3≥5x1

＋x2

＋

x3=4

x1

≥0,

x2

无约束，

x3

≤

0s.t.第1节线性规划的数学模型及相关概念例2-5将下述LP问题化成标准形式解：令z′=-z

，x2=

x2′－

x2〞，x3′=

-x3

maxz′=

－

2

x1＋3

x2′-

3x2〞＋x3′

x1－

x2′+

x2〞－2

x3′+

x4

=3

2x1+3x2′－

3x2〞+

x3′

－

x5

=5

x1

+

x2′

－

x2〞

－

x3′

=4

x1

,

x2′,

x2〞,

x3′,

x4

,

x5

≥0s.t.二、线性规划的标准形式17minz=2x1－3x2＋x3s.t.第17第1章线性规划的数学模型及相关概念18minz=

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练习：将下述LP问题化成标准形二、线性规划的标准形式第1章线性规划的数学模型及相关概念18minz=x118第1章线性规划的数学模型及相关概念19令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章线性规划的数学模型及相关概念19令x2=x2′19第1节线性规划的基本性质20只有两个变量的线性规划问题

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节线性规划的基本性质20只有两个变量的线性规划问题X20第1节线性规划的基本性质21几点说明实际运用时还须注意以下几点:(1)若函数约束原型就是等式,则其代表的区域仅为一直线,而且问题的整个可行域R(若存在的话)也必然在此直线上。(2)在画目标函数等值线时只须画两条就能确定其法线方向,为此,

只须赋给z

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

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

通过解方程组得出最优点坐标值三、线性规划的几何解释第1节线性规划的基本性质21几点说明三、线性规划的几何解释21第1节线性规划的基本性质22几种可能结果一、唯一解

如例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节线性规划的基本性质22几种可能结果s.t.maxz22第1节线性规划的基本性质23x1x2z*三、无界解3694812x1x2R2R1∩R2=Ø四、无可行解+∞R1三、线性规划的几何解释第1节线性规划的基本性质23x1x2z*三、无界解3623第1节线性规划的基本性质24相关定义定义2-1可行域在n维空间中，满足条件ai1x1+ai2x2+…+ainxn

≤(=≥)

bi且xj≥0的点集。O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)三、线性规划的几何解释第1节线性规划的基本性质24相关定义O(0,0)x1x2R24第1节线性规划的基本性质25定义2-2凸集三、线性规划的几何解释设S是n维空间中的一个点集。若对任意n维向量X1S，X2S，且X1X2，以及任意实数（01），有 X=X1+(1-)X2S则称S为n维空间中的一个凸集（ConvexSet）。点X称为点X1和X2的凸组合。

凸集：非凸集：第1节线性规划的基本性质25定义2-2凸集三、线性规划的25第1节线性规划的基本性质26定义2-3凸集的极点三、线性规划的几何解释设S为一凸集，且XS，若X不能用不同的两点X1S，X2S的线性组合表示为 X=X1+(1-)X2（01）则称X为S的一个极点。

运用以上的定义，线性规划的可行域以及最优解有以下性质：（1）若线性规划的可行域非空，则可行域必定为一凸集。（2）若线性规划有最优解，则最优解一定可以在凸集的极点中找到。

这样，求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为在其可行域的有限个极点上搜索的问题。第1节线性规划的基本性质26定义2-3凸集的极点三、线性2627第1节线性规划的数学模型及相关概念基：设A为线性规划模型约束条件系数矩阵（mn，m<n），而B为其mm子矩阵，若|B|≠0，则称B为该线性规划模型的一个基。基变量：基中每个向量所对应的变量称为基变量。非基变量：模型中基变量之外的变量称为非基变量。基本解（基解）：令模型中所有非基变量X非基=0后，由模型约束方程组 n

aijxj=bi(i=1,2,……,m)得到的一组解。

j=1基本可行解（基可行解）：在基本解中，同时又是可行解的解称为基本可行解。可行基：对应于基本可行解的基称为可行基。四、线性规划的基、基本可行解27第1节线性规划的数学模型及相关概念基：设A为线性规划模27-28-Maxz=2x1+3x2st.x1+x23 x1+2x24 x1,x2

0Maxz=2x1+3x2+0x3+0x4st.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4

0A=x1x2x3x411101201可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T

等。设B=1001，令，则|B|=1≠0,令x1=x2=0，则x3=3,x4=4，X=(0,0,3,4)T例：x3x4——基变量令B=1110x1x3

，则令x2=x4=0，则x3=-1,x1=4，X=(4,0,-1,0)T|B|=-1≠0,——非基本可行解——基本可行解标准化第1节线性规划的数学模型及相关概念四、线性规划的基、基本可行解-28-Maxz=2x1+3x2Maxz=2x12829定理2-1线性规划的基本可行解就是可行域的极点。第1节线性规划的数学模型及相关概念四、线性规划的基、基本可行解Maxz=2x1+3x2s.t.x1+x23 x1+2x24 x1,x2

0Maxz=2x1+3x2+0x3+0x4s.t.x1+x2+x3=3 x1+2x2+x4=4 x1,x2,x3,x4

0例：标准化A矩阵包含以下六个2×2的子矩阵：

B1=[p1，p2] B2=[p1，p3] B3=[p1，p4] B4=[p2，p3] B5=[p2，p4] B6=[p3，p4]其中所有的子矩阵行列式值均不等于0，均为非奇异方阵，因此该问题共有6个基。

29定理2-1线性规划的基本可行解就是可行域的极点。第12930第1节线性规划的数学模型及相关概念四、线性规划的基、基本可行解B6=1001，则|B6|=1≠0,x3x4——基变量——基本可行解对应O点令x1=x2=0，则x3=3,x4=4，X6=(0,0,3,4)T同理可以求得B1、B2、B3、B4、B5对应的基本解：X1=(x1，x2，x3，x4)T=(2，1，0，0)T

对应B点X2=(x1，x2，x3，x4)T=(4，0，-1，0)T对应E点X3=(x1，x2，x3，x4)T=(3，0，0，1)T对应C点X4=(x1，x2，x3，x4)T=(0，2，1，0)T对应A点X5=(x1，x2，x3，x4)T=(0，3，0，-2)T对应D点其中X1，

X3，X4是基本可行解。O(0,0)x1x2B(2,1)E(4,0)C(3,0)A(0,2)D(0,3)30第1节线性规划的数学模型及相关概念四、线性规划的基、基30谢谢！谢谢！31

第

1

节Linear

ProgrammingL

P线性规划的数学模型

第1节LinearProgramming32第1节线性规划的数学模型及相关概念33一、现实中的线性规划问题及数学模型二、线性规划的标准形式三、线性规划的几何解释四、线性规划的基及基本可行解第1节线性规划的数学模型及相关概念第1节线性规划的数学模型及相关概念2一、现实中的线性规划问3334一

现实中的线性规划问题及模型例2-1

生产计划问题某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如表2-1所示，试用线性规划制订使总利润最大的生产计划。第1节线性规划的数学模型及相关概念产品甲产品乙产品丙产品丁1.51.01.5200080005000设备A设备B设备C单位产品消耗的机时数产品设备能力（小时）利润（元/件）

5.247.308.344.181.05.03.02.41.03.51.03.51.03一现实中的线性规划问题及模型例2-1生产计划问题第3435一

现实中的线性规划问题及模型z

x1

x2x3x4决策变量z=5.24x1

+7.30x2+8.34x3+4.18x4max0目标函数1.5x1

+1.0x2+2.4x3+1.0x4

≤2000①函数约束非负性约束s.t.第1节线性规划的数学模型及相关概念1.0x1

+5.0x2+1.0x3+3.5x4

≤8000②1.5x1

+3.0x2+3.5x3+1.0x4

≤8000③x1，

x2，

x3，

x4≥0④产品甲产品乙产品丙产品丁1.51.01.5200080005000设备A设备B设备C单位产品消耗的机时数产品设备能力（小时）利润（元/件）

5.247.308.344.181.05.03.02.41.03.51.03.51.04一现实中的线性规划问题及模型zx13536一

现实中的线性规划问题及模型第1节线性规划的数学模型及相关概念求解这个线性规划，可以得到最优解为：

x1=294.12（件）x2=1500（件） x3=0 （件） x4=58.82（件）

最大利润为

z=12737.06（元）

请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。5一现实中的线性规划问题及模型第1节线性规划的数学3637一

现实中的线性规划问题及模型例2-2

配料问题某工厂要用四种合金T1，T2，T3和T4为原料，经熔炼成为一种新的不锈钢G。这四种原料含元素铬（Cr），锰（Mn）和镍（Ni）的含量（%），这四种原料的单价以及新的不锈钢材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示：设熔炼时重量没有损耗，要熔炼成100公斤不锈钢G，应选用原料T1，T2，T3和T4各多少公斤，使成本最小。第1节线性规划的数学模型及相关概念T1

T2

T3

T43.212.045.823.202.104.30CrMnNiG单价（元/公斤）

1159782764.531.123.062.193.574.271.764.332.73

x1

x2x3x46一现实中的线性规划问题及模型例2-2配料问题第1节3738第1节线性规划的数学模型及相关概念z=115x1

+97x2+82x3+76x4min0.0321x1

+0.0453x2+0.0219x3+0.0176x4

≥3.20s.t.x1，

x2，

x3，

x4≥00.0204x1

+0.0112x2+0.0357x3+0.0433x4

≥2.100.0582x1

+0.0306x2+0.0427x3+0.0273x4

≥4.30

x1

+

x2+

x3+

x4

=100求解这个线性规划，可以得到最优解为：

x1=26.58x2=31.57x3=41.84x4=0

最大利润为

z=9549.87（元）一

现实中的线性规划问题及模型7第1节线性规划的数学模型及相关概念z=115x13839一

现实中的线性规划问题及模型例2-3

背包问题一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：

要在背包中装入这三种物品各多少件，使背包中的物品价值最高。第1节线性规划的数学模型及相关概念物品1物品2物品3

1017重量（公斤/件）价值（元/件）41722035

x1

x2x38一现实中的线性规划问题及模型例2-3背包问题第1节3940第1节线性规划的数学模型及相关概念z=17x1

+72x2+35x3max10x1

+41x2+20x3

≤50s.t.x1，

x2，

x3≥0且为整数求解这个线性规划，可以得到最优解为：

x1=1x2=0x3=2

最高价值为

z=87（元）一

现实中的线性规划问题及模型9第1节线性规划的数学模型及相关概念z=17x1+4041一

现实中的线性规划问题及模型例2-4最小费用流问题

某公司下设两个分工厂，两个仓库及一个配送中心。其中F1和F2是两个工厂，W1和W2是两个仓库。D是一个分销中心。由工厂生产的产品经由图所示的运输网络运往仓库。每一条路线运输的单位成本在线段上给出，其中，F1→F2与D→W2路线由于受到路线中的桥梁承重上限的要求，因此有最大运输量限制。其他路线有足够的运输能力来运输两个工厂生产的货物。需要制订的决策是关于每一条路线应该运输多少，目标是总体的运输成本最小化。第1节线性规划的数学模型及相关概念10一现实中的线性规划问题及模型例2-4最小费用流问4142一

现实中的线性规划问题及模型例2-4最小费用流问题

第1节线性规划的数学模型及相关概念900元/单位x6100元/单位x7最多80单位x4x5x2x3x1300元/单位300元/单位F1需求30单位W1生产40单位F2需求60单位W2200元/单位D最多10单位200元/单位400元/单位图2-1公司的配送网络生产50单位11一现实中的线性规划问题及模型例2-4最小费用流问4243第1节线性规划的数学模型及相关概念z=200x1

+400x2+900x3+300x4+100x5+3x6+200x7minx1

+

x2+

x3=50s.t.x1，…，x7≥0-x1

+x4=40-x2-x4+x5=0-x3+

x6

–x7

=-30求解这个线性规划，可以得到最优解为：（x1

，x2，x3，x4，x5，x6，x7

）=（0，40，10，40，80，0，20）

z=49000（元）一

现实中的线性规划问题及模型-x5-

x6+x7

=-60x1

≤10，x5

≤8012第1节线性规划的数学模型及相关概念z=200x14344线性规划的一般形式

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

j，消耗系数a

ij，右端常数b

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

z=c1x1+c2x2+c3x3+…+cnxn

a11x1

+a12x2+…+a1nxn

≤(=≥)

b1a21x1

+a22x2+…+a2nxn

≤(=≥)

b2

…

am1x1+am2x2+…+amnxn

≤(=≥)

bm

xj≥(或≤)0,

或自由,j=1,2,…,n第1节线性规划的数学模型及相关概念一

现实中的线性规划问题及模型13线性规划的一般形式一般LP模型的三类参数：s.t.m4445线性规划的向量和矩阵的表达形式记向量和矩阵第1节线性规划的数学模型及相关概念一

现实中的线性规划问题及模型则线性规划问题可以表示为：max（min)z=CX

s.t.AX≤(=≥)bX≥014线性规划的向量和矩阵的表达形式记向量和矩阵第1节线性规4546二、线性规划的标准形式称以下线性规划的形式为标准形式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=CX

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

(M2):

第1节线性规划的数学模型及相关概念15二、线性规划的标准形式称以下线性规划的形式为标准形式ma4647非标准形LP问题的标准化

一、极小化目标函数的问题

minz=CX令z′=

－

z

maxz′=

－

CX

例：minz=3x1＋

2x2

maxz′=

－

3x1－

2x2

二、约束条件不是等式的问题

⑴bi<0两边同时乘以

-1

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

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

三、变量符号无限制或小于等于零的问题若xk为自由变量,

令xk

=xk′－

xk〞且xk′,xk〞≥0

若xk

≤0,

令xk

=－

xk′,则xk′≥0

第1节线性规划的数学模型及相关概念二、线性规划的标准形式xzzzminz=-zzmaxx*16非标准形LP问题的标准化第1节线性规划的数学模型及相关4748minz=2x1－

3x2＋x3

x1－

x2

＋2

x3

≤32x1＋

3x2

－

x3≥5x1

＋x2

＋

x3=4

x1

≥0,

x2

无约束，

x3

≤

0s.t.第1节线性规划的数学模型及相关概念例2-5将下述LP问题化成标准形式解：令z′=-z

，x2=

x2′－

x2〞，x3′=

-x3

maxz′=

－

2

x1＋3

x2′-

3x2〞＋x3′

x1－

x2′+

x2〞－2

x3′+

x4

=3

2x1+3x2′－

3x2〞+

x3′

－

x5

=5

x1

+

x2′

－

x2〞

－

x3′

=4

x1

,

x2′,

x2〞,

x3′,

x4

,

x5

≥0s.t.二、线性规划的标准形式17minz=2x1－3x2＋x3s.t.第48第1章线性规划的数学模型及相关概念49minz=

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练习：将下述LP问题化成标准形二、线性规划的标准形式第1章线性规划的数学模型及相关概念18minz=x149第1章线性规划的数学模型及相关概念50令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章线性规划的数学模型及相关概念19令x2=x2′50第1节线性规划的基本性质51只有两个变量的线性规划问题

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节线性规划的基本性质20只有两个变量的线性规划问题X51第1节线性规划的基本性质52几点说明实际运用时还须注意以下几点:(1)若函数约束原型就是等式,则其代表的区域仅为一直线,而且问题的整个可行域R(若存在的话)也必然在此直线上。(2)在画目标函数等值线时只须画两条就能确定其法线方向,为此,

只须赋给z

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

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

通过解方程组得出最优点坐标值三、线性规划的几何解释第1节线性规划的基本性质21几点说明三、线性规划的几何解释52第1节线性规划的基本性质53几种可能结果一、唯一解

如例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节线性规划的基本性质22几种可能结果s.t.maxz53第1节线性规划的基本性质54x1x2z*三、无界解3694812x1x2R2R1∩R2=Ø四、无可行解+∞R1三、线性规划的几何解释第1节线性规划的基本性质23x1x2z*三、无界解3654第1节线性规划的基本性质55相关定义定义2-1可行域在n维空间中，满足条件ai1x1+ai2x2+…+ainxn

≤(=≥)

bi且xj≥0的点集。O(0,0)x1x2RD(0,6)C(4,6)B(8,3)A(8,0)三、线性规划的几何解释第1节线性规划的基本性质24相关定义O(0,0)x1x2R55第1节线性规划的基本性质56定义2-2凸集三、线性规划的几何解释设S是n维空间中的一个点集。若对任意n维向量X1S，X2S，且X1X2，以及任意实数（01），有 X=X1+(1-)X2S则称S为n维空间中的一个凸集（ConvexSet）。点X称为点X1和X2的凸组合。

凸集：非凸集：第1节线性规划的基本性质25定义2-2凸集三、线性规划的56第1节线性规划的基本性质57定义2-3凸集的极点三、线性规划的几何解释设