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

Транспортная задача – это задача о минимизации расходов на перевозку грузов. Классическая транспортная задача формулируется следующим образом.

Имеется некоторое количество (m) пунктов отправления:

A1, A2, …, Am , (2.79)

в котором сосредоточены запасы какого-либо однородного товара в количествах

a1, a2, …, am . (2.80)

Имеется также n пунктов назначения:

B1, B2, …, Bn , (2.81)

подавших заявки на определенное количество товара соответственно:

b1, b2, …, bn (2.82)

Предполагается, что сумма всех заявок равна сумме всех запасов

Решение транспортной задачи - student2.ru . (2.83)

Стоимость перевозки товара из пункта отправления i в пункт назначения j известна для всех вариантов перевозок и равна сij­. Таким образом, имеется матрица стоимостей перевозок:

Решение транспортной задачи - student2.ru . (2.84)

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

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

Рассмотрим математическую формулировку задачи.

Введем некоторые обозначения:

xij – количество груза, отправляемого из i-го пункта отправления Аi в j-й пункт назначения Bj (i = 1, …, n; j = 1, …, m). Переменные x11, x12, …, xmn должны быть неотрицательны и удовлетворять следующим условиям:

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

Решение транспортной задачи - student2.ru . (2.85)

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

Решение транспортной задачи - student2.ru . (2.86)

3. Стоимость всех перевозок должна быть минимальной.

Решение транспортной задачи - student2.ru

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

В транспортной таблице записываются:

- пункты отправления (заголовки строк) и назначения (заголовки столбцов);

- запасы, имеющиеся в пунктах отправления (последний столбец таблицы);

- заявки, поданные пунктами назначения (последняя строка таблицы);

- стоимости перевозок из каждого пункта отправления в каждый пункт назначения (табличная часть).

    Пункты назначения
    B1 B2 ….. Bn Запасы аi
Пункты отправления A1 C11 C12 ….. C1n a1
A2 C21 C22 ….. C2n a2
. . . . . . . . . . . . . . . . . .
An Cm1 Cm2 . . . Cmn am
  Заявки bi b1 b2 . . . bn Решение транспортной задачи - student2.ru

Для решения транспортной задачи используется надстройка «Поиск решения» (Сервис ® Надстройки ® Поиск решения). Перед использованием механизма поиска решения необходимо ввести исходные данные и расположить их на листе соответствующим образом. Рассмотрим процесс решения транспортной задачи на примере.

Пример решения.

Предположим, необходимо организовать поставки товаров в какой-то город N. В городе N существует спрос на следующие товары:

Наименование товара Спрос, ед.
Товар1
Товар2
Товар3
Товар4 5 000
Товар5 10 000

Товары находятся в разных городах на разных оптовых базах. Запасы товаров на складах в различных городах представлены ниже в таблице.

Наши рекомендации