Определение источника и стока сети

Размещено на http://www.allbest.ru/

Оглавление

1. Условия и тексты заданий

2. Краткая теория

3. Расчет максимального потока в сети

3.1 Расчет максимального потока в сети в MathCad

3.2 Расчет максимального потока в сети в Excel

4. Поиск минимального пути от источника к стоку сети

4.1 Поиск минимального пути от источника к стоку сети в MatCad

4.2 Поиск минимального пути от источника к стоку сети в Excel

5. Решение задачи о «Назначениях рабочих»

5.1 Решение задачи о «Назначениях рабочих» в MathCad

5.2 Решение задачи о «Назначениях рабочих» в Excel

Вывод

Список используемой литературы



1. Условия и тексты заданий

Сетевая задача (вариант № 34):

Задача о назначениях (вариант № 34):

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

Матрица оплаты:



2. Краткая теория

Понятие сетевых моделей.

Сеть - это граф у которого один исток и один сток. Вершина графа имеющая только исходящие дуги - исток; вершина графа имеющая только входящие дуги - сток.

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

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

В сети рассматривают ориентированные пути.

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



3. Расчет максимального потока в сети

3.1 Расчет максимального потока в сети в MathCad

Поток - это некая информация, передаваемая по дугам в сети.

Предположим, что эта информация имеет количественное измерение, тогда вес дуги- это максимальное количество информации, которое можно передать по дуге (пропускная способность), если ввести обозначение для рисунка 1:

Хi - величина потока по i-ой дуге

Получим ограничения пропускной способности:

Будем считать, что весь поток, входящий в узел, равен потоку, исходящему из узла.

Получим ограничения на отсутствие задержек потока в узлах:

Величину в стоке сети можно вычислить:

где Х - вектор потока по каждой дуге.

Отсюда задача линейной оптимизации:

Вектор решения R определяет, что по дуге х1 необходимо пропустить поток величиной «3», по дуге x9 - «1», по x3 - «1» и так далее. При этом величина максимального потока = 18. Точка «А» является источником, «C» - стоком сети.

Графическая интерпретация решения (выделены дуги, переносящие максимальный поток):

3.2 Расчет максимального потока в сети в Excel

Подготовка бланка решения:



Подготовка бланка решения (в режиме формул):

СУММПРОИЗВ:

Перемножает соответствующие элементы заданных массивов и возвращает сумму произведений.

СУММПРОИЗВ (массив1;массив2;массив3; ...)

Массив1, массив2, массив3,...   -- от 2 до 255 массивов, компоненты которых нужно перемножить, а затем сложить результаты.

Замечания:

Аргументы, которые являются массивами, должны иметь одинаковые размерности. В противном случае функция СУММПРОИЗВ возвращает значение ошибки #ЗНАЧ!.

Функция СУММПРОИЗВ трактует нечисловые элементы массивов как нулевые.

Использование массивов дает более общее средство для выполнения действий, подобных функции СУММПРОИЗВ.

Заполнение параметров поиска решений:

Устанавливаем соответствующие параметры:

Нажимаем OK > Выполнить > Сохранить найденное решение > OK



Результат:



4. Поиск минимального пути от источника к стоку сети

4.1 Поиск минимального пути от источника к стоку сети в MatCad

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

Вес, данный каждой дуге, будем трактовать, как длину дуги.

Будем считать, что весь поток, входящий в узел, равен потоку, исходящий из узла. Получим ограничение на отсутствие задержки потока в узлах:

Длину можно вычислить как:

Получим задачу линейной оптимизации:



Вектор решения R определяет, какие дуги задействованы в минимальном пути. 1 - задействована, 0 - не задействована. При этом величина минимального пути = 6.

На приведенной ниже графической интерпретации видно, что найденный минимальный путь является единственным равным длине 6:

4.2 Поиск минимального пути от источника к стоку сети в Excel

Подготовка бланка решения:

Подготовка бланка решения (в режиме формул):



Заполнение параметров поиска решений:

Устанавливаем параметры:



Нажимаем OK > Выполнить > Сохранить найденное решение > OK

Результат:



5. Решение задачи о «Назначениях рабочих»

5.1 Решение задачи о «Назначениях рабочих» в MathCad

Так как условия задачи неоднозначны, имеется возможность в двух вариантах интерпретировать ответ. Воспользуемся матрицей из условий:

	Столб. 1	Столб. 2	Столб. 3	Столб. 4	Столб. 5	Столб. 6
Строк.1	3 x1	6 x2	4 x3	5 x4	4 x5	2 x6
Строк.2	1 x7	3 x8	2 x9	1 x10	3 x11	5 x12
Строк.3	5 x13	5 x14	5 x15	5 x16	1 x17	4 x18
Строк.4	4 x19	5 x20	6 x21	7 x22	1 x23	9 x24
Строк.5	2 x25	6 x26	6 x27	6 x28	1 x29	7 x30
Строк.6	5 x31	6 x32	4 x33	5 x34	1 x35	5 x36

Сумма всех элементов строки матрицы, должна быть равной 1, так как сотрудников 6 и их всех примут на работу. Сумма всех элементов одного столбца матрицы тоже, должна быть равной 1, так как на одно рабочее место должен быть назначен один сотрудник.

Общее количество всех назначений можно вычислить как:

Учитываем ограничения:



Получаем задачу оптимизации:

Для большей наглядности преобразуем транспонированный вектор в матрицу: поток сеть граф матрица

Матрица показывает, как будут распределены рабочие, например, вариант 1 показывает, что Раб. 1 будет работать на Мест. 5 и т.д. При этом минимальные затраты на производство будут равны 15. Матрица не однозначна, так как дать имена строкам и столбцам можно по-разному:

Вариант 1:

	Раб. 1	Раб. 2	Раб. 3	Раб. 4	Раб. 5	Раб. 6
Мест. 1						+
Мест. 2				+
Мест. 3					+
Мест. 4		+
Мест. 5	+
Мест. 6			+

Вариант 2:

	Мест. 1	Мест. 2	Мест. 3	Мест. 4	Мест. 5	Мест. 6
Раб. 1					+
Раб. 2				+
Раб. 3						+
Раб. 4		+
Раб. 5			+
Раб. 6	+

Из обеих интерпретаций решений видно, что при разном распределении сотрудников на места, затраты на производство по-прежнему будут равны 15.

5.2 Решение задачи о «Назначениях рабочих» в Excel

Подготовка бланка решения:



Подготовка бланка решения (в режиме формул):

Заполнение параметров поиска решений:

Устанавливаем параметры:



Нажимаем OK > Выполнить > Сохранить найденное решение > OK

Результат:



Вывод

Как видно из данной работы, необязательно решать задачи оптимизации вручную. С этой задачей успешно справляются компьютерные программы. Результаты вычислений и в MathCad, и в Excel совпали и оказались достаточно точными.

Задачи, приведённые в этой работе, являются лишь примером. С помощью оптимизации можно решать намного более сложные задачи, MathCad и Excel способны решать их также быстро и точно.



Список используемой литературы

1. Аносова С.В. Методические указания по использованию MathCad для решения некоторых учебных задач.

2. Ю.Ю. Тарасевич Численные методы на Mathcad'е. - Астраханский гос. Пед. Ун-т: Астрахань, 2000.

3. Поршнев С.В., Беленкова И.В. Численные методы на базе Mathcad. - СПб.: БХВ-Петербург, 2005.



Приложения

Приложение 1

Приложение 2



Приложение 3

Приложение 4



Приложение 5

Приложение № 6

Размещено на Allbest.ru

...