- 最后登录
- 2013-5-10
- 在线时间
- 0 小时
- 寄托币
- 21
- 声望
- 0
- 注册时间
- 2002-3-5
- 阅读权限
- 10
- 帖子
- 0
- 精华
- 0
- 积分
- 30
- UID
- 37585
- 声望
- 0
- 寄托币
- 21
- 注册时间
- 2002-3-5
- 精华
- 0
- 帖子
- 0
|
发表于 2003-12-18 08:52:48
|显示全部楼层
实在是解不出来了
小女子先谢过了!!!!
1.In several 'balancing' problems the situation is as follows.You have a variable
vector x of length n,linear constraints,and k constant vectors Ci(i=1,2,....k),
each of length n.The goal is to minimize maxi Ci'X (Ci 有个转秩符号我不知道怎么
打).Note that this objective function is not linear.Nevertheless one can solve problems of this
type using any methiod for LP.How does it work?
Caution>Resist the temptation to minimize every CiX separately and to take the maximum os these k values.*max min is not the same as min max.)
2.Consider a very basic facility location problem: given n points P1,....Pn in the plane,find a so called center,that is,a point P that minimizes the sum of distance from P to all Pi.Propose a simple method to approach an optimal solution.The standard way of setting partial dervatives to 0 may lead to teerible formulae.
(Hint: the object function has a helpful property)
Is the center p uniquely determined?
3.We are looking for a maximum matching in a given bipartite graph(see the note,NG-4 for definitions).
however we have further restrictions:the parts(color classes) V1 and V2 of our
bipartite graph are ordered sets,says V1=(x1,...,xm) and V2=(y1,...yn),
and we do not allow crossing edges in our matching,that means:For any two edges
XaYb and XcYd WITH a<c in our matching,we must have b<d
how could you compute such a "monotone" matching of maximum size?
(a)by computing a maximum flow in some suitable network?or
(b)by some completely different method?
Describe your method in detail.Make sure that your algorithm produces
in fact an optimal solution.(one can easily go wrong.) Motivate why you
discarded the other option((a) or (b)).
4.This problem came up in computational biology.Apart from all
laboratory
details,the mathematical essence is as follows.We have a set of unknow
and unvisible bit strings (i.e with symbols 0 or 1) of the same length.
The data you get is a set of many copies of these bit strings.Unfortunately,P
bits (or fewer) in every string became unreadable.For exammple,bit string
0110101000 may produce data strings ??10101000 011010?0?0 01001?1000(P=2).
Even worse ,the copies of alll the unknow bit strings are in one pool ,
one can not see which copies came from the same bit string.The problem
is to guess the original bit strings.Since we expect in the application that
their number was quite small,people have changed the question into an optimization problem:
Given n data strings with symbols 0,1,?(at most P question marks in every string),
replace each question mark with 0 or 1 such that the number of different bit
strings obtained is minimized.
Given an approximation algorithm that produres a solution with at most 2^P times
the optimal number of bit strings that would explain the same data.(2^P seems
to be unreasonable,however P is small in the application). |
|