（基础数学专业论文）01整数规划在教育问题中的应用研究.pdf

一】1 0 - 1 i n t e g e rp r o g r a m m i n g p r o b l e mi nt h ea p p l i c a t i o no fe d u c a t i o n at h e s i ss u b m i t t e df o rt h ed e g r e eo f m a s t e r c a n d i d a t e ：z h a n gh a i y a n s u p e r v i s o r ：p r o f l i uh u i q i n g h u b e i u n i v e r s i t y w u h a n ，c h i n a 0 3帅96洲3川，iii1州y 湖北大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 论文作者签名牟奇盔、 日期：幽，。年，月，o e l 学位论文使用授权说明 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 按照学校要求提交学位论文的印刷本和电子版本；学校有权保存并向国家有关 部门或机构送交论文的复印件和电子版，并提供目录检索与阅览服务；学校可以允 许采用影印、缩印、数字化或其它复制手段保存学位论文；在不以赢利为目的的前 提下，学校可以公开学位论文的部分或全部内容。( 保密论文在解密后遵守此规定) 作者签名厂辨备、丞、 ，t 一。l 、 、 指导教师签名：习蹩诵 日期：“彳j - j 。日 日期：珈，s o 摘要 已知许多实际的优化问题的数学模型都是线性规划，而整数规划是n p 难，整数线 性规划问题是n p 完全问题所以o 1 型线性整数规划模型必须在充分考虑问题本身的 性质的基础上采用适当的优化方法进行求解 本文利用整数规划的相关理论，研究了o 1 整数规划在教育领域中的两个应用对 于高校课程优选问题，分为学年制收费模式和完全学分制收费模式两种情形分别建立了 不同目标情况下的整数线性规划模型，并根据具体例子利用l i n d o 软件编程求出了最优 解这些最优方案对于学生选课有一定的指导意义而对于基于时间费用指标的课余技 能培训问题，通过分析建立了相应的o - 1 整数规划模型，并采用了基于l a g r a n g e 松弛的 分解算法将一个大规模问题转化为了小规模问题进行计算，进而给出了最优的培训方 案 关键词：o - l 整数规划；课程优选；技能培训；l a g r a n g e 松弛；分解算法 a b s t r a c t m a n vp r a c t i c a lo p t i m i z a t i o np r o b l e m sk n o w nt o t h em a t h e m a t i c a li n o d e l sa r el i n e a r p r o g r a m m i n g ，a n di n t e g e rp r o g r a m m i n gi sn ph a r d ，i n t e g e rl i n e a rp r o g r a m m i n gp r o b l e m i s n p c o m p l e t e s oo 1 l i n e a ri n t e g e rp r o g r a m m i n gm o d e lm u s tt a k ef u l la c c o u n to ft h en a t u r e o ft h ep r o b l e mi t s e l fb a s e do nt h eu s eo fa p p r o p r i a t eo p t i m i z a t i o nm e t h o dt os o l v e i t i n t h i sp a p e r , t h et h e o r yo fi n t e g e rp r o g r a m m i n gt os t u d yt h eo - 1i n t e g e rp r o g r a m m m g i nt w oa p p l i c a t i o n si nt h ef i e l do fe d u c a t i o n f o rc o l l e g ec o u r s e sp r e f e r r e di s s u ei n t ot h e a c a d e m i cy e a ra n df u l lc r e d i tf e ec h a r g i n gm o d e le s t a b l i s h e di nt w os i t u a t i o n sw i t hd i f f e r e n t g o a l si nc a s eo fi n t e g e rl i n e a rp r o g r a m m i n gm o d e l ，a n ds p e c i f i ce x a m p l e so fu s i n g s o f t w a r e p r o g r a m m i n gl i n d oo b t a i n e dt h eo p t i m a ls o l u t i o n t h e b e s to p t i o nf o rs t u d e n t st oh a v es o m e g u i d a n c ef o rc o u r s es e l e c t i o n t h ec o s ti n d e xf o rt h et i m e b a s e da f t e r - s c h o o ls k i l l st r a i n i n g , e s t a b l i s h e db ya n a l y z i n gt h ec o r r e s p o n d i n g0 - 1i n t e g e rp r o g r a m m i n gm o d e l ，w h i c h i sb a s e d o nl a g r a n g er e l a x a t i o nd e c o m p o s i t i o na l g o r i t h mw i l lb e al a r g ep r o b l e mi n t os m a l l e r p r o b l e m st ob ec a l c u l a t e d ，t h u sg i v i n gt h eo p t i m a lt r a i n i n gp r o g r a m k e yw o r d s ：0 - 1i n t e g e rp r o g r a m m i n g ；c o u r s e s e l e c t i o n ；s k i l l st r a i n i n g ；l a g r a n g er e l a x a t i o n ； d e c o m p o s i t i o na l g o r i t h m l l 目录 第章引言1 第_ 二章高校课程优选问题及模型3 2 1 情形一4 2 1 1 提出问题4 2 1 2 建立模型4 2 1 3 求解模型6 2 2 情形二8 2 2 1 提出问题8 2 2 2 建立模型一8 2 2 3 求解模型9 2 3 分析模型1 0 第三章课余技能培训问题及模型1 l 3 1 提出问题，1 3 3 2 建立模型1 4 3 3 求解模型15 3 4 分析模型1 8 参考文献1 9 致谢2 l 第一章引言 第一章引言 要求一部分或全部决策变董必须取整数值的规划问题称为整数舰划i 1 1 不考虑移数 条件，由余下的目标函数和约束条件构成的规划问题成为该整数舰划问题的松弛问 题若松弛问题是一个线性规划，则称该整数规划为整数线性规划整数线性规划同线 性规划形式上非常相似，不同之处是决策变量部分或全部取整数 而在整数规划中，为了满足整数解的要求，初看似乎只要把已得到的带有分数或小 数的解经过“舍入化整”就可以了，而实际上化整后不见得是可行解；或虽是可行解， 但不一定是最优解1 2 1 如果所有变量都必须取整数，则称为纯整数线性规划；如果仅一部分变量必须取整 数，另一部分可以不取整数，则称为混合整数线性规划整数规划的一种特殊情形是 0 1 整数规划，即变量只能取值0 或1 ，称其为o 一1 变量o 1 变量作为逻辑变量，常被 用来表示系统是否处于某个特定状态，或者决策时是否取某个特定方案例如 f 1当决策取方案p 时 石2 1 0 当决策不取方案尸时( 即取芦时) 当问题含有多项要素，而每项要素皆有两种选择时，可有一组o 1 变量来描述一 般地，设问题有有限项要素巨，最，e ，其中每项毛有两种选择彳j 和彳 ( j = 1 , 2 ，1 ) ，则可令 1 1 若e ，选搠， t 。1 0 若二，选崭，( j = 1 , 2 , - - - , n ) 对于o 1 型整数规划，若含有以个变量，则可以产生2 ”个可能的变量组合当阼较 大时，采用完全枚举法解题几乎是不可能的【3 1 如果该整数规划的目标函数和约束条件 对于决策变量而言都是线性的，那么该整数规划同时就又是一个线性规划所以一般 0 1 型线性整数规划模型的求解，可以采用l i n d o 软件和隐枚举法相结合，或者采用其 它优化算法f 4 1 假设问题和解决该问题的一个算法已经给定，若存在多项式函数g ( x ) ，使得 a ( ，) a g ( 1 ( i ) ) 对给定问题的所有实例均成立，则称该算法为解决对应问题的多项式时 湖北人学硕+ 学位论文 间算法这罩，为问题的一个实例，实例规模为，( ) ，算法a 在求解，时的汁算量( 基 本计算总次数) 为c 。( ，) 对于给定的一个优化问题，若存在一个求最优解的算法、个多项式函数g ( 工) 和 常数o e ，使得c 爿( ，) 昭( ，( 聊对该问题的所有实例成立，则称给定的优化问题是多项式 时间可解问题，或简称多项式问题而线性规划问题是多项式问题1 对一个判定问题，若存在一个多项式函数g ( x ) 和一个验证算法a ，满足，为判定问 题“是”实例的充分必要条件，即存在一个字符串s 表示，的可行解，其规模 t ( s ) = d ( g ( ，( 助) ，其中，( ，) 为j 的规模，且算法a 验证s 为实例，的“是”答案的计算 时间为d ( g ( ，( ) ) ) ，则称这个判定问题是非确定多项式的，简记为n p 。在不混淆的情况 下，用n p 表示所有非确定多项式问题的集合 并不是所有组合最优化问题都找到了求最优解的多项式时间算法也就是说，还不 能肯定一些组合最优化问题是否属于多项式问题集合m 迄今为止，对于这些还没有一 个有能求最优解的多项式时间算法的问题归为所谓的n p 完全嗍和n p 难9 1 具体来说， 如果判定问题a 满足a n p 且n p 中的任何一个问题都可在多项式时间内归约为a ， 则称a 为n p 完全若n p 中的任何一个问题都可在多项式时间归约为判定问题a ，则 称a 为n p 难 o 1 规划在整数规划中占有重要地位，借助于相关软件和优化算法，可以解决许多 实际问题 而当前正是知识经济时代，在校教育和业余学习是两条获取知识技能的主要途 径本文主要针对o 1 整数规划在教育领域的两个具体应用：高校课程优选问题和课余 技能培训问题加以分析，分别建立整数规划模型，并根据不同情况采取不同的方法进行 求解，最终获得各问题的最优方案 2 第二：章高校课科优选问题及模型 第二章高校课程优选问题及模型 现在，高校耻课程按学分值进行设置选课足大学 t - 学习过程中的，个非常重要的 组成部分在教务处有关规定下，每学期的必修课程学生必选，而选修课程( 包括专业 限选课程和任选课程) 则可由个人爱好学生自己决定0 0 1 学生可根据自己的实际情况 和学校关于学分选择的规定进行选课 而日d 订对于高校课程优选l u j 题人们已经做了大量的研究，提出了多种可行的解决方 案，但实际应用的情况并不理想，学生进行课程选择时缺乏理论的科学指导，主观的盲 目性造成了不合理的选课而这种盲目一方面会造成学校资源的浪费，另一方面也不利 于学生最优限度地学习知识和顺利完成学业针对这种情况，本章给出具体案例，提出 了基于0 - 1 整数规划的选课算法研究，并且根据不同情形下的不同需求修改了选课策 略，从而满足学校对于选课问题的特定规则，因此具有很高的可移植性 具体地，本章中考虑到有部分高校采取学年制收费模式，每学年学费数目固定，学 生只须按教务处有关规定选课；而还有部分高校学生采取的是学分制收费模式，学费主 要依据学分多少收取，那么学生选课必然会考虑相关的学费问题这就使得课程优选必 须根据不同情形，分别加以分析，并借助0 1 整数规划原理建立不同的课程优选模型， 从而解决此问题 下面结合某高校学生的选课实例对不同情形下的课程优选模型进行阐述 以下是某学校对大学二年级下学期在开学选课时的规定： 该学期必修课程4 门( 此4 门必修课未在文中列出) ，总共1 0 个学分；限选课程7 门，任选课程1 1 门限选课程和任选课程的学分设置情况及部分课程间关系如下表2 1 另，学校关于选课有如下相关规定： ( 1 ) 所选课程总学分( 包括1 0 个必修课程学分) 不能少于2 0 个学分； ( 2 ) 限选课至少选1 门； ( 3 ) 任选课的学分合计比例不能少于所修全部课程总学分数的六分之一 表2 1 课程学分及选修要求表 课程编码学分课程性质备注 12专业限选 22专业限选 3 湖j 匕人学硕十学位论文 2 1 课程学分及选修要求表( 续) 3 2 专业限选与课程7 只选其一 4 2专业限选 53专业限选必须在选课7 之前选此课程 63专：l k l j e 选 与课程1 3 只选其一 72 专业限选与课程3 只选其 82 任选 92 任选 l ol任选 必须与课程l1 一起选 1 1 2任选必须与课程1 0 一起选 1 2 3任选 1 32 任选与课程6 只选其一 1 42任选 1 53任选 1 62 任选必须同时选修课程1 5 1 71任选 1 8l任选 2 1 情形一 若该高校采取的是学年制收费模式，这是当前一部分高校所采用的学费收费模式。 即学费收取的数目固定，学生选择课程时可以不考虑学费因素 2 1 1 提出问题 按如上学校的相关规定，学生选课时会思考如下问题： ( 1 ) “为达到学校要求，我本学期最少应该选择几门课? 选哪几门课? ” ( 2 ) “在选修最少学分( 即2 0 学分) 的情况下，最多可以选修多少门课? 哪几门课? ” 2 1 2 建立模型 针对上述情况建立0 1 整数规划模型，具体如下： 4 第二章高校课私优选问题及模型 。二二二一 1 ) 用x i 表示是否选择该课程，这里，x ，= 1 表示该课程被选择，x i ：0 表示该课程未 被选择； 2 ) 若西门课程不能同时选，只能选择其一，用石，+ 工，1 表示； 3 ) 若两门课程必须f 一时选择，用工，一工，= 0 表示； 4 ) 若选课程f 自订必须先选课程，用一彳o ，x i + x l 表示； 5 ) 选修课程f 时必须同时选修课程，用一一_ o 表示； 6 ) 限选课至少选1 门，用工，l 表示 i = l 故对问题( 1 ) 可建立以所选课程数目最少为目标，同时又满足学分要求和选修要求 的0 - 1 型整数规划模型( 1 ) 如下： m i n x i 下： 2 _ + 2 x 2 + 2 屯+ 2 x 4 + 3 x 5 + 3 x 6 + 2 x 7 + 2 x s + 2 x 9 + o + 2 x l i + 3 x 1 2 + 2 _ 3 + 2 五4 + 3 五5 + 2 而6 + 西7 + 8 + 1 0 2 0 + 屯+ 毛+ + 黾+ 黾4 - 而1 2 而+ 2 x 2 + 2 而+ 2 x 4 + 3 x 5 + 3 x 6 + 2 x 7 一l o x s - l o x 9 - 5 x l o 一1 0 l 一1 5 而2 一l o 五3 一l o x l 4 1 5 x 1 5 1 0 x t 6 5 x 7 - 5 x 1 8 + 1 0 0 x 3 + x 7 1 工6 + 而3 1 z l o 飞l = 0 而5 一x 1 6 0 而一黾0 x 1 + x s 1 t = o 或l ( i = 1 , 2 ，1 8 ) 类似地，对问题( 2 ) 可建立以所选课程数目最多为目标的0 - 1 型整数舰划模型( 2 ) 如 1 8 m a x y t 一一 i = l 湖北人学硕十学位论文 一l _ 一 2 x 1 + 2 x 2 + 2 x 3 + 2 x 4 + 3 x 5 + 3 x 6 + 2 x 7 + 2 x 8 + 2 而+ x l o + 2 x l l + 3 x 1 2 + 2 x t 3 + 2 x 1 4 + 3 五5 + 2 x 1 6 + _ 7 + x 1 8 + 1 0 = 2 0 x i + x 2 + x 3 + 以+ x 5 + x 6 + x 7 1 2 x l + 2 x 2 + 2 x 3 + 2 x 4 + 3 x 5 + 3 j 6 + 2 x 7 一l o x l 3 一l o x s l o x 9 5 x i o l o x l i 一1 5 x 1 2 一l o x l 4 15 x 1 5 一l o x l 6 - 5 x 1 7 5 x 1 8 + 1 0 0 x 3 + x 7 1 x 6 - t - x 1 3 1 x l o - - x i l 50 x 1 5 一x 1 6 0 x 7 一屯0 x 7 + x 5 1 x i = 0 或l ( f = 1 , 2 ，1 8 ) 2 1 3 求解模型 利用l i n d o 软件来求解以上线性0 - 1 规划模型( 1 ) ，程序如下： m i n丑+ 也+ 为+ 舛+ 巧+ 娟+ 刃+ 弼+ 四+ n 僻dl + 矗2 + 丑3 十j c l “n 钭n “n 7 + 丑8 s t 2 x l + 2 x 2 + 2 x 3 + 2 x 4 + 3 x 5 + 3 x 6 + 2 x 7 - ! - 2 x 8 4 - 2 x 9 + x l o 第二章高校课雅优选问题及模型 l i n d o 语言中变量下标亦类推 运行结果为：x 。= x 。= x ，= _ 5 = l ，其它x ，= 0 。即最少要选修4 门课，课程编号 为4 ，6 ，7 ，15 该整数规划的最优解不唯一。例如，还有豉优解：x 。= x 。= x ，= x 。：= l ， 其它= 0 一般地，得到一个整数规划问题的所有最优解很困难2 】以下我们通过对 变量的约束进行隐式枚举并给出所有解1 1 3 j ，其具体操作是：在以上程序中每次添加约 束一= 0 ( 或1 )o = 1 , 2 ，1 8 ) 经过3 6 次运算，得到最优选课方案如下表2 - 2 ： 表2 2 最优选课方案 如上所得最优选课方案共有9 种，这9 种选课方案所得学分恰好为2 0 为得到2 0 个学分选4 门课就可以了 利用l i n d o 软件来求解以上线性0 一l 规划模型( 2 ) ，程序如下： m a xx l + x 2 + x 3 + 科+ 巧+ j d 5 + 刀+ 弼+ 力+ 姐o + 一l + 丑2 + 丑弭姐4 + 丑5 + d 6 + 矗7 + 姐8 s t 2 x l + 2 x 2 + 2 x 3 + 2 x 4 + 3 x 5 + 3 x 6 + 2 x 7 + 2 x 8 + 2 x 9 + x 1 0 + 2 x ll + 3 x 1 2 + 2 x 1 3 + 2 x 1 4 - 4 - 3 x 1 5 + 2 x 1 6 + x 1 7 + x l8 = l o 工l + x 2 + x 3 + x 4 + x 5 + x 6 + x 7 = 1 2 x l - i - 2 x 2 + 2 x 3 + 2 x 4 + 3 x 5 - 4 - 3 x 6 + 2 x 7 一l o x 8 l o x 9 5 x 1 0 1 0 x ll 一1 5 x 1 2 一l o x l 3 1 0 x 1 4 1 5 x l5 一l o x l6 5 x 1 7 5 x 1 8 = - 1 0 x 3 + x 7 = 0 x 7 + x 5 = 1 0 z l + x 2 - i - x 3 + x 4 + x 5 + x 6 + x 7 = 1 2 x l + 2 x 2 + 2 x 3 - i - 2 x 4 + 3 x 5 + 3 x 6 + 2 x 7 一l o x 8 一l o x 9 5 x 1 0 一l o x l l 1 5 x 1 2 1 0 x 1 3 一l o x l 4 1 5 x 1 5 一l o x l 6 5 x 1 7 5 x 1 8 = 一1 0 x 3 + x 7 = 0 x 7 + x 5 _ d 两组约束，采用l a 松弛的方法去掉式( 3 2 ) 中的约束工= y ，对任意旯得 m i n c r x + 2 r ( x y ) ) s t a x b b y d x , y z ： 由目标函数的线性性，式( 3 3 ) 等价于 z 圳( 五) = m i n c7 x + ；t r x s t a x b x z ： 和 1 2 ( 3 2 ) 第二章课余技能培训问题及模型 z 删( 旯) = m i n - 2 7y ) s 0 8 y d ( 3 5 ) y z 二 原整数线性规划问题松弛并且分解为式( 3 4 ) 和式( 3 5 ) 两个整数舰划问题它们每 一个选原整数舰划问题的一部分约束作为自己的约束，使得每一个问题的规模减少更 重要的是分解的目的寻求式( 3 4 ) 和式( 3 5 ) 的整数规划分解，并可以相对简单 的求解，这同l a g r a n g e 松弛的原理相同式( 3 4 ) 和式( 3 5 ) 称为整数规划问题的 l a g r a n g e 分解l a g r a n g e 分解是l a g r a n g e 松弛的一种特殊情况 l a g r a n g e 松弛算法可采用类似非线性规划的梯度次梯度优化算法，它有两个主 要步骤：第一步是确定一个兄及求解对应l a g r a n g e 松弛问题的最优解x ；第二步是当x 不是整数规划问题的可行解时，将其可行化m 1 系数修正法是l a g r a n g e 松弛启发式算 法1 7 1 的一种形式在给出后，类似次梯度优化算法，系统地调整l a g r a n g e 系数，而 修j 下的方法依赖于问题本身 3 1 提出问题 考虑如图3 1 所示的学生分阶段培训示意图 ， l 4 、一 第一阶段第二阶段第三阶段 第四阶段第五阶段第六阶段 图3 1 培训过程示意图 湖北人学硕十学何论文 图中共有7 个节点，即从节点1 到节点7 ，显然整个培训分为6 个阶段，每个阶段 针对一种素质进行培训而每个阶段，可能有多种方式( 如面授，短期培训，函授等) 完成培训比如第一阶段有3 种方式，第二阶段5 种方式，第六阶段2 种方式 而图3 1 中相邻节点之问每条连线上第1 个数字表示选择相应培训方式所需的时 问，第2 个数字表示选择该培训方式所需费用这罩完成整个培训过程所需最少时i 日j 和 最大时间分别为18 和3 0 若培训者希望完成整个培训过程所需时问不超过2 l 且具有最少的培训费用，该如 何在各阶段进行选择? 3 2 建立模型 设培训者所能接受的总的培训时间为t o ，若整个培训过程所需时间f t o = 2 1 ，那 么培训者才有可能参加该培训 对如上图3 1 所示的培训进程，设： i = 1 , 2 ，6 ； _ ，= 1 , 2 ，甩j( 以i = 3 ，疗2 = 5 ，以3 = 4 ，撑4 = 3 ，n 5 = 3 ，门6 = 2 ) 故引入记号： t 抒表示第i 阶段选择第种培训方式所需用的时间； 表示第i 阶段选择第歹种培训方式所需用的费用； 勤为决策变量，其取值嘞= 亿嚣段选择鳓种培训方式 而培训者在任何一个阶段都只能选择一种培训方式，所以必满足： m 嘞= 1 ( f - l ，2 ，6 ) ，譬l 6嘶 整个培训过程的时间为t = f i = 1 = l 则整个培训过程所需费用为 6嘶 c = c 驴 t = 1j = l 故满足要求的最小培训费用的培训方案可归结为如下模型( p ) ： 1 4 即： m l n m l n s j 6n i c 痨 i = l = l 6 怫 。痨2 1 i = l ，= l n = 1 = i 0 , 1 ) ( f = 1 , 2 ，6 ) ( i = 1 , 2 ，6 ；= 1 , 2 ，订j ) 1 o x i , + 1 3 x 1 2 + 1 4 x 1 3 + 1 1 x 2 i + 1 2 x 2 2 + 1 0 x 2 3 + 1 5 x 2 4 + 1 3 恐5 + 1 2 屯l + 0 9 b 2 + 1 2 x 3 3 + 1 1 x 3 4 + 1 0 x 4 l + 1 1 x 4 2 + 1 2 x 4 3 + 1 1 x 5 l + 1 1 x 5 2 + 1 2 x 5 3 + 1 2 x 6 i + 1 0 x 6 2 4 x i i + 6 西2 + 7 3 + 2 - 1 ：2 , + 3 x 2 2 + 6 x 2 3 + 3 x 2 4 + 4 x 2 5 + 6 x 3 i + 6 x 3 2 + 7 x 3 3 + 5 妇 + 4 矗l + 3 x 4 2 + 3 石4 3 + 3 石5 l + 2 工5 2 + 2 x 5 3 + 2 x 6 l + x 6 2 2 1 而i + 2 + 彳1 3 = 1 x 2 1 + 屹+ 砭3 + h + x 2 5 = 1 屯l + 屯2 + 工3 3 + h = 1 l + + = 1 墨l + 屯2 + x 5 32 1 x 6 l + x 6 2 21 x u 0 , 1 )o = 1 , 2 ，6 ；，= 1 , 2 ，仇) 3 3 求解模型 整数线性规划问题是n p 完全问题【1 8 1 而由文献 1 9 ，2 0 n - - 知：非线性整数规划问 题的求解则更为困难可以看出，该线性整数规划问题是典型的具有块对角化约束条件 的问题，故可利用分解的方法进行有效的求解 2 1 】 这里，将如上模型中的第一个约束条件通过 得到原模型的l a g r a n g e 松弛问题模型( p 。) 如下： m l n l a g r a n g e 松弛放到目标函数中，从而 o月i 6 月。 c 勤+ 五( 芝勺x u - 2 0 f = l ，= li = 1y = l 1 5 湖北人学硕十学位论文 - - _ - i l - - _ - _ l - - _ - _ l _ - - i _ _ _ _ _ _ _ i _ _ _ _ _ _ _ _ - - - _ l l _ l _ _ i - l _ l _ - _ - _ 一 这j 批松弛问题( p 。) 比原问题( p ) 易求解 即： ( i = 1 , 2 ，6 ) ( i = 1 , 2 ，6 ；= 1 , 2 ，玎，) 具体地，该松弛i u j 题可分解为如下6 个独立的子问题： m l n m l n m m ，l i c l j 而j j = l ( j = 1 , 2 ，n 1 ) 艺+ 五n 2 嘞 j = t j = t ( j = 1 , 2 ，万2 ) ( j = l ，2 ，刀6 ) r a i n 1 0 x l l + 1 3 x 1 2 + 1 4 x 1 3 + 2 ( 4 x l l + 6 x 1 2 + 7 x 1 3 ) m l n m l n 1 d = 瓯 吩芦为 ，【 = q 一川 1 b = q ，t f 也闩嘞 6 x ， 6 f 爿 力+ 6 x 6 c 脚 l 玲 = q，- t k 岸嘞 第= 章课余技能培训问题及模型 m i n 1 0 x 4 l + 1 1 x 4 2 + 1 2 2 4 3 + 3 ( 4 x 4 i + 3 x 4 2 + 3 x 4 3 ) ix 4 l + 工4 2 + x 4 32 1 【x 4 = o x l ( = 1 ，2 ，3 ) m i n 1 1 x 5 l + 1 1 x 5 2 + 1 2 x 5 3 + 2 ( 3 x 5 l + 2 j 5 2 + 2 x s 3 ) lx 5 l + x 5 2 + x 5 3 2 1 【石5 ，= o 或l ( = 1 , 2 ，3 ) m i n1 2 x 6 l + 1 0 x 6 2 + 2 ( 2 x 6 l + 3 x 6 2 ) lx 6 l + x 6 25 1 【x 6 ，= 0 9 _ 戈1 ( = l ，2 ) 如上6 个子问题是极易求解的，并且可以并行计算其步骤为： 第一步：给定初始的l a g r a n g e 乘子，= 0 ： 第二步：求解6 个子问题得到解i ， 得到最优解工= # ，停止计算；否则转入下一步 ( 3 9 ) ( 3 一l o ) ( 3 - 1 1 ) 如满足则 第三步：调整l a g r a n g e 乘子名。令矿1 = 2 ，= l + 1 ，转到第二步这里，调整 l a g r a n g e 乘子采用次梯度法 2 2 , 2 3 具体计算如下： 1 ) 取力= 0 0 1 ，求解6 个子问题得到最优解： 式= 1 , 0 ，0 ，0 ，0 ，1 ，0 ，0 ，0 ，1 ，0 ，0 ，1 ，0 ，0 ，0 ，1 ，0 ，0 ，1 ) ， 6风 验证白嘞= 2 5 _ ，o = 2 1 ； i = 1 = l 2 ) 取力= 2 岔= 0 0 2 ，求解6 个子问题得到最优解： i = 1 , 0 ，0 ，0 ，0 ，1 ，0 ，0 ，0 ，1 ，0 ，0 ，1 ，0 ，0 ，0 ，1 ，0 ，0 ，1 ) ， 6 仇 验证o = 2 5 ：, - t 。= 2 1 ； = 1 = i 3 ) 取矛= 2 3 , t = 0 0 4 ，求解6 个子问题得到最优解： 蔓= 1 , 0 ，0 ，1 ，0 ，0 ，0 ，0 ，0 ，1 ，0 , 0 ，1 ，0 ，0 ，0 ，1 ，0 ，0 ，1 ) ， 1 7 2 一 b勺 一闩 。硝 足满否是 征 验并 湖北人学硕十学何论文 6 n 。 验证勺x o = 2 1 = t 。 i = 1j = l 故得到最优解z = 1 , 0 ，0 ，1 ，0 , 0 , 0 ，0 ，0 ，1 ，0 , 0 ，1 ，0 , 0 , 0 ，1 ，0 ，0 ，1 ) ，此时f 标函数值为6 1 3 4 分析模型 这罩针对学生参加课外技能培训问题，建立了一个有时问约束条件下的最小培训 费朋的整数规划模型，并利刷基于l a g r a n g e 松弛的分解算法进行了求解，这种算法降 低了原问题的求解难度，将一个大规模问题进行分解进而转化为小规模问题进行计 算根据这种分解算法得到了最优培训方案，这对于现存类似繁多的各种技能培训过程 中的优选均具有一定的指导意义 1 8 参考文献 参考文献 1 胡运权运筹学教程 m 】北京：清华大学出版社，2 0 0 3 ，5 ：1 2 9 1 3 0 2 】钱颂迪运筹学 m 北京：清华大学出版社，1 9 9 0 ：116 11 6 3 o s m a nhi m e t a h e u r i s t i c s ：ab i b l i o g r a p h y j a n n a l so fo p e r a t i o n sr e s e a r c h ，19 9 6 ，6 3 ： 5 1 3 6 2 3 4 g u t j a h rw j ag r a p h b a s e da n t s y s t e ma n di t sc o n v e r g e n c e j f u t u r eg e n e r a t i o n c o m p u t i n gs y s t e m s ，2 0 0 0 ，16 ：8 7 3 8 8 8 5 x i ej ，x i n gw i n c o r p o r a t i n gd o m a i n s p e c i f i ck n o w l e d g ei n t oe v o l u t i o n a r ya l g o r i t h m s j b e i j i n gm a t h e m a t i c s ，1 9 9 8 ，4 ：1 3 1 - 1 3 9 【6 k h a c h i a nlgap o l y n o m i a la l g o r i t h mf o rl i n e a rp r o g r a m m i n g j d o k l a d ya k a d n a u k u s s r ，19 7 9 ，2 4 4 ( 5 ) ：10 9 3 - 10 9 6 【7 】加罩mr ，约翰逊ds 计算机和难解性：n p c 性理论导论 m 】张立昂北京：科 学出版社，1 9 8 7 ：3 5 7 3 5 9 8 c o o ksa t h ec o m p l e x i t yo ft h e o r e mp r o v i n gp r o c e d u r e s j p r o c3 r da c m s y r u po nt h e t h e o r y o f c o m p u t i n g a c m ，1 9 7 1 ：1 5 1 - 1 5 8 【9 w ub a ni n t r o d u c t i o nt on e u r a ln e t w o r k sa n dt h e i ra p p l i c a t i o n si nm a n u f a c t u r i n g j j o u r n a lo f i n t e l l i g e n tm a n u f a c t u r i n g , 1 9 9 2 ，3 ：3 9 1 - 4 0 2 1 0 】雍龙泉基于整数规划的选课模型 j 】伊犁师范学院学报，2 0 0 6 ，9 ( 3 ) ：1 2 8 1 3 0 【1 1 谢金星，薛毅优化建模与l i n d o l i n g o 软件【m 】北京：清华大学出版社，2 0 0 5 ，7 ： 2 5 3 2 1 2 】姜启源数学模型【m