Обобщенные целочисленные переменные

Простейшим примером использования обобщенных целочисленных переменных может служить модель, не использующая множества. Например, модель:

MODEL:

MAX = X;

X + Y = 25.5

X <= Y;

END

… вернет для X решение 12.75. Добавление строки

@GIN(X);

…принудительно заставит переменную X принимать только целые значения. В данном случае оптимальным значением будет 12. (Заметим, что простое округление значение X до 13 не было бы допустимым решением в этом примере).

Частным случаем, где целочисленные переменные доказывают свою полезность, является задача составления штатного расписания. Следующий пример (файл STAFF.LNG в поддиректории «SAMPLES») является моделированием типичной ситуации для работодателя: необходимо обеспечить дневные потребности в рабочей силе при минимальных затратах. Сотрудники должны работать последовательно 5 дней с двумя днями выходных, и вам следует определить, сколько сотрудников должны начинать работу в каждый из дней недели.

STAFF.LNG

MODEL:

1] SETS:

2] DAY / MON, TUE, WED, THU, FRI, SAT, SUN/:

3] NEED, START, COST;

4] ENDSETS

5]! Целевая фанкция;

6] [OBJ]MIN=@SUM(DAY(TODAY):START(TODAY)*COST(TODAY));

7]

8]! Ограничения;

9] @FOR(DAY(TODAY):

10] @SUM(DAY(COUNT)| COUNT #LE# 5:

11]START(@WRAP(TODAY-COUNT+1,@SIZE(DAY))))>=NEED(TODAY));

12]

13] DATA:

14] NEED = 18, 15, 12, 16, 19, 14, 12;

15] COST = 200, 200, 200, 200, 200, 200, 200;

16] ENDDATA

END

К данному моменты вы, конечно, уже имеете представление о моделях LINGO, но тем не менее приведем на всякий случай объяснение каждой строки, чтобы не осталось никаких неясностей.

Секция SETS определяет множество дней недели с атрибутами для каждого дня NTTD, START и COST, которые представляют соответственно потребности в рабочей силе (количество работников) на каждый день, количество сотрудников, начинающих работу в данный день, и затраты (выплату недельного пособия) каждому из этих работников. Значения для NEED и COST поставляются в секции DATA, в то время как атрибуты STARTS являются искомыми (неизвестными) при решении модели.

Строка с целевой функцией (с меткой [OBJ]) сообщает LINGO, что следует минимизировать по всем дням недели DAY(TODAY) (индекс TODAY пробегает значения всех дней недели) сумму плановых затрат: сумму (SUM) произведений числа работников START (TODAY), начинающих работу в этот день, на недельное пособие (COST) каждому из начинающих работу сотруднику.

Единственное ограничение, присутствующее в модели, звучит так: для каждого дня DAY(TODAY) сумма всех сотрудников, работающих в этот день, должна быть не меньше потребностей в рабочей силе на этот день. В тексте модели оно появляется в следующем виде:

@FOR(DAY(TODAY):

@SUM(DAY(COUNT)| COUNT #LE# 5:

START(@WRAP(TODAY-COUNT+1,@SIZE(DAY))))>=NEED(TODAY));

Небольшое отступление. Количество сотрудников, работающих в конкретный день, вычисляется с помощью функций @SIZE и @WRAP. Функция @SIZE(имя_множества) возвращает количество элементов множества. В данном частном примере @SIZE(DAYS) возвращает число 7 — количество дней недели.

Функция @WRAP(I,N) возвращает I, если I находится в интервале от 1 до N. В противном случае (I вне интервала) функция вычитает N из положительного I (или прибавляет N к отрицательному I) до тех пор, пока I не окажется в интервале., и возвращает полученное I. Например, @WRAP(5,7) возвратит 5, @WRAP(9,7) возвратит 9–7=2. Таким образом, функция циклически возвращает вас к началу (или концу) последовательности. Это особенно полезно в моделях, подобной нашей, когда оптимизируется циклический процесс по временному диапазону.

В данном примере мы используем @WRAP для суммирования работников, занятых в заданный день. Эта сумма складывается из сотрудников, приступивших к работе в рассматриваемый день, плюс каждый из приступивших к работе в предыдущие четыре дня. Например, присутствующие на работе в субботу — это те, кто приступил к работе в субботу, плюс те, кто приступи к работе в пятницу, четверг, среду и вторник. Те, кто приступил к работе в воскресенье и понедельник, не работают в субботу.

Таким образом, ограничение утверждает: для каждого DAY(TODAY) вычислить сумму (SUM), начинающих работу (STARTS) для каждого из COUNT дней, при условии, что COUNT меньше или равно 5 (пятидневная рабочая неделя), начиная с дня TODAY и во все предыдущие четыре дня. А также, что результирующая сумма для дня TODAY должна быть больше или равна NEED (потребность) для этого дня TODAY.

Ниже показана интересующая нас часть решения сформулированной модели:

OPTIMUM FOUND AT STEP 7

OBJECTIVE VALUE = 4240.00000

VARIABLE VALUE REDUCED COST

START(MON) 6.600000.0000000

START(TUE) 2.600000.0000000

START(WED).6000000.0000000

START(THU) 5.600000.0000000

START(FRI) 3.600000.0000000

START(SAT) 1.600000.0000000

START(SUN). 6000000. 0000000

Вряд ли нас устроит решение, в котором работу в понедельник должны начинать 6.6 сотрудника. Хотя может быть искусный хирург и сможет что-либо сделать с 0.6 часть человека, маловероятно, что такая часть сможет сделать что-либо полезное на работе. Мы исправим положение, добавив ограничение целочисленности переменной, используя функцию @GIN:

MODEL:

SETS:

DAY / MON, TUE, WED, THU, FRI, SAT, SUN/:

NEED, START, COST;

ENDSETS

! Целевая функция;

[OBJ]MIN=@SUM(DAY(TODAY):START(TODAY)*COST(TODAY));

! Ограничения;

@FOR(DAY(TODAY): [DAY]

@SUM(DAY(COUNT)| COUNT #LE# 5:

START(@WRAP(TODAY- COUNT+1,@SIZE(DAY))))>=NEED(TODAY));

! Мы хотим, чтобы START была целой;

@FOR(DAY(TODAY): @GIN(START(TODAY)));

DATA:

NEED = 18, 15, 12, 16, 19, 14, 12;

COST = 200, 200, 200, 200, 200, 200, 200;

ENDDATA

END

Новое добавление достаточно очевидно. В каждый из дней атрибут START должен быть целым. Новое решение выглядит так:

VARIABLE VALUE REDUCED COST

START(MON) 8.000000 200.0000

START(TUE) 1.000000 200.0000

START(WED) 1.000000 200.0000

START(THU) 6.000000 200.0000

START(FRI) 3.000000 200.0000

START(SAT) 3.000000 200.0000

START(SUN).0000000 200.0000

ROW SLACK OR SURPLUS DUAL PRICE

OBJ 4400.000 1.000000

Хотя получен результат с несколько более высокими затратами, оно имеет несомненное улучшение, поскольку содержит только целых работников.

Теперь несколько слов о бинарных целых.

Дата добавления: 2015-11-16