Материал: Д6520 Алексеев Математические методы в инженерии

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

Поскольку транспортная задача (ТЗ) является задачей линейного программирования, она может быть решена симплекс-методом. Но в силу специфики задачи (каждая переменная входит лишь в два уравнения системы (2), (3) и коэффициенты при переменных равны единице) оптимальный план ТЗ может быть получен путем некоторых преобразований транспортной таблицы. Как и в общем случае, оптимальный план ищется среди опорных решений.

Число переменных х_ij в ТЗ с m пунктами отправления и n пунктами назначения равно mn, а число уравнений в системах (2) и (3) равно m+n. Так как в закрытой ТЗ выполняется условие (5), то число линейно-независимых уравнений равно m+n–1. Следовательно, опорный план ТЗ может иметь не более m+n–1 отличных от нуля переменных. Это – базисные переменные.

Если в опорном плане число отличных от нуля переменных равно в точности равно m+n–1, то план является невырожденным, а если меньше – то вырожденным.

Для определения опорного плана существует несколько методов. Рассмотрим два из них – метод северо-западного угла и метод минимальной стоимости.

В методе северо-западного угла (МСЗУ) будем распределять товар, начиная с левой верхней клетки (1,1) и полагая х₁₁= min(a₁, b₁) (табл. 1). Если a₁ > b₁, то х₁₁= b₁ и потребитель В₁ будет полностью удовлетворён, и значит, надо положить х_i1= 0, i = 2  m («столбец 1 закрыт»). Переходим в соседнюю ячейку. Соседней здесь считается открытая ячейка снизу или справа от данной – в данном случае это ячейка (1,2). Она заполняется с учётом того, что запас пункта А₁ сократился на величину b₁ и составляет a₁–b₁.

Если же b₁ > a₁, то запас поставщика А₁ полностью исчерпан, и значит, надо положить х_1j = 0, j = 2  n («строка 1 закрыта»). Переходим в соседнюю ячейку – ячейку (2,1), учитывая, что потребность пункта В₁ сократилась на величину a₁ и составляет b₁–a₁. Аналогичным образом заполняются ячейки (1,2) или (2,1) и т. д. Последней заполняется ячейка (m, n). Рассмотрим применение этого метода на примере.

Примеры решения транспортных задач

Пример 1. Условия ТЗ заданы транспортной таблицей (табл. 2). Требуется составить опорный план перевозок методом северо-запад-ного угла.

Проверим, является ли задача закрытой. Так как = 130 не равна = 110, то ТЗ – открытая. Вводим фиктивного потребителя В₅,

b₅ = – = 20 (табл. 3).

Таблица 2 Таблица 3

Будем заполнять таблицу поэтапно.

Этап 1. х₁₁= min (а₁, b₁) = min(50,30) = 30. Закрыт 1-й столбец. Переходим в соседнюю ячейку (1,2) (табл. 4).

Таблица 4
Вj Аi	30	25	35	20	20
50	3 30	2 20	4 –	1 –	0 –
10	2 –	3 5	1 5	5 –	0 –
20	3 –	2 –	4 20	4 –	0 –
50	5 –	3 –	2 10	6 20	0 20

Этап 2. х₁₂ = min (а₁–b₁, b₂) = min(20,25) = 20. Закрыта 1-я строка. Переходим в соседнюю ячейку (2,2).

Этап 3. х₂₂ = min(10,5)= 5. Закрыт 2-й столбец. Переходим в соседнюю ячейку (2,3).

Этап 4. х₂₃ = min(5,35)= 5. Закрыта 2-я строка. Переходим в соседнюю ячейку (3,3).

Этап 5. х₃₃ = min(20,30)= 20. Закрыта 3-я строка. Переходим в соседнюю ячейку (4,3).

Этап 6. х₄₃ = min(50,10)=10. Закрыт 3-й столбец. Переходим в соседнюю ячейку (4,4).

Этап 7. х₄₄ = min(40,20)=20. Закрыт 4-й столбец. Переходим в соседнюю ячейку (4,5).

Этап 8. х₄₅ = min(20,20)=20. Закрыты 5-й столбец и 4-я строка. Заполнение таблицы закончено. Отметим, что число заполненных (базисных) клеток равно m+n–1 = 8, т. е. действительно построен опорный план перевозок.

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

Х_с-з=

(фиктивные поставщики и потребители в матрице перевозок не указываются). По этому плану из пункта А₁ завезено 30 ед. груза в В₁, 20 – в В₂, из А₂ завезено 5 ед. груза в В₂ и 5 – в В₃, из А₃ все 20 ед. груза завезены в В₃, из А₄ завезено 10 ед. груза в В₃ и 20 – в В₄. Груз в количестве 20 ед., «завезённый» в фиктивный пункт В₅, на самом деле остался в А₄. Затраты по плану Х_с-з составляют

z_с-з = 330 + 220 + 35 + 15 + 420 + 210 + 620 = 370 (ден. ед.).

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

Замечание 2. При использовании МСЗУ заполнение таблицы происходит чисто механически слева направо и сверху вниз без учёта тарифов перевозок. Поэтому полученный опорный план обычно далёк от оптимального. В рассматриваемом далее методе – минимальной стоимости (ММС) – порядок заполнения таблицы зависит от тарифов.

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

Пример 2. Рассмотрим применение ММС на решении той же ТЗ, что в примере 1 (табл. 2 и 3), и будем поэтапно заполнять табл. 3.

Этап 1. Начинаем, например, с ячейки (1,5), в которой мы имеем одну из минимальных стоимостей перевозки (с₁₅ = 0): х₁₅ = min(а₁, b₅) = min(50,20) = 20. Закрыт 5-й столбец. Переходим в соседнюю ячейку (табл. 5).

Таблица 5
Вj Аi	30	25	35	20	20
50	3 –	2 10	4 –	1 20	0 20
10	2 –	3 –	1 10	5 –	0 –
20	3 5	2 15	4 –	4 –	0 –
50	5 25	3 –	2 25	6 –	0 –

Этап 2. Среди оставшихся ячеек заполняем ячейку (1,4), имеющую одну из минимальных стоимостей (с₁₄ = 1): минимальных стоимостей (с₁₄ = 1): х₁₄ = min (а₁–b₅, b₄) = min (30, 20) = 20. Закрыт 4-й столбец. Переходим в соседнюю ячейку.

Этап 3. Среди оставшихся ячеек заполняем ячейку (2,3), имею-щую минимальную стоимость (с₂₃ = 1): х₂₃ = min(а₂, b₃) = min (10, 35) = 10. Закрыта 2-я строка. Переходим в соседнюю ячейку.

Этап 4. Среди оставшихся ячеек одну из минимальных стоимостей имеет ячейка (1,2), с₁₂=2. Поэтому х₁₂ = min(а₁–b₄–b₅, b₂) = = min(10,25) = 10. Закрыта 1-я строка. Переходим в соседнюю ячейку).

Этап 5. Среди оставшихся ячеек заполняем ячейку (3, 2), име-ющую одну из минимальных стоимостей (с₃₂ = 2): х₃₂ = min(20,15) = 15. Закрыт 2-й столбец. Переходим в соседнюю ячейку.

Этап 6. Среди оставшихся ячеек заполняем ячейку (4,3), имею-щую х₄₃ = min(50, 25) = 25. Закрыт 3-й столбец. Переходим в соседнюю ячейку.

Этап 7. Среди оставшихся ячеек заполняем ячейку (3, 1), имеющую минимальную стоимость (с₃₁ = 3): х₃₁ = min(5, 30) = 5. Закрыта 3-я строка. Переходим в соседнюю (последнюю) ячейку (4,1).

Этап 8. х₄₁ = min(25, 25) = 25. Закрыты 1-й столбец и 4-я строка. Заполнение таблицы закончено. Число заполненных (базисных) клеток равно m+n–1 = 8 , т. е. действительно построен опорный план.

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

Х_м.ст =

(фиктивные поставщики и потребители в матрице перевозок не указываются). По этому плану из пункта А₁ завезено 10 ед. груза в В₂ из А₂ завезено 10 ед. груза в В₃, из А₃ – 5 ед. груза завезено в В₁ и 15 – в В₂, из А₄ завезено по 25 ед. груза в В₁ и В₃. Те 20 ед. груза, «завезённые» в фиктивный пункт В₅, на самом деле остались в А₁. Затраты по плану Х_м.ст составляют z_м.ст = 210+120+110+35+215+525+225 = = 270 (ден. ед.), что на 100 ед. меньше, чем в МСЗУ.

Для ММС также справедливо замечание 2 (о нулевом базисном элементе), только здесь изменяется понятие соседней ячейки. Ячейкой, соседней с данной, считается любая открытая ячейка в данной строке и в данном столбце.

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

Таблица 6