На этом шаге мы рассмотрим (общих чертах) задачу нахождения потока наименьшей стоимости.

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

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

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

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

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

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

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

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

  a11x1 + a12x2 + … + a1nxn = b1
  a21x1 + a22x2 + … + a2nxn = b2    (*)
  .   .   .   .   .   .   .   .
  am1x1 + am2x2 + … + amnxn = bm

  f = c1x1 + c2x2 + ... + cnxn.

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

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

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

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

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

  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  (**)

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

  f = c0 +  с'r+1xr+1 + ... + с'nxn.

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

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

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

  fБ = с0.

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

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

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

    На следующем шаге мы рассмотрим пример построения сетевой модели.

Предыдущий шаг Содержание Следующий шаг