严格不等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。 原问题和对偶问题解的对应关系 max z?3x1?5x2
?x3 ?8? x1
? 2x2 ?x4 ?12?s.t. ?
?x5?36?3x1?4x2
? ?x1,x2,x3,x4,x5?0 cj→ 3 5 0 0 0
θ
CB XB b x1 x2 x3 X4 x5
2 X3 4 0 0 1 2/3 -1/3
5 X2 6 0 1 0 1/2 0
3 0 0 X1 4 1 -2/3 1/3 0 0 0 -1/2 -1
由原问题的最终迭代单纯形表可以看到其对偶问题的最优解为其松弛变量检验数的相反
**数，即： ? 1 ? 最优值都是42，即：
Y??0,,1? ?2? min ? ?2x?3x?5x?2x?3x12345松紧定理例题（1）
?x1?x2?2x3?x4?3x5?4已知线性规划问题，
? s.t. ?2x1?x2?3x3?x4?x5?3 ?x,x,x,x,x?0?12345
* 试用对偶性质求出原问题的最优解。 其对偶问题的最优解为： Y * ? 4 , 3 ? z ??5?? ?55?解：先写出其对偶问题 max z?4y1?3y2
? y1?2y2?2 (1)
? y ?y?3 (2)
2?1
??2y1?3y2?5 (3)
s.t. ? y1?y2 ?2 (4)?
?3y1?y2 ?3 (5)
? ??y1,y2?0
z???42将对偶问题的最优值代入到对偶问题的所有函数约束中去发现（2）（3）（4）为严格不等式，由互补松弛性定理可以得到： x * ? * ? x * ,又因为 y 1 , y 2 ? 0 ，则原问题的两个约x234?0***束条件应该取等式，综上可得： ?? x?3x?4x?1?1?15故原问题的最优解为： ??*?** X*?1,0,0,0,1T z*?5??x5?1?2x1? x5?3?3.3 对偶问题的经济解释
我们知道对任何一个LP问题，都有一个与之相对应的对偶问题，而在实际问题中，LP问题总是与经济活动相联系的，因此，一个LP问题及其对偶问题都有一定的经济意义。概括起来讲，一般这样理解其经济意义：若原问题是求解如何最优配置（利用或使用）资源的问题，则其对偶问题就是求解如何恰当的估计资源价值的问题。前者为资源的最优使用（配置问题），后者为资源的恰当评价（价格问题）。对偶问题的最优解（即资源的最优价格），在经济上就被称为―影子价格‖（Shadow Price）。
在上世纪30年代末，荷兰经济学家丁伯根和前苏联数学家、经济学家康脱洛维奇就分别提出了影子价格理论。丁伯根认为影子价格是反映资源得到合理配置的―预测价格‖。康脱洛维奇则是去研究一种使生产单位的直接物质利益与以国民经济系统最优计划所表示的全局利益完全相吻合的价格，即最优计划价格。
1）影子价格是针对LP问题的某一具体的约束条件而 言的；
2）对偶问题的对偶变量就是原问题约束条件的影子 价格变量；
3）最终单纯形表检验数行可以看出该问题的影子价 格。
对偶问题解的经济含义分析： 从单纯形法的矩阵描述中，目标函数取值 Z = CBB-1 b ，和检验数 CN - CBB-1N 中都有乘子 Y = CBB-1。
设B 是{ max Z = CX | AX ≤ b，X ≥0 }的最优基矩阵，由强对偶定理知
Z* =CX*= CBB-1b=Y*b=W*由此 定义：在一对对偶问题中，若P的某个约束条件的右端常数 b i 增加1个单位时，所引起的目标函数最优值 的改变量 y * 称为第 i 个约束条件的影子价格，又称为边际价Z *
i格、Lagrange乘子、灵敏度系数。
线性规划问题约束条件的右端常数项的单位改变量所引起的最优值的改变量就是该约束条件的影子价格。
影子价格在经济管理中的应用
影子价格说明了不同资源对总的经济效益产生的影响，因此，一般来说影子价格可以对企业的经营管理者提供一些有价值的信息。
（1）影子价格可以告诉企业管理者，若要增加资源以增加收益的话，应优先增加哪种资源最为有利。
（2）由影子价格可以知道花多大的代价增加资源才是有利的。
（3）由影子价格可以帮助企业管理人员制定新产品的价格，或判断某种新产品是否值得去投产。
3.4 对偶单纯形法
? 由前面的知识我们可以知道：在单纯形表中进行迭代时，在b列中得到的是原问题
的基可行解，检验数行得到的是每步对应对偶问题的可行解。通过逐步迭代，当在
??检验数行得到对偶问题的解也是基可行解时，此时原问题与对偶问题都是最优解了。
根据对偶问题的对称性，我们可以这样考虑：若保持对偶问题的解是基本可行解，即 ，而原问题在非基本可行解的基础上，通过逐步迭代 ? j ? 0达到基可行解，这样也可以得到最优解。其优点是原问题的初始基可行解不一定要是基本可行解，可以从非基本可行解开始迭代，避免引入更多的变量。
原始单纯形法其基本思路：在换基迭代过程中，始终保持基变量值非负，逐步使检验数变成非正，最后求得最优解或判断无最优解。
对偶单纯形法其基本思路：在换基迭代过程 中，始终保持检验数非正，逐步使基变量值变成非负，最后求得最优解或判断无最优解。 对偶单纯形法的步骤
（1）把m阶LP问题化成一个其系数阵中含有一个m阶单位阵的标准形式（但是允许其右端常数为负值），列出对应的初始单纯形表，检查b列的数字，若都为非负，检验数都为非正，则已经得到最优解，停止计算。若检查b列的数字时发现至少还有一个负分量，检验数都保持非正，转入下一步计算；
（2）检查表中b列各数字，只要存在一个负数 b ? 0 其所在行中所有的
l 系数 a ? 0 j ? 1 , , n ，则原问题无可行 2 , ?lj 解，停止计算；否则转下一步； （3）确定离基变量
iil
???j?（4）确定进基变量 ?min?alj?0??kj?a alk?lj??
以 lk 为主元，按原单纯形法对当前表格进行换基运算，得到新的单纯形表。重复以上步骤，直至得到最优解。下面举例说明这种对偶单纯形法的运算过程。 例：用对偶单纯形法求解下列LP问题 min ? ? 3x1?2x2
?2x1?3x2?18
? x? x?2? 2s.t. ?1
? x1?3x2?10 ??x1,x2?0
max z ? ?3x1?2x2解：该LP问题可以用图解法、人工变量法
?18?2x1?3x2?x3 求解，这里采用对偶单纯形法，先 化为标准形：
? x? x ?x ?2?124s.t. ? ?x5?10 max z ? ?3x1?2x2? x1?3x2 ??x1,x2,x3,x4,x5?0 ?18 ?2x1?3x2?x3 ??x ?x ?x
??2?124 s.t. ? ?x5??10 ??x1?3x2 ??x1,x2,x3,x4,x5?0
??min?bb?0??b???acjCB00-2-3-2000XBb810/3x11x20010x31000x40100x511/3-1/3-2/3—— x3x4x2比值-16/3-4/31/3-7/37/4检验数行
此时所有检验数都为非正，b列中各数字均为正 数，表明该LP问题已得到最优解，即：
T
X*?4,2 z*?16
使用对偶单纯形法求解LP问题的条件
? 单纯形表的b列中至少有一个负分量； ? 单纯形表的检验数行全部元素 ? 0 。
隐含： max——决策变量系数全为负数、min ——决策变量系数全为正数 从以上求解过程可以看到对偶单出形法求解有以下优点：
? 初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，不需要加入人
工变量，因此简化了计算。
? 当变量多于约束条件这样的LP问题，用对偶单纯形法求解可以减少计算工作量；
而约束条件很多的LP问题，可以先将它变换为对偶问题，然后用对偶单纯形法求解。
第5章 运输模型
运输模型是线性规划诸多模型中较早引起人们关注的一类模型，由美国学者希奇柯克 （Hitchcock，1941）和柯普曼（Koopman，1947）独立提出。
? 运输模型是线性规划诸多模型中的特例。
? 运输模型的约束方程组的系数矩阵具有特殊的结构，使得有可能找到比单纯形法更
为简便的求解方式。
? 适用于运输问题的专门求解方法不仅适用于运输问题本身，还适用于其他相当多的
应用问题（比如适用于指派问题），得以得到人们的高度重视和广泛的应用。 ? 在经济建设中经常会碰到大宗物资的调运问题，如煤、钢铁、木材、粮食等物
??
