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

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

(4.6).

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

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

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

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

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

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

где - заданные неотрицательные числа.

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

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

(4.6а).

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

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

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

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

(4.7).

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

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

(4.8).

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

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

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

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

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

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

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

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

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

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

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

• 1. Все числа должны быть неотрицательными:
  • (4.9)
• 2. Если , то

(4.10).

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

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

(4.11).

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

(4.12).

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

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

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

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

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

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

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