Adapt Megiddo’s 2D LP algorithm so that you can deal with parabolic constraints. You can assume that all constraints are convex (like U shapes, each symmetric about some vertical line, but with various widths and apex positions). Also assume that each constraint points upward (meaning the feasible region is convex). Ans) The linear programming (LP) problem calls for minimizing a linear objective function subject to linear constraints. Every such problem can be presented in the following form:  Here the vectors cT = (c1, . . . , cd), bT = (b1, . . . , bm), and the m × d matrix A constitute the input, and x = (x1, . . . ,xd) is the vector of variables to be optimized. Usually, one assumes that all input numbers are integers or rationals. The goal is to find an optimal x if such exists, and if not, to determine that the problem is unbounded (i.e., the minimum is  ) or infeasible (i.e., there is no x satisfying all the constraints).LP is one of the fundamental problems in operations research and computer science. It was formulated in the 1940s by George Dantzig, who also proposed a method for solving it. Since then, the problem has been studied in thousands of scientific papers and hundreds of books, and interest in the problem has stayed on a very high level. One reason for this is the wide applicability of LP: it is used to model practical, real-life problems in economics, industry, communications, military, and numerous other areas. It is perhaps the most widely used optimization model in the world, and except data structures, perhaps the largest single use of computer resources (see Lovász, 1980.) Another reason is that LP problems with special structure arise in various theoretical and practical areas. Yet another reason is that some fundamental properties of LP and its algorithms are still not fully understood. One of these is the efficiency of the simplex method, which will be discussed here. admin，如果您要查看本帖隐藏内容请回复 |
