任务分配问题的建模与求解

建立了极大极小任务分配问题的混合整数线性规划模型,提出一种矩阵作业解答,并与穷举解及混合整数线性规划解的计算复杂度进行了比较.理论分析和数值试验表明矩阵作业法对两类任务分配问题,极大极小和总体极小任务分配问题,有效地提供最优解.     

基于遗传算法的检测路段选择的优化

在分析交通检测点分布优化问题的现有算法的基础上，本文构造了交通检测点优化问 题的染色体表达式，建立了此问题的遗传算法．这是第一次将遗传算法应用于交通检测点分 布优化问题．实验结果表明，此算法可以有效求得交通检测点分布问题的优化解或近似优化 解，是求解交通检测点分布问题的一个较好的方法．     

求不相交QoS路由的一种整数线性规划方法

提出求解不相交QoS路由问题的一种整数线性规划方法.首先,利用一个0-1变量集合来表示不相交路由和路由的QoS需求;然后,通过拉格朗日乘子将集合中的复杂约束引入所导出的整数线性规划问题的目标函数中.因为约束系数矩阵是全幺模矩阵,所以这类整数线性规划问题能用单纯形法容易地求解,从而可在求解线性规划问题的迭代过程中求出不相交QoS路由.数值实验结果表明了所提出方法的有效性.     

Excel在经济数学模型中的应用

本文给出了用Ｅｘｃｅｌ求解矩阵问题，投入产出模型问题，多元线性回归问题线性规划问题的求解方法。     

一类直觉模糊线性规划的求解及其应用

研究一类直觉模糊线性规划及其应用.首先,定义直觉模糊不等式,给出直觉模糊线性规划模型;然后,提出一种基于总精确函数的直觉模糊线性规划求解方法,并给出其求解步骤;最后,建立证劵投资组合的直觉模糊线性规划模型.数值算例表明了所提出理论是合理有效的.     

三角模糊数互补判断矩阵排序的最小方差法

研究偏好信息为三角模糊数互补判断矩阵形式给出的方案排序方法.根据三角模糊数互补判断矩阵完全一致性的概念,建立了一个基于最小方差的非线性规划模型.通过求解该模型,得到三角模糊数互补判断矩阵的权重向量,并利用三角模糊数排序公式对决策方案进行排序.最后通过算例分析表明了所提出的方法是可行而有效的.     

赋权图匹配问题的一种新的松弛模型

图匹配是一个NP难(NP-hard)问题. 基于置换矩阵是非负正交矩阵这一经典结论, 提出赋权图匹配(Weighted graph matching, WGM)的双向松弛障碍规划, 理论上证明新模型的解与原模型的解是一致的. 该规划是一个二元连续规划, 它是正交矩阵上的线性优化问题, 同时也是非负矩阵上的凸二次优化问题. 故设计求解新模型的交替迭代算法, 并证明算法的局部收敛性. 数值实验表明, 在匹配精度方面, 新方法强于线性规划方法和特征值分解方法.     

线性规划问题的解法(上)

1.引言本文简短地讨论线性规划问题的主要性质及其最通用的算法:单纯形方法及对偶单纯形方法。这里给出解线性规划问题的这两种算法的证明和叙述,着重在计算工作中出现的一些细节问题。特别是关于保留变量置换过程的迹象的问题,我们利用矩阵来明显处理,这些矩阵     

原油选择优化模型在企业中的应用

本文论述了用于炼油工业的原油选择优化模型评价系统。精确企业模型建立是原油选择优化的基础,描述了企业模型的框架结构,并详细阐述了工艺流程模型、能耗模型、硫分布模型等建立精确企业模型所需要的内容。线性规划是求解大型优化命题的有力工具,文中论述了线性规划的特点及意义。在分析原油选择优化命题特点的基础上,利用成熟的线性规划软件和原油数据库、工艺模型、油品调合等技术建立企业模型系统,准确描述炼油工业中的物流传递、能量传递和性质传递。所建立的模型系统以经济目标为导向,结合国家环保政策法规要求,新工艺发展,为企业制定合理的原油优化选择提供定量的解决方案。应用案例结果证明利用线性规划和建立企业模型能有效解决原油优化选择问题。     

求解无线传感器网络定位问题的线性规划算法

传感器节点的定位问题是无线传感器网络中的基础性问题之一.提出了一种线性规划算法用于求解无线传感器网络定位问题.该算法利用RSSI值和经验的无线信号传播模型推导出所有可通信节点间距离的相对关系,利用节点的通信半径估算出可通信节点间的距离,并以此为约束条件利用矩形近似圆形,将二次约束的规划问题转化为线性规划问题;求解该线性规划问题便可得未知节点坐标.通过仿真实验,证明了当锚节点分布在网络边缘时该算法能得到较好的定位效果,分析了锚节点分布、锚节点个数、网络连通度等实验参数对定位结果的影响.相比凸规划定位算法,该算法大大降低了求解规划问题的次数,且在相同的实验条件下定位误差更小.     

Models and algorithms for the screen line-based traffic-counting location problems

We consider an overlooked, but important, practical problem about the optimal selection of cordon–screen lines for traffic census study in road networks. The problem can be stated as: (1) how to select the optimal locations of a given number of counting stations to separate as many origin–destination (O–D) pairs as possible, (2) how to determine the minimum number of counting stations and their locations required for separating all O–D pairs. Here, an O–D pair is said to be separated if trips between this O–D pair are entirely intercepted by the current traffic-counting stations. The problems of interest are formulated as integer linear-programming models. After exploring the relaxed linear-programming problems and their dual problems, a solution scheme that combines a shortest path-based column generation procedure and a branch-and-bound technique is developed to find an optimal counting location solution. The proposed models and algorithms are illustrated with numerical examples and compared with the genetic algorithm.     

HubLocator: an exact solution method for the multiple allocation hub location problem

HubLocator is a new branch-and-bound procedure for the uncapacitated multiple allocation hub location problem. An existing optimal method developed by Klincewicz (Location Sci. 4 (1996) 173) is based on dual ascent and dual adjustment techniques applied to a disaggregated model formulation. These techniques have already successfully been used to solve the closely related simple plant location problem. However, due to the specific structure of the problem at hand, the success of these techniques in reducing the computational effort is rather restricted. Therefore, HubLocator additionally considers an aggregated model formulation enabling us to significantly tighten the lower bounds. Upper bounds which satisfy complementary slackness conditions for some constraints are constructed and improved by means of a simple heuristic procedure. Computational experiments demonstrate that optimal solutions for problems with up to 40 nodes can be found in a reasonable amount of time.Scope and purposeGround and air transportation networks, postal delivery networks, and computer networks are often configured as hub-and-spoke systems. Traffic between two locations is not transported directly between these locations, but routed via particular switching or consolidation points called hubs. Due to increased traffic on linkages between hubs, larger vehicles can be used or the capacity of existing vehicles can be utilized more efficiently, resulting in smaller per unit transportation costs. The exploitation of scale economies as a result of the reduced number of linkages, which have to be operated in a hub-and-spoke system, compared to a fully interconnected network is an important advantage of this type of system.Designing hub-and-spoke networks deals with the selection of hubs from a given set of potential locations and the routing of traffic. We consider a special type of such a hub location problem and adapt a successful technique developed to find an optimal solution for the well-known simple plant location problem.     

The Capacitated p-facility Location Problem on the Real Line

The problem we address involves locating p new facilities to service a set of customers or fixed points on the real line such that a measure of total cost will be minimized. A basic form of this problem was investigated by Love (1976), who observed that the fixed points must be allocated in sequence to the new facilities in an optimal solution, and thus, the problem can be solved by a dynamic programming algorithm. Since then, other forms of the model have been investigated; however, in all cases it is assumed that the new facilities have unlimited capacity so that customer flows are always allocated to the nearest facility. The objective of this paper is to analyze the effect of capacity constraints on the optimal locations of the new facilities. A general fixed-cost function is also included to account for practical considerations such as zoning regulations, and to permit the facilities to be located anywhere on the line instead of only at the fixed vertices. A dynamic programming method is formulated to solve the problem when the variable cost components are increasing convex functions of travel distance. The problem is shown to be NP-hard under more general cost structures.     

Perturbation strategies for optimal traffic reassignment

Suboptimal static traffic reassignment strategies are developed following a traffic perturbation due to an incident or change in flow in a large freeway corridor network. The basic technique is perturbation analysis using a quadratic approximation to the cost of traversing the roadway links. A dynamic programming approach, using the subnetwork number as the stage variable, leads to an optimization problem which is a variant of the linear-quadratic optimal control problem. Explicit relationships between decay of perturbations, controllability, and lateral access in the network are obtained. The perturbation strategies are useful because they can be used 1) to isolate the subset of the network that needs to be reoptimized by nonlinear programming, or 2) as a real-time quasistatic traffic reassignment algorithm; in either case computational requirements are reduced.     

Probability based dynamic-alternate routing and the corresponding converter placement algorithm in all-optical WDM networks

This paper proposes a new dynamic-alternate routing algorithm and its corresponding converter placement algorithm in order to reduce the connection blocking probability for all-optical WDM networks. The main idea in the proposed dynamic-alternate routing algorithm is to try to route the traffics according to a predefined optimal probability distribution. The problem for finding the optimal probability distribution was shown as a convex optimization problem. The problem can be solved by flow deviation method or other standard optimization techniques. Simulation results show that the proposed routing algorithm yields lower connection blocking probabilities than the previous works. The proposed routing algorithm produces similar traffic pattern as the optimal traffic pattern. The similarity between the traffic pattern produced by the proposed dynamic-alternate routing algorithm and the optimal traffic pattern can be further employed for solving other network designing problems such as converter placement problem. Since the optimal traffic pattern can be easily predicted, the optimal traffic pattern which minimizes the blocked traffic intensity is utilized for finding the locations of wavelength converters. The key idea is to place the wavelength converters at the nodes where they are needed most. Simulations have been performed to study the performance of the proposed wavelength converter placement method. The simulation results have shown that the proposed placement method combined with the proposed probability based dynamic-alternate routing algorithm yields smaller connection blocking probability than the two converter placement methods with their corresponding alternate routing algorithms.     

Time-dependent green Weber problem

We consider an extension of the classical Weber problem, named as the green Weber problem (GWP), in which the customers have one-sided time windows. The GWP decides on the location of the single facility in the plane and the speeds of the vehicles serving the customers from the facility within the one-sided time windows so as to minimize the total amount of carbon dioxide emitted in the whole distribution system. We also introduce time-dependent congestion which limits the vehicle speeds in different time periods and call the resulting problem as the time-dependent green Weber problem (TD-GWP). In the TD-GWP, the vehicles are allowed to wait during more congested time periods. We formulate the GWP and TD-GWP as second order cone programming problems both of which can be efficiently solved to optimality. We show that if the traffic congestion is non-increasing, then there exists an optimal solution in which the vehicles do not wait at all. Computational results are provided comparing the locations of the facility and the resulting carbon dioxide emissions of the classical Weber problem with those of the GWP and comparing the GWP with the TD-GWP in terms of carbon dioxide emissions in different traffic congestion patterns.     

一类带延迟策略的库存优化模型及其仿真

考虑一类带延迟策略的库存优化模型, 即二层整数规划问题。证明了该二层整数规划问题等价于约束单层整数规划问题。借助罚函数思想化约束整数规划问题为无约束整数规划问题, 再利用遗传算法进行求解。数值模拟表明所得数值结果与已有的数值结果相比,不仅使得供应链整体库存效益有较大提高, 并且对每个库存分点的最优库存量作了更为合理的调整。     

Spare capacity provisioning for quasi-static traffic

Resource provisioning has for long been an important area of research in network design. The traffic grooming problem in optical networks is a design problem of aggregating sub-wavelength traffic demands onto lightpaths and lightpaths onto fiber links such that the required electronic switching capability, hence network cost, can be minimized. Because of the reconfiguration cost in optical grooming networks, a reactive resource provisioning approach may become inefficient, and result in revenue loss. In this paper, we propose an over-provisioning scheme, which pre-allocates the spare capacity of lightpaths to dynamic sub-wavelength traffic demands such that the network can be more agile in responding to traffic increment requests. For the single-link case, we formulate the problem as a non-linear programming problem, and for under reasonable assumptions, we prove the objective function is convex. We provide an exact algorithm to find the optimal solution. The problem with general topologies is then studied. We prove the NP-hardness in this case, and propose heuristics. Numerical results show our heuristics perform well.     

Joint optimization for area traffic control and network flow

A joint optimization problem for solving area traffic control and network flow is investigated. A bilevel programming is used to formulate this joint optimization problem where the network flow following Wardrop's principles can be obtained by solving traffic assignment problems. In this paper, we present a solution approach for jointly optimizing the area traffic control and network flow on the basis of a newly presented algorithm for concurrent flow (Comput. Oper. Res. (2004) in press). We propose three kinds of formulations for this joint optimization problem and present a gradient-based method to effectively solve this problem via a mixture of locally optimal search and global search heuristic where a near global optimum may be found. Numerical comparisons are made for the values of performance index achieved by the joint optimization problem with system optimal flow and those did by equilibrium flow at various sets of initial signal settings. Substantially good results have demonstrated the robustness of the proposed algorithm in solving both system optimal and user equilibrium flow for the joint optimization problem at large-scale networks.