Сетевые модели: нахождение потока наименьшей стоимости

Министерство образования и науки Российской Федерации

Байкальский Государственный Университет

Экономики и Права

Факультет информатики, учета и сервиса

Кафедра информатики и кибернетики

 

 

 

 

 

 

 

 

 

Курсовая работа на тему

"Сетевые модели: нахождение потока наименьшей  стоимости"

 

 

 

 

 

 

 

 

 

Выполнил:  студент группы ИС-09-1 Шелёмин А.В.

 

Проверила: Белых Т.И.

 

 

 

 

 

 

 

 

 

 

 

Иркутск, 2013

Оглавление

 

 

 

 

ВВЕДЕНИЕ

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

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

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

 

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Сетевая модель

 

    Рассмотрим сеть G = (N, A) с ограниченной пропускной способностью, где N - множество узлов, A - множество дуг. Обозначим:

• xij - величина потока, протекающего от узла i к узлу j,
• uij (lij) - верхняя (нижняя) граница пропускной способности дуги (i, j),
• cij - стоимость прохождения единицы потока по дуге (i, j),
• fi - величина "чистого" результирующего потока, протекающего через узел i.

 

    На рисунке 1 показано, как на схемах сетей будем  отображать определенные параметры  дуг. Метка [fi] указывает положительное (отрицательное) значение предложения (спроса), соответствующего узлу i:

 
Рис.1. Отображение параметров дуг

Сетевая модель как задача линейного программирования

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

1. Все ребра допускают только одностороннее направление потока, т.е. являются (ориентированными) дугами;
2. Каждой дуге поставлена в соответствие (неотрицательная) стоимость прохождения единицы потока по данной дуге;
3. Дуги могут иметь положительную нижнюю границу пропускной способности;
4. Любой узел сети может выступать как в качестве источника, так и стока.

 

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

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

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

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

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

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

• эти значения были неотрицательны;
• эти значения удовлетворяли некоторой системе линейных уравнений или линейных неравенств;
• при этих значениях некоторая линейная функция обращалась в минимум (или максимум).

 

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

    Дана система линейных уравнений

  a11x1 + a12x2 + … + a1nxn = b1

  a21x1 + a22x2 + … + a2nxn = b2    (*)                                                                                            (1)

  .   .   .   .   .   .   .   .

  am1x1 + am2x2 + … + amnxn = bm                                                                                                

и линейная функция

  f = c1x1 + c2x2 + ... + cnxn.                                                                                                       (2)    

Требуется найти такое неотрицательное решение

  x1>=0, x2>=0, ... , xn>= 0

системы, при котором функция f принимает наименьшее значение (минимизируется).    

 Естественно, что решение  таких задач связано с большим  объемом вычислений. Однако существуют  методы, позволяющие найти решение  любой задачи линейного программирования  за конечное число шагов. К  их числу относится прежде всего так называемый симплекс-метод.

Алгоритм симплекс-метода для сетей с ограниченной пропускной способностью

 

    Для начала работы  по симплекс-методу требуется, чтобы  заданная система уравнений была  приведена к такому виду, в котором какие - либо r неизвестных (r<=m) выражены через остальные, причем свободные члены этих выражений неотрицательны. Предположим, для определенности, что неизвестные, которые выражены через остальные, - это x1, ..., xr. Следовательно, система приведена к виду: приведена к виду:

 

  x1 =  a'1,r+1xr+1 + ... +  a'1,nxn +  b'1

  x2 =  a'2,r+1xr+1 + ... +  a'2,nxn +  b'2

  .   .   .   .   .   .   .   .                                                                                                     (3)

  xr =  a'r,r+1xr+1 + ... +  a'r,nxn +  b'r

где

b'1 >=0, b'2 >=0, ..., b'n >=0  (**)                                         (4)   

 Неизвестные x1, …, xr, находящиеся в левой части этой системы, называются базисными, а весь набор { x1, …, xr}, который мы обозначим для краткости одной буквой Б, - базисом, остальные неизвестные называются небазисными или свободными. Подставляя в форму f вместо базисных неизвестных их выражения через небазисные из последней системы, мы можем и саму форму f также записать через небазисные неизвестные xr+1, …, xn:

                                               f = c0 +  с'r+1xr+1 + ... + с'nxn.                                         (5)   

 Положим все небазисные  неизвестные равными нулю: xr+1 = ... = xn = 0 и и найдем из последней системы значения базисных неизвестных: x1 = b'1, …, xr = b'n. Полученное таким путем решение системы:

                                                (b'1, …, b'r, 0, …, 0)                                                      (6)

будет, вследствие (**), допустимым. Оно называется базисным решением, отвечающим базису x1, …, xr. Для базисного решения значение формы f равно

                                              fБ = с0.                                                                     (7)   

 Решение задачи при  помощи симплекс-метода распадается  на ряд шагов. Каждый из шагов  заключается в том, что от данного  базиса Б мы переходим к другому базису Б' с таким расчетом, чтобы значение fБ уменьшилось или, по крайней мере, не увеличилось: fБ' <= fБ. Новый базис Б' получается из старого Б весьма просто: из Б удаляется одна из неизвестных и взамен нее вводится другая (из числа прежних небазисных). Изменение базиса влечет за собой соответствующую перестройку системы (*). После некоторого числа таких шагов мы или приходим к базису Б(k), для которого fБ(k) есть искомый минимум формы f, а соответствующее базисное решение является оптимальным, или же выясняем, что задача решения не имеет.    

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

1. Каждому из m ограничений прямой задачи соответствует переменная двойственной задачи.
2. Каждой из n переменных прямой задачи соответствует ограничение двойственной задачи.
3. Коэффициенты при какой-либо переменной в ограничениях прямой задачи становятся коэффициентами ограничения двойственной задачи, соответствующей этой переменной, а правая часть формируемого ограничения равна коэффициенту при этой переменной в выражении целевой функции.
4. Коэффициенты целевой функции двойственной задачи равны правым частям ограниченной прямой задачи.

Транспортная задача

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

• обеспечить всех потребителей ресурсами;
• распределить все произведенные ресурсы;
• переместить ресурсы от производителей к потребителям с наименьшими затратами.

От каждого производителя ресурс может перемещаться к любому потребителю и измеряться в одних единицах измерения.

Методы составления опорного плана транспортной задачи:

Метод северо-западного угла

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

 Метод наименьшей стоимости

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую. И в клетку, которая ей соответствует, помещают меньшее из чисел ai или bj . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены. Либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Алгоритм:

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