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

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

1. Обзор методов решения задач дискретной

оптимизации

2. Метод последовательного исследования плоскостей

уровня для задачи ЦИП общего вида

2.1. Постановка задачи и описание метода

2.2. Результаты вычислительных экспериментов

2.3. Применение метода для решения задачи замены оборудования

3. Приближенное решение задачи ЦШ с матрицей

ограничений специального вида

3.1. Постановка задачи и анализ применимости метода вектора спада для ее решения

3.2. Метод замен

3.3. Выводы и результаты вычислительного
эксперимента
4. Задачи перспективного планирования в угольной промышленности
4.1. Задача перспективного развития действующих
шахт
4.2. Задача оптимального проектирования шахты
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ

В "Основных направлениях экономического и социального развития СССР на 1981-1985 гг. и период до 1990 г.", принятых на ХХУ1 съезде КПСС, указано, что для ускорения перевода экономики на путь интенсивного развития, повышения эффективности общественного производства необходимо, в частности, направить усилия на "совершенствование вычислительной техники, ее элементной базы и математического обеспечения..." /33/.
В математическом программировании теория и методы оптимизации являются одним из наиболее эффективных разделов прикладной ма^ тематики.
В последние годы большое внимание уделяется разработке и внедрению методов решения задач дискретной оптимизации.
Целью диссертационной работы является:
- изучить и обобщить опыт решения дискретных задач оптимизации, отраженный в отечественной и зарубежной литературе;
- разработать и исследовать новые методы решения задач полностью целочисленного линейного программирования (ДЛЮ общего и некоторых специальных видов;
- разработать программное обеспечение для решения задач ЦЛП "Библиотеки программ оптимизации и исследования операций для
СМ ЭВМ";
- используя созданное программное обеспечение, решить задачу о замене оборудования машиностроительного завода;
- разработать комплекс программ для решения задач ЦЛП по перспективному планированию в угольной промышленности.
Предметом исследований стали следующие классы задач:
- задача ЦЛП общего вида с двусторонними ограничениями на неизвестные;
- задача ЦЛП, матрица ограничений которой наряду с ограни-

чениями-неравенствами содержит ограничения-равенства специального вида;
- задачи оптимального планирования, которые по математической постановке являются задачами ЦЛП с булевыми неизвестными и матрицей ограничений специального вида, отнесенной к предыдущему классу.
Методологическую основу работы составляют методы построения последовательности решений и вектора спада.
Диссертация состоит из введения, 4 глав, списка литературы, заключения и приложения.
В первой главе приводится обзор методов решения задач дискретной оптимизации: подчеркивается актуальность рассматриваемых задач, обосновывается возрастающий интерес к исследованиям в этой области оптимизации, выделены наиболее распространенные классы задач, освещены вопросы вычислительной сложности этих задач, основанные на теории 1]Р - полных задач, проанализированы существующие точные и приближенные методы, указаны основные направления развития теории и практики решения задач дискретной оптимизации.
Во второй главе рассмотрен точный метод решения задачи ЦЛП с матрицей ограничений общего вида и двусторонними ограничениями на неизвестные, относящийся к классу методов построения последовательности решений. Метод заключается в замене исходной допустимой области расширенным множеством с последующим анализом точек расширенной области, попадающих на плоскости уровня функции. Приведены алгоритмы, реализующие метод, перечислены и обоснованы пути ускорения работы алгоритма. Рассмотрена возможность построения ограничения-фильтр, сужающего область поиска решений. Для нахождения точек уровня построена серия алгоритмов направленного перебора. Приведены результаты вычислительного эксперимента по

ір й'і') - целочисленные;
<&і іб^с — ^ • 'кУгп &
Г1 Ч
Ні п,
^йЬл, (3-6)
Е Г -4« -*•*
У(-Еі

% 1,т.
]*± •’і ч
Если к вектору X применить любое число замен вида:
Хі — +біі^ 'Хуса — Ху0 £^ ' 0> — Кі (3.7)
то ограничения (3.5) в X не нарушатся, цри этом применение #
одной замены -ого коэффициента изменит функцию цели на ±У* , каждое из ограничений на І 7^ (^К>~ /у
Проиллюстрируем применение замены на примере. Пусть решается задача минимизации функции:
/(х)= -2х1 +2,х$Хі - -хуі-5^^г -їх* +3х3
при ограничениях:
2х£ *л*-а> 44 +хґ+2х}-
гх,+6хг - Юз* +ИХ) = /0}
и имеется допустимое решение:
гч 1, *, І, А и о, о), /4М
Рассмотрим, например, строку таблицы замен для СС$ :
1 і | JW7Z Г77ЯІ І ” !
! / = // ~(С ї> г -1 ! //> г,Ъ/0)^_ , !
то есть ^4 =//^«1 или 7* 1 = 2*1 + 1*5,