《运筹学》讲义
运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。运筹学的核心思想是建立在优化的基础上。
例如，在线性规划中体现为两方面：
（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？
（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？
运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科学依据。
随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解已有相应的软件。因此，在实际求解计算时常可借助于软件在计算机上进行，这样可以节省大量的人力和时间。
第一部分 线性规划内容框架
LP问题基本概念 数学模型 可行解、最优解实际问题 LP问题 解的概念 基本解、基可行解提 出 基本最优解
基本方法
图解法
原始单纯形法
单纯形法 大M法
人工变量法
对偶单纯形法 两阶段法
对偶理论
进一步讨论
灵敏度分析──参数规划*
在经济管理领域内应用
运输问题（转运问题）
特殊的LP问题 整数规划
多目标LP问题*
第一部分 线性规划（Linear Programming）及其应用
第一章 LP问题的数学模型与求解
§1 LP问题及其数学模型
（一）引例1（生产计划的问题）
某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获的利润如下表所示。问应如何安排计划使该工厂获利最多？
Ⅰ
Ⅱ
资源限量
设备
1
2
8(台时)
原材料A
4
0
16(kg)
原材料B
0
4
12(kg)
单位产品利润（元）
2
3
该问题可用一句话来描述，即在有限资源的条件下，求使利润最大的生产计划方案。
解：设x1,x2分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。由于资源的限制，所以有：
机器设备的限制条件：x1+2x2≤8
原材料A的限制条件,4x1≤16 （称为资源约束条件）
原材料B的限制条件,4x2≤12
同时，产品Ⅰ、Ⅱ的产量不能是负数，所以有
x1≥0，x2≥0 （称为变量的非负约束）
显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1，x2以得到最大的利润，即使目标函数
Z=2x1+3x2 的值达到最大。
综上所述，该生产计划安排问题可用以下数学模型表示：
maxz=2x1+3x2
引例2,（营养配餐问题）
假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小？
序号
食品名称
热量(卡路里)
蛋白质(克)
钙(mg)
价格(元)
1
猪肉
1000
50
400
10
2
鸡蛋
800
60
200
6
3
大米
900
20
300
3
4
白菜
200
10
500
2
解:设xj(j=1,2,3,4)为第j种食品每天的购买量，则配餐问题数学模型为
minz=10x16x23x32x4
（二）LP问题的模型上述两例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有共同的特征。
（1）每个问题都可用一组决策变量(x1,x2,…xn)表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。
（2）存在一组线性等式或不等式的约束条件。
（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。
满足以上三个条件的数学模型称为LP的数学模型，其一般形式为：
max(或min)z=c1x1+c2x2+…+cnxn (1.1)
(1.2)
或紧缩形式
max(或min)z=
(1.4)
或矩阵形式
max(或min)z=cx
(1.5)
或向量形式：
max(或min)z=cx
(1.6)
其中C=(c1,c2,…,cn)，称为价值系数向量；
称为技术系数矩阵（并称消耗系数矩阵）
=(p1,p2,…,pn)
称资源限制向量
X=(x1,x2,…,xn)T称为决策变量向量。
（三）LP问题的标准型
1.为了讨论LP问题解的概念和解的性质以及对LP问题解法方便，必须把LP问题的一般形式化为统一的标准型：
maxz=；
或
maxz=cx
或
标准型的特点：
①目标函数是最大化类型
②约束条件均由等式组成
③决策变量均为非负
④bi(i=1,2,…,n)
2.化一般形式为标准型
①minz(max(-z)=-cx
②“(”(左边+松驰变量；“(”(左边－“松驰变量”
③变量xj(0(-xj(0变量xj无限制(令xj=xj(－xj(
④bi<0(等式两边同乘以(-1)。
3.模型隐含的假设
①比例性假定：决策变量变化的改变量与引起目标函数的改变量成比例；决策变量变化的改变量与引起约束方程左端值的改变量成比例。此假定意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数。
②可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其它变量的。
③连续性假定：决策变量应取连续值。
④确定性假定：所有的参数(aij,bi,cj)均为确定，所以LP问题是确定型问题，不含随机因素。
以上4个假定均由于线性函数所致。在现实生活中，完全满足这4个假定的例子并不多见，因此在使用LP时必须注意问题在什么程度上满足这些假定。若不满足的程度较大时，应考虑使用其它模型和方法。如非线性规划，整数规划或不确定型分析方法。
对LP标准型，我们还假定r(A)=m<n。
（四）LP问题的解的概念设LP问题
maxz= (1.7)
(1.8)
(1.9)
1.从代数的角度看：
可行解和最优解 满足约束条件(1.8)和(1.9)的解X=(x1,x2,…,xn)T称为可行解。所有可行解构成可行解集，即可行域。而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。
求解LP问题就是求其最优解和最优值，但从代数的角度去求是困难的。
2.从LP角度看：
基：设A为mxn矩阵，r(A)=m，B是A中的mxm阶非奇异子矩阵（即|B|(0），则称B是LP问题的一个基。
若B是LP问题的一个基，则B由m个线性独立的列向量组成，即B=(Pr1,Pr2,…,Prm)，其中Prj=(a1rj,a2rj,…,amrj)T，(j=1,2,…,m)称为基向理。与其向量Prj相对应的变量xrj称为基变量，其它变量称为非基变量。显然，对应于每个基总有m个基变量，n－m个非基变量。
基本解与基可行解 设B是LP问题的一个基，令其n－m个非基变量均为零，所得方程的解称为该LP问题的一个基本解。显然，基B与基本解是一一对应的，基本解的个数≤Cmn。在基本解中，称满足非负条件的基本解为基可行解，对应的基称为可行基。
退化解 如果基解中非零分量的个数小于m，则称此基本解为退化的，否则是非退化的。
最优基 如果对应于基B的基可行解是LP问题的最优解，则称B为LP问题的最优基，相应的解又称基本最优解。
3.LP问题解之间的关系如图所示
(
（五）两个变量LP问题的图解法
1.LP问题解的几何表示。以引例为例说明
maxz=2x1+3x2
按以下顺序进行：
解：（1）画出直角坐标系；
（2）依次做每条约束线，标出可行域的方向，并找出它们共同的
可行域；
（3）任取一目标函数值作一条目标函数线（称等值线），根据目标函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函数线接触的最终点即表示最优解。
图1
其中，将目标函数Z=2x1+3x2改写为，因此，它可以表示为：以z为参数，以为斜率的一族平行线。位于同一条直线上的点具有相同的值。
解的几种情况：
（1）此例有唯一解Q2，即x1=4,x2=2,z=14
（2）有无穷多最优解（多重解），若将目标函数改为z=2x1+4x2则线段Q2，Q3上的点均为最优解。
（3）无界解
求max无界但求min有唯一解
（4）无可行解
可行域与最优解间的关系：
可行域 最优解
空 集 无最优解（无可行解）
有界集 唯一最优解
多重解
无界集 无有限最优解（无界解）
结论：（1）LP问题的可行域是凸集（凸多边形，凸多面体，…）；
（2）LP问题最优解若存在，则必可在可行域的顶点上得到；
（3）LP问题的可行域的顶点个数是有限的；
（4）若LP问题有两个最优解，则其连线上的点都是最优解。因此，求解LP问题可转化为如何在可行域的顶点上求出使目标函数值达到最优的点的问题。
2.基可行解的几何意义
对例1 LP问题标准化为 maxZ=2x1+3x2
可求得所有的基本解：
x(1)=(0,0,8,16,12)T(0点),x(2)=(4,0,4,0,12)T(Q1点)
x(3)=(4,2,0,0,4)T(Q2点),x(4)=(2,3,0,8,0)T(Q3点)
x(5)=(0,3,2,16,0)T(Q4点),x(6)=(4,3,-2,0,0)T(C点)
x(7)=(8,0,0,-16,12)T(A点),x(8)=(0,4,0,16,-4)T(B点)
但A、B、C三点是非可行域上的点，即非可行解。因此，x(1)，x(2)，x(3)，x(4)，x(5)才是基可行解，它们与可行域的顶点相对应。于是还有结论：（5）对于标准型的LP问题，X是基可行解的充要条件是X为可行域的顶点。
（6）LP问题可行域顶点的个数=基可行解的个数≤基的个数≤Cmn
3.图解法只适用于两个变量（最多含三个变量）的LP问题。
4.求解LP问题方法的思考：
①完全枚举法，对m、n较大时，Cmn是一个很大的数，几乎不可能；
②从可行域的一个顶点（基可行解）迭代到另一个顶点（基可行解）。
§2 单纯形法与计算机求解
1.解LP问题单纯形法的基本思路：
求出一个初始基可行解
y
判别此基可行解是否最 优 解
N
求出使目标函数值得到改善的基可行解
2.单纯形法的计算步骤（表格形式）
（1）建立初始单纯形表，假定B=I，b≥0
设maxZ=c1x1+c2x2+…+cnxn
将目标函数改写为：-Z+c1x1+c2x2+…+cnxn=0
把上述方程组和目标函数方程构成n+1个变量，m+1个方程的方程组，并写成增广矩阵的形式：
-Z x1 x2 … xm xm+1 … xn
0 1 0 … 0 1m+1 … 1n 1
0 0 1 … 0 2m+1 … 2n 2
0 0 0 … 1 mm+1 … mn m
-1 c1 c2 … cm cm+1 … cn 0
以非基变量表示基变量形式代入Z中的基变量,有
令
于是
因此，上述的增广矩阵就可写成：
Z x1 x2 … xm xm+1 … xn
0 1 0 … 0 1m+1 … 1n 1
0 0 1 … 0 2m+1 … 2n 2
0 0 0 … 1 mm+1 … mn m
1 0 0 … 0 …－cn
再令
则上述增广矩阵可写成下面表格形式：即初始单纯形表T（B）
Cj
C1……Cm
cm+1……cn
(i
CB
xB
x1……xm
xm+1……xn
C1
x1
1
1……0
a1m+1……a1n
C2
x2
2
0……0
a2m+1……a2n
：
：
：
：,
：………：
Cm
xm
m
0……1
amm+1……amn
Z
Z0
0……0
(m+1……(n
((j检验数行
上述初始单纯形表可确定初始可行基和初始基可行解：
B=(P1,P2,…,Pm)=I,x=(b1,b2,…,bm,0……0)T
从初始单纯形表建立的过程可以看到以下事实：
（1）凡LP模型中约束条件为“≤”型，在化为标准型后必有B=I，如果b≥0，则模型中约束方程的各数据不改变符号照抄在表中相应的位置。目标函数非基变量的系数则以相反数填入检验数行各相应位置。
（2）在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应的检验数均为零。
（3）
更好表现一般规律的在矩阵形式的单纯形表中设MaxX=CX MaxZ=CX+0XL
其标准型为
将系数矩阵(A,I)分划为(B,N,I)，其中B为可行基，对应于基变量向量XB,N对应于XN，I对应于XL,(XN,XL)为非基变量向量。于是(X,L)T=(XB,XN,XL)T,(C,0)=(CB,CN,0)。因此，矩阵形式的LP模型改写为：
(
用非基变量向量表示基变量向量，有
XB=B-1b－B-1NXN－B-1XL
代入目标函数中有
Z =CB(B-1b－B－1NXN－B-1XL)+CNXN+0XL
=CBB-1b－CBB-1NXN－CBB-1XL)+CNXN
=CBB-1b－(CBB-1N－CN)XN－CBB-1XL
将
写成对应于基B的矩阵形式的单纯形表T（B）：
C(
CB
CN
CL
XB
XN
XL
XB
1
B-1N
B-1
Z
CBB-1b
0
CBB-1N－CN
CBB-1
例如将例1 化成标准型后如下表T（B）：
Cj
2
3
0
0
0
(i
CB
XB
x1
x2
x3
x4
x5
0
x3
8
1
2
1
0
0
0
x4
16
4
0
0
1
0
0
x5
12
0
4
0
0
1
-Z
0
-2
-3
0
0
0
(σj
初始可行基B=(P3,P4,P5)=I,X=(0,0,8,16,12)T
（2）判别最优解
1( 在T(B)中，若所有的检验数σj≥0 (j=1,2,…,n)
则B为最优基，相应的基可行解为最优解，停止计算。
2( 在T(B)中，若有σk<0 (1(k(n)，且xk的系数列向量Pk(0，则该问题无界，停止计算。否则转入（3）
（3）换基迭代（基变换）
1( 先确定入基变量Xk,k=min{j| (j<0}
2( 按最小比值原则确定出基变量xL：
3( 以为主元，进行初等行变换（又称旋转变换）即将列向量变换为单位列向量：
返回（2）。
换基迭代的关键在于将换入变量对应的列向量用初等行变换方法变换成单位列向量。其中主元变成1。即
第L个分量如果在最终表中有非基变量的检验数为0，则该问题有多重最优解。
3.单纯形法的进一步讨论──用人工变量法求初始基可行解
（一）人工变量法若对LP模型标准化后，不具有B=I时，如何办？此时可采用人工变量法得到初始基可行解。
所谓人工变量法是在原问题不含有初始可行基B=I的情况下，人为的对约束条件增加虚拟的非负变量（即人工变量），构造出含有B=I的另一个LP问题后求解。当增加的人工变量全部取值为0时，才与原问题等价。这样，新问题将有一个初始基可行解（以人工变量为基变量），可用单纯形法进行迭代。经迭代后，若人工变量全部被换成非基变量，则原问题的约束条件被恢复，同时也得到一个基可行解。在最终表中若不能全部被换出，则说明原问题无可行解。
因此，该法的关键在于将人工变量全部换出。
人工变量法常见的有大M法和两阶段法。
（1）大M法（通过下例简略介绍其方法与步骤）
例，用大M法求解
MinZ=x1+1.5x2
解：MinZ=x1+1.5x2+0.x3+0.x4+Mx5+Mx6
其中x3,x4为松驰变量，x5,x6为人工变量，M为任意大的正数。
注意到：①分别在约束条件增加人工变量x5,x6是为了构成“人工基”
②对于Min的目标函数采用(+M)，而对于Max的目标函数则采用(-M)作为人工变量的系数,是强加于人工变量的一种惩罚,其目的是为了强制人工变量由变量转为非基变量，使之恢复原问题，或与原问题等价。
③对于minZ判别最优性准则应是Cj－Zj≤0。
④大M法适合于手算，不适用于计算机求解。
（2）两阶段法第一阶段：不考虑原问题是否存在基可行解；给原LP问题的约束条件加入人工变量，构造仅含人工变量的目标函数并要求实现最小化（即使原LP问题目标函数是求最大化）的辅助问题：
MinW=xn+1+…+xn+m
然后用单纯形法求解（1）。若W(0，则原问题无可行解，停止计算。若W=0，且所有的人工变量均为非基变量，则去掉人工变量后可得到原问题的基可行解；如果人工变量中含有为0的基变量时（即退化解），则可再进行初等行变换将其换出，从而获得原问题的基可行解。
第二阶段：在第一阶段所得的基可行解的基础上，将最终表中的人工变量列删去，同时将人工目标函数行换入原问题的目标函数作为第二阶段计算的初始表。
仍以上例为例用两阶段法求解。
MinZ=x1+1.5x2+0x3+0x4
原问题：
MinW=x5+x6
辅助问题：
书中第19页表2.9和表2.10的说明：（1）第一阶段的初始表中非基变量的检验数=人工变量所在行的非基变量相应系数之和，目标函值值=人工变量所在行相应常数之和。
（2）第二阶段单纯形表中目标函数系数应将非基变量表示基变量后所得结果填入，或先直接填入原系数，再通过初等行变换使基变量的检验数为0。
（3）若maxZ，则可转化为minZ1(Z1=-Z)
（二）退化单纯形法计算中用(规则决定换出变量时，有时出现两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于0，出现退化解，如某个最大化问题的单纯形表为：
Cj
4
0
3
0
0
0
(i
CB
XB
x1
x2
x3
x4
x5
x6
0
x5
6
2
0
1
0
1
0
3
0
x4
3
[1]
-1
0
1
0
0
3
0
x6
5
1
1
1
0
0
1
5
Z
0
-4
0
-3
0
0
0
((j
0
x5
0
0
[2]
1
-2
1
0
0
4
x1
3
1
-1
0
1
0
0
/
0
x6
3
0
2
1
-1
0
1
1
Z
12
0
-4
-3
4
0
0
((j
在出现退化解后的继续迭代中，有可能出现基循环：
B1(B2(……(B1
这样迭代下去便永远得不到最优解。
解决基循环的方法很多，如“摄动法”、“字典序法”等等。
在计算机上常采用“Bland规则”：
（1）取表中下标最小的非基变量xk为换入变量，即
k=min{j | (j>0}
（2）按(规则计算，若存在两个相同以上最小比值时，选取下标最小的基变量为换出变量xL，即
值得庆幸的是出现基循环是罕见的。
§3 对偶理论与灵敏度分析
一、LP的对偶问题
1.引例 前已述引例1是一个在有限资源的条件下，求使利润最大的生产计划安排问题，其数学模型为：
maxZ=2x1+3x2
现从另一角度考虑此问题。假设有客户提出要求，租赁工厂的设备台时和购买工厂的原材料A、B，为其加工生产别的产品，由客户支付台时费和材料费，此时工厂应考虑如何为每种资源的定价问题？
解：设y1,y2,y3分别表示出租单位设备台时的租金和出售单位原材料A、B的价格（含附加值）
工厂决策者考虑：
（1）出租设备和出售原材料应不少于自己生产产品的获利，否则不如自己生产为好。因此有
工厂的总收入为 W=8y1+16y2+12y3
（2）价格应尽量低，否则没有竞争力（此价格可成为与客户谈判的底价）
租赁者考虑：希望价格越低越好，否则另找他人。
于是，能够使双方共同接受的是
MinW=8y1+16y2+12y3
上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶问题。
2.从矩阵形式讨论互为对偶LP问题由例1 有maxZ=cx
由矩阵形式的单纯形表中可知：
检验数的表达式为： CBB-1N－CN和CBB-1
当
表示LP问题已得到最优解令Y=CBB-1,且②有Y(0
由于基变量XB的检验数为0，可改写成CBB-1B－CB=0
因此，包括基变量在内的所有检验数可写成
(CBB-1B－CB,CBB-1N－CN)=(CBB-1A－C)= YA－C≥0
即YA(C
又对② Y=CBB-1，两边右乘b，有
Yb=CBB-1b=Z
由于Y无上界，所以只有最小值，因此有
MinW=Yb
它是原问题 {maxZ=CX| AX(b,X(0}的对偶问题于是，对称形式下两个互为对偶LP问题的数学模型为：
MaxZ=CX MinW=Yb
与
任何一个LP问题均有一个对偶LP问题与之匹配。
对偶理论就是研究LP问题及其对偶问题的理论，它是LP理论中的重要内容之一。
二、对偶理论
1.原问题与对偶问题的关系如下表所示原 始 对 偶 表原问题Max（对偶问题）
对偶问题Min（原问题）
约束条件数=m
变量个数=m
第i个约束条件为“”
第i个约束条件为“≥”
第i个约束条件为“=”
第i个变量≥0
第i个变量≤0
第i个变量无限制
变量个数=m
约束条件个数=n
第i个变量≥0
第i个变量≤0
第i个变量无限制
第i个约束条件为“”
第i个约束条件为“≥”
第i个约束条件为“=”
第i个约束条件的右端项目标函第i个变量的系数
目标函数第i个变量的系数
第i个约束条件的右端顶
2.对偶问题的基本性质
MaxZ=CX MinW=Yb
设
（1）（对称性）对偶问题的对偶是原问题；
（2）（弱对偶性）若是原问题的可行解，是对偶问题的可行解；
则；
（3）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解；
（4）（最优性准则），若、分别是互为对偶问题的可行解，且C=b，则、分别是它们的最优解；
（5）（对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。
从上述性质中，可看到原问题与对偶问题的解必然是下列三种情况之一：
①原问题与对偶问题都有最优解，且CX=Yb；
②一个问题具有无界解，则它的对偶问题无可行解；
③两个问题均无可行解。
（6）（互补松驰性），若X*、Y*分别是原问题的对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(其中XS,YS分别是原问题和对偶问题的松驰变量向量)。或，X*、Y*分别是原问题和对偶问题最优解的充要条件是：
①若y*i>0，则(aijX*j=bi
②若(aijX*j<b，则y*i=0
③若X*j>0，则(aijy*i=cj
④若(aijy*i>cj，则X*j=0
三、对偶单纯形法
1.单纯形法的重新解释
X*是最大化原LP问题最优解的充要条件是同时满足
因此，单纯形法是在保持原始可行下，经过迭代，逐步实现对偶可行，达到求出最优解的过程。
根据对偶问题的对称性，也可以在保持对偶可行下，经过迭代，逐步实现原始可行，以求得最优解。对偶单纯形法就是这种思想所设计的。
2.对偶单纯形法的计算步骤：
举例说明
3.对偶单纯形法与单纯形法的不同之点：
①不要求模型中b≥0
②先确定换出变量xL，再确定换入变量xK
③
4.对偶单纯形法适用对象
①maxZ=CX(C≤0) ②maxZ=CX
（b无限制），
③当变量个数（约束个数时，可先转化为其对偶问题，再用单纯形法或对偶单纯形法解之
④进行灵敏度分析时，有时会用到此法
四、对偶解的经济含义和影子价格
1.对偶解Y*=CBB-1的经济含义
设互为对偶的LP问题
maxZ=CX minW=Yb
(原) (对)
有 Z*=CBB-1b=W* (其中B为最优基)
因此
或者说Z*=y*1b1+y*2b2+y*mbm
则
其含义是：若对原问题右端常数项向量b中的某一常数项bi增加一个单位，目标函数的最优值Z*的变化将是Yi*。换句话说，Yi*表示当bi增加一个单位时，目标函数最优值的相应增量。实质上Yi*就是第i种资源边际价值的一种表现，也是对第i种资源的一种估价。
事实上，如引例中互为对偶LP问题分别描述生产计划问题和资源的定价问题，其数学模型分别是：
maxZ=2x1+3x2 minW=8y1+16y2+12y3
(原问题) (对偶问题)
对原问题用单纯形法求解所得最终表为
C
2
3
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
2
x1
4
1
0
0
1/4
0
0
x5
4
0
0
-2
1/2
1
3
x2
2
0
1
1/2
-1/8
0
Z
14
0
0
1.5
0.125
0
由此，它们的最优解分别是X*=(4,2)T和Y=(1.5,0.125,0)
Z*=W*=14=8Y1*+16Y2*12Y3*
其中Y1*=1.5表示单独对设备台时增加1个单位，可使Z值增加1.5个单位的利润；Y2*=0.125表示单独对原材料A增加1个单位，可使Z值增加0.125个单位的利润；而Y3*=0表示单独对原材料B增加一个单位，却不使Z值增加。这是因为从最终表中可看出，在最优方案中，松驰变量x5=4，即表示在最优生产方案中，原材料B尚有4个单位剩余被闲置，不产生任何经济效益。
2.影子价格的定义把某一经济结构中的某种资源，在最优决策下的边际价值称为该资源在此经济结构中的影子价格。
影子价格是在最优决策下对资源的一种估价，没有最优决策就没有影子价格，所以影子价格又称“最优计划价格”，“预测价格”等等。
资源的影子价格定量的反映了单位资源在最优生产方案中为总收益应提供的收益，因此，资源的影子价格也可称为在最优方案中投入生产的机会成本。
3.影子价格的求法
(1)在非退化情况下：设B为LP问题的最优基，则
资源的影价=Y*=CBB-1
(2)在退化情况下：
当对偶问题有K个最优解，则第i种资源的影价=即影价的第i个分量等于这K个对偶解中第i个分量的最小值。
例如，设某资源利用问题为
maxZ=3x1+x2
最 终 表
3
1
0
0
XB
x1
x2
x3
x4
x1
2
1
1
1
0
x4
0
0
-1
[-3]
1
Z
6
0
2
3
0
x1
2
1
2/3
0
1/3
x3
0
0
1/3
1
-1/3
Z
6
0
1
0
1
∴ 资源1的影价
=min{y1*(1),y1*(2)}
=min{3,0}=0
资源2的影价=min{y2*(1),y2*(2)}=min{0,1}=0
4.影子价格的参谋作用
（1）指出企业挖潜革新的途径
（2）对市场资源的最优配置起着推进作用
（3）可为企业决策者提供调整最优生产方案的信息
CBB-1Pj－Cj<0说明第j种产品应投产
CBB-1Pj－Cj>0说明第j种产品不应投产尤其对新产品是否应投产，可按以上两式考虑。
（4）可以预测产品的价格
（5）可作为同类企业经济效益评估指标之一。
五、灵敏度分析面对市场变化，灵敏度分析的任务是须解决以下两类问题：
（1）当系数A、b、c中的某个发生变化时，目前的最优基是否仍最优（即目前的最优生产方案是否要变化）？
（2）为保持目前最优基仍是最优基，参数A、b、c允许变化范围是什么？
灵敏度分析的方法是在目前最优基B下进行的。即当参数A、b、c中的某一个或几个发生变化时，考察是否影响以下两式的成立？
1.对资源数量br变化的分析当b中某个br发生改变时，将影响基变量的取值XB=B-1b。若br的变化仍满足B-1b≥0，则目前的基B仍为最优基，仅在B-1b和CBB-1b的数量上有些改变。若br的变化使B-1b中某些分量小于0，则目前的基成为非可行基，为此，可用对偶单纯形法迭代求得新的最优解。
B-1b≥0给出了使最优基B保持不变时△br的允许的变化范围：
由解不等式组
B-1(b+△b)=B-1b+B-1可得：
其中为最终表中列的第i个分量，为B-1中第r列的元素。
例
2.对价值系数Cj变化的分析
（1）当CN中某个Cj发生变化时，只影到非基变量xj的检验数
由于
若，则△Cj≤σj。
这就是保持最优基不变下，△Cj的允许变化范围。否则，用单纯形法继续迭代，求得新的最优解。
（2）当CB中某个Cr发生变化时，
则会影响到所有非基变量的检验数σN=CBB-1N－CN。
解不等式组 =(CB+△CB)B-1N－CN=(CBB-1N－CN)+△CBB-1N≥0
即 (CBB-1N－CN)+(0,…,△Cr,…,0)B-1N≥0
得到使最优解不变△Cr的允许变化范围；
例
（3）对增加新产品的分析设革企业在计划期内，拟议生产新产品Xn+1，并已知新产品的单位利润为Cn+1，消耗系数向量为Pn+1=(a1,n+1,a2,n+1,…am,n+1)T，此时应如何分析才能确定该新产品理澡投产？
增加新产品应在不影响企业目前计划期内最优生产的前提下进行。因此可从现行的最估基B出发考虑：
若σn+1=CBB-1Pn+1－Cn+1<0，则应投产若σn+1=CBB-1Pn+1－Cn+1>0，则不应投入。
即新产品的机会成本小于目前的市场价格时，应投产否则不应投产。
（4）对增加新约束条件的分析在企业生产过程中，经常有新情况发生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响，如水、电和资源的供应不足等，对生产过程提出了新约束等。
对增加新约束条件的分析方法步骤是：
第一步：将目前的最优解代入新增加的约束，若能满足约束条件，则说明新增约束对目前的最优解（即最优生产方案）不构成影响（称此约束为不起作用约束），可暂时不考虑新增约束条件。否则转下一步；
第二步：把新增约束添加到原问题最终表中，并作初等行变换，构成对偶可行的单纯形表，并用对偶单纯形法迭代，求出新的最优解。
例：
（5）技术系数aij变化的分析第一种情况（当j(JN）：方法与增加一个新产品的分析相同。
第二种情况（当j(JB）：由于B中元素的改变影响到B-1的变化，因此也影响到T(B)。目前的基B对应的解有可能既不是原始可行，也不是对偶可行。于是不如重新求解。
第二章 特殊LP问题及其解法
所谓特殊LP问题是指LP模型的系数矩阵具有特殊的结构，有可能找到比单纯形法更为简便的求解方法，从而节省人力和物力。
§1 运输问题及其解法引例：
某公司经销甲产品，它下设三个加工厂，每日的产量分别为：A1-7吨，A2-4吨，A3-9吨。该公司把这些产品分别运往四个销售点，各销售每日销量为：B1-3吨，B2-6吨，B3-5吨，B4-6吨。已知从各工厂到各销售点的单位产品的运价为下表所示。问该公司应如何调运产品，在满足各销售点需求量的前提下，使总运费为最少。
平衡表（单位：吨） 运价表 （单位：元/吨）
销地产地
B1
B2
B3
B4
产量
B1
B2
B3
B4
A1
7
3
11
3
10
A2
4
1
9
2
8
A3
9
7
4
10
5
销 量
3
6
5
6
解：这是一个产销平衡的运输问题，其数学模型是：
设Xij表示从Ai调运产品到Bj的数量（吨），则
minZ=3X11+11X12+3X13+10X14+X21+9X22
+2X23+8X24+7X31+4X32+10X33+5X34
x11+x12+x13+x14 =7
x21+x22+x23+x24 =4
x31+x32+x33+x34 =9
x11 +x21 +x31 =3
x12 +x22 +x32 =6
x13 +x23 +x33 =5
x14 +x24 +x34 =6
xij≥0 (i=1,2,3,j=1,2,3,4)
一、产量平衡的运输问题及其解法
1.产销平衡的运输问题的数学模型及其特点
特点：（1）其系数矩阵的结构疏松，且每一列向量
Pij=(0,…1,…1,…0)T=ei+em+j
可以证明，r(A)=m+n－1。即有m+n－1个独立方程。
于是，该LP问题有且仅有m+n－1个基变量。
（2）（产销平衡条件）
（3）因为故必有可行解和最优解。
由于上述特点，若按单纯形法求解必须增加人工变量，致使计算量大大增加，故用特殊解法──表上作业法。
2.表上作业法表上作业法实质上还是单纯形法，但具体计算和术语上有所不同。其计算步骤方法，并通过对引例的求解过程说明之一。
（1）用最小元素法确定初始方案（即初始基可行解）
切记在产销平衡表上必须且只能填写m+n－1个数字格
（2）用位势法求出空格的检验数并进行最优解的判别设u1,u2,…um; v1,v2,…,vn是对应运输问题m+n个约束条件的对偶变量，B为含有人工变量的初始可行基，由LP问题的对偶理论知
CBB-1=(u1,u2,…um; v1,v2,…,vn)
而每个决策变量Xij相应的系数向量Pij=ei+em+j，所以CBB-1Pij=ui+vj
于是，检验数σij=CBB-1Pij－Cij =(ui+vj)－Cij
又各基变量的检验数为0，故对每个基变量所在的数格的检验数有
(ui+vj)－Cij =0 i,j(JB
即有方程组
共m+n个未知数 s=m+n－1个方程显然上述方程有解，且由于含有一个自由变量，因此，可令任一未知数为0，就可求出上述方程组的解(ui1,ui2,…uim,vj1,vj2,…vjn)──称为位势解。
如用位势法求引例初始基可行解的检验数：
销地产地
B1
B2
B3
B4
ui
A1
-1
3
-2
11
③
⑩
0
A2
1
-1
9
②
+1
⑧
-1
A3
-10
7
④
-12
⑩
⑤
-5
vj
2
9
3
10
第一步：将运价表中的数字分别写在各格听右上角，并对基变量相应的运价加圈，同时在表中增加vj和ui列。
第二步：利用圈数格分别算出ui和vj，即令u1=0，然后按ui+vj=Cij (i,j(JB)，相继确定ui，vj的值。于是有v3=3,v4=10,u2=-1,v1=2,u3=-5,v2=9
第三步：按σij= (ui+vj)－Cij (i,j(JN)算出表中各空格（即非基变量）的检验数：
σ11=(0+2)－3=-1，σ12=(0+9)－11=-2，σ22=-1，σ24=1，σ31=-10，σ33=-12
由于运输问题的目标函数是求最小化，故判别最优解的准则是所有的σij=CBB-1Pij－Cij≤0
因为(24=+1>0，所以目前尚未得到最优解，尚须改进
（3）在调运平衡表上用闭回路法进行调整，得到新的基可行解（新的调运方案）
i) 确定换入变量：自上而上，自左向右第一个正检验数相应的非基变量（空格）为入基变量。
ii) 作闭回路：以换入变量空格为出发点，用水平或垂直线向前划，当碰到某一恰当数格转90(后，继续前进，直至回到起始空格止。
iii) 确定调整量(=min{第奇数次拐角格的调运量}
iv) 在闭回路上进行调整：对闭回路上每个奇数次拐角格的调运量－(对闭回路上每个第偶数次（含起始格）拐角格的调运量+(。调整后，将闭回路中为0的一个数格作为空格（即出基变量）。
闭回路外的各调运量不变。这样便得到新的调运方案（新基可行解）
销地产地
B1
B2
B3
B4
产量
A1
(+1)4
3(-1)
7
A2
3
(-1)1
(+1)
4
A3
6
3
9
销量
3
6
5
6
对调整后所得的新方案，再进行检验，已得到最优解（最优调运方案）；
从A1调运到5吨到B3，调运2吨到B4
从A2调运到3吨到B1，调运1吨到B4
从A3调运到6吨到B2，调运3吨到B4
总运费最小是85元
（4）在进行表上作业法须注意的问题：
i) 在最终调运表中，若有某个空格（非基变量）的检验为0时，则表明该运输问题有多重调运方案；
ii) 在确定初始方案时，若在(i,j)格填上某数字后,出现Ai处的余量=Bj处的需量，此时必须在平衡表上被划去行和列相应位置的任一空格处填上一个“0”，以满足数格=m+n－1个的需要；
iii) 在用闭回路法调整时，当闭回路上第奇数次拐角数有几个相同的最小值时，调整后只能有一个空格，其余均要保留数“0”，以保证数格=m+n－1个的需要。
以上ii)，iii)均出现退化解。
iv) 用最小元素法所得到的初始方案可以不唯一。
二、产销不平衡的运输的问题及其求解方法
1.数学模型：产大于销 产小于销
2.解法思路：
将不平衡转化为平衡。即当时，考虑在平衡表中增加一虚拟列，表示增加一个销货点(j=n+1)如仓库，其销货量为，且各运价Cin+1=0；当时，考虑在平衡表中增加一虚拟行，表示增加一个新产地，且各运价Cm+1j=0。然后再用产销平衡的运输问题的解法进行解之。
例三、转运问题及其解法：
1.所谓转运问题是在以下背景产生的：
(1)每个工厂生产的产品不直接运到销地，可以几个产地集中一起运。
(2)运往各销地的物资可先运给其中的几个销地，再转运给其它销地。
(3)除产、销地之外，还可以有几个中间转运站，在产地之间，销地之间或产销之间转运。
凡类似上述情况下的调运物资并使总运费最小的问题统称为转运问题。
2.求解“转运问题”的思路是把问题中所有的产地、中转站和销地都既看作产地，又都看作销地，把“转运问题”变成扩大后的产销平衡的运输问题处理。
3.求解“转运问题”的方法步骤：
(1)建立扩大的产销平衡运输问题单位运价表。其中
1)对两地不能直接运输的单位运价定为M（很大的正数）；
2)对所有中转站Tj的产量和销量定为相等，设定为；
3)对产量列的各数据可按下式计算并填入：
Ai的产量=ai+(,Tj产量=(，Bj的产量=(
4)对销量行的各数据可按下式计算并填入：
Aj的产量=(,Tj销量=(，Bj的销量=(+bj
(2)用表上作业法进行求解
§2 指派问题及其解法引例任务人员
E
J
G
R
甲
2
15
13
4
乙
10
4
14
15
丙
9
14
16
13
丁
7
8
11
9
解：设Xij表示第i人从事第j项工作，且
因此，该问题的数学模型为
MinZ=2X11+15X12+13X13+4X14+10X21+4X22+14X23+15X24
+9X31+14X32+16X33+13X34+7X41+8X42+11X43+9X44
表示第j项工作只指派人完成
表示第i人被指派完成一项工作
Xij=0或1(i,j=1,2,3,4)
诸如此类，有n项任务，恰好有n个人可承担这些任务，但由于每人的专长技术不同，完成任务的效率(所费时间_不同，为使完成n项任务的总效率最高（即所需总时最少），应如何指派（分派）人员的问题统称为指派（分派）问题。
一、指派问题的数学模型及其特点
1.数学模型：
2.特点
（1）给定一个指派问题时，必须给出效率矩阵（系数矩阵）C=(Cij)nxn,且Cij(0，因此必有最优解()。
（2）指派问题是一种特殊的平衡的运输问题，由于模型结构的特殊性（看作每产地的产量均为1，每销地的销量均为1），故可用更为简便的匈牙利法进行求解。
（3）解矩阵
是指派问题的可行解，但不一定是最优解。
二、指派问题的解法──匈牙利法
1.匈牙利法的基本思想是：对同一项工作（任务）j来说，同时提高或降低每人相同的效率（常数ti），不影响其最优指派；同样，对同一个人i来说，完成各项工作的效率都提高或降低相同的效率（常数di），也不影响其最优指派，因此可得到新的效率矩阵(bij)nxn，其中
bij=Cij+ti+dj （对所有的i,j）
则新的目标函数为
其中为常数这说明Z(与Z同时达到最小值。因而最优解相同。故指派问题有以下性质：
若从效率矩阵(Cij)nxn的一行（列）各元素中分别减去该行（列）的最小元素，得到的新效率矩阵(bij)nxn不改变原指派问题的最优解。
2.匈牙利法
三、对求最大化的指派问题，（即求）,可采用构造新的效率矩阵(M－Cij)nxn，其中M=max{Cij}，（显然M－Cij(0），将其转化为
求所得到的最优解就是原问题的最优解。事实上
由于nM为常数，因此，使Z(取得最小的最优解就是使Z取得最大的最优解。
4.以上讨论的指派问题是效率矩阵的行数等于列数，即m+n的情况。当m(n时，则可用增加虚设的零元数行（列）使效率矩阵变成方阵后，再用匈牙利法求解。
当m<n时 当m>n时
5.指派问题必有最优解，但可以不唯一。
§3 整数线性规划问题及其解法
一、整数线性规划在上一章讨论的LP问题中,对决策变量只限于不能取负值的连续型数值,即可以是正分数或正小数。然而在许多经济管理的实际问题中，决策变量只有非负整数才有实际意义。对求整数最优解的问题，称为整数规划(Integer Programming)(简记为IP)。又称约束条件和函数均为线性的IP为整数线性规划(Integer Linear Programming)(简记为ILP)。
ILP问题数学模型的一般形式为：求一组变量X1,X2,…,Xn，使
人们对IP感兴趣，还因为有些经济管理中的实际问题的解必须满足如逻辑条件和顺序要求等一些特殊的约束条件。此时需引进逻辑变量（又称0-1变量），以“0”表示“非”，以“1”表示“是”。凡决策变量均是0-1变量的IP为0-1规划。
严格地说，IP是个非线性问题。这是因为IP的可行解集是由一些离散的非负整数所组成，不是一个凸集。迄今为止，求解IP问题尚无统一的有效方法。
求解ILP问题方法的思考：
1）“舍入取整”法：即先不考虑整数性约束，而去求解其相应的LP问题（称为松驰问题），然后将得到的非整数最优解用“舍入取整”的方法。这样能否得到整数最优解？否！这是因为“舍入取整”的解一般不是原问题的最优解，甚至是非可行解。
但在处理个别实际问题是，如果允许目标函数值在某一误差范围内，有时也可采用“舍入取整”得到的整数可行解作为原问题整数最优解的近似。这样可节省求解的人力、物力和财力。
设X*是原ILP的最优解，X是其松驰问题的非整数最优解，是“舍入取整”的整数可行解，d为给出目标函数值的允许误差。由于(CX*(CX
所以 CX*－(CX－
当CX－(d时，则可将作为X*的近似解。
2）完全枚举法 此法仅在决策变量很少的情况下才实际有效。对于变量稍多的ILP问题则几乎不可能。如在指派问题中，当n=20，则有可行解20！个，而20！>2X1018，这在计算机上也是不可能实现的。
3）求解ILP问题常见的几种解法有：分枝定界法，割平面法，0-1规划的特殊解法等。
二、0-1变量产生的背景和应用引例（详见书P72例2）
由引例可见，利用0-1变量处理一类“可供选择条件”的问题查非常简明且方便的。下面再进一步分别说明对0-1变量的应用。
假定现有m种资源对可供选择的n个项目进行投资的数学模型为：
求一组决策变量X1,X2,…,Xn，使
（3.1）
满足
其中，Cj表示投资第j项获得的期望收益，aij表示第i种资源投于第j项目数量，bj表示第i种资源的限量。
1.对可供项目的选择
（1）如果在可供选择的前k(k(n)个项目中，必须且只能选择一项，则在(3.2)中加入新的约束条件：
（2）如果可供选择的k(k(n)个项目是相互排斥的，则在(3.2)中加入新的约束条件：
同时它还表示在第k个项目中至多只能选择一项投资。
（3）如果在可供选择的k(k(n)个项目中，至少应选择一项投资，则在(3.2)中加入新的约束条件：
（4）如果项目j的投资必须以项目i的投资为前提，则可在(3.2)中加入新的约束条件：
Xj(Xi
（5）如果项目i与项目j要么同时被选中，要么同时不被选中，则在(3.2)中加入新的约束条件：
Xj=Xi (i(j)
2.对可供资源的选择
（1）如果对第r种资源br与第t种资源bt的投资是相互排斥的，即只允许对资源br与bt中的一种进行投资，则可将(3.2)的第r个和第t个约束条件改写为：
①
②
其中y为新引进的0-1变量，M为充分大正数。易见，当y=0时，①式就是原来的第r个约束条件，具有约束作用。此时对②式而方，无论Xj为何值，都成立，毫无约束作用，这就使问题仅允许第r种资源进行投资。当y=1时，②式对Xj起了约束作用，而①式成了多余的条件。到底是满足①还是②，则视问题在求出最优解后，y为0还是1而言。
（2）如果问题是要求在前m个约束条件中至少满足k(1<k<m)个，则可将(3.2)中的原约束条件修改为：
其中M为充分大的正数，k为整数。
3.在固定费用问题中的应用（详见书）
三、0-1规划的解法
1.完全枚举法：其基本思想是：首先将全部变量取0或1的所有组合（解）列出，然后在逐个检查这些组合（解）是否可行的过程中，利用增加并不断修改过滤条件的办法，减少计算量，以达到求出最优解之目的。
例（详见书）
该法只在变量少的情况下使用才有效。
2.隐枚举法：
0-1规划的隐枚举法是一种特殊的分枝定界法，其基本思想是利用变量只能为0或1两个值的特性，进行分枝定界，以减少枚举而达到求出最优解之目的。该法适用于任何0-1规划问题的求解。
运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。运筹学的核心思想是建立在优化的基础上。
例如，在线性规划中体现为两方面：
（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成？
（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多？
运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科学依据。
随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解已有相应的软件。因此，在实际求解计算时常可借助于软件在计算机上进行，这样可以节省大量的人力和时间。
第一部分 线性规划内容框架
LP问题基本概念 数学模型 可行解、最优解实际问题 LP问题 解的概念 基本解、基可行解提 出 基本最优解
基本方法
图解法
原始单纯形法
单纯形法 大M法
人工变量法
对偶单纯形法 两阶段法
对偶理论
进一步讨论
灵敏度分析──参数规划*
在经济管理领域内应用
运输问题（转运问题）
特殊的LP问题 整数规划
多目标LP问题*
第一部分 线性规划（Linear Programming）及其应用
第一章 LP问题的数学模型与求解
§1 LP问题及其数学模型
（一）引例1（生产计划的问题）
某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获的利润如下表所示。问应如何安排计划使该工厂获利最多？
Ⅰ
Ⅱ
资源限量
设备
1
2
8(台时)
原材料A
4
0
16(kg)
原材料B
0
4
12(kg)
单位产品利润（元）
2
3
该问题可用一句话来描述，即在有限资源的条件下，求使利润最大的生产计划方案。
解：设x1,x2分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。由于资源的限制，所以有：
机器设备的限制条件：x1+2x2≤8
原材料A的限制条件,4x1≤16 （称为资源约束条件）
原材料B的限制条件,4x2≤12
同时，产品Ⅰ、Ⅱ的产量不能是负数，所以有
x1≥0，x2≥0 （称为变量的非负约束）
显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1，x2以得到最大的利润，即使目标函数
Z=2x1+3x2 的值达到最大。
综上所述，该生产计划安排问题可用以下数学模型表示：
maxz=2x1+3x2
引例2,（营养配餐问题）
假定一个成年人每天需要从食物中获取3000卡路里热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成份以及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小？
序号
食品名称
热量(卡路里)
蛋白质(克)
钙(mg)
价格(元)
1
猪肉
1000
50
400
10
2
鸡蛋
800
60
200
6
3
大米
900
20
300
3
4
白菜
200
10
500
2
解:设xj(j=1,2,3,4)为第j种食品每天的购买量，则配餐问题数学模型为
minz=10x16x23x32x4
（二）LP问题的模型上述两例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大或最小的问题。它们具有共同的特征。
（1）每个问题都可用一组决策变量(x1,x2,…xn)表示某一方案，其具体的值就代表一个具体方案。通常可根据决策变量所代表的事物特点，可对变量的取值加以约束，如非负约束。
（2）存在一组线性等式或不等式的约束条件。
（3）都有一个用决策变量的线性函数作为决策目标（即目标函数），按问题的不同，要求目标函数实现最大化或最小化。
满足以上三个条件的数学模型称为LP的数学模型，其一般形式为：
max(或min)z=c1x1+c2x2+…+cnxn (1.1)
(1.2)
或紧缩形式
max(或min)z=
(1.4)
或矩阵形式
max(或min)z=cx
(1.5)
或向量形式：
max(或min)z=cx
(1.6)
其中C=(c1,c2,…,cn)，称为价值系数向量；
称为技术系数矩阵（并称消耗系数矩阵）
=(p1,p2,…,pn)
称资源限制向量
X=(x1,x2,…,xn)T称为决策变量向量。
（三）LP问题的标准型
1.为了讨论LP问题解的概念和解的性质以及对LP问题解法方便，必须把LP问题的一般形式化为统一的标准型：
maxz=；
或
maxz=cx
或
标准型的特点：
①目标函数是最大化类型
②约束条件均由等式组成
③决策变量均为非负
④bi(i=1,2,…,n)
2.化一般形式为标准型
①minz(max(-z)=-cx
②“(”(左边+松驰变量；“(”(左边－“松驰变量”
③变量xj(0(-xj(0变量xj无限制(令xj=xj(－xj(
④bi<0(等式两边同乘以(-1)。
3.模型隐含的假设
①比例性假定：决策变量变化的改变量与引起目标函数的改变量成比例；决策变量变化的改变量与引起约束方程左端值的改变量成比例。此假定意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数。
②可加性假定：每个决策变量对目标函数和约束方程的影响是独立于其它变量的。
③连续性假定：决策变量应取连续值。
④确定性假定：所有的参数(aij,bi,cj)均为确定，所以LP问题是确定型问题，不含随机因素。
以上4个假定均由于线性函数所致。在现实生活中，完全满足这4个假定的例子并不多见，因此在使用LP时必须注意问题在什么程度上满足这些假定。若不满足的程度较大时，应考虑使用其它模型和方法。如非线性规划，整数规划或不确定型分析方法。
对LP标准型，我们还假定r(A)=m<n。
（四）LP问题的解的概念设LP问题
maxz= (1.7)
(1.8)
(1.9)
1.从代数的角度看：
可行解和最优解 满足约束条件(1.8)和(1.9)的解X=(x1,x2,…,xn)T称为可行解。所有可行解构成可行解集，即可行域。而使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。
求解LP问题就是求其最优解和最优值，但从代数的角度去求是困难的。
2.从LP角度看：
基：设A为mxn矩阵，r(A)=m，B是A中的mxm阶非奇异子矩阵（即|B|(0），则称B是LP问题的一个基。
若B是LP问题的一个基，则B由m个线性独立的列向量组成，即B=(Pr1,Pr2,…,Prm)，其中Prj=(a1rj,a2rj,…,amrj)T，(j=1,2,…,m)称为基向理。与其向量Prj相对应的变量xrj称为基变量，其它变量称为非基变量。显然，对应于每个基总有m个基变量，n－m个非基变量。
基本解与基可行解 设B是LP问题的一个基，令其n－m个非基变量均为零，所得方程的解称为该LP问题的一个基本解。显然，基B与基本解是一一对应的，基本解的个数≤Cmn。在基本解中，称满足非负条件的基本解为基可行解，对应的基称为可行基。
退化解 如果基解中非零分量的个数小于m，则称此基本解为退化的，否则是非退化的。
最优基 如果对应于基B的基可行解是LP问题的最优解，则称B为LP问题的最优基，相应的解又称基本最优解。
3.LP问题解之间的关系如图所示
(
（五）两个变量LP问题的图解法
1.LP问题解的几何表示。以引例为例说明
maxz=2x1+3x2
按以下顺序进行：
解：（1）画出直角坐标系；
（2）依次做每条约束线，标出可行域的方向，并找出它们共同的
可行域；
（3）任取一目标函数值作一条目标函数线（称等值线），根据目标函数（最大或最小）类型，平移该直线即将离开可行域上，则与目标函数线接触的最终点即表示最优解。
图1
其中，将目标函数Z=2x1+3x2改写为，因此，它可以表示为：以z为参数，以为斜率的一族平行线。位于同一条直线上的点具有相同的值。
解的几种情况：
（1）此例有唯一解Q2，即x1=4,x2=2,z=14
（2）有无穷多最优解（多重解），若将目标函数改为z=2x1+4x2则线段Q2，Q3上的点均为最优解。
（3）无界解
求max无界但求min有唯一解
（4）无可行解
可行域与最优解间的关系：
可行域 最优解
空 集 无最优解（无可行解）
有界集 唯一最优解
多重解
无界集 无有限最优解（无界解）
结论：（1）LP问题的可行域是凸集（凸多边形，凸多面体，…）；
（2）LP问题最优解若存在，则必可在可行域的顶点上得到；
（3）LP问题的可行域的顶点个数是有限的；
（4）若LP问题有两个最优解，则其连线上的点都是最优解。因此，求解LP问题可转化为如何在可行域的顶点上求出使目标函数值达到最优的点的问题。
2.基可行解的几何意义
对例1 LP问题标准化为 maxZ=2x1+3x2
可求得所有的基本解：
x(1)=(0,0,8,16,12)T(0点),x(2)=(4,0,4,0,12)T(Q1点)
x(3)=(4,2,0,0,4)T(Q2点),x(4)=(2,3,0,8,0)T(Q3点)
x(5)=(0,3,2,16,0)T(Q4点),x(6)=(4,3,-2,0,0)T(C点)
x(7)=(8,0,0,-16,12)T(A点),x(8)=(0,4,0,16,-4)T(B点)
但A、B、C三点是非可行域上的点，即非可行解。因此，x(1)，x(2)，x(3)，x(4)，x(5)才是基可行解，它们与可行域的顶点相对应。于是还有结论：（5）对于标准型的LP问题，X是基可行解的充要条件是X为可行域的顶点。
（6）LP问题可行域顶点的个数=基可行解的个数≤基的个数≤Cmn
3.图解法只适用于两个变量（最多含三个变量）的LP问题。
4.求解LP问题方法的思考：
①完全枚举法，对m、n较大时，Cmn是一个很大的数，几乎不可能；
②从可行域的一个顶点（基可行解）迭代到另一个顶点（基可行解）。
§2 单纯形法与计算机求解
1.解LP问题单纯形法的基本思路：
求出一个初始基可行解
y
判别此基可行解是否最 优 解
N
求出使目标函数值得到改善的基可行解
2.单纯形法的计算步骤（表格形式）
（1）建立初始单纯形表，假定B=I，b≥0
设maxZ=c1x1+c2x2+…+cnxn
将目标函数改写为：-Z+c1x1+c2x2+…+cnxn=0
把上述方程组和目标函数方程构成n+1个变量，m+1个方程的方程组，并写成增广矩阵的形式：
-Z x1 x2 … xm xm+1 … xn
0 1 0 … 0 1m+1 … 1n 1
0 0 1 … 0 2m+1 … 2n 2
0 0 0 … 1 mm+1 … mn m
-1 c1 c2 … cm cm+1 … cn 0
以非基变量表示基变量形式代入Z中的基变量,有
令
于是
因此，上述的增广矩阵就可写成：
Z x1 x2 … xm xm+1 … xn
0 1 0 … 0 1m+1 … 1n 1
0 0 1 … 0 2m+1 … 2n 2
0 0 0 … 1 mm+1 … mn m
1 0 0 … 0 …－cn
再令
则上述增广矩阵可写成下面表格形式：即初始单纯形表T（B）
Cj
C1……Cm
cm+1……cn
(i
CB
xB
x1……xm
xm+1……xn
C1
x1
1
1……0
a1m+1……a1n
C2
x2
2
0……0
a2m+1……a2n
：
：
：
：,
：………：
Cm
xm
m
0……1
amm+1……amn
Z
Z0
0……0
(m+1……(n
((j检验数行
上述初始单纯形表可确定初始可行基和初始基可行解：
B=(P1,P2,…,Pm)=I,x=(b1,b2,…,bm,0……0)T
从初始单纯形表建立的过程可以看到以下事实：
（1）凡LP模型中约束条件为“≤”型，在化为标准型后必有B=I，如果b≥0，则模型中约束方程的各数据不改变符号照抄在表中相应的位置。目标函数非基变量的系数则以相反数填入检验数行各相应位置。
（2）在单纯形表中，凡基变量所在的列向量必是单位列向量，其相应的检验数均为零。
（3）
更好表现一般规律的在矩阵形式的单纯形表中设MaxX=CX MaxZ=CX+0XL
其标准型为
将系数矩阵(A,I)分划为(B,N,I)，其中B为可行基，对应于基变量向量XB,N对应于XN，I对应于XL,(XN,XL)为非基变量向量。于是(X,L)T=(XB,XN,XL)T,(C,0)=(CB,CN,0)。因此，矩阵形式的LP模型改写为：
(
用非基变量向量表示基变量向量，有
XB=B-1b－B-1NXN－B-1XL
代入目标函数中有
Z =CB(B-1b－B－1NXN－B-1XL)+CNXN+0XL
=CBB-1b－CBB-1NXN－CBB-1XL)+CNXN
=CBB-1b－(CBB-1N－CN)XN－CBB-1XL
将
写成对应于基B的矩阵形式的单纯形表T（B）：
C(
CB
CN
CL
XB
XN
XL
XB
1
B-1N
B-1
Z
CBB-1b
0
CBB-1N－CN
CBB-1
例如将例1 化成标准型后如下表T（B）：
Cj
2
3
0
0
0
(i
CB
XB
x1
x2
x3
x4
x5
0
x3
8
1
2
1
0
0
0
x4
16
4
0
0
1
0
0
x5
12
0
4
0
0
1
-Z
0
-2
-3
0
0
0
(σj
初始可行基B=(P3,P4,P5)=I,X=(0,0,8,16,12)T
（2）判别最优解
1( 在T(B)中，若所有的检验数σj≥0 (j=1,2,…,n)
则B为最优基，相应的基可行解为最优解，停止计算。
2( 在T(B)中，若有σk<0 (1(k(n)，且xk的系数列向量Pk(0，则该问题无界，停止计算。否则转入（3）
（3）换基迭代（基变换）
1( 先确定入基变量Xk,k=min{j| (j<0}
2( 按最小比值原则确定出基变量xL：
3( 以为主元，进行初等行变换（又称旋转变换）即将列向量变换为单位列向量：
返回（2）。
换基迭代的关键在于将换入变量对应的列向量用初等行变换方法变换成单位列向量。其中主元变成1。即
第L个分量如果在最终表中有非基变量的检验数为0，则该问题有多重最优解。
3.单纯形法的进一步讨论──用人工变量法求初始基可行解
（一）人工变量法若对LP模型标准化后，不具有B=I时，如何办？此时可采用人工变量法得到初始基可行解。
所谓人工变量法是在原问题不含有初始可行基B=I的情况下，人为的对约束条件增加虚拟的非负变量（即人工变量），构造出含有B=I的另一个LP问题后求解。当增加的人工变量全部取值为0时，才与原问题等价。这样，新问题将有一个初始基可行解（以人工变量为基变量），可用单纯形法进行迭代。经迭代后，若人工变量全部被换成非基变量，则原问题的约束条件被恢复，同时也得到一个基可行解。在最终表中若不能全部被换出，则说明原问题无可行解。
因此，该法的关键在于将人工变量全部换出。
人工变量法常见的有大M法和两阶段法。
（1）大M法（通过下例简略介绍其方法与步骤）
例，用大M法求解
MinZ=x1+1.5x2
解：MinZ=x1+1.5x2+0.x3+0.x4+Mx5+Mx6
其中x3,x4为松驰变量，x5,x6为人工变量，M为任意大的正数。
注意到：①分别在约束条件增加人工变量x5,x6是为了构成“人工基”
②对于Min的目标函数采用(+M)，而对于Max的目标函数则采用(-M)作为人工变量的系数,是强加于人工变量的一种惩罚,其目的是为了强制人工变量由变量转为非基变量，使之恢复原问题，或与原问题等价。
③对于minZ判别最优性准则应是Cj－Zj≤0。
④大M法适合于手算，不适用于计算机求解。
（2）两阶段法第一阶段：不考虑原问题是否存在基可行解；给原LP问题的约束条件加入人工变量，构造仅含人工变量的目标函数并要求实现最小化（即使原LP问题目标函数是求最大化）的辅助问题：
MinW=xn+1+…+xn+m
然后用单纯形法求解（1）。若W(0，则原问题无可行解，停止计算。若W=0，且所有的人工变量均为非基变量，则去掉人工变量后可得到原问题的基可行解；如果人工变量中含有为0的基变量时（即退化解），则可再进行初等行变换将其换出，从而获得原问题的基可行解。
第二阶段：在第一阶段所得的基可行解的基础上，将最终表中的人工变量列删去，同时将人工目标函数行换入原问题的目标函数作为第二阶段计算的初始表。
仍以上例为例用两阶段法求解。
MinZ=x1+1.5x2+0x3+0x4
原问题：
MinW=x5+x6
辅助问题：
书中第19页表2.9和表2.10的说明：（1）第一阶段的初始表中非基变量的检验数=人工变量所在行的非基变量相应系数之和，目标函值值=人工变量所在行相应常数之和。
（2）第二阶段单纯形表中目标函数系数应将非基变量表示基变量后所得结果填入，或先直接填入原系数，再通过初等行变换使基变量的检验数为0。
（3）若maxZ，则可转化为minZ1(Z1=-Z)
（二）退化单纯形法计算中用(规则决定换出变量时，有时出现两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于0，出现退化解，如某个最大化问题的单纯形表为：
Cj
4
0
3
0
0
0
(i
CB
XB
x1
x2
x3
x4
x5
x6
0
x5
6
2
0
1
0
1
0
3
0
x4
3
[1]
-1
0
1
0
0
3
0
x6
5
1
1
1
0
0
1
5
Z
0
-4
0
-3
0
0
0
((j
0
x5
0
0
[2]
1
-2
1
0
0
4
x1
3
1
-1
0
1
0
0
/
0
x6
3
0
2
1
-1
0
1
1
Z
12
0
-4
-3
4
0
0
((j
在出现退化解后的继续迭代中，有可能出现基循环：
B1(B2(……(B1
这样迭代下去便永远得不到最优解。
解决基循环的方法很多，如“摄动法”、“字典序法”等等。
在计算机上常采用“Bland规则”：
（1）取表中下标最小的非基变量xk为换入变量，即
k=min{j | (j>0}
（2）按(规则计算，若存在两个相同以上最小比值时，选取下标最小的基变量为换出变量xL，即
值得庆幸的是出现基循环是罕见的。
§3 对偶理论与灵敏度分析
一、LP的对偶问题
1.引例 前已述引例1是一个在有限资源的条件下，求使利润最大的生产计划安排问题，其数学模型为：
maxZ=2x1+3x2
现从另一角度考虑此问题。假设有客户提出要求，租赁工厂的设备台时和购买工厂的原材料A、B，为其加工生产别的产品，由客户支付台时费和材料费，此时工厂应考虑如何为每种资源的定价问题？
解：设y1,y2,y3分别表示出租单位设备台时的租金和出售单位原材料A、B的价格（含附加值）
工厂决策者考虑：
（1）出租设备和出售原材料应不少于自己生产产品的获利，否则不如自己生产为好。因此有
工厂的总收入为 W=8y1+16y2+12y3
（2）价格应尽量低，否则没有竞争力（此价格可成为与客户谈判的底价）
租赁者考虑：希望价格越低越好，否则另找他人。
于是，能够使双方共同接受的是
MinW=8y1+16y2+12y3
上述两个LP问题的数学模型是在同一企业的资源状况和生产条件下产生的，且是同一个问题从不同角度考虑所产生的，因此两者密切相关。称这两个LP问题是互为对偶的两个LP问题。其中一个是另一个问题的对偶问题。
2.从矩阵形式讨论互为对偶LP问题由例1 有maxZ=cx
由矩阵形式的单纯形表中可知：
检验数的表达式为： CBB-1N－CN和CBB-1
当
表示LP问题已得到最优解令Y=CBB-1,且②有Y(0
由于基变量XB的检验数为0，可改写成CBB-1B－CB=0
因此，包括基变量在内的所有检验数可写成
(CBB-1B－CB,CBB-1N－CN)=(CBB-1A－C)= YA－C≥0
即YA(C
又对② Y=CBB-1，两边右乘b，有
Yb=CBB-1b=Z
由于Y无上界，所以只有最小值，因此有
MinW=Yb
它是原问题 {maxZ=CX| AX(b,X(0}的对偶问题于是，对称形式下两个互为对偶LP问题的数学模型为：
MaxZ=CX MinW=Yb
与
任何一个LP问题均有一个对偶LP问题与之匹配。
对偶理论就是研究LP问题及其对偶问题的理论，它是LP理论中的重要内容之一。
二、对偶理论
1.原问题与对偶问题的关系如下表所示原 始 对 偶 表原问题Max（对偶问题）
对偶问题Min（原问题）
约束条件数=m
变量个数=m
第i个约束条件为“”
第i个约束条件为“≥”
第i个约束条件为“=”
第i个变量≥0
第i个变量≤0
第i个变量无限制
变量个数=m
约束条件个数=n
第i个变量≥0
第i个变量≤0
第i个变量无限制
第i个约束条件为“”
第i个约束条件为“≥”
第i个约束条件为“=”
第i个约束条件的右端项目标函第i个变量的系数
目标函数第i个变量的系数
第i个约束条件的右端顶
2.对偶问题的基本性质
MaxZ=CX MinW=Yb
设
（1）（对称性）对偶问题的对偶是原问题；
（2）（弱对偶性）若是原问题的可行解，是对偶问题的可行解；
则；
（3）（无界性）若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解；
（4）（最优性准则），若、分别是互为对偶问题的可行解，且C=b，则、分别是它们的最优解；
（5）（对偶定理）若互为对偶问题之一有最优解，则另一问题必有最优解，且它们的目标函数值相等。
从上述性质中，可看到原问题与对偶问题的解必然是下列三种情况之一：
①原问题与对偶问题都有最优解，且CX=Yb；
②一个问题具有无界解，则它的对偶问题无可行解；
③两个问题均无可行解。
（6）（互补松驰性），若X*、Y*分别是原问题的对偶问题的可行解，则X*、Y*是最优解的充要条件是：Y*XS=0,YSX*=0(其中XS,YS分别是原问题和对偶问题的松驰变量向量)。或，X*、Y*分别是原问题和对偶问题最优解的充要条件是：
①若y*i>0，则(aijX*j=bi
②若(aijX*j<b，则y*i=0
③若X*j>0，则(aijy*i=cj
④若(aijy*i>cj，则X*j=0
三、对偶单纯形法
1.单纯形法的重新解释
X*是最大化原LP问题最优解的充要条件是同时满足
因此，单纯形法是在保持原始可行下，经过迭代，逐步实现对偶可行，达到求出最优解的过程。
根据对偶问题的对称性，也可以在保持对偶可行下，经过迭代，逐步实现原始可行，以求得最优解。对偶单纯形法就是这种思想所设计的。
2.对偶单纯形法的计算步骤：
举例说明
3.对偶单纯形法与单纯形法的不同之点：
①不要求模型中b≥0
②先确定换出变量xL，再确定换入变量xK
③
4.对偶单纯形法适用对象
①maxZ=CX(C≤0) ②maxZ=CX
（b无限制），
③当变量个数（约束个数时，可先转化为其对偶问题，再用单纯形法或对偶单纯形法解之
④进行灵敏度分析时，有时会用到此法
四、对偶解的经济含义和影子价格
1.对偶解Y*=CBB-1的经济含义
设互为对偶的LP问题
maxZ=CX minW=Yb
(原) (对)
有 Z*=CBB-1b=W* (其中B为最优基)
因此
或者说Z*=y*1b1+y*2b2+y*mbm
则
其含义是：若对原问题右端常数项向量b中的某一常数项bi增加一个单位，目标函数的最优值Z*的变化将是Yi*。换句话说，Yi*表示当bi增加一个单位时，目标函数最优值的相应增量。实质上Yi*就是第i种资源边际价值的一种表现，也是对第i种资源的一种估价。
事实上，如引例中互为对偶LP问题分别描述生产计划问题和资源的定价问题，其数学模型分别是：
maxZ=2x1+3x2 minW=8y1+16y2+12y3
(原问题) (对偶问题)
对原问题用单纯形法求解所得最终表为
C
2
3
0
0
0
CB
XB
b
x1
x2
x3
x4
x5
2
x1
4
1
0
0
1/4
0
0
x5
4
0
0
-2
1/2
1
3
x2
2
0
1
1/2
-1/8
0
Z
14
0
0
1.5
0.125
0
由此，它们的最优解分别是X*=(4,2)T和Y=(1.5,0.125,0)
Z*=W*=14=8Y1*+16Y2*12Y3*
其中Y1*=1.5表示单独对设备台时增加1个单位，可使Z值增加1.5个单位的利润；Y2*=0.125表示单独对原材料A增加1个单位，可使Z值增加0.125个单位的利润；而Y3*=0表示单独对原材料B增加一个单位，却不使Z值增加。这是因为从最终表中可看出，在最优方案中，松驰变量x5=4，即表示在最优生产方案中，原材料B尚有4个单位剩余被闲置，不产生任何经济效益。
2.影子价格的定义把某一经济结构中的某种资源，在最优决策下的边际价值称为该资源在此经济结构中的影子价格。
影子价格是在最优决策下对资源的一种估价，没有最优决策就没有影子价格，所以影子价格又称“最优计划价格”，“预测价格”等等。
资源的影子价格定量的反映了单位资源在最优生产方案中为总收益应提供的收益，因此，资源的影子价格也可称为在最优方案中投入生产的机会成本。
3.影子价格的求法
(1)在非退化情况下：设B为LP问题的最优基，则
资源的影价=Y*=CBB-1
(2)在退化情况下：
当对偶问题有K个最优解，则第i种资源的影价=即影价的第i个分量等于这K个对偶解中第i个分量的最小值。
例如，设某资源利用问题为
maxZ=3x1+x2
最 终 表
3
1
0
0
XB
x1
x2
x3
x4
x1
2
1
1
1
0
x4
0
0
-1
[-3]
1
Z
6
0
2
3
0
x1
2
1
2/3
0
1/3
x3
0
0
1/3
1
-1/3
Z
6
0
1
0
1
∴ 资源1的影价
=min{y1*(1),y1*(2)}
=min{3,0}=0
资源2的影价=min{y2*(1),y2*(2)}=min{0,1}=0
4.影子价格的参谋作用
（1）指出企业挖潜革新的途径
（2）对市场资源的最优配置起着推进作用
（3）可为企业决策者提供调整最优生产方案的信息
CBB-1Pj－Cj<0说明第j种产品应投产
CBB-1Pj－Cj>0说明第j种产品不应投产尤其对新产品是否应投产，可按以上两式考虑。
（4）可以预测产品的价格
（5）可作为同类企业经济效益评估指标之一。
五、灵敏度分析面对市场变化，灵敏度分析的任务是须解决以下两类问题：
（1）当系数A、b、c中的某个发生变化时，目前的最优基是否仍最优（即目前的最优生产方案是否要变化）？
（2）为保持目前最优基仍是最优基，参数A、b、c允许变化范围是什么？
灵敏度分析的方法是在目前最优基B下进行的。即当参数A、b、c中的某一个或几个发生变化时，考察是否影响以下两式的成立？
1.对资源数量br变化的分析当b中某个br发生改变时，将影响基变量的取值XB=B-1b。若br的变化仍满足B-1b≥0，则目前的基B仍为最优基，仅在B-1b和CBB-1b的数量上有些改变。若br的变化使B-1b中某些分量小于0，则目前的基成为非可行基，为此，可用对偶单纯形法迭代求得新的最优解。
B-1b≥0给出了使最优基B保持不变时△br的允许的变化范围：
由解不等式组
B-1(b+△b)=B-1b+B-1可得：
其中为最终表中列的第i个分量，为B-1中第r列的元素。
例
2.对价值系数Cj变化的分析
（1）当CN中某个Cj发生变化时，只影到非基变量xj的检验数
由于
若，则△Cj≤σj。
这就是保持最优基不变下，△Cj的允许变化范围。否则，用单纯形法继续迭代，求得新的最优解。
（2）当CB中某个Cr发生变化时，
则会影响到所有非基变量的检验数σN=CBB-1N－CN。
解不等式组 =(CB+△CB)B-1N－CN=(CBB-1N－CN)+△CBB-1N≥0
即 (CBB-1N－CN)+(0,…,△Cr,…,0)B-1N≥0
得到使最优解不变△Cr的允许变化范围；
例
（3）对增加新产品的分析设革企业在计划期内，拟议生产新产品Xn+1，并已知新产品的单位利润为Cn+1，消耗系数向量为Pn+1=(a1,n+1,a2,n+1,…am,n+1)T，此时应如何分析才能确定该新产品理澡投产？
增加新产品应在不影响企业目前计划期内最优生产的前提下进行。因此可从现行的最估基B出发考虑：
若σn+1=CBB-1Pn+1－Cn+1<0，则应投产若σn+1=CBB-1Pn+1－Cn+1>0，则不应投入。
即新产品的机会成本小于目前的市场价格时，应投产否则不应投产。
（4）对增加新约束条件的分析在企业生产过程中，经常有新情况发生，造成原本不紧缺的某种资源变成为紧缺资源，对生产计划造成影响，如水、电和资源的供应不足等，对生产过程提出了新约束等。
对增加新约束条件的分析方法步骤是：
第一步：将目前的最优解代入新增加的约束，若能满足约束条件，则说明新增约束对目前的最优解（即最优生产方案）不构成影响（称此约束为不起作用约束），可暂时不考虑新增约束条件。否则转下一步；
第二步：把新增约束添加到原问题最终表中，并作初等行变换，构成对偶可行的单纯形表，并用对偶单纯形法迭代，求出新的最优解。
例：
（5）技术系数aij变化的分析第一种情况（当j(JN）：方法与增加一个新产品的分析相同。
第二种情况（当j(JB）：由于B中元素的改变影响到B-1的变化，因此也影响到T(B)。目前的基B对应的解有可能既不是原始可行，也不是对偶可行。于是不如重新求解。
第二章 特殊LP问题及其解法
所谓特殊LP问题是指LP模型的系数矩阵具有特殊的结构，有可能找到比单纯形法更为简便的求解方法，从而节省人力和物力。
§1 运输问题及其解法引例：
某公司经销甲产品，它下设三个加工厂，每日的产量分别为：A1-7吨，A2-4吨，A3-9吨。该公司把这些产品分别运往四个销售点，各销售每日销量为：B1-3吨，B2-6吨，B3-5吨，B4-6吨。已知从各工厂到各销售点的单位产品的运价为下表所示。问该公司应如何调运产品，在满足各销售点需求量的前提下，使总运费为最少。
平衡表（单位：吨） 运价表 （单位：元/吨）
销地产地
B1
B2
B3
B4
产量
B1
B2
B3
B4
A1
7
3
11
3
10
A2
4
1
9
2
8
A3
9
7
4
10
5
销 量
3
6
5
6
解：这是一个产销平衡的运输问题，其数学模型是：
设Xij表示从Ai调运产品到Bj的数量（吨），则
minZ=3X11+11X12+3X13+10X14+X21+9X22
+2X23+8X24+7X31+4X32+10X33+5X34
x11+x12+x13+x14 =7
x21+x22+x23+x24 =4
x31+x32+x33+x34 =9
x11 +x21 +x31 =3
x12 +x22 +x32 =6
x13 +x23 +x33 =5
x14 +x24 +x34 =6
xij≥0 (i=1,2,3,j=1,2,3,4)
一、产量平衡的运输问题及其解法
1.产销平衡的运输问题的数学模型及其特点
特点：（1）其系数矩阵的结构疏松，且每一列向量
Pij=(0,…1,…1,…0)T=ei+em+j
可以证明，r(A)=m+n－1。即有m+n－1个独立方程。
于是，该LP问题有且仅有m+n－1个基变量。
（2）（产销平衡条件）
（3）因为故必有可行解和最优解。
由于上述特点，若按单纯形法求解必须增加人工变量，致使计算量大大增加，故用特殊解法──表上作业法。
2.表上作业法表上作业法实质上还是单纯形法，但具体计算和术语上有所不同。其计算步骤方法，并通过对引例的求解过程说明之一。
（1）用最小元素法确定初始方案（即初始基可行解）
切记在产销平衡表上必须且只能填写m+n－1个数字格
（2）用位势法求出空格的检验数并进行最优解的判别设u1,u2,…um; v1,v2,…,vn是对应运输问题m+n个约束条件的对偶变量，B为含有人工变量的初始可行基，由LP问题的对偶理论知
CBB-1=(u1,u2,…um; v1,v2,…,vn)
而每个决策变量Xij相应的系数向量Pij=ei+em+j，所以CBB-1Pij=ui+vj
于是，检验数σij=CBB-1Pij－Cij =(ui+vj)－Cij
又各基变量的检验数为0，故对每个基变量所在的数格的检验数有
(ui+vj)－Cij =0 i,j(JB
即有方程组
共m+n个未知数 s=m+n－1个方程显然上述方程有解，且由于含有一个自由变量，因此，可令任一未知数为0，就可求出上述方程组的解(ui1,ui2,…uim,vj1,vj2,…vjn)──称为位势解。
如用位势法求引例初始基可行解的检验数：
销地产地
B1
B2
B3
B4
ui
A1
-1
3
-2
11
③
⑩
0
A2
1
-1
9
②
+1
⑧
-1
A3
-10
7
④
-12
⑩
⑤
-5
vj
2
9
3
10
第一步：将运价表中的数字分别写在各格听右上角，并对基变量相应的运价加圈，同时在表中增加vj和ui列。
第二步：利用圈数格分别算出ui和vj，即令u1=0，然后按ui+vj=Cij (i,j(JB)，相继确定ui，vj的值。于是有v3=3,v4=10,u2=-1,v1=2,u3=-5,v2=9
第三步：按σij= (ui+vj)－Cij (i,j(JN)算出表中各空格（即非基变量）的检验数：
σ11=(0+2)－3=-1，σ12=(0+9)－11=-2，σ22=-1，σ24=1，σ31=-10，σ33=-12
由于运输问题的目标函数是求最小化，故判别最优解的准则是所有的σij=CBB-1Pij－Cij≤0
因为(24=+1>0，所以目前尚未得到最优解，尚须改进
（3）在调运平衡表上用闭回路法进行调整，得到新的基可行解（新的调运方案）
i) 确定换入变量：自上而上，自左向右第一个正检验数相应的非基变量（空格）为入基变量。
ii) 作闭回路：以换入变量空格为出发点，用水平或垂直线向前划，当碰到某一恰当数格转90(后，继续前进，直至回到起始空格止。
iii) 确定调整量(=min{第奇数次拐角格的调运量}
iv) 在闭回路上进行调整：对闭回路上每个奇数次拐角格的调运量－(对闭回路上每个第偶数次（含起始格）拐角格的调运量+(。调整后，将闭回路中为0的一个数格作为空格（即出基变量）。
闭回路外的各调运量不变。这样便得到新的调运方案（新基可行解）
销地产地
B1
B2
B3
B4
产量
A1
(+1)4
3(-1)
7
A2
3
(-1)1
(+1)
4
A3
6
3
9
销量
3
6
5
6
对调整后所得的新方案，再进行检验，已得到最优解（最优调运方案）；
从A1调运到5吨到B3，调运2吨到B4
从A2调运到3吨到B1，调运1吨到B4
从A3调运到6吨到B2，调运3吨到B4
总运费最小是85元
（4）在进行表上作业法须注意的问题：
i) 在最终调运表中，若有某个空格（非基变量）的检验为0时，则表明该运输问题有多重调运方案；
ii) 在确定初始方案时，若在(i,j)格填上某数字后,出现Ai处的余量=Bj处的需量，此时必须在平衡表上被划去行和列相应位置的任一空格处填上一个“0”，以满足数格=m+n－1个的需要；
iii) 在用闭回路法调整时，当闭回路上第奇数次拐角数有几个相同的最小值时，调整后只能有一个空格，其余均要保留数“0”，以保证数格=m+n－1个的需要。
以上ii)，iii)均出现退化解。
iv) 用最小元素法所得到的初始方案可以不唯一。
二、产销不平衡的运输的问题及其求解方法
1.数学模型：产大于销 产小于销
2.解法思路：
将不平衡转化为平衡。即当时，考虑在平衡表中增加一虚拟列，表示增加一个销货点(j=n+1)如仓库，其销货量为，且各运价Cin+1=0；当时，考虑在平衡表中增加一虚拟行，表示增加一个新产地，且各运价Cm+1j=0。然后再用产销平衡的运输问题的解法进行解之。
例三、转运问题及其解法：
1.所谓转运问题是在以下背景产生的：
(1)每个工厂生产的产品不直接运到销地，可以几个产地集中一起运。
(2)运往各销地的物资可先运给其中的几个销地，再转运给其它销地。
(3)除产、销地之外，还可以有几个中间转运站，在产地之间，销地之间或产销之间转运。
凡类似上述情况下的调运物资并使总运费最小的问题统称为转运问题。
2.求解“转运问题”的思路是把问题中所有的产地、中转站和销地都既看作产地，又都看作销地，把“转运问题”变成扩大后的产销平衡的运输问题处理。
3.求解“转运问题”的方法步骤：
(1)建立扩大的产销平衡运输问题单位运价表。其中
1)对两地不能直接运输的单位运价定为M（很大的正数）；
2)对所有中转站Tj的产量和销量定为相等，设定为；
3)对产量列的各数据可按下式计算并填入：
Ai的产量=ai+(,Tj产量=(，Bj的产量=(
4)对销量行的各数据可按下式计算并填入：
Aj的产量=(,Tj销量=(，Bj的销量=(+bj
(2)用表上作业法进行求解
§2 指派问题及其解法引例任务人员
E
J
G
R
甲
2
15
13
4
乙
10
4
14
15
丙
9
14
16
13
丁
7
8
11
9
解：设Xij表示第i人从事第j项工作，且
因此，该问题的数学模型为
MinZ=2X11+15X12+13X13+4X14+10X21+4X22+14X23+15X24
+9X31+14X32+16X33+13X34+7X41+8X42+11X43+9X44
表示第j项工作只指派人完成
表示第i人被指派完成一项工作
Xij=0或1(i,j=1,2,3,4)
诸如此类，有n项任务，恰好有n个人可承担这些任务，但由于每人的专长技术不同，完成任务的效率(所费时间_不同，为使完成n项任务的总效率最高（即所需总时最少），应如何指派（分派）人员的问题统称为指派（分派）问题。
一、指派问题的数学模型及其特点
1.数学模型：
2.特点
（1）给定一个指派问题时，必须给出效率矩阵（系数矩阵）C=(Cij)nxn,且Cij(0，因此必有最优解()。
（2）指派问题是一种特殊的平衡的运输问题，由于模型结构的特殊性（看作每产地的产量均为1，每销地的销量均为1），故可用更为简便的匈牙利法进行求解。
（3）解矩阵
是指派问题的可行解，但不一定是最优解。
二、指派问题的解法──匈牙利法
1.匈牙利法的基本思想是：对同一项工作（任务）j来说，同时提高或降低每人相同的效率（常数ti），不影响其最优指派；同样，对同一个人i来说，完成各项工作的效率都提高或降低相同的效率（常数di），也不影响其最优指派，因此可得到新的效率矩阵(bij)nxn，其中
bij=Cij+ti+dj （对所有的i,j）
则新的目标函数为
其中为常数这说明Z(与Z同时达到最小值。因而最优解相同。故指派问题有以下性质：
若从效率矩阵(Cij)nxn的一行（列）各元素中分别减去该行（列）的最小元素，得到的新效率矩阵(bij)nxn不改变原指派问题的最优解。
2.匈牙利法
三、对求最大化的指派问题，（即求）,可采用构造新的效率矩阵(M－Cij)nxn，其中M=max{Cij}，（显然M－Cij(0），将其转化为
求所得到的最优解就是原问题的最优解。事实上
由于nM为常数，因此，使Z(取得最小的最优解就是使Z取得最大的最优解。
4.以上讨论的指派问题是效率矩阵的行数等于列数，即m+n的情况。当m(n时，则可用增加虚设的零元数行（列）使效率矩阵变成方阵后，再用匈牙利法求解。
当m<n时 当m>n时
5.指派问题必有最优解，但可以不唯一。
§3 整数线性规划问题及其解法
一、整数线性规划在上一章讨论的LP问题中,对决策变量只限于不能取负值的连续型数值,即可以是正分数或正小数。然而在许多经济管理的实际问题中，决策变量只有非负整数才有实际意义。对求整数最优解的问题，称为整数规划(Integer Programming)(简记为IP)。又称约束条件和函数均为线性的IP为整数线性规划(Integer Linear Programming)(简记为ILP)。
ILP问题数学模型的一般形式为：求一组变量X1,X2,…,Xn，使
人们对IP感兴趣，还因为有些经济管理中的实际问题的解必须满足如逻辑条件和顺序要求等一些特殊的约束条件。此时需引进逻辑变量（又称0-1变量），以“0”表示“非”，以“1”表示“是”。凡决策变量均是0-1变量的IP为0-1规划。
严格地说，IP是个非线性问题。这是因为IP的可行解集是由一些离散的非负整数所组成，不是一个凸集。迄今为止，求解IP问题尚无统一的有效方法。
求解ILP问题方法的思考：
1）“舍入取整”法：即先不考虑整数性约束，而去求解其相应的LP问题（称为松驰问题），然后将得到的非整数最优解用“舍入取整”的方法。这样能否得到整数最优解？否！这是因为“舍入取整”的解一般不是原问题的最优解，甚至是非可行解。
但在处理个别实际问题是，如果允许目标函数值在某一误差范围内，有时也可采用“舍入取整”得到的整数可行解作为原问题整数最优解的近似。这样可节省求解的人力、物力和财力。
设X*是原ILP的最优解，X是其松驰问题的非整数最优解，是“舍入取整”的整数可行解，d为给出目标函数值的允许误差。由于(CX*(CX
所以 CX*－(CX－
当CX－(d时，则可将作为X*的近似解。
2）完全枚举法 此法仅在决策变量很少的情况下才实际有效。对于变量稍多的ILP问题则几乎不可能。如在指派问题中，当n=20，则有可行解20！个，而20！>2X1018，这在计算机上也是不可能实现的。
3）求解ILP问题常见的几种解法有：分枝定界法，割平面法，0-1规划的特殊解法等。
二、0-1变量产生的背景和应用引例（详见书P72例2）
由引例可见，利用0-1变量处理一类“可供选择条件”的问题查非常简明且方便的。下面再进一步分别说明对0-1变量的应用。
假定现有m种资源对可供选择的n个项目进行投资的数学模型为：
求一组决策变量X1,X2,…,Xn，使
（3.1）
满足
其中，Cj表示投资第j项获得的期望收益，aij表示第i种资源投于第j项目数量，bj表示第i种资源的限量。
1.对可供项目的选择
（1）如果在可供选择的前k(k(n)个项目中，必须且只能选择一项，则在(3.2)中加入新的约束条件：
（2）如果可供选择的k(k(n)个项目是相互排斥的，则在(3.2)中加入新的约束条件：
同时它还表示在第k个项目中至多只能选择一项投资。
（3）如果在可供选择的k(k(n)个项目中，至少应选择一项投资，则在(3.2)中加入新的约束条件：
（4）如果项目j的投资必须以项目i的投资为前提，则可在(3.2)中加入新的约束条件：
Xj(Xi
（5）如果项目i与项目j要么同时被选中，要么同时不被选中，则在(3.2)中加入新的约束条件：
Xj=Xi (i(j)
2.对可供资源的选择
（1）如果对第r种资源br与第t种资源bt的投资是相互排斥的，即只允许对资源br与bt中的一种进行投资，则可将(3.2)的第r个和第t个约束条件改写为：
①
②
其中y为新引进的0-1变量，M为充分大正数。易见，当y=0时，①式就是原来的第r个约束条件，具有约束作用。此时对②式而方，无论Xj为何值，都成立，毫无约束作用，这就使问题仅允许第r种资源进行投资。当y=1时，②式对Xj起了约束作用，而①式成了多余的条件。到底是满足①还是②，则视问题在求出最优解后，y为0还是1而言。
（2）如果问题是要求在前m个约束条件中至少满足k(1<k<m)个，则可将(3.2)中的原约束条件修改为：
其中M为充分大的正数，k为整数。
3.在固定费用问题中的应用（详见书）
三、0-1规划的解法
1.完全枚举法：其基本思想是：首先将全部变量取0或1的所有组合（解）列出，然后在逐个检查这些组合（解）是否可行的过程中，利用增加并不断修改过滤条件的办法，减少计算量，以达到求出最优解之目的。
例（详见书）
该法只在变量少的情况下使用才有效。
2.隐枚举法：
0-1规划的隐枚举法是一种特殊的分枝定界法，其基本思想是利用变量只能为0或1两个值的特性，进行分枝定界，以减少枚举而达到求出最优解之目的。该法适用于任何0-1规划问题的求解。
