Цитата:
Сообщение от простой
Недавно закончил чтение МВ (читал с первого февраля 2007 года по 20 августа 2008 года), в принципе всё понятно, кроме линейного и динамического программирования.
|
Линейное программирование - метод нахождения оптимального решения, если условия задачи можно свести к системе линейных (все слагаемые уравнений в нулевой (постоянная) или первой (переменная) степени) уравнений и неравенств. Классическими примерами являются задачи определения выпуска максимального набора продукции из определенного набора ресурсов, транспортная задача, игры с нулевой суммой (всегда есть проигравший) и другие. Симплекс-метод - это алгоритм решения задачи линейного программирования в общем виде. Уравнение межотраслевого баланса, тоже есть есть задача линейного програмирования.
Динамическое программирование применяется тогда, когда задачу можно свести к последовательности однотипных подзадач, и решение одной задачи становиться основанием для решения следующей. Классическим примером может служить задача распределения одного ресурса между несколькими потребителями, имеющими различную и неравномерную зависимость производительности от потребляемого ресурса. Мы сначала снабжаем наиболее производительного потребителя, потом менее производительного и т.д по остаточному принципу, но так, чтобы расход всего ресурса дасть наибольший выход продукта всеми потребителями ресурса.