寄托天下 寄托天下
查看: 1984|回复: 0

sos:这儿有优化高手吗??? [复制链接]

Rank: 1

声望
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).
回应

使用道具 举报

RE: sos:这儿有优化高手吗??? [修改]
您需要登录后才可以回帖 登录 | 立即注册

问答
Offer
投票
面经
最新
精华
转发
转发该帖子
sos:这儿有优化高手吗???
https://bbs.gter.net/thread-156350-1-1.html
复制链接
发送
报offer 祈福 爆照
回顶部