Автор работы: Пользователь скрыл имя, 15 Июня 2014 в 12:03, курсовая работа
Целью данной курсовой работы является рассмотрение теоретической части, в которую входят различные методы решения задачи нахождения потока наименьшей стоимости и практической части, в которой реализованы данные методы для конкретно поставленной задачи.
ВВЕДЕНИЕ 3
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 4
Сетевая модель 4
Сетевая модель как задача линейного программирования 4
Алгоритм симплекс-метода для сетей с ограниченной пропускной способностью 6
Транспортная задача 8
Метод северо-западного угла 9
Метод наименьшей стоимости 9
Метод потенциалов 10
ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ РЕШЕНИЯ ЗАДАЧИ СИМПЛЕКС-МЕТОДОМ 12
Постановка задачи 12
Нахождение первоначального плана методом северо-западного угла 13
Нахождение первоначального плана методом наименьшей стоимости 14
Метод потенциалов 15
ЗАКЛЮЧЕНИЕ 19
ЛИТЕРАТУРА 20
Министерство образования и науки Российской Федерации
Байкальский Государственный Университет
Экономики и Права
Факультет информатики, учета и сервиса
Кафедра информатики и кибернетики
Курсовая работа на тему
"Сетевые модели: нахождение потока наименьшей стоимости"
Выполнил: студент группы ИС-09-1 Шелёмин А.В.
Проверила: Белых Т.И.
Иркутск, 2013
Оглавление
Сетевые и графовые модели охватывают довольно большой класс задач, встречающихся при исследовании целого ряда проблем в транспорте, связи и других областях, связанных с действительным или воображаемым движением товаров, информации или людей. Характерной особенностью задач, решаемых с помощью теории графов, является большая размерность поля данных. Поэтому возникает необходимость использования методов оптимизации, которые позволяют экономить вычислительные ресурсы и обеспечивают их гибкость по отношению к изменениям исходных данных.
Одной из таких задач теории графов является задача о потоке минимальной стоимости, которая заключается в поиске способа пересылки с минимальными затратами заданного количества единиц потока из одного пункта в другой в графе с заданными на дугах пропускными способностями и стоимостями прохождения одной единицы потока . Такая задача возникает, например, когда некоторый предприниматель имеет возможность выбирать маршруты для перевозки готовых изделий от своего предприятия до склада, с выбором различных маршрутов перевозок связаны те или иные затраты, по каждому маршруту можно пропустить ограниченное количество изделий.
Целью данной курсовой работы является рассмотрение теоретической части, в которую входят различные методы решения задачи нахождения потока наименьшей стоимости и практической части, в которой реализованы данные методы для конкретно поставленной задачи.
Рассмотрим сеть G = (N, A) с ограниченной пропускной способностью, где N - множество узлов, A - множество дуг. Обозначим:
На рисунке 1 показано,
как на схемах сетей будем
отображать определенные
Задача нахождения потока наименьшей стоимости в сети с ограниченной пропускной способностью обобщает задачу определения максимального потока по следующим направлениям.
В рассматриваемой
задаче необходимо найти
Прежде чем приступить
к рассмотрению поставленной
задачи коротко изложим
Линейное программирование - это метод математического моделирования, разработанный для оптимизации использования ограниченных ресурсов.
К числу задач линейного программирования можно отнести задачи:
С математической точки зрения в каждой задаче ищутся значения нескольких неизвестных, причем требуется, чтобы:
Число переменных и число условий могут быть какими угодно. В реальных задачах эти числа весьма велики. Общая математическая формулировка задачи линейного программирования выглядит следующим образом.
Дана система линейных уравнений
a11x1 + a12x2 + … + a1nxn = b1
a21x1 + a22x2 + … + a2nxn = b2
(*)
. . . . . . . .
am1x1 + am2x2 + … + amnxn = bm
и линейная функция
f = c1x1 + c2x2 + ... + cnxn.
Требуется найти такое неотрицательное решение
x1>=0, x2>=0, ... , xn>= 0
системы, при котором функция f принимает наименьшее значение (минимизируется).
Естественно, что решение
таких задач связано с большим
объемом вычислений. Однако существуют
методы, позволяющие найти решение
любой задачи линейного
Для начала работы
по симплекс-методу требуется, чтобы
заданная система уравнений
x1 = a'1,r+1xr+1 + ... + a'1,nxn + b'1
x2 = a'2,r+1xr+1 + ... + a'2,nxn + b'2
. . .
. . . . .
xr = a'r,r+1xr+1 + ... + a'r,nxn + b'r
где
b'1 >=0, b'2 >=0, ..., b'n >=0 (**)
Неизвестные x1, …, xr, находящиеся
в левой части этой системы, называются базисными,
а весь набор { x1, …, xr}, который
мы обозначим для краткости одной буквой Б,
- базисом, остальные неизвестные называются небазисными или
Положим все небазисные
неизвестные равными нулю: xr+
будет, вследствие (**), допустимым. Оно называется базисным решением, отвечающим базису x1, …, xr. Для базисного решения значение формы f равно
Решение задачи при
помощи симплекс-метода
При рассмотрении
Транспортная задача относится к классу задач линейного программирования. Транспортная задача решает проблему нахождения оптимального (минимального по стоимости) плана распределения и перемещения ресурсов от производителей к потребителям. Проблема оптимизации стоимости перевозок актуальна и на сегодняшний день, так как позволяет фирмам и предприятиям существенно сократить расходы на транспорт. Правильная организация перевозок позволяет устранить встречные и дублирующие перевозки, сократить количество дальних перевозок и т. д. При решении транспортной задачи необходимо:
От каждого производителя ресурс может перемещаться к любому потребителю и измеряться в одних единицах измерения.
Методы составления опорного плана транспортной задачи:
На каждом этапе максимально возможным числом заполняют левую верхнюю клетку оставшейся части таблицы. Заполнение таким образом, что полностью выносится груз из или полностью удовлетворяется потребность .
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую. И в клетку, которая ей соответствует, помещают меньшее из чисел ai или bj . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены. Либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Алгоритм:
Информация о работе Сетевые модели: нахождение потока наименьшей стоимости