Формулирайте модела | Проба и грешка | Решете модела
Използвайте решателя в Excel за да намерите най -краткия път от възел S до възел Т в ненасочена мрежа. Точките в мрежата се наричат възли (S, A, B, C, D, E и T). Линиите в мрежата се наричат дъги (SA, SB, SC, AC и т.н.).
Формулирайте модела
Моделът, който ще решим, изглежда както следва в Excel.
1. За да формулираме това проблем с най -краткия път, отговорете на следните три въпроса.
а. Какви решения трябва да се вземат? За този проблем се нуждаем от Excel, за да разберем дали дъгата е на най -краткия път или не (Да = 1, Не = 0). Например, ако SB е част от най -краткия път, клетка F5 е равна на 1. Ако не, клетка F5 е равна на 0.
б. Какви са ограниченията на тези решения? Нетният поток (Flow Out - Flow In) на всеки възел трябва да бъде равен на предлагане/търсене. Възел S трябва да има само една изходяща дъга (Net Flow = 1). Възел Т трябва да има само една входяща дъга (Net Flow = -1). Всички останали възли трябва да имат една изходяща дъга и една входяща дъга, ако възелът е на най -краткия път (Net Flow = 0) или няма поток (Net Flow = 0).
° С. Каква е общата мярка за изпълнение на тези решения? Общата мярка за изпълнение е общото разстояние на най -краткия път, така че целта е да се намали това количество.
2. За да направите модела по -лесен за разбиране, създайте следните именовани диапазони.
| Име на диапазон | Клетки |
|---|---|
| От | В4: В21 |
| Да се | С4: С21 |
| Разстояние | D4: D21 |
| Отивам | F4: F21 |
| NetFlow | I4: I10 |
| SupplyDemand | K4: K10 |
| TotalDistance | F23 |
3. Вмъкнете следните функции.
Обяснение: Функциите SUMIF изчисляват нетния поток на всеки възел. За възел S функцията SUMIF сумира стойностите в колоната Go с „S“ в колоната From. В резултат на това само клетка F4, F5 или F6 може да бъде 1 (една изходяща дъга). За възел T функцията SUMIF сумира стойностите в колоната Go с „T“ в колоната To. В резултат на това само клетка F15, F18 или F21 може да бъде 1 (една входяща дъга). За всички други възли Excel търси в колоната От и До. Общото разстояние се равнява на произхода на Distance и Go.
Проба и грешка
С тази формулировка става лесно да се анализира всяко пробно решение.
1. Например, пътят SBET има общо разстояние 16.
Не е необходимо да използвате опит и грешка. След това ще опишем как Excel Solver може да се използва за бързо намиране на оптималното решение.
Решете модела
За да намерите оптималното решение, изпълнете следните стъпки.
1. В раздела Данни в групата Анализ щракнете върху Решител.
Забележка: не можете да намерите бутона Solver? Щракнете тук, за да заредите добавката Solver.
Въведете параметрите на решавача (прочетете нататък). Резултатът трябва да е в съответствие със снимката по -долу.
Имате избор да въведете имената на диапазоните или да щракнете върху клетките в електронната таблица.
2. Въведете TotalDistance за целта.
3. Щракнете върху Мин.
4. Въведете Go за промяна на променливите клетки.
5. Щракнете върху Добавяне, за да въведете следното ограничение.
6. Поставете отметка в „Неограничени променливи като отрицателни“ и изберете „Simplex LP“.
7. Накрая щракнете върху Решаване.
Резултат:
Оптималното решение:
Заключение: SADCT е най -краткият път с общо разстояние 11.
