назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [ 16 ] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]


16

раничений, переменных и матрицы, содержащей коэффициенты функций ограничений. Важно отметить, что эти данные определяются пользователем до начала использования модели. На рис. 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 для того, чтобы можно было сравнить модели



в LINGO и AMPL). Далее с помощью оператора param задаются имена элементов целевой функции и ограничений. Так, С определяет коэффициенты целевой функции как функция множества Var. Rhs определяет значения правых частей ограничений как функция множества Constr, a Aij - коэффициенты левых частей ограничений как функция множеств Constr и Var.

Global optimal solution found at step: 4

Objective value: 21.00000

Model Title: REDDY MIKKS MODEL

Variable

Value

Reduced Cost

RHS (

00000

.000000

RHS (

.00000

.000000

RHS( DEMAND1)

.00000

,000000

RHS( DEMAND2)

,00000

.000000

,00000

.000000

,00000

.000000

,00000

,000000

,50000

.000000

AIJ( Ml,

,00000

.000000

AIJ( Ml,

,00000

.000000

AIJ( M2,

,00000

.000000

AIJ( M2,

,00000

.000000

AIJ( DEMAND1,

00000

,000000

AIJ( DEMAND1,

,00000

,000000

AIJ( DEMAND2,

0.000000

,000000

AIJ( DEMAND2,

00000

,000000

Slack oc Surplus

Dual Pcice

21.0000

1.00000

0.000000

0.750000

0.000000

0.500000

2.50000

0.000000

0 . 500000

0.000000

Рис. 2.13. Выходной отчет программы LINGO

!Модель Reddy Mikks - входные данные во внешних файлах; MODEL:

TITLE Reddy mikks model;

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

SETS :

Constr: Rhs;

Vac: С, X;

ConsVar(Constr,Van): Aij; ENDSETS

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

MAX=@SUM( Var (j) : C(j)*X(j) ); !целевая функция;

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

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

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

DATA:

Constr=@FIL,E(ch2LingoFldata.lng) ; !чтение из файла; Rhs = 24 б 1 2; Var = XI Х2; С = 5 4;

Aij=@FILE (ch2LingoFldata.lng) ; !чтение из файла; EHDDATA END

Рис. 2.14. Листинг LINGO модели Reddy Mikks с внешними файлами

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [ 16 ] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147] [148] [149] [150] [151] [152] [153] [154] [155] [156] [157] [158] [159] [160] [161] [162] [163] [164] [165] [166] [167] [168] [169] [170] [171] [172] [173] [174] [175] [176] [177] [178] [179] [180] [181] [182] [183] [184] [185] [186] [187] [188] [189] [190] [191] [192] [193] [194] [195] [196] [197] [198] [199] [200] [201] [202] [203] [204] [205] [206] [207] [208] [209] [210] [211] [212] [213] [214] [215] [216] [217] [218] [219] [220] [221] [222] [223] [224] [225] [226] [227] [228] [229] [230] [231] [232] [233] [234] [235] [236] [237] [238] [239] [240] [241] [242] [243] [244] [245] [246] [247] [248] [249] [250] [251] [252] [253] [254] [255] [256] [257] [258] [259] [260] [261] [262] [263] [264] [265] [266] [267] [268] [269] [270] [271] [272] [273] [274] [275] [276] [277] [278] [279] [280] [281] [282] [283] [284] [285] [286] [287] [288] [289] [290] [291] [292] [293]