第二章对偶规划

（1）标准型的矩阵形式——

（2）将式中矩阵写成分块矩阵形式

第2章

对偶理论和灵敏度分析第1节单纯形法的矩阵描述略讲将分块形式代入矩阵形式标准型，得出两个基本表达式：（1）由约束条件

可得用非基变量表示基变量的表达式：（2-1）

略讲（2）将式（2-1）代入目标函数的表达式，可得：用非基变量表示目标函数的表达式：略讲（3）借助一个恒等式推出用非基变量表示目标函数的另一个等价表达式：代入式（2-2），并令（2-4）

单纯形乘子

略讲三、单纯形表格的矩阵形式：

cj

CB

XB

xjbCBCN

0

略讲第2节改进单纯形法（自学）略讲一、对偶思想1.

对偶思想举例---矩形的面积与周长关系的两种表述：周长一定的矩形中，以正方形面积最大；面积一定的矩形中，以正方形周长最小；第3节

对偶问题的提出----§1.6对偶是指对同一问题从不同的角度观察，得到两种独立的表述的思想。例1

要求制定一个生产计划方案，在设备和原材料可能供应的范围内，使得产品的总利润最大：甲产品乙产品提供量设备128台时材料A4016kg材料B0412kg利润23单位元二、对偶问题的提出它的对偶问题就是一个价格系统，使在平衡了设备和原材料的直接成本后，所确定的价格系统最具有竞争力。（用于生产第i种产品的资源转让收益不小于生产该种产品时获得的利润）

若工厂自己不生产甲和乙产品，将现有的设备及原材料转为外租时，那么上述的价格系统能保证不亏本又最富有竞争力（包工及原材料的总价格最低）。

当原问题和对偶问题都取得最优解时，这一对线性规划对应的目标函数值是相等的：

Zmax=Wmin=14

对偶变量的经济意义可以解释为对设备及原材料的单位定价。表示对偶关系3.再举一个对偶问题的例子：饮食与营养问题

例2

采购甲、乙、丙、丁4种食品量分别为x1，x2，x3，x4单位，在保证人体所需维生素A、B、C前提下，使总的花费最小。

成本构建对偶线性规划模型：

换一个角度，生产营养药制品公司力图制造各种营养药品代替食品。于是，营养药品的单位成本不能超过相应食品的市场价格。制药公司面对的问题是为营养药品确定单价，以获得最大的收益，同时与真正的食品竞争。由此得到下面的对偶问题：二、原问题和对偶问题的关系1.对称形式的对偶关系（1）定义：若原问题是

则定义其对偶问题为:这两个式子之间的变换关系称为“对称形式的对偶关系”。

（2）对称形式的对偶关系的矩阵描述（L）

（3）怎样从原始问题写出其对偶问题？

对称性问题按照定义“上、下”交换，“左、右”换位，不等式变号，“极大”变“极小”例3

写出下面线性规划的对偶规划

（1）原问题（2）

对偶问题特点：对偶变量符号不限，系数阵转置。(特点：等式约束)2.非对称形式的对偶关系：为什么？证明略。看一个具体例子：例4

写出下面线性规划的对偶规划：

原问题（或对偶问题）

对偶问题（或原问题）

目标函数MaxZ目标函数MinW约束条件数：m个第i个约束条件类型为“≤”第i个约束条件类型为“≥”第i个约束条件类型为“=”

对偶变量数：m个第i个变量≥0第i个变量≤0第i个变量是自由变量

决策变量数：n个第j个变量≥0第j个变量≤0第j个变量是自由变量

约束条件数：n第j个约束条件类型为“≥”第j个约束条件类型为“≤”第j个约束条件类型为“=”

（2）原始问题与对偶问题关系表对偶定理是揭示原始问题与对偶问题解之间重要关系的

定理1

对称性定理(证明略)

对偶问题的对偶是原问题。第4节

线性规划的对偶理论一系列定理。定理2弱对偶定理对于任意的可行解成立该结论对非对称形式的对偶问题同样成立。由该定理可以得到关于“界”的结果:极小化问题有下界——推论1

极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。极大化问题有上界——推论2

极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。推论3

若原问题与对偶问题都有可行解，则它们都有最优解。能达到最优（由连续函数的性质得到）证毕推论4若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。其逆不真。证明由弱对偶定理得:C=bCX≤Yb弱对偶定理已知结论最优解定义X=CX≤bY=特别取C≤Yb证明思路若原问题有最优，则对偶问题也有最优，且最优值相等，反之亦然。定理4强对偶定理推论对偶问题的最优解为原问题最优表中，相应的松弛变量的检验数的相反数。单纯形方法计算过程:略讲甲产品乙产品提供量设备128台时材料A4016kg材料B0412kg利润23单位元定理5互补松弛定理略讲为了保证检验数的非正性取第6节

对偶单纯形法最小比值原则为了保证检验数的非正性取应知道此方法：回到（55张）前几张PPT总结对偶单纯性方法。作业P-73-1.12P-73-1.125/7202实际上，此题为无界解。举例：举例：第7节

灵敏度分析将模型写在黑板上二、思考练习考察线性规划问题(1)：一、讨论总结对偶定理的应用。写出其对偶问题;讨论：如果知道是原问题的可行解（用什麽办法可以较方便地寻找一个可行解？），能否对对偶问题的目标函数值做出估计？以此为启发，能否对原问题目标函数值作出估计？