Yup: And stochastic dynamic programming and stochastic optimal control! Suppose a cargo plane is to fly from Kansas City to St. Louis, Chicago, Indianapolis, Dayton, Nashville, and Memphis and at each city pickup cargo. Suppose the cargo weights are known only in probability distribution from history and otherwise are probabilistically independent. Have weather reports for the winds and temperatures, but the actual values can vary from the reports. And suppose the fuel prices vary significantly among the stops but are known.
Then, how much fuel should the pilot buy at each stop to minimize expected cost for the trip? I.e., in simple terms, buy extra fuel where it's cheap and carry (tanker) it to where it's expensive but in so doing burn extra fuel from the extra weight of the extra fuel.
Solution: Stochastic dynamic programming.
Hint: In Canada, the solution is illegal!
Was meeting with Nemhauser (see references below); my cab back to the airport was waiting; and he gave me a 15 second lecture. On the plane thought about his lecture, ..., and stood for my Ph.D. orals and passed (extra credit for guessing my employer).
Some references (with TeX markup):
Stuart E.\ Dreyfus and
Averill M.\ Law,
{\it The Art and Theory of Dynamic Programming,\/}
ISBN 0-12-221860-4,
Academic Press,
New York.\ \
Dimitri P.\ Bertsekas,
{\it Dynamic Programming:
Deterministic and Stochastic Models,\/}
ISBN 0-13-221581-0,
Prentice-Hall.\ \
George L.\ Nemhauser,
{\it Dynamic Programming,\/}
ISBN 0-471-63150-7,
John Wiley and Sons,
New York\ \
E.\ B.\ Dynkin and
A.\ A.\ Yushkevich,
{\it Controlled Markov Processes,\/}
ISBN 0-387-90387-9,
Springer-Verlag,
Berlin.\ \
Wendell H.\ Fleming and
Raymond W.\ Rishel,
{\it Deterministic and Stochastic Optimal Control,\/}
ISBN 0-387-90155-8,
Springer-Verlag,
Berlin.\ \
Michael Athans and
Peter L.\ Falb,
{\it Optimal Control:\ \
An Introduction to the Theory and Its Applications,\/}
McGraw-Hill Book Company,
New York.\ \
Dimitri P.\ Bertsekas and
Steven E.\ Shreve,
{\it Stochastic Optimal Control:
The Discrete Time Case,\/}
ISBN 0-12-093260-1,
Academic Press,
New York.\ \
E.\ B.\ Lee and
L.\ Markus,
{\it Foundations of Optimal Control Theory,\/}
ISBN 0471-52263-5,
John Wiley, New York,
Then, how much fuel should the pilot buy at each stop to minimize expected cost for the trip? I.e., in simple terms, buy extra fuel where it's cheap and carry (tanker) it to where it's expensive but in so doing burn extra fuel from the extra weight of the extra fuel.
Solution: Stochastic dynamic programming.
Hint: In Canada, the solution is illegal!
Was meeting with Nemhauser (see references below); my cab back to the airport was waiting; and he gave me a 15 second lecture. On the plane thought about his lecture, ..., and stood for my Ph.D. orals and passed (extra credit for guessing my employer).
Some references (with TeX markup):
Stuart E.\ Dreyfus and Averill M.\ Law, {\it The Art and Theory of Dynamic Programming,\/} ISBN 0-12-221860-4, Academic Press, New York.\ \
Dimitri P.\ Bertsekas, {\it Dynamic Programming: Deterministic and Stochastic Models,\/} ISBN 0-13-221581-0, Prentice-Hall.\ \
George L.\ Nemhauser, {\it Dynamic Programming,\/} ISBN 0-471-63150-7, John Wiley and Sons, New York\ \
E.\ B.\ Dynkin and A.\ A.\ Yushkevich, {\it Controlled Markov Processes,\/} ISBN 0-387-90387-9, Springer-Verlag, Berlin.\ \
Wendell H.\ Fleming and Raymond W.\ Rishel, {\it Deterministic and Stochastic Optimal Control,\/} ISBN 0-387-90155-8, Springer-Verlag, Berlin.\ \
Michael Athans and Peter L.\ Falb, {\it Optimal Control:\ \ An Introduction to the Theory and Its Applications,\/} McGraw-Hill Book Company, New York.\ \
Dimitri P.\ Bertsekas and Steven E.\ Shreve, {\it Stochastic Optimal Control: The Discrete Time Case,\/} ISBN 0-12-093260-1, Academic Press, New York.\ \
E.\ B.\ Lee and L.\ Markus, {\it Foundations of Optimal Control Theory,\/} ISBN 0471-52263-5, John Wiley, New York,