перейти к полному списку дипломных проектов
Ссылка на скачивания файла в формате .doc находится в конце странички
2.2.2 ПРЯМОЙ АЛГОРИТМ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ
Термин “прямой”, примененный к алгоритму целочисленного программирования, обозначает метод, который приводит к оптимальному решению посредством получения последовательно “улучшаемых” решений. Каждой из этих решений допустимо в том смысле, что оно удовлетворяет как линейным ограничениям, так и условию целочисленности. Одним из вероятных достоинств алгоритма является возможность прервать вычисления, до того как получено оптимальное решение, и использовать наилучшее из полученных решений как приближенное. Кроме того, можно использовать прямой алгоритм в соединении с двойственными алгоритмами, чтобы получать различные составные алгоритмы, которые могут переходить от фазы, дающей двойственно допустимые решения, к фазе, дающей прямо допустимые решения.
Естественным прецедентом для прямого алгоритма является полностью целочисленный алгоритм Гомори, поскольку в процессе этого алгоритма получается последовательность двойственно допустимых целочисленных решений. Следует напомнить, что полностью целочисленный алгоритм Гомори представляет собой модификацию двойственного симплекс-метода. Основное отличие этого алгоритма состоит в том, что в качестве ведущей строки используется отсечение Гомори с ведущим элементом, равным –1. Это отсечение получается из производящей строки, которая определяется как одна из возможных ведущих строк в двойственном симплекс-методе. Использование такого отсечения в качестве ведущей строки сохранит после итерации двойственную допустимость и целочисленность таблицы.
Оказывается, можно аналогично модифицировать симплекс-метод таким образом, чтобы получить алгоритм, который сохраняет прямую допустимость и целочисленность таблиц. Для описания вычислительной процедуры рассмотрим следующую задачу целочисленного программирования:
максимизировать
при условиях
,
(целые) (k=1,…,n),
где a0j, aij и ai0 – целые числа и ai00.
Предположим, что столбец выбран в качестве ведущего и строка v – ведущая строка в итерации симплекс-метода, т.е. для всех строк I, в которых ais>0. Прежде чем провести процедуру исключения Гаусса в симплекс-методе, добавим к таблице отсечение Гомори, полученное из строки v:
где J – множество индексов небазисных переменных в (22), sk – новая (базисная) слабая переменная и - неопределенная (временно) положительная константа.
Заметим, что если положить = avs, отсечение (23) будет обладать двумя важными свойствами. Во-первых,
Это означает, что прямая допустимость таблицы сохраниться, если использовать отсечение (23) в качестве ведущей строки. Во-вторых, , т.е. ведущий элемент равен 1 (если отсечение используется как ведущая строка). Легко удостовериться (путем исследования формул изменения базисных переменных), что преобразование симплексной таблицы с единичным ведущим элементом сохраняет целочисленность элементов симплексной таблицы.
Эти идеи послужили основанием прямого алгоритма в целочисленном программировании:
Шаг 0. Начать со столбцовой таблицы, в которой ai00 (i1) и все элементы a0j, aij и ai0 – целые.
Шаг 1. Проверить выполнение условий a0j0 (j1); если они выполнены, то конец, текущее базисное решение оптимально; если нет – перейти к шагу 2.
Шаг 2. Выбрать ведущий столбец s с a0s< 0. Выбрать строку v по правилу проверки отношения ai0/ais среди строк с ais> 0. Эта строка служит производящей для отсечения Гомори.
Шаг 3. Получить отсечение Гомори из производящей строки и дописать ее внизу таблицы, т.е. добавить к ограничениям задачи уравнение (23), где .
Шаг 4. Произвести преобразование таблицы, используя отсечение (23) как ведущую строку. Слабая переменная sk в (23) станет небазисной. Вернуться к шагу 1.
Доказательство конечности алгоритма см. [2], стр. 346-353.
Поскольку выбор производящей строки является задачей нетривиальной, по-видимому, должно существовать несколько строк, которые могут служить в качестве производящих. В предварительных рассуждениях в качестве производящей строки использовалась ведущая строка симплекс-метода. Эта строка всегда дает отсечение, которое является ведущей строкой с ведущим элементом, равным единице. По-видимому, в таблице существуют и другие строки, из которых могут быть получены отсечения с такими же свойствами. Допустим, что отсечение получается по формуле:
Строка v может стать производящей тогда и только тогда, когда
где определяется из условия
Определим множество V(s) как совокупность строк, удовлетворяющих условию (25).
Следующие два правила представляют собой примеры допустимых правил выбора производящей строки:
Правило 1.
Составить последовательный конечный список индексов строк таким образом, чтобы индекс каждой строки вошел в него по меньшей мере один раз. Перейти к 2.
Если список пуст или не содержит ни одного индекса из V(s), вернуться к 1.; в противном случае найти в списке первый индекс vV(s). Выбрать строку v как производящую. Вывести из списка индекс v и все предшествующие ему индексы. Перейти к 3.
Последовательно выбирать строку v, взятую в 2., как производящую, до тех пор, пока vV(s). Как только vV(s), вернуться к 2.
Правило 2.
Пусть Vt(s) – множество V(s), соответствующее t-й таблице. Если Vt(s) содержит более одного элемента: Vt(s) = {v1, v2, …, vk+2}, то в качестве производящей выбрать такую строку , что в последовательности множеств V1(s1), V2(s2), …, Vt(s) строка появилась раньше (не позднее) остальных и затем сохранялась вплоть до Vt(s); перейти к 2.
Последовательно выбирать строку v, взятую в 1., до тех пор, пока . Как только , вернуться к 1.
Подробнее об алгоритме можно прочитать в [2], стр. 344.
скачать бесплатно Описание технологической области
Содержание дипломной работы
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1.1. ФОРМУЛИРОВКА ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ
1.1.1. ОБЩАЯ ФОРМУЛИРОВКА ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЙ
1.1.2. ФОРМУЛИРОВКА ЗАДАЧИ СОСТАВЛЕНИЯ РАПИСАНИЯ В ПРИМЕНЕНИИ К РАСПИСАНИЮ УЧЕБНЫХ ЗАНЯТИЙ.
1.2. АНАЛИЗ СУЩЕСТВУЮЩЕГО ПО
1.3. ПОСТАНОВКА ЗАДАЧИ.
2.1. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ РАСПИСАНИЯ В ВУЗЕ
2.1.1. ОБОЗНАЧЕНИЯ
ПРЕПОДАВАТЕЛИ
2.1.2. ПЕРЕМЕННЫЕ
2.1.3. ОГРАНИЧЕНИЯ
2.1.4. ЦЕЛЕВАЯ ФУНКЦИЯ
2.2. МЕТОДЫ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ
2.2.1. ПОЛНОСТЬЮ ЦЕЛОЧИСЛЕННЫЙ АЛГОРИТМ
2.2.2 ПРЯМОЙ АЛГОРИТМ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ
2.2.3. ТЕХНИКА ПОЛУЧЕНИЯ НАЧАЛЬНОГО ДОПУСТИМОГО БАЗИСА
2.3. ОСОБЕННОСТИ ПРАКТИЧЕСКОЙ РЕАЛИЗАЦИИ СИСТЕМЫ
2.3.1. ВЫБОР МОДЕЛИ
ИЕРАРХИЧЕСКИЙ СПОСОБ ОРГАНИЗАЦИИ
СЕТЕВОЙ СПОСОБ ОРГАНИЗАЦИИ
РЕЛЯЦИОННЫЙ СПОСОБ ОРГАНИЗАЦИИ
2.3.2. ОПИСАНИЕ ВХОДНОЙ ИНФОРМАЦИИ
2.3.3. РАЗРАБОТКА ИНФОРМАЦИОННОГО ОБЕСПЕЧЕНИЯ ЗАДАЧИ
2.3.4. ОСОБЕННОСТИ ФОРМИРОВАНИЯ ОГРАНИЧЕНИЙ МАТЕМАТИЧЕСКОЙ МОДЕЛИ ЗАДАЧИ СОСТАВЛЕНИЯ РАСПИСАНИЯ
2.4. РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММЫ
2.5. АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ
ВЫВОДЫ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ 1. ВОЗМОЖНОСТИ ПРОГРАММНЫХ ПРОДУКТОВ СИСТЕМ СОСТАВЛЕНИЯ РАСПИСАНИЙ.
3. Система “Методист”
ПРИЛОЖЕНИЕ 2. ЛИСТИНГ ПРОГРАММНОГО МОДУЛЯ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ АВТОМАТИЧЕСКОГО СОСТАВЛЕНИЯ РАСПИСАНИЯ
