（运筹学与控制论专业论文）求解线性丢番图方程组及不等式组的abs算法.pdf

大连理工大学硕士学位论文 摘要 1 9 8 4 年，a a b b y 、b r o y d e n 及s p e d i c a t o 共同研究开发了一类用于求解线性方程组与 非线性方程组的投影算法一a b s 算法。随后二十多年的发展，a b s 算法扩展到可以 求解最d , - - 乘问题、不等式组、线性规划和具有线性约束的非线性规划等问题。而线性 丢番图方程组及不等式组的求解是实际应用中经常遇到的一类问题，在物流、运输中起 着重要的作用，于是对线性丢番图方程组及不等式组的求解就显得尤为必要。本文在 a b s 的框架下，系统地研究了线性丢番图方程组及不等式组的解法。 本文的研究工作分为五个部分，首先介绍了a b s 算法的研究进展和a b s 软件的概 况，其次对线性丢番图方程组的解法做了系统的阐述，接着给出了求解线性丢番图不等 式组的求解算法，随后给出了求解超定线性丢番图方程组及不等式组的修正a b s 算法， 最后给出了用m a t l a b 编写的相关a b s 算法程序。所取得的成果如下： 1 第二章，我们系统地分析了当前求解线性丢番图方程组的方法：r o s s e r 算法和 f o r t c r b a c h e r 算法，求解线性丢番图方程组的方法：e m a s 算法和c o n t e j e a n 算法。 2 第三章，详细分析了求解线性丢番图方程组的整隐式l u 算法和整隐式l x 算法， 并给出一算例说明了隐式l u 与隐式l x 算法在整数域与实数域内的一个差别。 3 第四章给出了求解线性丢番图不等式组的a b s 算法及其在整线性规划中的应用。 4 第五章给出了求解超定线性丢番图方程组和不等式组的修正a b s 算法。 5 附录中给出了用m a t l a b 编写的相关a b s 算法程序。 关键词：a b $ 算法；线性丢番图方程组；隐式l u 算法：线性整不等式组 超定线性丢番图方程组；超定线性不等式组；m t l a b 程序 求解线性丢番图方程组及不等式组的a b s 算法 a b s a l g o r i t h m sf o rs o l v i n g l i n e a rd i o p h a n t i n ee q u a t i o n sa n di n e q u a t i o n s a b s t r a c t i n1 9 8 4 ，a b a f f y , b r o y e d na n ds p e d i c a t od e v e l o p e dak i n do fp r o j e c t i o na l g o r i t h m sf o r l i n e a ra n dn o n l i n e a re q u a t i o n s - - - a b sa l g o r i t h m s t h r o u g h o u tt h ef o l l o w i n gt w e n t yy e a r s ， a b s a l g o r i t h m sh a v e b e e ne x t e n d e dt os o l v et h el e a s ts q u a r e s ，t h ei n e q u a l i t ys y s t e m s ，l i n e a r p r o g r a m 血n ga n dn o n l i n e a rp r o g r a m m i n gw i t hl i n e a rc o n s t z a i n t s ，c t c l i n e a rd i o p h a n t i n e e q u a t i o n sa n di n e q u a t i o n sa p p e a ro f t e ni nm o d e l i n ga n dp r a c t i c a la p p l i c a t i o n , w h i c hp l a ya n i m p o r t a n tr o l ei nt h et r a n s p o r t a t i o n s oi ti sp a r t i c u l a r l yn e c e s s a r yt of i n do u tt h es o l u t i o no f l i n e a rd i o p h a n t i n ee q u a t i o n sa n di n e q u a t i o n s t h i sp a p e ri sd e v o t e dt os t u d y i n gt h el i n e a r d i o p h a n t i n ee q u a t i o n sa n di n e q u a t i o n su n d e rt h ea b s e n v i r o n m e n t i nt h i st h e s i s f i v ep a r t sa c o n s i d e r e d f i r s t l y , t h ed e v e l o p m e n to fa b sa l g o r i t h m sa n d t h ea b ss o f t w a r ea r eo u t l i n e d ；s e c o n d l y , t h ea p p r o a c h e sf o rl i n e a rd i o p h a n t i n ee q u a t i o n sf i r e i l l u m i n a t e c li nd e t a i l ；t h i r d l y , a b sa l g o r i t h m sf o rs o l v i n gl i n e a rd i o p h a n t i n ei n e q u a t i o n sa n d t h e i r a p p l i c a t i o ni ni n t e g e rl i n e a rp r o g r a m m i n ga r eg i v e n ；f o u r t h l y , t h em o d i f i e da b s a l g o r i t h m sf o rs o l v i n go v e r d e t e n n i n e dl i n e a rd i o p t m u f i n ee q u a t i o n sa n di n e q u a t i o n sa r e p m s e n t e d ；f i n a l l y , t h ep r o g r a m sc o d e db ym a t l a b f o rs o m ec o r r e s p o n d i n ga b sa l g o r i t h m s a r eg i v e n t h em a i nr e s u l t so b t a i n e di nt h i st h e s i sc a nb es u m m a r i z e d 聃f o l l o w s ： 1 i nc h a p t e rt w o ，t h em e t h o & f o rs i n g l ed i o p h a n t i n ee q u a t i o na r ca n a l y z e d ，s u c ha s r o s s e ra l g o r i t h ma n df o r t e n b a c h e ra l g o r i t h m ；s oa r et h em e m o d 8f o rl i n e a rd i o p h a n t i n e e q u a t i o n s ，s u c h a se m a sa l g o r i t h ma n dc o n t e j e a na l g o r i t h m 2 i nc h a p t e rt h r e e ，t h ei n t e g e ri m p l i c i tl ua l g o r i t h ma n dt h ei n t e r g e ri m p l i c i tl x a l g o r i t h ma r ea n a l y z e dbd e t i a l ；f i t h e m o r e a l le x a m p l ei sg i v e n t oi l l u s t r a t et h ed i f f e r e n c e o f t h ei m p l i c i tl ua l g o r i t h ma n dt h ei m p l i c i tl xa l g o r i t h mb e t 、v 嘲r e a ln u m b e rf i e l da n d i n t e g e rf i e l d 3 c h a p t e rf o u rg i v e sa b sa l g o r i t h m sf o rs o l v i n gl i n e a rd i o p h a n t i n ei n e q u a t i o n sa n d t h e i ra p p l i c a t i o ni ni n t e g e rl i n e a rp r o g r a m m i n g 4 c h a p t e rf i v ep r e s e n t st h em o d i f i e da b sa l g o r i t h m sf o rs o l v i n l gl i n e a ro v e r d e t e n n i n e d l i n e a rd i o p h a n t i n ee q u a t i o n sa n di n e q u a t i o m 5 t h ep r o g r a m sc o d eb ym a t l a bf o rs o m ec o r r e s p o n d i n ga b sa l g o r i t h m sa r eg i v e ni l l a p p e n d i x k e y w o r d s ：a b sa l g o r i t h m s ；l i n e a rd i o p h a n t i n ee q u a t i o n s ；t h ei m p f i e i tl ua l g o r i t h m ； f i n e a ri n t e g e ri n e q u a l i t i e s ；o v e r d e t e r m i n e dl i n e a rd l o p h a n t i n ee q u a t i o n s ； o v e r d e t e r m i n e dl i n e a ri n e q u a l i t i e s ；u 虹l a bp r o g r a m s - 求解线性丢番圈方程组及不等式组的a b s 算法 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：盍盟日期：趔：z ：竺 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版 权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的 复印俘和电子版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等 复制手段保存和汇编学位论文。 高执錾 作者躲边气历作者签名：迨照。竺= 一r 。二淤 、 p r o fz u n 0 u a nx 门 l o - 导师签名：_ 蒜豁罨鼎篙等；蔷滟。b v 翌越键百月船 大连理工大学硕士学位论文 1 绪论 1 。1 线性丢番图方程的研究发展 丢番图方程是较为常见的一类整方程模型，近些年来得到广泛的研究。求解线性丢 番图方程组的方法很多，大部分集中在对指数形式丢番图方程的求解与研究，线性丢番 圈方程组却少为人注意，特别是不等式组。线性丢番图方程组及不等式组是实际应用中 较为常见的一类方程，在物流、运输等问题中起着重要的作用。2 0 世纪4 0 年代，r o s s e r 给出了单个线性丢番图方程组的求解算法【l 】，即求n 个整数的最大公因子算法，e g e r v a r y 随后给出齐次线性丢番图方程组的求解算法【2 】。6 0 年代，w e i n s l o c k ( 1 9 6 0 ) 1 3 ，b l a n d s h i p ( 1 9 6 3 ) 【4 】，b r a d l e y ( 1 9 7 0 ) 1 5 相继找到求解最大公因予的算法，但是从计算的稳定性 考虑仍然逊于r o s s e r 算法。这些算法的缺点是都局限于欧几里德算法。 8 0 年代f o r t e n b a c h e r 采用搜索的方法直接求解单个齐线性丢番图方程嘲：9 0 年代， c ：i e _ i e 随和d e v i e 推广了f o r t e n b a c h e r 算法的思想【7 】，将其应用至u 齐次线性丢番图方程 组的求解中，该算法首次从整体上求解方程组而不必使用g a u s s 消元；p o t t i e r ，d o m e n j o u d 等也给出了此类算法f 9 1 【1 们，基本思想与c o n t e j e a n 算法一致，唯一不同的是搜索过程中 的限制条件不同。薛方的l f l 方法用于求单个线性丢番图方程的非负解【l l 】，与上述算 法本质相同。 1 9 9 9 年a 1 ) a 妇f 5 r 等开始致力于a b s 算法在线性丢番图方程组中的应用，e s m a e i l i ， m a h d a v i a m i f i 和s p e c i d a t o 将r o s s e r 算法求解最大公因子的技巧应用到a b s 算法中， 给出了判断线性丢番图方程组是否有解和计算一般解的新算法，简记为e m a s 算法【1 2 1 ， 该算法能够给出通解的一般表达式。本文在此基础上继续探讨a b s 算法在线性丢番图 方程及不等式组中的求解及其应用，为此下面介绍a b s 算法的一些概况。 1 _ 2a b $ 算法与软件的进展 1 2 1 船s 算法的研究 1 9 7 9 年，匈牙利数学a b a 妇f j r 教授受到当时行之有效的求解线性方程组、非线性方 程组以及无约束优化问题的拟牛顿法的影响，给出了a b s 算法的原始模型。在此之前， 已有许多与该算法有密切关系的工作，如w e d d e r b u r n ( 1 9 3 4 ) 的矩阵降秩校正，e g e r v a r y ( 1 9 5 3 1 9 6 0 ) 已考虑到校正a b a 仔y 阵的紧缩形式( 遗著，1 9 6 0 ) 【1 3 】，a d a c h i ( 1 9 7 1 ) 关于拟牛顿法的工作，h u a n g ( 1 9 7 5 ) 关于线性方程组的一个直接法的工作【，a b a f 母 ( 1 9 7 9 ) 关于h u a n g 算法推广工作以及赵金熙( 1 9 8 1 ) 关于相容方程组的h u a n g 算法 及其推广工作1 1 4 】。 求解线性丢番图方程组及不等式组的a b s 算法 1 9 8 2 年，a b a f t 与英国著名优化与计算数学专家b r o y d e n 以及意大利著名优化与计 算数学、天体物理学专家s p e d i a t o 在共同合作研究中发展了一类用于求解线性方程组与 非线性方程级的投影算法，后来被正式命名为a b s 算法【嘲。经过近2 0 年的发展，a b s 算法目前不仅可用于求解线性与非线性方程组的等有关数值代数问题【m ，而且还可以用 于求解线性规划和具有线性约束的非线性规划等问题”埘【1 9 1 2 0 。从统一模式的观点来看， a b s 算法类具有很强的潜在的统一功能。 1 9 8 9 年，a b a f f y 教授和s p e c i d a t o 教授合写了关于a b s 算法的专著( a b s 投影算 法求解线性和非线性方程组的数学方法f l 嗣，书中介绍了一些典型的a b s 算法， 如h u a n g 算法、隐式l u 算法、尺度化a b s 算法、q r 算法等。非线性a b s 算法首先 由a b a f f y ，g a l a n m i s p e c i d a t o 以逐个方程、分块的形式提出。非线性a b s 算法的进 一步发展多集中在对其收敛性的研究和数值实验方面。1 9 9 0 年以后，s p e o i d a t o 等用a b s 算法研究构造求解线性约束最优化问题的可行方向法、线性规划的单纯形法、二次规划 的惯性数方法，取得了重要的进展和较为系统的研究成果，参见专著优化中的a b s 算法引论【2 n ，这些结果还部分用于实际工程计算中。这一时期，重要的成果之一是隐 式l x 算法的产生，这体现在单纯形法中的显式转轴公式的建立及良好的计算效果。 目前，a b s 算法由三个基本子类，基本( 非尺度化) 算法、尺度化算法与块尺度化 算法所构成。 首先，考虑线性方程组 血= b ( 1 1 ) 其中a e r ” ，b r “并且, n s 一。 a b s 算法是一类求解线性方程组的直接法，它产生个近似解序列托 ：1 ，这个序 列具有这样的性质，即在第i 次迭代得到的而+ 是前i 个方程的解。 下面我们介绍a b s 算法类的基本迭代格式。 基本( 非尺度化) a b s 算法： 其中含三个参数( a b a f f y 参数嵋，b r o y d e n 参数五，s p e d i c a t o 参数日) s t e p l ：假设毛r ”为任意向量，h i r ”为非奇异矩阵，f = l 且孵昭= 0 。 s t e p 2 ：计算q = 而一6 f 和暑= 日q 。 s t e p3 ：若o ，转到s t e p 4 ；若= 0 ，f l = 0 ，置而+ l = 毛，q “= 皿，f l a g = t f l a g + 1 ； 若i 0 ，a ta 2 吒o ( 如果巳 o ，那么令为一；如果q 口l ， ， f ，那么交换x ，和；如果口l = o ，那么我们得到平凡方程) 。令a = ( 口l ，) ，r o s s e r 算法起始与矩阵c = ( 纯j ) 7 ，再令c f ，表示( i ，j ) 处元素，c j 表示c 的第j 列。算法步骤可 以概括如下( 我们记i 口i 为不大于a 的最大整数) 。 r o s s e r 算法 ( 1 ) 令c ( o ) = c ，k = 0 ； ( 2 ) 如果c 譬0 ，进行如下步骤 ( a ) c f m - c f “一lq p c 紫 c ” ( b ) 对c ( “1 进行列变换，使得c f 2 芝搿“ 令k = k + l ： ( 3 ) 记终结矩阵为u = ( d ，u 7 ) ，其中u = ( 1 ，一，) ， ，z “，d z “，d 除了第一 个元素等予占= g e d ( a ，a n ) 外，其余所有元素为0 。如果6 不能整除b ，那么方 l 程无整数解，g i 女l u x = 詈“1 + y 2 u 2 + + y 。u n ，对于任意的整数y 2 ，以，构成了方 u 程组的一般解。 下面列出了从算法中观察到的一些结论： 1 一个整矩阵称为是幺模的，如果矩阵行歹l | 式的模等于l ( 由此可以推倒出其相应逆矩 阵也是整矩阵) 。 2 如上定义的矩阵u = 0 l ，一，) 是幺模的。 3 由( 1 ，一a 7 ) c = 0 ，我们有( 1 ，一，) c ( ) = 0 ，对所有的七( 即从c ( “到c ( 仅仅是列变 换) 。从而口7 = 6 ，a t l 4 j = 0 ，= 2 ，蚪。 4 r o s s v r 算法在多项式时间内终止，见下面s e h r i j v e r ( 1 9 8 6 ) 的定理。 定理2 1 1 2 r o s s e r 算法终止于玎的多项式运算次数，从而使单个有理丢番图方程的复 杂性是多项式的。而且对于整数相容的丢番图方程组出= b ，z z ”，可以看到在多项 式时间内，得到的整数向量而，t ，x ，中x l ，x 。是线性无关的， x z ”i a x = 6 = x o + f 1 x 1 + + f p x p l f i z ，f = 1 ，p ) 。 小结：从算法中我们可以观察到r o s s e r 算法本质上是辗转相除法的不断运用。无论在理 论上还是在实际运算中都是成功的。 2 1 2e m a s 算法 大连理工大学硕士学位论文 e s m a e i l i ，m a h d a v i a m i r i 和s p e d i c a t o 将r o s s e r 算法求解最大公园子的技巧应用到 a b s 算法中，给出了判断线性丢番图方程组是否有解和计算一般解的新算法，简记为 e m a s 算法。 下面的两个定理给出了解的存在性和确定性证明。 定理2 1 2 1 假设一行满秩，线性丢番图方程组( 2 i ) 可解，考虑运用基本a b s 算法， 基于如下参数选择所产生的a b a f f y 序列： ( a ) e 是幺模矩阵； ( b ) 对于f = l ，m ，w t 满足日j q = 6 r ，最= g e d ( h t a , ) ； 那么下面的性质成立： ( c ) 算法所产生的a b a f f y 序列是良定的整数矩阵： ( d ) 如果只+ 。是前i 个方程的一个特解，那么前i 个方程的任意整数解可以表述如下： x = y j + 1 + 磁l q ，q z ”a 定理2 1 2 2 假设彳行满秩，考虑参数选择如前面定理的基本a b s 算法所产生的a b a f f y 阵序列骂，设而是基本a b s 算法中的任意初始整数解，的选取满足 彳h e a j = g e d ( h t a t ) 则线性丢番图方程组有整数解的充要条件是g c d ( q 口i ) i ( a s x , 一6 j ) ，i = 1 ，l 。 运用上述结果，e s m a e i l i ，m a h d a v i a m i r i 和s p e d i e a t o 给出了求解线性丢番图方程 组的e m a s 算法，如下所述： s t e p l ：任取向量置z ”，幺模矩阵h i z “”，置i = 1 ， = 0 。 s t e p 2 ：计算f ，= 一t - b , 和t = 珥口f 。 s t e p3 ：若= 0 ，f f = 0 ，置t + l = 薯，h e “= i - 1 , ，+ 1 = ；若i 0 ，那么对于某个满足q o 的一加1 。 f o n e n b a c h e r 的限制可以用下面的简单条件表示2 某个工f 如果满足a ( x ) x a ( e ，) 0 ，则x j = x ，+ 1 。 其几何解释如下图所示： 0 图2 2 1 表示f o r t e n b a c h e r 限制的几何解释 2 2 2c o n t e j e a n 算法( f o r t e n b a c h e r 算法的推广) 无论单个方程还是方程组系统，( 2 2 ) 中给出的口( z ) 的定义表明系统的任意解可以 看作是和为0 的缺省向量的组合。从这些向量中选取任意的序使得我们可以构造从原点 出发而又回到原点的缺省向量序列。算法的根本思想就是从空序列开始逐步地构造这样 的序列，新的缺省向量非确定性地增加直到找到解或得不到最小解为止。不同的序列可 能对应相同的解，f o r t c n b a c h e r 的限制能够约束搜索，淘汰掉大部分而不是所有的多余 序列。对于方程组系统，c o n t e j e a n 和d e v i e 在构造缺省序列的每步中去掉了不含原点的 半空间，推广了f o r t e n b a e h e r 的限制。其几何解释如下图所示； 0 图2 2 2f o r t e n b a c h e r 限制的推广( c o n t e j e a n 算法的几何解释) 一般的说，缺省向量的一个序列x ，如果和口o ) 非零，那么第，个元素可以加1 ， 使得口o + 勺) = 口( x ) + 口呜) 属于包含原点且被垂直于向量口( x ) 的仿射超平面限定的半空 间。用数学的语言可以将这个约束表述成： 求解线性丢番图方程组及不等式组的a b s 算法 对某个，如果满足砷口( 巳) 0 ，则t = t + l 。 这个约束减小了搜索空间却没漏掉最小解。下面给出一个求解线性丢番图方程组的基卢 的算法。 c o n t v j v a n 算法【7 】： i n p u t ：口( 劝= 0 为一线性丢番图方程组系统。 p ：= 岛，e q ) 口= o w h i l e p o ，d o 卢：= 卢w x pj a ( x ) = o ) ：= x p 卢l v s 卢，x 。s ) p ：= j + qi 膏，口( 功口( q ) o ，则循环：j = 1 ，i ， a j 厶，则 ( a ) x j4 ：- - + 1 ； ( b ) 调用f a c t o r 2 ( k - d l j ) o ( c ) 1 时，驴老瓮。 定理3 1 2 1 当4 是强非奇异阵且口】。a 埘1 为整矩阵时，i i l u 算法是适定的。 推论3 1 2 1a 的顺序主子式都是幺模的，则i i l u 算法适定的。 定理3 1 2 2 假定a 强非奇异且阻“】- 1 a ”1 为整矩阵，在( 2 1 ) 式中考虑i i l u 算法， 则该线性丢番图方程组有整数解的充要条件是，e q | a r x , 一6 j ，i = 1 ，小。 推论3 1 2 2 如果爿的顺序主子式都是幺模的，则线性丢番图方程组有整数解。 推论3 1 2 3 如果彳满秩的全幺矩阵，则线性丢番图方程组有整数解。 3 1 3i i l u 算法的性质 性质3 1 3 1 假设算法是适定的，则a b a 仟y 校正矩阵耳+ 1 为 县“= 三， ，其中矸= 叶彳u r l 4 加。 性质3 1 3 ，2 迭代方向p j 至多有i 个非零整分量且第i 元素为1 ，后 一i 个元素为0 ，即 只= ( p l ，只) 是上三角单位整矩阵。 性觚l s s 系统的一般解可表示如下：对任意的峭一，一。+ 乏 g 。 性质3 1 3 4 假设一z ”强非奇异且【爿】。a ”“为整矩阵，则i i l u 算法的乘法性运算 次数不超过n m 2 2 m 3 3 加低阶项。 3 1 4 算法在求初始可行解中的应用 i i l u 算法可应用于系数矩阵满足一定条件的网络流计算中的一类问题，如运输问 题，分配问题等。设g = ( 矿，三) 是非平凡赋权连通图，6 = ( 岛) 。为满足魏= o 的供应量， c = ( 乞) 。为费用向量。最小费用流问题可如下表示： m i n 巳t ( p ) s t t 一t = 6 f ，f 矿 t 0 ，p e 记4 是问题( p ) 的点弧关联矩阵，则问题( p ) 可以表示如下： m i n c 7 z s t a x = b 大连理工大学硕士学位论文 任取，v ，去掉，所在的行后得到矩阵彳和向量b 。关联矩阵彳去掉一行后得到的矩阵 爿是行满秩的，且是完全幺模的，一经列变换后可以转化成顺序主子式为幺模的矩阵。 于是问题等价于下面的问题 n f m c 7 z s t a x = b x 0 对于c = ( 1 ，1 ，1 ) 的情形，求解规划问题只要求出约束条件的一个可行解就可以， 应用i i l u 算法可以直接求解。 对于c ( 1 ，1 ，1 ) 7 的情形，由于矩阵的特殊性，问题a x ；b 如果有解，则每个基 本可行解都是整向量，可用网络单纯形法求解此规划问题。应用i i l u 算法可以获得一 个初始可行解。 算例 有向图g 的关联矩阵如下表所示： 点弧 e , 2岛3e 1 6岛4e 2 5e 3 5e 4 6 1 1l1o0oo0 0 21oo11o0o0 30100o1100 40 o0 1 0 1o11 50 0 o01 0 + 1 o 1 6o010o0o- 1o 表3 1 4 有向图g 的关联矩阵 当c = ( 1 ，l 1 一，1 ) 7 时，关联矩阵去掉最后一行后得到的矩阵，经验证顺序主子式全为幺模 的，b = ( 1 ，0 ，0 ，0 ，0 ) ，应用i i l u 算法可以得到一个解x = ( 1 ，0 ，0 ，0 ，1 ，0 ，0 ，1 ，1 ) 。 与终端因子列表法( l f l 方法相比) ，i i l u 算法不仅可以计算解是自然数的情况， 而且对于负整数同样也是适用的。 3 1 5i i l u 算法在整线性规划中的应用 考虑整线性规划问题( i l p ) m i n c 7 x s t a x = b( 3 1 ) x e z ” 其中c z ”，b z ”。a z 擀”，m s 拜。 假设a x = b 是整数可解的，运用i i l u 算法求解a x = b ，那么上述问题等价于下面 无约束问题【3 4 1 求解线性丢番图方程组及不等式组的a b s 算法 m i n ( c t x m + l + c 7 磁“g ) 设c = ( 气，一。) ，q = ( ，吼一。) 7 ，利用i i l u 算法的性质，则目标函数可以简化为 憾吨 ：乏煳= h “。“令峭一 m i n c + i + ( 群+ 。) 们 ( 3 2 ) ( b ) 如果( c 。群+ c 。，) g = 0 ，贝1 1 x m + 。是问题的最优解；否则( 3 2 ) 整数无界，从而问 而= i ，屿= 工= | h 三避孵 因为x t ，x 2 ，x 3 0 ，所以有o s q 3s 3 ，于是目标函数 f ( x ) = 3 ( 3 一q 3 ) + 4 ( 3 - q 3 ) + 吼= 2 1 - 6 q 3 3 。2ii l x 算法及整线