Математика

Общая постановка и алгоритм решения задач методом динамического программирования

Будем считать, что состояниерассматриваемой системы S на k-м шаге (k = 1, 2, ..., п) определяется совокупностью чисел

которые получены в результате реализации управления обеспечивающего переход системы S из состояния в состояние

Задача о наборе высоты и скорости летательным аппаратом

Как уже отмечалось, динамическое программирование (иначе, «динамическое планирование») представляет собой метод оптимизации решений, специально приспособленный к многошаговым (или многоэтапным) операциям.

Динамическое программирование

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

Транспортная задача

Одна из наиболее распространенных задач математического (обычно — линейного) программирования — транспортная задача. В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или

суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям продукции (и наоборот). В простейшем виде, когда распределяется один вид продукта и потребителям безразлично, от кого из поставщиков его получать, задача формулируется следующим образом.

Проблема двойственности в линейном программировании

Ранее уже упоминалось о прямых и обратных задачах поиска экстремума (см., например, рис. 2.4, а, б, в, г), в которых критерий и ограничения «меняются местами». Рассмотрим прямую и двойственную задачи линейного программирования и те экономические понятия, которые с этим связаны.

Прямая задача. Требуется, чтобы был достигнут максимум

(2.30)