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


[Старт] [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]


15

личное представление модели более понятным и удобочитаемым. Относительное расположение ячеек, содержащих информацию разных типов, не обязательно должно быть таким, как показано на рис. 2.10. Например, ячейки, содержащие значения переменных и целевой функции, не обязательно должны располагаться в одном непрерывном диапазоне ячеек или внизу таблицы - часто их размещают в верхней части табличной модели. Важно только то, чтобы они находились в отдельных ячейках и на них можно было бы сослаться при задании параметров средства Поиск решения. Вместе с тем мы рекомендуем придерживаться структуры табличной модели, как показано на рис. 2.10, поскольку она наглядна и удобна в работе.

Покажем соответствие между математической моделью и табличной. Начнем с соответствия формул этих моделей. Коэффициенты целевой функции и левых частей ограничений помещены в диапазон ячеек В5:С9. В следующей таблице приведены алгебраические формулы и эквивалентные им формулы Excel и ячейки, в которых эти формулы записаны.

Алгебраическая формула

Формула Excel

Ячейка

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

5xi +4хг

=В5*В$13+С5*С$13

Ограничение 1

6X1 + 4X2

=В6*В$13+С6*С$13

Ограничение 2

Xi + 2X2

=В7*В$13+С7*С$13

Ограничение 3

- Xi + Хг

=В8*В$13+С8*С$13

Ограничение 4

0xi + хг

=В9*В$13+С9*С$13

Отметим, что вы должны ввести формулу только в ячейку D5, а затем ее надо скопировать в ячейки D6:D9. Чтобы правильно скопировать формулы, в формуле ячейки D5 надо ссылки на ячейки В13 и С13 (содержащих значения хх и х2) сделать абсолютными в виде $В$13 и $С$13. Для больших табличных моделей в ячейку D5 можно ввести формулу

= СУММПРОИЗВ(В5:С5;$В$13:$С$13) и затем скопировать ее в ячейки D6:D9.

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

в поле ввода Установить целевую ячейку вводится D5;

устанавливается переключатель Равной максимальному значению;

в поле ввода Изменяя ячейки вводится $В$13:$С$13.

Эта информация указывает средству Поиск решения, что переменные находятся в ячейках В13 и С13, и надо найти максимум целевой функции, значение которой вычисляется в ячейке D5.

Далее надо задать ограничения модели, щелкнув на кнопке Добавить в диалоговом окне Поиск решения. Отрывшееся диалоговое окно Добавление ограничения предоставляет средства для ввода всех частей ограничений (левой части, знака неравенства и значения правой части). Используя это окно, вводим ограничения модели в таком виде.

$D$6:$D$9<=$F$6:$F$9



Напомним, что в ячейках F6:F9 записаны значения правых частей ограничений. Теперь осталось ввести ограничения неотрицательности для переменных. С помощью диалогового окна Добавление ограничения вводим

$В$13:$С$13>=0

Когда Поиск решения найдет решение данной задачи, оптимальное значение целевой функции появится в ячейке D5, а значения переменных хх и х2 - в ячейках В13 и С13 соответственно. Для удобства мы используем ячейку D13 для отображения значения целевой функции (в эту ячейку введена формула =D5) - в этом случае все элементы оптимального решения отображаются рядом в одной строке.

Теперь все готово для решения нашей задачи, достаточно щелкнуть на кнопке Выполнить в диалоговом окне Поиск решения. Но перед этим желательно проверить установленные параметры работы средства Поиск решения (максимальное время поиска решения, максимальное количество итераций, относительная погрешность и т.д.), для чего надо открыть диалоговое окно Параметры поиска решения, щелкнув на кнопке Параметры. Самое важное - установить опцию Линейная модель. В этом же окне можно указать, что все переменные должны быть неотрицательными (опция Неотрицательные значения).6

Если табличная модель создана правильно, то решение появится в выходных ячейках табличной модели (в нашем случае в ячейках B13:D13). Также появится новое диалоговое Результаты поиска решения, которое даст возможность получить более детальную информацию о решении в виде отчетов, включая важный отчет по устойчивости. Эти отчеты формируются на отдельных листах рабочей книги. На рис. 2.11 показан отчет по устойчивости для модели Reddy Mikks. Информация в этом отчете полностью совпадает с той, что предоставляет программа TORA, и интерпретируется аналогичным образом. Заметим, что здесь теневая цена - то же самое, что dual price (двойственная цена) в отчете программы TORA.

Необходимо подчеркнуть, что описанная табличная модель Reddy Mikks построена и решена "прямолинейно". Другие модели могут потребовать определенных ухищрений и преобразований для того, чтобы к ним можно было применить средство Поиск решения. Один класс таких моделей ЛП, а именно сетевых моделей, будет рассмотрен в главе 6.

2.4.3. Решение задач ЛП с помощью LINGO и AMPL

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

Для выполнения таких задач существует несколько коммерческих программных пакетов, среди которых назовем AMPL, GAMS, LINGO и MPL. Основная идея

Необходимо предостеречь от некоторых "причуд" средства Поиск решения. Если вы зададите слишком малое значение Относительная погрешность (например, 0,000000001), то можете получить странное сообщение, что для вашей модели не выполняются предположения о линейности. Также вследствие округления значений в выходных отчетах можно получить не совсем точные значения (например, 1Е-14 вместо 0 или 9,999999999999 вместо 10).



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

А В С D Е

1 , Microsoft Excel 10.0 Отчет по устойчивости

2 s Рабочий лист: [ch2SolverReddyMikks.xlsJJlHCTl

Н Г

5 1 Изменяемые ячейки

6 i Результ. Нормир. Целевой Допустимое Допустимое

7 Ячейка Имя значение стоимость Коэффициент Увеличение Уменьшение

8 . $В$13 Решение х1 3

9 i $С$13 Решение х2 1,5

3 , 0,666666667

"М.

Л1 [Ограничения

J2j Результ. 13 Ячейка Имя значение

Теневая Цена

Ограничение Правая часть

Допустимое Увеличение

Допустимое Уменьшение

J4 $D$6 Сырье М1 Всего 24 15 $D$7 Сырье М2 Всего 6 •18- $D$8 Спрос 1 Всего -1,5 17; $D$9 Спрос 2 Всего 1.5

0,75 0,5 0 0

24 6 1 2

0,666666667 1Е+30 1Е+30

4 2 2,5 0.5

-ТО - -, ,

И « -» МЛ Отчет по устойчивости 1 / Лист! /

I мг

Рис. 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 пользователем вводятся имена основных компонентов модели ЛП - ог-

[Старт] [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]