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

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

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

ВВЕДЕНИЕ 3
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 4
Сетевая модель 4
Сетевая модель как задача линейного программирования 4
Алгоритм симплекс-метода для сетей с ограниченной пропускной способностью 6
Транспортная задача 8
Метод северо-западного угла 9
Метод наименьшей стоимости 9
Метод потенциалов 10
ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ РЕШЕНИЯ ЗАДАЧИ СИМПЛЕКС-МЕТОДОМ 12
Постановка задачи 12
Нахождение первоначального плана методом северо-западного угла 13
Нахождение первоначального плана методом наименьшей стоимости 14
Метод потенциалов 15
ЗАКЛЮЧЕНИЕ 19
ЛИТЕРАТУРА 20

Вложенные файлы: 1 файл

Курсовая ИСО.docx

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

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

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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

Рассмотрим сеть 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 принимает наименьшее значение (минимизируется).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник