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

第六章静态线性系统最优化模型及求解方法第一页，共二十七页，2022年，8月28日6.6对偶规划及影子价格应用线性规划处理问题经常出现以下情况：所建模型变量不多，但约束却很多。求解这类问题时，由于引入松弛变量和人工变量，导致矩阵A的规模急骤增大。如两个变量，10个约束的线性规划模型，如果都是大于等于约束，则引入松弛变量和人工变量20个，是矩阵A的阶次由10×2增大为10×22，使计算工作量增大。第二页，共二十七页，2022年，8月28日在处理问题时，经常需从不同角度来研究。如某建材厂生产两种产品，其单位消耗量及单位利润见表，现欲安排生产计划。甲产品乙产品拥有量原料A22.51000原料B0.51600单位利润250500第三页，共二十七页，2022年，8月28日如果从另一个角度研究，现将原料出售，又不低于产品生产所获得的利润，两种原料出售的最低利润（在成本的基础上的加价）应为多少合算？甲产品乙产品拥有量原料A22.51000原料B0.51600单位利润250500第四页，共二十七页，2022年，8月28日在研究问题中，经常需要分析某种资源的增加或减少对目标值的影响程度。有些资源的增减并不影响目标值，这类资源是长线资源，某些资源的增减对目标值影响很大，这种资源是较稀缺的资源，称为短线资源。为了确定资源的长短程度，需要一种评价方法。第五页，共二十七页，2022年，8月28日线性规划的对偶理论目标要求变量数与约束数C与b系数矩阵第六页，共二十七页，2022年，8月28日原问题与对偶问题的对应关系原问题（对偶问题）对偶问题（原问题）目标函数minZ目标函数maxZ约束条件约束条件数为m变量对偶变量数为m个约束条件为≥对偶变量为yj≥0约束条件为≤对偶变量yj≤0约束条件为=对偶变量yj为自由变量变量变量数为n个约束条件约束条件为n个变量xi为自由变量约束条件为=变量xi≥0约束条件为≤变量xi≤0约束条件为≥约束的系数矩阵为A约束的系数矩阵为AT约束常数项为b约束常数项为C指标因素为C指标因素为b第七页，共二十七页，2022年，8月28日求下述线性规划原问题的对偶问题第八页，共二十七页，2022年，8月28日第九页，共二十七页，2022年，8月28日区分基变量XB非基变量等式右端RHSXNXS系数矩阵检验数0矩阵形式描述与单纯形表第十页，共二十七页，2022年，8月28日原问题第十一页，共二十七页，2022年，8月28日对偶理论一对对偶问题，是一个问题的两个侧面，其目标是一致的，若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等；若原问题解无界，对偶问题无可行解。原问题的检验数，对应于对偶问题的一组基解，基矩阵B为最优基，则最优基下的检验数对应于对偶问题的最优解。对偶问题的最优解是原问题的最优基下的检验数。在线性规划最优解中，若对应的某一约束条件的对偶变量值非零，则该约束条件取严格等式，如果约束条件取严格不等式，则对应的对偶变量一定为零。第十二页，共二十七页，2022年，8月28日已知线性规划问题第十三页，共二十七页，2022年，8月28日maxz=4y1+3y2y1+2y2≤2①y1-y2≤3②2y1+3y2≤5③y1+y2≤2④3y1+y2≤3⑤y1，y2≥0第十四页，共二十七页，2022年，8月28日原问题和对偶问题最优解之间的关系原问题判断数行0对偶问题原问题单纯形表的检验数行对应其对偶问题的一个基解。第十五页，共二十七页，2022年，8月28日设原问题对偶问题问题可表示为第十六页，共二十七页，2022年，8月28日求得原问题的一个基解第十七页，共二十七页，2022年，8月28日6.6.2影子价格由单纯形法知，目标函数值，当b增加一个单位时，Z增加，称为单纯形乘子。它体现了资源增加一个单位时，目标函数的增长量，起到了资源参考价格的作用，因此又称为影子价格。又称为机会成本、会计价格、隐含价格、最优计划价格、完全竞争条件下的市场价格以及最优分工协作方案的实现价格等。是经济管理中相当重要的参数之一。第十八页，共二十七页，2022年，8月28日由判断准则知，在最优基时只有非基变量所对应的判断数才大于零，基变量的判断数均为零。因此对原问题来说，松弛变量不为零，则它一定是基变量，且在基矩阵中，因基变量的判断数为零，故根据对偶原理，它的影子价格为零，这种资源增长不会使目标值增加，故它是长线资源。如果松弛变量为非基变量，其值为零，且判断数大于零，这说明系统取最优解时，该资源已用尽，其数量的增加可使目标函数值增加，它的影子价格就是它所对应的判断数。第十九页，共二十七页，2022年，8月28日6.6.3对偶单纯形法对偶单纯形法的计算步骤；（1）将模型标准化第二十页，共二十七页，2022年，8月28日（2）求初始基解（判断数均大于零的基解，可不是基可行解）第二十一页，共二十七页，2022年，8月28日例子：第二十二页，共二十七页，2022年，8月28日234000-3-1-2-1100-4[-2]1-30123400出基进基第二十三页，共二十七页，2022年，8月28日234000-10[-5/2]1/21-1/2221-1/23/20-1/2041012340002/501-1/5-2/51/5211/5107/5-1/5-2/5009/58/51/5第二十四页，共二十七页，2022年，8月28日回顾运输问题平衡型运输问题设有m个供应地，n个需求地，现需求编制产品调运计划，使产品运输费用最省。需求地供应地12….n拥有量1c11c12….c1na12c21c22…..c2na2….……………mcm1cm2….cmnam