Xreferat.com » Рефераты по информатике и программированию » Разработка математической модели и ПО для задач составления расписания

Разработка математической модели и ПО для задач составления расписания

alt="Разработка математической модели и ПО для задач составления расписания" width="44" height="20" /> (правило выбора будет описано дальше) и написать внизу таблицы дополнительную строку

Разработка математической модели и ПО для задач составления расписания

Эта строка выбирается в качестве ведущей.

Шаг 3. Провести шаг двойственного симплекс-метода, вычеркнуть дополнительную строку и вернуться к шагу 1.

Доказательство конечности алгоритма см. [2], стр. 303-304.

Правило выбора Разработка математической модели и ПО для задач составления расписания формулируется следующим образом.

Шаг 0. Пусть строка с номером v является производящей.

Шаг 1. Пусть Разработка математической модели и ПО для задач составления расписания - лексикографически минимальный столбец среди столбцов с avj<0.

Шаг 2. Для каждого avj<0 пусть Разработка математической модели и ПО для задач составления расписания - наибольшее целое, такое, что Разработка математической модели и ПО для задач составления расписания (лексикографически меньше).

Шаг 3. Пусть Разработка математической модели и ПО для задач составления расписания, а Разработка математической модели и ПО для задач составления расписания (строка v - производящая). Тогда

Разработка математической модели и ПО для задач составления расписания.

Шаг 4. Положить Разработка математической модели и ПО для задач составления расписания для avj<0.

Правило выбора Разработка математической модели и ПО для задач составления расписания, описанное выше, позволяет сделать ведущий элемент равным –1, при этом сохраняется двойственная допустимость таблицы и в то же время нулевой столбец будет максимально лексикографически уменьшаться.

Подробнее об алгоритме можно прочитать в [2], стр. 300.

2.2.2 Прямой алгоритм целочисленного программирования

Термин “прямой”, примененный к алгоритму целочисленного программирования, обозначает метод, который приводит к оптимальному решению посредством получения последовательно “улучшаемых” решений. Каждой из этих решений допустимо в том смысле, что оно удовлетворяет как линейным ограничениям, так и условию целочисленности. Одним из вероятных достоинств алгоритма является возможность прервать вычисления, до того как получено оптимальное решение, и использовать наилучшее из полученных решений как приближенное. Кроме того, можно использовать прямой алгоритм в соединении с двойственными алгоритмами, чтобы получать различные составные алгоритмы, которые могут переходить от фазы, дающей двойственно допустимые решения, к фазе, дающей прямо допустимые решения.

Естественным прецедентом для прямого алгоритма является полностью целочисленный алгоритм Гомори, поскольку в процессе этого алгоритма получается последовательность двойственно допустимых целочисленных решений. Следует напомнить, что полностью целочисленный алгоритм Гомори представляет собой модификацию двойственного симплекс-метода. Основное отличие этого алгоритма состоит в том, что в качестве ведущей строки используется отсечение Гомори с ведущим элементом, равным –1. Это отсечение получается из производящей строки, которая определяется как одна из возможных ведущих строк в двойственном симплекс-методе. Использование такого отсечения в качестве ведущей строки сохранит после итерации двойственную допустимость и целочисленность таблицы.

Оказывается, можно аналогично модифицировать симплекс-метод таким образом, чтобы получить алгоритм, который сохраняет прямую допустимость и целочисленность таблиц. Для описания вычислительной процедуры рассмотрим следующую задачу целочисленного программирования:

максимизировать

(22)

Разработка математической модели и ПО для задач составления расписания

при условиях

Разработка математической модели и ПО для задач составления расписания,

Разработка математической модели и ПО для задач составления расписания (целые) (k=1,…,n),

где a0j, aij и ai0 – целые числа и ai0Разработка математической модели и ПО для задач составления расписания0.

(23)

Предположим, что столбец Разработка математической модели и ПО для задач составления расписания выбран в качестве ведущего и строка v – ведущая строка в итерации симплекс-метода, т.е. Разработка математической модели и ПО для задач составления расписаниядля всех строк I, в которых ais>0. Прежде чем провести процедуру исключения Гаусса в симплекс-методе, добавим к таблице отсечение Гомори, полученное из строки v:

Разработка математической модели и ПО для задач составления расписания

где J – множество индексов небазисных переменных в (22), sk – новая (базисная) слабая переменная и Разработка математической модели и ПО для задач составления расписания - неопределенная (временно) положительная константа.

Заметим, что если положить Разработка математической модели и ПО для задач составления расписания= avs, отсечение (23) будет обладать двумя важными свойствами. Во-первых,

Разработка математической модели и ПО для задач составления расписания

Это означает, что прямая допустимость таблицы сохраниться, если использовать отсечение (23) в качестве ведущей строки. Во-вторых, Разработка математической модели и ПО для задач составления расписания, т.е. ведущий элемент равен 1 (если отсечение используется как ведущая строка). Легко удостовериться (путем исследования формул изменения базисных переменных), что преобразование симплексной таблицы с единичным ведущим элементом сохраняет целочисленность элементов симплексной таблицы.

Эти идеи послужили основанием прямого алгоритма в целочисленном программировании:

Шаг 0. Начать со столбцовой таблицы, в которой ai0Разработка математической модели и ПО для задач составления расписания0 (iРазработка математической модели и ПО для задач составления расписания1) и все элементы a0j, aij и ai0 – целые.

Шаг 1. Проверить выполнение условий a0jРазработка математической модели и ПО для задач составления расписания0 (jРазработка математической модели и ПО для задач составления расписания1); если они выполнены, то конец, текущее базисное решение оптимально; если нет – перейти к шагу 2.

Шаг 2. Выбрать ведущий столбец s с a0s< 0. Выбрать строку v по правилу проверки отношения ai0/ais среди строк с ais> 0. Эта строка служит производящей для отсечения Гомори.

Шаг 3. Получить отсечение Гомори из производящей строки и дописать ее внизу таблицы, т.е. добавить к ограничениям задачи уравнение (23), где Разработка математической модели и ПО для задач составления расписания.

Шаг 4. Произвести преобразование таблицы, используя отсечение (23) как ведущую строку. Слабая переменная sk в (23) станет небазисной. Вернуться к шагу 1.

Доказательство конечности алгоритма см. [2], стр. 346-353.

Поскольку выбор производящей строки является задачей нетривиальной, по-видимому, должно существовать несколько строк, которые могут служить в качестве производящих. В предварительных рассуждениях в качестве производящей строки использовалась ведущая строка симплекс-метода. Эта строка всегда дает отсечение, которое является ведущей строкой с ведущим элементом, равным единице. По-видимому, в таблице существуют и другие строки, из которых могут быть получены отсечения с такими же свойствами. Допустим, что отсечение получается по формуле:

(24)

Разработка математической модели и ПО для задач составления расписания

Строка v может стать производящей тогда и только тогда, когда

(25)

Разработка математической модели и ПО для задач составления расписания

где Разработка математической модели и ПО для задач составления расписанияопределяется из условия

Разработка математической модели и ПО для задач составления расписания

Определим множество V(s) как совокупность строк, удовлетворяющих условию (25).

Следующие два правила представляют собой примеры допустимых правил выбора производящей строки:

Правило 1.

1. Составить последовательный конечный список индексов строк таким образом, чтобы индекс каждой строки вошел в него по меньшей мере один раз. Перейти к 2.

2. Если список пуст или не содержит ни одного индекса из V(s), вернуться к 1.; в противном случае найти в списке первый индекс vРазработка математической модели и ПО для задач составления расписанияV(s). Выбрать строку v как производящую. Вывести из списка индекс v и все предшествующие ему индексы. Перейти к 3.

3. Последовательно выбирать строку v, взятую в 2., как производящую, до тех пор, пока vРазработка математической модели и ПО для задач составления расписанияV(s). Как только vРазработка математической модели и ПО для задач составления расписанияV(s), вернуться к 2.

Правило 2.

1. Пусть Vt(s) – множество V(s), соответствующее t-й таблице. Если Vt(s) содержит более одного элемента: Vt(s) = {v1, v2, …, vk+2}, то в качестве производящей выбрать такую строку Разработка математической модели и ПО для задач составления расписания, что в последовательности множеств V1(s1), V2(s2), …, Vt(s) строка Разработка математической модели и ПО для задач составления расписания появилась раньше (не позднее) остальных Разработка математической модели и ПО для задач составления расписания и затем сохранялась вплоть до Vt(s); перейти к 2.

2. Последовательно выбирать строку v, взятую в 1., до тех пор, пока Разработка математической модели и ПО для задач составления расписания. Как только Разработка математической модели и ПО для задач составления расписания, вернуться к 1.

Подробнее об алгоритме можно прочитать в [2], стр. 344.

2.2.3. ТЕХНИКА ПОЛУЧЕНИЯ НАЧАЛЬНОГО ДОПУСТИМОГО БАЗИСА

Решение каждым из приведенных выше методов

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: