Методы последовательного анализа решений в частично целочисленных задачах линейного программирования и их применение

• Автор: Мащенко, Сергей Олегович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1985
• Место защиты: Киев
• Количество страниц: 214 c. : ил

Глава I. МЕТОДЫ ПОСЛЕДОВАТЕЛЬНОГО АНАЛИЗА РЕШЕНИЙ

ЧАСТИЧНО ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

§ I.I. Схема последовательного анализа решений

§ 1.2. Оператор аппроксимации множества допустимых решений частично целочисленной задачи линейного программирования и его реализация

§ 1.3. Процедура локализации области оптимума

Глава 2. АЛГОРИТМЫ СХЕШ ПОСЛЕДОВАТЕЛЬНОГО АНАЛИЗА

РЕШЕНИЙ И ИХ ПРИМЕНЕНИЕ В УСЛОВИЯХ ФУНКЦИОНИРОВАНИЯ СИСТЕМ ОТРАСЛЕВОГО ПЛАНИРОВАНИЯ
§ 2.1. Алгоритмы последовательного анализа решений частично целочисленных задач линейного программирования

§ 2.2. Нахождение приближенных решений частично

целочисленной задачи линейного программирования

§ 2.3. Постановка задачи математического программирования выбора годовой производственной программы в отраслевых системах
§ 2.4. Методы последовательного анализа решений
многокритериальных задач отраслевого планирования
§ 2.5. Методы последовательного анализа решений в
задачах системной оптимизации структурного подразделения отрасли
Глава 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ РЕШЕНИЯ
ЧАСТИЧНО ЦЕЛОЧИСЛЕННЫХ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
- 3 -
§ 3.1. Программная реализация алгоритмов оптимизации частично целочисленных задач линейного программирования
§ 3.2. Вычислительный эксперимент по решению частично целочисленных задач линейного программирования
§ 3.3. Диалоговая система многокритериальной оптимизации (ДИСМОП)
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ

В решениях съездов КПСС и специальных постановлениях ЦК КПСС и Совета Министров СССР содержатся программные указания о совершенствовании механизмов управления народим хозяйством на всех его уровнях. Важные задачи экономики, управления, проектирования и другие задачи, имеющие большое народнохозяйственное значение сводятся к частично целочисленным задачам линейного -программирования.
Современный уровень развития математических методов'и вычислительной техники позволяет решать задачи, которые несколько лет назад считались практически неразрешимыми. Вместе с тем решение целого ряда важных в прикладном отношении частично целочисленных задач линейного программирования особенно таких, которые необходимо решать в условиях функционирования АСУ различного уровня и назначения, требует использования искусственных приемов, либо вообще их решение не удается найти за практически приемлемое время.
В настоящее время в области дискретной оптимизации ведутся интенсивные исследования по разработке методов решения различных классов задач. Наиболее изученными являются задачи линейного и выпуклого, в основном сепарабельного, программирования с ограничениями специальной структуры. Развит целый ряд методов нахождения решений (как точных, так и приближенных) различных классов задач дискретной оптимизации. В этой связи следует отметить работы Михалевича B.C., Журавлева Ю.И., Сергиенко И.В., Емеличе-ва В.А., Хачатурова В.Р., Данцига Дж., Вендерса Дж. и других как советских, так и зарубежных ученых.
Вместе с тем, разработанные в настоящее время методы решении множества индексов 0 на подмножества Т , К - 1, р > размерность каждой из этих подзадач меньше размерности исходной задачи (1.1) - (1.3). Для решения непрерывных: оценочных подзадач можно использовать алгоритмы симплекс-метода, например, изложенные в [47,94]. Решение целочисленных оценочных подзадач может быть получено с помощью алгоритмов пошагового конструирования решений [40,54,61-6б], алгоритмов метода [6,7,12,13] , декомпозиционных алгоритмов последовательного анализа вариантов [8-10,57,58,69] и т.д. Естественно, при выборе конкретных алгоритмов необходимо учитывать специфические особенности как самих алгоритмов, так и соответствующих подзадач. В частности, в тех случаях, когда объем множества частичных решений целочисленных подзадач достаточно небольшой (порядка 10^ -г 10^), то для решения этих подзадач целесообразно использовать алгоритмы прямого перебора. Для решения целочисленных подзадач с малым числом ограничений можно использовать методы динамического программирования [40].
В соответствии с общей схемой оператора аппроксимации окончание работы процедуры РР производится на некотором шаге Б0, когда система допусков
01%)(5О) = , (1-56)
либо по условию (1.29). На основании теорем 6,9 справедливо следующее следствие.
Следствие. Окончание работы процедуры РР происходит за конечное число шагов