林夏祥 , think again. If we are trying to minimize the maximum distance, then we want to minimize the upper bound. That is what I specified: letting c be the upper bound, find the smallest c such that all of the distances do not exceed c. That gives rise to the inequalities |x(i)-x(j)| <= c. If necessary, this can be written as two inequalities: x(i) - x(j) <= c and x(j) - x(i) <= c.
Since the relationship is "and," we can just use the two inequalities as part of the constraint conditions. Dave On Oct 21, 12:02 am, 林夏祥 <saltycoo...@gmail.com> wrote: > I don't think LP can solve it. We are to maximize c, not minimize c. > The formulas we have are: > > |x(i)-x(j)| >= c for all i and j > r1(i) <= x(i) <= r2(i) for all i > The first inequality actually is combination of two linear equalities: x(i) > - x(j) >= c or x(i) - x(j) <= -c. Notice the relation of the two is "or", > and we cannot put them together to get a system of linear inequalities. > 2009/10/21 Dave <dave_and_da...@juno.com> > > > > > > > > > This is a linear programming problem. The way you formulate the > > problem depends on the capabilities of the linear programming software > > you have. > > > Basically, you want to > > minimize c > > by finding x(1) to x(n) such that > > > |x(i)-x(j)| <= c for all i and j > > r1(i) <= x(i) <= r2(i) for all i > > > Dave > > > On Oct 5, 9:22 am, monty 1987 <1986mo...@gmail.com> wrote: > > > We have to locate n points on the x-axis > > > For each point xi > > > the x co-ordinate of it lies between a range > > > [r1i,r2i] > > > Now we have to decide the location of points such that > > > minimum { distance between any two points } is maximum. > > > > Any answer is welcomed. > > -- > 此致 > 敬礼! > > 林夏祥- Hide quoted text - > > - Show quoted text - --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---