|
|
 | | From: | Steve | | Subject: | Re: What kind of problem is this? | | Date: | 31 Dec 2004 06:08:52 -0800 |
|
|
 | You can try the Excel optimization solver as Dr. Rubin suggests. But
if this is a real business problem that you are trying to solve you may
run into some limitations with that. The built-in Excel optimizer can
only handle a relatively small number of variables unless you buy an
upgraded version of the solver engine. No real problem there. You can
find information on an upgrade at, www.solver.com.
But formulating the problem in Excel may be a major challenge because
decision variables are defined by sets of indexes that describe a set
of characteristics. For example, a PC of what type is bought from what
vendor, in what period represents a variable with 3 underlying indexes,
type, vendor and period. Once you get beyond two indexes in Excel,
managing the variable set becomes difficult because of the two
dimensional nature of a spreadsheet. However, there are other
mathematical programming products that allow you to easily formulate
complex, multi-index problems.
If you have to get this job done rather quickly and you need a product
that is easy to use (we call that "turn-key"), you may want to hire
an Italian mathematical programmer to help you. I use a mathematical
programming software package called MPL produced by Maximal Software,
www.maximalsoftware.com. I know that they have Italian users and they
have an Italian version of their documentation. You may want to contact
them to see if they could refer you to an Italian consultant you could
hire for support. The developer of MPL, Bjarni Kristjansson, travels
to Europe regularly so you may want to contact him directly,
bjarni@maximalsoftware.com for a referral.
Good Luck,
Steve
Washington DC
Paul A. Rubin wrote:
> JPC wrote:
> > Hi,
> >
> > I'm a programmer of an italian software house, we develop
accounting and
> > financial applications.
> > Now I have to resolve a particular problem that I think can be
solved
> > applying the Operative Research methodology.
> > But I'm completely ignorant of Operative Research.
> > Can you help me in identifying/classifying the type of the problem
> > (Assignment, scheduling or whatever else) and give me little
advices to deal
> > with this difficult (for me) problem?
> >
> > The problem is:
> >
> > One big Company, needs to have a certain number of PCs to perform
its
> > business (these PCs are needed by the employees for the daily
activity).
> > The needed qty can vary in the various months, depending on the
business
> > turnover of the different months/periods.
> > This big company makes some Supply Contracts (AGREEMENTS) with its
Suppliers
> > (IBM, COMPAQ, DELL,...):
> > the company can buy (and therefore resell) the PCs from its
supplier in two
> > different way:
> >
> > "Lease" (It means that after a period on wich the PC is
used by the
> > big-company, the PC will be returned to the Supplier, and the
Supplier will
> > give a fixed amount (depending on the usage period above) to the
Company in
> > exchange for the PC)
> >
> > "NO-Lease" (the Company after having used the PC, will resell the
PC to
> > other customers/persons, estabilishing a price based on market
conditions
> > and on the usage period)
> >
> > each of the two "Purchase Type" is subjected to some rules and
restrictions
> > (constraints, see later).
> >
> >
> > The PCs have some attributes:
> > PC_MODEL (PC01, PC02,...) PC01 = Pentium 2, PC02 = AMD Athlon XP
2800 ,
> > etc..
> > PC_GROUP (A, B, ....) this is a sort of classification: Small PC,
Medium PC,
> > etc.
> >
> > The company business is divided into some BUSINESS_LINEs (A1, A2,
B2, ... it
> > is a Departments Classification like Production, Administration,
Sales
> > etc...)
> >
> > At the beginning of each month, the Company makes a forecast for
the future
> > PC addition and deletion, in order to
> > decide how many PC must be sold in the month and how many must be
> > ordered/bought.
> > The Company estimates the PC quantity needed
> > each month by each BUSINESS_LINE in the future/next months
(TARGET_QTY).
> >
> > The TARGET_QTY is not a unique list, but it is separated for each
PC_GROUP
> > and for each BUSINESS_LINE.
> > For example, the Company can decide that they need
> > , in Jan 2004, 100 Small PC for Business Line A1, 70 Small PC for
Business
> > Line B1, 40 Medium PC for BusLine A2
> > , in Feb 2004, 200 Small PC for Business Line A1, 50 Small PC for
Business
> > Line B1, 60 Medium PC for BusLine A2
> > , and so on
> >
> > Then, they want to plan the purchases and the dismissions of the
PCs to
> > satisfy (to best satisfy) their TARGET_QTY.
> > So they want to Optimise the addition/dismission of each month in
oder to
> > make the PC_QTY of each month as close as possible to the
TARGET_QTY
> > They want also to optimise the COST (the cost is fixed and can be
easily
> > pre-calculated for each PC_GROUP, for each purchase month, for each
> > supplier, and obviously for each different dismission month and
dismission
> > type "Lease" or "NotLease").
> >
> > Each month there is, obviously, an already existing qty of PC in
the company
> > (INITIAL_QTY, or IQ)
> > And there is also a certain number of already ordered PCs (RAISED
ORDERS, or
> > RO), that are being delivered.
> > All of this PCs (IQ and RO), MUST BE scheduled, that is to say that
we have
> > to assure that all of the already owned PC and the PC that we have
already
> > ordered, must be planned so that for each of them we can estabilish
when it
> > will be sold (in Lease or NotLease)
> >
> > The problem, I think, is to obtain the Min( SUM( ABS(TARGET_QTY -
> > PC_QTY) ) ) , and the MIN ( SUM( COST)) ,
> > respecting a lot of conditions (constraints) like the following:
> >
> > 1) The RO and the IQ qty must be scheduled.
> > 2) For each Agreement, a Minimum Overall Purchasable Qty and a
Maximum
> > Overall Purchasable Qty can exist.
> > 3) For each Agreement and PC Model, a Minimum Overall Purchasable
Qty and a
> > Maximum Overall Purchasable Qty can exist.
> > 4) For each Agreement and PC Model, a Maximum Monthly Purchasable
Qty
> > exists.
> > 5) For each Agreement and PC Model, a Maximum Monthly "Lease"
Return Qty can
> > exists.
> > 6) For each Agreement and PC Model, a Minimum Purchasable Qty can
exists for
> > a number of contiguos months.
> > 6) For each Agreement and PC Model, a Maximum Purchasable Qty can
exists for
> > a number of contiguos months.
> > 7) For each Agreement and PC Model, a Maximum Monthly "Lease"
Return Qty can
> > exists.
> >
> >
> >
> >
> > Sorry for the long description , and for my very bad english!!
> > Can you help me telling what sort of problem is this ?
> > If I knew the type/classification of this problem (scheduling,
> > assignemnt,... ), perhaps I'd be able to search for a solution.
> > And, can you advise me the algorithm-name to be used?
> > Some books dedicated to these specific kind of problem?
> > Do you think it is better to write the algorithm by myself, or
> > it is better to buy a commercial Solver?
> > Can you give me an advice also on the name of valid and fast
commercial
> > Solver?
> >
> > Thanks.
> > JPC
>
> The problem sounds like a linear program (if you are willing to
accept a
> solution that involves fractions of PCs, and then just round the
answer
> to integer values and manually adjust if the rounded solution falls
> short here or there); otherwise it is an integer program (like a
linear
> program but with variables required to be integer-valued --
formulation
> is very similar, but solution time will be longer).
>
> There are a number of good commercial packages for solving such
> problems, but unless the dimensions of the problem are very large, I
> suggest you try using the Solver in Excel.
>
> You might want to take a look at a few introductory operations
research
> (or management science) texts. You might find a superficially
similar
> problem in the linear programming or integer programming chapters
that
> would serve as a template to get you started.
>
> -- Paul
>
>
******************************************************************************************
> Paul A. Rubin
Phone:
> (517) 432-3509
> Department of Management Fax:
(517)
> 432-1111
> The Eli Broad Graduate School of Management E-mail:
rubin@msu.edu
> Michigan State University
> http://www.msu.edu/~rubin/
> East Lansing, MI 48824-1122 (USA)
>
******************************************************************************************
> Mathematicians are like Frenchmen: whenever you say something to
them,
> they translate it into their own language, and at once it is
something
> entirely different. J. W. v. GOETHE
|
|
| | From: | JPC | | Subject: | Re: What kind of problem is this? | | Date: | Mon, 3 Jan 2005 13:33:13 +0100 |
|
|
| Thanks a lot to all of you for your advices.
The dimensions of the problem are very large, so I think the Excel Solver is
not a good idea.
I think also I can accept a solution that involves fractions of PCs, if this
will improve the solution time considerably.
Since I think that a good commercial package is the easiest solution, could
you kindly give me the names of some good products (besides
www.maximalsoftware.com) ?
What about Lingo9 ?
Thanks again
JPC
|
|
|
