第六章静态线性系统最优化模型及求解方法.pptVIP

位势法检验 设u1，u2，…，um；v1，v2，…，vn是对应运输问题的m+n个约束条件的对偶变量。B是含有一个人工变量xa的(m+n)×(m+n)初始基矩阵。人工变量xa在目标函数中的系数ca=0，从线性规划的对偶理论可知。 而每个决策变量xij的系数向量Pij=ei+em+j，所以 CBB-1Pij=ui+vj。于是检验数 由单纯形法得知所有基变量的检验数等于0。即 xa为人工变量（基变量），这时对应的检验数是： xa ca-u1=0 ∵ca=0 ∴u1=0 任意指定某一位势等于零。 徐晓鸣 Guangdong Ocean University Engineering College E-mail:gdouxxm@163.com Optimization Model 6.6对偶规划及影子价格 应用线性规划处理问题经常出现以下情况： 所建模型变量不多，但约束却很多。求解这类问题时，由于引入松弛变量和人工变量，导致矩阵A的规模急骤增大。 如两个变量，10个约束的线性规划 模型，如果都是大于等于约束，则引入松弛变量和人工变量20个，是矩阵A的阶次由10×2增大为10×22，使计算工作量增大。 在处理问题时，经常需从不同角度来研究。 如某建材厂生产两种产品，其单位消耗量及单位利润见表，现欲安排生产计划。 甲产品 乙产品 拥有量 原料A 2 2.5 1000 原料B 0.5 1 600 单位利润 250 500 如果从另一个角度研究，现将原料出售，又不低于产品生产所获得的利润，两种原料出售的最低利润（在成本的基础上的加价）应为多少合算？ 甲产品 乙产品 拥有量 原料A 2 2.5 1000 原料B 0.5 1 600 单位利润 250 500 在研究问题中，经常需要分析某种资源的增加或减少对目标值的影响程度。有些资源的增减并不影响目标值，这类资源是长线资源，某些资源的增减对目标值影响很大，这种资源是较稀缺的资源，称为短线资源。为了确定资源的长短程度，需要一种评价方法。 6.6.1线性规划的对偶理论 目标要求 变量数与约束数 C与b 系数矩阵 原问题与对偶问题的对应关系 原问题（对偶问题） 对偶问题（原问题） 目标函数minZ 目标函数maxZ 约 束 条 件 约束条件数为m 变量 对偶变量数为m个 约束条件为≥ 对偶变量为yj≥0 约束条件为≤ 对偶变量yj≤0 约束条件为= 对偶变量yj为自由变量 变 量 变量数为n个 约束条件 约束条件为n个 变量xi为自由变量 约束条件为= 变量xi≥0 约束条件为≤ 变量xi≤0 约束条件为≥ 约束的系数矩阵为A 约束的系数矩阵为AT 约束常数项为b 约束常数项为C 指标因素为C 指标因素为b 求下述线性规划原问题的对偶问题 区分 基变量XB 非基变量 等式右端RHS XN XS 系数矩阵 检验数 0 矩阵形式描述与单纯形表 原问题 对偶理论 一对对偶问题，是一个问题的两个侧面，其目标是一致的，若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等；若原问题解无界，对偶问题无可行解。 原问题的检验数 ，对应于对偶问题的一组基解，基矩阵B为最优基，则最优基下的检验数对应于对偶问题的最优解。 对偶问题的最优解是原问题的最优基下的检验数。 在线性规划最优解中，若对应的某一约束条件的对偶变量值非零，则该约束条件取严格等式，如果约束条件取严格不等式，则对应的对偶变量一定为零。 已知线性规划问题 max z=4y1+3y2 y1+2y2≤2 ① y1-y2≤3 ② 2y1+3y2≤5 ③ y1+y2≤2 ④ 3y1+y2≤3 ⑤ y1，y2≥0 原问题和对偶问题最优解之间的关系 原问题 判断数行 0 对偶问题 原问题单纯形表的检验数行对应其对偶问题的一个基解。 设原问题 对偶问题问题可表示为 求得原问题的一个基解 6.6.2影子价格 由单纯形法知，目标函数值 ，当b增加一个单位时，Z增加 ， 称为单纯形乘子。 它体现了资源增加一个单位时，目标函数的增长量，起到了资源参考价格的作用，因此又称为影子价格。又称为机会成本、会计价格、隐含价格、最优计划价格、完全竞争条件下的市场价格以及最优分工协作方案的实现价格等。是经济管理中相当重要的参数之一。 由判断准则 知，在最优基时只有非基变量所对应的判断数才大于零，基变量的判断数均为零。因此对原问题来说，松弛变量