线性规划与单纯形法

一、线性规划问题及其数学模型线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。例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

0max

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的秩为3A是约束条件的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

0cj23000cBxBb

x1x2x3x4x5000x3x4x54861210040010040010

230004/26/4－cj23000cBxBbx1x2x3x4x500x3x4840010

9/23x23/2010011010-1/21/420-20-3/41/1–8/4cj23000cBxBbx1x2x3x4x520x1x4400-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/2cj230000cBxBbx1x2x3x4x5x60003x3x4x5x262163

20100-1/210010-1/2400010010001/49

20000-3/46/2216/4－0203x3x1x5x22283001-201/210010-1/2000-412010001/44－41213000-201/40203x6x1x5x2

4402

002-401101-10000-441001-1/21001400-1/2-100000-201/4134－412001-201/210010-1/2000-412010001/42283x3x1x5x20203x1x2x3x4x5x6bxBcB230000cj0203x3x1x6x2

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.21.无法给出初始基可行解四、大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根原材料就可制造出100套钢架。注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。例7：根据对77种食物所含的九种营养物：热量(糖与脂肪)、蛋白质、钙、铁、维生素A、维生素B1、维生素B2、草酸与维生素C的成份及食物的市场价格调查，按照医生所提出的对每个人每天所需的营养要求。问怎样采购食物才能在保证营养要求的前提下花费最省？这就是营养问题或饮食问题，配料问题就是由此而推广来的。4.配料问题解：设每天购买甲，乙，丙，丁四种食物的数量分别为x1，x2，x3，x4，即可列出如下的线性规划模型：

例8：某工厂要用三种原料1、2、3混合调配出三种不同规格的