Christos H Papadimitriou Turing (pdf)

Odnośniki

[ Pobierz całość w formacie PDF ]

you. Oversimplified thinking, primitive decision mak-
ing, the stuff of instincts, of slogans. Flee as fast as you
can. Procreate as much as you can. All power to the
Soviets. But modern life is full of complex trade-
offs, situations where you have to make sophisticated
160 Christos H. Papadimitriou
choices in order to improve your station. The most
simple and characteristic examples are problems of re-
source allocation. A corporation has several activities, all
profitable albeit to a different extent, and each is taxing
the corporation s resources (personnel, factory space,
machinery, computers, truck fleet, and so forth) in differ-
ent ways. How do the corporation s decision makers
choose the optimum level of each activity? Not by in-
stinct and slogan, let me assure you. It s a mathematical
problem actually. And it can be solved by computer. It s p. 261
called the resource allocation problem, or RAP for short.
Governments use it too, and consumers can as well.
Let s take a very simple example. A farmer has ten acres
of land and can grow on it two crops: wheat or potatoes.
Any combination is possible, from all wheat to all pota-
toes, through any amounts of the two that add up to ten
or less.
Even no crops at all? Alexandros asks.
|
Even that, if the market says that neither kind of crop is
profitable this year. We are assuming that the farmer
knows precisely the profitability of each kind; we ll
come to that soon. You see, we are suppressing uncer-
tainty in this example, perhaps the biggest source of dif-
ficulty in real-life decision making.
But perhaps not all combinations of crops are possible.
Maybe there are so many hands around to help for harvest
in July, and so the farmer knows that he can plant wheat
in no more than five acres. The realm of all possibilities is
now amputated; only combinations of wheat and pota-
toes that include five or fewer acres of wheat are possible.
But maybe irrigation is scarse also you know about
irrigation, Alexandros, don t you, a nasty problem since
Turing (A Novel about Computation) 161
the ancient times. And potatoes take much more ir-
rigation (ten cubic feet per acre and day) than wheat
(just three). And the farmer can only get his hands on
eighty cubic feet of water every day (I m making up
these numbers as we go, Alexandros; you probably
know the ballpark range here, but never mind). This
is another consideration that is going to restrict the
farmer s choice.
And that s it, suppose that there are no other constraints
the farmer must abide by. Any combination of wheat
and potato acres that satisfy these restrictions (no more
than five wheat, no more than ten of both, no water
shortage due to too many potatoes) is a possible busi-
ness strategy for the farmer. So, which choice within
these constraints represents the best decision for the
farmer? What do you think, Alexandros?
Don t we need the prices at which the farmer will
sell each crop in order to decide this?
|
Of course. More precisely, we need the numbers that
capture the profitability of each kind of crop, taking into
account market price, labour and irrigation costs, every-
thing. Well, suppose that the farmer has made these cal-
culations and has come up with the following numbers:
Every acre of potato brings a profit of ten thousand dol-
lars, every wheat acre a profit of eight thousand.
Now what? What would you do, Alexandros? Can you
figure out how many acres of wheat and how many of
potatoes you should plant this year?
Alexandros is at a loss. He tries a few calculations.
Mostly potatoes perhaps, as many as irrigation per-
mits. He hesitates again. Right?
162 Christos H. Papadimitriou
|
You see, Alexandros, even this toy problem is a little
challenging. But here s the great news: There is an algo-
rithm that solves any resource allocation problem of this
sort in a flash even the monster RAPs with many thou-
sands of activities and resources that corporations and
governments face every minute. In our example, this
code would start from the null decision, the one in
which zero acres are devoted to each crop, and would
cruise to a better and better decision, with larger and
larger profit, until it doesn t pay to continue, and then it
stops and declares the decision where it got stuck a win-
ner. The optimum solution.
In our example, it would go from zero to $40,000 profit
(five acres of wheat, no potatoes), then on to the next so-
lution with $90,000 profit (five acres of each), from there
to the next solution with $94,285 profit. And there it
would stop, because if we change anything from that
solution we shall either violate the rules of the game
or decrease the profit and the farmer does not want
either of those, does he?
So, the optimum strategy is for the farmer to plant 7.14
acres of potatoes and 2.86 acres of wheat. Isn t this nice?
Not exactly everybody s instinctual reaction, is it?
And we can solve the same way RAPs with more choices
(sunflowers, soybeans, corn, rice), and more resource
constraints (tractors, autumn labour, seed, and so on). [ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

angamoss.xlx.pl