第二章对偶规划

第二章对偶规划第1页，课件共159页，创作于2023年2月将分块形式代入矩阵形式标准型，得出两个基本表达式：（1）由约束条件

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

略讲第2页，课件共159页，创作于2023年2月（2）将式（2-1）代入目标函数的表达式，可得：用非基变量表示目标函数的表达式：略讲第3页，课件共159页，创作于2023年2月（3）借助一个恒等式推出用非基变量表示目标函数的另一个等价表达式：代入式（2-2），并令（2-4）

单纯形乘子

略讲第4页，课件共159页，创作于2023年2月三、单纯形表格的矩阵形式：

cj

CB

XB

xjbCBCN

0

略讲第5页，课件共159页，创作于2023年2月第2节改进单纯形法（自学）略讲第6页，课件共159页，创作于2023年2月一、对偶思想1.

对偶思想举例---矩形的面积与周长关系的两种表述：周长一定的矩形中，以正方形面积最大；面积一定的矩形中，以正方形周长最小；第3节对偶问题的提出----§1.6对偶是指对同一问题从不同的角度观察，得到两种独立的表述的思想。第7页，课件共159页，创作于2023年2月例1

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

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

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

Zmax=Wmin=14

对偶变量的经济意义可以解释为对设备及原材料的单位定价。表示对偶关系第10页，课件共159页，创作于2023年2月3.再举一个对偶问题的例子：饮食与营养问题

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

成本第11页，课件共159页，创作于2023年2月构建对偶线性规划模型：

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

第14页，课件共159页，创作于2023年2月则定义其对偶问题为:这两个式子之间的变换关系称为“对称形式的对偶关系”。

第15页，课件共159页，创作于2023年2月（2）对称形式的对偶关系的矩阵描述（L）

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

对称性问题按照定义“上、下”交换，“左、右”换位，不等式变号，“极大”变“极小”第16页，课件共159页，创作于2023年2月例3写出下面线性规划的对偶规划

第17页，课件共159页，创作于2023年2月（1）原问题（2）对偶问题特点：对偶变量符号不限，系数阵转置。(特点：等式约束)2.非对称形式的对偶关系：为什么？证明略。看一个具体例子：第18页，课件共159页，创作于2023年2月例4写出下面线性规划的对偶规划：第19页，课件共159页，创作于2023年2月第20页，课件共159页，创作于2023年2月第21页，课件共159页，创作于2023年2月第22页，课件共159页，创作于2023年2月第23页，课件共159页，创作于2023年2月第24页，课件共159页，创作于2023年2月第25页，课件共159页，创作于2023年2月

原问题（或对偶问题）

对偶问题（或原问题）

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

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

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

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

（2）原始问题与对偶问题关系表第26页，课件共159页，创作于2023年2月第27页，课件共159页，创作于2023年2月对偶定理是揭示原始问题与对偶问题解之间重要关系的

定理1

对称性定理(证明略)对偶问题的对偶是原问题。第4节线性规划的对偶理论一系列定理。第28页，课件共159页，创作于2023年2月定理2弱对偶定理对于任意的可行解成立第29页，课件共159页，创作于2023年2月第30页，课件共159页，创作于2023年2月该结论对非对称形式的对偶问题同样成立。由该定理可以得到关于“界”的结果:极小化问题有下界——推论1

极大化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个下界。第31页，课件共159页，创作于2023年2月极大化问题有上界——推论2

极小化问题的任意一个可行解所对应的目标函数值是其对偶问题最优目标函数值的一个上界。第32页，课件共159页，创作于2023年2月推论3

若原问题与对偶问题都有可行解，则它们都有最优解。能达到最优（由连续函数的性质得到）证毕第33页，课件共159页，创作于2023年2月推论4若原问题(对偶问题)为无界解，则其对偶问题(原问题)无可行解。其逆不真。证明由弱对偶定理得:第34页，课件共159页，创作于2023年2月第35页，课件共159页，创作于2023年2月第36页，课件共159页，创作于2023年2月C=bCX≤Yb弱对偶定理已知结论最优解定义X=CX≤bY=特别取C≤Yb证明思路第37页，课件共159页，创作于2023年2月第38页，课件共159页，创作于2023年2月若原问题有最优，则对偶问题也有最优，且最优值相等，反之亦然。定理4强对偶定理第39页，课件共159页，创作于2023年2月第40页，课件共159页，创作于2023年2月推论对偶问题的最优解为原问题最优表中，相应的松弛变量的检验数的相反数。第41页，课件共159页，创作于2023年2月单纯形方法计算过程:第42页，课件共159页，创作于2023年2月第43页，课件共159页，创作于2023年2月第44页，课件共159页，创作于2023年2月第45页，课件共159页，创作于2023年2月第46页，课件共159页，创作于2023年2月略讲第47页，课件共159页，创作于2023年2月甲产品乙产品提供量设备128台时材料A4016kg材料B0412kg利润23单位元第48页，课件共159页，创作于2023年2月定理5互补松弛定理略讲第49页，课件共159页，创作于2023年2月第50页，课件共159页，创作于2023年2月第51页，课件共159页，创作于2023年2月第52页，课件共159页，创作于2023年2月第53页，课件共159页，创作于2023年2月为了保证检验数的非正性取第54页，课件共159页，创作于2023年2月第6节对偶单纯形法最小比值原则第55页，课件共159页，创作于2023年2月第56页，课件共159页，创作于2023年2月第57页，课件共159页，创作于2023年2月为了保证检验数的非正性取第58页，课件共159页，创作于2023年2月第59页，课件共159页，创作于2023年2月第60页，课件共159页，创作于2023年2月应知道此方法：第61页，课件共159页，创作于2023年2月第62页，课件共159页，创作于2023年2月第63页，课件共159页，创作于2023年2月回到（55张）前几张PPT总结对偶单纯性方法。第64页，课件共159页，创作于2023年2月第65页，课件共159页，创作于2023年2月第66页，课件共159页，创作于2023年2月作业P-73-1.12第67页，课件共159页，创作于2023年2月第68页，课件共159页，创作于2023年2月第69页，课件共159页，创作于2023年2月第70页，课件共159页，创作于2023年2月P-73-1.12第71页，课件共159页，创作于2023年2月第72页，课件共159页，创作于2023年2月5/7202第73页，课件共159页，创作于2023年2月第74页，课件共159页，创作于2023年2月第75页，课件共159页，创作于2023年2月第76页，课件共159页，创作于2023年2月第77页，课件共159页，创作于2023年2月实际上，此题为无界解。举例：第78页，课件共159页，创作于2023年2月举例：第79页，课件共159页，创作于2023年2月第80页，课件共159页，创作于2023年2月第81页，课件共159页，创作于2023年2月第82页，课件共159页，创作于2023年2月第83页，课件共159页，创作于2023年2月第84页，课件共159页，创作于2023年2月第85页，课件共159页，创作于2023年2月第86页，课件共159页，创作于2023年2月第87页，课件共159页，创作于2023年2月第88页，课件共159页，创作于2023年2月第89页，课件共159页，创作于2023年2月第90页，课件共159页，创作于2023年2月第91页，课件共159页，创作于2023年2月第92页，课件共159页，创作于2023年2月第93页，课件共159页，创作于2023年2月第94页，课件共159页，创作于2023年2月第95页，课件共159页，创作于2023年2月第96页，课件共159页，创作于2023年2月第97页，课件共159页，创作于2023年2月第98页，课件共159页，创作于2023年2月第7节灵敏度分析第99页，课件共159页，创作于2023年2月将模型写在黑板上第100页，课件共159页，创作于2023年2月第101页，课件共159页，创作于2023年2月第102页，课件共159页，创作于2023年2月第103页，课件共159页，创作于2023年2月第104页，课件共159页，创作于2023年2月第105页，课件共159页，创作于2023年2月第106页，课件共159页，创作于2023年2月第107页，课件共159页，创作于2023年2月第108页，课件共159页，创作于2023年2月第109页，课件共159页，创作于2023年2月第110页，课件共159页，创作于2023年2月第111页，课件共159页，创作于2023年2月第112页，课件共159页，创作于2023年2月第113页，课件共159页，创作于2023年2月第114页，课件共159页，创作于2023年2月第115页，课件共159页，创作于2023年2月第116页，课件共159页，创作于2023年2月第117页，课件共159页，创作于2023年2月第118页，课件共159页，创作于2023年2月第119页，课件共159页，创作于2023年2月第120页，课件共159页，创作于2023年2月第121页，课件共159页，创作于2023年2月第122页，课件共159页，创作于2023年2月第123页，课件共159页，创作于2023年2月第124页，课件共159页，创作于2023年2月第125页，课件共159页，创作于2023年2月第126页，课件共159页，创作于2023年2月第127页，课件共159页，创作于2023年2月第128页，课件共159页，创作于2023年2月第129页，课件共159页，创作于2023年2月第130页，课件共159页，创作于2023年2月第131页，课件共159页，创作于2023年2月第132页，课件共159页，创作于2023年2月第133页，课件共159页，创作于2023年2月第134页，课件共159页，创作于2023年2月第135页，课件共159页，创作于2023年2月第136页，课件共159页，创作于2023年2月第137页，课件共159页，创作于2023年2月第138页，课件共159页，创作于2023年2月第139页，课件共159页，创作于2023年2月第140页，课件共159页，创作于2023年2月第141页，课件共159页，创作于2023年2月二、思考练习考察线性规划问题(1)：一、讨论总结对偶定理的应用。第142页，课件共159页，创作于