Модели оптимизации потоков

Каноническая постановка модели оптимизации потоков.

Задача отыскания наиболее рационального способа транспортировки некоторого продукта довольно часто может быть описана следующим образом. Имеется т пунктов отправления, в каждом на которых сосредоточено определенное количество единиц однородного продукта, предназначенного к отправке: в первом пункте отправления имеется а_х единиц этого продукта, во втором — а₂ единиц, в i-м — a_i единиц и, наконец, в т-м пункте — а_т единиц продукта. Этот продукт следует доставить в п пунктов назначении (потребления), причем в первый пункт назначения следует доставить Ь, единиц продукта, во второй — Ь₂ единиц, в j-й — Ь единиц и, наконец, в п-й пункт — Ь_п единиц продукта.

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

Далее предполагается, что каждый пункт отправления соединен с каждым пунктом назначения некоторым маршрутом (число этих маршрутов равно т? п), причем известна стоимость перевозки одной единицы продукта по этому маршруту. Общая стоимость перевозки по любому маршруту пропорциональна количеству перевозимого продукта. Стоимость перевозки единицы продукта из i-ro пункта отправления в j-й пункт назначения обозначим числом с^.

Перечисленные данные удобно свести в табл. 4.1, называемую таблицей стоимостей.

Таблица 4.1. Таблица стоимостей.

В этой таблице строкам соответствуют пункты отправления, а столбцам — пункты назначения. В клетке? j, расположенной на пересечении ?-й строки и;-го столбца, указана стоимость перевозки единицы продукта по маршруту, ведущему из ?-го пункта отправления в j-й пункт назначения.

Количество продукта (а, а₂, …, а_ш), имеющееся в пунктах отправления, и количество продукта (Ь₁, Ъ₂, Ь_п), потребное в пунктах назначения, размещены соответственно в левом столбце и верхней строке таблицы стоимостей.

Обозначим количество единиц продукта, планируемое к перевозке из i-ro пункта отправления в j-й пункт назначения, через х^.

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

Любой план перевозок определяется заданием совокупности чисел Ху (i = 1, 2, mj = 1, 2, п), т. е. перечислением величин перевозок, совершаемых по каждому из маршрутов. Эти числа должны удовлетворять следующим условиям.

1. Из каждого пункта отправления должен вывозиться весь имеющийся там продукт:

2. В каждом пункте назначения должна быть удовлетворена вся потребность в рассматриваемом продукте:

3. Числа x^. должны быть неотрицательными:

Нетрудно видеть, что, наоборот, всякая совокупность чисел Ху, удовлетворяющих условиям (4.1)—(4.3), может рассматриваться как некоторый план перевозок.

Каждый план перевозок может быть наглядно изображен в виде табл. 4.2.

Таблица 4.2. План перевозок.

Подсчитаем общую стоимость перевозок по плану по данным табл. 4.2. По маршруту, соединяющему t-й пункт отправления и j-й пункт назначения, перевозитсях единиц продукта, а стоимость перевозки одной единицы продукта равна c (j. Поскольку общая стоимость перевозки по данному маршруту пропорциональна количеству единиц перевозимого продукта, эта стоимость равна суху. денежных единиц.

Отсюда суммарная стоимость перевозок по всем маршрутам.

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

Математически транспортная задача линейного программирования формулируется следующим образом: найти значения неизвестных^ (i = 1, 2, …, m;j = 1, 2, п), удовлетворя ющие условиям (4.1)—(4.3) и обращающие в минимум линейную функцию (4.4).

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

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

В более общей постановке эту же задачу можно сформулировать следующим образом. Пусть столбцы таблицы стоимостей означают различные виды каналов обслуживания, а строки — различные классы заявок. Каждое число b_j при этом показывает, сколько каналов содержит данный вид, а числа a_j — сколько имеется заявок класса i. Числа с., могут характеризовать время обслуживания заявки i-ro класса каналом обслуживания j-го вида или любые другие издержки, связанные с этим обслу;

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

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

Следует отметить, что исторически некоторые методы решения транспортной задачи были разработаны не на базе общих методов линейного программирования, а непосредственно из рассмотрения свойств транспортной задачи; связь же этих методов с общими была выяснена позже. Именно так возник один из наиболее эффективных методов решения транспортной задачи — венгерский метод, являющийся с точки зрения классификации, данной во введении, типичным представителем методов последовательного сокращения невязок. Идея метода была высказана еще в 1931 г. венгерским математиком Эгервари. В начале 1950;х гг. американский математик Кун, развив эту идею, разработал метод решения задачи выбора, являющейся частным случаем транспортной задачи [14, 15]. Позже венгерский метод был усовершенствован и обобщен на случай произвольной транспортной задачи Манкресом.

Пример решения канонической транспортной задачи.

Имеются три поставщика и четыре потребителя. Мощности поставщиков, спросы потребителей, а также затраты на перевозку грузов сведены в таблицу поставок.

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

Решение

По условию задачи = ?Ь,. Следовательно, транспортная.

i )

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

Для решения задачи необходимо построить первоначальное базисное решение любым способом, затем попробовать улучшить полученное решение. Построим первоначальное базисное решение методом наименьших затрат, для улучшения решения используем метод потенциалов. Число базисных переменных закрытой транспортной задачи должно быть равно (т + п — 1), где п — число поставщиков; т — число потребителей. Возможно, что число базисных переменных будет меньше, чем (т + п — 1). Мы получим вырожденное решение. В этом случае необходимо использовать искусственный прием ввода в базисное решение клеток с нулевыми поставщиками. В нашей задаче ранг матрицы равен 3 + 4 — -1 = 6.

Определим потенциалы каждого столбца и каждой строки, начиная с нулевого значения потенциала, заданного для первого столбца, при этом будем исходить из условия, что потенциалы клеток с базисным решением равны нулю, т. е. должно соблюдаться условие ц. + v = с^. Затем вычислим потенциал каждой клетки, не вошедшей в базисное решение, по формуле и₍ + г — - с = р_у, где Ру — потенциал свободной клетки (расположен в правом углу клетки).

юз.

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

В нашей задаче потенциалы клеток не имеют положительных значений, следовательно получено оптимальное решение. Минимальные издержки: 10 • 7 + 30 • 2 + 60 • 3 + 30 • 1 + + 50 • 2 + 80 • 5 = 840. Необходимо заметить, что полученное оптимальное решение в данной задаче не является единственным.

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

В действительности это условие может не выполняться. Так, например, имеющееся количество продукта может превышать потребности в нем, т. е.

В этом случае система уравнений (4.1)—(4.2) оказывается несовместной, так как при обеспечении имеющихся потребностей в продукте часть продукта обязательно должна остаться в некоторых из пунктов отправления. Поэтому в рассматриваемой задаче следует равенства (4.1) заменить неравенствами.

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

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

Рассмотрим в качестве примера следующую задачу. Пусть имеется п строительных площадок, в каждой из которых задан объем потребностей кирпича (b_v Ъ₂, …, Ъ_п штук). Для обеспечения этих потребностей следует заранее завезти по железной дороге необходимый кирпич на имеющиеся т железнодорожных станций, откуда он будет доставляться на строительные площадки автотранспортом, причем удельные стоимости перевозки кирпича этим транспортом известны и заданы табл. 4.1. На каждой из упомянутых железнодорожных станций может быть сосредоточено ограниченное количество кирпича — а_; штук (в силу, скажем, ограниченности складских помеще;

П

ний). Общее количество необходимого кирпича? меньше,.

j-i.

чем его количество, которое можно одновременно запасти.

т

на всех станциях, т. е. меньше, чем? а,• штук. Возникает вопрос:

i=i.

сколько кирпича следует запасти на каждом из складов, чтобы суммарная стоимость перевозок этого кирпича от складов к строительным площадкам была минимальна?

Предположим сначала, что на каждый склад завезено максимально возможное количество кирпича — а₍ штук, и найдем оптимальный план автомобильных перевозок, обеспечивающий минимум расходов на эти перевозки.

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

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

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

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

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

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

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

где к — номер кирпичного завода; г — число заводов; 1_к — множество номеров складов, снабжаемых fc-м кирпичным заводом; S_k—максимальное количество кирпича, которое может произвести к-й кирпичный завод.

Ясно, что производительность завода имеет смысл учитывать только в том случае, если она меньше суммарной вместимости складов, снабжаемых этим заводом. Это соответствует неравенству S_k < X ^аг Если же для некоторых заводов это неравенство.

ielk

не выполняется, то для них условия (4.6) выписывать не нужно, ибо они будут автоматически выполнены, если обеспечить выполнение условий (4.5).

Назовем рассмотренную задачу минимизации расходов на перевозки (функции (4.4) при ограничениях (4.5), (4.6), (4.2), (4.3) транспортной задачей с дополнительными ограничениями по вывозу продукта. Эта задача была проанализирована в работе [25].

Задача с ограничениями пропускных способностей.

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

Поэтому наряду с изложенной задачей представляет интерес задача минимизации линейной функции (4.4) при условиях (4.1)—(4.3) и дополнительных условиях:

где d_(j — заданные неотрицательные числа.

Следует отметить, что обычная транспортная задача может рассматриваться как частный случай транспортной задачи с ограниченными пропускными способностями, если положить все d_{. = оо.

Ясно, что для того чтобы транспортная задача с ограниченными пропускными способностями была разрешима, необходимо, чтобы числа d_tj были не слишком малы, а именно, чтобы выполнялись следующие неравенства:

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

Пусть имеется п видов работ, которые следует распределить между п исполнителями по одной работе на каждого исполнителя. Эффективность использования i-ro исполнителя на j-й работе равна с. Заданные числа образуют квадратную таблицу эффективностей. Всякий выбор п чисел из этой таблицы по одному числу в строке и по одному числу в столбце определяет некоторый план распределения работ между исполнителями, а именно выбор числа, расположенного на пересечении i-й строки и j-го столбца, означает, что i-й исполнитель закрепляется за j-й работой. Требуется найти план распределения, обеспечивающий наибольшую суммарную эффективность. Эта задача называется задачей назначения или задачей выбора.

Определим матрицу чисел х. по следующему правилу: положим х~ = 1, если число c_t- выбрано, и х_у. = 0, если число не выбрано. Теперь любой план задачи назначения однозначно определяет некоторую матрицу ||х_у||.

Необходимым и достаточным условием для того, чтобы матрица целых неотрицательных чисел х~ могла рассматриваться как план задачи выбора, является удовлетворение следующим соотношениям:

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

Суммарную эффективность данного плана распределения можно записать в следующем виде:

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

Если вместо функции (1.8) рассмотреть противоположную функцию.

то задача назначения обращается в транспортную задачу линейного программирования, заключающуюся в минимизации этой функции Ф при ограничениях (4.7).

Особенность такой задачи в том, что а. = b. = 1. Это позволяет упростить некоторые алгоритмы ее решения для рассматриваемого частного случая.

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

В заключение следует указать, что так же, как и общая транспортная задача, задача назначения может рассматриваться при отсутствии равенства между количеством распределяемых средств и количеством объектов, на которые эти средства надлежит направить (между числом рабочих и числом работ). В этом частном случае открытой модели транспортной задачи одна из двух групп равенств (4.7) должна быть заменена соответствующими неравенствами. Так, если т > п, то ограничения, накладываемые на неизвестные, должны иметь вид.

Задача о максимальном потоке (в матричной постановке). Весьма близка к транспортной следующая более простая задача. Пусть, как и ранее, заданы количество продукта а_р а₂,…, а_т, предназначенные к отправке из пунктов отправления, и потребности Ь_р Ь₂,…, Ъ_п в этом продукте в пунктах назначения. Однако каждый пункт отправления связан лишь с некоторыми пунктами назначения, т. е. из любого пункта отправления в некоторые пункты назначения можно совершать перевозки, а в некоторые — нельзя.

Математически эти условия можно задать числами азаполняющими матрицу | |сг. 11. Эти числа формируются по такому правилу: число а" = 1, если нельзя совершать перевозку из i-ro пункта отправления bj'-й пункт назначения, и число а. = 0, если такая перевозка возможна. Естественнее было бы обозначать отсутствие маршрута нулем, а наличие — единицей, однако введенное противоположное правило оказывается более удобным в дальнейшем, при построении алгоритма решения транспортной задачи.

Задача заключается в том, чтобы составить такой план перевозок, при котором было бы перевезено максимальное количество продукта (чтобы поток перевозимого продукта был максимален). Ясно, что это количество зависит от числа имеющихся маршрутов (от числа нулей в матрице 11 |).

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

т

совпадает с общим количеством? а, продукта, имеющегося.

i=1.

m n

в пунктах отправления (для случая X ^а; - X Ь/) или с суммарной п i=i ;=i.

потребностью в продукте X в пунктах назначения (для слу;

т п ;=1.

чая X^ai — XVТакое же количество продукта можно пере;

1=1 .1=1.

везти, если нулей в матрице 11 а^. 11 достаточно много. При дальнейшем уменьшении количества нулей в матрице 11 | макси мально достижимое количество перевозок уменьшается.

Тот или иной план перевозок может быть определен заданием чисел х~ (i = 1, …, т; j = 1, …, п), указывающих, сколько следует перевозить продукта из i-ro пункта отправления в j-й пункт назначения. Числа х_; должны удовлетворять ряду требований, которые могут быть сформулированы следующим образом.

1. Все числа х_у. должны быть неотрицательными:

2. Если а ^ 0, то.

Это условие означает, что перевозка из i-ro в j-й пункт не производится, если эти пункты не связаны между собой.

3. Из каждого (i-ro) пункта отправления нельзя вывезти продукта больше, чем его имеется:

4. В каждый (j-й) пункт назначения нельзя ввезти количество продукта, превышающее потребность в нем:

Всякие m • п чисел x_i}, удовлетворяющие условиям (4.9) — (4.12), определяют некоторый план перевозок. При этом общее количество перевозимого продукта Ф определяется следующей формулой:

В соответствии со сказанным требуется найти такие т? п чисел x_ijt удовлетворяющих условиям (4.9)—(4.12), которые обращают функцию Ф в максимум.

Заметим, что фактическое число неизвестных в задаче не т? п, а меньше, так как условие (4.10) определяет ряд неизвестных, т. е. число неизвестных равно т • п минус количество чисел ане равных нулю.

Так же как и в транспортной задаче, здесь можно ввести ограничение пропускной способности каждого маршрута, наложив дополнительные ограничения на неизвестные х~ : < d_j},

где — максимальное количество продукта, которое можно везти из пункта i в пункт;.

В этом случае матрицу Ца^.Ц можно не задавать, а принять все пропускные способности cL, соответствующие запрещенным маршрутам (т.е. маршрутам, для которых а.= 1), равными нулю.

Эта задача, так же как и транспортная, может быть сформулирована в терминах заявок и каналов обслуживания. Пусть, как и в транспортной задаче, индекс i соответствует различным классам заявок, а индекс) — различным видам имеющихся каналов обслуживания. Равенство = 1 означает невозможность обслуживания заявки (-го класса каналом обслуживания j-го вида. Требуется так распределить заявки между каналами обслуживания, чтобы поток заявок, обслуженных без задержки, был максимален, т. е. чтобы создавшаяся очередь необслуженных заявок была минимальна.

В задаче о максимальном потоке иногда, так же как и в транспортной задаче, следует учитывать дополнительные ограничения по вывозу продукта, о которых говорилось выше. В этом случае наряду с условиями (4.9)—(4.12) неизвестные должны удовлетворять условиям (4.6).

Распределительная задача. Многие задачи линейного программирования, встречающиеся при решении вопросов планирования, могут быть сведены к задаче, одна из многочисленных экономических интерпретаций которой такова. Имеется т видов сырья в количествах а_р а₂,а_т единиц. Существуют п пунктов производства, в которых любой вид этого сырья может перерабатываться в готовый продукт, причем на изготовление единицы готового продукта в j-м пункте производства идет ау единиц сырья i-ro вида. Заданы количества Ь_р Ь₂, …, Ь_п единиц продукта, которые должны быть изготовлены на каждом из пунктов производства. Пусть — количество продукта, изготавливаемое в j-м пункте производства из сырья г-го вида, а с- — стоимость изготовления единицы продукта этим способом.

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

Требования отсутствия перерасхода каждого вида сырья могут быть записаны в виде неравенств.

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

а все неизвестные должны быть неотрицательными:

Стоимость производства, определяемая планом | х^, выражается формулой.

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

из Эта задача носит название распределительной. Часто ее называют также^{-задачей} (лямбда-задачей) или обобщенной транспортной задачей. Последнее название отражает то, что в частном случае, когда все а_у = 1, распределительная задача сводится к транспортной. В терминах перевозок распределительную задачу можно сформулировать иначе. Числа a_v а₂, а_т означают запасы топлива, сконцентрированные в т пунктах отправления, причем в различных пунктах различное топливо. Все это топливо или часть его требуется доставить к потребителям, причем для каждого потребителя указано количество тепла b_j (число калорий), которое должно быть получено в результате сжигания завезенного топлива.

Числа <�т. означают теплотворную способность топлива из i-ro пункта отправления, которая предполагается зависящей не только от источника снабжения, но и от того, какой потребитель это топливо сжигает. Расходы на транспортировку одной весовой единицы топлива из i-ro пункта отправления к)-му потребителю обозначим через и будем считать также известными. Всякая совокупность чисел х, означающих величины перевозок, совершаемых из пунктов отправления к потребителям, является планом задачи, если она удовлетворяет требованиям по обеспечению калориями каждого потребителя, т. е.

и если она не предполагает превышения запасов топлива, имеющихся в пунктах отправления:

При этом следует считать перевозки неотрицательными:

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

Итак, требуется найти минимум линейной функции (4.20) при условиях (4.17)—(4.19). Эта постановка несколько отлична от ранее приведенной. Однако если ввести замену переменных = а_ух_у и обозначить 1/а_у = а', с_у/а_у = с', то задача сведется к отысканию минимума линейной функции.

при условиях.

что с точностью до обозначений совпадает с ранее сформулированной распределительной задачей.

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

Задача оптимизации потоков в сетевой постановке. Условия транспортной задачи в матричной постановке предполагают, что все пункты делятся на две категории — отправления и назначения (производства и потребления), что каждый пункт потребления связан с каждым пунктом производства единственным маршрутом, а пункты одной категории не связаны между собой маршрутами.

Однако во многих практических задачах ситуация оказывается более сложной. Это относится прежде всего к задачам о реальных перевозках на железнодорожном или автомобильном транспорте, когда имеется сложная сеть коммуникаций, в узлах которой расположены пункты производства, потребления и так называемые перевалочные пункты, т. е. пункты, в которых нет ни производства, ни потребления, но через которые транзитом перевозится продукт. Последнее обстоятельство объясняется тем, что не всегда можно попасть непосредственно из любого пункта производства в любой пункт потребления, минуя промежуточные пункты. Другими словами, маршрут следования продукции из пункта производства в пункт назначения может состоять из последовательности коммуникаций, каждая из которых соединяет два «соседних пункта», причем таких маршрутов для заданного пункта производства и заданного пункта потребления может быть несколько.

В соответствии со сказанным введем понятие транспортной сети. Под транспортной сетью будем понимать совокупность пунктов (Р_р Р₂,…, P_N), некоторые из которых соединены направленными отрезками (коммуникациями) КЕсли существует коммуникация К₍., идущая от пункта Р₍ к пункту Я, то это означает, что из пункта Р_{ в пункт Я могут осуществляться перевозки продукта. Подчеркнем, что наличие коммуникации означает возможность только одностороннего движения.

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

Каждый пункт транспортной сети должен быть охарактеризован числом р₍ — объемом производства. В зависимости от знака этой величины все пункты делятся на пункты производства, пункты потребления и перевалочные пункты. Для пунктов производства числа p_i должны быть положительными, для пунктов потребления — отрицательными (противоположное объему производства число означает объем потребления). Для перевалочных пунктов объем производства полагается равным нулю.

Каждой коммуникации К~ следует приписать два числа — пропускную способность и стоимость перевозки. Первое из них (Д.) показывает, какое максимальное количество единиц продукта может быть перевезено по этой коммуникации, а второе (с₄.) определяет стоимость перевозки одной единицы продукта из пункта Р₍ в пункт Р₍ по коммуникации К~.

Пример транспортной сети изображен на рис. 4.7. Здесь имеется 10 пунктов Pj—Р₁₀. Положительные и отрицательные числа, проставленные в изображениях этих пунктов, означают объемы производства.

Пункты Р,—Р₃ — пункты производства с объемами производства соответственно 30, 70, 50 единиц; пункты Р₅—Р₇ — пункты потребления с объемами потребления, равными соответственно 60, 40, 50 единиц; пункты Р₄, P_g—Р₁₀ — перевалочные пункты (отсутствие в соответствующих кружочках объемов производства означает, что они равны нулю).

Направленные отрезки, соединяющие некоторые пункты, изображают коммуникации. Так, из пункта Рj в пункт Р₈ продукт может перевозиться по коммуникации К_{г 8}. В то же время из пункта Р₈ в пункт Р_] или в пункт Р₅ непосредственно, минуя промежуточные пункты, продукт перевозиться не может, ибо коммуникации К₈, иК₈ отсутствуют. В то же время между пунктами Р₄ и Р_д перевозки могут осуществляться непосредственно в обе стороны, ибо эти пункты соединены парой коммуникаций К_{4 9} и К_{9 4}. Пропускные способности коммуникаций представлены знаменателями дробей, стоящих у каждой коммуникации, а стоимости перевозок — числителями этих дробей.

р₆

Рис. 4.7. Пример транспортной сети.

Если задана транспортная сеть, то возникает задача организации перевозок по коммуникациям этой сети. Число единиц продукта, перевозимое по коммуникации К_{. из пункта Р в пункт Pj, обозначим через х^, поскольку мы условились рассматривать лишь коммуникации с односторонним движением, Ху > 0. Учет пропускной способности приводит к дополнительному требованию х. < d… Совокупность чисел {х^.}, удовлетворяющих условиям.

определяет некоторую систему перевозок по всем коммуникациям транспортной сети. Однако эта система, вообще говоря, не согласуется с объемами производства и потребления пунктов сети.

Количество единиц продукта, вывозимого из произвольного пункта в соответствии с системой перевозок {х^}, равно X ^xij> где E’i — множество номеров тех пунктов, в которые из пункта Р_; идут коммуникации. Точно так же количество единиц продукта, ввозимого в пункт Р., определяется выражением X ^xij> где Е"  — множество номеров пунктов, из которых.

j’eE/'.

в пункт Р_; идут коммуникации. Таким образом, разница между количеством вывозимого и количеством ввозимого продукта для пункта Р. равна.

Для того чтобы система перевозок {х^} согласовалась с объемами производства и потребления, необходимо, чтобы эта разница для каждого пункта была равна объему производства в этом пункте.

Отсюда приходим к следующему определению плана транспортной задачи на сети: планом называется любая совокупность чисел {х~}, удовлетворяющая условиям.

0<�х.<^;

вывоз > ввоза, то пункт производства; вывоз < ввоза, то пункт потребления; вывоз = ввозу, то транзит.

Легко подсчитать общую стоимость перевозок, определяемых планом {Ху}:

где суммирование ведется по всем коммуникациям транспортной сети.

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

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

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

Рассмотрим транспортную сеть, имеющую один пункт производства Р_р один пункт потребления P_N и N- 2 перевалочных пункта. Назовем потоком из пункта Р_у в пункт P_N систему перевозок, удовлетворяющую следующим условиям:

Величину р назовем величиной потока. Эта величина показывает, какое количество продукта вывозится из пункта P_v называемого источником. Поскольку для всех перевалочных пунктов существует баланс между количеством ввозимого и количеством вывозимого продукта (4.25), то ясно, что весь продукт, вывозимый из пункта Р_р должен прибыть в пункт P_N, что легко показать и аналитически. Для этого обозначим количество продукта, вывозимое из пункта P_N, через p_N. Оно определяется соотношением.

Сложим последнее равенство со всеми равенствами (4.25) и (4.26). Нетрудно видеть, что левая часть полученного равенства обращается в нуль, так как для любого числа стоящего со знаком «плюс», найдется это же число, стоящее со знаком «минус». Действительно, всякая коммуникация fC. выходит ровно из одного пункта Р₍ и входит ровно в один пункт Ру Поэтому одно из равенств (4.25) или (4.26), соответствующее пункту Ру содержит в левой части слагаемое, а другое, соответствующее пункту Ру — вычитаемое х_у. Таким образом, приходим к соотношению.

Итак, из пункта P_N вывозится отрицательное количество единиц продукта (—р), а это и означает, что в него ввозится р единиц, что и утверждалось.

Пункт P_N носит название «сток».

Задачей о максимальном потоке называется задача отыскания потока наибольшей величины из пункта Р_г в пункт P_N или, что-то же самое, задача нахождения максимума линейной функции (4.26) при линейных ограничениях (4.25) и (4.24).

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

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

Другим условием, необходимым для существования максимального потока, является наличие ограниченных пропускных способностей у достаточно большого числа коммуникаций. В противном случае поток может быть сделан сколь угодно большим.

Задача о максимальном потоке легко обобщается на случай, когда на транспортной сети задается несколько пунктов P_v Р₂, …, Р_к, из которых надо перевезти как можно больше продукта в несколько других пунктов Q_p Q₂,…, Q₍.

В этом случае под потоком понимается система перевозок, удовлетворяющая следующим условиям:

Здесь I — множество номеров всех пунктов транспортной сети, за исключением пунктов P_v Р₂, Р_к, Q_v Q₂, …, Q_;. Величиной потока р, которая максимизируется, называется суммарное количество продукта, вывозимое из пунктов Р_р Р₂, Р_к.

Метод решения задачи о максимальном потоке разработан американскими математиками Фордом и Фулкерсоном [11, 36, 38, 39].