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

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

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

(12)

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

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

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

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

Условия (12) могут быть записаны как

(13)


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

Предположим, что для t=0 (т.е. для исходной таблицы) все aij – целые и столбцы Разработка математической модели и ПО для задач составления расписания(j = 1 ,…, n) – лексикографически положительны. Тогда все столбцы на протяжении вычислений остаются лексикографически положительными.

Прежде чем изложить способ получения дополнительного ограничения из производящей строки, введем новое представление чисел. Пусть [x] обозначает наибольшее целое число, не превосходящее x. Для любого числа y (положительного или отрицательного) и положительного Разработка математической модели и ПО для задач составления расписанияможно записать:

(14)

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

где Разработка математической модели и ПО для задач составления расписания(ry – неотрицательный остаток от деления нацело y на Разработка математической модели и ПО для задач составления расписания). В частности, Разработка математической модели и ПО для задач составления расписания. Поэтому если Разработка математической модели и ПО для задач составления расписания, то Разработка математической модели и ПО для задач составления расписания и r = 1. Если Разработка математической модели и ПО для задач составления расписания, то Разработка математической модели и ПО для задач составления расписания и r = 0.

Вводимое дополнительное неравенство должно выполняться при любом целом решении задачи (12). Рассмотрим некоторое уравнение в t – таблице (опуская индекс строки) с a0<0:

(15)


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

где x – соответствующая компонента вектора Разработка математической модели и ПО для задач составления расписания, а Разработка математической модели и ПО для задач составления расписания - текущие небазисные переменные. Можно выразить x, a0 и aj, используя введенное выше представление (14):

(16)

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

(17)

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

Подставив выражения (16) и (17) в (15) и переставив члены, получим:

(18)

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

Поскольку Разработка математической модели и ПО для задач составления расписания, Разработка математической модели и ПО для задач составления расписания и на переменные x и Разработка математической модели и ПО для задач составления расписания наложено требование неотрицательности, левая часть уравнения (18) всегда неотрицательна. Рассмотрим выражение в правой части, заключенное в фигурные скобки. Коэффициенты в этом выражении представляют собой целые числа, а переменные подчинены требованию целочисленности. Поэтому все выражение в скобках должно быть целым. Обозначим его через s, т.е.:

(19)

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

Целочисленная слабая переменная s является неотрицательной. Действительно, если бы s было отрицательным, т.е. принимало бы значения -1, -2, …, то умножение на Разработка математической модели и ПО для задач составления расписания Разработка математической модели и ПО для задач составления расписания сделало бы всю правую часть уравнения (18) отрицательной, в то время как левая часть неотрицательна.

Рассмотрим два случая Разработка математической модели и ПО для задач составления расписания и Разработка математической модели и ПО для задач составления расписания. Для Разработка математической модели и ПО для задач составления расписания Разработка математической модели и ПО для задач составления расписания и Разработка математической модели и ПО для задач составления расписания. Подставляя в уравнение (19) выражение для x из (15), получим:

(20)


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

Полученное уравнение есть не что иное как отсечение Гомори. Для Разработка математической модели и ПО для задач составления расписания имеем Разработка математической модели и ПО для задач составления расписания и уравнение (19) приобретает вид:

(21)

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

Уравнение (21) должно выполняться для любого целочисленного решения задачи (12). Заметим, что если a0<0, то Разработка математической модели и ПО для задач составления расписания в уравнении (21). Потому уравнение (21) может использоваться в качестве ведущей строки в симплекс-методе. В частности, всегда можно выбрать Разработка математической модели и ПО для задач составления расписания достаточно большим, так чтобы ведущий элемент Разработка математической модели и ПО для задач составления расписания в строке (21) стал равным –1, что позволит сохранить целочисленность таблицы. Выбор соответствующего Разработка математической модели и ПО для задач составления расписания будет влиять на скорость сходимости алгоритма. Прежде всего опишем сам алгоритм. В качестве начального необходимо взять двойственно допустимое решение, которое можно получить добавлением ограничения xn+m+1=M – x1 - - … - xn Разработка математической модели и ПО для задач составления расписания 0, где M – достаточно большая константа, и проведением одной итерации с добавленной строкой и с лексикографически минимальным столбцом, взятыми в качестве ведущих. Алгоритм состоит из следующих шагов:

Шаг 0. Начать с двойственно допустимой матрицы A0 в уравнении (13), элементы которой – целые числа (матрица A0 может содержать и нецелые элементы, об этом см. [2], стр. 306).

Шаг 1. Среди строк с ai0<0 (i=1, …, n+m) выбрать строку с наименьшим значением i; эта строка станет производящей. (Если ai0Разработка математической модели и ПО для задач составления расписания0 (i=1, …, n+m), то задача решена.)

Шаг 2. Выбрать

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

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

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

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