基于点截集的围堵嫌犯模型

研究了在突发事件中交巡警对在逃嫌犯的围堵问题, 该问题为2011年全国大学生数学建模竞赛B题的一部分。接到报警后,交巡警服务平台的警力需要指派到路网路口以堵截嫌犯。将该问题转化为阻止嫌犯逃到特定点集的问题;并分析了怎样判断被选为围堵点的点集对一个指定点形成包围的问题。推广了点截集的概念,给出了判断点集是否为点截集和紧点截集的优化模型。然后将判断是否为点截集的模型转换为约束集合, 用于建立围堵嫌犯模型,以四个不同的优化标准分别建立了围堵问题的0-1整数规划模型。并给出了部分模型的Lingo算例。     

交巡警平台设置与调度模型

设置交巡警平台需要考虑各平台工作量的均衡性以及最长出警时间不能超过3min这两个方面,可利用0-1整数规划,建立平台管辖区域划分模型。发生突发事件时,交巡警平台的警力需要被调度到指定的路口执行任务,最快到达指定路口并且总调度距离最短的方案,即为最佳调度方案,运用0-1规划可以解决这类指派问题。在犯罪嫌疑人从P逃跑3min后,为尽快抓捕逃犯,以点P为中心,从不可封锁点向外逐步延伸,在平台警力能成功封锁的前提下形成最小围堵圈,再利用平台警力调度模型,最终设计出了最佳围堵方案。     

《实用数学建模》介绍

设置交巡警平台需要考虑各平台工作量的均衡性以及最长出警时间不能超过3min这两个方面,可利用0-1整数规划,建立平台管辖区域划分模型。发生突发事件时,交巡警平台的警力需要被调度到指定的路口执行任务,最快到达指定路口并且总调度距离最短的方案,即为最佳调度方案,运用0-1规划可以解决这类指派问题。在犯罪嫌疑人从P逃跑3min后,为尽快抓捕逃犯,以点P为中心,从不可封锁点向外逐步延伸,在平台警力能成功封锁的前提下形成最小围堵圈,再利用平台警力调度模型,最终设计出了最佳围堵方案。     

模糊环境下动态供应商选择的混合整数非线性规划模型

基于供应商选择问题的动态性和模糊性,考虑在每个周期内生产商的需求能力及供应商的供应能力为模糊变量,本文将一个多阶段多商品多渠道的供应商选择问题视为一个0-1混合整数模糊动态非线性规划问题,目标函数为总成本最小化。然后建立了0-1混合整数模糊动态非线性规划模型。为了求解该模型,通过可信性理论把模型中模糊机会约束清晰化,将该模型转化为一个确定型的0-1混合整数动态非线性规划模型。最后给出了一个数值算例验证了模型的可行性。     

对带有盒约束的二次整数规划的一种线性化方法

本文主要讨论了二次整数规划问题的线性化方法.在目标函数为二次函数的情况下,我们讨论了带有二次约束的整数规划问题的线性化方法,并将文献中对二次0-1问题的研究拓展为对带有盒约束的二次整数规划问题的研究.最终将带有盒约束的二次整数规划问题转化为线性混合本文主要讨论了二次整数规划问题的线性化方法.在目标函数为二次函数的情况下,我们讨论了带有二次约束的整数规划问题的线性化方法,并将文献中对二次0-1问题的研究拓展为对带有盒约束的二次整数规划问题的研究.最终将带有盒约束的二次整数规划问题转化为线性混合0-1整数规划问题,然后利用Ilog-cplex或Excel软件中的规划求解工具进行求解,从而解决原二次整数规划.     

N车探险问题的一种ε-近似度的近似算法

本文探讨了一类N车探险问题的近似算法,首先通过建模将N车问题转变为一个等价的非线性0-1混合整数规划问题,进而将该非线性0-1混合整数规划问题转化为一个一般的带约束非线性规划问题,并用罚函数的方法将得到的带约束非线性规划问题化为相应的无约束问题.我们证明了可通过求解该无约束非线性规划问题得到原N车问题的ε-近似度的近似解,并设计了-个收敛速度为二阶的迭代箅法,文章最后给出算法实例.     

考虑乘客时间成本与换乘感受的中转航班登机口分配问题研究

针对2018年"华为杯"第十五届中国研究生数学建模竞赛F题展开研究对考虑乘客时间成本与换乘感受的中转航班登机口分配调度问题(Airport Gate Assignment Problem,AGAP)进行研究,建立了多目标0-1整数线性规划的中转航班登机口分配模型.根据不同的实际应用条件,对该模型进行相应改进,并使用Lingo求解,得出在最大化航班分配数量的基础上,最小化乘客换乘成本,同时尽量减少登机口使用数量的最优中转航班登机口分配方案,最后对分配结果进行分析.模型亮点在于:1)创新性地引入了乘客换乘成本惩罚因子,令模型对实际问题考虑更加全面.2)模型在时间离散化的基础上,将航班间隔时间纳入航班占用时间,建立了0-1整数线性规划模型求最优解,求解结果更加可靠.3)模型通过线性加权的方法,将多目标规划问题简化为单目标问题进行建模.     

0-1非线性混合整数规划的罚函数解法

本文中我们对一类0-1非线性混合整数规划的解法进行了探讨,通过罚函数把有约束问题化为相应的无约束问题,我们证明了可通过求解一个无约束非线性规划问题得到原问题的ε近似极小解,数值试验表明算法是有效的.     

整数规划新进展

整数规划是对全部或部分决策变量为整数的最优化问题的模型、算法及应用等的研究, 是运筹学和管理科学中应用最广泛的优化模型之一. 首先简要回顾整数规划的历史和发展进程, 概述线性和非线性整数规划的一些经典方法. 然后着重讨论整数规划若干新进展, 包括0-1二次规划的半定规划~(SDP)~松弛和随机化方法, 带半连续变量和稀疏约束的优化问题的整数规划模型和方法, 以及0-1二次规划的协正锥规划表示和协正锥的层级半定规划~(SDP)~逼近. 最后, 对整数规划未来研究方向进行展望并对一些公开问题进行讨论.     

封锁嫌疑犯的数学建模方法

本文是对《数学建模及其应用》第一期“问题征解”的题目的一个解答。利用一对一的匹配模型建立了交巡警平台围堵嫌疑犯的基本模型,而对于何时完成有效的围堵,可以通过逐次逼近的方法解决。利用所设计的模型和给出的算法,得到了该问题的最优解。最后给出在具体假设下的一个优化围堵方案。     

最小封堵圈的扩张算法设计

在发生突发事件之后,及时制定有效的封堵方案才能掌握抓捕嫌疑犯的主动权.提出了对逃跑罪犯实施完全封堵的最小包围圈的计算机算法,通过规则图形的仿真演示,验证了该算法的正确性.最后以某市案发时候的警力分布和交通图作为实例,模拟了对嫌疑犯实施封堵时计算最小包围圈的最优方案.结果证明该算法具有简洁、可靠的优点.     

Linear,Integer, Separable and Fuzzy Programming Problems: A Unified Approach towards Reformulation

For mathematical programming (MP) to have greater impact as a decision tool, MP software systems must offer suitable support in terms of model communication and modelling techniques. In this paper, modelling techniques that allow logical restrictions to be modelled in integer programming terms are described, and their implications discussed. In addition, it is illustrated that many classes of non-linearities which are not variable separable may be, after suitable algebraic manipulation, put in a variable separable form. The methods of reformulating the fuzzy linear programming problem as a max-min problem is also introduced. It is shown that analysis of bounds plays a key role in the following four important contexts: model reduction, reformulation of logical restrictions as 0-1 mixed integer programmes, reformulation of non-linear programmes as variable separable programmes and reformulation of fuzzy linear programmes. It is observed that, as well as incorporating an interface between the modeller and the optimizer, there is a need to make available to the modeller software facilities which support the model reformulation techniques described here.     

Examining Optimal Criterion Weights in Mixed Integer Programming Approaches to the Multiple-group Classification Problem

Several mixed integer programming approaches to the multiple-group statistical classification problem are examined. Many papers have investigated conditions under which a degenerate solution occurs in linear programming approaches to the two-group discriminant problem. Very little research has been conducted in the multiple-group case. We investigate conditions under which a degenerate solution can occur in mixed integer programming approaches to the multiple-group classification problem. A multiple-group ‘minimize the sum of deviations’ model is presented. This model is similar in structure to the general single function classification model. Also, a two-goal approach to the multiple-group classification problem is discussed.     

A Reference Direction Algorithm for Solving Multiple Objective Integer Linear Programming Problems

In this paper, we propose a reference direction approach and an interactive algorithm to solve the general multiple objective integer linear programming problem. At each iteration, only one mixed integer linear programming problem is solved to find an (weak) efficient solution. Each intermediate solution is integer. The decision maker has to provide only the reference point at each iteration. No special software is required to implement the proposed algorithm. The algorithm is illustrated with an example.     

Extending Dantzig's bound to the bounded multiple-class binary Knapsack problem

 The bounded multiple-class binary knapsack problem is a variant of the knapsack problem where the items are partitioned into classes and the item weights in each class are a multiple of a class weight. Thus, each item has an associated multiplicity. The constraints consists of an upper bound on the total item weight that can be selected and upper bounds on the total multiplicity of items that can be selected in each class. The objective is to maximize the sum of the profits associated with the selected items. This problem arises as a sub-problem in a column generation approach to the cutting stock problem. A special case of this model, where item profits are restricted to be multiples of a class profit, corresponds to the problem obtained by transforming an integer knapsack problem into a 0-1 form. However, the transformation proposed here does not involve a duplication of solutions as the standard transformation typically does. The paper shows that the LP-relaxation of this model can be solved by a greedy algorithm in linear time, a result that extends those of Dantzig (1957) and Balas and Zemel (1980) for the 0-1 knapsack problem. Hence, one can derive exact algorithms for the multi-class binary knapsack problem by adapting existing algorithms for the 0-1 knapsack problem. Computational results are reported that compare solving a bounded integer knapsack problem by transforming it into a standard binary knapsack problem versus using the multiple-class model as a 0-1 form. Received: May 1998 / Accepted: February 2002-09-04 Published online: December 9, 2002 Key Words. Knapsack problem – integer programming – linear programming relaxation     

New convergent heuristics for 0–1 mixed integer programming

Several hybrid methods have recently been proposed for solving 0–1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0–1 multidimensional Knapsack problem. Other encouraging results obtained for 0–1 MIP problems are also presented.