Формулирајте модел | Покушај и грешка | Решите модел
Користите решавач у Екцел да пронађем најкраћи пут од чвора С до чвора Т у неусмереној мрежи. Тачке у мрежи се називају чворови (С, А, Б, Ц, Д, Е и Т). Линије у мрежи називају се лукови (СА, СБ, СЦ, АЦ итд.).
Формулирајте модел
Модел који ћемо решити изгледа овако у Екцелу.
1. Да ово формулишем проблем најкраћег пута, одговорите на следећа три питања.
а. Које одлуке треба донијети? За овај проблем потребан нам је Екцел да бисмо сазнали да ли је лук на најкраћој путањи (Да = 1, Не = 0). На пример, ако је СБ део најкраћег пута, ћелија Ф5 је једнака 1. Ако није, ћелија Ф5 је једнака 0.
б. Која су ограничења за ове одлуке? Нето проток (Флов Оут - Флов Ин) сваког чвора требао би бити једнак Понуди/Потражњи. Чвор С би требао имати само један одлазни лук (нето проток = 1). Чвор Т треба да има само један улазни лук (нето проток = -1). Сви други чворови треба да имају један одлазни лук и један улазни лук ако је чвор на најкраћој путањи (нето проток = 0) или без протока (нето проток = 0).
ц. Која је укупна мера учинка ових одлука? Општа мера перформанси је укупна удаљеност најкраћег пута, па је циљ минимизирати ову количину.
2. Да бисте модел лакше разумели, креирајте следеће именоване опсеге.
| Назив опсега | Ћелије |
|---|---|
| Фром | Б4: Б21 |
| До | Ц4: Ц21 |
| Удаљеност | Д4: Д21 |
| Иди | Ф4: Ф21 |
| Нето прилив | И4: И10 |
| Потражња понуда | К4: К10 |
| Укупна раздаљина | Ф23 |
3. Уметните следеће функције.
Објашњење: СУМИФ функције израчунавају нето проток сваког чвора. За чвор С, функција СУМИФ сумира вредности у колони Иди са „С“ у колони Од. Као резултат тога, само ћелије Ф4, Ф5 или Ф6 могу бити 1 (један одлазни лук). За чвор Т, функција СУМИФ сумира вредности у колони Иди са „Т“ у колони То. Као резултат тога, само ћелије Ф15, Ф18 или Ф21 могу бити 1 (један улазни лук). За све остале чворове Екцел тражи у колони Од и До. Укупна удаљеност једнака је супроизводу удаљености и кретања.
Покушаја и грешке
Помоћу ове формулације постаје лако анализирати било које пробно решење.
1. На пример, путања СБЕТ има укупну удаљеност 16.
Није потребно користити покушај и грешку. Следеће ћемо описати како је Екцел Солвер може се користити за брзо проналажење оптималног решења.
Решите модел
Да бисте пронашли оптимално решење, извршите следеће кораке.
1. На картици Подаци у групи Анализа кликните на Решивач.
Напомена: не можете да пронађете дугме за решавање проблема? Кликните овде за учитавање програмског додатка Солвер.
Унесите параметре решавача (читајте даље). Резултат би требао бити у складу са доњом сликом.
Имате избор да откуцате имена опсега или кликнете на ћелије у табели.
2. Унесите ТоталДистанце за циљ.
3. Притисните Мин.
4. Унесите Го за промену променљивих ћелија.
5. Притисните Додај да бисте унели следеће ограничење.
6. Означите „Учини неограничене променљиве негативним“ и изаберите „Симплек ЛП“.
7. На крају кликните на Реши.
Резултат:
Оптимално решење:
Закључак: САДЦТ је најкраћи пут са укупном удаљеношћу од 11.
