第一章线性规划及单纯形法

线性规划是运筹学的一个重要分支。自1947年美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法——单纯形法之后，线性规划在理论上趋于成熟，在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后，它的适用领域更广泛了。第一章线性规划及单纯形法

线性规划是一种合理利用资源、合理调配资源的应用数学方法。其中：规划就是利用某种数学方法使得有效资源的运用最优化；线性就是用来描述变量之间关系的函数是线性函数。当前第1页\共有112页\编于星期三\7点线性规划研究的主要内容：

（1）计划任务的确定，如何统筹安排，精心筹划，用最少的资源来实现。这方面的问题涉及到系统的投入和求极小值问题（2）资源的确定，如何合理利用，合理规划，使得完成的任务最大。

这方面的问题涉及到系统的产出和求最大值问题

线性规划研究和应用的内容是实现系统的投入产出的问题，就是用最少的劳力和物力消耗，获利更多更好的社会需求产品。当前第2页\共有112页\编于星期三\7点1.1线性规划问题及其数学模型

1.1.1问题的提出(一)

例某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时和原料A、B的消耗量如下表。该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排生产计划能使该厂获利最多？

这个问题可以用下面的数学模型来描述，设计划期内产品Ⅰ、Ⅱ的产量分别为x1，x2，可获利润用z表示，则有：MaxZ=2x1+3x2x1+2x2≤84x1≤16

4x2≤12x1,x2≥0当前第3页\共有112页\编于星期三\7点

1.1.1问题的提出(二)

例靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，两工厂之间有一条流量为每天200万m3的支流（见图）。

第一化工厂每天排放污水2万m3，第二化工厂每天排放污水1.4万m3。污水从工厂1流到工厂2前会有20%自然净化。根据环保要求，河水中污水的含量应不大于0.2%。而工厂1和工厂2处理污水的成本分别为1000元/m3和800元/m3。问两工厂各应处理多少污水才能使处理污水的总费用最低？

设工厂1和工厂2每天分别处理污水x1和x2万m3，则有：Minz=1000x1+800x2(2-x1)/500≤0.002[0.8(2-x1)+1.4-x2]/700≤0.002x1≤2,x2≤1.4

x1,x2≥0当前第4页\共有112页\编于星期三\7点1.1.1问题的提出(三)例

某养鸡场所用的混合饲料是由n种配料组成。要求这种混合饲料必须含有m种不同的营养成份，而且要求每单位混合饲料中第i种营养成份的含量不能低于bi(i=1,2,…,m）。已知第i种营养成份在每单位的第j种配料中的含量为aij,j=1,2,…,n，每单位的第j种配料的价格为cj

。现在要求在保证营养条件的前提下，应采用何种配方，使混合饲料的成本最小.配料营养成份B1B2

…Bn含量A1A2…Am

a11a12

…a1na21a22

…a2nam1am2

…amnb1b2bm单价c1c2…

cn当前第5页\共有112页\编于星期三\7点建立模型：MinZ=c1x1+c2x2+…+cnxn

设xj

表示在单位混合饲料中，第j种配料的含量（j=1,2,…,n）则有如下的数学模型：配料营养成份B1B2

…Bn含量A1A2…Ama11a12

…a1na21a22

…a2nam1am2

…amnb1b2bm价格c1c2…

cna11x1+a12x2+…+a1nxn≥

b1a21x1+a22x2+…+a2nxn≥

b2……am1x1+am2x2+…+amnxn≥

bmx1≥0,x2≥0,…,xn≥0当前第6页\共有112页\编于星期三\7点

1.1.2线性规划问题的数学模型

线性规划问题的共同特征（1）每个问题都用一组决策变量(x1,x2,···,xn，Decisionvariable)表示某一方案,这组未知数的值就代表一个具体的方案,通常要求这些未知数取值是非负的。

（2）存在一定的限制条件(称为约束条件，Constraint),这些条件都可以用关于决策变量的一组线性等式或不等式来表示。（3）都有一个目标要求,并且这个目标可表示为这组决策变量的线性函数(称为目标函数，Objectivefunction),按研究问题的不同,要求目标函数实现最大化或最小化。

满足以上三个条件的数学模型称为线性规划数学模型。其一般形式为当前第7页\共有112页\编于星期三\7点线性规划一般模型的代数式为：max(min)Z=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn≤(或＝,≥)b1a21x1+a22x2+…+a2nxn≤(或＝,≥)b2……………am1x1+am2x2+…+amnxn≤(或＝,≥)bmx1,x2,…,xn≥(≤)0当前第8页\共有112页\编于星期三\7点1.1.3线性规划问题的标准形式

线性规划问题的数学模型有各种不同的形式，如

目标函数有极大化和极小化；

约束条件有“≤”、“≥”和“＝”三种情况；

决策变量一般有非负性要求，有的则没有。

为了求解方便，特规定一种线性规划的标准形式，非标准型可以转化为标准型计算

当前第9页\共有112页\编于星期三\7点标准形式为：

（一）标准形式

目标函数最大化

约束条件为等式

右端常数项bi≥0

决策变量非负

maxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥0当前第10页\共有112页\编于星期三\7点标准型的表达方式有代数式、矩阵式：（二）标准型的表达方式

1.代数式maxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥0简记maxZ=cjxjaijxj＝bi

(i=1,2,…,m)xj≥0(j=1,2,…,n)当前第11页\共有112页\编于星期三\7点

2.矩阵式化为maxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥0当前第12页\共有112页\编于星期三\7点（三）非标准型向标准型转化

目标函数极小化问题

只需将等式两端乘以-1即变为极大化问题。因为minZ=–max(–Z)=CTX，令Z′=-Z，则maxZ′=–CTXminZ=CTX约束条件中右端常数项非正

两端同乘以-1

约束条件为不等式

当约束方程为“≤”时，左端加入一个非负的松弛变量，就把不等式变成了等式；如4X1＋2X2

≤60→4X1＋2X2

＋X3

=60

当约束条件为“≥”时，不等式左端减去一个非负的剩余变量(也可称松弛变量)，就把不等式变成了等式。

决策变量xk为无约束变量

令xk=xk‘-xk〃，其中令xk′，xk〃≥0，用xk′、xk〃取代模型中xk当前第13页\共有112页\编于星期三\7点例1：试将如下线性规划问题化成标准型例1的标准型

maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.maxZ=

3x1+5x2+0x3

x1+x3=82x2≤123x1+4x2≤36x1,x2,x3

≥0maxZ=

3x1+5x2+0x3+

0x4

x1+x3=8

2x2+x4=12

3x1+4x2≤36x1,x2,x3,x4≥0maxZ=

3x1+5x2+0x3+

0x4+0x5

x1+x3=8

2x2+x4=12

3x1+4x2+x5=36x1,x2,x3,x4,x5≥0maxZ=

3x1+5x2+0x3+

0x4+0x5

x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0需要化为标准型引进一x3引进一x4引进一x5当前第14页\共有112页\编于星期三\7点例2：试将如下线性规划问题化成标准型minZ=

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

-x1-x2-x3≥-2x1≥0,x3≤0S.t.例2的标准化minZ=

x1+2x2+3x3′x1+2x2+x3

′≤52x1+3x2+x3

′≥6

-x1-x2+x3

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

minZ=

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

minZ=

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

maxZ′=-x1-2(x2′-x2〃

)

-3x3′+0x4

x1+2(x2′-x2〃

)

+x3

′+x4=52x1+3(x2′-x2〃

)+x3

′≥6

x1+(x2′-x2〃

)

-x3

′≤2x1,

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

maxZ′=-

x1-2(x2′-x2〃

)

-3x3′

+0x4+0x5

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

maxZ′=-x1-2(x2′-x2〃

)

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

x1+2(x2′-x2〃

)

+x3

′+x4=5

2x1+3(x2′-x2〃

)+x3

′-x5=6

x1+(x2′-x2〃

)

-x3

′+x6=2x1,

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

maxZ′=-

x1-2(x2′-x2〃

)

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

)

+x3

′≤5

2x1+3(x2′-x2〃

)+x3

′≥6

x1+(x2′-x2〃

)

-x3

′≤2x1,

x2′,x2〃,x3′≥0

maxZ′=-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

需要化为标准型令－x3＝x3’令x2＝x2’–x2’’令-Z＝Z’引进一x4引进一x5引进一x6当前第15页\共有112页\编于星期三\7点例3:试将如下线性规划问题化成标准型例3的标准型为：

需要化为标准型当前第16页\共有112页\编于星期三\7点练习：试将如下线性规划问题化成标准型（1）maxZ=-x1+3

x3+4

x42x1+4

x2+x3-2

x4≤13

6x1+x3+8

x4≥50-x1+4

x2-5

x3-3

x4=-10xi≥0,i=1,2,3,4S.t.（2）minZ=

6

x1+7

x2-

x33x1+2

x2-x3≤10

x2+x3≤15x1≥3x2≥2x1,

x2≥0，x3无限制S.t.当前第17页\共有112页\编于星期三\7点答案：（1）maxZ=-x1+3

x3+4

x4+0

x5+0

x62x1+4

x2+x3-2

x4+x5=13

6x1+x3+8

x4-x6=50x1-4

x2+5

x3+3

x4=10xi≥0,i=1,2,3,4,5,6S.t.（2）maxZ’=-6

x1-7

x2+

x3－x4+0x5+0x6+0x7+0x83x1+2

x2-x3+x4+x5=10

x2+x3－x4+x6=15x1-x7=3x2-x8=2x1,

x2,

x3,

x4,

x5,

x6,

x7,

x8≥0S.t.当前第18页\共有112页\编于星期三\7点1.1.4线性规划解的概念

在讨论线性规划问题的求解之前,先要了解线性规划问题的解的概念。由前面讨论可知线性规划问题的标准型为：

求解线性规划问题就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数（1）达到最大值。

若设矩阵A的秩R(A)=m；根据线性代数定理可知，当R(A)=m＜n，则方程组有无穷多个解，这也正是线性规划寻求最优解的余地所在。当前第19页\共有112页\编于星期三\7点关于标准型解的若干基本概念可行解（feasiblesolution）与非可行解（infeasiblesolution

）满足约束条件（2）和非负条件（3）的解

X

称为可行解，满足约束条件（2）但不满足非负条件（3）的解

X称为非可行解可行域（feasibleregion）:可行解组成的集合叫做最优解（optimalsolution）：使目标函数(1)达到最大的解称为最优解当前第20页\共有112页\编于星期三\7点

基在标准型中，约束方程组的系数矩阵有n列，即

A=(P1,P2,…,Pn)设A的秩为m，当R(A)=m＜n，A中必有线性独立的m列，构成该标准型的一个基，

即B=(P1,P2,…,Pm)，|B|0

P1,P2

,…,Pm

称为基向量与基向量对应的变量称为基变量，记为XB=(x1,x2,…,xm)T其余的变量称为非基变量，记为XN=(xm+1,xm+2,…,xn)T，故有

X=XB+XN，最多有个基当前第21页\共有112页\编于星期三\7点

基本解令非基变量XN=0，求得基变量XB的值称为基解，即XB=B1

b基解是有限的基本可行解基本解XB的非零分量都0时，称为基本可行解，否则为基非可行解基本可行解的非零分量个数<m时，称为退化解可行基对应于基本可行解的基，称为可行基当前第22页\共有112页\编于星期三\7点线性规划标准型问题解的关系约束方程的解空间基本解可行解非可行解基本可行解退化解当前第23页\共有112页\编于星期三\7点例1的标准型为maxZ=

3x1+5x2+0x3+0x4+0x5x1+x3=82x2+x4=123x1+4x2+x5=36x1,x2,x3,x4,x5≥0约束方程的增广矩阵x1x2x3x4x53阶非奇异子矩阵为基矩阵还原为maxZ=

3x1+5x2+0x3+0x4+0x5x3=-x1+8x4=-2x2+12x5=-3x1-4x2+36

基变量是x3,x4,x5，令非基变量x1=x2=0，得到x3=8，x4=12，x5=36基解。此解为基可行解：X0=(0,0,8,12,36)TR(A)=3非基变量是x1,x2，当前第24页\共有112页\编于星期三\7点1.2

线性规划问题的求解

1.2.1图解法

对于简单的线性规划问题(只有两个决策变量的线性规划问题)，可以通过图解法对它进行求解。

图解法即是用图示的方法来求解线性规划问题。图解法简单直观，有助于了解线性规划问题求解的基本原理。

一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能用图示了。

当前第25页\共有112页\编于星期三\7点（一）图解法的基本步骤

满足所有约束条件的解叫可行解，解的集合称之为可行域。即所有约束条件共同围成的区域。1.可行域的确定例1求解线性规划x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D

五边形OABCD内(含边界)的任意一点(x1，x2)都是满足所有约束条件的一个解，称之可行解。maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0当前第26页\共有112页\编于星期三\7点2.最优解的确定

确定x1、x2希望目标函数Z=

3x1+5x2达到最大，图形中Z=

3x1+5x2代表以Z为参数的一族平行线，即等值线。

等值线：位于同一直线上的点的目标函数值相同。

Z=3x1+5x2＝0x1=82x2=123x1+4x2

=36x1x248123690AB(8,3)C(4,6)D

最优解：可行解中使目标函数最优(极大或极小)的解

本题中：满足目标函数最大的极点是离原点距离最远的点（4,6）Z=3x1+5x2＝24Z=3x1+5x2＝30Z=39Z=42即x1=4，x2=6时Z的值最大为42。

C(4,6)为最优解当前第27页\共有112页\编于星期三\7点（二）解的几种可能性唯一最优解：只有一个最优点。如上题的最优解（4,6）

多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D如例1的数学模型变为

maxZ=

3x1+4x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.Z=24Z=36Z=12当前第28页\共有112页\编于星期三\7点

线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）例如

maxZ=

3x1+2x2-2x1+x2≤2x1-3x2≤3x1≥0,x2≥0-2x1+x2=2x1-3x2=3x2123-1x1123-1Z=6Z=12S.t.例如

maxZ=

3x1+2x2-2x1+x2≥2x1-3x2≥3x1≥0,x2≥0-2x1+x2=2x1-3x2=3x2123-1x1123-1S.t.无界解：无可行解：若约束条件相互矛盾，则可行域为空集。当前第29页\共有112页\编于星期三\7点例：求最大值问题数学模型为：

四边形OBQC内(含边界)的任意一点(x1，x2)都是满足所有约束条件的一个解，称之可行解。maxZ=

8x1+6x24x1+2x2≤602x1+4x2≤482x1+3x2≤36x1≥0,x2≥02x1+3x2

=36x1x2510510150C(0,12)4x1+2x2

=602x1+4x2

=48B(15,0)Z=0Z=72Z=120Z=126Q(13.5,3)结论：在Q(13.5,3)处利润最大为126，Q(13.5,3)为最优解当前第30页\共有112页\编于星期三\7点例：求最小值问题

设有某林场需配制某种灭虫药水500公斤，该药水系由甲与乙两种药水混合而成。甲种药水每公斤5元，乙种药水每公斤8元。按照两种药水的化学性质，在混合时，500公斤混合药水中含甲种药水最多不能超过400公斤，含乙种药水最少不能少于200公斤。问如何配制可使该药水配制成本最低？.

minZ=

5x1+8x2x1≤400x2≥200x1+x2=500x1≥0,x2≥0则数学模型为：设：500公斤混合药水中，甲种药水x1公斤，乙种药水x2公斤当前第31页\共有112页\编于星期三\7点例：求最小值问题数学模型为：

线段BC上的任意一点(x1，x2)都是满足所有约束条件的一个解，称之可行解。

minZ=

5x1+8x2x1≤400x2≥200x1+x2=500x1≥0,x2≥0结论：等成本线往右下移，成本越来越小，A(300,200)成本为最小Z=5x1+8x2

=4000Z=3100x2

=200x1+x2

=500x1x2502004000B(0,500)100300500x1

=400100200300400CA最优解为（300,200）当前第32页\共有112页\编于星期三\7点练习题：用图解法求解下列问题－x＋2y≤2x＋2y≤6x－y≤3x＋3y≥3x≥0,y

≥01.约束条件为：（1）maxZ=

4x+y画出可行域图形，求下面几种情况下的最优解（2）minZ=

2x-3y（3）maxZ=

x+2y（4）maxZ=

2x-3y当前第33页\共有112页\编于星期三\7点练习题：求解－x＋2y≤2x＋2y≤6x－y≤3x＋3y≥3x≥0,y

≥0（1）maxZ=

4x+y求下面几种情况下的最优解（2）minZ=

2x-3y（4）maxZ=

x+2y（3）maxZ=

2x-3yx+3y=3－x+2y=2x－y

=3x1x2161234523x+2y=6(2,2)(4,1)(3,0)(0,1)Z=4x+y=1Z=10Z=12Z=17Z=-3Z=-2Z=5Z=6最优解x=4,y=1maxZ=

17最优解x=0,y=1minZ=

-3Z=2x+y=1Z=3Z=6有无穷多最优解maxZ=

6最优解x=3,y=0maxZ=

6当前第34页\共有112页\编于星期三\7点1.2.2单纯形法（SimpleMethod）（一）线性规划解的基本概念和基本定理基本概念1、凸集:假设K是n维欧氏空间的一个点集,若对于K中的任意两点X1、X2,其连线上的所有点X1+(1-)X2(01)都在集合K中,即:X1+(1-)X2K(01),则称K为凸集。2.顶点:假设K是凸集,XK;若不能用不同的两个点X1、X2K的线性组合表示为:X=X1+(1-)X2，(0<<1)，则称X为凸集K的一个顶点（或称为极点）。当前第35页\共有112页\编于星期三\7点若线性规划问题存在可行域，则其可行域一定是凸集。

定理2：线性规划问题的基本可行解对应于可行域的顶点。

定理3：

若可行域有界，线性规划的目标函数一定可以在可行域的顶点上达到最优。

x1x248123690ABC(4,6)D

定理1：基本定理综合定理2和定理3得：线性规划问题若存在最优解则最优解一定存在于基本可行解之中。当前第36页\共有112页\编于星期三\7点（二）线性规划的解题思路

线性规划问题可以有无数个可行解，而有限个顶点对应的是基本可行解，最优解只可能在顶点(基本可行解)上达到，故只要在有限个基可行解中寻求最优解即可。其思路是：

从线性规划问题的一个基本可行解开始，转换到另一个使目标函数值增大的基本可行解。反复迭代，直到目标函数值达到最大时，就得到了最优解。。当前第37页\共有112页\编于星期三\7点（三）线性规划单纯形法的解题流程当前第38页\共有112页\编于星期三\7点（四）线性规划解题工具----单纯形表格及其格式CjC1…CmCm+1…Cn比值CBXBbx1…XmXm+1…xnC1X1b11…0a1m+1…a1n1C2X2b20…0a2m+1…a2n2………………………Cmxmbm0…1amm+1…amnm检验数j-Z0…0m+1…nmaxZ=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bm当前第39页\共有112页\编于星期三\7点（五）线性规划求解需要解决的技术问题

按照单纯形法的思路求解线性规划问题,要解决三个技术问题:⑴给出第一个基本可行解;⑵检验一个基本可行解是否是最优解;⑶转换到另一个基本可行解.

⑴把线性规划问题变成标准型后,观察是否每个约束方程中都有独有的、系数为1的变量.如果是,则取这些变量作为基变量,便得到一个基本可行解;否则,就给没有这种变量的约束条件添加一个人工变量,同时修改目标函数.(见例题)

⑵如果单纯形表最后一行中的σj都满足σj≤0,则对应的基本可行解是最优解;否则就不是最优解.σj称为检验数.

当前第40页\共有112页\编于星期三\7点

⑶第一,确定换入变量.在大于0的检验数中找最大的为σk,对应变量xk为换入变量.第二,确定换出变量.取θ=min{bi/a‘ik|a’ik>0}=bl/a’lk,对应的第l行的基变量为换出变量.第三,旋转运算.换入变量所在的行与换出变量所在的列交叉点的元素称为中心元素,用高斯消去法把中心元素化成1,同列的其他元素化成0,得到一个新的单纯形表,也就得到一个新的基本可行解.

当前第41页\共有112页\编于星期三\7点（六）表格单纯形法的计算步骤maxZ=3x1+5x2x1

≤82x2

≤123x1+4x2

≤36Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000maxZ=3x1+5x2+0x3+0x4+0x5x1+x3=82x2+x4=123x1+4x2+x5=36

标准型基变量x3,x4,x5，1、建立初始单纯形表非基变量x1,x2当前第42页\共有112页\编于星期三\7点2、求初始基本可行解并进行最优性检验Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000

令非基变量x1=0，x2=0，找到一个初始基可行解：

x1=0，x2=0，x3=8，x4=12，x5=36，

σj＞0，此解不是最优（因为z=3x1+5x2+0x3+0x4+0x5)可求基可行解的状态即X0=(0,0,8,12,36)T，此时利润Z=0当前第43页\共有112页\编于星期三\7点初始基本可行解图示Z=3x1+5x2＝0x1=82x2=123x1+4x2

=36x1x248123690AB(8,3)C(4,6)DX0=(0,0,8,12,36)T说明：一个可行解就是一个生产方案，上述方案表明两种产品都不生产x1=0，x2=0，利润Z=0。当前第44页\共有112页\编于星期三\7点3、寻找另一基本可行解Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9

中心元素首先确定换入变量再确定换出变量当前第45页\共有112页\编于星期三\7点检验数j81010060101/2012300-21x3x2x5050-30300-5/20Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9令x1=0，x4=0，得x2=6，x3=8，x5=12，即得基可行解X1=(0,6,8,0,12)T此时Z＝30σ1=3＞0，此解不是最优迭代可求基可行解的状态当前第46页\共有112页\编于星期三\7点第一次基迭代可行解图示Z=3x1+5x2＝30x1=82x2=123x1+4x2

=36x1x248123690AB(8,3)C(4,6)DX1=(0,6,8,0,12)T当前第47页\共有112页\编于星期三\7点4、寻找下一基本可行解Cj比值CBXBb检验数jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1最优解:X*=(4,6,4,0,0)T，Z*=42令x4=0，x5=0，得x1=4，x2=6，x3=4，即X0=(4,6,4,0,0)T此时Z＝42j＜0当前第48页\共有112页\编于星期三\7点单纯形法的几何意义x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)DX0=(0,0,8,12,36)T,Z＝0X1=(0,6,8,0,12)T,Z＝30X1=(4,6,4,0,0)T,Z＝42当前第49页\共有112页\编于星期三\7点单纯形法－表格法又例Cj比值CBXBb检验数jx1x2x3x4x52300081210016400101204001x3x4x5000023000

Maxz=2x1+3x2x1+2x2+x3=84x1+x4=164x2+x5=12x1,x2,x3≥0标准型基变量x3,x4,x5，非基变量x1,x21、建立初始单纯形表Maxz=2x1+3x2x1+2x2≤84x1≤164x2≤12x1,x2,x3≥0j＞0当前第50页\共有112页\编于星期三\7点2、寻找另一基本可行解Cj比值CBXBb检验数jx1x2x3x4x52300081210016400101204001x3x4x50000230004-3中心元素检验数j21010-2/41640010301001/4x3x4x2003-92000-3/4σ1=2＞0，此解不是最优当前第51页\共有112页\编于星期三\7点3、寻找下一基本可行解Cj比值CBXBb检验数jx1x2x3x4x52300021010-2/41640010301001/4x3x4x2003-92000-3/424－中心元素检验数j21010-2/4800－412301001/4x1x4x2203－1300－201/4σ5=1/4＞0，此解不是最优当前第52页\共有112页\编于星期三\7点4、再次寻找下一基本可行解Cj比值CBXBb检验数jx1x2x3x4x52300021010-2/4800－412301001/4X1X4X2203－1300－201/4-412检验数j41001/40400－21/212011/2-1/80x1x5x2203－1400－3/2-1/80σi＜0，此解最优令x3=0，x4=0，x1=4，x2=2，x5=4，即X0=(4,2,0,0,4)T此时Z＝14当前第53页\共有112页\编于星期三\7点小结：单纯形表格法的计算步骤①将线性规划问题化成标准型。②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。③计算各非基变量xj的检验数j=Cj-CBPj′，若所有j≤0，则问题已得到最优解，停止计算，否则转入下步。④在大于0的检验数中，若某个k所对应的系数列向量Pk′≤0，则此问题是无界解，停止计算，否则转入下步。⑤根据max{j｜j＞0}=k原则，确定xk为换入变量(进基变量)，再按规则计算：=min{bi′/aik′|aik′＞0}=bl′/alk′确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。⑥以aik′为中心元素进行迭代，把xk所对应的列向量变为单位列向量，即aik′变为1，同列中其它元素为0，转第③步。当前第54页\共有112页\编于星期三\7点

用单纯形法求解线性规划问题后，应回答下面几个问题：⑴是否解无界？上面的步骤已作出回答。⑵是否无可行解？求解后，若人工变量都已取0，则有可行解；否则，无可行解。⑶唯一最优解还是无穷多最优解？在最后的单纯形表中，若所有非基变量的检验数都严格小于0，则为唯一最优解；若存在某个非基变量的检验数等于0，则有无穷多最优解。当前第55页\共有112页\编于星期三\7点

1.2.3单纯形法的进一步讨论用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“≤”时，加入松弛变量就形成了初始基。但实际存在“≥”或“＝”型的约束，就没有现成的单位矩阵。采用人造基的办法：人为构造单位矩阵处理方法有两种：大M法两阶段法当前第56页\共有112页\编于星期三\7点（一）大M法1、单纯形法表maxZ=

3x1-x2-2x33x1+2x2-3x3=6x1-2x2+x3=4x1,x2,x3≥0S.t.没有单位矩阵，不符合构造初始基的条件，需加入人工变量。maxZ=

3x1-x2-2x3-Mx4-Mx53x1+2x2-3x3+x4=6x1-2x2+x3+x5=4x1,x2,x3,x4,x5≥0人工变量最终必须等于0才能保持原问题性质不变。为保证人工变量为0，在目标函数中令其系数为-M。M为无限大的正数，这是一个惩罚项，倘若人工变量不为零，则目标函数就永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。当前第57页\共有112页\编于星期三\7点

按大M法构造人造基，引入人工变量x4,x5的辅助问题如下：maxZ=

3x1-x2-2x3-Mx4-Mx53x1+2x2-3x3+x4=6x1-2x2+x3+x5=4x1,x2,x3,x4,x5≥0Cj比值CBXBb检验数jx1x2x3x4x53-1-2-M-M632-31041-2101x4x5-M-M0-M-2+M-1-2M3+M4M00-2-2M-13+4M10M-M-M-2-13当前第58页\共有112页\编于星期三\7点

检验数jbXBCB比值Cjx5x4x3x2x1-M-M-2-1301-3236101-21400-2-2M-13+4M10Mx5x4-M-M42-1检验数j212/3-11/3020-8/32-1/31-70-3-8M/31+2M-1-4M/30x1x53-M检验数j31-2/301/61/210-4/31-1/61/2-70-5/30-M-5/6-M-1/2x1x33-2x2=0,x4=0,x5=0,x1=3,x3=1,σj<0，此解最优,Z=7当前第59页\共有112页\编于星期三\7点2、矩阵解法按大M法构造人造基，引入人工变量x4,x5的辅助问题如下：maxZ=

3x1-x2-2x3-Mx4-Mx53x1+2x2-3x3+x4=6x1-2x2+x3+x5=4x1,x2,x3,x4,x5≥0例如maxZ=

3x1-x2-2x33x1+2x2-3x3=6x1-2x2+x3=4x1,x2,x3≥0S.t.当前第60页\共有112页\编于星期三\7点

将线性规划问题标准化3x1+2x2-3x3+x4=6x1-2x2+x3+x5=4-Z+3x1-x2-2x3-Mx4-Mx5=0x1,x2,x3,x4,x5≥00-M-2-13-Z411-21060-3230-M01初等变换～10M0-2-2M-13+4M-Z411-21060-3230001当前第61页\共有112页\编于星期三\7点初等变换10M0-2-2M-13+4M-Z411-21060-3230001～-6+2M01+2M-3-8M/30-Z212-8/30020-12/310-1-4M/3-1/31/3-7-M-1/20-5/30-Z11/21-4/30031/20-2/310-M-5/6-1/61/6～x2=0,x4=0,x5=0,x1=3,x3=1,σj<0，此解最优,Z=7当前第62页\共有112页\编于星期三\7点试用大M法求解如下线性规划问题的最优解。按大M法构造人造基，引入人工变量x4,x5的辅助问题如下：松驰变量剩余变量人工变量惩罚项当前第63页\共有112页\编于星期三\7点试用大M法求解如下线性规划问题的最优解。0-M0-1-13-Z’11010-2030021-4011011-21000-10-M010～4M00-1+3M-1+M3-6M-Z’11010-2030021-4011011-210-M0-10