1.2. Решение транспортной задачи
1.2.1. Определение опорного плана транспортной задачи.
Решение транспортной задачи, как и всякой задачи ЛП начинается с нахождения допустимого опорного решения (опорного плана). Рассмотрим два метода нахождения опорного плана транспортной задачи: метод северо-западного угла и метод минимального элемента.
Введем основные определения и обозначения.
Условие транспортной задачи задают в виде транспортной таблицы (табл. 3.3) вида:
Таблица 3.3.
Решение транспортной задачи задают в виде матрицы (плана перевозок):
или в виде таблицы плана перевозок (табл. 3.4):
Таблица 3.4.
Элементы матрицы плана перевозок (ячейки, клетки таблицы) называют базисными, если они отличны от нуля; нулевые клетки таблицы называют свободными.
План перевозок – допустимый, если он удовлетворяет балансовым условиям (3.1): все заявки удовлетворены, все запасы исчерпаны.
Допустимый план – опорный, если в нем отличны от нуля не более чем r=m+n-1 базисных перевозок 
, а остальные перевозки равны нулю. Если отличных от нуля перевозок менее чем r=m+n-1, то такой план называют вырожденным опорным планом.
Оптимальный план перевозок – план с наименьшей стоимостью из всех допустимых планов перевозок.
Метод северо-западного угла для нахождения опорного плана ТЗ.
Шаг 0. Условие транспортной задачи задают в виде транспортной таблицы (табл. 3.3).
Шаг 1. Проверяют выполнение условия баланса (3.1). Если условие баланса не выполняется, т. е. задача открытая, то ее сводят к закрытому типу.
Шаг 2. Создают таблицу плана перевозок (табл. 3.4), в которой заполнены только объемы производства и объемы потребления. Далее начинают заполнять таблицу перевозок с левого верхнего (северо-западного) угла. При заполнении двигаются по строке вправо и по столбцу вниз.
Процесс продолжают до тех пор, пока не исчерпаются предложения и полностью не удовлетворится спрос.
Пример 1. Определить опорный план по методу северо-западного угла для транспортной задачи, заданной в табл. 3.5.
На первом шаге проверяют выполнение балансовых условий. Суммарный объем производства составляет: 200+40+110=350 условных единиц; суммарный объем потребления равен: 120+50+190+110=470. Следовательно, ТЗ – открытая. Для ее сведения к закрытому типу необходимо ввести четвертый пункт производства с объемом производства равным: 
=470-350=120 условных единиц. Так как пункт производства фиктивен, то стоимости перевозок продукции из этого пункта в пункты потребления нулевые (табл. 3.6).
Таблица 3.5
| Таблица 3.6
|
На втором шаге создают пустую таблицу плана перевозок и начинают ее заполнение (табл. 3.7).
В первую клетку помещают: 
(табл. 3.7). Заявки первого потребителя полностью удовлетворены, остальные клетки первого столбца заполняют нулями. Остаток продукции в первом пункте составляет: 200-120=80 условных единиц груза.
Далее двигаются по первой строке вправо и заполняют клетку (1,2): 
. Заявки второго потребителя полностью удовлетворены, оставшиеся клетки второго столбца заполняют нулями. Остаток продукции в первом пункте равен: 80-50=30 условных единиц груза.
Двигаются по первой строке вправо и заполняют клетку (1,3): 
. Предложения первого поставщика исчерпаны, клетка (1,4) заполняется нулем.
Далее заполняют таблицу плана перевозок по аналогии.
Полученный план перевозок (табл. 3.8) – допустимый, так как для него выполняются условия баланса и опорный, так как число базисных клеток равно 7 и r=m+n-1=4+4-1=7.
Таблица 3.7
| Таблица 3.8
|
Стоимость плана перевозок составляет:
.
Метод северо-западного угла — наиболее простой метод нахождения опорного плана, при его построении не учитываются стоимости перевозок. План перевозок, полученный по этому методу, обычно бывает достаточно далек от оптимального.
Метод минимального элемента для нахождения опорного плана ТЗ.
Метод минимального элемента при нахождении опорного решения учитывает стоимости перевозок, прежде всего, осуществляются перевозки (заполняются клетки транспортной таблицы) с минимальными стоимостями перевозок единицы продукции от производителя к потребителю.
Шаг 0. Условие транспортной задачи задают в виде транспортной таблицы (табл. 3.3).
Шаг 1. Проверяют выполнение условия баланса. Если условие баланса не выполняется, т. е. задача открытая, то ее сводят к закрытому типу.
Шаг 2. Создают таблицу плана перевозок (табл. 3.4), в которой заполнены только объемы производства и объемы потребления. Выбирают клетку таблицы, которой соответствует минимальная стоимость перевозки единицы продукции от производителя к потребителю. В выбранную клетку аналогично методу северо-западного угла помещают максимально возможное число единиц продукции, разрешенное ограничениями на запасы и заявки. После этого, если предложение производителя исчерпано, остальные клетки соответствующей строки заполняют нулями; если спрос удовлетворен, остальные клетки соответствующего столбца заполняют нулями.
Процесс продолжается до тех пор, пока не заполнены все клетки таблицы перевозок.
Пример 2. Определить опорное решение по методу минимального элемента для транспортной задачи, заданной в табл 3.5.
На первом шаге проверяют выполнение балансовых условий, сводят задачу к закрытому типу и переходят к табл. 3.6
На втором шаге создают пустую таблицу плана перевозок и начинают ее заполнение (табл. 3.9).
Таблица 3.9
Минимальная стоимость перевозки единицы продукции соответствует клеткам (4,1), (4,2), (4,3), (4,4): с41= с42= с43= с44=0. Начать заполнение таблицы перевозок можно с любой из этих клеток. Пусть 
. Остальные клетки четвертой строки и первого столбца заполняются нулями.
Из оставшихся клеток минимальная стоимость перевозки соответствует клетке (3,3), поэтому: 
. Запасы третьего поставщика полностью исчерпаны, потребности третьего потребителя полностью удовлетворены, поэтому оставшиеся клетки третьей строки и третьего столбца заполняются нулями.
Далее заполняется клетка (1,4), как имеющая наименьшую стоимость перевозок единицы продукции: 
. Оставшиеся клетки четвертого столбца заполняются нулями. Затем заносится в клетку (1,2): 
; в клетку (2,2): 
.
В результате получен допустимый план перевозок, все балансовые условия выполнены (табл. 3.9). План перевозок также опорный и вырожденный, так как число базисных клеток равно 5 и меньше r=7.
Стоимость плана перевозок составляет:
.
и значительно ниже стоимости плана, полученного методом северо-западного угла.
Примечание. Стоимость плана, полученного методом северо-западного угла, не всегда ниже стоимости плана, полученного методом минимального элемента.
1.2.2. Нахождение оптимального решения транспортной задачи
Метод потенциалов. Метод позволяет найти оптимальное решение транспортной задачи.
Идея метода потенциалов, его экономическая интерпретация. Пусть каждый из пунктов производства продукции 
вносит за перевозку единицы груза (неважно куда) какую-то сумму 
; в свою очередь, каждый из пунктов потребления 
также вносит за перевозку единицы груза (все равно, откуда) сумму 
; эти платежи передаются некоторому третьему лицу («перевозчику»).
Предположим, что интересы пунктов i и j не противоречат друг другу и они действуют как единая экономическая система. Перевозка единицы груза из i-го в j-ый пункт объективно стоит 
, а стороны вместе платят за эту перевозку «перевозчику» сумму:
, (3.9)
величина 
называется «псевдостоимостью» перевозки единицы груза из i-го пункта производства в j-ый пункт потребления.
Платежи 
и 
не обязательно должны быть положительными: не исключено, что «перевозчик» сам платит тому или другому пункту какую-то премию за перевозку.
Оптимальным будет такой план перевозок, при котором пункты i и j не переплачивают «перевозчику» ничего сверх объективной стоимости перевозок , т. е. такой план, любое отступление от которого не выгодно для пунктов производства и потребления, так как заставит их платить за перевозку больше, чем если бы они возили грузы сами.
В [3] доказано, что признаком оптимальности плана 
является выполнение двух условий.
1. Для всех базисных клеток:
. (3.10)
2. Для всех свободных клеток:
. (3.11)
План, обладающий такими свойствами, называется потенциальным, а соответствующие ему платежи (,) – потенциалами пунктов и .
Процедура построения потенциального (оптимального плана) состоит в следующем.
В качестве первого приближения к оптимальному берется любой опорный план. Для этого плана потенциалы (,), соответствующие базисным клеткам, подчиняются условию: сумма потенциалов (псевдостоимость) равна стоимости перевозки единицы груза (3.10). Уравнений всего m+n-1, а число неизвестных равно m+n. Следовательно, потенциал одного пункта можно задать произвольно (например, равным нулю). После этого из m+n-1 уравнений можно найти остальные потенциалы, а по ним вычислить псевдостоимости (3.9) для каждой свободной клетки. Если оказалось, что все эти псевдостоимости не превосходят стоимостей (3.11), то план оптимален. Если нет, то план может быть улучшен переносом перевозок по циклу.
Циклом в транспортной таблице называют несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90о. В каждой строке и в каждом столбце транспортной таблицы не может быть более чем две клетки (вершины) цикла.
Знаком «+» отмечаются те вершины цикла, в которых перевозки увеличиваются, а знаком «-» – те вершины, в которых они уменьшаются. Перенести какое-то количество единиц груза по циклу – это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах – уменьшить на то же количество. Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется. При любом циклическом переносе, оставляющем перевозки неотрицательными, допустимый план остается допустимым. Стоимость же этого плана может меняться – увеличиваться или уменьшаться.
Цена цикла – увеличение стоимости перевозок при перемещении одной единицы груза по циклу. Цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла. Стоимости, стоящие в положительных вершинах, берутся со знаком «+», а в отрицательных – со знаком «–».
Пример 3. В табл. 3.10 приведена транспортная таблица, в которой отмечен цикл. Пусть требуется загрузить клетку (4,1). Максимальное число единиц, которое может быть перенесено, равно 40, так как это минимальное количество единиц груза в отрицательных вершинах. Цена цикла:
.
Транспортная таблица после циклического переноса приведена в табл. 3.11. Стоимость плана увеличиться на 40 единиц и составит: z=2150+40=2190. Очевидно, что выполненный циклический перенос удаляет от оптимального решения и перенос по циклу имеет смысл только при отрицательной цене цикла.
Можно доказать, что для любой свободной клетки транспортной таблицы всегда существует цикл (и притом единственный), одна из вершин которого лежит в свободной клетке, а все остальные – в базисных клетках. Метод потенциалов основан на выделении циклов с отрицательной ценой и переносу единиц груза по этим циклам для достижения оптимального плана перевозок.
Таблица 3.10
| Таблица 3.11
|
Если количество базисных клеток в транспортной таблице меньше r=m+n-1, (план вырожденный), то необходимо перейти от него к невырожденному опорному плану. Для этого часть свободных клеток объявляют условно занятыми и работают с ними как с базисными клетками.
Пример 4. Построим цикл для загрузки клетки (3,1) в транспортной таблице (табл. 3.12).
Так как в отрицательных вершинах минимальное количество единиц груза равно нулю, то по циклу переносится нуль единиц груза. В результате такого фиктивного переноса стоимость плана не меняется, изменяется только занятая базисная клетка (табл. 3.13). В табл. 3.13 в условно занятых свободных клетках нули имеют нижний индекс «б».
Фиктивный перенос по циклу может применяться при решении транспортной задачи методом потенциалов.
Таблица 3.12
| Таблица 3.13
|
Приведем алгоритм метода потенциалов.
Шаг 0. Берут любой невырожденный опорный план перевозок, в котором отмечены m+n-1 базисных клеток (остальные клетки – свободные).
Шаг 1. Для этого плана вычисляют потенциалы (,), исходя из условия: в любой базисной клетке псевдостоимости равны стоимостям:
. (3.12)
Один из платежей назначают произвольно, например, равным нулю.
Шаг 2. Рассчитывают псевдостоимости для всех свободных клеток:
. (3.13)
Шаг 3. Проверяют условие: для всех свободных клеток псевдостоимость не превышает стоимости перевозок груза. Если условие выполняется, то план оптимален, иначе переходят к шагу 4.
Шаг 4. Улучшают план путем переброски перевозок по циклу, соответствующему любой свободной клетке с отрицательной ценой (для которой псевдостоимость больше стоимости). Если таких клеток несколько, то выбирают клетку с максимальной по модулю ценой цикла.
Шаг 5. Проверяют «невырожденность» нового опорного плана. Если план вырожден, то его сводят к невырожденному, объявляя часть свободных клеток условно занятыми, и переходят к шагу 1.
Шаги 1-5 алгоритма итерационно повторяются, пока не будет найден оптимальный план.
Пример 5. Решим транспортную задачу, заданную в табл 3.5. В примере 2 был найден вырожденный опорный план по методу минимального элемента (табл. 3.9) для этой транспортной задачи. Найдем оптимальный план методом потенциалов.
Для сведения плана к невырожденному в табл. 3.9 условно занимают две свободные клетки и объявляют их базисными. Клетки необходимо выбрать так, чтобы вокруг оставшихся свободных клеток можно было строить циклы. Например, нельзя одновременно объявить базисными клетки (1,1) и (2,1). Также свободным клеткам, которые условно занимаются, должна соответствовать как можно меньшая стоимость перевозки единицы груза.
На первом шаге вычисляют потенциалы производителей и потребителей (,), для чего составляется система уравнений:
|
|
;
;
;
;
;
; (3.14)
.Один из потенциалов задается произвольно, например: 
. Далее вычисляются потенциалы производителей и потребителей из системы уравнений (3.14). Результаты вычислений представлены в табл. 3.15.
На втором шаге рассчитывают псевдостоимости для всех свободных клеток. В табл. 3.15 вычисленные псевдостоимости указаны в клетках в левом верхнем углу.
На третьем шаге проверяют выполнение условий оптимальности. Для двух клеток (1,3) и (4,2) псевдостоимость выше стоимости, поэтому план не оптимален.
Таблица 3.14
| Таблица 3.15
|
На четвертом шаге для улучшения плана перевозок загружается переносом по циклу клетка (1,3), как имеющая максимальную по модулю цену цикла. Цена цикла равна -4. По циклу может быть перенесено максимум 10 единиц груза (табл. 3.16). Следовательно, циклический перенос приведет к уменьшению стоимости плана перевозок на 40 условных единиц.
В табл. 3.17 приведена транспортная таблица после циклического переноса. Стоимость плана составила: z=770-40=730.
Таблица 3.16
| Таблица 3.17
|
На пятом шаге проверяют «невырожденность» нового опорного плана. В табл. 3.17 число базисных клеток равно 7. Следовательно, план невырожденный опорный и можно переходить ко второй итерации, к шагу 1.
В табл. 3.18 приведены потенциалы производителей и потребителей, псевдостоимости для нового опорного плана. В клетке (4,2) псевдостоимость превышает стоимость, следовательно, план не оптимален и необходимо загрузить клетку (4,2) путем циклического переноса.
Выполняется фиктивный перенос по циклу 0 единиц груза. В результате меняется условно занятая клетка (вместо клетки (4,3) – занимается клетка (4,2)). Стоимость плана при этом не меняется. Полученная транспортная таблица приведена в табл. 3.19.
Таблица 3.18
| Таблица 3.19
|
В табл. 3.20 приведена транспортная таблица, соответствующая третьей итерации. В клетке (2,1) псевдостоимость превышает стоимость, поэтому клетка (2,1) загружается с помощью переноса груза по циклу.
Таблица 3.20
По циклу переносится 40 единиц груза. Итоговая транспортная таблица приведена в табл. 3.21. Цена цикла равна -1, поэтому стоимость плана уменьшится на 40 единиц и составит: z=730-40=690.
Далее вычисляются потенциалы поставщиков, потребителей и псевдостоимости для свободных клеток. Так как для всех свободных клеток псевдостоимости не превышают стоимостей (табл. 3.21), полученный план перевозок оптимален, ему соответствует минимальная стоимость перевозки всех грузов.
Таблица 3.21
Оптимальный план перевозок транспортной задачи в матричном виде:
.
Стоимость оптимального плана:
.
Основные порталы (построено редакторами)