一类线性规划逆问题及解法

本文讨论了逆ＬＰ问题的更一般的情况,这里称它为广义逆ＬＰ问题,即在知道了一部分变量和价值系数的条件下,求余下的未知的变量和价值系数,将它们合起来组成给定的ＬＰ问题的最优解。显然若知道全部价值系数就成为ＬＰ问题;若知道全部变量就成为逆ＬＰ问题,它是在根据研制应用软件时提出的。文中给出了解广义逆ＬＰ问题的算法,并成功地用于“宏观经济调控系统”等应用软件的研制中,对要解决的实际问题,给出了强多项式算法。     

On single-machine scheduling without intermediate delays

This paper introduces the non-idling machine constraint where no intermediate idle time between the operations processed by a machine is allowed. In its first part, the paper considers the non-idling single-machine scheduling problem. Complexity aspects are first discussed. The “Earliest Non-Idling” property is then introduced as a sufficient condition so that an algorithm solving the original problem also solves its non-idling variant. Moreover it is shown that preemptive problems do have that property. The critical times of an instance are then introduced and it is shown that when their number is polynomial, as for equal-length jobs, a polynomial algorithm solving the original problem has a polynomial variant solving its non-idling version.     

Problem solving and Working Mathematically: an Australian perspective

This article reviews “problem solving” in mathematics in Australia and how it has evolved in recent years. In particular, problem solving is examined from the perspectives of research, curricula and instructional practice, and assessment. We identify three key themes underlying observed changes in the research agenda in Australia in relation to problem solving: Obliteration, Maturation and Generalisation. Within state mathematics curricula in Australia, changes in the language and construction of the curriculum and in related policy documents have subsumed problem solving within the broader category of Working Mathematically. In relation to assessment, research in Australia has demonstrated the need for alignment of curriculum, instruction and assessment, particularly in the case of complex performances such as mathematical problem solving. Within the category of Working Mathematically, recent Australian curriculum documents appear to accept an obligation to provide both standards for mathematical problem solving and student work samples that illustrate such complex performances and how they might be assessed.     

The nature and development of experts’ strategy flexibility for solving equations

Largely absent from the emerging literature on flexibility is a consideration of experts’ flexibility. Do experts exhibit strategy flexibility, as one might assume? If so, how do experts perceive that this capacity developed in themselves? Do experts feel that flexibility is an important instructional outcome in school mathematics? In this paper, we describe results from several interviews with experts to explore strategy flexibility for solving equations. We conducted interviews with eight content experts, where we asked a number of questions about flexibility and also engaged the experts in problem solving. Our analysis indicates that the experts that were interviewed did exhibit strategy flexibility in the domain of linear equation solving, but they did not consistently select the most efficient method for solving a given equation. However, regardless of whether these experts used the best method on a given problem, they nevertheless showed an awareness of and an appreciation of efficient and elegant problem solutions. The experts that we spoke to were capable of making subtle judgments about the most appropriate strategy for a given problem, based on factors including mental and rapid testing of strategies, the problem solver’s goals (e.g., efficiency, error-free execution, elegance) and familiarity with a given problem type. Implications for future research on flexibility and on mathematics instruction are discussed.     

An adaptation of the dual-affine interior point method for the surface flatness problem

This paper presents an adaptation of the dual-affine interior point method for the surface flatness problem. In order to determine how flat a surface is, one should find two parallel planes so that the surface is between them and they are as close together as possible. This problem is equivalent to the problem of solving inconsistent linear systems in terms of Tchebyshev’s norm. An algorithm is proposed and results are presented and compared with others published in the literature.     

Problem solving heuristics,affect, and discrete mathematics

It has been suggested that activities in discrete mathematics allow a kind of new beginning for students and teachers. Students who have been “turned off” by traditional school mathematics, and teachers who have long ago routinized their instruction, can find in the domain of discrete mathematics opportunities for mathematical discovery and interesting, nonroutine problem solving. Sometimes formerly low-achieving students demonstrate mathematical abilities their teachers did not know they had. To take maximum advantage of these possibilities, it is important to know what kinds of thinking during problem solving can be naturally evoked by discrete mathematical situations—so that in developing a curriculum, the objectives can include pathways to desired mathematical reasoning processes. This article discusses some of these ways of thinking, with special attention to the idea of “modeling the general on the particular.” Some comments are also offered about students' possible affective pathways and structures.     

Estimating the Oil Reserve Base in the UK Continental Shelf

Various models have been used to estimate the amount of oil recoverable from an oil province and the likely sequence of discoveries from any further exploration programme, often with significantly different results. One particular type of model, the discovery-process model, considers oil exploration as a sampling process without replacement, with the underlying size distribution of oilfields determined by the maximum likelihood method. In this paper we consider one example of this type of model, the O'Carroll model, which was previously dismissed as misspecified because of the apparently unrealistic results it gave from early North Sea data. We re-examine this model, solving the integer-constrained maximum likelihood problem in a novel way—as an allocation problem in dynamic programming. Our conclusion is that this model gives a robust estimate of the oil potential in the UK Continental Shelf and a credible distribution of fields yet to be found.     

One-pass heuristics for large-scale unconstrained binary quadratic problems

Many significant advances have been made in recent years for solving unconstrained binary quadratic programs (UQP). As a result, the size of problem instances that can be efficiently solved has grown from a hundred or so variables a few years ago to 2000 or 3000 variables today. These advances have motivated new applications of the model which, in turn, have created the need to solve even larger problems. In response to this need, we introduce several new “one-pass” heuristics for solving very large versions of this problem. Our computational experience on problems of up to 9000 variables indicates that these methods are both efficient and effective for very large problems. The significance of problems of this size is that they not only open the door to solving a much wider array of real world problems, but also that the standard linear mixed integer formulations of the nonlinear models involve over 40,000,000 variables and three times that many constraints. Our approaches can be used as stand-alone solution methods, or they can serve as procedures for quickly generating high quality starting points for other, more sophisticated methods.     

A constraint-based parallel local search for the edge-disjoint rooted distance-constrained minimum spanning tree problem

Many network design problems arising in areas as diverse as VLSI circuit design, QoS routing, traffic engineering, and computational sustainability require clients to be connected to a facility under path-length constraints and budget limits. These problems can be seen as instances of the rooted distance-constrained minimum spanning-tree problem (RDCMST), which is NP-hard. An inherent feature of these networks is that they are vulnerable to a failure. Therefore, it is often important to ensure that all clients are connected to two or more facilities via edge-disjoint paths. We call this problem the edge-disjoint RDCMST (ERDCMST). Previous work on the RDCMST has focused on dedicated algorithms and therefore it is difficult to use these algorithms to tackle the ERDCMST. We present a constraint-based parallel local search algorithm for solving the ERDCMST. Traditional ways of extending a sequential algorithm to run in parallel perform either portfolio-based search in parallel or parallel neighbourhood search. Instead, we exploit the semantics of the constraints of the problem to perform multiple moves in parallel by ensuring that they are mutually independent. The ideas presented in this paper are general and can be adapted to other problems as well. The effectiveness of our approach is demonstrated by experimenting with a set of problem instances taken from real-world passive optical network deployments in Ireland, Italy, and the UK. Our results show that performing moves in parallel can significantly reduce the elapsed time and improve the quality of the solutions of our local search approach.     

Eigenvalue Multiplicity Estimate in Semidefinite Programming

A semidefinite programming problem is a mathematical program in which the objective function is linear in the unknowns and the constraint set is defined by a linear matrix inequality. This problem is nonlinear, nondifferentiable, but convex. It covers several standard problems (such as linear and quadratic programming) and has many applications in engineering. Typically, the optimal eigenvalue multiplicity associated with a linear matrix inequality is larger than one. Algorithms based on prior knowledge of the optimal eigenvalue multiplicity for solving the underlying problem have been shown to be efficient. In this paper, we propose a scheme to estimate the optimal eigenvalue multiplicity from points close to the solution. With some mild assumptions, it is shown that there exists an open neighborhood around the minimizer so that our scheme applied to any point in the neighborhood will always give the correct optimal eigenvalue multiplicity. We then show how to incorporate this result into a generalization of an existing local method for solving the semidefinite programming problem. Finally, a numerical example is included to illustrate the results.     

Local improvement in planar facility location using vehicle routing

In physical distribution the location of depots and vehicle routes are interdependent problems, but they are usually treated independently. Location-routing is the study of solving locational problems such that routing considerations are taken into account. We present an iterative heuristic for the location-routing problem on the plane. For each depot the Weber problem is solved using the end-points of the routes found previously as input nodes to the Weiszfeld procedure. Although the improvements found are usually small they show that it pays not to ignore the routing aspects when solving continuous location problems. Possible research avenues in continuous location-routing will also be suggested.     

The Linear Rational Pseudospectral Method with Preassigned Poles

We present a linear rational pseudospectral (collocation) method with preassigned poles for solving boundary value problems. It consists in attaching poles to the trial polynomial so as to make it a rational interpolant. Its convergence is proved by transforming the problem into an associated boundary value problem. Numerical examples demonstrate that the rational pseudospectral method is often more efficient than the polynomial method.     

Modelling alcohol problems: total recovery

Binge drinking in the UK is an increasing problem, resulting in negative health, social and economic effects. Mathematical modelling allows for future predictions to be made and may provide valuable information regarding how to approach solving the problem of binge drinking in the UK. We develop a 3-equation model for alcohol problems, specifically binge drinking, which allows for total recovery. Individuals are split into those that are susceptible to developing an alcohol problem, those with an alcohol problem and those in treatment. We find that the model has two equilibrium points: one without alcohol problems and one where alcohol problems are endemic in the population. We compare our results with those of an existing model that does not allow for total recovery. We show that without total recovery, the threshold for alcohol problems to become endemic in the population is lowered. The endemic equilibrium solution is also affected, with an increased proportion of the population in the treatment class and a decreased proportion in the susceptible class. Including totally recovery does not determine whether the proportion of individuals with alcohol problems increases or decreases, however it does effect the size of the change. Parameter estimates are made from information regarding binge drinking where we find an increase in the recovery rate decreases the proportion of binge drinkers in the population.     

A Brief Account on Lagrange’s Algebraic Identity

In Indiscrete Thoughts [18], G.-C. Rota remarked, ??The mystery, as well as the glory of mathematics, lies not so much in the fact that abstract theories do turn out to be useful in solving problems, but, wonder of wonders, in the fact that a theory meant for one type of problem is often the only way of solving problems of entirely different kinds, problems for which the theory was not intended. These coincidences occur so frequently, that they must belong to the essence of mathematics.?? Indeed, it happens often that abstract mathematics leads to concrete applications, and real-life problems constitute a source of inspiration for sophisticated theories. The strong synergy between pure mathematics and its applications advocates for teaching methods that intertwine physical intuition with mathematical abstraction, and recognize the universality of mathematical laws throughout the sciences.     

Multimethodology in Metaheuristics

As a combination of different methodologies or parts of methodologies, Multimethodology is becoming more frequent in OR practice. This paper contributes with a new proposal and a new field of application: the employment of Multimethodology in problem solving with Metaheuristics (Mh). A convenient selection of soft and hard methods will be considered, from Soft OR, Creativity and Metaheuristics, such as Strategic Choice Approach, SWOT Analysis and Divergent and Convergent thinking. Formulating the ‘right’ optimisation problem, choosing a method based on Mh and accomplishing an effective implementation is an imprecise decision-making process, which may require skills and ideas that are beyond the ordinary boundaries of Mh practice. The relevance and success of Mh have been well-known for decades, but some open questions concerning choice and implementation strategies, for instance, still remain. If these questions are not adequately answered, they may lose credibility in the long term. The quality of solutions and computational times are not the only criteria used to analyse Mh, nor are they the most important. Very often, the effectiveness of an approach has to be evaluated from the perspective of modelling and practical problem solving. This paper investigates the advantages of Multimethodology and, furthermore, it sketches a framework for a coherent and comprehensive comparison of Mh and recommends a dynamic guiding tool for their implementation.     

基于正弦型光滑打磨函数对0-1规划问题的连续化求解方法

传统的求解0-1规划问题方法大多属于直接离散的解法.现提出一个包含严格转换和近似逼近三个步骤的连续化解法:(1)借助阶跃函数把0-1离散变量转化为[0,1]区间上的连续变量;(2)对目标函数采用逼近折中阶跃函数近光滑打磨函数,约束条件采用线性打磨函数逼近折中阶跃函数,把0-1规划问题由离散问题转化为连续优化模型;(3)利用高阶光滑的解法求解优化模型.该方法打破了特定求解方法仅适用于特定类型0-1规划问题惯例,使求解0-1规划问题的方法更加一般化.在具体求解时,采用正弦型光滑打磨函数来逼近折中阶跃函数,计算效果很好.     

Developing Interdisciplinary Units: A Strategy Based on Problem Solving

While the benefits of the interdisciplinary unit are well documented, it presents a complex challenge to teachers in the natural and social sciences, mathematics, and humanities. Teachers must become active curriculum designers who shape and edit the curriculum according to students' needs. This paper describes knowledge for teachers as curriculum designers and a framework for interdisciplinary unit development. The framework addresses a metacurricular process (problem solving) that will be the unit centerpiece, the development of this central process related to the learner, and the tasks that teach explicit learning and thinking skills attached to the central process. An example of the framework in action is also described. As the faculty and curriculum coordinators for an innovative summer academy for minority students in northern Arizona have used this framework, they have evolved from a group that created a good idea to interest students with parallel subject development in separate classrooms to humanities/mathematics/science teams united in one team/classroom, in which content is integrated through the actions of the problem solving process.     

Solving some problems for systems of linear ordinary differential equations with redundant conditions

Numerical methods are proposed for solving some problems for a system of linear ordinary differential equations in which the basic conditions (which are generally nonlocal ones specified by a Stieltjes integral) are supplemented with redundant (possibly nonlocal) conditions. The system of equations is considered on a finite or infinite interval. The problem of solving the inhomogeneous system of equations and a nonlinear eigenvalue problem are considered. Additionally, the special case of a self-adjoint eigenvalue problem for a Hamiltonian system is addressed. In the general case, these problems have no solutions. A principle for constructing an auxiliary system that replaces the original one and is normally consistent with all specified conditions is proposed. For each problem, a numerical method for solving the corresponding auxiliary problem is described. The method is numerically stable if so is the constructed auxiliary problem.     

Journey toward Teaching Mathematics through Problem Solving

Teaching mathematics through problem solving is a challenge for teachers who learned mathematics by doing exercises. How do teachers develop their own problem solving abilities as well as their abilities to teach mathematics through problem solving? A group of teachers began the journey of learning to teach through problem solving while taking a Teaching Elementary School Mathematics graduate course. This course was designed to engage teachers in problem solving during class meetings and required them to do problem solving action research in their classrooms. Although challenged by the course problem solving work, teachers became more comfortable with the mathematics and recognized the importance of group work while problem solving. As they worked with their students, teachers were more confident in their students' abilities to be successful problem solvers. For some teachers, a strong problem solving foundation was established. For others, the foundation was more tentative.     

Solving an Inverse Problem for an Elliptic Equation by d.c. Programming

An inverse problem of determination of a coefficient in an elliptic equation is considered. This problem is ill-posed in the sense of Hadamard and Tikhonov's regularization method is used for solving it in a stable way. This method requires globally solving nonconvex optimization problems, the solution methods for which have been very little studied in the inverse problems community. It is proved that the objective function of the corresponding optimization problem for our inverse problem can be represented as the difference of two convex functions (d.c. functions), and the difference of convex functions algorithm (DCA) in combination with a branch-and-bound technique can be used to globally solve it. Numerical examples are presented which show the efficiency of the method.