Постановка транспортной задачи

Пусть в m пунктах производится определенное количество однородной продукции. Эту продукцию требуется доставить в n пунктов потребления. При этом количество производимой продукции в точности равно количеству потребляемой продукции. Стоимость перевозки единицы продукции из каждого пункта производства в каждый пункт потребления известна.

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

Для составления математической модели этой задачи введем следующие обозначения:

m – число пунктов производства;

i – номер пункта производства ();

n – число пунктов потребления;

j – номер пункта потребления ();

a_i– количество единиц продукции, производимое в i-м пункте производства;

b_j– количество единиц продукции, которое необходимо доставить в j-й пункт потребления;

c_ij– стоимость перевозки единицы продукции от i-го пункта производства к j-му пункту потребления;

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

Величины x _ijтребуется определить.

Совокупность чисел x _ijназывается планом перевозок груза, а матрица С = [ c _ij] – матрицей транспортных издержек.

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

(1.13)

в которых первые m равенств означают, что из каждого пункта производства вывозится весь произведенный продукт, а последние n равенств означают, что каждый пункт потребления полностью удовлетворяется.

Общая стоимость перевозок всей продукции равна

(1.14)

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

Решение транспортной задачи сводится к минимизации линейной функции F(x) (1.14) при ограничениях (1.13).

Условие разрешимости.

Теорема 1.10. Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы произведенной продукции совпадали с общими суммарными потребностями потребителей:

(1.15)

Следствие. Из m+n уравнений в системе ограничений транспортной задачи одно (любое) уравнение можно отбросить, так как оно вытекает из остальных m+n–1 уравнений.

Действительно, если определены количество груза у всех отправителей и потребность всех потребителей, кроме одного, то спрос последнего легко устанавливается как разница между общим запасом и общей потребностью других потребителей. Поскольку модель транспортной задачи содержит m+n–1 независимых уравнений, любой ее невырожденный план включает m+n–1 переменных с положительным значением. Поэтому из m´n возможных маршрутов перевозок в оптимальном плане транспортной задачи загружается не более m+n–1 маршрут.

Если план задачи включает меньше чем m+n–1 положительных переменных, то он называется вырожденным планом. О некоторых приемах, позволяющих избежать вырождения плана, будет сказано ниже. Опасность же возникновения цикла в транспортной задаче практически исключена.

Теорема 1.11. В транспортной задаче всегда существует оптимальный план, в котором число ненулевых компонент не будет превышать m+n-1.

При этом если исходные величины поставок a _iи b _jявляются целыми числами, то и все переменные в оптимальном плане будут целыми величинами. Свойство целочисленности оказывается практически важным при планировании перевозок неделимых грузов.

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

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

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

при условиях

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

,

где

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

Эти дополнительные переменные удовлетворяют следующему условию:

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

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

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

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

Другой вариант открытой транспортной задачи возникает тогда, когда спрос потребителей выше возможностей производителей. В этом случае задача формулируется следующим образом:

при условиях

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

Условия транспортной задачи обычно записываются в виде следующей таблицы:

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

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

I. Правило “северо-западного угла”

Условия задачи записываем в виде таблицы. Распределение поставок по данному правилу проиллюстрируем на примере. Начинают распределение поставок из первого пункта производства к первому пункту потребления, т. е. с верхней левой клетки таблицы. После ее заполнения следующей должна загружаться одна из соседних к ней клеток: либо в той же строке, либо в том же столбце. Если ни в одну из соседних клеток нечего поставить (т. е. возможности соответствующих строки и столбца уже исчерпаны), то в любую из них ставится нуль и от нее продолжается процесс последовательного распределения поставок груза. Этот прием гарантирует получение в исходном плане необходимого количества занятых клеток, равного m+n–1. В методе "северо-западного угла" первоначальный план совершенно игнорирует стоимости перевозок, так что он значительно отличается от оптимального плана.

II. Метод наименьшей стоимости

В "методе наименьшей стоимости" учитывается матрица C транспортных издержек. Суть метода состоит в следующем: в первую очередь заполняются клетки с минимальной во всей таблице стоимостью перевозки груза (c _ij). Грузопоток x _ijопределяется точно так же, как в методе "северо-западного угла", т. е. равняется наименьшему значению из остатка груза в i-м пункте отправления и недостающего груза в j-м пункте назначения.

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

Заполненные клетки таблицы, даже с нулевыми поставками, называются загруженными клетками, а пустые – свободными.

Дата добавления: 2015-11-14