Представлен алгоритм решения задачи линейного программирования посредством процедуры последовательной активации ограничений (включения в расчёт одного за другим) с удержанием состояния оптимальности на сгенерированной последовательности вложенных многогранников. Вследствие сжатия области допустимых решений при критерии оптимальности «шах» целевая функция на каждом шаге убывает (движение к максимуму сверху), в противоположность росту в других методах (снизу). Компьютерные эксперименты демонстрируют преимущества программной реализации этого алгоритма перед опцией симплекс-метода программы linprog библиотеки MATLAB в скорости и полноте выводимой информации.
Скачать электронную версию публикации
Загружен, раз: 262
- Title Метод последовательной активации ограничений в линейном программировании
- Headline Метод последовательной активации ограничений в линейном программировании
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 41
- Date:
- DOI 10.17223/20710410/41/11
Ключевые слова
линейное программирование, активация ограничения, MATLAB, компьютерный эксперимент, linear programming, activation of limitation, MATLAB, computer experimentАвторы
Ссылки
Канторович Л. В. Математические методы в организации и планировании производства. Л.: Изв. Ленингр. гос. ун-та, 1939. 67с.
Данциг Дж. Линейное программирование, его применение и обобщения. М.: Прогресс, 1966. 600 с.
Юдин Д. Б., Гольштейн Е. Г. Линейное программирование: теория, методы и приложения. М.: Наука, 1969. 424 с.
Дикин И. И. Итеративное решение задач линейного и квадратичного программирования // Докл. АН СССР. 1967. Т. 174. С. 747-748.
Хачиян Л. Г. Полиномиальный алгоритм в линейном программировании // Докл. АН СССР. 1979. Т. 244. С. 1093-1096.
Зоркальцев В. И. Двойственные алгоритмы внутренних точек // Изв. вузов. Математика. 2011. №4. С. 33-53.
Зоркальцев В. И., Медвежонков Д. С. Численные эксперименты с вариантами алгоритмов внутренних точек на нелинейных задачах потокораспределения // Управление большими системами. Ин-т систем энергетики им. Л. А. Мелентьева СО РАН, 2013. Вып. 46. С.68-87.
Медвежонков Д. С. Экспериментальные исследования алгоритмов внутренних точек на нелинейных задачах потокораспределения // Вестник Бурятского гос. ун-та. 2013. №9. С. 12-16.
Вылегжанин О. Н., Шкатова Г. И. Решение задачи линейного программирования с использованием оператора-проектора // Изв. Томского политехн. ун-та. 2009. Т. 314. №5. С.37-40.
Бахшиян Б. Ц., Гориянов А. В. Скелетный алгоритм решения задачи линейного программирования и его применение для решения задач оценивания // Вестник МАИ. 2008. Т. 15. №2. С. 5-16.
Гордуновский В. М. Метод экспоненциальной аппроксимации для линейного программирования. М.: Эдитус, 2013. 32 с.
Колосов В. С. Конечный параметрический метод решения задачи линейного программирования // Науч. труды МЛТИ. 1978. Вып. 103. С. 197-198.
Колосов В. С. Роль двойственных оценок в параметрическом методе решения задачи линейного программирования // Науч. труды МЛТИ. 1986. Вып. 183. С. 51-54.
Карманов В. Г. Математическое программирование. М.: ФИЗМАТЛИТ, 2004. 264 с.
Метод последовательной активации ограничений в линейном программировании | Прикладная дискретная математика. 2018. № 41. DOI: 10.17223/20710410/41/11
Скачать полнотекстовую версию
Загружен, раз: 572