Показать сообщение отдельно
  #5  
Старый 30.10.2008, 10:17
SergeyDe SergeyDe вне форума
участник
 
Регистрация: 03.10.2008
Адрес: Москва
Сообщений: 119
SergeyDe на пути к лучшему
По умолчанию Ответ: Линейное программирование и динамическое программирование

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

Динамическое программирование применяется тогда, когда задачу можно свести к последовательности однотипных подзадач, и решение одной задачи становиться основанием для решения следующей. Классическим примером может служить задача распределения одного ресурса между несколькими потребителями, имеющими различную и неравномерную зависимость производительности от потребляемого ресурса. Мы сначала снабжаем наиболее производительного потребителя, потом менее производительного и т.д по остаточному принципу, но так, чтобы расход всего ресурса дасть наибольший выход продукта всеми потребителями ресурса.
Ответить с цитированием