выбор, цвет ячеек изменится (зеленый для вводимых переменных, красный для исключаемых переменных и серый для остальных).
На рис. 5.4 представлено решение задачи из примера 5.3.1, полученное в системе TORA с применением метода северо-западного угла.
Рис. 5.4. Решение в системе TORA транспортной задачи из примера 5.3.1
Средство Excel Поиск решения. Ввод данных транспортной модели в рабочую книгу Excel не вызывает затруднений. На рис. 5.5 показан пример решения задачи из примера 5.3.1 (файл ch5SolverTransportation.xls). Этот шаблон может быть использован для решения моделей, которые состоят из не более 10 пунктов отправления и не более 10 пунктов назначения. Рабочий лист состоит из разделов входных и выходных данных. В разделе входных данных обязательно должны содержаться следующие данные: количество пунктов отправлений (ячейка ВЗ), количество пунктов назначений (ячейка В4), транспортная таблица, т.е. матрица стоимостей (диапазон В6:К15)6, названия пунктов отправления (диапазон А6:А15), названия пунктов назначения (диапазон В5:К5), объемы предложения (диапазон L6:L15) и спрос (диапазон В16:К16). В разделе выходных данных (диапазон В20:К29) содержится оптимальное решение в матричном виде, которое вычисляется автоматически. Соответствующее значение общей стоимости вычислено в ячейке А19. Размер модели был ограничен до 10 х 10 для того, чтобы все данные поместились на экране. Ниже приведем подробные объяс-нения того, как можно создать в Excel табличную модель, размер которой регулируется пользователем.
На рис. 5.5 часть строк этого диапазона и диапазона В20:К29 скрыты. - Прим. ред.
| | | : Ох- | | | | | L.h | | L J | | |
| Входные данные | | | | | | | | | | | |
| К-во п. отправления | | «максимум 10 | | | | | | | | |
| К-во п. назначения | | | | | | | | | | |
| Матрица стоимостей | | | | | | | | | Предложение |
| | | | | | |
| | | | | | |
| | | | 16 - | | |
| | | | | | |
| Спрос | | | | | | | | | | | |
| Оптимальное решение |
| Общая стоимость | | | | | | | | | | | |
| | | | | | | | | | | | |
| | | | | | | | | | | | |
| | | | | | | | | | | | |
| | | | | | | | | | | | |
| | | | | | | | | | | | |
| | | | | | | | | | | |
| | | | | |
Пг)игк рршениа | | | | | | | | |
Установить целевую ячейку: $А$19~4j Равной: с иагеииальному значению *~ значению: (о~
иадтальному значению , Изменяя ячейки:
Ограничения:
Выполнить I Закрыть
*М Предгтопоасить I
$8$30:$К$30 = *в$16:$К$16 tl$20:*L$29 = $L$6:tL$15
Рис. 5.5. Решение задачи из примера 5.3.1, полученное с помощью средства Поиск решения
После ввода исходных данных откройте средство Поиск решения и щелкните на кнопке ОК. Решение появится в диапазоне В20:К29.
Для создания транспортной модели в рабочий лист необходимо ввести следующие формулы.
Формула вычисления значения целевой функции в ячейке А19: =СУММПРОИЗВ(В6:К15;В20:К29).
Объемы перевозки от пунктов отправления: в ячейку L20 сначала введится формула =СУММ(В20:К20), после чего она копируется в диапазон L21:L29.
Объемы перевозки до пунктов назначения: в ячейку В30 вводится формула =СУММ(В20:В29), затем она копируется в диапазон С30:К30.
Ограничения модели связаны с отношениями объемов перевозок и объемов предложения в пунктах отправления и спросом в пунктах назначения. Ограничения формируются в виде следующих равенств
$L$20:$L$29=$L$6:$L$15 $В$30:$К$30=$В$16:$К$16
На основе этих входных данных можно получить еще одну интересную формулировку транспортной модели. Различия проявятся в структуре выходных данных и в определении параметров средства Поиск решения. В модель также добавится раздел промежуточных вычислений - ключевая часть табличной модели. В нашей модели разделы выходных данных и промежуточных вычислений будут полностью автоматизированы. Пользователю достаточно будет ввести параметры средства Поиск решения (и исходные данные, конечно же).
На рис. 5.6 показано решение примера 5.2.5 с использованием новой формулировки задачи (файл ch5SolverNetworkBasedTransportation.xls). Решение задачи находится в столбце В (начиная с ячейки В22) под заголовком "Поток". Названия маршрутов были сгенерированы автоматически на основе названий пунктов отправления и назначения в разделе входных данных и находятся в столбце А (начиная с ячейки А22 и ниже).
Основные формулы, с помощью которых вычисляется оптимальное решение, содержатся в разделе промежуточных вычислений. В столбце Е (начиная с ячейки Е21) находятся порядковые номера пунктов отправлений и назначений, причем сначала идут пункты отправлений. Эта информация, а также номера пунктов отправлений и назначений используются для числового представления путей модели. Например, пункт отправления 1 (ячейка Н21) в пункт назначения 4 (ячейка 121) обозначают путь от пункта отправления S1 в пункт назначения D1.
На основе информации из столбцов Н и I в столбце F (начиная с ячейки F21) строятся формулы для вычисления потока через узел. В частности, в ячейке F21 содержится следующая формула5.
=СУММЕСЛИ($Н$21:$Н$121;$Е21;$В$22:$В$122)--СУММЕСЛИ($1$21:$1$121;$Е21;$В$22:$В$122)
Затем эта формула была скопирована в диапазон F22:F121.
В сущности, в формуле СУММЕСЛИ вычисляется чистый поток (вход-выход) через каждый узел, перечисленный в столбце Е (начиная с ячейки Е21). Важно отметить, что в данной стандартной транспортной модели с помощью формулы можно эффективно вычислить сумму выходных потоков из каждого пункта отправления или сумму входных потоков в каждый узел пункта назначения. Несмотря на то что необходимо использовать две отдельные формулы для представления выходных потоков в пунктах отправлений и входных потоков в пунктах назначений, при использовании основных сетевых моделей (которые обсуждаются в главе 6) все вычисления можно объединить в одной формуле.
Для каждого узла величина потока вычисляется по формуле:
входной поток - выходной поток = чистый поток.
Нам необходимо определить объем чистого потока для каждого узла. В столбце G (начиная с ячейки G21) содержатся данные, которые автоматически копируются из раздела входных данных с помощью функции ИНДЕКС. Заметьте, что чистый поток для узла пункта отправления имеет положительный знак, в то время как для узлов пунктов назначения чистый поток имеет отрицательное значение. Необходимость использования отрицательных значений чистого потока для узлов пунктов назначений обусловлена тем, как определен поток через узлы сети в столбце F.
Идея использования функции СУММЕСЛИ для представления баланса потоков в сети позаимствована из статьи С. Т. Ragsdale, "Solving Network Flow Problems in a Spreadsheet", COMPASS News, No. 2, Spring 1996, pp. 4, 5. Остальная часть таблицы, частичная автоматизация вычислений и раздел промежуточных вычислений разработаны автором.