36. Транспортная задача: стандартная постановка и особенности решения.

Для решения задачи построим ее математическую модель. Обозначим количество заводов N, а количество магазинов M. Для нумерации заводов и магазинов введем индексы i и j. Индекс i пробегает целочисленные значения от 1 до N и указывает номер завода, индекс j принимает значения от 1 до M и соответствует номеру магазина. Объем производства i-го завода обозначим a_i, объем спроса j-го магазина - b_j. Условие баланса спроса и предложения имеет вид

. (7.1)

Неизвестными величинами в данной задаче являются объемы перевозок, которые мы обозначим x_ij. Величина x_ij – это объем перевозок с i-го завода в j-й магазин. Затраты на перевозку единицы продукции из пункта i в пункт j по аналогии обозначим c_ij. Очевидно, что величины x_ij и c_ij в нашей задаче могут принимать лишь неотрицательные значения

, (7.2.)

. (7.3)

Стоимость одной перевозки составит x_ijc_ij, а общие транспортные расходы Z будут складываться из затрат по каждому маршруту:

. (7.4)

По условию задачи требуется минимизировать совокупные затраты на перевозки. В нашей модели оптимальному графику перевозок соответствует минимальное значение функции Z. Если не накладывать на величины x_ij и c_ij дополнительных условий и попытаться минимизировать целевую функцию (3.5.4), то в результате мы получим Z = 0 и x_ij = 0. Такой результат, очевидно, не может быть удовлетворительным ответом. Для правильного решения поставленной задачи необходимо ввести ограничения на объемы вывозимой и ввозимой продукции. Объем вывозимой с i-го завода продукции должен быть равен объему производства a_i, объем ввозимой продукции должен соответствовать объему спроса b_j:

, (7.5)

. (7.6)

Выражения (7.1)-(7.6) составляют математическую модель сбалансированной транспортной задачи. Если спрос и предложение не сбалансированы, то в модель нужно ввести фиктивные пункты производства или пункты потребления. В случае дефицита вводится фиктивный завод, стоимость и объем перевозок с которого равны штрафу за недопоставку и объему недопоставки соответственно. В случае перепроизводства продукции вводится фиктивный магазин, стоимость и объем перевозок в который полагается равной стоимости складирования и объему излишней продукции соответственно.

Рассмотрим решение сбалансированной транспортной задачи средствами OpenOffice.org Calc. Пусть имеется 3 завода (N=3) и 4 магазина (M=4). Введем в рабочий лист данные об объемах производства и спроса как показано на рис. 7.4. Для проверки баланса (выражение (7.1)) просуммируем значения в диапазонах B4:B6 и G4:G7, затем сравним вычисленные суммы в ячейке C10 с помощью формулы

«=IF(B7=G8;"Задача сбалансирована";"Нарушен баланс!")».

Далее в диапазон B14:E16 вводим данные о себестоимости перевозок между заводами и магазинами.

Для распределения объемов перевозок между экономическими объектами создадим таблицу «Объемы перевозок» (рис. 7.5). Для проверки условий (7.5) и (7.6) в ячейках B23:E23 и F20:F22 вычислим суммы строк и столбцов таблицы «Объемы перевозок». Суммы по столбцам соответствуют объемам ввозимой продукции, а по строкам – объемам вывозимой продукции. Значения объемов перевозок заранее неизвестны, для определенности в качестве начального приближения вводим в ячейки B20:E22 нулевые значения. Для вычисления целевой функции (7.4) введем в ячейку E25 формулу

«=SUMPRODUCT(B14:E16;B20:E22)».

Теперь рабочий лист содержит всю необходимую информацию для «Поиска решения». Выполним команду «Сервис|Решатель» и заполним поля открывшегося диалогового окна (рис. 7.6). Условия (7.2), (7.5) и (7.6) вводим в диалог «Решатель» в виде ограничений. Для корректного решения линейной задачи выберем соответствующий алгоритм в диалоговом окне «Параметры» и установим все необходимые параметры. После нажатия кнопки «Решить» «Решатель» находит оптимальный план перевозок грузов, показанный на рисунке