软件对偶理论课件

例1有两个煤厂A、B，每月分别进煤不少于60吨、100吨，它们担负供应三个居民区用煤任务，这三个居民区每月需用煤分别为45吨、75吨和40吨，A厂离这三个居民区分别是10公里、5公里、6公里，B厂离这三居民区分别为4公里、8公里、15公里。问这两煤厂如何分配供煤，才使运量最小？

1软件对偶理论课件2软件对偶理论课件3Matlab:c=[10564815];A=[-1-1-1000;000-1-1-1];b=[-60;-100];Aeq=[100100;010010;001001];beq=[45;75;40];lb=zeros(6,1);[x,fval]=linprog(c,A,b,Aeq,beq,lb)Matlab:c=[10564815];4原料种类含化学成份的百分比价格(美元/加仑)购买上限(加仑)ABC10.900.070.030.70400020.700.200.100.50600030.100.700.200.65500040.600.300.100.855000例2：一家石油公司的炼油厂提供两种无铅汽油燃料：无铅高级汽油和无铅普通汽油。炼油厂购买四种不同的石油原料，每种石油原料的化学成份分析、价格及购买上限见下表：无铅高级汽油的售价是每加仑1.00美元，它应至少含有60%的A成份，20%的B成份，而不能超过10%的C成份。无铅普通汽油的售价是每加仑0.90美元，它应至少50%的A成份，15%的B成份，而不能超过15%的C成份。公司预测：无铅高级汽油的销售量为6000加仑，无铅普通汽油的销售量为9000加仑。试确定每种汽油中各种原料的用量，使得公司获得最大的利润。原料含化学成份的百分比价格购买上限ABC10.900.0705软件对偶理论课件6model:max=6000*1+9000*0.9-(0.7*x1+0.5*x2+0.65*x3+0.85*x4+0.7*y1+0.5*y2+0.65*y3+0.85*y4);0.9*x1+0.7*x2+0.1*x3+0.6*x4>=0.6*6000;0.07*x1+0.2*x2+0.7*x3+0.3*x4>=0.2*6000;0.03*x1+0.1*x2+0.2*x3+0.1*x4<=0.1*6000;0.07*y1+0.2*y2+0.7*y3+0.3*y4>=0.15*9000;0.9*y1+0.7*y2+0.1*y3+0.6*y4>=0.5*9000;0.03*y1+0.1*y2+0.2*y3+0.1*y4<=0.15*9000;x1+y1<=4000;x2+y2<=6000;x3+y3<=5000;x4+y4<=5000;EndLingo:model:0.07*y1+0.2*y2+0.7*y3+0.73.4对偶理论3.4对偶理论8换个角度审视生产计划问题如何安排生产计划，使得获利最多？某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120换个角度审视生产计划问题如何安排生产计划，使得获利最多？某厂9

现从另一个角度提出问题。假定另有个工厂想利用该工厂的资源来生产产品。就要事先考虑至少付出多大代价才能使该工厂放弃生产自己的产品A、B，将现有的资源转而接受外来加工？产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120y1为每个劳动力的工时价格，y2为使用每台机器的价格，y3为消耗每单位原材料的价格。s.t.现从另一个角度提出问题。假定另有个工厂想利用该工厂的10

它的对偶问题就是一个价格系统，使在平衡了劳动力、设备和原材料的直接成本后，所确定的价格系统最具有竞争力（总价格最低）：（用于生产第i种产品的资源转让收益不小于生产该种产品时获得的利润）

对偶变量的经济意义可以解释为对资源的单位定价；s.t.它的对偶问题就是一个价格系统，使在平衡了劳动11s.t.（P）（D）cbbcAATmaxmins.t.（P）（D）c12二、原问题和对偶问题的关系1、对称形式的对偶关系（1）定义：若原问题是

（L）（D）则定义其对偶问题为价值系数右端项右端项价值系数约束矩阵约束矩阵的转置maxmin二、原问题和对偶问题的关系（1）定义：若原问题是（L）（D13例：找出下面LP的对偶问题:

（D）（P）例：找出下面LP的对偶问题:（D）（P）14

原问题（或对偶问题）

对偶问题（或原问题）

目标函数max目标函数min约束条件数：m个第i个约束条件类型为“≤”第i个约束条件类型为“≥”第i个约束条件类型为“=”对偶变量数：m个第i个变量≥0第i个变量≤0第i个变量是自由变量

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

约束条件数：n第i个约束条件类型为“≥”第i个约束条件类型为“≤”第i个约束条件类型为“=”约束中的右端项目标函数中的价值系数目标函数中的价值系数约束中的右端项相同相反原问题（或对偶问题）对偶问题（或原问题）目标函数15例写出下列线性规划的对偶规划约束条件数：n第i个约束条件类型为“≥”第i个约束条件类型为“≤”第i个约束条件类型为“=”决策变量数：n个第i个变量≥0第i个变量≤0第i个变量是自由变量

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

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

目标函数max

对偶问题（或原问题）

原问题（或对偶问题）

约束中的右端项目标函数中的价值系数目标函数中的价值系数约束中的右端项s.t.（原问题是极小化问题，因此应从原始对偶表的右边往左边查！）例写出下列线性规划的对偶规划约束条件数：n决策变量数：16

原问题

对偶问题原-对偶问题关系原问题17对偶定理对偶定理是揭示原始问题的解与对偶问题的解之间重要关系的

一系列定理。对偶定理18定理1.

弱对偶定理——若一对对称形式的对偶线性规划（L）

（D）

均有可行解，分别为和，则恒有证明思路：由（L）

由（D）

左乘左乘定理1.弱对偶定理——若一对对称形式的对偶线性规划（L）19该结论对任意形式的对偶问题同样成立。（证明:先转化为对称形式下的对偶问题，然后利用上面的定理）

由该定理可以得到什么附带结果？

•

关于“界”的结果；

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

min问题的任意一个可行解所对应的目标函数值是其对偶问题max最优目标函数值的一个上界。该结论对任意形式的对偶问题同样成立。（证明:先转化为对称形式20Lemma1.如果原问题无界，则对偶问题不可行。Lemma2.如果对偶问题无界，则原问题不可行。Lemma1.如果原问题无界，则对偶问题不可行。21推论1.

最优性准则定理

若、分别为对称形式对偶线性规划的可行解，且则，分别为原始问题和对偶问题的最优解。结论最优解定义特别取证明思路弱对偶定理已知推论1.最优性准则定理若、分别为对称形式22定理2.

强对偶定理若原始问题和对偶问题两者均可行，则两者均有最优解，且此时目标函数值相等。定理2.强对偶定理若原始问题和对偶问题两者均可行，则23对偶问题的解利用原问题的最优单纯形表求解对偶问题的最优解。如何求y*？Lemma3

对于对称形式的原问题（min）,若有最优解，则在其最优单纯形表中，剩余变量的检验数的负值即为对偶问题（max）的一个最优解。对偶问题的解利用原问题的最优单纯形表求解对偶问题的最优解。如24•原问题与对偶问题的关系；对偶原始有最优解问题无界无可行解有最优解

问题无界

无可行解

综上所述，一对对偶问题的关系，只能有下面三种情况之一出现：①.都有最优解，分别设为x*

和y*，则必有cTx*=bTy*；②.一个问题无界，则另一个问题无可行解；③.两个都无可行解。•原问题与对偶问题的关系；对偶有最优解问题25

一般而言，我们把某一可行点（如X*和Y*

）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。原问题对偶问题原问题和它的对偶问题之间存在着一种松紧关系：一个问题中某个约束是“紧”的，另一个问题中对应的约束就是“松”的。最终的平衡表达式，就是x和y分别是原始和对偶最优解的充要条件，即互补松紧性条件。一般而言，我们把某一可行点（如X*和Y*）处的严26定理3（互补松弛定理）：原问题及其对偶问题的可行解和是最优解的充要条件是证明思路定义

，是最优解定理3（互补松弛定理）：原问题及其对偶问题的可行解和27推论：设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束(严格不等式约束)，则它的对偶约束一定是其对偶问题最优解的紧约束(严格等式约束)。推论：28例5、已知试通过求对偶问题的最优解来求解原问题的最优解。解：对偶问题为例5、已知试通过求对偶问题的最优解来求解原问题的最优解。解：29用图解法求出：y*=（1,3），w=11。将y*1=1，y*2=3代入对偶约束条件，（1）（2）（5）式为紧约束(=)，（3）（4）为松约束。令原问题的最优解为x*=（x1.x2.x3.x4.x5），则根据互补松弛条件，必有x3=x4=0.(1.3)（1）（2）（3）（4）（5）用图解法求出：y*=（1,3），w=11。(1.30

又由于y*1＞0，