利用平面上的黄金分割法求全局最优解

给出了无约束全局最优问题的一种解法 ,该方法是一维搜索中的 0 .61 8法的推广 ,不仅使其适用范围由一维扩展到平面上 ,并且将原方法只适用于单峰函数的局部搜索改进为可适用于多峰函数的全局最优解的搜索 .给出了收敛性证明 .本法突出的优点在于 :适用性强、算法简单、可以在任意精度内寻得最优解并且克服了以往直接解法所共有的要求大量计算机内存的缺点 .仿真结果表明算法是有效的 .     

二级线性价格控制问题的满意解的求解思路及实例

本文就文献 [1]对线性二级价格控制问题 (BLP) 2 研究的结果及文献 [2 ]提出的问题进行了进一步的讨论。用反例指出文 [1]求出的极点最优解是错的 ,以及一般的 (BL P) 2 问题求出的最优解 ,可能是下层决策者根本无法接受的。因此 ,本文提出 (BLP) 2 的求下层目标最优解的边界搜索法及在此基础上用多目标的观点来求 (BLP) 2 的满意解的思路及实例     

四面体的一种补形方法及其应用

如图1,从长方体中砍下一个角,可以得到直角四面体PABC.反之,对于直角四面体,我们可以将它补成长方体用以解题,这是立体几何中已经司空见惯的一种补形解法.本文介绍对于一般四面体都适用的另一种补形解法.如图2,从平行六面体中砍下四个角,可以得到四面体ABCD.反之,我们可以将四面体补成图2所示的平行六面体来解决一些问题.下举数例,予以说明.图1长方体图2平行六面体例1(2003年全国高中数学联赛题)在四面体ABCD中,设AB=1,CD=3,直线AB与CD的距离为2,夹角为3π,则四面体ABCD的体积等于()(A)23.(B)21.(C)31.(D)33.图3例1图图4例1图解…     

对“如何寻找《线性规划问题》的整点最优解”一文具体操作中的补充和完善

贵刊 2 0 0 0年第 3期刊登了山西省代县中学校安培录同志的“如何寻找《线性规划问题》的整点最优解”一文 (以下简称———原文 ) ,对线性规划问题中整点最优解提出了三种解法 .但在具体操作中 ,有些地方可以加以补充和完善 .这三种方法都要作出可行域 ,然后 ,在寻找最优解过程中 ,要打网格 ,所以 ,宜提倡用数学中的坐标纸来作图 .在“原文”例 1解法一中写道 :“将直线ｌ1 向下平移至ｌ2 的位置时 ,直线ｌ2 最先经过可行域上的整点Ｂ( 0 ,1 2 )和Ｃ( 3,8)且使ｚ= 2 0 0ｘ 1 5 0ｙ取得最大值” ,现将具体操作方法说明如下 .图 1在例 1中 …     

在WDM环网中疏导率为12的分插复用器数目最小化问题

在WDM网中的一个重要问题是使网络的费用最小化.我们的目的是最小化网络中ADM的个数.这个问题的模型是分拆一个完全图的边成一些子图,使每个子图至多有C条边(这里C是疏导率),并且这些子图的点数之和最小.本文对于给定的C,使用图论和设计理论的工具得到了一些求ADM个数(即A(C,N))的方法.也给出了当C=12并且WDM环网的点数N≡0,16(mod 24)时,问题的最优解(即A(C,N)=N(N-1)/4).     

线性规划的对偶理论在图解法中的应用

对于多个变量两个约束的线性规划,首先利用线性规划的对偶理论,写出其对偶问题;其次利用图解法求出对偶问题的最优解,最后利用互补松弛条件求出原问题的最优解.     

整数规划的渐进强对偶方法

虽然整数规划中经典的Lagrange对偶方法是一个有效的方法，但是由于对偶缝隙的原因它经常不能求出原问题的最优解。该文提出一个用于有界整数规划的指数对偶公式。此公式具有渐进强对偶的特性并且可以保证找到原问题的最优解。它的另一个特性是当参数选择的合适时不需要进行实际的对偶搜索。     

用区域图形解题

在解线性规划问题中,由约束条件作出相应平面区域,进而求出目标函数最优解.其中,作出平面区域是重要的一步,由于平面区域是由不等式(组)、方程来表示的,所以它与函数、不等式、方程等有着密切联系.用平面区域来解决有关问题,尤其是含二个变量及可转化为二个变量的问题,会有独特的作用.下面举几个例子.     

由2013年高考山东卷(理)第9题引发的探究

1题目及解法题目(2013山东理-9)过点(3,1)作圆(x-1)~2+y~2=1的两条切线,切点分别为A,B,则直线AB的方程为()A.2x+y-3=0 B.2x-y-3=0C.4x-y-3=0 D.4x+y-3=0此题考查圆的切点弦方程.试题短小精悍,难易适中,解法多样.为了方便说明,记点P(3,1),圆心C(1,0).思路1:如图1,欲求直线AB的方程,需求出点A,B的坐标,即两条切线与圆的公共点,因此,可以先求出两切线的方程,与圆的方程联立,通过解方程组求出点A,B的坐标,写出直线AB的方程.由于     

一种求解救灾物资运输问题的改进解法

本文通过对B运输问题建立数学模型,提出了一种求解B运输问题的改进解法。改进解法首先通过最小元素法求出初始解,然后进行变量闭回路法调整,直到求出最优解,并给出了一个计算实例证明了解法的有效性。文章还对改进解法和另外两种现有的算法进行了综合的分析,由于改进解法计算过程中采用的变量闭回路法省略了求检验数的环节,使得新算法比两种现有的算法更简便。     

钢管定购和运输的策略优化

本文为图 1主管道和图 2树形管道的定购和运输计划给出了一个最优化模型 .通过解这一个最优化模型得到钢管的定购和运输的最优策略 .同时 ,分析了哪个钢厂钢管销价的变化对图 1主管道购运计划和总费用影响最大 ,哪个钢厂钢管产量的上限的变化对购运计划和总费用影响最大     

A heuristic for BILP problems: The Single Source Capacitated Facility Location Problem

In the Single Source Capacitated Facility Location Problem (SSCFLP) each customer has to be assigned to one facility that supplies its whole demand. The total demand of customers assigned to each facility cannot exceed its capacity. An opening cost is associated with each facility, and is paid if at least one customer is assigned to it. The objective is to minimize the total cost of opening the facilities and supply all the customers. In this paper we extend the Kernel Search heuristic framework to general Binary Integer Linear Programming (BILP) problems, and apply it to the SSCFLP. The heuristic is based on the solution to optimality of a sequence of subproblems, where each subproblem is restricted to a subset of the decision variables. The subsets of decision variables are constructed starting from the optimal values of the linear relaxation. Variants based on variable fixing are proposed to improve the efficiency of the Kernel Search framework. The algorithms are tested on benchmark instances and new very large-scale test problems. Computational results demonstrate the effectiveness of the approach. The Kernel Search algorithm outperforms the best heuristics for the SSCFLP available in the literature. It found the optimal solution for 165 out of the 170 instances with a proven optimum. The error achieved in the remaining instances is negligible. Moreover, it achieved, on 100 new very large-scale instances, an average gap equal to 0.64% computed with respect to a lower bound or the optimum, when available. The variants based on variable fixing improved the efficiency of the algorithm with minor deteriorations of the solution quality.     

流向受限运输问题解法的进一步探讨

本文对流向受限运输问题的求解作了进一步探讨。讨论了虚运价取适当值时,最优解中不含有非退化的限制配点,去掉模型中的某些约束条件不影响问题的可行解,并指出不改变运输问题最佳调运方案的前提下,使总运费下降的条件及方法.     

The time-dependent capacitated profitable tour problem with time windows and precedence constraints

We introduce the time-dependent capacitated profitable tour problem with time windows and precedence constraints. This problem concerns determining a tour and its departure time at the depot that maximizes the collected profit minus the total travel cost (measured by total travel time). To deal with road congestion, travel times are considered to be time-dependent. We develop a tailored labeling algorithm to find the optimal tour. Furthermore, we introduce dominance criteria to discard unpromising labels. Our computational results demonstrate that the algorithm is capable of solving instances with up to 150 locations (75 pickup and delivery requests) to optimality. Additionally, we present a restricted dynamic programing heuristic to improve the computation time. This heuristic does not guarantee optimality, but is able to find the optimal solution for 32 instances out of the 34 instances.     

The uncapacitated facility location problem with demand-dependent setup and service costs and customer-choice allocation

We consider a generalization of the uncapacitated facility location problem, where the setup cost for a facility and the price charged for service may depend on the number of customers patronizing the facility. Customers are represented by the nodes of the transportation network, and facilities can be located only at nodes; a customer selects a facility to patronize so as to minimize his (her) expenses (price for service + the part of transportation costs paid by the customer). We assume that transportation costs are paid partially by the service company and partially by customers. The objective is to choose locations for facilities and balanced prices so as to either minimize the expenses of the service company (the sum of the total setup cost and the total part of transportation costs paid by the company), or to maximize the total profit. A polynomial-time dynamic programming algorithm for the problem on a tree network is developed.     

Variable neighborhood search for the travelling deliveryman problem

A travelling deliveryman needs to find a tour such that the total waiting time of all the customers he has to visit is minimum. The deliveryman starts his tour at a depot, travelling at constant velocity. In this paper we suggest a general variable neighborhood search based heuristic to solve this NP-hard combinatorial optimization problem. We combine several classical neighborhood structures and design data structure to store and update the incumbent solution efficiently. In this way, we are able to explore neighborhoods as efficiently as when solving the travelling salesman problem. Computational results obtained on usual test instances show that our approach outperforms recent heuristics from the literature.     

The routing open-shop problem on a network: Complexity and approximation

In the routing open-shop problem, jobs are located at nodes of an undirected transportation network, and the machines travel on the network to execute jobs in the open-shop environment. The machines are initially located at the same node (depot) and must return to the depot after completing all the jobs. It is required to find a nonpreemptive schedule that minimizes the makespan. We prove that the problem is NP-hard even on a two-node network with two machines, and even on a two-node network with two jobs and m machines. We develop polynomial-time approximation heuristics and obtain bounds on their approximation performance.     

An inventory-transportation system with stochastic demand

We study a logistic system in which a supplier has to deliver a set of products to a set of retailers to face a stochastic demand over a given time horizon. The transportation from the supplier to each retailer can be performed either directly, by expensive and fast vehicles, or through an intermediate depot, by less expensive but slower vehicles. At most one time period is required in the former case, while two time periods are needed in the latter case. A variable transportation cost is charged in the former case, while a fixed transportation cost per journey is charged in the latter case. An inventory cost is charged at the intermediate depot. The problem is to determine, for each time period and for each product, the quantity to send from the supplier to the depot, from the depot to each retailer and from the supplier to each retailer, in order to minimize the total expected cost. We first show that the classical benchmark policy, in which the demand of each product at each retailer is set equal to the average demand, can give a solution which is infinitely worse with respect to the optimal solution. Then, we propose two classes of policies to solve this problem. The first class, referred to as Horizon Policies, is composed of policies which require the solution of the overall problem over the time horizon. The second class, referred to as Reoptimization Policies, is composed of a myopic policy and several rolling-horizon policies in which the problem is reoptimized at each time period, once the demand of the time period is revealed. We evaluate the performance of each policy dynamically, by using Monte Carlo Simulation.     

Location of depots in a sugar-beet distribution system

In the following case study the problem of the location of depots in a sugar-beet distribution system for a certain sugar enterprise in Poland is considered. The sugar-beet is delivered from farms to sugar-mills either directly or through some depots. Lower and upper limits on the depot throughputs are imposed. The depot investment and operating costs are estimated by a piecewiselinear function. Given a set of possible depot locations, costs associated with the depots and the unit transportation costs, we seek a minimum cost location-transportation plan determining the number, location and sizes of the depots to be opened and the amounts of the sugar-beet flows. Two solution procedures are developed: (1) The application of MPSX and MIP systems for the problem of the reduced size; (2) The heuristic method. Based upon the computational results both approaches can be treated as alternative solution techniques to the presented problem.     

The coordination of transportation and batching scheduling

We study a coordinated scheduling problem of production and transportation in which each job is transported to a single batching machine for further processing. There are m vehicles that transport jobs from the holding area to the batching machine. Each vehicle can transport only one job at a time. The batching machine can process a batch of jobs simultaneously where there is an upper limit on the batch size. Each batch to be processed occurs a processing cost. The problem is to find a joint schedule of production and transportation such that the sum of the total completion time and the total processing cost is optimized. For a special case of the problem where the job assignment to the vehicles is predetermined, we provide a polynomial time algorithm. For the general problem, we prove that it is NP-hard (in the ordinary sense) and present a pseudo-polynomial time algorithm. A fully polynomial time approximation scheme for the general problem is obtained by converting an especially designed pseudo-polynomial dynamic programming algorithm.