递归回溯法求解整数线性规划及MATLAB实现

基于递归回溯法解决整数线性规划问题的算法思想及求解过程,使用MATLAB软件编写通用程序,实现了求解整数线性规划问题.通过MATLAB中的文件存储功能,对符合要求的整数解可存储在文件中,并舍弃从该解出发的分支,从而得到了符合要求的所有整数解和最优整数解.实验结果表明,该算法达到了局部最优.     

一类线性规划问题的强多项式算法

对一类线性规划问题提出了一个强多项式算法．此算法可进行双向搜索．可行解集、目标函数的两个目标值以及相应的最优解，全部可行基与最优基可以一步求得，无需迭代．算法的复杂性为Ｏ（ｎ３＋ｎ２＋ｎ），其中ｎ为线性规划问题变量的个数     

求解混合整数双层规划的凸组合算法

利用罚函数思想和最优值函数的概念将混合整数双层规划转化为连续变量的单层非线性规划,然后用事先确定步长的凸组合算法迭代求解此单层非线性规划,进而得到原双层规划的局部最优解.     

一类线性规划问题的强多基式算法

对一类线性规划问题提出了一个强多项算法，此算法可进行双向搜索，可行解集，目标函数的两个目标值以有相就的最优解，全部可行基与最优基可以一步求得，无需迭代，算法的复杂性为Ｏ（ｎ＾２＋ｎ＾２＋ｎ），其中ｎ为线性规划问题变量的个数。     

求解混合整数线性规划的降维搜索法

很多实际问题归结为解如下线性规划max C~TX AX=b (1) {X≥0 其中X=(x_1,…x_L,x_(L 1),…x_n)~T的x_1…x_L 为整数。降维搜索法求解这个问题,首先是从(1)的约束中除掉x_1…x_L为整数的要求,求出线性规划的最优解。此解若不为整数解,则从解的分量x_1开始取整,即令x_1=[x_1~(0)] 代入约束,在n-1维空间上求最优解。如果仍不是整数解,则继续在n-1维最优解中令分量x_2取整,求n-2维空间的最优解。若降维至n-r得一整数解,则依定理1,停止继续降维。此时的整数解为(1)的可行解。然后在此可行解的基础上在x的两边进行左右搜索,用新的更优的可行整数解代替原有的可行整数解。用定理(2)和(3)判别是否停止搜索,搜索完毕便得n-r 1维(1≤r≤L)的一个最优整数解。然后求出所有n-r 1维的最优整数解,比较所有n-r 1维的最优解,得n-r 2维的一个最优整数解,如此类推,一定可求得原问题(1)的最优整数解。降维搜索法可以完全平行地推广到求非线性规划的整数解。     

非退化混合整数线性规划的一种解法

本文引进关于点x的邻近整标点x~的概念,利用割面集x=x~分支,证明非退化的混合整数线性规划的解必在割面集上取得,从而把非退化混合整数线性规划的求解化为有限个线性规划的求解,只要比较这些解的目标函数值,就能获得非退化混合整数线性规划的全部解,或化为混合0—1线性规划求解。     

线性规划中两阶段法的简便计算法

在线性规划问题中引入人工变量,把问题变为约束方程组的系数矩阵中含有单位矩阵,用以作为人造基,然后按单纯形方法进行换基迭代,求得最优解或判定无最优解.本文给出了线性规划问题两阶段法的简便计算方法,即根据所给问题尽可能少的引入人工变量,以使线性规划问题的计算变得更加简单.     

覆盖对策模型的均衡性

研究了覆盖合作对策模型的均衡性。基于线性规划对偶理论，证明了覆盖对策均衡性的等价条件：覆盖对策是均衡的当且仅当其对应线性规划松弛有整数最优解，并且此时核心就是对偶规划的最优解集。     

基于整数规划的投资项目选择模型及Matlab实现

介绍了用Matlab优化工具箱中的intlinprog函数求解整数线性规划问题,并用投资项目的选择问题进行仿真,能快速方便的得到最优解.     

一类混合整数双层线性规划的枚举法

通过对上层变量为0-1型变量和下层变量为连续型变量的混合整数双层线性规划问题的,根据分支定界法原理,给出了一种定界函数和寻找问题最优解的搜索准则,由此提出了一个求解混合整数双层线性规划问题的有效枚举方法。提出的算法能求得问题的全局最优解,并通过算例说明了算法的求解过程。     

目标等值面切割定界与割平面法结合求解整数规划

把目标等值面切割定界原理与Gomory的割平面法结合起来求解整数线性规划(ILP)问题．首先通过目标函数等值面的平行移动来切去(LP)可行域中含其非整数最优解但不含(ILP)可行解的“无用部分”;然后,应用Gomory的割平面在通过(ILP)最优解的目标等值面上切割其最优解。     

基于线性规划逆优化模型的供应链资源优化配置支持系统研究

为帮助供应链合理组织企业资源,快速有效响应市场需求,设计开发了一个基于线性规划逆优化模型的供应链资源优化配置支持系统。系统内置的供应链资源优化配置线性规划逆优化模型的快速建模和求解模块以及专家决策支持模块,实现了面向市场的供应链资源快速优化配置,在实际应用中提供的生产计划调度和业务改进建议,有效缩短了供应链响应市场的周期,降低了成本。     

背包问题的若干性质及问题的简化

对单约束线性整数规划（ILP,背包问题）的特性进行了分析,通过剪去无效变量对问题进行简化,并给出了问题的一个上界及最优值判定条件。     

波长路由多纤环网的优化设计

在给出波长路由环网模型的基础上,提出了一种新的整数线性规划公式以解决波长路由多纤环网（MFR）的优化设计问题,整数线性规划公式所采用的优化目标是最小结点端口数目,以此为优化目标可以保证所设计的多纤环网具有最大的经济性,利用所提出的整数线性规划公式,定量分析了在不同通信模式（单Hub和双Hub),及路由方案（波长通道和虚波长通道）的情况下,单向和双向波长路由多纤环网的网络性能差异,所获得的结论有助于多纤环网结构的优化设计。     

基于主动网络的最佳缓存位置计算

主动网络是一种新型的智能性网络,其中的任何一个主动节点都可以用于放置缓存。基于主动网络,通过使用ILP算法,解决了在哪个节点中进行缓存为最佳的问题,从而使整个网络缓存系统的花费较小、效率较高。并使用ANTS对这个算法进行了模拟实现。     

多目标分层规划问题的最优均衡宽容值序列算法

对多目标分层规划问题的宽容完全分层序列算法做改进，寻求各层次多目标子问题的最优均衡值和最优均衡解，针对上级优先层次对下级层次的宽容值，求出所有层次按优先级顺序的最优均衡解；给出多目标分层规划问题的最优均衡宽容完全分层序列算法，得到在一定宽容限下所有层     

利用ILP分子标记分析籼粳杂交水稻的遗传多样性

采用ILP标记分析了福建地区20个亲本和30个育成品系构建的水稻籼粳亚种间杂交育种系谱的遗传多样性,并对结果进行聚类分析。结果表明,ILP标记可明显区分供试材料的籼粳特征。基于ILP标记聚类结果,以相似系数0.67为阈值,将该育种系谱划分成3个类群,即籼稻型、中间型和粳稻型。     

基于整数线性规划的MPSoC通信优化策略

摘要： 针对多处理器片上系统 (Multiprocessor System on chip,MPSoC) 的通信优化技术--通信流水线和消息聚合,其过度使用可能会导致系统同步开销上升从而带来整体系统性能降低的问题,提出了基于整数线性规划(Integer Linear Programming, ILP)的优化策略.该策略以综合优化系统通信和同步开销为目标,通过对通信流水线技术和消息聚合技术的合理规划,使系统性能达到最优.实验结果表明,基于ILP的通信优化策略能够充分发挥通信优化技术的优点,使系统性能显著提升.
关键词： 通信优化; 整数线性规划; Simulink
中图分类号： TP 31文献标志码： A     

装卸工人调配问题新解法及其证明

阐述了现代物流技术中装卸工人调配问题、装卸工问题、限制情况下装卸工问题及其数学模型,证明了装卸工人调配问题与限制情况下装卸工问题的数学模型是等价的.通过分析装卸工人调配问题的数学性质得出该问题的一种新解法并给出其证明.新解法给出了该问题的所有最优解.