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

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

位势法检验设u1，u2，…，um；v1，v2，…，vn是对应运输问题的m+n个约束条件的对偶变量。B是含有一个人工变量xa的(m+n)×(m+n)初始基矩阵。人工变量xa在目标函数中的系数ca=0，从线性规划的对偶理论可知。

而每个决策变量xij的系数向量Pij=ei+em+j，所以

C