第三章 对偶理论与灵敏度分析
3.1 对偶理论问题的提出（1学时）
3.1.1 对偶线性规划问题的导出
对一个问题可以从不同的角度去看，解决一个问题也可以有多种方法。
例3.6 一个工厂生产三种产品所用工时和材料以及单位产品利润如下表所示，决策应该
怎么生产获得最大利润。
表3-3
单位产品消耗ⅠⅡⅢ总量
工时1 1 1 3
材料1 4 7 9
利润2 3 3
其线性规划模型为
123max z2x3x3x=++
⎪
⎩⎪
⎨⎧
≥≥≥≤++≤++
0,0,09743
..
321321321
xxxxxxxxx
ts
或1
2
3x
max z(2,3,3)x
x⎛⎞
⎜⎟=⎜⎟
⎜⎟⎝⎠
⎪⎪⎪⎪
⎩⎪⎪⎪⎪
⎨⎧
⎟⎟⎟
⎠⎞
⎜⎜⎜
⎝⎛
≥
⎟⎟⎟
⎠⎞
⎜⎜⎜
⎝⎛⎟⎟
⎠⎞
⎜⎜
⎝⎛
≤
⎟⎟⎟
⎠⎞
⎜⎜⎜
⎝⎛
⎟⎟
⎠⎞
⎜⎜
⎝⎛
00093
741111
..
321321
xxxxxx
ts
从另一个角度去思考这个问题，就是当另外一个工厂提出购买这个厂的所有工时和材料
时，工厂应该怎么做决策才会使得这样一个交易出现双赢的局面。
简要的介绍双赢的原理：价格尽量低，使得其产品具有竞争力，同时希望客户能出更高
的价格，这样企业就可以获得更多的利润。亦即，
生产一件A的工时和材料的销售收入应该不少于A产品的单位利润；
生产一件B的工时和材料的销售收入应该不少于B产品的单位利润；
生产一件C的工时和材料的销售收入应该不少于C产品的单位利润。
定义工时和材料销售价格分别为y1,y2，于是有
2193minyyW+=⎟⎟
⎠⎞
⎜⎜
⎝⎛
=
21)9,3(min
yy
W
⎪⎪
⎩⎪⎪
⎨⎧
≥≥≥+≥+≥+
0,037342
..
21212121
yyyyyyyy
ts或
⎪⎪⎪
⎩⎪⎪⎪
⎨⎧
≥⎟⎟
⎠⎞
⎜⎜
⎝⎛⎟⎟⎟
⎠⎞
⎜⎜⎜
⎝⎛
≥⎟⎟
⎠⎞
⎜⎜
⎝⎛
⎟⎟⎟
⎠⎞
⎜⎜⎜
⎝⎛
0322
714111
..
2121
yyyy
ts
上述两个线性规划模型是在同一企业的资源状况和生产技术条件下产生的，是同一个问
题从不同角度来观察所产生的，因此两者是密切相关的，我们称这两个线性规划问题是互为
4 运输问题
1、运输问题表上作业法的基本步骤。
答：表上作业法的基本步骤可参照单纯形法归纳如下：
（1）找出初始基可行解：即要在阶产销平衡表上给出“”个数字格（基变量）；
（2）求各非基变量（空格）的检验数，判断当前的基可行解是否是最优解，如已得到最优解，则停止计算，否则转到下一步；
(3确定入基变量，若，那么选取为入基变量；
(4确定出基变量，找出入基变量的闭合回路，在闭合回路上最大限度地增加入基变量的值，那么闭合回路上首先减少为“0”的基变量即为出基变量；
（5）在表上用闭合回路法调整运输方案；
（6）重复2、3、4、5步骤，直到得到最优解。
2、“最小元素法”和“伏格尔”法的基本思想及基本操作。
答：最小元素法的基本思想是就近供应，即从单位运价表中最小的运价开始确定产销关系，依此类推，一直到给出基本方案为止。
伏格尔法把费用增量定义为给定行或列次小元素与最小元素的差（如果存在两个或两个以上的最小元素费用增量定义为零）。最大差对应的行或列中的最小元素确定了产品的供应关系，即优先避免最大的费用增量发生。当产地或销地中的一方在数量上供应完毕或得到满足时，划去运价表中对应的行或列，再重复上述步骤，即可得到一个初始的基可行解。
3、闭合回路的构成以及利用闭合回路法求检验数的基本操作。
答：判断基可行解的最优性，需计算空格（非基变量）的检验数。闭合回路法即通过闭合回路求空格检验数的方法。从给定的初始方案的任一空格出发寻找闭合回路，闭合回路顶点所在格括号内的数字是相应的单位运价，单位运价前的“+”、“-”号表示运量的调整方向。
空格处单位运量调整所引起的运费增量就是空格的检验数。仿照此步骤可以计算初始方案中所有空格的检验数。
4、利用位势法求检验数以及利用闭合回路进行方案调整的基本操作。
答：位势法求解非基变量检验数的基本步骤：
第一步：把方案表中基变量格填入其相应的运价并令；让每一个基变量都有，可求得所有的位势；
1 / 137 运筹学（第3版）习题答案
第1章线性规划 P36
第2章线性规划的对偶理论
P74
第3章整数规划 P88
第4章目标规划 P105
第5章运输与指派问题P142
第6章网络模型 P173
第7章网络计划
P195
第8章动态规划 P218
第9章排队论 P248
第10章存储论P277
第11章决策论P304
第12章 多属性决策品P343
第13章博弈论P371
全书420页
第1章 线性规划
1.1工厂每月生产A、B、C三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－23所示．
表1－23
产品
资源 A B C 资源限量
材料(kg) 1.5 1.2 4 2500
设备(台时) 3 1.6 1.2 1400
利润(元/件) 10 14 12
根据市场需求,预测三种产品最低月需求量分别是150、260和120,最高月需求是250、310和130.试建立该问题的数学模型,使每月利润最大．
【解】设x1、x2、x3分别为产品A、B、C的产量，则数学模型为
123123123123123max1014121.51.24250031.61.21400150250260310120130,,0Zxxxxxxxxxxxxxxx
1.2建筑公司需要用5m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格及数量如表1－24所示：
表1－24 窗架所需材料规格及数量
型号A 型号B
每套窗架需要材料 长度（m） 数量(根) 长度(m) 数量(根)
A1：2 2 B1：2.5 2
A2：1.5 3 B2：2 3
需要量（套） 300 400 2 / 137 问怎样下料使得（1）用料最少；（2）余料最少．
【解】 第一步：求下料方案，见下表。
方案 一 二 三 四 五 六 七 八 九 十 需要量
第一章 线性规划及单纯形法
一、复习思考题
1 试述线性规划数学模型的结构及各要素的特征。
2 线性规划的解有哪几种情况。
3 什么是线性规划问题的标准形式，如何将一个非标准型的线性规划问题转化为标
准形式。
4 试述线性规划问题的可行解、基解、基可行解、最优解的概念以及上述解之间的相互关系。
5 试述单纯形法的计算步骤，如何在单纯形表上去判别问题是具有惟一最优解、无穷多最优
解、无界解或无可行解。
6 如果线性规划的标准型式变换为求目标函数的极小化min z，则用单纯形法计算时如何判
别问题已得到最优解。
7 在确定初始可行基时，什么情况下要在约束条件中增添人工变量，在目标函数中人工变量
前的系数为(一M)的经济意义是什么。
8 什么是单纯形法计算的两阶段法，为什么要将计算分两个阶段进行，以及如何根据第一阶
段的计算结果来判定第二阶段的计算是否需继续进行。
9 简述退化的含义及处理退化的勃兰特规则。
10 举例说明生产和生活中应用线性规划的方面，并对如何应用进行必要描述。
二、判断下列说法是否正确
1、 图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的；
2、 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可
行域的范围一般将扩大；
3、线性规划问题的每一个基解对应可行域的一个顶点.
4、如线性规划问题有最优解，则最优解一定对应可行域边界上的一个点；
5、用单纯形法求解标准型式的线性规划问题时，与0＞j对应的变量都可被选作换入变量；
6、单纯形法计算中，选取最大正检验数σk对应的变量xk作为换入变量，将使目标函
数值得到最快的增长；
7、线性规划问题任一可行解都可以用全部基可行解的线性组合表示；
9、对一个有n个变量，m个约束的标准型的线性规划问题，其可行域的顶点恰好为mnC
个；
10、单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行
解；
