线性规划与单纯形法详解演示文稿

线性规划与单纯形法详解演示文稿目前一页\总数一百零五页\编于八点（优选）线性规划与单纯形法目前二页\总数一百零五页\编于八点例1.1生产计划问题（资源利用问题）某家具厂生产桌子和椅子两种家具。

桌子售价50元/个，椅子销售价格30元/个。需要木工和油漆工两种工种。生产一个桌子需要木工4小时，油漆工2小时。生产一个椅子需要木工3小时，油漆工1小时。该厂每个月可用木工工时为120小时，油漆工工时为50小时。

问如何组织生产才能使每月的销售收入最大？1、问题的提出目前三页\总数一百零五页\编于八点是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。第1步-确定决策变量设——桌子的产量

——椅子的产量

——利润目前四页\总数一百零五页\编于八点第2步--定义目标函数决策变量

MaxZ=50x1+30x2目前五页\总数一百零五页\编于八点价值系数第2步--定义目标函数

MaxZ=50x1+30x2目前六页\总数一百零五页\编于八点第3步--表示约束条件4x1+3x2

120（木工工时限制）

2x1+x2

50（油漆工工时限制）

x1，x2≥0（变量取非负值限制）目前七页\总数一百零五页\编于八点

该计划的数学模型

maxZ=50x1+30x24x1+3x2

1202x1+x250

x1,x20s.t.线性函数线性等式线性不等式线性规划+目前八页\总数一百零五页\编于八点例1.2简化的环境保护问题

靠近某河流有两个化工厂(见下图)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。

目前九页\总数一百零五页\编于八点第一化工厂每天排放含有某种有害物质的工业污水2万立方米，第二化工厂每天排放这种工业污水1.4万立方米。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是1000元/万立方米。第二化工厂处理工业污水的成本是800元/万立方米。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小。目前十页\总数一百零五页\编于八点

建模型之前的分析和计算

设：第一化工厂每天处理工业污水量为x1万立方米，第二化工厂每天处理工业污水量为x2万立方米目前十一页\总数一百零五页\编于八点数学模型目前十二页\总数一百零五页\编于八点线性规模解决的问题给定一定数量的人力、物力、财力等资源，研究如何充分利用，以发挥其最大效果已给定计划任务，研究如何统筹安排，用最少的人力、物力、财力去完成目前十三页\总数一百零五页\编于八点线性规划数学模型三要素：

决策变量、目标函数、约束条件

每一个线性规划问题都有一组决策变量

(x1,x2,……,xn),这组决策变量的值就代表一个具体方案。

有使用各种资源的约束条件，用等式或不等式表示。

有一个要达到的目标，是决策变量的线性函数，实现最大化或最小化。2、线性规划问题的数学模型目前十四页\总数一百零五页\编于八点

一般形式线性规划模型的表示形式

矩阵形式

标准形式

将一般线性规划化成标准形

简写形式目前十五页\总数一百零五页\编于八点max(min)Z=c1x1+c2x2+…..+cnxna11x1+a12x2+….+a1nxn(=,)b1

a21x1+a22x2+….+a2nxn(=,)b2

….

am1x1+am2x2+….+amnxn(=,)bm

x1,

x2,….,xn0s.t.线性规划问题的一般形式目前十六页\总数一百零五页\编于八点

线性规划问题的简写形式目前十七页\总数一百零五页\编于八点

max

Z=CTX

s.t.AX=b

X

0C—价值向量b—资源向量X—决策变量向量线性规划的矩阵形式目前十八页\总数一百零五页\编于八点

a11

a12….a1nb1A=a21

a22….a2n

b

=

b2…….

am1

am2….amnbm

c1

x10

c2

x20C=X=0=……...

cn

xn0目前十九页\总数一百零五页\编于八点线性规划问题的标准形式max

Z=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+….+a1nxn

=b1

a21x1+a22x2+….+a2nxn=

b2

….

am1x1+am2x2+….+amnxn=

bm

x1,

x2,….,xn0其中：bi

0,i=1,2,….,m.目前二十页\总数一百零五页\编于八点四点要求:将一般线性规划化成标准型

求max

等式约束

bi0

xi0目前二十一页\总数一百零五页\编于八点(1)若目标函数是求最小值:

min

Z=CTX

令Z’=Z,则化成max

Z’=CTX注意:

因为min

Z=max(Z)

所以变换后的最优解不变，最优值变号。目前二十二页\总数一百零五页\编于八点(2)若约束条件是不等式1)若约束条件是“”不等式，则不等式左边“加上”非负的松驰变量；如：2X1+2X2≤12令X3=12-2X1-2X2

则有2X1+2X2+X3=12

2)若约束条件是“”不等式，则不等式左边“减去”非负的松驰变量。如：10X1+12X2≥18令X4=10X1+12X2-18则有10X1+12X2-X4=18

为了使添加松驰变量不影响原来的目标，添加松驰变量在目标函数中的系数为0。目前二十三页\总数一百零五页\编于八点(3)若约束条件右面的某一常数项bi<0,

这时只要在bi相对应的约束方程两边乘1。(4)若变量xj无非负限制引进两个非负变量xj’

xj”0

令xj=

xj’

xj”

（可正可负）任何形式的线性规划总可以化成标准型目前二十四页\总数一百零五页\编于八点例1.3将下列问题化成标准型:

min

Z=

x1+2x23x3

s.t.x1+x2+x37

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3无限制目前二十五页\总数一百零五页\编于八点例1.3将下列问题化成标准型:

min

Z=

x1+2x23x3

s.t.x1+x2+x37

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3无限制minx3

无限制目前二十六页\总数一百零五页\编于八点例1.3将下列问题化成标准型:

max

Z’=

x1

2x2+3x3

s.t.x1+x2+x37

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3无限制目前二十七页\总数一百零五页\编于八点例将下列问题化成标准型:

max

Z’=

x1

2x2+3x3+0x4

s.t.x1+x2+x3+x4=7

x1

x2+x32

3x1+x2+2x3=5

x10,x20,x3无限制，x4

0目前二十八页\总数一百零五页\编于八点例将下列问题化成标准型:

maxZ’=

x1

2x2+3x3+0x4+0x5

s.t.x1+x2+x3+x4=7

x1

x2+x3

x5=2

3x1+x2+2x3=5

x10,x20,x3无限制，x4

0，x5

0目前二十九页\总数一百零五页\编于八点max

Z’=

x1

2x2+3x3’

3x3’’+0x4+0x5

s.t.x1+x2+x3’

x3’’

+x4=7

x1

x2+x3’

x3’’

x5=2

3x1+x2+2x3’

2x3’’

=5

x10,x20,x3’0,

x3’’0，x4

0，x5

0令x3=

x3’

x3’’目前三十页\总数一百零五页\编于八点例将下列一般形式划为标准形式：目前三十一页\总数一百零五页\编于八点目前三十二页\总数一百零五页\编于八点标准型习题P55-2.2（1）划为标准形式目前三十三页\总数一百零五页\编于八点二、LP问题的图解法max

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

50

x1,x2

01.例目前三十四页\总数一百零五页\编于八点x240302010102030x1

由4x1+3x2120

x10,x20

围成的区域50

由2x1+x250

x10,x20

围成的区域目前三十五页\总数一百零五页\编于八点x240302010102030x1

由4x1+3x21202x1+x250

x10,x20

围成的区域

(可行域)50可行域满足约束条件的解称为可行解，全部可行解的集合称为可行域。目前三十六页\总数一百零五页\编于八点x240302010102030x1

该问题的可行域是由

Q1，Q2，Q3，Q4

作为顶点的凸多边形50可行域Q1(0,0)Q2(25,0)Q4(0,40)Q3(15,20)目前三十七页\总数一百零五页\编于八点x240302010102030x1

目标函数

Z=50x1+30x2

是一组平行线50可行域目前三十八页\总数一百零五页\编于八点x240302010102030x1

此组平行线沿其法线方向(50,30)右上方函数值Z

增加50可行域目前三十九页\总数一百零五页\编于八点x240302010102030x1当该直线移到Q3(15,20)点时，Z值达到最大：

max

Z=5015+3020=1350此时最优解X*=（15，20）50Q3(15,20)目前四十页\总数一百零五页\编于八点二个重要结论：可行域是一个凸多边形。最优解必定能在某一个顶点上取得。目前四十一页\总数一百零五页\编于八点2.LP问题的解

可行解：满足约束条件（包括非负条件）的一组变量值，称可行解。

可行域：可行解的全体。

最优解：使目标函数达到最大的可行解。

最优值：将最优解代入目标函数得到的值。目前四十二页\总数一百零五页\编于八点

可行域为空集无可行解

可行域非空，则有三种情况：(1)有唯一解(顶点)(2)有无穷多个解(两个顶点间的连线)(3)无最优解(无界解)无最优解目前四十三页\总数一百零五页\编于八点⑴⑵x1x2

无可行解目前四十四页\总数一百零五页\编于八点x240302010102030x1

当目标函数由

max

Z=50x1+30x2

变成

max

Z=40x1+30x2

目标函数是同约束条件

4x1+3x2120

平行的直线

Q2与Q3之间都是最优解50Q3(15,20)Q2(25,0)目前四十五页\总数一百零五页\编于八点⑴⑵无界解x1x2

目前四十六页\总数一百零五页\编于八点无界解：若可行域无界，且目标函数值可增加(减少)到正无穷(负无穷)，称这种无最优解的情况为无界解。注意：

可行域无界，不一定无最优解；可行域非空有界，则必定有最优解。目前四十七页\总数一百零五页\编于八点LP问题解的类型习题P55-2.1目前四十八页\总数一百零五页\编于八点三、单纯形法的基本思路和原理（一）单纯形法的基本思路

从可行域中某一个顶点开始，判断此顶点是否是最优，如不是，则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解，直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。目前四十九页\总数一百零五页\编于八点找出一个初始可行解是否最优转移到另一个目标函数（找更大的基本可行解）最优解是否循环直到找出为止，核心是：变量迭代结束目前五十页\总数一百零五页\编于八点

例

max

Z=2x1+3x2s.t.x1+2x244x1

84x2

6

x1,x2

01.基本概念目前五十一页\总数一百零五页\编于八点划为标准型：

max

Z=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=44x1+x4=84x2+x5=6

x1,x2,x3,x4,x5

0目前五十二页\总数一百零五页\编于八点约束方程的系数矩阵A=P1P2P3P4P5单位矩阵A中存在一个不为零的三阶子式，A的秩为3目前五十三页\总数一百零五页\编于八点A是约束条件的m×n阶系数矩阵，设r(A)=m,且B是A的m

阶非奇异的子矩阵（det(B)0),则称矩阵B为线性规划问题的一个基(阵)。（1）基(阵)B=或目前五十四页\总数一百零五页\编于八点(mn)

r(A)=m，至少有一个m阶子式不为0。a11

…a1m

a1m+1

…a1na21

…

a2m

a2m+1

…

a2n………am1

…

amm

amm+1

…

amnp1

…

pm

pm+1

…

pnBN目前五十五页\总数一百零五页\编于八点基B中的一列即称为一个基向量，基B中共有m个基向量。（2）基向量与非基向量B=P3P4P5基向量A=(p1

…

pm

pm+1

…

pn)=(B,N)

基向量

非基向量目前五十六页\总数一百零五页\编于八点（3）基变量与非基变量设A=(p1,p2,……,pn)，若B=(pi1,pi2,……,pim)为A的基阵，则称x1,x2,……,xn中的xi1,xi2,……,xim为对应于B的基变量，其余的称为非基变量。目前五十七页\总数一百零五页\编于八点B=P3P4P5x3,x4,x5是基变量x1,x2,是非基变量基向量X=(x1

…

xm

xm+1

…

xn

)T=(XBXN)T

基变量

非基变量A=(p1

…

pm

pm+1

…

pn)=(B,N)

基向量

非基向量目前五十八页\总数一百零五页\编于八点（4）基(本)解令非基变量取值为零,则基变量的取值可从AX=b中唯一解得。如此的一组解称为对应于B的一个基（本）解。目前五十九页\总数一百零五页\编于八点（5）基可行解若X0是一个基解，而且又是一个可行解，则称X0是一个基可行解。基可行解对应于可行域的顶点。目前六十页\总数一百零五页\编于八点退化的基可行解问题:

在基可行解中,非基变量的取值必定为零,基变量的取值是否必定大于零?若X0是一个基可行解,其基变量的取值全部大于零，则称X0是非退化的;否则称为退化的。目前六十一页\总数一百零五页\编于八点解的关系可行解基解基可行解最优解目前六十二页\总数一百零五页\编于八点代数概念几何概念满足一个等式约束的解满足一个不等式约束的解满足一组不等式约束的解基解基可行解目标函数值等于一个常数的解组约束直线约束半平面约束半平面的交集：凸多边形约束直线的交点可行域顶点目标函数等值线：一组平行线目前六十三页\总数一百零五页\编于八点举例目前六十四页\总数一百零五页\编于八点化为标准型目前六十五页\总数一百零五页\编于八点可行解、基解和基可行解举例目前六十六页\总数一百零五页\编于八点2.最优解的判断检验数公式或最优解检验的依据是计算检验数目前六十七页\总数一百零五页\编于八点检验数的判别规则(max)若所有的，则基B所对应的基可行解就是最优解。若所有的，而非基变量的检验数满足条件，则该线性规划问题有唯一最优解。若所有的

，又有某个非基变量的检验数，则该线性规划问题有无穷多最优解。若存在某个，又其对应的向量的所有分量，则该线性规划问题存在无界解。目前六十八页\总数一百零五页\编于八点3.单纯形表目前六十九页\总数一百零五页\编于八点（二）单纯形法的内容1.初始基可行解的确定（假定基阵B为单位阵）2.最优解的判断3.换基可行解的方法目前七十页\总数一百零五页\编于八点例

max

Z=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=44x1+x4=84x2+x5=6

x1,x2,x3,x4,x5

0目前七十一页\总数一百零五页\编于八点

cj23000x1x2x3x4x5121004001004001cBxBbx3x4x5000486

max

Z=2x1+3x2+0x3+0x4+0x5s.t.x1+2x2+x3=44x1+x4=84x2+x5=6

x1,x2,x3,x4,x5

0目前七十二页\总数一百零五页\编于八点cj23000cBxBb

x1x2x3x4x5000x3x4x54861210040010040010

230004/26/4－cj23000cBxBbx1x2x3x4x500x3x4840010

9/23x23/2010011010-1/21/420-20-3/41/1–8/4目前七十三页\总数一百零五页\编于八点cj23000cBxBbx1x2x3x4x520x1x4400-412

13/23x23/2010011010-1/21/400-201/4–64/2cj23000cBxBbx1x2x3x4x520x1x5200-21/21

73x21011/2-1/821001/40000-3/2-1/40目前七十四页\总数一百零五页\编于八点例目前七十五页\总数一百零五页\编于八点cj230000cBxBb

x1x2x3x4x5x60000x3x4x5x612816122210001201004000100400010

23000012/28/2－12/4000x3x4x516

400010

3x23010001/42620100-1/2100100-1/2目前七十六页\总数一百零五页\编于八点cj230000cBxBbx1x2x3x4x5x60003x3x4x5x262163

20100-1/210010-1/2400010010001/49

20000-3/46/2216/4－0203x3x1x5x22283001-201/210010-1/2000-412010001/44－41213000-201/4目前七十七页\总数一百零五页\编于八点0203x6x1x5x2

4402

002-401101-10000-441001-1/21001400-1/2-100000-201/4134－412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cj目前七十八页\总数一百零五页\编于八点0203x3x1x6x2

0442001-1-1/4010001/40000-21/210101/2-1/8014000-3/2-1/80000-201/4134－412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cj目前七十九页\总数一百零五页\编于八点例

求线性规划问题

目前八十页\总数一百零五页\编于八点00-1/12-7/2433/4

x2x112x1x2x3x4bxBcB2100cj15/43/4011/4-1/810-1/125/24目前八十一页\总数一百零五页\编于八点单纯形法解线性规划问题习题P55-2.2目前八十二页\总数一百零五页\编于八点1.无法给出初始基可行解四、大M法2.添加人工变量3.修改目标函数目前八十三页\总数一百零五页\编于八点例先减去再加上加入松弛变量加入人工变量目前八十四页\总数一百零五页\编于八点

加入人工变量后，目的是找到一个单位向量。其目标价值系数要确定，但不能影响目标函数的取值。一般可采用两种方法处理：大M法和两阶段法。

即假定人工变量在目标函数中的系数为-M（任意大正数。如基变量中还存在M，就不能实现极值。大M法：目前八十五页\总数一百零五页\编于八点目前八十六页\总数一百零五页\编于八点0-M0-5+2M3-4M2+3M-17M51-101-5210x6-M70011117X4-Mx6x5x4x3x2x1bxBcB-M0-M-532cj-M+1/7-1/7-M-16/7-50/700102/71/7-1/75/76/70145/7x12-1/71/72/71/7104/7x23x6x5x4x3x2x1bxBcB-M0-M-532cj目前八十七页\总数一百零五页\编于八点一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。要求解问题的目标函数能用数值指标来反映，且为线性函数；存在着多种方案；要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。五、线性规划在工商管理中的应用目前八十八页\总数一百零五页\编于八点1.人力资源分配的问题；2.生产计划的问题；3.套裁下料问题；4.配料问题；5.投资问题。应用举例目前八十九页\总数一百零五页\编于八点1.人力资源分配的问题

例1：某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：

设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?目前九十页\总数一百零五页\编于八点分析：不同上班班次时段的司机和乘务人员数设xi

表示第i班次时开始上班的司机和乘务人员数目前九十一页\总数一百零五页\编于八点例2：一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？目前九十二页\总数一百零五页\编于八点设xi

(i=1,2,…,7)表示星期一至日开始工作的人数。目前九十三页\总数一百零五页\编于八点2.生产计划的问题例3：某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？目前九十四页\总数一百零五页\编于八点解：设x1，x2，x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4，x5

分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。求xi的利润：利润=售价-各成本之和产品甲全部自制的利润=23-(3+2+3)=15

产品甲铸造外协，其余自制的利润=23-(5+2+3)=13

产品乙全部自制的利润=18-(5+1+2)=10

产品乙铸造外协，其余自制的利润=18-(6+1+2)=9

产品丙的利润=16-(4+3+2)=7可得到xi

（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。目前九十五页\总数一百零五页\编于八点通过以上分析,可建立如下的数学模型:目标函数：Max15x1+10x2+7x3+13x4+9x5

约束条件：5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0目前九十六页\总数一百零五页\编于八点例5：现有一批某种型号的圆钢长8米，需要截取2.5米长的毛坯100根，长1.3米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？100200321002462.5米1.3米需要根数

一二三四下料下料毛件数方式坯型号设变量为第j种方法的所有原料件数3.套裁下料问题目前九十七页\总数一百零五页\编于八点

例6：某工厂要做100套钢架，每套用长为2.9m,2.1m,1.5m的圆钢各一根。已知原料每根长7.4m，问：应如何下料，可使所用原料最省？解：共可设计下列5种下料方案，见下表

设x1,x2,x3,x4,x5分别为上面5种方案下料的原材料根数。这样我们建立如下的数学模型。目标函数：Minx1+x2+x3+x4+x5

约束条件：s.t.x1+2x2+x4≥1002x3+2x4+x5≥1003x1+x2+2x3+3x5≥100x1,x2,x3,x4,x5≥0目前九十八页\总数一百零五页\编于八点用软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。即x1=30;x2=10；

x3=0；

x4=50；

x5=0；只需90