《运筹学》课件 第1章 线形规划

第一章线性规划第1章内容提要1.1线性规划问题及其数学模型1.2图解法1.3线形规划的标准形式1.4线形规划解的概念1.5线形规划的基本理论线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian(哈奇扬

)提出“椭球法”线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar(卡马卡)提出“投影梯度法”

线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的Khachian提出“椭球法”1984年印度的Karmarkar提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。线性规划（概论）线性规划（LinearProgramming)创始人：1947年美国人G.B.丹齐克（Dantzing）1951年提出单纯形算法（Simpler）1963年Dantzing写成“LinearProgrammingandExtension”1979年苏联的哈奇扬提出“椭球法”1984年印度的卡马卡提出“投影梯度法”线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论，是线性代数的应用和发展。1.1线性规划问题及其数学模型LP:LinearProgramming1.1.1问题的提出1.1.2线性规划问题的标准型1.1.3线性规划问题解的概念1.1.1问题的提出生产经营中经常提出的一个问题是：如何合理地利用人、财、物，以降低成本，获取效益提问

建模

求解

检验

控制

实施运筹学的工作步骤生产计划问题如何合理使用有限的人力，物力和资金，使得收到最好的经济效益。如何合理使用有限的人力，物力和资金，以达到最经济的方式，完成生产计划的要求。1-1线性规划基本概念

一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。

——实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（max或min）。

另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。线性规划研究的主要问题例1:某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗如下表所示：III合计设备128台时原材料A4016千克原材料B0412千克该工厂每生产一件I

可获得2元，每生产一件产品II可获得3元。问应如何安排计划使该工厂获得最多？例1解这是一个求极大值问题，可用数学模型来描述。设计划期内产品的产量为：I

x1IIx2则得到利润z为:z=2x1+3x2约束条件台时约束：x1+2x2

8原材料约束4x1

164x2

12问题为求x1、

x2的值，使得利润z

最大例1数学模型归结为：目标函数Max

z=2x1+3x2约束条件x1+2x2

84x1

16s.t.4x2

12x1,x2

0s.t.Subjectto受…约束例2某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。

8221丁7141丙6102乙5321甲单位成本（元／吨）CBA药物原料解：1.决策变量：设四种原料的使用量分别为：x1、x2、x3

、x42.目标函数：设总成本为z，则有：

minz=5x1+6x2+7x3+8x43.约束条件：

x1+2x2+x3+x4≥1602x1+4x3+2x4

＝2003x1

＋x2+x3+2x4

≤180

x1、x2

、x3

、x4≥0例题3：人员安排问题(自己动手做一做)医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：

序号时段最少人数安排人数106—1060X1210—1470X2314—1860X3418—2250X4522—0220X5602—0630x6例题3建模目标函数：minZ=x1+x2+x3+x4+x5+x6约束条件：

x1+x2≥70x2+x3≥60x3+x4≥50x4+x5≥20x5+x6≥30X6+X1≥60非负性约束：xj≥0,j=1,2,…6船只种类船只数拖轮30A型驳船34B型驳船52航线号合同货运量12002400航线号船队类型编队形式货运成本（千元／队）货运量（千吨）拖轮A型驳船B型驳船1112—362521—4362023224724041—42720问：应如何编队，才能既完成合同任务，又使总货运成本为最小？课堂练习：某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：解：设：xj为第j号类型船队的队数（j=1，2，3，4），z为总货运成本则：minz=36x1+36x2+72x3+27x4

x1+x2+2x3+x4≤302x1+2x3≤344x2+4x3+4x4≤5225x1+20x2

＝20040x3+20x4＝400xj≥0j=1,2,3,4其他典型问题：合理下料问题其他典型问题：合理下料问题运输问题其他典型问题：合理下料问题运输问题生产的组织与计划问题其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题其他典型问题：合理下料问题运输问题生产的组织与计划问题投资证券组合问题分派问题生产工艺优化问题线性规划模型特点决策变量：向量(x1…

xn)T决策人要考虑和控制的因素非负目标函数：有一个目标函数可以表示为这组变量的线形函数约束条件：线性等式或不等式目标函数：Z=ƒ(x1

…

xn)线性式，求Z极大或极小线形规划的一般数学模型1.决策变量：X=(x1,x2,…..,xn)T2.目标函数：max(minz)=c1

x1+c2

x2+…….+cnxn3.约束条件：

a11x1+a12

x2+……..+a1n

xn≤(=≥)b1

a21x1+a22

x2+……..+a2n

xn≤(=≥)b2

…………am1x1+am2

x2+……..+amnxn≤(=≥)bmx1,x2,……xn≥0模型特点1都用一组决策变量X=(x1,x2,…,xn)T表示某一方案，且决策变量取值非负；———

满足以上三个条件的数学模型称为线性规划2都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数；3都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等式来表示。其它形式其中：①求和形式②矩阵形式决策变量常数项系数矩阵价值系数其中：线性规划图解法一、解题步骤4将最优解代入目标函数，求出最优值。1在直角平面坐标系中画出所有的约束等式，并找出所有约束条件的公共部分，称为可行域，可行域中的点称为可行解。2标出目标函数值增加的方向。3若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最后相交的点，该点就是最优解。图解法最简单、直观的方法但只适用有两个决策变量的情况非负约束Thenon-negativityconstraintsx2x1可行域

满足线性规划模型所有约束条件的所有点（可行解）的集合——可行域

可行域的性质：(1)、可行域为凸多边形。(2)、若有最优解，定可在可行域的极点得到。X(1)X(2)凸多边形凹多边形X(1)X(2)012345678可行域x2非可行域x1+2x2£84x2£

1243214x1£16x1用图解法解例1最优解点x1=4，x2

=2例1数学模型归结为：目标函数Max

z=2x1+3x2约束条件x1+2x2

84x1

16s.t.4x2

12x1,x2

0z=2x1+3x2即x2=-2x1/3+z/3z取不同值时是一束斜率为-2/3平行线，z最大值出现在最高的一条线上。某玩具公司生产S和Z两种塑料玩具其所用特殊塑料每周可用量为1000磅每周生产时间是40小时市场需求是总产量不能超过700件，其中S产量不能超过Z产量350件生产每件S产品需2磅塑料和3分钟时间生产每件Z产品需1磅塑料和4分钟时间生产计划要求尽可能地生产利润更高的S产品（每件利润8元，而Z每件利润5元）问如何安排两种产品的生产，使获利最大？例2玩具公司生产计划

Maxz=8x1+5x2

subjectto 2x1+1x2≤1000(1)塑料约束

3x1+4x2≤2400(2)生产时间约束（分钟）

x1+x2≤700(3)总产量约束

x1-x2≤350(4)产量差约束

xj>=0,j=1,2(5)例2的线性规划模型为1000500可行域x2非可行域生产时间约束(3)3x1+4x2£

2400总产量约束(2)x1+x2£

700(多余的)500700塑料约束(1)2x1+x2£1000x1700图解法1000500可行域x2非可行域生产时间约束(3)

3x1+4x2£2400总产量约束(2)

x1+x2£700(多余的)500700产量差约束(4)

x1-x2£

350塑料约束(1)2x1+x2£1000x1700图解法三种可能的点域内点边界点顶点用图解法求最优解寻求最优解从任意一个z值开始，如

z=2000如可能，增加z值直到不能再增加最大利润Z*=43605007001000500x2x1Maxz=8x1+5x2即x2=-8x1/5+z/5斜率-8/5的直线例2结果总结

x1

=320

x2=360

z*=4360约束(1)、(2)全部取等号

2x1+x2≤1000(1)3x1+4x2≤2400(2)x1+x2

只有680(而不是700)。x2-x1

只有

40。012345678910可行域x2非可行域直线5x1+10x2=50直线x1+x2=

154321直线x2=

4x1例3最优解点x1=2,x2

=4目标函数Max

z=

x1+3x2约束条件5x1+10x2

50

x1

+x2

1

x2

4x1,x2

0z=

x1+3x2即x2=-x1/3+z/3z取不同值时是一束斜率为-1/3平行线，z最大值出现在最高的一条线上。如果线性规划问题有最优解，可行域的一个顶点肯定是最优解顶点和最优解如果存在多个最优解，目标函数必须与某一个约束条件平行。多个最优解在此线段上的任一点均为最优解。无界解和无可行解若可行域无界，目标函数值可以增大到无穷大，则为无界解。若可行域为空集，即无可行解，也不存在最优解。无界解

可行域Thefeasibleregion

Maximize目标函数值最大化

112323无可行解没有点能同时处在直线1上方和直线2、3的下方。总结

唯一解无穷多解无有限最优解无可行解有解无解可行域为封闭的有界区域：唯一、多个最优解可行域为非封闭的无界区域：唯一、多个最优解对于目标函数无界：无最优解可行域为空集：没有可行解，更无最优解线性规划的可行域及最优解的可能结果(a)可行域封闭，唯一最优解(b)可行域封闭，多个最优解(d)可行域开放，多个最优解(e)可行域开放，目标函数无界(f)可行域为空集(c)可行域开放，唯一最优解线性规划的可行域及最优解的可能结果图示:线性规划问题的标准型Max

z=

c1x1+c2x2+…+cnxna11x1+a12x2+…+

a1nxn=b1a21x1+a22x2+…+

a2nxn=b2

……am1x1+am2x2+…+

amnxn=bm

x1,x2…

,xn

0

并规定,右端项

bi

0s.t.和式标准型的矩阵表示Max

z=CXAX=bX

0C价值向量b资源向量X决策变量向量A约束条件的m

n阶系数矩阵,一般m<n标准型的特征目标函数极大化约束条件为等式决策变量非负化标准型若目标函数为最小化,即Min

z=CX,可令,z‘=-z得到Max

z‘=-CX,就成目标函数最大化了。若约束方程为不等式:

在不等式号左端加非负松驰变量在不等式号左端减非负剩余变量若存在取值无约束的变量xk，可令xk=

x’k-

x”k

，其中x’k,

x”k

0

。(1)、约束条件

X1+2X2+X3=303X1+2X2+X4=602X2+

+X5=24

X1,

…,X50

松弛变量

例1maxZ=40X1+50X2+0·X3+0·X4+0·X54X1+6X2+X3+2X4-X5=12X1+X2+7X3+5X4-X6=142X2+X3+3X4-X7=8

X1,

…,X70

剩余变量

例2

minZ=2X1+5X2+6X3+8X4(2)、变量3X1'-3X1"+2X28X1'

-X1"-4X2

14X1',X1",X201、3X1+2X28X1-4X2

14X20令X1=X1'-X1"X1'

+X211X1'

16X1',X202、X1+X25-6

X110X20-6+6X1+6

10+6

令X1'

=X1+6

0

X1'

16例：将minZ=-X1+2X2-3X3X1+X2+X37X1-X2+X32X1，X20，X3无限制化为标准型解：①令X3=X4-

X5②加松弛变量X6③加剩余变量X7

④令Z'=-ZmaxZ'=X1-2X2+3X4-3X5X1+X2+X4-X5+X6=7X1-X2+X4-X5-X7=2X1,

X2,

X4,…,X70例：将以下线性规划问题转化为标准形式

Minf=-3x1

+5x2+8x3

-7x4s.t.2x1

-3x2+5x3+6x4

≤284x1

+2x2+3x3-9x4

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

x1,x3,x4

≥0解：首先，将目标函数转换成极大化：令

z=-f=3x1–5x2–8x3+7x4

；其次考虑约束，有3个不等式约束，引进松弛变量x5,剩余变量x6,x7

≥0；由于x2无非负限制，可令x2=x2’-x2”,其中 x2’≥0，x2”≥0；由于第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

非标准型转化举例之一maxZ=70X1+120X29X1+4X2≤3604X1+5X2

≤2003X1+10X2

≤300

X1≥0X2≥0

maxZ=70X1+120X29X1+4X2+X3=3604X1+5X2+X4=2003X1+10X2+X5=300Xj≥0j=1,2,…,5非标准型转化举例之二minZ=x1+2x2-3x3

x1+x2+x3

≤9-x1-2x2+x3≥23x1+x2-3x3=5x1≤0x2≥0x3无约束

maxZ’=x’1－2x2+3(x’3－x”3)－x’1+x2+x’3－x”3+x4=9x’1－2x2+x’3

－x”3-x5=2－3x’1+x2－3(x’3

－x”3)=5x’1≥0x2≥0x’3≥0x”3≥0x4≥0x5≥0练习

minZ=

x1+2x2-3x3x1+2x2-x3≤52x1+3x2-x3≥6

-x1-x2+x3≥-2x1≥0,x3≤0S.t.

minZ=

x1+2x2+3x3′x1+2x2+x3′≤52x1+3x2+x3′≥6

-x1-x2-x3′≥-2x1≥0,x3′≥0

标准化1解答过程标准化2minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′≤52x1+3(x2′-x2〃)

+x3′≥6

-x1-(x2′-x2〃)

-x3′≥-2x1,

x2′,x2〃

,x3′≥0

标准化3minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′≤52x1+3(x2′-x2〃)+x3′≥6

x1+(x2′-x2〃

)

+x3

′≤2x1,

x2′,x2〃,x3′≥0标准化4minZ=

x1+2(x2′-x2〃)

+3x3′

x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′≥6

x1+(x2′-x2〃)

+x3′≤2x1,

x2′,x2〃,x3′,x4≥0标准化5minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′+x4=5

2x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

+x3′≤2x1,

x2′,x2〃,x3′,x4,x5≥0标准化6minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

+x3′+x6=2

x1,

x2′,x2〃,x3′,x4,x5,x6

≥0标准化7maxZ’=-x1-2(x2′-x2〃)

-3x3′+0x4+0x5+0x6

x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

+x3′+x6=2x1,

x2′,x2〃,x3′,x4,x5,x6≥0

线性规划解的概念可行解：满足约束条件(2)和(3)的解

X=(x1,x2,…,xn)T称为可行解最优解：使目标函数达到最大值的可行解基Basis设A是约束方程组的m

n维系数矩阵(Matrix)，其秩为mB是矩阵A中m

m

阶非奇异子矩阵则称B为线性规划问题的一个基即矩阵B由m个线性独立的列向量(vector)组成矩阵B是由m个线性独立的列向量组成。称Pj(j=1,2,…,m)是为基向量。与基向量Pj为相应的变量xj为基变量(basicvariables)，否则称为非基变量(

nonbasicvariables)。线性规划的基本概念线性规划的基矩阵、基变量、非基变量==目标函数约束条件行列式≠0基矩阵右边常数1可行解（feasiblesolution）：满足线性规划约束条件的解称为可行解。线性规划解的概念2最优解（optimalsolution）：使线性规划目标函数达到最优的可行解称为最优解。3基本解（basicsolution）：以线性规划约束等式的系数矩阵A中任意m行m列组成的m×m满秩子矩阵为基矩阵，与基矩阵相对应的变量称为基变量（basicvariable），其余变量称为非基变量，令非基变量为零，可求得基变量的值，这样求出的解称为基本解。

4基本可行解（basicfeasiblesolution）：满足非负约束的基本解称为基本可行解。若约束等式中有n个变量，m个约束，则基本解的个数≤基可行解(basicfeasiblesolution)：满足非负条件的基解(Basicsolution)。可行基(feasiblebasis)：对应于基可行解的基。非可行解可行解基解基可行解s.t.x1+3x2+x3£152x1+3x2-x3£18x1-x2+x3£3x1,x2,x3³0例化为标准形式stx1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1,x2,x3,x4,x5,x6³0基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=20x1+3x2+x3=152x1+3x2-x3=18x1-x2+x3=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x1、x2、x4，非基变量x3、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=18x1+3x2+x4=152x1+3x2=18x1-x2=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x1、x2、x5，非基变量x3、x4、x6基础解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0）是基础解，但不是可行解，不是一个极点。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1+3x2=152x1+3x2+x5=18x1-x2=3基变量x1、x2、x6，非基变量x3、x4、x5基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基础可行解，表示可行域的一个极点。目标函数值为：z=18x1+3x2=152x1+3x2=18x1-x2+x6=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x2、x3、x4，非基变量x1、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基础解，但不是可行解。3x2+x3+x4=153x2-x3=18-x2+x3=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=15x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3+x5=18-x2+x3=3基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，