Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Телекомунікації
Кафедра:
Не вказано
Інформація про роботу
Рік:
2014
Тип роботи:
Розрахунково - графічна робота
Предмет:
Радіоелектроніка
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Інститут телекомунікацій, радіоелектроніки та електронної техніки
/
Розрахунково-графічна робота
з дисципліни "Комп'ютерна оптимізація проектних рішень"
МЕТА РОБОТИ
Опанування теоретичних засад і набуття навичок практичного застосування інструменту Solver Microsoft Excel для розв'язання традиційної та нетрадиційної транспортної задачі і задач, що зводяться до транспортної.
ЗАВДАННЯ
Варіант 1. Телевізійна компанія планує підключення до своєї кабельної мережі п’яти нових районів. На рисунку нижче показана структура мережі, що буде створюватися, і відстань у км між районами та телецентром (п. 1). Спланувати найкоротшу кабельну мережу.
/
Рис. 1. Структура мережі.
ПОШУК РІШЕННЯ
За справжній пункт пропозиції з обсягом пропозиції 1 приймемо вершину і=1, решту вершин розглянемо як транзитні пункти попиту з обсягом попиту bj=1, j = 2(6. Оскільки граф має w = 6 вершин, то обсяг буферу приймемо B=w-1=5. Матриця невідомих набуває розмірності (п)((п-1); серед пунктів попиту відсутній лише п. 1 (справжній пункт пропозиції) (рис. 1).
/
Рис. 2. Модель задачі для пошуку мінімального остівного дерева на графі (рис. 1) як транзитної транспортної задачі (Т-задачі) з умовою балансу потоків у Solver MS Excel.
Розрахунок моделей за допомогою Solver MS Excel
Реалізація моделі задачі у MS Excel відображена у табл. 1.
Таблиця 1
Реалізація елементів моделі задачі для пошуку мінімального остівного дерева на графі (рис. 1) як транзитної Т-задачі (рис. 2) на аркуші MS Excel
Адреса комірки
Формула
Розповсюдже-на на комірки
Зміст, виконуване завдання
1
2
3
4
D4:H9
Транспортна таблиця (матриця) невідомих, яка є редукованою матрицею суміжності остаточного графа, який відповідає маршруту перевезень
D14:H19
Чисельні значення відстаней між суміжними вершинами
Транспортна таблиця (матриця) вартостей, яка містить значення відстаней між суміжними вершинами
D22:H27
0(1
Редукована матриця суміжності вихідного графа; задає обмеження на структуру остаточного графа
Q17
5, чисельне значення обсягу пропозиції у п. 1
Обсяг пропозиції у п.1, прийнятому за справжній пункт пропозиції, за (25)
Q19
1, чисельне значення справжнього попиту у всіх вершинах графа, крім п.1
Чисельне значення справжнього по-питу у всіх вершинах графа, прийняв-тих за транзитні пункти попиту
1
2
3
4
Q18
=МАКС(Q17;Q19)
Чисельне значення обсягу буфера, розраховане за (6)
J5
=$Q$19+$Q$18
J5:J9
Чисельне значення граничного обсягу пропозиції у транзитних пунктах попиту за (10)
D11
=$Q$19+$Q$18
D11:H11
Чисельне значення граничного обсягу попиту у транзитних пунктах попиту за (11)
D10
=СУММПРОИЗВ(D4:D9;D22:D27)
D10:H10
Обсяг «пропозиції», ввезеної у кожну вершину графа, прийняту за транзитний пункт попиту, з урахуванням обмежень на структуру графа (СУММ – дає суму по рядку, а ПРОИЗВ забезпечує не включення у остаточний граф неіснуючих у вихідному графу ребер завдяки обмеженню балансу потоків)
I4
=СУММПРОИЗВ(D4:H4;D22:H22)
I5:I9
Обсяг «пропозиції», вивезеної з кожної вершини графа з урахуванням обмежень на структуру графа
О5:О9
{=ТРАНСП(D10:I14)}
Формула масиву
Сумарний обсяг «вантажу», ввезеного у кожну з вершин графа, прийняту за транзитний пункт попиту за (14), (27) (сумарний вхідний потік)
Р5
=I5
Р5:Р9
Сумарний обсяг вантажу, вивезеного кожної з вершин графа, прийнятої за транзитний пункт попиту за (14), (27) (сумарний вихідний потік)
Q5
=O5-1
Q6:Q9
Сумарний обсяг вантажу, який має бути вивезений з кожного з транзитних пунктів попиту за (14), (27) для задоволення попиту у 1, тобто для забезпечення «остівності» дерева
С29
=СУММПРОИЗВ(D4:H9;D14:H19)
Цільова функція – мінімальне остівне дерево за (23)
Постановка зазначеної задачі як оптимізаційної передбачає ідентифікацію у діалоговому вікні Пошуку рішення надбудови Solver (Пошук рішення) MS Excel: типу екстремуму (мінімум); адрес комірок, які містить цільову функцію (С29) та змінні (С4:H9); обмежень (рис. 3) та параметрів пошуку (модель – лінійна, значення – невідємні).
/
Рис. 3. Обмеження моделі у полі «Обмеження» діалогового вікна «Пошук рішення».
Зміст обмежень моделі у полі «Обмеження» діалогового вікна «Пошук рішення» (рис. 3) розкривається у табл. 2.
Таблиця 2
Реалізація обмежень моделі задачі для пошуку мінімального остівного дерева на графі як транзитної Т-задачі (рис. 2) у Solver MS Excel
№
Модель обмеження
Зміст обмеження
1.
$D$4:$H$9=целое
Обмеження цілочисельності змінних (24)
2.
$I$4=$J$4
Обмеження задоволення пропозиції (25) для вершини графа 1, прийнятої за справжній пункт пропозиції
3.
$I$5:$I$9<=$J$5:$J$9
Обмеження пропозиції та попиту (26) для вершин графа 2 ( 7, прийнятих за транзитні пунктів попиту обсягом 1
4.
$D$10:$Н$10<=$D$11:$Н$11
5.
$Р$5:$Р$9=$Q$5:$Q$9
Умова балансу потоків (27) для вершин графа 2 ( 7, прийнятих за транзитні пунктів попиту обсягом 1
6.
$D$10:$Н$10>=1
Умова задіяння усіх вершин графа
ВИСНОВОК
Після розв’язування задачі мінімальне остівне дерево буде отримано при наступних з’єднаннях на графі п.1 - п.2, п.1 - п.3, п.2 - п.4, п.2 - п.5, п.4 - п.6.
Сумарна найменша довжина кабельної мережі буде дорівнювати 23 км.
05.06.2014 11:06-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора