Транспортная задача

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

Рассмотрим пример типичной транспортной задачи.

Таблица 7.6 – Пример транспортной задачи

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

Имеются два пункта производства, складирования товара (поставщи­ки 1, 2) и три пункта потребления (потребители 1, 2, 3). Поставщики не могут предоставить более Zl, Z2 ед. товара; потребителям требуется не менее Yl, Y2,Y3 ед. При этом Yl +Y2 +Y3 ≤Z1 +Z2.

Знаки неравенства могут поменять направление: поставщики предо­ставляют не менее (≥) Zl, Z2, а потребители используют не более (≤) Y1, Y2, Y3. Тогда Zl + Z2 ≤Yl + Y2 + Y3.

Обычно суммы Zl + Z2 и Y1 + Y2 + Y3 близки друг к другу (сбаланси­рованная транспортная задача).

С1, С2,..., С6 – параметры, характеризующие ситуацию (стоимость до­ставки 1 ед. товара от данного поставщика данному потребителю, руб./ед.; расстояние доставки, км; доход от поставки единицы и т. п.).

Требуется определить, сколько товара следует отправить от данного поставщика данному потребителю XI, Х2,..., Х6, чтобы минимизировать общие транспортные издержки или максимизировать общий доход (целе­вую функцию L):

L = С1 х X1 + С2 х Х2 +С3 х ХЗ + С4 х Х4 + С5 х Х5 + С6 х Х6 = min (max).

Количество неизвестных задачи М = 3 х 2 = 6; число ограничений N = =3+2 = 5;

R1 = 1 х Х1 + 1 х Х2 + l x X3 + 0 x X4 + 0 x X5 + 0 x X6 ≤ Zl;

R2 = 0 х X1 + 0 х Х2 + 0 х ХЗ + 1 х Х4 + 1 х Х5 + 1 х Х6 ≤ Z2;

R3 = l x Xl + 0 x X2 + 0 x X3 + l x X4 + 0 x X5 + 0 x X6 ≥ Yl;

R4 = 0 х X1 + 1 х Х2 + 0 х ХЗ + 0 х Х4 + 1 х Х5 + 0 х Х6 ≥ Y2;

R5 = 0 x Xl + 0 x X2 + 1 x X3 + 0 x X4 + 0 x X5 + l x X6 ≥ Y3.

Заполнение транспортной матрицы методом минимальной стои­мости по строке или столбцу. Метод минимальной стоимости по строке основан на том, что мы распределяем продукцию от поставщика Z_i не к любому из потребителей Y_j, а к тому, к которому стоимость перевозки минимальна. Если заявка потребителя полностью удовлетворена, то мы убираем его из расчетов и находим минимальную стоимость перевозки отоставшихся поставщиков Z_i.

Метод минимальной стоимости по столбцу аналогичен предыдущему. Их отличие состоит в том, что при применении второго способа мыраспределяем продукцию от поставщиков Z_i к потребителям Y_j по минималь­ной стоимости C_ji. Опорный план, составленный способами минимальных стоимостей, обычно более близок к оптимальному решению. Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными. Их чис­ло должно равняться т + п - 1. Необходимо отметить также, что встречаются такие ситуации, когда количество базисных клеток меньше, чем т + п - 1. В этом случае распределительная задача называется вырожденной. И следует в одной из свободных клеток поставить количество перево­зок, равное нулю.

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

Проверка оптимальности решения транспортной задачи методом потенциалов. Идея метода потенциалов для решения транспортной зада­чи сводится к следующему. Представим себе, что каждый из поставщиков Z_i вносит за перевозку единицы груза какую-то сумму Z_i; в свою очередь каждый из потребителей Y_j также вносит за перевозку груза сумму Y_j. Эти платежи передаются некоему третьему лицу (перевозчику). Обозначим Z_i + Y_j = K_ji (i=1...m;j=1...n) и будем называть величину K_ji псевдостоимо­стью перевозки единицы груза от Z_i к Y_j. Заметим, что платежи Z_i и Y_j не обязательно должны быть положительными; не исключено, что перевоз­чик сам платит тому или другому пункту какую-то премию за перевозку. Также надо отметить, что суммарная псевдостоимость любого допустимо­го плана перевозок при заданных платежах (Z_i и Y_j) одна и та же и от плана к плану не меняется.

До сих пор мы никак не связывали платежи (Z_i и Y_j) и псевдостоимости K_ji с истинными стоимостями перевозок C_ji. Теперь мы установим между ними связь. Для всех клеток Х_ji > 0 определим платежи (Z_i и Y_j) так, чтобы во всех базисных клетках псевдостоимости, были равны стоимостям:

K_ji = Z_i + Y_j = C_ji при Х_ji > 0.

Что касается свободных клеток (где Х_ji = 0), то в них соотношение между псевдостоимостями и стоимостями может быть каким угодно.

Оказывается, соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является план оптимальным или же он может быть улучшен. Существует специальная теорема: если для всех ба­зисных клеток плана (Х_ji > 0)

Z_i + Y_j = K_ji = C_ji,

а для всех свободных клеток (Х_ji = 0)

Z_i + Y_j = K_ji = C_ji,

то план является оптимальным и никакими способами улучшен быть не может.

В Интернете можно также ознакомиться с возможностью использова­ния MS Excel для решения транспортной задачи.

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