安全渡河问题的计算机求解和模拟

本文介绍利用数学软件包来求解和利用计算机多媒体制作工具来模拟数学模型课程中安全渡河问题的方法     

安全渡河问题的计算机求解和模拟

本介绍利用数学软件包来求解和利用计算机多媒体制作工具来模拟数学模型课程中安全渡河问题的方法。     

超图的Alcuin数与其横贯数的关系

1000多年前, 英国著名学者Alcuin曾提出过一个古老的渡河问题, 即狼、羊和卷心菜的渡河问题. 最近, Prisner和Csorba等考虑了一般``冲突图"上的渡河问题. 将这一问题推广到超图$H=(V,\mathcal{E})$\,上, 考虑一类情况更一般的运输计划问题. 现在监管者 欲运输超图中的所有点\,(代表``items")\,渡河, 这里$V$的点子 形成超边 当且仅当这些点代表的``items"在无人监管的情况下不能留在一起. 超图$H$的Alcuin数是指超图$H$具有可行运输方案\,(即把$V$的点代表的``items" 全部运到河对岸)\,时船的最小容量. 给出了 $r$-一致完全二部超图和它的伴随超图, 以及$r$-一致超图的Alcuin数, 同时证明了判断$r$-一致超图是否为小船图是NP 困难的.     

抢渡长江最佳路线的探讨

1　问题的提出2 0 0 2年 5月 1日 ,武汉市体委在长江武汉段举行了中国武汉国际抢渡长江挑战赛 .这次大赛 ,共有183名选手参赛 .但成功到达终点的仅有 34人 .其中大部分的人被冲到下游 ,这是什么原因呢 ?怎样设计省时的渡江方案呢 ?为此 ,我们研究性学习小组多次访问武汉体委的有关同志和男子组第一名宋济的父亲 ,还到渡江地点进行实地考察和测量 ,这为我们以后继续研究打下了基础 .2　分析与数学模型的建立1)简单的渡河问题分析 .在分析具体的渡江问题前 ,我们先讨论一下简单的渡河问题 .图 1　渡河问题分析用图如图 1,设人的速度为向量 ｖ…     

数学复习中的多学科沟通

随着高考改革的不断深入,命题中突出了数学的工具性,加强了知识间的联系,特别是注意了数学与其他学科的沟通,所以在高考复习中要重视数学与其他学科的联系.一、与物理的沟通物理考试不会刻意追求数学,但应该使学生懂得,如何利用数学知识来解决物理问题.其实物理中的很多问题都和数学有关,如物理中的最值问题、受力分析、运动问题、变力做功问题、气态变化问题等等.例1河宽H,船速为V船,水流速度为V水,船速V船与河岸的夹角为θ,如图1所示.①求渡河所用的时间,并讨论θ=?时渡河时间最短.②怎样渡河,船的合位移最小?分析①用船静水中的分运动…     

最大度为5的图的Alcuin数

1000多年前,英国著名学者Alcuin曾提出过一个古老的渡河问题,即狼、羊和卷心菜的渡河问题.最近,Prisner和Csorba等人把这一问题推广到任意的"冲突图"G=(V,E)上,考虑了一类情况更一般的运输计划问题.现在监管者欲运输V中的所有"物品/点"渡河,这里V的两个点邻接当且仅当这两个点为冲突点.冲突点是指不能在无人监管的情况下留在一起的点.特别地,Alcuin渡河问题可转化成"冲突路"P_3上是否存在可行运输方案问题.图G的Alcuin数是指图G具有可行运输方案(即把V的点代表的"物品"全部运到河对岸)时船的最小容量.最大度为5且覆盖数至少为5的图和最大度Δ(G)≤4且覆盖数不小于Δ(G)-1的图的Alcuin数已经被确定.本文给出最大度为4且覆盖数不超过2和最大度为5且覆盖数不超过4的图的Alcuin数.至此,最大度不超过5的图的Alcuin数被完全确定.     

用MATHEMATICA求解商人渡河问题

提出了一种求解商人渡河问题的算法,并给出了用数学软件MATHEMATICA实现该算法的源代码,列出了部分计算结果供进一步研究.该算法可以应用于求解更一般的多步决策问题.     

渡河问题的补充

渡河问题的补充吴怀军（广东鹤山市一中５２９７００）读《数学通讯》１９９７年第８期《渡河的最短路程和最少时间》，深受启发．但文中分析渡河的最短路程时，仅考虑船速ｖ′大于水流速度ｖ０的情况，实际上，当ｖ′＜ｖ０时，船的合运动方向无法与河岸垂直．因此，本文...     

工程兵舟桥营战术行动中的多目标决策——渡口优化计算

现实生活和作战指挥当中的决策都是多目标的。本文以渡口构筑时间、所需作业兵力、所需物资器材、渡口的输送能力、渡口的生存能力等五项为决策目标,用系数加权方法求解。一、渡口优化计算的数学模型本文是解决工程兵舟桥营在执行任务中的渡口选优和模拟的问题。通常是根据合成军首长的作战企图,要求在某地域强渡江河,如果该地域有M个待选点可供构筑渡口选用,同时还有N种渡河方法需要选择。这样一来,就有一个渡口位置的选择问题,还有一个渡河方法的选择问题。它的数学模型如下:     

商人渡河问题的算法实现

"商人渡河问题"是一个传统的智力游戏问题,常常是作为数学模型、数据结构与智能算法分析等学科中很重要的教学或实验案例被引用.其求解算法尚未得到很好的解决,问题解的存在性等还缺少一般性和明确的结论.将首先从算法实现方面对这个问题进行深入地探讨.设计出思想方法较简单的、能在Matlab中编程实现的算法,且算法能求出问题的全部最少步数解.此外还报告了该类问题在各种情形下有趣的计算结果.     

MONOTONIZATION IN GLOBAL OPTIMIZATION

A general monotonization method is proposed for converting a constrained programming problem with non-monotone objective function and monotone constraint functions into a monotone programming problem. An equivalent monotone programming problem with only inequality constraints is obtained via this monotonization method. Then the existing convexification and concavefication methods can be used to convert the monotone programming problem into an equivalent better-structured optimization problem.     

Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times

In this paper, we study the identical parallel machine scheduling problem with a planned maintenance period on each machine to minimize the sum of completion times. This paper is a first approach for this problem. We propose three exact methods to solve the problem at hand: mixed integer linear programming methods, a dynamic programming based method and a branch-and-bound method. Several constructive heuristics are proposed. A lower bound, dominance properties and two branching schemes for the branch-and-bound method are presented. Experimental results show that the methods can give satisfactory solutions.     

Nonlinear leastpth optimization and nonlinear programming

Over the past few years a number of researchers in mathematical programming became very interested in the method of the Augmented Lagrangian to solve the nonlinear programming problem. The main reason being that the Augmented Lagrangian approach overcomes the ill-conditioning problem and the slow convergence of the penalty methods. The purpose of this paper is to present a new method of solving the nonlinear programming problem, which has similar characteristics to the Augmented Lagrangian method. The original nonlinear programming problem is transformed into the minimization of a leastpth objective function which under certain conditions has the same optimum as the original problem. Convergence and rate of convergence of the new method is also proved. Furthermore numerical results are presented which illustrate the usefulness of the new approach to nonlinear programming.This work was supported by the National Research Council of Canada and by the Department of Combinatorics and Optimization of the University of Waterloo.     

求解弱线性双层规划问题的一种全局优化方法

双层规划在经济、交通、生态、工程等领域有着广泛而重要的应用.目前对双层规划的研究主要是基于强双层规划和弱双层规划.然而,针对弱双层规划的求解方法却鲜有研究.研究求解弱线性双层规划问题的一种全局优化方法,首先给出弱线性双层规划问题与其松弛问题在最优解上的关系,然后利用线性规划的对偶理论和罚函数方法,讨论该松弛问题和它的罚问题之间的关系.进一步设计了一种求解弱线性双层规划问题的全局优化方法,该方法的优势在于它仅仅需要求解若干个线性规划问题就可以获得原问题的全局最优解.最后,用一个简单算例说明了所提出的方法是可行的.     

ASYMPTOTIC APPROXIMATION METHOD AND ITS CONVERGENCE ON SEMI-INFINITE PROGRAMMING

The aim of this article is to discuss an asymptotic approximation model and its convergence for the minimax semi-infinite programming problem. An asymptotic surrogate constraints method for the minimax semi-infinite programming problem is presented by making use of two general discrete approximation methods. Simultaneously, the consistence and the epi-convergence of the asymptotic approximation problem are discussed.     

Initialization in semidefinite programming via a self-dual skew-symmetric embedding

The formulation of interior point algorithms for semidefinite programming has become an active research area, following the success of the methods for large-scale linear programming. Many interior point methods for linear programming have now been extended to the more general semidefinite case, but the initialization problem remained unsolved.In this paper we show that the initialization strategy of embedding the problem in a self-dual skew-symmetric problem can also be extended to the semidefinite case. This method also provides a solution for the initialization of quadratic programs and it is applicable to more general convex problems with conic formulation.     

A General Alternative Procedure for Solving Negative Degree of Difficulty Problems in Geometric Programming

The degree of difficulty is an important concept in classical geometric programming theory. The dual problem is often infeasible when the degree of difficulty is negative and little has been published on this topic. In this paper, an alternative procedure is developed to find the optimal solution for the posynomial geometric programming problem with a negative degree of difficulty. First an equivalent problem was constructed with a positive degree of difficulty and the general posynomial geometric programming problem was solved using an original method previously developed by the authors. This method avoids the difficulty of non-differentiability of the dual objective function in the classical methods classified as dual. It also avoids the problem that appears when the feasible region for the dual problem is formed by an inconsistent system of linear equations.     

A minimization method with approximation of feasible set and epigraph of objective function

For a convex programming problem we propose a solution method which belongs to the class of cutting-plane methods. When constructing approximate solutions to the problem, this technique concurrently approximates its feasible set and the epigraph of the objective function. Planes for cutting the iteration points are being constructed with the help of subgradients of the objective function and left-hand sides of constraints. In this connection, one can find each iteration point by solving a linear programming problem. As distinct from most other well-known cuttingplane methods, the proposed technique allows the possibility to periodically update approximating sets by dropping accumulated constraints. We substantiate the convergence of the proposed method and discuss its numerical realization.     

On active-set methods for the quadratic programming problem

The active-set Newton method developed earlier by the authors for mixed complementarity problems is applied to solving the quadratic programming problem with a positive definite matrix of the objective function. A theoretical justification is given to the fact that the method is guaranteed to find the exact solution in a finite number of steps. Numerical results indicate that this approach is competitive with other available methods for quadratic programming problems.     

0-1线性规划的连续化及其遗传算法解法

将0-1离散规划通过一个非线性等式约束表示为[0,1]区间上等价的连续变量非线性规划列式.对非线性等式约束的问题进行了两种方法的处理.第一种方法使用乘子法,第二种方法将非线性的等式约束近似为一个非线性的不等式约束,均利用遗传算法程序GENOCOP进行了求解.对多个算例进行了计算,结果表明了该方法的可行性和有效性.