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

Рис. 2.11. Отчет по устойчивости

В этом разделе кратко опишем два популярных пакета решения задач оптимизации: LINGO и AMPL. Это описание по понятным причинам не будет очень подробным и всесторонним, но, вместе с тем, даст общее представление о том, как работают эти пакеты. Оба этих пакета имеют специальные обучающие версии, которые можно загрузить с Web-узлов www. lingo. com и www. ampl. com.

Моделирование в LINGO. На рис. 2.12 показан листинг модели Reddy Mikks, созданный в LINGO (файл ch2LingoReddyMikks.lng). В этом листинге служебные слова LINGO записаны прописными буквами и выделены полужирным начертанием (на самом деле язык LINGO не чувствителен к регистру символов), остальные элементы листинга записаны пользователем.

В листингах LINGO строки, начинающиеся с восклицательного знака, являются комментариями и игнорируются процессором LINGO. Все стандартные операторы, включая комментарии, должны заканчиваться точкой с запятой. Служебные слова MODEL, SETS и DATA должны заканчиваться двоеточием, однако служебные слова END, ENDSETS и ENDDATA (закрывающие операторные скобки) не требуют в конце каких-либо знаков препинания.

В модели на рис. 2.12 входные данные содержатся внутри модели, что не удобно, если необходимо найти решение одной и той же модели для разных исходных данных. Ниже мы покажем, как можно выйти из этой ситуации путем сохранения данных в отдельных внешних файлах.

Оператор TITLE предваряет название модели. В операторных скобках SETS: ENDSETS пользователем вводятся имена основных компонентов модели ЛП - ог-

раничений, переменных и матрицы, содержащей коэффициенты функций ограничений. Важно отметить, что эти данные определяются пользователем до начала использования модели. На рис. 2.12 видно, что мы использовали имена Constr (Ограничения), Var (Переменные) и ConsVar(Constr,Var) (это массив коэффициентов, размерности ConstrxVar). Конечно, вы можете использовать любые другие

Шодель Reddy Mikks - данные внутри модели; MODEL:

TITLE Reddy mikks model;

I--------------------алгебраическое определение модели ЛП;

SETS:

Constr: Rhs; Var: С, X;

ConsVar (Constr, Var) : Aij ; ENDSETS

1------------------------------------построение модели;

MM-esUM( Var(j) : C(j)*X(j) ); ! целевая функция;

SFOR( Ограничения;

Constr (i) : esiM( Var (j) : Aij (i, j ) *X (j) )<=Rhs (i) ) ;

I------------------------------------данные для модели;

DATA:

Constr = Ml M2 Demandl Demand2; Rhs = 24 6 1 2; Var = XI X2; С = 5 4; Aij =64

-1 1

0 1;

E HDD AT A END

Рис. 2.12. Листинг LINGO модели Reddy Mikks

имена по вашему выбору. Ограничения имеют числовые значения правой части, вектор этих значений назовем Rhs (от Right-hand side - правая часть). Отношение между ограничениями и их правыми частями задается оператором Constr: Rhs; Аналогично оператор Var: С, X;

указывает, что каждой переменной X соответствует в целевой функции коэффициент С (X и С - векторы). Наконец, матрица, содержащая коэффициенты функций ограничений, названа Aij с помощью оператора

ConsVar(Constr,Var): Ai j ;

Теперь заданы все элементы, необходимые для построения алгебраической модели. Используя фиктивный индекс j для представления переменной у, целевая функция строится как

MAX=@SUM( Var(j): C(j)*X(j) );

Этот оператор задает целевую функцию как сумму произведений C(j)*X(j), причем сумма берется по всем элементам множества Var(j). Ограничение i строится следующим образом:

Constr (i) :@STJM( Var(j): Aij (i, j ) *X (j ) )<=Rhs(i)

Для вычисления всех ограничений из множества Constr(i) используется цикл

@FOR(Constr(i):

@SUM( Var(j): Aij(i,j)*X(j) )<=Rhs(i) ) ;

Отметим, что тело цикла @FOR ограничивается круглыми скобками.

Последний раздел листинга на рис. 2.12 содержит данные, подставляемые в алгебраическую модель. Так, множество Constr определяется как множество из четырех ограничений, названных Ml, М2, Demandl и Demandl (Cnpocl и Спрос2). Отметим обязательные пробелы между именами - по их числу определяется количество элементов в множестве. В следующей строке вектору Rhs присваиваются значения правых частей ограничений 24, 6, 1 и 2. Элементам множества Var обычно даются имена XI и Х2 (если модель имеет только две переменные). Соответственно, С присваиваются два элемента, 5 и 4, значения коэффициентов целевой функции. Наконец, массиву Aij присваиваются значения коэффициентов левых частей ограничений в соответствии с определением множества ConsVar(Constr,Var). Не обязательно помещать элементы каждого ограничения в отдельной строке, как в листинге на рис. 2.12. Здесь это сделано для удобства чтения.

По умолчанию в LINGO предполагается, что все переменные неотрицательны. Свободные переменные (т.е. такие, которые могут принимать как положительные, так и отрицательные, значения) задаются с помощью оператора @FREE. Например, если Х2 - свободная переменная, то в модели она должна быть описана оператором @FREE(X(2));

Этот оператор можно вставить в любое место листинга после оператора ENDSETS, даже в оператор цикла.

Стандартный выходной результат работы программы LINGO представлен на рис. 2.13. Оптимальное решение записано как Х(Х1) = 3 и Х(Х2) = 1.5 со значением целевой функции 21. В нижней части выходного отчета выводится список значений дополнительных переменных для каждого ограничения (строки 2- 5) вместе с соответствующими двойственными ценами (столбец Dual Prices). В строке 1 приведено значение целевой функции. Остальные значения в выходном отчете повторяют входные данные модели.

Выходной отчет программы LINGO можно настраивать, выводя только необходимые данные. Отметим, что в этот отчет не включаются автоматически результаты анализа чувствительности оптимального решения. Вместе с тем LINGO предоставляет возможности проведения такого анализа и вывода его результатов.

Мощность и гибкость таких программ, как LINGO, заключается в том, что входные данные модели не обязательно должны быть включены непосредственно в модель, как это сделано в листинге на рис. 2.12. Входные данные могут находиться во внешних файлах. На рис. 2.14 показан листинг модели Reddy Mikks, где с помощью оператора @FILE присоединяются два внешних файла. Содержимое этих файлов показано на рис. 2.15. Таким образом, заменяя эти файлы другими, можно просчитывать модель для разных входных данных.

Моделирование в AMPL. Используем ту же модель Reddy Mikks для описания работы программы AMPL. На рис. 2.16 показан листинг этой модели, созданный в AMPL (файл ch2AmplReddyMikks.mod). Как и в примере LINGO, служебные слова AMPL здесь выделены полужирным шрифтом.

Первым в листинге стоит оператор set, определяющий ограничения и переменные модели с помощью задаваемых пользователем имен Constr и Var (мы сохранили здесь имена из модели LINGO для того, чтобы можно было сравнить модели