Информатика и программирование

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

Пусть задана задача целочисленного линейногопрограммирования:

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

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

при условиях

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

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

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

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

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

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

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

Предположим, что для t=0 (т.е. для исходнойтаблицы) все a_ij – целые и столбцы

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

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

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

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

можно записать:

где

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

(r_y – неотрицательный остаток от деления нацело y на). В частности, . Поэтому если , то и r = 1. Если , то и r = 0.

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

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

где x – соответствующая компонента вектора

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

, а - текущие небазисныепеременные. Можно выразить x, a_{0 и} a_j,используя введенное выше представление (14):

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

Поскольку

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

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

.

Целочисленная слабая переменная s являетсянеотрицательной. Действительно, если бы s было отрицательным, т.е.принимало бы значения -1, -2, …, тоумножение на

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

сделалобы всю правую часть уравнения (18) отрицательной, в то время как левая частьнеотрицательна.

Рассмотрим два случая

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

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

читать дальше

4