物流运筹学 课件 第2章 线性规划

线性规划LinearProgramming

线性规划（LinearProgramming，简称LP）运筹学的一个重要分支，是运筹学中研究较早、发展较快、理论上较成熟和应用上极为广泛的一个分支。

1947年G.B.Dantying提出了一般线性规划问题求解的方法——单纯形法之后，线性规划的理论与应用都得到了极大的发展。

60年来，随着计算机的发展，线性规划已广泛应用于工业、农业、商业、交通运输、经济管理和国防等各个领域，成为现代化管理的有力工具之一。§1线性规划问题及其数学模型e.g.1

资源的合理利用问题问：如何安排生产计划，使得既能充分利用现有资源又使总利润最大？

表1

产品资源 甲乙库存量

A 1 3 60 B 1 1 40

单件利润

15 25

某工厂在下一个生产周期内生产甲、乙两种产品，要消耗A、B两种资源，已知每件产品对这两种资源的消耗，这两种资源的现有数量和每件产品可获得的利润如表1。第一章线性规划及单纯形法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

解：

设x1，x2

为下一个生产周期产品甲和乙的产量；

约束条件：Subjecttox1+3x2≤60x1

+x2≤40x1，x2≥0目标函数：z=15x1+25x2

表1

产品资源 甲乙库存量

A 1 3 60 B 1 1 40

单件利润

15 25

决策变量§1线性规划问题及其数学模型e.g.2

营养问题

假定在市场上可买到B1,B2,…Bnn

种食品，第

i

种食品的单价是ci,另外有m

种营养A1,A2,…Am。设

Bj内含有

Ai

种营养数量为aij

(i=1~m,j=1~n)，又知人们每天对Ai

营养的最少需要量为bi。见表2：

表2

食品最少营养 B1B2…Bn

需要量

A1 a11 a12…a1n b1A2 a21 a22…a2n b2………………Amam1am2…amn

bm

单价

c1c2…cn

试在满足营养要求的前提下，确定食品的购买量，使食品的总价格最低。第一章线性规划及单纯形法

表2

食品最少营养 B1B2…Bn

需要量

A1 a11 a12…a1n b1A2 a21 a22…a2n b2………………Amam1am2…amn

bm

单价

c1c2…cn

解：

设xj

为购买食品

Bj

的数量(j=1,2,…,n)（i=1,2,…,m）xj≥0（j=1,2,…,n）§1线性规划问题及其数学模型三个基本要素：Note：1、善于抓住关键因素，忽略对系统影响不大的因素；2、可以把一个大系统合理地分解成n

个子系统处理。1、决策变量xj≥0

2、约束条件——一组决策变量的线性等式或不等式3、目标函数——决策变量的线性函数第一章线性规划及单纯形法max（min）z=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn≤（或=，≥）b1

a21x1+a22x2+…+a2nxn≤（或=，≥）b2

……am1x1+am2x2+…+amnxn

≤（或=，≥）bm

xj

≥0（j=1,2,…,n） 其中aij、bi、cj（i=1,2,…,m；j=1,2,…,n）为已知常数

线性规划问题的一般形式：§1线性规划问题及其数学模型线性规划问题的标准形式：maxz=c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2

……am1x1+am2x2+…+amnxn

=bm

xj

≥0（j=1,2,…,n）

bi≥0（i=1,2,…,m） 特点：1、目标函数为极大化；2、除决策变量的非负约束外，所有的约束条件都是等式，且右端常数均为非负；3、所有决策变量均非负。

第一章线性规划及单纯形法如何转化为标准形式？1、目标函数为求极小值，即为：。

因为求minz等价于求max(-z)，令z’=-z，即化为：

2、约束条件为不等式，xn+1≥0松弛变量如何处理？§1线性规划问题及其数学模型

３、右端项bi<0时，只需将等式两端同乘（-1）则右端项必大于零

4、决策变量无非负约束

设xj

没有非负约束，若xj≤0，可令xj=-xj’

，则xj’≥0；

又若

xj

为自由变量，即

xj

可为任意实数，可令xj

=xj’-xj’’，且xj’,xj’’≥0第一章线性规划及单纯形法e.g.3试将LP

问题minz=-x1+2x2-3x3

s.t.x1+x2+x3

≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0

化为标准形式。解：令x3=x4-x5

其中x4、x5

≥0；对第一个约束条件加上松弛变量x6

；对第二个约束条件减去松弛变量x7

；对第三个约束条件两边乘以“-1”；令z’=-z

把求minz

改为求maxz’maxz’=x1-2x2+3x4-3x5

s.t.x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0

§1线性规划问题及其数学模型LP的几种表示形式：§2线性规划问题的图解法定义1在LP问题中，凡满足约束条件(2)、(3)的解x=(x1,x2,…,xn)T

称为LP问题的可行解，所有可行解的集合称为可行解集（或可行域）。记作D={x|Ax=b,x≥0}。定义2

设LP问题的可行域为D，若存在x*∈D，使得对任意的x∈D

都有cx*≥cx，则称x*为LP问题的最优解，相应的目标函数值称为最优值，记作z*=cx*。§2线性规划问题的图解法maxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

(40,0)(0,0)BC(30,10)O(0,20)AL1L2Z=250目标函数变形：x2=-3/5

x1+z/25x2x1最优解：

x1=30x2=10最优值：zmax=700B点是使z达到最大的唯一可行点第一章线性规划及单纯形法LP问题图解法的基本步骤：1、在平面上建立直角坐标系；2、图示约束条件，确定可行域和顶点坐标；3、图示目标函数（等值线）和移动方向；4、寻找最优解。§2线性规划问题的图解法maxz=3x1+5.7x2

s.t.x1+1.9x2≥3.8

x1-1.9x2≤3.8x1+1.9x2≤11.4

x1-1.9x2≥-3.8

x1，x2≥0x1x2ox1-1.9x2=3.8x1+1.9x2=3.8x1+1.9x2=11.4（7.6,2）D0=3x1

+5.7x2

maxZ

minZ（3.8,4）34.2=3x1

+5.7x2

可行域x1-1.9x2=-3.8(0,2)(3.8,0)

绿色线段上的所有点都是最优解,即有无穷多最优解。Zman=34.2第一章线性规划及单纯形法maxz=2x1+2x2s.t.2x1–x2≥2-x1+4x2≤4

x1，x2≥0OA(１,0)x1x2Note:可行域为无界区域，目标函数值可无限增大，即解无界。称为无最优解。可行域为无界区域一定无最优解吗？无可行解

指找不到一组变量能满足线性规划的所有约束条件的情况，也就是线性规划问题不存在可行解，或者说可行域是空集。例如线性规划问题：§2线性规划问题的图解法由以上两例分析可得如下重要结论：1、LP问题从解的角度可分为：⑴有可行解⑵无可行解有唯一最优解b.有无穷多最优解C.无最优解2、LP问题若有最优解，必在可行域的某个顶点上取到；若有两个顶点上同时取到，则这两点的连线上任一点都是最优解。§2线性规划问题的图解法图解法优点：直观、易掌握。有助于了解解的结构。图解法缺点：只能解决低维问题，对高维无能为力。例某工厂经市场调研，决定生产甲、乙两种产品，其单台利润分别为60元和30元，两种产品共用一种钢材、一台设备，其资源及获利情况如下：甲乙现有资源钢材消耗定额（公斤/台）24600公斤台时消耗定额（小时/台）31400小时配件（件/台）20250件利润（元）6030求利润最大的产品结构决策。作业练习②确定目标函数及约束条件——建立数学模型目标函数：③将不等式变为等式并在x1－x2坐标图中作出直线④最优点在凸边形的顶点，代入（1）式可得maxP解：①设变量：设甲生产x1台，乙生产x2台，可得最大利润约束条件：05050100100150150200250300350200250300350400x1x2A(0,150)B(100,100)C(125,25)D(125,0)(4)基、基向量、基变量⊙设r(A)=m,并且B是A的m阶非奇异的子矩阵（det(B)

0),则称矩阵B为线性规划问题的一个基。⊙矩阵B=（P1，P2….Pm)，其列向量Pj称为对应基B的基向量。⊙与基向量Pj

相对应的变量xj就称为基变量，其余的就称为非基变量。MaxS=CX（3-6）

s.t.AX=b（3-7）

X

0（3-8）基解.基可行解.可行基⊙对于某一特定的基B，非基变量取0值的解，称为基解。⊙满足非负约束条件的基础解，称为基可行解。⊙与基可行解对应的基，称为可行基。为了理解基解.基可行解.最优解的概念，用下列例子说明：例：maxS=2x1+3x2s.t.-2x1+3x2

63x1-2x2

6x1+x2

4x1,x2

0x243211234x1O-1-1-2-2-3-3-2x1+3x2=63x1-2

x2=6x1+x2=4AQ1Q2Q3Q4BmaxS=2x1+3x2s.t.-2x1+3x2

63x1-2x2

6x1+x2

4x1,x2

0x243211234x1O-1-1-2-2-3-3ABx243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4BmaxS=2x1+3x2s.t.-2x1+3x2

63x1-2x2

6x1+x2

4x1,x2

0满足约束条件

-2x1+3x2

63x1-2

x2

6x1+x2

4

与坐标系

x1,x2=0的交点（O，A，B，Q1，Q2，Q3，Q4）都是代表基解。注意：点（4，0）（0，4）不满足约束条件满足约束条件

-2x1+3x2

63x1-2

x2

6x1+x2

4

且满足

x1,x2

0的交点（O，Q1，Q2，Q3，Q4）都是代表基可行解。注意：点A，B不满足x1,x2

0点（O，Q1，Q2，Q3，Q4）刚好是可行域的顶点。x243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4B可行域x243211234x1O-1-1-2-2-3-3-2x1+3x2

63x1-2

x2

6x1+x2

4AQ1Q2Q3Q4B可行域本问题解的情况：基解：点（O，A，B，Q1，Q2，Q3，Q4）可行解：由点（O，Q1，Q2，Q3，Q4）围成的区域。基可行解：点（O，Q1，Q2，Q3，Q4）最优解：

Q3解的集合：非可行解可行解解的集合：基解解的集合：可行解基解基可行解解的集合：可行解基解基最优解基可行解线性规划（2）-单纯形方法单纯形方法基本思路：从可行域中某个基可行解（一个顶点）开始（称为初始基可行解）。如可能，从可行域中求出具有更优目标函数值的另一个基可行解（另一个顶点），以改进初始解。继续寻找更优的基可行解，进一步改进目标函数值。当某一个基础可行解不能再改善时，该解就是最优解。

由于军事上的需要，担任美国空军审计官的数学顾问旦茨基博士，根据在第二次世界大战中实际规划的经历，从1946年起就开始寻找一种方法，想用它较快地计算出包括进度、训练及后勤供应在内的规划问题。研究先从建立数学模型着手。在研究中，得到了投入—产出模型的启发，并在其他数学家的支持下，提出了解决线性规划问题极其有效的单纯形方法。单纯形法的由来

旦茨基教授在一次演说中，形象而风趣地说明了单纯形解法的奇效：设给70个人分配70项任务，每人一项。如果每人完成各项任务所需要付出的代价（时间、工资）都知道，要寻求代价最小的方案。所有的可行方案共有70！种。70！比还要大。如果用穷举法，逐个来比较的话，基本是不可能的。而用单纯形法软件，几秒钟就可以给出答案。

不仅如此，还能预测当方案中某因素发生变化，对决策目标的影响。神奇的单纯形法返回目录

线性规划问题的可行解有无穷多个，与某一凸集上的无穷多个点一一对应。要从无穷多个可行解中寻找最优解，几乎不可能。可以证明，最优解必定能取在凸集的顶点（极点、基本可行解）上，而极点的个数是有限的。当然，这个“有限”，数字往往相当可观，如前面的70！，要逐个比较的话，也不现实。而单纯形解法，用跨跃的方式，高速地优化基本可行解，迅速达到最优。单纯形法—跨跃式地寻求最优解优maxSS=ooABCDE凸集概念：

设D是n维线性空间Rn的一个点集，若D中的任意两点x(1),x(2)的连线上的一切点x仍在D中，则称D为凸集。凸集（非凸集）

开始，用单纯形表进行换基迭代。后来的改进单纯形法，大大减少了计算量。为利用计算机创造了条件。最初使用手摇和电动台式计算器，不能完成特大量的计算。由于线性规划应用广泛，大到整个国民经济计划，小到一个车间的生产安排，因此受到重视。解线性规划的能力迅速提高。1951年只能解约束条件为十几个方程的问题。现在，能解上万个方程的问题。且解题速度大大加快。专家们已经用单纯形解法开发出了计算效率极高应用软件。运用这个软件，输入数据，立即就可以打印出结果。

单纯形解法应用的发展过程例：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？解：数学模型

maxS=6x1+4x2s.t.2x1+3x2

1004x1+2x2

120x1,x2

0引进松弛变量x3,x4

0数学模型标准形式：

maxS=6x1+4x2s.t.2x1+3x2+x3=1004x1+2x2+x4=120x1,x2,

x3,x4

0

A=（P1，P2，P3，P4）

=23104201

X=（x1,x2,x3,x4)B=(P3，P4

）=1001P3，P4线性无关，x3和x4是基变量，x1、x2是非基变量。

用非基变量表示的方程：

x3=100-2x1-3x2x4=120-4x1-2x2(I)S=6x1+4x2令非基变量（x1,

x2）t=（0，0）t

得基础可行解：

x(1)=(0,0,100,120)t

S1=0

经济含义：不生产产品甲乙，利润为零。分析：S=

6x1+

4x2（分别增加单位产品甲、乙，目标函数分别增加6、4，即利润分别增加6百元、4百元。）

增加单位产品对目标函数的贡献，这就是检验数的概念。

增加单位产品甲（x1）比乙对目标函数的贡献大（检验数最大），把非基变量x1换成基变量，称x1为进基变量，而把基变量x4换成非基变量，称x4为出基变量。确定了进基变量x1

，出基变量x4

以后，得到新的系统：

x3=40-2x2+（1/2）x4x1=30-（1/2）x2-（1/4）x4(II)S=180+x2-（3/2）x4令新的非基变量（

x2，x4）=（0，0）t得到新的基础可行解：x(2)=(30,0,40,0)t

S2=180经济含义：生产甲产品30个，获得利润18000元。

这个方案比前方案，但是否是最优？分析：S=180+x2-（3/2）x4非基变量x2系数仍为正数，确定x2为进基变量。在保证常数项非负的情况下，确定x3为出基变量。得到新的系统：

x1=20+（1/4）x3-（3/8）x4x2=20-（1/2）x3+（1/4）x4(III)S=200-（1/2）x3-（5/4）x4

令新的非基变量（x3,x4）t=（0,0）t得到新的基础可行解：x(3)=(20,20,0,0)t

S3=200经济含义：分别生产甲乙产品20个，可获得利润20000元。分析：S=200-（1/2）x3-（5/4）x4目标函数中的非基变量的系数无正数，S3=200是最优值，x(3)=(20,20,0,0)t是最优解。该企业分别生产甲乙产品20个，可获得最大利润20000元。X(3)=(20,20,0,0)t相当于Q2(20,20)X(1)=(0,0,100,120)t相当于O(0,0)X(1)=(0,0,100,120)t相当于O(0,0)X(2)=(30,0,40,0)t相当于Q1(30,0)X(2)=(30,0,40,0)t相当于Q1(30,0)X(3)=(20,20,0,0)t相当于Q2(20,20)举例:求解下列线性规划问题maxz＝1.5x1+2.4x2+0x3+0x4+0x5S.t.x1+x2+x3=1003x1+2x2+x4=1902x1+3x2+x5=240xj≥0(j=1,2,3…5)解：约束方程的系数矩阵为：1

1

100

A=(P1，P2，P3

，P4

，P5

）＝3

2

010

23

001初始可行基为：100B＝（P3，P4

，P5

）＝010001用非基变量表达基变量：

x3=100

－x1－1x2

x4=190

－3x1－2x2

x5=240

－2x1－3x2

将上式代入目标函数得：

z=0+１.５x1+2.4x2令非基变量为零，即令x1＝0，x2＝0得一个基可行解：x（0）＝（0,0,100,190,240)此时得z＝0非基变量的系数都是正数，因此将非基变量变换成基变量，目标函数的值就可能变大。取x2为入基变量（一般选择正价值系数最大的非基变量为入基变量，而2.4>1.5）于是还要确定基变量x3，x4，x5中的一个换出来成为非基变量。下面来确定换出变量：当x1=0时（先固定x1是两个非基变量中的一个）,x3=100

－1x2≥0x4=190

－2x2≥0x5=240

－3x2≥0要让x3，x4，x5非负，且有一个为0，只有选择x2≤80时，才能使x3,x4x5同时非负。(此时x3≥20>0，x4≥30>0，x5≥0)因此只有当x2=min(100/1,190/2,240/3)=80时,才能使x3,x4x5非负的同时，有一个原来的基变量x5取值为0，从而可以换出来成为非基变量。其中x3=20

>0，

x4=30

>0，

X5=0，取X5为出基变量（所谓的最小比值规则）x2≤100x2≤

95x2≤80x2≤80用非基变量表达基变量：

x3+x2=100-x1x3=20

-1/3x1+1/3x5

x4+2x2=190-3x1x4=30-5/3x1+2/3x5

3x2=240-2x1-

x5x2=80

-2／3x1-1/3x5

将上式代入目标函数得：z=192-0.1x1-0.8x5令非基变量为零，即x1＝0，x5＝0得一个基本可行解：x（1）＝（0,80,20,30,0),z=192由于非基变量的价值系数都是负数，而x1≥0，x5≥0，因此当x1＝0，x5＝0时，z取得最大值192。所以最优解

X*=x（1）＝（0,80,20,30,0),目标函数值z*=192

c

c1c2cmcm+1cm+2cncBxBx1x2xmxm+1xm+2xnbc1c2cmx1x2xm

100a’1m+1a’1m+2a’1n

010a’2m+1a’2m+2a’2n

001a’mm+1a’mm+2a’mnb’1b’2b’m检验数

0

00-z(0)用单纯形表求解问题例、用单纯形表求解LP问题解：化标准型表1：列初始单纯形表（单位矩阵对应的变量为基变量）

21000

01505100

0

24620100511001

21000

—24/65/1正检验数中最大者对应的列为主列主元化为1主列单位向量换出换入最小的值对应的行为主行表2：换基（初等行变换，主列化为单位向量，主元为1）

21000

01505100

2

412/601/600104/60-1/61

01/30-1/30

15/524/26/4

0*52*2/6+0*4/61-2/3=主元检验数>0确定主列

最小确定主列表3：换基

（初等行变换，主列化为单位向量，主元为1）

21000

015/20015/4-15/2

2

7/21001/4-1/213/2010-1/43/2000-1/4-1/2

最优解为X=(7/2,3/2,15/2,0,0)目标函数值Z=8.5

2*7/21*3/2+0*15/28.5检验数<=0例2、试利用单纯形表求例1中的最优解解：

得初始的单纯形表：初始基本可行解，Z=-1，122108x4-1-130400341017x51x1x2x3x4x5bXBCBΘ523-11C

换入变量，换出变量，２为主元进行旋转变换基本可行解，Z=15，1/2

1

1

1/2

04x33151-40-205/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ523-11C122108x4-1-130400341017x51x1x2x3x4x5bXBCBΘ523-11C8/27/1

最优解

最优值

换入变量，换出变量，５/２为主元进行旋转变换4/1/21/2

1

1

1/2

04x33151-40-203/5/25/230-1/213x51

x1

x2

x3

x4

x5bXBCBΘ523-11C02/513/5-1/517/5x3381/5

0-26/50-9/5-2/516/50-1/52/56/5x15x1x2x3x4x5bXBCBΘ

523-11Cmaxz=15x1+25x2s.t.x1+3x2≤60

x1

+x2≤40x1，x2≥0

maxz=15x1+25x2+0x3+0x4s.t.x1+3x2+x3=60

x1

+x2++x4=40