ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1449. Credit Operations 2

Does this problem require linear programming?
Posted by SPIRiT 24 May 2006 16:22
Funny to say, but once I've read this problem, I remembered
the simplex method we were taught last year.
The classic problem of simplex method is like this:
find min(max)f(X)=C1*X1+C2*x2+c3*x3.. where ci - constants
Also where is a system of conditions:
a11*x1+..<=(>=)b1
a21*x1+..<=(>=)b2 and so on.
The simplex method finds the solution very fast, but it can be a real value, not an integer. There is also a modification of SM called integer SM - it will find an integer solution. Is the problem based on this algo or not?
Out solutions are not about simplex at all. But you may try to use it anyway (-)
Posted by Dmitry 'Diman_YES' Kovalioff 24 May 2006 23:29
Re: Out solutions are not about simplex at all. But you may try to use it anyway (-)
Posted by SPIRiT 29 May 2006 20:37
Thanks for allowing. I think I've seen in Kormen a chapter how to model linear programming with graphs (unbelievable, isn't it?). I'll see what will happen
Re: Out solutions are not about simplex at all. But you may try to use it anyway (-)
Posted by Denis Koshman 30 Jul 2008 23:00
I think you may round all BR down and all BC up to get integer solution.