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

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

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

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

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

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

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

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

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

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

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

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

(4.1).

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

(4.2).

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

(4.3).

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

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

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

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

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

(4.4).

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

Математически транспортная задача линейного программирования формулируется следующим образом: найти значения неизвестных (), удовлетворяющие условиям (4.1)-(4.3) и обращающие в минимум линейную функцию (4.4).

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

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

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

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

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