线性规划的原始对偶法及其经济意义.docx

自然科学版N a tu ra l S ciences Ed itionVo l. 33 No. 4 2006第 33 卷 第 4 期 2006 年线性规划的原始对偶法及其经济意义3杨爱珍(上海财经大学 应用数学系 ,上海 200433)摘 要 :解线性规划问题除常见的单纯形法和对偶单纯形法外 ,还有一种原始对偶法 . 其基本思想是从对偶问题的一个可行解开始 ,制定一个受限制的原始问题并使它达到最优 . 工厂可用它来制定最优生产方 案 ,使生产成本最低 ;而公司可据此制订出最优售价 ,使利润最大 .关键词 :原始对偶法 ;经济意义 ;最优方案 .文章编号 : 1000 25846 ( 2006) 0420316 205中图分类号 : O29文献标识码 : A( y0 , y0 ,0, y ) , 我们定义集合 { 1, 2, , n }的一个解线性规划问题除常见的单纯形法和对偶单纯形法外 ,还有一种原始对偶法 . 这种方法的基本 思想是从对偶问题的一个可行解开始 ,制定一个受限制的原始问题并使它达到最优 . 如果得到的最优解满足原始问题的约束条件 ,则解题到此结 束 ;否则 ,那就要改进对偶问题的可行解并相应地 确定一个新的受 限制 的 原始 问题 再 使它 达到 最优 . 这样继续下去直到产生满足原始问题约束条 件的最优解为止. 下面先介绍这种方法 ,然后进行 案例分析 ,最后说明它的经济意义.1 2mmmy00子集 J. 如果 6a= cj , 则 j∈J ; 如果 6 cj ,aij yiij ii = 1i = 10则 j| J. 对应于这个可行解 Y 和子集 J , 我们定义受限制的原始问题如下 :mm in r = 6 rii = 16 a x + r = b , i = 1, 2,s. t., m( 3 )ij j i ij∈Jri ≥0, xj ≥0, j∈J.问题 ( 3 ) 的对偶问题是受限制的对偶问题 ,它是m1 原始对偶法的原理设有线性规划问题nm axu = 6 bi uii = 1m6 aij ui ≤0, j∈J( 4 )s. t.i = 1m inz = 6 cj xj原始对偶法是从受限制的原始问题 ( 3 )来求得线性规划问题 ( 1 ) 的解 . 它的理论根据是以下 两个定理.j = 1n6( 1 )s. t.xj ≥0,aij xj = bi , i = 1, 2,, mj = 1j = 1, 2,, n.000定理 1 如果 Y 是 ( 2 )的可行解 , X 和 R 是( 3 )的可行解 , 且使 ( 3 )的目标函数值 r = 0, 则 X0和 Y0 分别是 ( 1 )和 ( 2 )的最优解 .证明由于 r = 0, 所以 X0 和 R0 实际上就是它的对偶问题是mm axw = 6 bi yji = 1ms. t.6 aij yi ≤cj , j = 1, 2,, n, m.( 2 )i = 1yi 无限制 , i = 1, 2,0( 3 )的最优解 . 当然此时 X 也是 ( 1 )的最优解 . 由0Y子集的构造可知 , ( 3 ) 中的 x ≥0 对应于 ( 2 ) 中的如果已知 对 偶 问 题 ( 2 ) 的 一 个 可 行 解=j3 作者简介 :杨爱珍 ( 1963 2) ,女 ,江苏苏州人 ,上海财经大学副教授 ,从事应用数学研究.收稿日期 : 2006 204 211317第 4期杨爱珍 :线性规划的原始对偶法及其经济意义m确定受限制的原始问题 ( 3 ) , 再求解 ( 3 ) , 得到最优解 X0 和 R0 .此时有两种情况 :①如果 ( 3 ) 的最 小目 标 值 r = 0, 则 由定 理 1可知 , ( 3 )的最优解中的 X0 即为 ( 1 )的最优解.②如果 ( 3 )的最小目标值 r 0, 则 ( 3 )的最优 解中的 X0 不是 ( 1 )的可行解 , 于是要改进对偶问题 ( 2 )的可行解 . 由 ( 3 ) 的最优解表格可得到 ( 4 )m06aij yi = cj , 假定 X 中有k 个分量大于零 , 不妨记i = 1为 x0 , x0 ,0, x , 则1 2nkkkm000 06j = 1m k= 6= 6 ( 6aij yi ) xj=cj xjcj xjmj = 1j = 1 i = 1mm0 00 006 ( 6aij xj ) yi= 6( 6aij xj ) yi= 6 bi yj .i = 1 j = 1i = 1 j = 1i = 1上式表明原始问题 ( 1 ) 和它的对偶问题 ( 2 )的目标函数值相等 , 因此 ,