Основные направления развития методов решения задач математического программирования
Можно построить математические модели для достаточно широкого круга явлений. Однако мы выяснили, что не всякую математическую задачу мы в состоянии решить — во-первых, по причине большой ее размерности, а во-вторых, из-за наличия нелинейных целевых функций и условий-ограничений. Кроме того, нам хотелось бы, чтобы, не решая заново задачу, иметь инструмент, который позволял бы с небольшими затратами изменять решения при небольших изменениях исходных данных (параметров целевой функции и условий-ограничений). Поскольку такие изменения исходных данных являются случайными величинами,™ следовало бы определить и доверительные границы для решений реальной задачи. Но тогда мы выйдем за рамки этой книги — это область стохастического программирования.
Тем не менее удается, хотя достаточно и громоздкими методами, в задачах линейного программирования установить, как будет изменяться решение задачи, если известны функциональные зависимости, описывающие изменение исходных данных. Подобные задачи решают в разделе, посвященном параметрическому программированию.
Несмотря на обилие разработанных методов решения сетевых задач трудности остаются. В гл. 2 упоминалось, что из-за большой размерности некоторые сетевые задачи строгими методами решить не удается; в подобных случаях применяют эвристические методы, которые дают хотя и не строго оптимальное решение, но приемлемое в практических приложениях.
В гл. 3 были рассмотрены сетевые задачи для однородного потока. В реальных условиях по сети требуется транспортировать (передавать) различные «продукты»: например, телефонные разговоры, телеграммы, телевизионные передачи и т.п., т.е. необходимо иметь алгоритмы, которые позволяли бы решать задачи о многопродуктовых потоках в сетях. Методы решения многопродуктовых сетевых задач сложны и поэтому выбираемые алгоритмы позволяют решить задачу только приближенно.
Естественно стремление исследователей тем не менее создать в некотором роде универсальные алгоритмы, которые были бы применимы кдостаточно широкому кругу задач математического программирования. К ним относят алгоритмы, реализующие методы: проекции градиента, штрафных (барьерных) функций, внутренней точки, внешней точки и комбинированный внутренней и внешней точек. Методами штрафных функций можно решать задачи как линейного, так и нелинейного программирования. Хотя вряд ли экономно их использовать для решения линейных задач.
Особое место занимают многокритериальные задачи и целевое программирование, которые более адекватно описывают реальные проблемы.
Эта теория взята со страницы лекций по предмету «математическое программирование»:
Предмет математическое программирование
Возможно эти страницы вам будут полезны:
| Дробно-линейное программирование |
| Анализ устойчивости оптимального решения задачи линейного программирования |
| Понятие о параметрическом программировании |
| Многопродуктовые потоки в сетях |
