Классическая транспортная задача и ее модификации

Если требуется решение вопросов о выборе схемы прикрепления поставщиков и потребителей продукции, используются модели транспортного типа. Классическая транспортная задача заключается в планировании прикрепления поставщиков к потребителям продукции и формулируется следующим образом: однородный продукт, находящийся в m пунктах производства в количестве Р₁, Р₂,...Р_m, требуется доставить в n пунктов потребления. Потребность продукции в этих пунктах равна S₁, S₂,...S_n.

Экономико-математическая модель задач транспортного типа:

целевая функция - затраты на перевозку продукта должны быть минимальными:

(5.1)

Ограничения.

1. Вся продукция из предприятий поставщиков отправляется потребителям:

(5.2)

2.Все потребители обеспечены продукцией:

(5.3)

3. Мощность поставщиков равна потребности в продукции (условие закрытости):

(5.4)

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

1. Запрет каких-либо перевозок.

Если между поставщиками и потребителями продукции не существует маршрутов (связей) или ими нельзя пользоваться, можно задать стоимость перевозки с_ij, намного превышающую стоимость остальных перевозок (например, 99999).

2. Ограниченность пропускных способностей коммуникаций.

Это условие учитывается введением ограничений лимитирующих наибольшее значение объема перевозки по конкретному маршруту:

(5.5.)

где d_ij - пропускная способность транспортной линии.

3. Нарушение условия равенства производства и потребления (открытая транспортная задача).

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

(5.6)

Транспортная задача сводится к классическому виду путем введения фиктивного потребителя S _m+1 с потребностью

(5.7)

В целевой функции должны учитываться затраты, связанные с хранением и с потерей излишней продукции в каждом пункте производства.

Если суммарный объем производства меньше суммарного объема потребления, необходимо учитывать не только транспортные расходы, но и ущерб от недопоставок. В этой задаче

(5.8)

и ограничения на продукцию, поступающую в каждый пункт потребления, будут:

(5.9)

Этот случай также сводится к классической транспортной задаче путем введения фиктивного поставщика с объемом производства

(5.10)

Пример решения задачи по планированию перевозок. Практическое задание 3

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

Исходные данные представлены в таблице 5.1.

Таблица 5.1 - Исходные данные для расчета

В соответствующих клетках таблицы задана стоимость перевозок 1 тонны груза от поставщиков к потребителям - с_ij, тыс.р. за 1 тонну. Потери, связанные с хранением продукции у поставщиков составляют: 5, 7, и 4 тыс. р. за 1 тонну для базы N 1, 2 и 3 соответственно.

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

Решим задачу с использованием программы симплекс-метода. Размерность задачи составляет переменных.

Симплекс-матрица представлена на рис. 5.1.

Необходимо представить симплекс-матрицу в виде формул.

Рис. 5.1 – Симплекс-матрица транспортной задачи

Решение задачи в системе электронных таблиц EXCEL осуществляется с помощью пункта меню «Сервис», «Поиск решения».

Рис.5.2 – Диалоговое окно «Поиск решения»

Таблица 5.3 - Результаты решения

По результатам расчета можно сделать следующие выводы. Возможная минимальная стоимость всех перевозок составит 6840 руб.

При этом на объект N 1 продукция доставляется с базы N 3 в объеме 100 тонн; на объект N 2 - с базы N 2 в объеме 120 тонн; на объект N 3 - с базы N 2 в объеме 100 тонн и с базы N 3 в объеме 100 тонн; на объект N 4 - с базы N 1 в объеме 210 тонн и с базы N 4 в объеме 120 тонн.

Данные для проведения расчетов эффективности перевозок по вариантам представлены в Приложении 5.