Transcription of Chapter 9 Linear programming - École normale supérieure ...
{{id}} {{{paragraph}}}
Example: bankruptcy
Chapter 9 Linear programming - École normale supérieure ...
Chapter 9 Linear programmingThe nature of the programmes a computer scientist has to conceive often requires some knowl-edge in a specific domain of application, for example corporate management, network proto-cols, sound and video for multimedia streaming,.. Linear programming is one of the necessaryknowledges to handle optimization problems. These problems come from varied domains asproduction management, economics, transportation network planning, .. For example, one canmention the composition of train wagons, the electricity production, or the flight planning byairplane of these optimization problems do not admit an optimal solution that can be computedin a reasonable time, that is in polynomial time (See Chapter 3). However, we know how to ef-ficiently solve some particular problems and to provide an optimal solution (or at least quantifythe difference between the provided solution and the optimal value) by using techniques fromlinear fact, in 1947, Dantzig conceived the Simplex Method to solve military planningproblems asked by the US Air Force that were written as a Linear pr
130 CHAPTER 9. LINEAR PROGRAMMING Linear programmes can be written under the standard form: Maximize ∑n j=1cjxj Subject to: ∑n j=1aijxj ≤ bi for all 1≤i≤m xj ≥ 0 for all 1≤ j ≤n. (9.1) All constraints are inequalities (and not equations) and all variables are non-negative.
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: