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

1、徐晓鸣Guangdong Ocean University Engineering CollegeE-mail:第第6 6章静态线性系统最优化模型及求解方法章静态线性系统最优化模型及求解方法Optimization Model6.6对偶规划及影子价格应用线性规划处理问题经常出现以下情况：所建模型变量不多，但约束却很多。求解这类问题时，由于引入松弛变量和人工变量，导致矩阵A的规模急骤增大。如两个变量，10个约束的线性规划 模型，如果都是大于等于约束，则引入松弛变量和人工变量20个，是矩阵A的阶次由102增大为1022，使计算工作量增大。在处理问题时，经常需从不同角度来研究。如某建材厂生产两种产品

2、，其单位消耗量及单位利润见表，现欲安排生产计划。甲产品乙产品拥有量原料A22.51000原料B0.51600单位利润2505000,6005 . 010005 . 22. .500250max21212121xxxxxxtsxxZ如果从另一个角度研究，现将原料出售，又不低于产品生产所获得的利润，两种原料出售的最低利润（在成本的基础上的加价）应为多少合算？0,5005 . 22505 . 02. .6001000min2121212121yyyyyytsyySyy为两种原料的最低利润、设：甲产品乙产品拥有量原料A22.51000原料B0.51600单位利润250500在研究问题中，经常需要分析某

3、种资源的增加或减少对目标值的影响程度。有些资源的增减并不影响目标值，这类资源是长线资源，某些资源的增减对目标值影响很大，这种资源是较稀缺的资源，称为短线资源。为了确定资源的长短程度，需要一种评价方法。6.6.1线性规划的对偶理论0,6005 . 010005 . 22. .500250max21212121xxxxxxtsxxZ0,5005 . 22505 . 02. .6001000min21212121yyyyyytsyyS目标要求变量数与约束数C与b系数矩阵原问题与对偶问题的对应关系原问题（对偶问题）对偶问题（原问题）目标函数minZ目标函数maxZ约束条件约束条件数为m变量对偶变量数为

4、m个约束条件为对偶变量为yj0约束条件为对偶变量yj0约束条件为=对偶变量yj为自由变量变量变量数为n个约束条件约束条件为n个变量xi为自由变量约束条件为=变量xi0约束条件为变量xi0约束条件为约束的系数矩阵为A约束的系数矩阵为AT约束常数项为b约束常数项为C指标因素为C指标因素为b求下述线性规划原问题的对偶问题 无约束432134322431143214321, 0, 0362422153532minxxxxyxxxyxxxyxxxxxxxxz无约束3213213213121321001523322645y,y,yyyyyyyyyyyyyyzmax0maxXbAXCXZ约束条件：目标函数：

5、区分基变量XB非基变量等式右端RHSXNXS系数矩阵检验数0IBB1NB1NBCCBN11B1BCBbB1bBCB1矩阵形式描述与单纯形表011ABCCABCCBNBN基变量的系数均为零是非基变量的系数，CYAAYC001ABCCB01BCYB令zbBCbYbBCYBB11两边同时乘以只能存在最小值无限大）（表示bYYBCYB010minYCYAbYw0maxXbAXCXZ原问题 对偶理论一对对偶问题，是一个问题的两个侧面，其目标是一致的，若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等；若原问题解无界，对偶问题无可行解。原问题的检验数 ，对应于对偶问题的一组基解，基矩阵B为最优基，

6、则最优基下的检验数对应于对偶问题的最优解。对偶问题的最优解是原问题的最优基下的检验数。在线性规划最优解中，若对应的某一约束条件的对偶变量值非零，则该约束条件取严格等式，如果约束条件取严格不等式，则对应的对偶变量一定为零。ABCCB1已知线性规划问题求其原问题的最优解。解为已知其对偶问题的最优5,53,540,43243232532min*2*154321543215432154321zyyxxxxxxxxxxxxxxxxxxxxwmax z=4y1+3y2y1+2y22 y1-y23 2y1+3y25 y1+y22 3y1+y23 y1，y20原问题和对偶问题最优解之间的关系原问题判断数行0对

7、偶问题BX1SYNXNBNABCC12SYSX1BCBY原问题单纯形表的检验数行对应其对偶问题的一个基解。设原问题0maxXbAXCXZ0,max;SNBSNBNNBBXXXbIXNXBXXCXCZNBAB原问题可以改写为：于是，是原问题的一个可行基设0,min2121SSNSBSYYYCYYNCYYBYbw对偶问题问题可表示为0minYCYAbYw求得原问题的一个基解)(0122111111NBCCYCYYNYCYYBBCYBCNBCCbBXBNSNSSBSBBBNB得出代入得出代入令。与其相应的检验数为6.6.2影子价格由单纯形法知，目标函数值 ，当b增加一个单位时，Z增加 ， 称为单纯形

8、乘子。它体现了资源增加一个单位时，目标函数的增长量，起到了资源参考价格的作用，因此又称为影子价格。又称为机会成本、会计价格、隐含价格、最优计划价格、完全竞争条件下的市场价格以及最优分工协作方案的实现价格等。是经济管理中相当重要的参数之一。bBCB11BCB1BCB由判断准则 知，在最优基时只有非基变量所对应的判断数才大于零，基变量的判断数均为零。因此对原问题来说，松弛变量不为零，则它一定是基变量，且在基矩阵中，因基变量的判断数为零，故根据对偶原理，它的影子价格为零，这种资源增长不会使目标值增加，故它是长线资源。如果松弛变量为非基变量，其值为零，且判断数大于零，这说明系统取最优解时，该资源已用尽

9、，其数量的增加可使目标函数值增加，它的影子价格就是它所对应的判断数。01ABCCB6.6.3对偶单纯形法对偶单纯形法的计算步骤；（1）将模型标准化0minXbAXCXZ（2）求初始基解（判断数均大于零的基解，可不是基可行解）。）进行旋转变换，转（。列，得旋转中心）选（）；（则问题解无解，否则转）如果所有（行。）选（）。束，否则转（则得最优解，计算就结如果370min66, 050min44, 0)3(rsrjrjjSrjiiriaaaccabbbb例子：0,43232432min321321321321xxxxxxxxxxxxw0,43232432min5432153214321321xxxx

10、xxxxxxxxxxxxw0,43232432min5432153214321321xxxxxxxxxxxxxxxxw234000-3-1-2-1100-4-21-30123400jcBCBXb1x4x3x2x5xjjzc 4x5x出基。行）选（2,0min4rbbbiir12234,22min0mincaaccjjjS进基234000-10-5/21/21-1/2221-1/23/20-1/204101jcBCBXb1x4x3x2x5xjjzc 4x1x2340002/501-1/5-2/51/5211/5107/5-1/5-2/5009/58/51/5jcBCBXb1x4x3x2x5xjj

11、zc 2x1x)5/1 , 5/8()0 , 0 , 0 , 5/2 , 5/11(YXb对偶问题的最优解为：，故问题的最优解为列非负，检验数全为正回顾运输问题平衡型运输问题设有m个供应地，n个需求地，现需求编制产品调运计划，使产品运输费用最省。 需求地供应地12.n拥有量1c11c12.c1na12c21c22.c2na2.mcm1cm2.cmnam需求量b1b2bniiba的运费。个需求地供应单位产品个生产地向第为第个需求地的需求量；为第个生产地的生产量；为第量；个需求地运输的产品数个生产地向第为第jicjbiajixijjiij 0,2, 1,2, 1.min1111ijnjiijmijijminjijijxmiaxnjbxtsxcz这就是运输问题的数学模型。它包含mn个变量，(m+n)个约束方程。其系数矩阵的结构比较松散，且特殊。 行行nmvvvuuuxxxxxxxxxnmmnmmnn1111111111111111112121212222111211位势法检验设u1，u2，um；v1，v2，vn是对应运输问题的m+n个约束条件的对偶变量。B是含有一个人工变量xa的(m+n)(m+n)初始基矩阵。人工变量xa在目标函数中的系数ca=0，从线性规划的对偶理论可