第二章： 线性规划问题
线性规划问题及其标准形式：
问题：某工厂可生产P1和P2两种产品，现有A、B、C三种资源情况如下：
产品
单位消耗量 P1 P2 资源拥有量(吨)
资源
A 50 30 2000
B 6 5 300
C 3 5 200
单位产品获利(元) 50 60
问：根据现有资源如何安排各产品的生产量，并使工厂获利最大
解：设P1产品生产X1，P2产品生产X2
max S= 50x1+60x2
50 x1+30 x2≤2000
6 x1+5 x2≤300
3 x1+5 x2≤200
x1≥0; x2≥0
问题：运输问题
单位粮食 粮食需求
运输费用 城市
(元)
粮食产地
P1 P2
拥有粮食量
A
B
4
5 3
800
200
城市需求粮食量
400 600
平衡
问：怎样安排运输使总的运费最少。
解：
设：
P1 P2
A
B
X11 X12
X21 X22
MinS=2 X11+4 X12+5 X21+3 X22
X11+ X12=800
X21+ X22=200
X11+ X21=400
X12+ X22=600
Xij≥0
给出线性规划的一般定义如下：
对于求取一组变量xj (j =1,2,......,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。
线性规划问题：是研究在一组线性不等式或线性等式的约束条件下，使某个线性目标函数取得最大值（或最小值）
通过案例建模可以总结出建立一个实际问题的线性规划模型的步骤：
第一步：设置要求解的决策变量。决策变量选取得当，不仅能顺利地建立模型而且能方便地求解，否则很可能事倍功半。
第二步：找出所有的限制，即约束条件，并用决策变量的线性方程或线性不等式来表示。当限制条件多，背景比较复杂时，可以采用图示或表格形式列出所有的已知数据和信息，从而避免“遗漏”或“重复”所造成的错误。
第三步：明确目标要求，并用决策变量的线性函数来表示，标出对函数是取极大还是取极小的要求。
决策变量的非负要求可以根据问题的实际意义加以确定。
需要特别说明的是：
要使用线性规划方法来处理一个实际问题，必须具备下面的条件：
1.优化条件---问题的目标有极大化或极小化的要求,而且能用决策变量的线性函数来表示。
2选择条件---有多种可供选择的可行方案，以便从中选取最优方案。
3限制条件---达到目标的条件是有一定限制的（比如，资源的供应量有限度等），而且这些限制可以用决策变量的线性等式或线性不等式表示出来。
此外，描述问题的决策变量相互之间应有一定的联系，有可能建立数学关系，即这些变量之间是内部相关的，这一点自然是不言而喻的。
为了便于研究线性规划问题的理论与一般解法，人们需要将任意一个线性规划问题化为标准形式。
n个变量的线性规划问题的标准形式为：
Max S = (1)
i=1,2,3,…..m (2)
≥0 (bi是≥0的常数) （3）
或max S=CX C=(c1,c2,…，cn)
X=(1,2,…，n)T
AX=b A=(aij)m×n
x≥0 b=(b1,b2,…，bm)T
线性规划问题的标准形式：简记“LP”问题
标准形式的要求和特点：
所有的变量非负 （即≥0 ,j=1,2,3,…... ，n）
所有的约束条件都是等式（ ）
目标函数统一为求最大值（ Max S = ）
4)右端常数均为非负值 (bi是≥0的常数)
线性规划问题的一般模型转化为标准形式的方法如下：
1）当(≠0)
xj=yj+lj
2)当bi<0 都乘“－1”
的方程式两边
3）约束条件中含有不等式采用引进松驰变量变为等式
xn+i≥0
xn+i≥0
4)变量xj无非负约束采用引进非负变量转换
无非负约束
xj’ ≥0;xj” ≥0 xj=xj’-xj”
5)目标函数求最小值采用负变换法
min S = max s’=
问题1的标准型：
max S= 50x1+60x2+++
50x1+30x2+x3=2000
6x1+5x2+x3=300
3x1+5x2+x5=200
x1,x2,x3,x4，x5≥0
二、线性规划问题的图解法及其解的定义
所谓线性规划的图解法就是用几何作图的方法分析并求出其最优解的过程。求解的思路是：先将约束条件加以图解，求得满足约束条件的解的集合（即可行域），然后结合目标函数的要求从可行域中找出最优解。
线性规划模型(决策部分确定型案例)
max Z=2x1+3x2
实施图解法，以求出最优生产计划（最优解）。
由于线性规划模型中只有两个决策变量，因此只需建立平面直角坐标系就可以进行图解了。
第一步：建立平面直角坐标系，标出坐标原点，坐标轴的指向和单位长度。我们用x1轴表示产品A的产量，用x2轴表示产品B的产量。
第二步：对约束条件加以图解。
每一个约束不等式在平面直角坐标系中都代表一个半平面，只要先画出该半平面的边界，然后确定是哪个半平面就可以了。现在以第一个约束条件 1/3 x1+1/3 x2 (1 为例说明约束条件的图解过程。
如果全部的劳动工时都用来生产A 产品而不生产B产品，那么A产品的最
大可能产量为3吨，计算过程为：
1/3x1+1/3×0(1 (x1(3
这个结果对应着图案例中的点A(3,0),同样我们可以找到B产品最大可能生产量对应的点B(0,3)。
5–
4–
l1 3–B
2 D E （1/3）x1+(4/3)x2=3
l2 1–
0 1〡 2〡 3A 4〡 5〡 6〡 7〡 8〡 9〡C
(1/3)x1+(1/3)x2=1
连接A、B两点得到约束 1/3 x1+1/3 x2 (1 所代表的半平面的边界 1/3 x1+1/3 x2 ＝1，即直线AB。
完全类似地可以画出第二个约束条件的边界－－直线CD:
1/3x1+4/3 x2 =3
然后我们寻找这两个约束条件及非负条件
x1,x2 (0所代表的公共部分－－图中阴影区，就是满足所有约束条件和非负条件的点的集合，即可行域。在这个区域中的每一个点都对应着一个可行的生产方案。
第三步：画出目标函数等值线，结合目标函数的要求求出最优解－－最优生产方案。
令 Z=2x1+3x2=c,其中c为任选的一个常数，在图1－3中画出直线 2x1+3x2=c,这条直线上的点即对应着一个可行的生产方案，即使两种产品的总利润达到c。可以看出，这样的直线有无数条，而且相互平行，我们称这样的直线为目标函数等值线。我们只要画出两条目标函数等值线，比如令c＝0和c=6，就可以看出目标函数值递增的方向，通常用箭头标出这个方向。图中两条虚线l1和l2就分别代表目标函数等值线 2x1+3x2=0 和2x1+3x2=6,箭头表示使两种产品的总利润递增的方向。
沿着箭头的方向平移目标函数等值线，使其达到可行域中的最远点E, E点就是我们要求的最优点，它对应的相应坐标 x1=1,x2=2 就是最有利的产品组合，即生产A产品1吨，B产品2吨能使两种产品的总利润达到最大值 Zmax=2(1+3(2=8（千元），x1=1,x2=2也就是要求的线性规划模型（1－1）式的最优解，Zmax=8就是相应的目标函数最优值。
尽管最优点的对应坐标可以直接从图中给出，但是在大多数情况下，对实际问题精确地看出一个解答是比较困难的。所以，通常总是用解联立方程的方法求出最优解的精确值。比如E点对应的坐标值我们可以通过求解下面的联立方程，即求直线AB和CD的交点来求得。
1/3x1+1/3x2=1
1/3x1+4/3x2=3
顺便提及，每一个线性规划都有一个“影像”（一个伴生的线性规划）。这个影像叫做线性规划的对偶规划。当建立一个线性规划并达到最优目标值时，同时也就解出了对偶规划并达到了另一个不同意义的目标。比如案例是研究求得一个生产计划方案，使得在劳动力和原材料可能供应的范围内，使产品的总利润最大，它的对偶问题就是一个价格系统，使在平衡了劳动力和原材料的直接成本后，所确定的价格系统最具有竞争力。
案例的对偶规划如下：
min W=y1+y2
它的图解见图1－4。其中L1和L2分别为两个约束半平面的边界，虚线为目标函数等值线，可行域为图中阴影部分，沿着与箭头（目标函数值递增的方向）相反的方向平移目标函数等值线（注意：对偶规划中要求对目标函数极小化）得最优点为A, 其对应坐标为 y1=5,y2=1
其经济意义可以解释为对包工工时及原材料的单位定价（影子价格），若工厂自己不生产产品A和B，将现有的工时及原材料转而接受外来加工时，那么上述的价格系统能保证不亏本又最富有竞争力（包工及原材料的总价格最低）。可以看到，当原问题和对偶问题都取得最优解时，这一线性规划对应的目标函数值是相等的
Zmax=Wmin=8
考察原问题和对偶问题的解，给作决策的管理者另一个自由度，比如除了研究怎样利用已有的资源以取得最大利润的同时，还可以进一步探讨怎样通过增加更多的资源或使用不同类型的资源来增加利润。关于这方面的讨论我们将放在灵敏度分析的有关内容中进行。
问题1： max S= 50x1+60x2
50 x1+30 x2≤2000
6 x1+5 x2≤300
3 x1+5 x2≤200
x1≥0; x2≥0
解： 50x1+30x2 =2000
选两点： x1=25 x1=16
x2=25 x2=40
3x1+5x2=200
选两点：x1=0 x1=25
x2=40 x2=25
目标：
S＝50x1+60x2
取S＝300
得 x1=0 x1=6
x2=5 x2=0
x2
45
40 6x1+5x2=300(多余)
35
30 6x1+5x2=300
选两点 x1=20 x1=50
25 x2=36 x2=0
20
15
10
5
0 x1
5 10 15 20 25 30 35 40 45 50 55
等值线 3 x1+5 x2 =200
问题1的最优解：x1=25
x2=25
50 x1+30 x2 =9000
注：图解法解决两个变量的问题比较方便
1、线性规划问题解的定义
可行解：滿足约束条件（2）和（3）的一组x1,x2,x3…xn的取值称为线性规划问题的可行解。所有可行解构成的集合称为线性规划问题的可行解集或可行域
最优解：使目标函数取最大值的可行解称为线性规划问题的最优解。
2、线性规划问题最优解的情况
线性规划问题有无究多个最优解（可行域有界；如果线性规划问题有两个最优解，则有无究多个最优解）
A
B
AB边线与目标函数线平行 AB边上任一点都是最优解
线性规划问题有唯一最优解（可行域有界）
线性规划问题无最优解 可行域无界
可行域是空集
三、线性规划问题的单纯形方法
基可行解与可行基
标准型系数矩阵A=；A的秩等于行数m；其中m＜n ；
A中任取m列用B表示：B=且B为非奇异矩阵(B的行列式值不等于零) ；
如果B非奇异称B为LP问题的一个基，相应的，，…，为基变量；其佘称为非基变量。
令：基B的所有非基变量取值为零，则约束条件方程为：
即：BxB=b
令：xB=( EMBED ，…，)T 得：xB=B-1b
则：xB＝Bb EMBED
如果x=， ，…. ，) ；其中 为非基变量取值为“0”
为基变量取值为“bj0”
则称为基B的基本解；
如果bj0≥0（j=1,2,3….,m）
则称X为基B的基可行解； B为可行基
2、最优解与最优基
C＝（c1,c2,…..,cn） 取CB＝（cj1,cj2,….cjm） 其中CB由基B确定
令：（σ1，σ2…σn）=C-CBB-1A为对应基B的检验数
如果基B为可行基且基B的检验数C-CBB-1A＜0，则称基B为LP问题的最优基，最优基对应的解为最优解（基可行解就是最优解）
结论1：LP问题解的定义与关系
①可行解：满足约束条件和非负条件的决策变量的一组取值。
②最优解：使目标函数达到最优值的可行解。
③基本解：设AX=b是含n个决策变量、m个约束条件的LP的约束方程组，B是LP问题的一个基，若令不与B的列相应的n-m个分量（非基变量）都等于零，所得的方程组的解称为方程组AX=b关于基B的基本解，简称为LP的基本解。
B Pj xj 0
基 m个独立向量组成 基向量 对应之决策变量 基变量 剩余n-m个变量 非基变量
令非基变量取值为零，计算出基变量取值，两者搭配构成基本解。
④基本可行解（对应的基为可行基）：满足非负条件的基本解。
⑤基本最优解（对应的基为最优基）：使目标函数达到最优值的基本可行解。
非可行解 最优解 基本最优解
可行解 基本可行解 基本解
图 LP各种解的关系
结论2：把线性规划问题的求解过程整理成表格，称为单纯形法
3、单纯形法
初始单纯形表：
CB
XB
cj
xj
C1……. Cn Cn+1 Cn+2 …Cn+m
b
X1…… .Xn Xn+1 Xn+2…Xn+m
Cn+1
Cn+2
EMBED
Cn+m
Xn+1
Xn+2
EMBED
Xn+m
b1
b2
bm
a11 …. a1n 1 0… 0
a21… a2n 0 1… ….0
…………………………..
am1… amn 0 0…… 1
-Z
-
C1-…Cn-- 0… 0
问题1初始单纯形表：
CB
XB
cj
xj
C1 C2 C3 C4 C5
b
X1 .X2 X3 X4 X5
0
0
0
X3
X4
X5
2000
300
200
50 30 1 0 0
6 5 0 1 0
3 5 0 0 1
-Z
0
50 60 0 0 0
基B＝（p3,p4,p5）=
x3 x4 x5 基变量
x1,x2 非基变量
基可行解XB＝（0，0，2000,300,200）
基B所对应的检验数=C－CBB－1A＝（50，60,0，0,0）
换基迭代求最优解：
选进基变量（依据δk的取值情况；选xk进基必须δk＞0；一般按小指标原则选择）
确定出基变量（先求θ的值，θ＝min=40
即：用基变量的取值除检验数为正的那一列所对应行的正数
θ＝ min
(确定出基变量：X3（取值等于40所在的那一行基变量）选择轴心项：50
选取迭代运算（计算轴心项所在行和列）：
a: 将出基变量所在行的轴心项元素化为“1” ； 即给所在行各元素除“50”
b: 将轴心项所在列的其它元素化为“0” ；即给出基变量行的元素ד？”±到“其它行”
CB
XB
cj
xj
C1 C2 C3 C4 C5
b
X1 . X2 X3 X4 X5
0
0
0
X1
X4
X5
40
60
80
1 3/5 1/50 0 0
0 7/5 -6/50 1 0
0 16/5 -3/50 0 1
-Z
－2000
0 30 -1 0 0
θ＝min=25
CB
XB
cj
xj
C1 C2 C3 C4 C5
b
X1 . X2 X3 X4 X5
X1
X4
X5
25
25
25
1 0 1/32 0 -3/16
0 0 -3/32 1 -7/16
0 1 -3/160 0 5/16
-Z
2750
0 0 -7/16 0 -75/8
最优解： x1=25 最优值 S＝2750
x2=25
4、单纯形法求解过程的经济解释
求轴心项的经济意义
只考虑生产x1
则x1必须满足条件： 50x1≤2000
6x1≤300
3x1≤200
即x1≤θ＝min=40
换基迭代的解释：
把约束条件的系数化为“0”等于按x1=40进行生产，看资源的剩余情况
x4=60 资源B还余60
x5=80 资源B还余80
把目标函数系数化为“0”等于按x1=40进行生产，判别方案是否最优
例：S=2000+30x2-x3
只要x2>0 目标函数值S还可以增大
5、影子价格
把获得最优解时的检验数称为LP问题的影子价格。
影子价格是A、B、C三种资源在实现最大利润时的一种价格估计，而这种估计是针对具体问题而存在的一种特殊的价格。
(2)7/16 A资源增加一个单位，在其它条件不变的情况下，引起目标函数值的增量
75/8 C资源增加一个单位，在其它条件不变的情况下，引起目标函数值的增量
B资源很多，对生产没有什么限制
影子价格的数值反映了某种资源稀缺的程度(边际度量)
在生产实际中，根据A、B、C的影子价格与市场卖方价格进行比较：
市场价格低于影子价格 买进资源，扩大生产
市场价格高于影子价格民 买出资源，不生产
影子价格是微观价格对市场有调节作用
6、线性规划问题解的性质
线性规划问题的所有可行解构成的可行域是凸集(也可能是无界区域)
线性规划问题的可行域有有限个顶点
线性规划问题的每个基可行解对应可行域的一个顶点
线性规划问题若有最优解，必在可行域的某个顶点上达到
结论：
(1)表格单纯形方法是利用解的性质建立初始单纯形表。先求线性规划问题的一个基可行解(可行域的顶点，一般在原点) ；
检验数C-CBB-1A 若<0，计算终止求得最优解
否则，换基迭代到另一个相邻的顶点，并使目标值增大
相邻的顶点就是新可行解，再利用检验数C-CBB-1A进行判断，继续…
单纯形方法把从无限个可行解中选最优解的问题变为在有限个顶点上进行迭代，并使计算能在有限个步终止 求得最优解
无法换基迭代 无最优解
四、线性规划问题的进一步说明
1、单纯形法的计算机软件求解
由于线性规划问题的可行域是凸多边形或凸多面体，而且如果一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。换言之，若某线性规划只有唯一的一个最优解，那么这个最优解所对应的点一定是可行域的一个顶点，若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。单纯形法的基本思想就是顶点的逐步转移，即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。
现在就以案例2为例，讨论怎样用计算机借助单纯形法求解一个线性规划问题的实施过程。与教材配套的运筹学教材软件中的线性规划程序可以解决线性规划问题的规模依赖于你的计算机的内存，一般，解几十个变量和约束的小型LP是没有问题的。
为了使用单纯形法，必须将所有的约束条件变换成等式，如果约束条件是小于等于类型(()，可以引入非负的松弛变量s1,s2,……；如果约束条件是大于等于类型( ( )，则可以引入非负的剩余变量s1,s2,……；前者在不等式左边加上松弛变量，后者在不等式左边减去剩余变量即可把不等式变为等式了；倘若约束条件已经是等式，通常会在等式左边加入一个非负的人工变量Ai；这样做的目的是使约束方程的系数矩阵中出现一个单位阵，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样出现在单纯形表格中的B(i)列（即约束方程的右边常数）值正好就是基变量的取值。
案例2的线性规划模型是
MaxZ=2x1+3x2+x3
(1-2)
引入松弛变量s1和s2，其中，s1表示结余的工时比例，s2表示结余的原材料，那么上面的模型就可以改写成：
MaxZ=2x1+3x2+x3+0s1+0s2
(1-3)
在使用线性规划程序时，由式（1－2）到式（1－3）的“标准化”过程是自动完成的。
我们只需按提示信息输入该问题的名称（由用户自由输入6个以内的字符）、目标函数的类型（求极大化问题输入“1”，极小化问题输入“2”）、变量和约束条件的个数后，即可输入有关数据（目标函数中决策变量的系数、各约束条件中变量前面的系数及右端常数）。
应注意的是，数据中的分数必须化成小数才能输入，另外约束条件的类型（≤，=，≥等）占用两个字符，不足两个字符时按空格键补足。
输入完成后，可按菜单提示显示或打印输入数据，也可以存盘。
式（1－3）的输入打印结果如表1－3所示。
表1－3 案例2的输入数据打印结果
Input
data
Describing
your
problem
MBA1
Max
+
+
+
subject
to
(1)
+.333300x1
+.333300x2
+.333300x3
<
+
(2)
+.333300x1
+
+
<
+
表1－3中显示，我们将案例2命名为MBA1,另外，变量的非负条件是隐含的，“<”与“(”等同。
如果输入结果存盘，再次利用时可以直接读取。
表1－4为初始表格，最左边一列指明当前的基变量是s1和s2，左边第二列为对应的基变量s1和s2的单位贡献，O表示其单位贡献为0，即s1、s2在目标函数表达式中的系数，B(i)列表示约束方程的右端常数，表格的中间部分相当于约束方程的系数矩阵，表头部分x1、x2、x3、s1、s2显示出问题所包含的所有变量，它们的下方就是对应的变量在目标函数中的系数（称单位贡献或价值系数）。从行来看，表中的第一行分别表示出第一和第二个约束方程。由基变量列和B(i)列我们可以得到初始基本可行解即初始顶点s1=1，s2=3，其余变量称为非基变量，取值为0，即x1=x2=x3=0,这个结果也可以写成
Z(0)=(x1,x2,x3,s1,s2)T=(0,0,0,1,3)T
它对应着图解法中相应可行域的一个顶点－－－坐标原点。其经济意义是：所有产品均不生产，劳动工时和原材料没有动用（全部结余），自然产品总利润为0。
表1－4 初始单纯形表
Basis
c(j)
x1
x2
x3
s1
s2
B(i)
B(i)/A(i,j)
0
0
s1
0
0
0
s2 EMBED
0
0
0
c(i)-Z(j)
*BigM
0
0
0
0
0
0
0
0
0
初始单纯形表的最后一行叫做检验数行，是用来确定解是否还能得到改善的。从本质上讲，它是将目标函数表达式改写成等式形式的一种表达方式，比如该表的最后一行实际上代表了等式 Z=2x1 + 3x2 + x3 = 0 (1-4)
在x1对 在 x2对 在x3对 在B（i）对
应的列 应的列 应的列 应 的列
还要注意这个目标函数表达式有一个特点，即出现的决策变量都是非基变量，也就是用非基变量表示目标函数的表达式。至于BigM所对应的行是在出现人工变量Ai时才用得上，这里没有出现人工变量，所以全用零表示。
考察式（1－4），其中决策变量前面的系数分别是三种产品的单位利润（贡献），如果生产一个单位的产品B，目标函数值将增加3×1＝3（千元）利润，而生产一个单位的产品A或产品C将分别使总利润增加2×1或1×1千元，反之，如果产品的单位利润为负值，那么只要生产该种产品，总利润就会下降。由于问题期望总利润获得为最大值，所以我们总是选择检验数行中最大的正值（此时为3）所对应的变量（此时为x2）取正值（成为基变量），即生产产品B，这样可以使产品总利润获得较大的增加。我们把表1－4中最大正检验数所对应的系数列称为“主元列”。
上面的分析也告诉我们，一旦检验数行（cj-zj行）全部取值都为零或为负数时，目标函数值便再也不能得到改善，即总利润已经达到最大值，相应的基变量的取值也就构成了最优解（最优生产方案）。
接着应该考虑，当把变量x2变成基变量（生产产品B)时，它应取代初始表中的哪一个基变量？因为我们希望生产最多数量的产品以求总利润最大，但是同时又必须满足资源的限制条件，所以必须比较每一种资源允许生产的产品数量。
考虑第一个约束方程，即初始表中基变量S1所在的行。
可利用的总工时比例为1，每吨产品B需花费工时比例为1/3，则最多可能生产产品B的数量为1/=3（吨）。
再考虑第二个约束方程，对应着初始表中基变量S2所在的行。
可利用的原材料总量为3吨，每吨产品B需消耗原材料4/3吨，则所有的原材料最多可供生产产品B的数量为 3÷=（吨）
min（3,）=，因此应当用x2来替换s2,通常称x2为“进基变量”（或换入变量），x2所对应的系数列称为“主元列”；称S2为“出基变量”（或换出变量），S2所在的系数行称“主元行”，而选择出基变量的法则称为“最小比值原则”，也就是由B（i）列与主元列系数的比值中选择最小者。诸比值已列在第一次迭代表格表（1－5）中最右边的B（i）/A（i，j）列。
该表中同时指明了进基变量（Entering）为x2，出基变量（Leaving）为S2，及当前产品总利润Current objective function value （Max）=0。
表1－5 Iteration 1
Basis
c(j)
x1
x2
x3
s1
s2
B(i)
B(i)/A(i,j)
0
0
s1
0
0
s2 EMBED
0
0
c(i)-Z(j)
*BigM
0
0
0
0
0
0
0
0
0
Current objection function value (Max.)=0
(Highlighted variable is the entering or leaving variable)
Entering：x2 Leaving：s2
主元列和主元行的交叉处元素称为“主元素”，程序中通过矩阵的初等行变换（即约束方程的同解变换）把主元素变为1，把主元列的其他元素（包括检验数行所对应的相应元素）变为0。这样出现在迭代表格中基变量S1和x2对应的系数列仍然构成一个二阶单位阵，从而B（i）列的值恰好就是基变量S1和x2的取值，检验数行和B（i）列交叉处元素也正好就是总利润的值。检验数行仍然对应着非基变量表示目标函数的表达式。这一步的迭代结果见表1－6。
表1－6 Iteration 2
Basis
c(j)
x1
x2
x3
s1
s2
B(i)
B(i)/A(i,j)
0
0
s1
0
0
x2
0
c(i)-Z(j)
*BigM
0
0
0
0
0
0
0
Current objection function value (Max.)=
(Highlighted variable is the entering or leaving variable)
Entering：x1 Leaving：s1
从上表的基变量列（Basic ）和B（i）列可以看出：S1=, x2=, 也就是说当前解（即现行生产方案）为X(1)=(0,,0,,0)T,其经济解释为：只生产B产品吨，不生产A、C两种产品，总工时节余四分之一（），此时产品总利润可达到Z(1)=。X(1)对应着图解法求解该案例时可行域中的C点（见图1－5）。
此时检验数行仅有唯一的正值 ,对应着非基变量x1，因此应继续迭代，选x1对应的列为主元列，B（i）列与主元列的比值中选取较小的对应的S1所在的行为主元行，也就是选x1为进基变量，S1为出基变量，进行换基迭代得表1－7。
表1－7 Final tableau (Total iteration =2)
Basis
c(j)
x1
x2
x3
s1
s2
B(i)
B(i)/A(i,j)
0
0
x1
0
-1
0
x2
0
0
C(i)-Z(j)
*BigM
0
0
0
0
0
0
0
0
(Max.)Optimal OBJ value =
该表中检验数行全部为非正值，所以产品总利润已经得到最大值，由基变量列和B（i）列可知：
x1=, x2= 目标函数最大值为
表明最优解为X*=(,,0,0,0)T, 产品最大总利润为Zmax=。由于这些最终数据均出现在B(i)列，所以通常也把B(i)列称为解答列。
表1－7是经过两次迭代得到的最终表，所得结果的经济意义是：最优生产计划为安排生产A产品1吨，B产品2吨而不生产C产品，此时全部工时和原材料均用完而无结余（因为S1=S2=0）,产品总利润将达到最大为（或）千元。
将单纯行法求解结果与图1－5相对照可以发现，最优解X*正好对应着可行域中的B点，也就是用图解法求解得到的最优点。
案例2的单纯形法求解过程就是从可行域的一个顶点（坐标原点）出发，按照一定的规则迭代寻求另一个顶点（第一步转移到C点，第二步从C点转移到B点）的过程，每一次顶点转移的结果都使目标函数值得到改善（产品总利润从0上升到,又上升到），当目标函数值不能再改善时，相应的现行顶点B就是最优解，它对应着一个最优生产计划X*和一个产品最大总利润Zmax=。
单纯形法小结
(1)求解思想－－顶点的逐步转移，条件是使目标函数值不断得到改善。
(2)表格单纯形法求解步骤
第一步：将LP化为标准型，并加以整理。引入适当的松驰变量、剩余变量和人工变量，使约束条件化为等式，并且约束方程组的系数阵中有一个单位阵。（这一步计算机可自动完成）。
第二步：选择最大正检验数（最小负检验数）对应的系数列为主元列，最小比值对应的行为主元行，从而确定进基变量和出基变量。
第三步：利用矩阵的初等行变换（方程的同解变换）把主元列变成单位向量，主元素变为1，进基变量对应的检验数变成0，从而得到一张新的单纯形表，返回第二步。
该迭代过程直至检验数行全部变为非正值（非负值）时停止。
对极小化线性规划，只需将第二步、第三步有关原则改用括号中的规则即可。
(3)计算机求解时的注意点：
第一：输入数据中如有分数，需先化为小数再执行输入过程。
第二：每一张迭代表格中由基变量列（Basic）和B(i)列（解答列）可以读出现行解及相应的目标函数值，同时显示进基变量和出基变量，从而很容易识别主元列、主元行和主元素。
第三：最终表显示最优解、最优目标函数值及总的迭代次数。如遇该线性规划无可行解或无“有限最优解”，则屏幕将显示有关信息：
NO feasible solution . 或
* * unbounded solution !!!
2、灵敏度分析
当一个线性规划求解完毕，得出了最优解及目标函数最优值后，并不意味着工作的结束，相反，还应该继续作一些更有意义的事情－－优化后分析或灵敏度分析，以便帮助决策者利用线性规划去发现和解决实际问题中的各种关键环节并起到辅助决策的作用。
所谓灵敏度分析就是研究线性规划模型某些系数或限制量的变化对最优解的影响及影响程度的分析过程。
当我们用图解法或单纯形法求解一个线性规划时，目标函数及约束条件中决策变量的系数以及资源的限制量等都是确定的常数，而最优解正是在这些确定数值的基础上计算得到的。实际上，这些系数或资源限制量并不是一成不变的，比如价值系数会随着市场营销情况而波动，资源限制量往往是预测或估算的，各种资源的消耗定额会随着工艺的改革、新技术被采用、劳动力的合理调配及补充等因素而发生变动，至于未来产品的需求量等更是存在着不确定甚至不可控的因素，那么当这些系数发生变化时最优解会受到什么影响？最优解对哪个参数的变动感觉最灵敏？对这些问题的研究讨论将会帮助决策者在处理实际管理问题时，具有更大的主动性和可靠性。下面我们就几个专题分别加以研究。
(1)关于“影子价格”的讨论
在介绍案例1的对偶规划时，我们曾提到“影子价格”这个名词，其确切的定义是：一个线性规划对偶问题的最优解（简称为“对偶最优解”）。在经济上可以解释为约束条件所付出的代价。
从案例1及其对偶规划的求解结果可以看出，当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的，即有
Zmax=CX*=2x*1+3x*2+x*3=Wmin=y*b=y*1+3y*2=8
其中X*就是原问题的最优解，y*就是对偶问题最优解。从前面的求解结果已经知道
X*=(x1,x2)T=(1,2)T
Y*=(y1,y2)=(5,1)
如果原材料供应量能增加一个单位，即右端常数向量b=(b1,b2)T=(1,3)T中的b2从3个单位增加到4个单位，那么目标函数值的变化量将为
（y*1+4y*2)-(y*1+3y*2)=y*2=1
即目标函数将增加一个单位，这就是放宽一个约束条件所产生的附加贡献。这样，影子价格确定了为得到一个附加单位的约束因素所应花费的成本上限。
用单纯形法求解一个线性规划时，在求得最优解的同时也就求得了对偶最优解，这可以从迭代的最终表格中看出来。我们回过头来看案例2的单纯形迭代最终表－－表1－7：
一方面从基变量列和解答列可以迭代原问题的最优解和目标函数最优值：
X*=(x1*,x2*,x3*,s1*,s2*)Τ=(,,0,0,0)T
Zmax=
另一方面从检验数行可以得到对偶最优解和对偶问题的目标函数最优值，只要将所有非基变量的检验数变号，得到
Y*=(y*1,y*2,s1,s2,s3)T=(,,0,0,)T
Wmin=
先解释一下Y*的各分量与X*的对应关系。
原问题有两个约束条件对应着对偶问题的两个变量。表1－7中的S1、S2分别表示两个约束条件中剩余的资源量，它们所对应的检验数的相反数就正好是对应的两个对偶变量即 Y*1=,Y*2=，而x1，x2，x3所对应检验数的相反数分别对应着对偶问题中三个约束条件的剩余变量，即s1=0,s2=0,s3=。
y*1=表示如果总工时比例增加1个单位（即总工时翻一番），则产品总利润将增加5千元，y*2=则表明若原材料增加1吨，产品总利润将增加1千元。
而s3=则说明如果生产一个单位的产品C，将使产品总利润下降3千元。
由上面的分析可以判断出，目前最敏感的资源在于劳动工时，它的变化对产品总利润的影响最大，因此劳动力是最关键的生产环节，若能采取有力措施增加劳动总工时，则产品总利润将得到较大的提高。
在计算机求解结果中将约束条件的影子价格和变量的机会成本统称为机会成本（opportunity cost）,见表1～8。
综上所述，影子价格是灵敏度分析的一种形式，因为它通过获取一个单位的追加的产品因素，去测量放宽一个约束条件的价值，比较追加资源的价值和资源的实际成本，就能比较有把握地作出各种可行的决策。
表1～8 MBA1问题的求解结果总表
Summarized
Resulted for
MBA1
Variables
Opportunity
Variables
Opportunity
No. Names
Solution
Cost
No. Names
Solution
Cost
1 x1
4 s1
2 x2
5 s2
3 x3
Maximum
value of
the OBJ
=
Iters.=2
(2)关于保持线性规划最优解不变的余数范围的讨论
①关于目标函数系数的变化范围。
利用计算机软件中线性规划的灵敏度分析功能，以案例2为例，可得到如下的输出结果（表1～9）：
表1～9 案例2的灵敏度分析表
Sensitivity
Analysis
for OBJ
coefficients
Page：1
c(j)
(j)
Original
(j)
c(j)
(j)
Original
(j)
c(1)
c(3)
-infinity
c(2)
表中价值系数的原始值位于Original一栏，Min(j)栏及Max(j)栏给出了相应价值系数的变化范围，如x1价值系数c(1)原始值为2，其变化范围最小值为，最大值为3，就是说当c(1)在(,(的范围中变化时，最优解不变。换言之，当产品A的单位利润大于等于且小于等于时，不必修改生产计划，原来的最优解仍然是最优生产计划。类似地，当产品B的单位利润在区间(2，(之间波动或产品C 的单位利润在区间(－(，(之间波动时均不影响最优生产计划。
②关于约束方程右边常数的变化范围
案例2的右边常数灵敏度分析输出结果见表1－10
表1－10 案例2的右边常数灵敏度分析输出表
Sensitivity
Analysis
for RHS
Page：1
B(i)
Min. B(i)
Original
Max. B(i)
B(i)
Min. B(i)
Original
Max. B(i)
B(1)
B(2)
该表格显示约束方程的右端常数原始值分别为B(1)= (总工时比例)和 B(2)=(原材料供应限制)。
当B(1) ((,(或B(2)((,(时最优解的结构不变（也叫最优基不变)，意思是基变量保持不变，即保持生产的品种不变，但生产的数量会随着B(i)的变化而有所变化。
(3)、当系数变化超出上述范围的讨论
当系数的变化超出了上述范围或是约束方程的系数矩阵中元素有增减变化，比如单位产品消耗定额发生变化，增加一个新产品品种，增加或减少一个约束条件等等，一般来说最优解会发生变化，也即原先的最优生产计划已不再是最优的，此时，可以利用程序中的修改功能（Modify problem)方便地修改原线性规划模型，然后很快地求出新的最优解。下面我们仍以案例2为背景讨论可能出现的各种情况。
当产品C的单产利润由1变为6时，由于x3的价值系数已超过了灵敏度分析的范围，所以可以利用修改功能中的修改目标函数一项，将C(3)修改为6，经两步迭代即可求得新的最优解 x1=2, x3=1，也就是新的生产计划应为生产A产品2吨，C产品1吨而不生产B产品，此时可得产品最大总利润为Zmax=。由于s1=s2=0，所以工时和原材料全部用完而无节余。进一步分析s1和s2的机会成本分别为和,所以此时劳动工时资源比原材料资源更为敏感和关键。如果我们在此基础上将劳动工时翻一番，即总工时比例由1变为2，利用修改功能中的修改一个约束条件将B(1)改为2，经两步迭代可得下面的迭代结果(表1－11)。
表1－11 案例2灵敏度分析（总工时比例变为2时求解结果）
Summarized
Resulted for
Page：1
Variables
Opportunity
Variables
Opportunity
No. Names
Solution
Cost
No. Names
Solution
Cost
1 x1
4 s1
2 x2
5 s2
3 x3
Maximum
value of
the OBJ
=
Iters.=2
目标函数值由原先的增加到,新增的部分恰好等于总工时约束中松驰变量s1的机会成本。
表1－11还显示最优生产计划应改变为生产A产品吨，C产品吨，从机会成本的比较中发现，倘若还可以增加劳动工时，产品总利润还将提高，右边常数的灵敏度分析输出结果(见表1－12）告诉我们劳动总工时一直增加到3以上时，上述工时紧张的局面才能得到缓和。
表1－12 案例2右边常数的灵敏度分析输出结果
Sensitivity
Analysis
for RHS
Page：1
B(i)
Min. B(i)
Original
Max. B(i)
B(i)
Min. B(i)
Original
Max. B(i)
B(1)
B(2)
倘若工厂试制了一种型产品D ，已知单位产品D需消耗全部现有工时和1吨原材料，单位利润为3千元，需作出是否投产的决策。利用修改功能中的“增加一个变量”项，可以方便地将原模型修改成
max Z=2x1+3x2+x3+3x4
（1-5）
求解的结果（见表1－13）表明x4=0，即不宜投产，由x4对应的机会成本为知道，若一定要投产，则每投产1吨，产品总利润将下降。而从资源上来讲，关键还在于劳动工时，每增加一个劳动工时比例，产品总利润将上升千元。
表1－13 式（1-5）求解结果输出
Summarized
Resulted for
Variables
Opportunity
Variables
Opportunity
No. Names
Solution
Cost
No. Names
Solution
Cost
1 x1
4 x4
2 x2
5 s1
3 x3
6 s2
Maximum
value of
the OBJ
=
Iters.=2
进一步，表1－14所显示的目标函数系数灵敏度分析输出结果告诉我们，c(4)的系数范围是（－(,(，说明产品D的单位利润不能超过时，生产该产品是无利可图的。
表1－14 式（1-5）目标函数系数灵敏度分析输出结果
Sensitivity
Analysis
for OBJ
coefficients
Page：1
c(j)
Min. c(j)
Original
Max. c(j)
c(j)
Min. c(j)
Original
Max. c(j)
c(1)
c(3)
-infinity
c(2)
c(4)
-infinity
最后，我们再来讨论增加一个约束条件的情况。
倘若给案例2增加一个设备约束，即可利用的设备生产能力只有4个单位，且已知A、B、C三种产品的定额生产能力分别为1，2，1。这就意味着增加一个新的约束条件：
x1+2x2+x3 ( 4
模型的修改很容易，只需调用修改功能中的“增加一个约束条件”即可。在模型式（1-5）基础上经两步迭代得出最优结果为表1－15。
表1－15 增加一个约束条件后的求解结果输出
Summarized
Resulted for
Variables
Opportunity
Variables
Opportunity
No. Names
Solution
Cost
No. Names
Solution
Cost
1 x1
4 x4
2 x2
5 s1
3 x3
6 s2
Maximum
value of
the OBJ
=
Iters.=2
结果表明，由于增加了约束条件，使产品总利润下降至。此时的最优生产计划是生产A产品吨，B产品吨。若要生产产品C，则每生产一个单位C将使产品总利润下降1千元。目前生产的关键所在仍在资源方面。劳动工时和生产能力全部饱和而无剩余，两者相比，劳动工时资源更为灵敏，若能增加一个劳动总工时比例，产品总利润将会上升。但表1－16显示B(1)的上限为，就是说上述总利润上升的状况仅在劳动总工时比例不超过时才能保持。一旦超出这个界限，矛盾就将转化。另外，原材料将节余吨，这种资源的不平衡是影响总利润的一个主要原因，闲置的资源必然造成浪费，但这仅仅是一种表象。由于B(1)和B(3)的可波动范围都很小：(B(1) (，(B(3) (，因此要打破目前的小范围可调局面应该采取更加有力的措施，比如调整产品结构，大幅度扩大资源来源等等，在此基础上进一步作定量分析，可能会有更大的成效。
表1－16 增加一个约束条件后右端系数的灵敏度分析
Sensitivity
Analysis
for RHS
coefficients
Page：1
B(j)
Min. B(j)
Original
Max. c(j)
B(j)
Min. c(j)
Original
Max. B(j)
B(1)
B(3)
B(2)
+infinity
3、线性规划问题的一般方法技术(2阶段法)
问题：max S=CX 形成新问题
AXb 约束条件增加人工变量 maxZ=-xn+1-xn+2-…-xn+m
x>0 第一阶段 =bi (i=1..n)
x1,x2…xn>0 划去人工变量所在的列
求解新问题：１)新问题的最优解中人工变量均为非基变量 约束条件的系数矩阵有一个单位阵 原问题的初始基可行解；
2)新问题的最优解中人工变量不为0且最优值Z<0，说明原问题无可行解；
3)新问题的最优值为0，有人工变量在基变量中，这时基中的人工变量取值为0，只要选某个不是人工变量的非基变量进基，把在基中的人工变量替换出来，就回到1)的情形。
以第一阶段的基可行解作为初始基可行解建立初始单纯形表进行计算
第二阶段
4. 线性规划问题的对偶问题
问题1的对偶问题： minW=
50y1+6y2+3y3>50 (出卖大于生产品的价格)
30y1+5y2+5y3>60 (出卖大于生产品的价格)
y1,y2,y3>0
问题：不生产产品P1和P2，将资源A、B、C出卖，yj为A、B、C资源的出卖价格。
原问题与对偶问题间的关系(讲义)
对偶问题的性质(讲义)
应用：证明题
利用对偶定理证明下列线性规划问题无最优解
maxS=x1-x2+x3
x1-x3>4
x1-x2+2x3>3
x1>0,x2>0,x3>0
证：由于x0=(5,1,0)满足 x1-x3>4
x1-x2+2x3>3
x1>0,x2>0,x3>0
所以x0是此规划问题的可行解
原问题的对偶问题为：
minW=4y1+3y2
y1+y2>1
-y2>-1
-y1+2y2>1
y1<0,y2<0
由对偶问题的约束条件可知对偶问题无可行解
又根据对偶理论：原问题有可行解。对偶问题无可行解，则原问题无最优解可知，故此规划问题无最优解。
PAGE
PAGE 2
