Доставка любой диссертации в формате PDF и WORD за 499 руб. на e-mail - 20 мин. 800 000 наименований диссертаций и авторефератов. Все авторефераты диссертаций - БЕСПЛАТНО
Ситникова, Ольга Дмитриевна
01.01.09
Кандидатская
1984
Донецк
127 c. : ил
Стоимость:
499 руб.
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,
Название работы | Автор | Дата защиты |
---|---|---|
Задача оптимального управления в модели эпидемии | Овсянникова, Наталья Игоревна | 2009 |
Реализуемость решений многошаговых кооперативных игр | Дементьева, Мария Борисовна | 2002 |
Универсальное тестирование в частных классах автоматов | Пономаренко, Александр Владимирович | 2007 |