Лекции Хуторецкий

Обратно, если (39) выполнено, то построим план поставок следующим образом. От-

правляем товар от поставщика 1 потребителю 1, пока есть товар у поставщика и не удовле-

творен потребитель. Если кончится товар у поставщика, перейдем к следующему поставщи-

ку. Если будет удовлетворена потребность, перейдем к следующему потребителю. Продол-

жаем процедуру до удовлетворения всех потребностей; допустимость полученного плана очевидна. #

Если не все поставки возможны (ТЗМП с запретами), то соответствующий двудольный граф G не является полным. Задачу с запретами можно свести к исходной, если положить cij

равным достаточно большому числу для всех пар (i, j)(V1 V2) \ E. Если исходная задача разрешима, то минимизация затрат подавит перевозки по добавленным «дорогим» дугам.

Заметим, что для задачи с запретами условие (39) является необходимым, но не достаточным условием разрешимости задачи. Если в оптимальном решении преобразованной задачи все перевозки по «запрещенным» дугам равны нулю, то остальные перевозки дают оптимальный план исходной задачи, в противном случае исходная задача неразрешима(1).

Определение. Если (39) выполняется как равенство, то задачу (35) – (38) называют

замкнутой или сбалансированной.

Следствие 3.2.(2) Предположим, что задача (35) – (38) разрешима.

(а) Если задача замкнута, то все ограничения (36) и (37) в любом допустимом решении выполняются как равенства (потребители получают в точности по потребностям, и весь то-

вар распределяется).

(б) Если задача не замкнута и все cij положительны, то в оптимальном решении ограниче-

ния (37) выполняются как равенства (потребности удовлетворены в точности), а некоторые из ограничений (36) ― как строгие неравенства (излишки у поставщиков).

Следствие 3.3. Матрица ТЗМП (35) – (38) вполне унимодулярна.

Доказательство. Переменная xij входит с коэффициентом 1 в одно из ограничений (37) и

одно из ограничений (38). Распределим строки матрицы задачи между двумя множествами: в

первое включим строки, соответствующие ограничениям (37), во второе ― строки, соответ-

ствующие ограничениям (38). Остается только применить теорему 3.3. #

(1)Гимади Э.Х., Глебов Н.И. Математические модели и методы принятия решений. Новосибирск: НГУ, 2008 (стр. 71).

(2)Доказательство оставляем читателю.

42

Существует эффективный алгоритм для решения замкнутой ТЗМП (метод потенциа-

лов)(1). Как и симплекс-метод, он находит оптимальное БДР задачи в канонической форме.

Если планируются поставки неделимого товара, то правые части ограничений являют-

ся, естественно, целыми числами. В этом случае, как показывают следствия 3.3 и 3.1, цело-

численность оптимального решения (полученного симплекс-методом или методом потен-

циалов) гарантирована без включения в задачу условия целочисленности xij.

3.2.2. Несбалансированные задачи

Если задача разрешима, но не сбалансирована (наличие товара больше потребности), то ее можно сбалансировать введением фиктивного «потребителя» с номером 0 и потребностью

Этот нулевой пункт потребления можно интерпретировать как склад невостребованного то-

вара. Затраты ci0 можно положить равными нулю (излишки товара бесплатно остаются у по-

ставщика). Но лучше в качестве ci0 использовать оценку убытка, который возникает у по-

ставщика i вследствие невостребованности единицы товара. Тогда задача будет по возмож-

ности минимизировать указанные убытки.

Предположим, что задача неразрешима. Тогда, по теореме 3.4,

Удовлетворить потребности невозможно, но можно наилучшим образом распределить на-

личный товар. Для этого следует замкнуть задачу, добавив фиктивного «поставщика» с но-

мером 0 и мощностью

Такой пункт поставки «распределяет» дефицит между потребителями. Если для оперирую-

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

жить c0j = 0 для всех j. Но желательно в качестве c0j использовать денежную оценку ущерба от недопоставки единицы товара потребителю j, если ситуация позволяет получить такую оценку. Например, c0j может быть равно штрафу за недопоставку единицы товара потребите-

лю j.

(1) Волков И.К., Загоруйко Е.А. Исследование операций. М.: Изд-во МГТУ им. Н.Э. Баумана, 2000 (раз-

дел 5.5).

43

Доказательство. Задача (35) – (38) разрешима по теореме 3.2. Тогда задача (40) – (42)

разрешима по первой теореме двойственности. Пусть (p*, q*) ― решение задачи (40) – (42).

Зафиксируем ε R и построим векторы p(ε), q(ε) следующим образом:

p(ε) = (pi(ε) | i 1, m ), q(ε) = (qj(ε) | j 1, n ), pi(ε) = pi* – ε, и qj(ε) = q*j + ε.

Векторы p(ε), q(ε) удовлетворяют условиям (41) при любом ε R и существует число ε0 ≤ 0

такое, что условия (42) для p(ε) и q(ε) выполнены при всех ε ≥ ε0 и нарушаются при ε < ε0.

Значит, набор (p(ε), q(ε)) является допустимым решением задачи (40) – (42), если и только если ε[ε0, ∞). При этом

Для натурального числа k обозначим 1k вектор из R1 k, все координаты которого равны единице. По доказанному, луч {(p, q) | p = p(ε0) – λ1m, q = q(ε0) + λ1n, λ ≥ 0} состоит из опти-

мальных решений задачи (40) – (42). #

Если ТЗМП замкнута, то многочисленность решений двойственной задачи, доказанная теоремой 3.5, осложняет использование двойственных оценок. Однако симплекс-метод на-

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

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

ную оптимального значения целевой функции по правой части этого ограничения. При этом для замкнутой задачи (35) – (38) допустимы только односторонние вариации правых частей ограничений: увеличение Si или уменьшение Dj, ― в противном случае возмущенная задача окажется несовместной.

По утверждению (а) следствия 3.2 в ограничениях (37) и (38) замкнутой ТЗМП можно неравенства заменить равенствами. Именно такой вид должна иметь задача для применения метода потенциалов. Но если все ограничения являются равенствами, то всякое изменение правой части любого ограничения сделает задачу несовместной. В таком случае теневые це-

ны позволяют оценивать последствия только согласованных изменений параметров задачи

(например, единичного увеличения Si и такого же увеличения Dj для каких-то i и j).

Итак, хорошо интерпретируемые двойственные оценки находятся в результате решения ТЗМП вида (35) – (38) с ограничениями-неравенствами, даже в случае сбалансированности.

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

45

3.3.Задача о назначениях

3.3.1.Основная модель

Задача о назначениях (максимальное паросочетание в двудольном графе) является ча-

стным случаем сбалансированной ТЗМП при Si = Dj = 1 для всех i, j. Название задачи связано со следующей интерпретацией.

Есть n исполнителей и n работ. Исполнитель i выполняет работу j с затратами cij. Нуж-

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

нены с минимальными суммарными затратами.

Введем переменные xij для i 1, n , j 1, n . Будем считать, что xij = 1, если исполнитель i

назначен на работу j, в противном случае xij = 0. Пусть x = (x11, …, xmn)T. Теперь задача фор-

мализуется следующим образом:

Целевая функция (43) описывает суммарные затраты. Ограничения (44) требуют, чтобы

каждый исполнитель был назначен ровно на одну работу (для каждого i ровно одна перемен-

ная xij равна единице). Условие (45) гарантирует, что на каждую работу будет назначен ис-

полнитель (один).

Задача (43) – (45), (47) является сбалансированной ТЗМП. Это линейная релаксация задачи

(43) – (46). Пусть X – множество ее допустимых решений. Разрешимость задачи (43) – (45), (47) следует из теоремы 3.4. По утверждению (г) теоремы 2.3 среди оптимальных решений задачи есть угловая точка множества X. По теореме 2.4 эта точка является базисным решени-

ем задачи.

Пусть x = (xij | i 1, n , j 1, n ) ― БДР задачи (43) – (45), (47). Из (44) ясно, что 0 ≤ xij ≤ 1.

По следствиям 3.3 и 3.1 все БДР задачи (43) – (45), (47) целочисленны. Поэтому xij{0, 1}.

Следовательно, вместо задачи (43) – (46) можно решать ее линейную релаксацию любым ме-

тодом, который находит БДР, например, симплекс-методом или методом потенциалов. Су-

46

ществует более быстрый алгоритм решения задачи о назначениях (венгерский алгоритм)(1).

Он находит базисное (и, следовательно, целочисленное) решение задачи (43) – (45), (47).

3.3.2. Варианты постановки задачи

Если известен эффект eij ≥ 0 от выполнения работы j исполнителем i, то максимизация суммарного эффекта достигается решением задачи (43) – (45), (47) при сij = –eij.

Предположим, что надо распределить n работ между m исполнителями, причем на каж-

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

нить более одной работы, исполнитель i выполняет работу j с затратами cij > 0. Тогда ЦФ

(43) и ограничения (44) и (45) примут вид

i 1

По теореме 3.4 неравенство m ≥ n является необходимым и достаточным условием раз-

решимости задачи (48) – (50), (47). При m > n задача выберет эффективного исполнителя для каждой работы. Условие минимизации затрат гарантирует, что на одну работу не будут на-

значены два исполнителя.

Пусть m > n и eij ≥ 0 ― эффект от выполнения работы j исполнителем i. При максими-

зации суммарного эффекта ограничения (49), (50), (47) не обеспечивают назначение единст-

венного исполнителя на каждую работу. Изменим целевую функцию (48) и ограничение (50):

i 1

Из m > n и eij ≥ 0 следует, что существует решение задачи (51), (49), (52), (47), в кото-

ром на каждую работу назначен один исполнитель. Если же eij > 0 для всех i, j, то этим свой-

ством обладает любое решение указанной задачи.

Заметим, что при m > n задачу можно свести к исходной введением m – n фиктивных

«работ». Затраты каждого исполнителя на выполнение фиктивной работы следует устано-

вить запретительно большими или равными реальному ущербу от незанятости этого испол-

нителя.

(1) Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. М.: Мир, 1984 (раздел 2.12.2).

47

Теперь предположим, что m < n и исполнитель не может выполнить более одной рабо-

ты. Тогда невозможно выполнить все работы. Но можно выбрать для выполнения m работ так, чтобы минимизировать затраты или максимизировать эффект.

Задача минимизации суммарных затрат (при сij > 0 для всех i, j):

Эта задача находит одну работу для каждого исполнителя и не более одного исполнителя для каждой работы.

Задача максимизации суммарного эффекта (при eij > 0 для всех i, j):

Здесь требование максимизации обеспечивает выполнение m самых выгодных работ, а огра-

ничения гарантируют взаимно однозначное соответствие между исполнителями и выпол-

няемыми работами.

Кроме того, при m < n задача сводится к исходной введением n – m фиктивных «испол-

нителей». Затраты на «выполнение» работы фиктивным исполнителем следует задать запре-

тительно большими или равными ущербу от невыполнения этой работы.

Во всех описанных вариантах постановки задачи о назначениях целочисленность угло-

вых решений задачи сохраняется. Это позволяет получать целочисленное решение задачи,

решая ее линейную релаксацию любым методом, который находит угловое решение.

3.4.Транспортная задача в сетевой постановке

3.4.1.Основная модель

Определения и обозначения.

Взвешенный граф G = (V, E) называют транспортной сетью, если каждой вершине i V сопоставлена интенсивность bi, каждой дуге (i, j) E сопоставлены стоимость (пере-

мещения единицы потока по дуге) cij и пропускная способность rij R+ {+∞}.

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

Вершину i транспортной сети называют: источником, если bi < 0; стоком, если bi > 0;

нейтральной вершиной, если bi = 0.

Множества источников, стоков и нейтральных вершин обозначим I–, I+, I0 соответст-

венно.

Потоком в транспортной сети G = (V, E) называют вектор x = (xij | (i, j) E) такой, что:

48

― стоимостью потока, а ограничение (53) ― условием непрерывности потока.

Транспортная задача в сетевой постановке (ТЗСП)(1) формулируется следующим об-

разом: для данной транспортной сети найти поток минимальной стоимости.

Величину bi можно интерпретировать как чистую потребность пункта i в товаре. В ис-

точниках наличие товара больше потребности на |bi|; в стоках потребность больше наличия на bi; в нейтральных вершинах потребность равна наличию, эти вершины являются транзит-

ными пунктами.

Условие (53) для стока i требует удовлетворения спроса (ввоз больше вывоза хотя бы на bi). Для источника i перепишем (53) следующим образом:

xij ≤ |bi| +

вывоз не больше суммы наличия и ввоза. Для нейтральной вершины вывоз не может превы-

шать ввоз.

Запрет на перевозку по дуге (i, j) можно отразить в ТЗМП разными способами: исклю-

чить дугу (i, j) из множества E; сделать затраты cij достаточно большими; установить для ду-

ги (i, j) нулевую пропускную способность.

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

ждению (г) теоремы 2.2 она разрешима, если и только если совместна и ограниченна.

Аналогом теоремы 3.4 для ТЗСП является следующий результат.

Теорема 3.6 (о совместности ТЗСП).(2)

(а) Если ТЗСП совместна, то

(б) Если выполняется условие (56) и в транспортной сети существует путь с достаточно большими пропускными способностями из любого источника в любой сток, то ТЗСП совме-

стна.

(1)Другое название ― транспортная задача с промежуточными пунктами

(2)Доказательство оставляем читателю.

49

Теорема 3.7 (об ограниченности ТЗСП). Совместная ТЗСП с транспортной сетью G ог-

раниченна тогда и только тогда, когда в графе G нет контура отрицательной суммарной стоимости с бесконечной пропускной способностью.

Доказательство.

1. Предположим, что в графе G = (V, E) есть контур с вершинами i(1), …, i(n + 1) = i(1)

такой, что ri(k)i(k+1) = +∞ для k 1, n и

n

ci (k )i (k 1) = a < 0, k 1

Пусть x = (xij | (i, j) E) ― поток в сети (существует, так как задача совместна по предположе-

нию). Если поток по каждой дуге контура увеличить на ε > 0, не меняя потоки по остальным дугам, то получим вектор x(ε). Легко проверить, что этот вектор удовлетворяет условиям

(53), (54) и, следовательно, является потоком. При этом функция (55) на x(ε) принимает зна-

чение С(x(ε)) = C(x) + εa и неограниченно убывает с ростом ε.

2. Предположим теперь, что задача совместна и в графе G нет контура отрицательной суммарной стоимости с бесконечной пропускной способностью. В графе может быть конеч-

ное число (обозначим его N) простых контуров с отрицательной суммарной стоимостью. Ес-

ли N > 0, то присвоим этим контурам обозначения Ks, s 1, N . Стоимость и пропускную спо-

собность контура с номером s обозначим Cs и rs соответственно. Пусть x = (xij | (i, j) E) ―

поток в сети. Положим

(множество дуг с ненулевыми потоками и множество инцидентных им вершин) и рассмот-

рим граф G(x) = (V(x), E(x)).

Допустим, что в G(x) есть контур i(1), …, i(n + 1) = i(1) неотрицательной суммарной стоимости. Уменьшив поток по каждой дуге этого контура на величину

= min{xi(k)j(k) | k 1, n },

получим поток z такой, что C(z) ≤ C(x) и число контуров неотрицательной суммарной стои-

мости в графе G(z) меньше, чем в графе G(x).

Допустим, что в G(x) есть контур i(1), …, i(n + 1) = i(1) отрицательной суммарной стоимости. Тогда граф содержит один из контуров Ks, s 1, N . Построим поток z, уменьшив потоки по всем дугам контура на = min{xi(k)j(k) | k 1, n }. Ясно, что C(x) = C(z) + Cs ≥ C(z) + rsCs и число простых контуров отрицательной суммарной стоимости в графе G(z) меньше,

чем в графе G(x).

50