Исходные данные - Задача оптимизации городской транспортной сети

Решить задачу о минимальном покрывающем дереве в графе, используя в качестве исходных данных граф транспортных связей микрорайонов города, представленный на рис. 1, и матрицу смежности исходного графа, представленную в табл. 2.

Пассажиропоток граф минимум математический

Рис. 1. Граф транспортных связей микрорайонов города

Таблица 2. Матрица смежности исходного графа

Примечание: Матрица смежности является симметричной, т. е. расстояния между пунктами в прямом и обратном направлении равны. Знак "?" означает отсутствие прямой связи между пунктами.

Решение.

Матрица смежности для нашего случая имеет вид

Таблица 3

V12

V13

V14

V15

1,0

1,5

0,9

0,7

0,8

1,1

1,7

0,9

1,2

0,8

0,9

V12

0,9

1,6

2,1

V13

1,5

V14

1,4

V15

Для рассматриваемого примера математическая постановка задачи о минимальном покрывающем дереве может быть записана в следующем виде:

(3)

Где множество допустимых альтернатив формируется следующей системой ограничений:

Для решения данной задачи с помощью программы MS Excel создадим новую книгу и изменим имя ее первого листа на Покрывающее дерево. Для решения поставленной задачи выполним следующие подготовительные действия.

1. Внесем необходимые надписи в ячейки A1:F1, A11 (рис. 2). Следует отметить, что конкретное содержание этих надписей не оказывает влияние на решение рассматриваемой задачи. 2. В ячейки A2:A15 введем индексы начальных вершин, а в ячейки B2:B15 - индексы конечных вершин всех имеющихся ребер исходного графа. 3. В ячейки C2:C15 введем значения коэффициентов целевой функции (1). 4. В ячейку F2 введем формулу: =СУММПРОИЗВ(C2:C15; D2:D15), которая представляет собой целевую функцию (3). 5. В ячейки E2:E15 введем значение левых частей первых двенадцати ограничений системы ограничений (4) (см. рис. 7). 6. В ячейку D16 введем формулу: =СУММ(D2:D14), которая представляет собой левую часть тринадцатого ограничения в системе (4).

Внешний вид рабочего листа MS Excel с исходными данными решения задачи о минимальном покрывающем дереве в графе имеет вид, представленный на рис. 2.

Рис. 2. Исходные данные для решения задачи о минимальном покрывающем дереве в графе

Далее следует вызвать мастер поиска решения, для чего необходимо выполнить операцию главного меню Сервис>Поиск решения.

После появления диалогового окна Поиск решения следует выполнить следующие действия:

1. В поле с именем Установить целевую ячейку: ввести абсолютный адрес ячейки $F$2. 2. Для группы Равной: выбрать вариант поиска решения - минимальному значению. 3. В поле с именем Изменяя ячейки: ввести абсолютный адрес ячеек $D$2:$D$15. 4. Задать ограничения рассматриваемой задачи, как показано на рис. 3.

Рис. 3. Переменные и параметры поиска решения

5. В окне дополнительных параметров поиска решения выбрать отметки Линейная модель и Неотрицательные значения.

После задания ограничений и целевой функции можно приступить к поиску численного решения. После выполнения расчетов программой MS Excel будет получено количественное решение, представленное на рис. 9.

Рис. 4. Результат решения задачи о минимальном покрывающем дереве в графе

Результатом решения задачи о минимальном покрывающем дереве в графе являются найденные оптимальные значения переменных:

Найденному оптимальному решению соответствует значение целевой функции:

На рис. 5 представлено минимальное покрывающее дерево графа.

Рис. 5. Минимальное покрывающее дерево исходного графа

Вывод. Найден оптимальный проект транспортной сети, связывающей по кратчайшему расстоянию все микрорайоны города. Суммарная протяженность всех автодорог, по которым пройдут автобусные маршруты, минимальна и составляет 10 км.

Похожие статьи

Задание на лабораторную работу - Задача оптимизации городской транспортной сети

Создать и оптимизировать в Microsoft Excel табличную модель задачи оптимизации городской транспортной сети. Табл. 1 Номер варианта Номера вершин 8 1 - 8,...
Автоматизированное решение транспортной задачи линейного программирования, Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала., С помощью полученных в результате реализации модели отчетов сделать рекомендации филиалу фирмы по расширению программы выпуска ассортимента продукции. - Определение оптимальной стратегии рыночного поведения с использованием макроэкономических методов и моделей

В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
Количественный анализ и параметрическая оптимизация - Моделирование распределительных процессов на основе динамических задач векторной оптимизации

Для примера рассмотрим вытекающую из общей постановки (3),(4) двухкритериальную () многоэтапную динамическую задачу, с целевыми функциями дохода и потерь...
Теоремы двойственности и их использование в задачах ЛП - Решение оптимизационных экономических задач методами линейного программирования

Исходная задача: При ограничениях: Двойственной является следующая задача: При ограничениях: Число неизвестных в двойственной задаче равно 2....
Нелинейное программирование - Реферативно-прикладное исследование применения экономико-математических методов в решении задач производства (метод нелинейного программирования)

Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
Решение задачи с помощью прикладных программ, Технология разработки формы для ввода исходных данных средствами VBA - Формирование оптимального штата фирмы

Технология разработки формы для ввода исходных данных средствами VBA Для разработки формы ввода исходных данных необходимо отобразить вкладку...
Составить двойственную задачу и найти ее оптимальное решение по теореме равновесия, Решение двойственной задачи - Методика решения двойственных задач линейного программирования

Известно оптимальное решение X*=(0;0;1;1) задачи линейного программирования: Составьте двойственную задачу и найдите ее оптимальное решение по теореме...
Нелинейное программирование - Методики решения задач линейного и нелинейного программирования

Задача математического программирования называется нелинейной, если нелинейны ограничения или целевая функция. Задачи нелинейного программирования бывают...
Постановка задачи многокритериальной оптимизации - Многокритериальная оптимизация на основе нейросетевой, нечеткой и нейро-нечеткой аппроксимации функции предпочтений лица, принимающего решения

Пусть - вектор параметров задачи (вектор варьируемых параметров), где - n-мерное арифметическое пространство (пространство параметров). Множеством...
Обобщенные интервальные оценки исходных данных - Метод представления знаний в интеллектуальных системах поддержки экспертных решений

Построим теперь на базе полиинтервальной оценки такую теоретико-вероятностную модель представления экспертных знаний, которая сочетала бы в себе описание...
Метод решения задачи - Многокритериальная оптимизация на основе нейросетевой, нечеткой и нейро-нечеткой аппроксимации функции предпочтений лица, принимающего решения

Многокритериальный оптимизация нейронный аппроксимация Общая схема рассматриваемого метода является итерационной и состоит из следующих основных этапов....
Результаты применения МГА для оптимизации ИП - Возможности генетических алгоритмов для решения задачи многокритериальной оптимизации инвестиционного портфеля

Все генетические алгоритмы участвовали в двух группах тестов. В каждой группе исследовались различные наборы значений управляющих параметров МГА:...
Тестовые данные для задачи оптимизации ИП - Возможности генетических алгоритмов для решения задачи многокритериальной оптимизации инвестиционного портфеля

Инвестиционный портфель оптимальный многокритериальный В качестве тестового примера использовались следующие входные данные [Социальная сеть инвесторов,...
Особенности постановки и решения общей задачи линейного программирования - Определение оптимальной стратегии рыночного поведения с использованием макроэкономических методов и моделей

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

Математическая модель задачи нелинейного программирования (ЗНП) (*) Для ЗНП в отличие от Задачи Линейного Программирования (ЗЛП) нет единого метода...
Решение задачи графическим методом - Математическое моделирование в менеджменте и маркетинге

Необходимо найти максимальное значение целевой функции L(x)= 2x1+2x2 > max, при системе ограничений: 6x1+8x2?48, (1) 8x1+11x2?88, (2)...
Целочисленное линейное программирование - Методики решения задач линейного и нелинейного программирования

При решении некоторых задач линейного программирования бывает необходимо получить целочисленное решение, которое находится методами целочисленного...
Нелинейное программирование, Общая задача нелинейного программирования - Экономико-математические методы

Во многих экономических моделях исследования операций зависимости между постоянными и переменными факторами лишь в первом приближении можно считать...
Геометрический метод - Приложение интегрального и дифференциального исчисления к решению прикладных задач

Теория: Применяется, как правило, для задач линейного программирования, содержащих не более 2 переменных. Суть геометрического метода сводится к...
Геометрический метод решения задач ЛП - Решение оптимизационных экономических задач методами линейного программирования

Необходимо найти минимальное значение целевой функции F = 4x1+18x2 > min, при системе ограничений: X1+4x2?14(1) X1+6x2?15(2) X1+x2?5(3)...
Задача поиска маршрутов в графе (путей в орграфе)

Задача поиска маршрутов в графе (путей в орграфе) Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и. Правила. 1) Идя по произвольному...
Свертка скалярных критериев и условия компромисса - Моделирование распределительных процессов на основе динамических задач векторной оптимизации

Пусть ограничения (4) не противоречивы, т. е. не пусто множество допустимых решений, а оптимальное решение достигается я в точке для каждой K -ой...
Задача маршрутизации - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

Задача маршрутизации реализуется набором алгоритмов, каждый из которых осуществляет решение задачи коммивояжера. Коммивояжер (распространитель товаров)...
Постановка задачи и генетические алгоритмы для многокритериальной оптимизации ИП - Возможности генетических алгоритмов для решения задачи многокритериальной оптимизации инвестиционного портфеля

Рассматриваемая задача оптимизации ИП основывается на двухкритериальной модели Г. Марковица с незначительной корректировкой (вместо поиска долей каждого...
Нахождение кратчайшего пути в транспортной сети - Применение экономико-математических методов и моделей в управлении производством (на примере КУП "Спецкоммунтранс")

В зависимости от содержания задачи может быть два случая: когда ребра графа G единичной длины; когда ребра графа произвольной длины. Для каждого из этих...
О вычислительной сложности алгоритмов, реализованных на предфрактальных графах - Моделирование крупномасштабной транспортной сети предфрактальными графами

Моделирование транспортной сети большой размерности с помощью предфрактальных графов позволяет строить эффективные алгоритмы благодаря свойству...
Введение - Моделирование распределительных процессов на основе динамических задач векторной оптимизации

Развитие методов многокритериальной оптимизации сложных систем обусловлено необходимостью повышения эффективности их функционирования на основе обобщения...
Транспортная задача и ее решение методом потенциалов - Решение оптимизационных экономических задач методами линейного программирования

Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
Транспортная задача - Экономико-математические методы

Методы линейного программирования, являются хорошим инструментом для решения ряда проблем распределения ресурсов. Применение пакетов прикладных программ...
Математическая модель с учетом дополнительных условий, Математическая модель транспортной задачи - Методика решения задачи целочисленного программирования

Вводим дополнительные ограничения в модель: А) продукция типа 1 выпускается только в том случае, если разрешен выпуск хотя бы одного типа продукции: 2 и...
Пример транспортной задачи линейного программирования - Оптимальное программирование

Транспортная задача -- математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из...
Данные об исследуемой культуре - Постановка задачи прогнозирования продуктивности агроэкосистем

В результате численных экспериментов были обнаружены следующие недостатки модели: Структуру сети и ее обучение необходимо проводить под каждую конкретную...
Исследование разрешимости второй краевой задачи для уравнения в частных производных с инволютивным отклонением в младших членах

Исследование разрешимости второй краевой задачи для уравнения в частных производных с инволютивным отклонением в младших членах Многие математические...
Линейное программирование, Симплекс - метод - Методики решения задач линейного и нелинейного программирования

Основная задача линейного программирования: Найти неотрицательное решение системы ограничений обеспечивающее максимум (минимум) целевой функции. Чтобы...
Раскраска графов - Математические модели, используемые в системе оптимизации доставки товаров автотранспортом

Задача кластеризации может быть сведена к задаче раскраски вершин графа. Для этого строится граф несовместимости. Вершинам графа соответствуют...
Анализ чувствительности оптимального решения к вариациям правых частей ограничений - Исследование чувствительности оптимального решения задачи линейного программирования к вариациям ее параметров и введению нового ограничения

Ограничение чувствительность задача программирование Вариации правых частей ограничений приводят к изменению области допустимых решений ЗЛП, в действии...
Обобщенная модель задачи формирования производственной программы предприятия, Экономико-математическая модель задачи формирования производственной программы предприятия - Формирование оптимальной производственной программы предприятия

С целью формализации задачи введем необходимые обозначения: I - код изделия (i = 1,...,n); ХI - искомый объем выпуска годовой программы по i-му изделию;...
АНАЛИЗ ДЕЯТЕЛЬНОСТИ ПРЕДПРИЯТИЯ - Оптимизация управлением производства на примере ОАО "Днепропетровский стрелочный завод"

В результате проведенного финансового анализа предприятия можно сделать вывод, что состояние его удовлетворительное, но имеется ряд недостатков: В...
Основные задачи анализа временных рядов - Динамические ряды

Принципиальные отличия временного ряда от последовательности наблюдений, образующих случайную выборку, заключаются в следующем: Во-первых, в отличие от...
ПОСТАНОВКА ЗАДАЧИ - Задача коммивояжера

Пусть имеется п городов. Расстояния между любой парой городов (i, j) известны и составляют dij, где i=1, m; j=1, n; i?j. Если прямого маршрута...

Исходные данные - Задача оптимизации городской транспортной сети

Предыдущая | Следующая