Индивидуальное задание студента

ЛАБОРАТОРНАЯ РАБОТА № 5

По дисциплине «Имитационное моделирование»

Логистические модели в экономике

Цель занятия:

- ознакомиться с видами логистических задач;

- освоить алгоритмы построения минимальных остовных деревьев;

- освоить методы решения задачи о минимальном покрывающем

дереве с помощью программы MS Excel.

 

Немного из теории

 

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

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

При построении минимального покрывающего дерева ребра просматриваются в порядке возрастания их весов: первое ребро – с минимальным весом, последующие в порядке возрастания, последнее ребро с максимальным весом. Если два и более ребра имеют одинаковые веса, то они выбираются в произвольном порядке.

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

В исходном состоянии все ребра исходного графа непомечены и ни одно подмножество вершин не сформировано. Предварительно ранжируем по весу ребра, начиная с ребра наименьшего веса.

Шаг 1. Выбрать ребро наименьшего веса. Пометить и сформировать подмножество вершин, включив в него концевые вершины.

Шаг 2. Выбрать следующее непомеченное ребро. Если в графе таких ребер нет, то закончить процедуру.

После выбора ребра возможны следующие четыре случая:

1. Обе концевые вершины ребра принадлежат одному и тому же подмножеству.

2. Одна из концевых вершин принадлежит некоторому подмножеству, а другая концевая вершина не принадлежит ни одному из сформированных подмножеств.

3. Ни одна из концевых вершин не принадлежит ни одному из сформированных подмножеств.

4. Концевые вершины выбранного ребра принадлежат разным подмножествам.

При первом варианте ребро не помечается (оно не включается в покрывающее дерево) и выбирается следующее ребро.

При втором варианте ребро помечается (включается в покрывающее дерево), а вторая концевая вершина его, не принадлежавшая ранее ни одному подмножеству, включается в то же подмножество, в котором находится его первая концевая вершина.

Если имеет место третий вариант, то ребро помечается, а из его вершин формируется новое подмножество вершин.

И, наконец, в четвертом варианте ребро помечается, а оба подмножества, которым принадлежат концевые вершины, объединяются в единое подмножество.

По завершении шага 2 перейти к шагу 3.

Шаг 3. Если все вершины графа вошли в одно подмножество, закончить процедуру. В этом случае все помеченные ребра образуют покрывающее дерево. В противном случае вернуться к шагу 2.

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

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

 

В табл. 1 приведена стоимость прокладки дороги между пятью населенными пунктами в млн. руб.

Таблица 1

 

 

1) Упорядочим значения стоимостей в порядке возрастания

 

2) Построим покрывающее дерево минимальной стоимости. Будем рассматривать ребра в следующей последовательности: (x₁,x₂), (x₃,x₄), (x₄,x₅), (x₃,x₅), (x₁,x₃), (x₂,x₅), (x₂,x₄), (x₂,x₃), (x₁,x₄), (x₁,x₅). Результаты каждого шага приведем в табл.2.

Таблица 2

№	Ребро	Помечается или нет ребро?	Подмножество вершин х1	Подмножество вершин х2
	х1, х2	да		-
	х3, х4	да	-
	х4, х5	да	-
	х3, х5	нет	-	-
	х2, х5	да		-

 

Покрывающее дерево построено, так как все вершины вошли в единое подмножество Х₁ = Х и число дуг на единицу меньше числа вершин. Построено покрывающее дерево минимальной стоимости

.

 

Общий вид покрывающего дерева представлен на рис.1.

 

 

 

Что касается построения максимального покрывающего дерева, то его построение аналогично алгоритму минимального покрывающего дерева.

Построение кратчайшего покрывающего дерева c помощью программы MS Excel. Требуется дать предложения по минимизации стоимости проекта реконструкции транспортной сети. В качестве ограничения задачи - обязательное условие по возможности достижения из любого пункта транспортной сети в любой другой населенный пункт данного региона.

Пусть данный географический регион представлен в виде неориентированного связного графа (рис.2)

 

 

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

Ограничения задачи представлены следующей системой неравенств:

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

Для решения задачи посредством надстройки ПОИСК РЕШЕНИЯ программы MS Excel выполним следующие подготовительные действия:

1. Внесем необходимые надписи в рабочий лист в ячейки .

2. В ячейки введем индексы начальных вершин, а в ячейки - индексы конечных вершин всех ребер множества ребер графа.

3. В ячейки введем значения коэффициентов целевой функции.

4. В ячейку F2 введем формулу вычисления целевой функции: = СУММПРОИЗВ ().

5. В ячейки введем значение левой части первых сумм ограничений:

- в ячейку Е2: = СУММ ;

- в ячейку Е3: = СУММ ;

- в ячейку Е4: = СУММ ;

- в ячейку Е5: = СУММ ;

- в ячейку Е6: = СУММ ;

- в ячейку Е7: = СУММ ;

- в ячейку Е8: = СУММ (D12;D13).

6. В ячейку D14 введем формулу для вычисления левой части восьмого ограничения: = СУММ .

Для решения задачи выполним операции главного меню: «СЕРВИС ® ПОИСК РЕШЕНИЯ». После появления диалогового окна «ПОИСК РЕШЕНИЯ» выполним следующие действия:

1. В поле с именем «УСТАНОВИТЬ ЦЕЛЕВУЮ ЯЧЕЙКУ» введем абсолютный адрес: $F$2.

 

Внешний вид рабочего листа исходных данных показан на рис.3.

	А	В	С	D	E	F
				Переменные Xij:	Ограничения	=СУММПРОИЗВ
					=СУММ
					=СУММ
					=СУММ
					=СУММ
					= СУММ
					= СУММ
					=СУММ
	Ограничение дуг	=СУММ

Рис.3 - Рабочий лист MS Excel

 

2. Для группы «РАВНОЙ»задать вариант поиска - «МИНИМАЛЬНОМУ ЗНАЧЕНИЮ».

3. В поле «ИЗМЕНЯЯ ЯЧЕЙКИ» ввести абсолютный адрес .

4. Зададим первые семь ограничений задачи:

- в диалоговом окне «ПОИСК РЕШЕНИЯ» нажать кнопку «ДОБАВИТЬ»;

- в появившемся окне выбрать диапазон ячеек , который отображается в поле с именем «ССЫЛКА НА ЯЧЕЙКУ»;

- в качестве знака ограничения в среднем окне выбрать «>=»;

- в качестве правой части ввести с клавиатуры значение 1;

- для добавления первой группы ограничений нажать кнопку «ДОБАВИТЬ».

5. Добавим восьмое ограничение, для этого выполним действия:

- в диалоговом окне «ПОИСК РЕШЕНИЯ» нажать кнопку «ДОБАВИТЬ»;

- в появившемся окне выбрать диапазон ячеек , который отображается в поле с именем «ССЫЛКА НА ЯЧЕЙКУ»;

- в качестве знака ограничения из выпадающего списка в среднем окне выберем «=»;

- в качестве правой части ввести с клавиатуры значение 6;

- для добавления ограничения нажимаем кнопку «ДОБАВИТЬ».

6. Добавим ограничение на булевы переменные задачи:

- в диалоговом окне «ПОИСК РЕШЕНИЯ» нажать кнопку «ДОБАВИТЬ»;

- в появившемся окне выбрать диапазон ячеек , который отображается в поле с именем «ССЫЛКА НА ЯЧЕЙКУ»;

- в качестве знака ограничения в среднем окне выберем «ДВОИЧН»;

- в качестве правой части в поле с именем «ОГРАНИЧЕНИЯ» оставим без изменения вставленное программой значение «ДВОИЧНОЕ»;

- для добавления ограничения нажимаем кнопку «ДОБАВИТЬ».

7. В окне параметров «ПОИСКА РЕШЕНИЯ» поставим отметки «ЛИНЕЙНАЯ МОДЕЛЬ» и «НЕОТРИЦАТЕЛЬНЫЕ ЗНАЧЕНИЯ». После нажатия кнопки ОК вновь появляется диалоговое окно «ПОИСК РЕШЕНИЯ» на котором необходимо нажать кнопку «ВЫПОЛНИТЬ».

После выполнения расчетов программой MS Excel будет получено решение, которое имеет следующий вид (рис.4).

 

	А	В	С	D	E	F
				Переменные:
	Ограничение дуг

 

Рис.4 - Рабочий лист решения задачи

 

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

и

 

Найденное оптимальное решение соответствует значению целевой функции Этому решению соответствует граф, представленный на рис.5.

 

 

 

 

Тем самым найден оптимальный проект реконструкции транспортной сети, предполагающий построение автодорог между населенными пунктами со стоимостью 32 млн. руб.

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

 

 

Индивидуальное задание студента

Администрация Фатежского района рассматривает проект газификации семи населенных пунктов района. Работы, которые необходимо выполнить при реализации проекта (в млн. руб.), а также взаимосвязь между пунктами представлены в виде графа (рис. 6). С помощью приведенного в работе алгоритма оценить наименьшую стоимость работ. Уточнить стоимость проекта и построить минимальное покрывающее дерево с помощью программы MS Ecxel.

 

Примечание: Параметры исходных данных определяются по номеру зачетной книжки студента (пропуска): m – предпоследняя цифра, n -последняя цифра.

Литература

1. Лугинин О.Е. Экономико-математические методы и модели: теория и практика с решением задач: учебн. пособие/ О.Е.Лугинин, В.Н.Фомишина. – Ростов на Дону: Феникс, 2009. – 440 с.

2. Экономико-математические методы и прикладные модели: Учебн. Пособие для вузов / В.В.Федосеев, А.Н.Гармаш и др.; Под ред. В.В.Федосеева. – М.:ЮНИТИ, 2005 – 304 с.

3. Экономико-математические методы и модели: Учебн. Пособие/ кол. авторов под ред. С.И.Макарова. – М.: КНОРУС, 2009. – 240 с.

4. Экономико-математические методы и модели. Задачник: учебно-практическое пособие/ кол. авторов под ред. С.И.Макарова. – М.: КНОРУС, 2009. – 208 с.

 

Поделиться:

Воспользуйтесь поиском по сайту: