Промышленный лизинг Промышленный лизинг  Методички 

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

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

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



F

J К

Общая сетевая модель

2 Входные данные:

3 К-во п. отправления

маюимум 10

К-во п. назначения

максимум 10

Пр.способностьи пи

изыемиетенз

V, \ * М8ется пр способность

Матрица удельных стоимостей

1!.

Предложение

S1

ипрос

Оптимальное решение:

Промежуточные вычисления:

Общая стоимость

Узел

Поток

Спрос

Уд. стоимость

От-в

Поток

Пр спос.

. 1S

S1-D1

99959

1 25

SI - D2

999999

S1 - D3

999999

7 11

S1 -D4

999999

4 ,2

S2-D1

999999

S2-D2

999999

S2-D3

999999

S2-D4

999999

S3-D1

999999

S3-D2

999999

S3-D3

999999

S3-D4

999999

34

Поиск решения

Установить целевую чайку: Равной; 11мсииальнаму значению С

Р ницимапьному значению Изменяя ячейки:-

$В$22:$В$ЗЭ

Ограничения:-

JB$22:$B$33 <=$C$22:$C$33 F$21:$F$27 = $G$21:$G$27


Рис. 5.6. Решение примера 5.3.1, полученное с использованием сетей

Можно также наложить ограничения на пропускные способности на различных маршрутах транспортной модели. Сначала введите латинскую букву у (без кавычек) в ячейку В5. В результате будут созданы и соответствующим образом озаглавлены ячейки в диапазоне N8:W17, в которые можно ввести ограничения пропускной способности маршрута. Если пропускная способность маршрута не ограничена, то соответствующая ячейка должна остаться пустой. После этого ограничения пропускной способности с помощью функции ИНДЕКС будут автоматически скопированы в столбец С (начиная с ячейки С22). Число 999 999 представляет неограниченную пропускную способность.



Теперь для решения задачи осталось только задать параметры средства Поиск решения. Целевая ячейка уже содержит следующую общую формулу, которую не нужно изменять для моделей, размер которых не превышает 10 х 10.

=CyMMnPOH3B(B22:B122;J21:J121)

Осталось заполнить поля Изменяя ячейки и Ограничения в диалоговом окне средства Поиск решения. На рис. 5.6 показано, что в поле Изменяя ячейки содержится ссылка $В$22:$В$33.

В строках 22:33 содержатся все возможные маршруты модели, которые изменяются в соответствии с размерами транспортной задачи.

Ограничения можно сформулировать следующим образом.

Поток на маршруте (/, ;) < пропускной способности на маршруте (/, j), (входной поток - выходной поток) через узел = спрос в узле

Для первого множества ограничений левая часть выражения соответствует значениям в столбце В (начиная с ячейки В22), а правая часть - значениям в столбце С (начиная с ячейки С22). Например, на рис. 5.6 первой группе ограничений соответствует такое выражение.

$В$22:$В$33 <= $С$22:$С$33

Значения для второго множества ограничений содержатся в столбцах F и G, а выражение выглядит следующим образом.

$F$21:$F27 = $G$21:$G$27

Условия неотрицательными можно задать в диалоговом окне Параметры поиска решения, которое появляется после щелчка на кнопке Параметры в окне средства Поиск решения6.

Решение транспортной задачи в программе LINGO. На рис. 5.7 представлена модель LINGO для транспортной задачи примера 5.3.1 (файл ch5LingoTrans.lg4). Используемые в модели имена не нуждаются в пояснениях. Обратите внимание на то, что имена пунктов отправлений (SI, S2, S3) и пунктов назначений (Dl, D2, D3, D4) можно ввести так, как показано на рисунке, вместо того, чтобы включать их в раздел DATA (Данные) модели.

УПРАЖНЕНИЯ 5.3.2

1. В табл. 5.26 приведены исходные данные (в долл.) для трех транспортных задач.

a) Используя начальное решение, полученное методом северо-западного угла, найдите их оптимальное решение.

b) В программе TORA сравните начальные решения, полученные методами северо-западного угла, наименьшей стоимости и Фогеля.

c) Решите задачи с помощью средства Excel Поиск решения.

d) Решите задачи с помощью программы LINGO.

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



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