求解线性不等式组问题的几种方法

求解线性不等式组问题的几种方法 3 求解线性不等式组问题的几种方法 雍龙泉 () 陕西理工学院 数学系 , 陕西 汉中 723001 摘 要 :本文研究了求解线性不等式组的几种实用算法 ,首先把线性不等式组问题转化为线 性规划和凸二次规划 ,通过求解线性规划和凸二次规划得到线性不等式组的一个解 , 紧接着给出 了直接求解线性不等式组的旋转算法 ;实例说明这些方法是可行的 . 关键词 :线性不等式组 ; 线性规划 ; 凸二次规划 ; 旋转算法 中图分类号 :O151 . 25 文献标识码 : A 例 1 求解不等式组线性不等式组问题是运筹学与最优化的一 个重要研究方向. 本文研究线性不等式组问题的 - x1 x2 ?5 , 标准形为 A x ?b ,其中 A 是 m ×n 维实矩阵 , x ? 2 x ?- 3 . 2x1 - - n m R, b ?R. 关于该问题研究的重点是找到满足问 解 化不等式组为线性规划 题的一个可行解 ,或者证明该问题解不存在. 该问 mi n y1+ y2 题又是数学 、物理 、计算机科学以及管理科学等诸 - = 5 , s. t. xx+ y1 2 1 多领域所面临的一个常见基本问题 , 它有利于解 - x- 2 x+ y= - 3 , 1 2 2 [ 1 ] 决大规模稀疏的能源规划问题; 解决由其所描 y, y?0 .1 2 [ 2 ] 述的选课模型; 还可以通过求解线性不等式组 [ 7 ] [ 8 ] 用数学软件 L INDO 或者 M A TL AB 求 [ 3 ] 来给出线性规划的一个解等. 因此 ,这几年有越 得该线性规划问题的最优解为 x= - 3 , x= 5 ,1 2 来越多的学者来研究线性不等式组问题的求解 , y1 = 0 , y2 = 0 ;由于 y1 = y2 = 0 ,因此原线性不 [ 4 - 6 ] 并取得一些成果. 本文主要分析线性不等式 Τ ) ( 等式组的一个可行解为 x = - 3 , 5. 组为线性规划和凸二次规划以及直接求解线性不 2 . 化线性不等式组为二次规划等式组的旋转算法这三种方法 , 并给出相应的例 () 对于线性不等式 1 . 1,在它的可行域 F 上构 题进行说明 . 造如下凸二次规划问题 1 . 化线性不等式组为线性规划Τ y y mi n 对于线性不等式组 ()2 . 1 s. t. A x + y = b , y ?0 ()? b1 . 1 A x n 通过求解该凸二次规划问题就可以得到不等 () 假设问题 1 . 1的可行域 F = { x ? R| A x 式组的一个可行解. ? b} 非空. 构造如下的线性规划问题 例 2 求解不等式组 mi n y ()1 . 2 x1 + 2 x2 ?6 , A x + y = b , y ?0s. t. 2 x+ x?8 .1 2 通过求解线性规划就可以得到原不等式组问 解化不等式组为二次规划 题的一个可行解. 3 收稿日期 :2007 - 09 - 16 () 作者简介 :雍龙泉 1980 - ,男 ,陕西洋县人 ,硕士 ,讲师 ,从事数学教学与最优化算法研究 . 33 ()第 21 卷第 5 期Vol . 21 No . 5 自然科学版 高等函授学报 ( )J o ur nal of Higher Co r re spo ndence Educatio n Nat ural Scie nce s 2007 年 10 月 Octo ber 2007 22 + y ( )mi n y如果 I1 2 3 ? = Ø,转步骤 3 ; 否则对于某个 r ζ? I3 ,当 ar 的偏差r 是负数 ,正数或 0 时 ,分别转 x+ 2 x+ y= 6 , s. t. 1 2 1 ( ) ( ) ( ) ?, ?, ?;2 x+ x+ y= 8 , 1 2 2 ( ) ?若同 行 没 有 与 基 不 等 式 对 应 的 正 元 y, y?0 .1 2 [ 7 ] [ 8 ] 素 ,则不等式组无解 , 否则 以其 中一 个 正元 素为 用数学软件 L INDO或者 MA TL AB求 I: I\ { r} , = 枢 轴 进 行 一 次 旋 转 运 算 , 令3 3 得该二 次 规 划 问 题 的 K - T 点 为 x= 10/ 3 ,1 ( ) 转 ?;x= 4/ 3 , y= 0 , y = 0 ; 又利用凸规划的局部2 1 2 ( ) ?若同 行 没 有 与 基 不 等 式 对 应 的 负 元 , 就 得 到 原 线 性极小值必是 全 局 极 小 值 的 原 理 Τ 素 ,则不等式组无解 , 否则 以其 中一 个 负元 素为( ) 10/ 3 , 4/ 3.不等式组的一个可行解为 x= I: I\ { r} , = 枢 轴 进 行 一 次 旋 转 运 算 , 令3 3 3 . 旋转算法( ) 转 ?;3 . 1 算法描述 考虑( ) ?若同 行 与 基 不 等 式 对 应 的 元 素 均 为 不等式组 零 ,则 axb是不等式组的一个冗余等式 , 令= r r b, i = 1 , 2 , ax = i , l ; i ( ) I: = I\ { r} ,转 ?,否则以其中一个非零元素 3 3 ax ? b, i =l + 1 , l + 2 , i i , m . : = I \ { r} , 为枢 轴 进 行 一 次 旋 转 运 算 , 令 I3 3 其中 , x 是 n 维 未 知 列 向 量 , ai 是 n 维 行 向 ( ) 转 ?.. 旋转算法用到以下, m量 , bi 是标量 , i = 1 , 2 , 步骤 3主迭代 . 进行非基不等式与基不等 基本概念 : a, a,, a中一 个最 大 线性 无 关 组1 2 m 式的交换 . 称为不等式组的基 , 基中 的 向量 称为 基 向量 , 其 ) ( ?若所有非 基 向 量 偏 差 非 负 , 则 当 前 基 ( ) 余向量称为非 基 向 量 . 基 向 量 对 应 的 不 等 式 本解是不等式组的解 ,停止运算 . ( ) ( ) 称为基 不等式 ,否则称为非基 不等式 . 由基 否则 , 等式和基不等式构成的 不等 式组 称 为基 本不 等 ( ) ?以其 中 一 个 偏 差 为 负 的 非 基 向 量 入 式组 ,其解 集 是 个 锥 , 称 为 基 锥 . 基 本 不 等 式 组基 . 如果同行没有与基不等 式 对应 的正 元素 , 则 对应的方程组的解即基 锥顶 点 , 称为 基 本解 . 算 不等式组无 解 , 否 则 以 其 中 一 个 正 元 素 为 枢 轴 法如下 : ( ) 进行一次旋转运算 ,转 ?. 1步骤 构 造 初 始 表 . 如 果 不 等 式 组 含 有 从以上算法的步骤 2 和步骤 3 可以看出 ,我 ( ) 形 如 x i ?li 的不等式 li 是有限实数,则以 x i ? 们总是用非基等式或非 基 不等 式与 基 不等 式进 l为初始基本不等式 ,否则以 x ?- M 为初始基i i 行交换 ,非基等式一旦成为 基本 的 就不 再出 基 . 本不等式 , i = 1 , 2 ,, n ,其中 M 是一个充分大 这是因为 ,如果一个不等式 组 有解 , 其 每个 解必 的数 ,x ?- M 称为人工不等式 . 它们的系数向 i 须满足所有等式 . 为了使基 等 式不 出基 , 只 需不 ( ) 量 初始基向量是 n 阶单位矩阵的 n 行 . 其余等 在基等式所在列寻找枢 轴 元素 . 因 此 , 非基 等式 式和不等式 的 系 数 向 量 都 是 非 基 向 量 . 初 始 基 一旦成为基本的 ,其所在列 就 可以 删掉 . 设 基本Τ 本解为 x l或 -M , i = 1 , 2 , , n. 将它们代i i = , ?x ,其获取方法为 : 如果 x n i解 x = x 1 , x 2 ,??? 入每个非基 等 式 和 不 等 式 , 两 边 相 减 即 得 各 非 l或 - M 是基不等式 ,则 x = l或 - M ; 如果 ? ?i i i ζ 它是非基 不 等 式 , 则 x i 等 于 其 偏 差 加 上 li 或?基向量的偏差,从而列出初始表 .i - M . 如果不等式组没有形如 x ?l的不等式 ,但 i i 3 . 2 算例分析( ) 是有形如 x ? u的不等式 u是有限实数, 也i i i [ 9 ] 例 3 求解不等式组 可 以以 - x i ?- ui 为初始基本不等式 ,无需添加 - 2 x= 1 , 1+ x3 人工变量 ,此时 -ei 是初始基向量 . + x+ 2 x ?3 ,2 3- 4 x 1 步骤 2预处理 . 尽可能把所有非基等式换 3 x+ 2 x+ x?12 ,1 2 3 成基等式 . 用 I, I, I, I分别表示基等式 、基不0 1 2 3 x?0 , x?2 . 1 2 等式 、非基不等式 、非基等式的编号集 . 34 ()第 21 卷第 5 期Vol . 21 No . 5 自然科学版 高等函授学报 ( )J o ur nal of Higher Co r re spo ndence Educatio n Nat ural Scie nce s 2007 年 10 月 Octo ber 2007 解) ( ) 令 a( 2 , 0 , 1, a= - 4 , 1 , 2, 1 = - 2 参 考 文 献 ( ) ( ) ( ) = 0 , 1 , 0. 引a3 = 3 , 2 , 1, e1= 1 , 0 , 0, e2 [ 1 ] WA YN E L , W IN S TON . Operatio ns Re sea rch [ M ] . ( ) 入人工不等式 x3?- M ,并令 e3 = 0 , 0 , 1. 以 北京 :清华大学出版社 ,2003 . x?0 , x?2 , x?- M 为初始基本不等式组 ,1 2 3[ 2 ] 王若鹏 . 基于线性不等式组的选课模型 [J ] . 北京石油 ( )Τ 0 ( ) 初始基本解为 x = 0 , 2 , - M,初始基向量() 化工学院学报 ,2003 ,11 4:31 - 32 . 为 e, e, e, 非基向量为 a, a, a, 它们的偏差分1 2 3 1 2 3 [ 3 ] 卢开澄 . 单目标 、多目标与整数规划 [ M ] . 北京 : 清华 8 , 初始表见表别为 - M - 1 , - 2 M - 1 , - M - 大学出版社 ,1999 . 1 ; 经过两次旋转后见表 2 . [ 4 ] 顾阿伦 , 孙永广 , 吴宗鑫 . 求解线性不等式组 的方法 表 1 初始表 () [J ] . 运筹与管理 ,2002 ,11 4:26 - 27 . eee1 2 3 [ 5 ] 顾阿伦 , 孙永广 , 吴宗鑫等 . 求解线性不等式 组的一 3 a- 2 - M - 1 0 1 1() 类无约束极值方法 [J ] . 清华大学学报 ,2002 ,42 12: a2 - 4 1 2 - 2 M - 1 1572 - 1574 . 3 2 1 - M - 8 a3 [ 6 ] 张忠桢 ,唐小我 . 线性不等式组的一种新算法 [J ] . 电 表 2 第二次旋转后的结果 () 子科技大学学报 ,2002 ,31 6:642 - 645 . [ 7 ] 谢金 星 . 优 化 建 模 与 L INDO/ L IN GO 软 件 [ M ] . 北 ea1 3 e2 M + 1 0 3 京 :清华大学出版社 ,2005 . a- 5/ 2 1/ 2 9/ 2 2 [ 8 ] 王沫然 . MA TL AB 5 . X 与科学计算 [ M ] . 北京 : 清华 e- 5/ 2 1/ 2 7/ 2 2 大学出版社 , 2000 . [ 9 ] 张忠桢 . 凸规划 ———投资组合与网络优化的旋转算 至此 ,所有非基向量偏差非负 ,当前基本解 法 [ M ] . 武汉 :武汉大学出版社 ,2004 . 是不等式组的一个解 . 由表可见 , 此基本解为 x1 [ 10 ] 方述诚 , S. 普森普拉 . 线性优化及扩展理论与算法= 0 , x= 11/ 2 , x = 1 . 2 3 [ M ] . 北京 :科学出版社 , 1994 .文中给 出 的 三 种 解 不 等 式 组 问 题 的 方 法 , 读者要多应用才能体会其实用性及重要性 . ()上接第 27 页 内变化即可达到目的. ( ) ( )3 x + 2x - 2 此例的证明使我们看到了证明函数极限的思 | 3 x + 2 | | x - 2 | ?= ( )3 x + 1 3 | x + 1 | 想方法与数列的情况类似 , 经常用到“预先限定” ( ) 3 ?3 + 2| x - 2 | 11 及“适当放大”的技巧. = |ε x - x - 2 | < Ζ | ( )6 3 1 + 1 综观上述各例 ,运用极限的定义证明极限的要 ε ε66 1δ ,ε 2 | < ,所以取= mi n. 于是 , Π> 0 , ε( ) 点在于求使不等式 | a- a | < 或 | f x- b | ε 6 δ1,δ , Π x , < , ϖ= mi n - 2 | 有 | x )ε )ε ((11 f 或 | x - a | < f 来体现的. 这里关键是求得 2 2 δ限定自变量变化范围的 N 或, 其具体求法和常 x 4 4 x -ε< . 即li m= . x + 1 x ?2 3 3 x + 1 用技巧希望读者认真加以体会 ,适当地做些练习.说明这里与上面例 1 不同之处在于 :为了 |3 x + 2 | | x - 2 | 参 考 文 献 ε要得到使 < 成立的形如 | x 3 | x + 1 | ( ) [ 1 ] 巫锡禾 . 高等数学 第一 版[ M ] . 上 海 : 上海 科学技 3 x + 2 | | x - 2 | |术出版社 ,1988 . ε) (- 2 | < f 的不等式 , 应在 3 | x + 1 | [ 2 ] 王仲春等 . 极限的基本理论与方法 [ M ] . 兰州 :甘肃人 中消去除 | x - 2 | 外的一切变量 ,为此限定了 x 的 民出版社 ,1982 . 变化范围 ,由于 x ?2 ,可令 x 在范围 | x - 2 | < 1 35