книги / Моделирование и оптимизация в LINGO

Допустим, множество FOODS с атрибутом Prod содержит 10 продуктов, и из первых трех в рацион можно включить не более одного. Такое требование будет учтено записью

@SOS1('DIET', Prod(1)); @SOS1('DIET', Prod(2));

@SOS1('DIET', Prod(3));

Очевидно, что возможен вариант и с использованием функции цикла:

@FOR(FOODS(J) | J #LE# 3: @SOS1('DIET', Prod(J)));

В этих примерах набору из первых трех продуктов присвоено имя

DIET.

Если же из этого набора должен войти в рацион только один, то в предыдущих записях достаточно заменить @SOS1 на @SOS3.

Следующий пример отражает требование, чтобы каждый потребитель получал товары только от одного поставщика:

@FOR(CONSUMERS(J): @FOR(SUPPLIERS(I):X(I,J)<= 100*Y(I,J);@SOS3('CONSUM_' + CONSUMERS(J), Y(I,J))));

Здесь Y(I, J) определяет, есть поставки от I к J или нет. Пусть имеем потребителей A,B,C и D. Тогда для каждого потребителя определится свой набор переменных с именами 'CONSUM_A', 'CONSUM_B', 'CONSUM_C' и 'CONSUM_D'. Если условие поставить в виде «не более одного поставщика», то достаточно применить функцию @SOS1 без использования бинарных переменных Y(I, J):

@FOR(CONSUMERS(J): @FOR(SUPPLIERS(I): @SOS1('CONSUM_' + CONSUMERS(J), X(I,J))));

Функция @SOS2 применяется, например, при описании ку- сочно-линейных зависимостей. В этом случае веса точек изломов кусочно-линейной функции будут переменными, к которым относится требование смежности. Очевидно, если вычисляемая точка (аргумент функции) точно соответствует излому, то только один из весов изломов будет равна 1. Если же вычисляемая точка лежит между изломами, то ровно 2 веса будут положительными, в сумме равные 1, а их индексы – смежными. Например, с помощью @SOS2 некоторая кусочно-линейная функция Profit=F(X), описывается линейными зависимостями:

31

Генератор моделей выдаст развернутую модель ограничений на переменные в виде:

MODEL:

@CARD( 'CONSUM_A', X_SUP1_A); @CARD( 'CONSUM_A', X_SUP2_A); @CARD( 'CONSUM_A', X_SUP3_A); @CARD( 'CONSUM_A', X_SUP4_A); @CARD( 'CONSUM_A', 2);

@CARD( 'CONSUM_B', X_SUP1_B); @CARD('CONSUM_B', X_SUP2_B); @CARD( 'CONSUM_B', X_SUP3_B); @CARD( 'CONSUM_B', X_SUP4_B); @CARD( 'CONSUM_B', 3);

END

Функция @SEMIC используется для описания зависимостей с разрывом в нуле. Так, при учете в модели фиксированных затрат на производство или перевозки суммарные затраты равны нулю при нулевом производстве, а при ненулевом – растут пропорционально объему производства со значения, равного фиксированным затратам.

Синтаксис функции @SEMIC имеет вид

@SEMIC(lower_bound,variable,upper_bound);

Из него следует, что при наличии производства или перевозок затраты должны лежать в диапазоне [нижняя граница, верхняя граница].

Примеры:

@SEMIC(5, COST, 40);

В этом случае COST может быть равна нулю либо лежать в диапа-

зоне [5,40].

@FOR( ROUTES: @SEMIC(2, VOLUME, 15));

Здесь накладывается ограничение на объем перевозок по маршрутам: либо не перевозить, либо перевозить не менее двух и не более 15 единиц груза. Как и ранее, границы могут быть заданы символьными константами, значения которых приводятся в секции

DATA или CALC.

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

@PRIORITY(variable_name, relative_priority);

33

отличаются временем tij, необходимым на изготовление одного i-го изделия на j-м оборудовании. При получении заказа на изделия его необходимо распределить по оборудованию так, чтобы выполнить заказ за минимальное время. Следует учесть, что заказ может включать не весь ассортимент изделий, и по технологическим причинам число видов изделий, производимых на одном типе оборудования за время выполнения заказа, ограничено величиной kj.

На основе постановки строим математическую модель задачи

Production в виде:

где xij – количество изделий i-го типа, производимых на j-м оборудовании; bi – заказанное количество изделий i-го типа; yij =1, если на j-м оборудовании производятся i-е изделия, иначе yij = 0; M – большое положительное число; Tj – время работы j-го оборудования.

Приведенная модель содержит 2nm+n переменных, n+m равенств и n+nm неравенств, что говорит о большой размерности задачи для реального производства.

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

MODEL: sets:

PRODUCT: order;

EQUIPMENT /1..3/: TWORK, K; PR_EQ (PRODUCT, EQUIPMENT): T, X; endsets

data:

35

[_5] 7 * X_PR1_1 + 14 * X_PR2_1 + 10 * X_PR4_1 – TWORK_1 = 0; [_6] 11 * X_PR1_2 + 8 * X_PR2_2 + 9 * X_PR4_2 – TWORK_2 = 0; [_7] 9 * X_PR1_3 + 10 * X_PR2_3 + 11 * X_PR4_3 – TWORK_3 = 0; [_8] TIME = @SMAX( TWORK_1, TWORK_2, TWORK_3);

@CARD( 'NAME1', X_PR1_1); @CARD( 'NAME1', X_PR2_1); @CARD( 'NAME1', X_PR4_1); @CARD( 'NAME1', 2); @CARD( 'NAME2', X_PR1_2); @CARD( 'NAME2', X_PR2_2); @CARD( 'NAME2', X_PR4_2); @CARD( 'NAME2', 1); @CARD( 'NAME3', X_PR1_3); @CARD( 'NAME3', X_PR2_3); @CARD( 'NAME3', X_PR4_3); @CARD( 'NAME3', 3);

@GIN( X_PR1_1); @GIN( X_PR1_2); @GIN( X_PR1_3); @GIN(X_PR2_1); @GIN( X_PR2_2); @GIN( X_PR2_3); @GIN( X_PR4_1); @GIN(X_PR4_2); @GIN( X_PR4_3);

END

Как и следовало ожидать, в этой модели присутствуют только те ограничения и переменные, которые соответствуют реальному заказу.

После успешного решения данной модели LINGO выдает стандартный отчет:

37

В первой строке отчета мы видим, что найдено только локальное решение. Этого следовало ожидать, так как построенная модель задачи является нелинейной и целочисленной (класс PINLP). Затем в первой части отчета приводится оптимальное значение критерия, его лучшая граница, величина недопустимости решения, число итераций и полная характеристика модели.

Во второй части отчета выведены исходные данные, имена

(Variable), значения (Value) и оценки переменных (Reduced Cost).

Третья часть относится к строкам модели (Row). В ней показывается, как выполняется соответствующее ограничение: для неравенств <= выдается резерв (Slack), а для неравенства >= – избыток (Surplus). В нашем случае ограничения заданы в виде равенств, поэтому для допустимого решения значения Slack or Surplus равны нулю. Значения, приводимые в столбце двойственных переменных (Dual Price), как и в столбце Reduced Cost второй части отчета, в анализе целочисленных задач не используются. Далее будет дана интерпретация этих величин.

Модель (1)–(6) можно простым преобразованием привести к линейному виду: достаточно исключить из целевой функции взятие максимума, заменив его неравенствами

Тогда в LINGO-модели изменяется только раздел ММ:

MIN = TIME;

@FOR(PRODUCT(I)|order #NE# 0: @SUM(EQUIPMENT(J): X(I,J))=order);

@FOR(EQUIPMENT(J): @SUM(PRODUCT(I)|order #NE# 0: T(I,J)*X(I,J))- TWORK(J)=0);

@FOR(EQUIPMENT: TIME>=TWORK); @FOR(PR_EQ(I,J)|order(I) #NE# 0: @GIN(X));

@FOR( EQUIPMENT(J): @CARD( 'name'+ EQUIPMENT(J), K); @FOR( PRODUCT(I)|order #NE# 0: @CARD('name'+ EQUIPMENT(J), X(I,J))));

Отчет о решении этой модели представим только его началом:

39