Транспортной задачи

Распределительный метод решения

Пусть дан некоторый опорный план. Для каждой свободной клетки таблицы перевозок вычислим алгебраические суммы стоимостей в вершинах цикла D_ij. Так, для клетки (4,1) получим

D₄₁ = 6 – 5 + 4 – 3 + 1 – 2 = 1.

Если все D_ij неотрицательны (D_ij ³ 0), то задача решена, т.е. найден оптимальный план перевозок.

Допустим, есть хотя бы одно отрицательное значение D_ij, тогда среди отрицательных D_ij выбираем наименьшее и для этой клетки i₀, j₀ делаем сдвиг по циклу пересчета на величину q₀, равную наименьшей из перевозок, стоящих в отрицательных вершинах цикла. Полученный новый опорный план будет лучше предыдущего, при этом целевая функция уменьшится на величину q₀ × .

Замечания:

1. Каждая сумма D_ij начинается с положительного числа и кончается отрицательным. Количество всех слагаемых четное.

2. Если опорный план вырожденный, то возможен сдвиг по циклу пересчета на величину q = 0. При этом значение целевой функции не изменится, а изменятся базисные клетки.

Найдем решение задачи, первоначальный опорный план которой получен методом северо-западного угла, и введем дополнительное условие: груз из пункта А₂ в пункт В₃ не может быть доставлен:

	В1	В2	В3	В4		Для всех свободных клеток вычислим Dij: D13 = 2 – 1 + 3 – 4 = 0, D14 = 5 – 1 + 2 – 1 + 3 – 4 = = 4, D21 = 6 – 5 + 4 – 1 = 4, D23 = М – 1 + 3 – 1 = = М + 1, D24 = 3 – 1 + 2 – 1 + 3 – 1 = = 5,
А1	- ^5 20	+ ^4 10	^2	^5
А2	^6	^1 70	^М	^3
А3	+ ^2 q	- ^3	^1 40	^8
А4	^6	^3	^2 30	^1 70

D₃₁ = 2 – 3 + 4 – 5 = -2, D₃₄ = 8 – 1 + 2 – 1 = 8,

D₄₁ = 6 – 5 + 4 – 3 + 1 – 2 = 1, D₄₂ = 3 – 3 + 1 – 2 = -1.

Поскольку не все D_ij ³ 0, план перевозок не оптимален. Среди D_ij < 0 выбираем наименьшее. Это D₃₁ = -2. Делаем сдвиг по циклу пересчета для свободной клетки (3,1) на величину q₀. Этот цикл проходит через базисные клетки (1,1), (1,2) и (3,2). В этом цикле две отрицательные клетки (1,1) и (3,2). Им соответствуют перевозки 20 и 10. В качестве q₀ выбираем меньшее из этих чисел, т.е. q₀ = 10. После сдвига по циклу пересчета на величину q₀ переходим к следующему опорному плану:

	В1	В2	В3	В4		Делаем второй шаг распределительного метода. Находим значения Dij для всех свободных клеток D13 = 2 – 5 + 2 – 1 = -2, D14 = 5 – 1 + 2 – 1 + 2 – 5 = = 2, D21 = 6 – 5 + 4 – 1 = 4, D23 = М – 1 + 4 – 5 + 2 - 1 = М – 1 >> 0,
А1	- ^5 10	^4 20	+ ^2 q	^5
А2	^6	^1 70	^М	^3
А3	+ ^2 10	^3	- ^1 40	^8
А4	^6	^3	^2 30	^1 70

D₂₄ = 3 – 1 + 4 – 5 + 2 – 1 + 2 – 1 = 3,

D₃₂ = 3 – 4 + 5 – 2 = 2,

D₃₄ = 8 – 1 + 2 – 1 = 8,

D₄₁ = 6 – 2 + 1 – 2 = 3,

D₄₂ = 3 – 4 + 5 – 2 + 1 – 2 = 1.

f(х) = 10 × 5 + 20 × 4 + 70 × 1 + 10 × 2 + 40 × 1 + 30 × 2 + 70 × 1 = 390.

Делаем сдвиг по циклу пересчета для свободной клетки (1,3) на величину q₀ = 10. Переходим к новому опорному плану:

	В1	В2	В3	В4		Найдем Dij для этой таблицы D11 = 5 – 2 + 1 – 2 = 2, D14 = 5 – 2 + 2 – 1 = 4, D21 = 6 – 1 + 4 – 2 + 1 – 2 = 6, D23 = М – 2 + 4 – 1 = = М + 1, D24 = 3 – 1 + 4 – 2 + 2 – 1 = 5, D32 = 3 – 4 + 2 – 1 = 0, D34 = 8 – 1 + 2 – 1 = 8,
А1	^5	- ^4 20	+ ^2 10	^5
А2	^6	^1 70	^М	^3
А3	^2 20	^3	^1 30	^8
А4	^6	+ ^3 q	- ^2 30	^1 70

D₄₁ = 6 – 2 + 1 – 2 = 3, D₄₂ = 3 – 4 + 2 – 2 = -1.

f(х) = 20 × 4 + 10 × 2 + 70 × 1 + 20 × 2 + 30 × 1 + 30 × 2 + 70 × 1 = 370.

Делаем сдвиг по циклу пересчета для свободной клетки (4,2) на величину q₀ = 20.

Переходим к новому опорному плану:

	В1	В2	В3	В4		Определим значения Dij D11 = 5 – 2 + 1 – 2 = 2, D12 = 4 – 2 + 2 – 3 = 1, D14 = 5 – 1 + 2 – 2 = 4, D21 = 6 – 1 + 3 – 2 + 1 – 2 = = 5, D23 = М – 1 + 3 – 2 = = М >> 0, D24 = 3 – 1 + 3 – 1 = 4, D32 = 3 – 3 + 2 – 1 = 1,
А1	^5	^4	^2 30	^5
А2	^6	^1 70	^М	^3
А3	^2 20	^3	^1 30	^8
А4	^6	^3 20	^2 10	^1 70

D₃₄ = 8 – 1 + 2 – 1 = 8, D₄₁ = 6 – 2 + 1 – 2 = 3.

f(х) = 30 × 2 + 70 × 1 + 20 × 2 + 30 × 1 + 20 × 3 + 10 × 2 + 70 × 1 = 350.

Для этого плана все D_ij > 0. Следовательно, этот опорный план оптимальный.

Для расчёта задач транспортного типа в среде Excel (рис. 73) необходимо ввести в таблицу тарифы на перевозку единицы груза по различным маршрутам (например, в ячейки B3:Е6), величину предложения поставщиков (например, в ячейки F3:F6) и величину спроса потребителей (например, в ячейки B7:Е7). Для размещения искомых значений переменных необходимо зарезервировать свободные ячейки (например, ячейки B9:Е12). Математические выражения для системы ограничений по спросу и предложению вводятся (например, в ячейки F9:F12 и B13:E13 соответственно) с помощью функции СУММ (рис. 74). Целевая функция вводятся (например, в ячейку F13) с помощью функции СУММПРОИЗВ из категории Математические (рис. 75). Для этого необходимо выбрать в меню Вставка строку Функция….

Рис. 73. Ввод исходных данных транспортной задачи в Excel

Рис. 74. Табличное представление транспортной задачи в Excel

Аргументами функции СУММПРОИЗВ являются: Массив1 - адреса матрицы тарифов перевозок, Массив2 – адреса пустых ячеек, зарезервированных под размещение искомых переменных задачи (плана перевозок).

Рис. 75. Ввод целевой функции транспортной задачи

Условия транспортной задачи вводятся в диалоговую форму надстройки Поиск решения, вызываемой из меню Сервис (рис. 76). В окно Установить целевую ячейку вводится адрес функции цели щелчком левой кнопки мышки по ячейке, содержащей математическое выражение для подсчёта общих затрат на перевозки. Направление поиска экстремума целевой функции устанавливается соответствующим минимальному значению. В окно Изменяя ячейки вводятся адреса искомых значений переменных (B9:Е12).

Рис. 76. Заполнение диалоговой формы Поиск решения

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

Рис. 77. Заполнение диалоговой формы Добавление ограничения

В левом окне формы Добавление ограничения (рис. 77) вводятся адреса левой части ограничений – суммы объёмов перевозок от поставщиков и суммы объёмов перевозок к потребителям. Знак ограничения устанавливается в виде знака равенства “ =“. В правом окне формы Добавление ограничения вводятся адреса правой части ограничений – числовые значения предложения и спроса.

Нажав кнопку Параметры, следует поставить «галки», выделив пункты: Линейная модель, Неотрицательные значения и Автоматическое масштабирование (рис. 78).

Рис. 78. Заполнение диалоговой формы Параметры

Оптимальный план перевозок представлен на рис. 79. Так, от первого поставщика третьему потребителю перевозится 30 единиц груза, от второго поставщика второму потребителю – 70 единиц груза. Третий поставщик обеспечивает поставки первому потребителю в объёме 20 единиц груза и третьему потребителю – 30 единиц груза. Поставки из четвёртого пункта отправления осуществляются по трём маршрутам: второму потребителю – 20 единиц груза, третьему потребителю – 10 единиц груза, третьему – 70 единиц груза. Общие затраты на перевозки составят 350 ден.ед.

Рис. 79. Результаты решения транспортной задачи

Метод потенциалов

Для решения транспортной задачи можно использовать метод потенциалов. Пусть задан опорный план задачи, тогда каждому пункту отправления А_i приписывается некоторое число U_i, а каждому пункту назначения В_j – число V_j. Эти числа называют потенциалами, они подбираются так, чтобы для каждой базисной клетки (i, j) выполнялось равенство

U_i + V_j = C_ij.

Таким образом, получаем m + n – 1 простых уравнений с m + n неизвестными U_i и V_j. В таком случае, когда система состоит из числа уравнений, меньшего, чем число неизвестных, появляется свободная неизвестная величина, которой мы можем придать любое значение. Все остальные неизвестные можно найти из системы уравнений.

После того, как будут найдены все потенциалы U_i и V_j, для каждой свободной клетки (i, j) определяют числа D_ij = C_ij– – (U_i + V_j). Далее поступаем так же, как и в распределительном методе: находим наибольшее по модулю отрицательное число (т.е. самое малое из отрицательных) и делаем сдвиг по соответствующему циклу пересчета. Таким образом, в методе потенциалов для нахождения чисел D_ij не нужно искать циклы пересчета для всех свободных клеток. Надо найти только один цикл пересчета, соответствующий наименьшему отрицательному .

Пример решения задачи методом потенциалов:

	V1 = 5	V2 = 4	V3 = 2	V4 = 1		Для занятых клеток U1 + V1 = 5, U1 + V2 = 4, U2 + V2 = 1, U3 + V2 = 3, U3 + V3 = 1, U4 + V3 = 2, U4 + V4 = 1.
U1 = 0	20 ^5	10 ^4	^2	^5
U2 = -3	^6	70 ^1	^1	^3
U3 = -1	^2 Q	10 ^3	40^1	^8
U4 = 0	^6	^3	30 ^2	70 ^1

Положим U₁ = 0, тогда учитывая занятые клетки

V₁ = 5, V₂ = 4, U₂ = –3, U₃ = –1, V₃ = 2, U₄ = 0, V₄ = 1.

Подсчитаем D_ij для свободных клеток:

D₁₃ = 2 – (0 + 2) = 0, D₁₄ = 5 – (0 + 1) = 4,

D₂₁ = 6 – (–3 + 5) = 4, D₂₃ = 1 – (–3 + 2) = 2,

D₂₄ = 3 – (–3 + 1) = 5,

D₃₁ = 2 – (–1 + 5) = –2, D₃₄ = 8 – (–1 + 1) = 8,

D₄₁ = 6 – (0 + 5) = 1, D₄₂ = 3 – (0 + 4) = –1.

Поскольку среди значений D_ij есть отрицательные, то план перевозок не оптимален и необходимо, сделав сдвиг по циклу пересчета для клетки (3,1), перейти к новому плану.

	V1 = 5	V2 = 4	V3 = 4	V4 = 3		Для занятых клеток U1 + V1 = 5, U1 + V2 = 4, U2 + V2 = 1, U3 + V1 = 2, U3 + V3 = 1, U4 + V3 = 2, U4 + V4 = 1.
U1 = 0	10 ^5	20 ^4	^Q^2	^5
U2 = -3	^6	70 ^1	^1	^3
U3 = -3	10 ^2	^3	40^1	^8
U4 = -2	^6	^3	30 ^2	70 ^1

Положим U₁ = 0, тогда

V₁ = 5, V₂ = 4, U₂ = –3, U₃ = –3, V₃ = 4, U₄ = –2, V₄ = 3.

Подсчитаем D_ij для свободных клеток:

D₁₃ = 2 – (0 + 4) = –2, D₁₄ = 5 – (0 + 3) = 2,

D₂₁ = 6 – (– 3 + 5) = 4, D₂₃ = 1 – (–3 + 4) = 0,

D₂₄ = 3 – (–3 + 3) = 3,

D₃₂ = 3 – (–3 + 4) = 2, D₃₄ = 8 – (–3 + 3) = 8,

D₄₁ = 6 – (–2 + 5) = 3, D₄₂ = 3 – (–2 + 4) = 1.

Поскольку среди значений D_ij есть отрицательное, то план перевозок не оптимален и необходимо, сделав сдвиг по циклу пересчета для клетки (1,3), перейти к новому плану.

	V1 = 3	V2 = 4	V3 = 2	V4 = 1		Для занятых клеток U1 + V2 = 4, U1 + V3 = 2, U2 + V2 = 1, U3 + V1 = 2, U3 + V3 = 1, U4 + V3 = 2, U4 + V4 = 1.
U1 = 0	^5	20 ^4	10 ^2	^5
U2 = -3	^6	70 ^1	^1	^3
U3 = -1	20 ^2	^3	30^1	^8
U4 = 0	^6	Q ^3	30 ^2	70 ^1

Положим U₁ = 0, тогда учитывая занятые клетки

V₂ = 4, V₃ = 2, U₂ = –3, U₃ = –1, V₁ = 3, U₄ = 0, V₄ = 1.

Подсчитаем D_ij для свободных клеток:

D₁₁ = 5 – (0 + 3) = 2, D₁₄ = 5 – (0 + 1) = 4,

D₂₁ = 6 – (– 3 + 3) = 6, D₂₃ = 1 – (–3 + 2) = 2,

D₂₄ = 3 – (–3 + 1) = 5,

D₃₂ = 3 – (–1 + 4) = 0, D₃₄ = 8 – (–1 + 1) = 8,

D₄₁ = 6 – (0 + 3) = 3, D₄₂ = 3 – (0 + 4) = –1.

Поскольку среди значений D_ij есть отрицательное, то план перевозок не оптимален и необходимо, сделав сдвиг по циклу пересчета для клетки (4,2), перейти к новому плану.

	V1 = 3	V2 = 4	V3 = 2	V4 = 1		Для занятых клеток U1 + V3 = 2, U2 + V2 = 1, U3 + V1 = 2, U3 + V3 = 1, U4 + V2 = 2, U4 + V3 = 2, U4 + V4 = 1.
U1 = 0	^5	^4	30 ^2	^5
U2 = -3	^6	70 ^1	^1	^3
U3 = -1	20 ^2	^3	30^1	^8
U4 = 0	^6	20 ^3	10 ^2	70 ^1

Положим U₁ = 0, тогда учитывая занятые клетки

V₃ = 2, U₃ = –1, U₄ = 0, V₁ = 3, V₂ = 4, U₂ = –3, V₄ = 1.

Подсчитаем D_ij для свободных клеток:

D₁₁ = 5 – (0 + 3) = 2, D₁₂ = 4 – (0 + 4) = 0,

D₁₄ = 5 – (0 + 1) = 4,

D₂₁ = 6 – (– 3 + 3) = 6, D₂₃ = 1 – (–3 + 2) = 2,

D₂₄ = 3 – (–3 + 1) = 5,

D₃₂ = 3 – (–1 + 4) = 0, D₃₄ = 8 – (–1 + 1) = 8,

D₄₁ = 6 – (0 + 3) = 3.

Поскольку среди значений D_ij нет отрицательных, то найден оптимальный план перевозок.

f(х) = 30 × 2 + 70 × 1 + 20 × 2 + 30 × 1 + 20 × 3 + 10 × 2 + 70 × 1 = 350.

Решение транспортной задачи методом потенциалов, реализованным в ППП PRIMA показано на рис. 80 и 81.

Рис. 80. Заполнение диалоговой формы Транспортная задача

Рис. 81. Решение транспортной задачи в ППП PRIMA

Рис. 81. Продолжение

Этапы метода потенциалов:

1. Найти первоначальный опорный план. Число заполненных клеток равно m + n – 1.

2. Найти потенциалы U_i и V_j. Составить для базисных клеток m + n – 1 уравнений с m + n неизвестными.

3. Для каждой свободной клетки найти значения D_ij = C_ij –– (U_i + V_j). Если среди значений D_ij нет отрицательных, то полученный план транспортной задачи оптимальный. Если же такие имеются, то перейти к новому опорному плану.

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

5. Полученный опорный план проверить на оптимальность. Если он не оптимален, то перейти к п. 2.

Альтернативный оптимум в транспортных задачах

Признаком наличия альтернативного оптимума в транспо­ртной задаче является равенство нулю хотя бы одной из оце­нок свободных переменных в оптимальном решении (X_опт1). Сделав перераспределение грузов относительно клетки, име­ющей ∆_ij=0, получим новое оптимальное решение (Хопт2), при этом значение целевой функции (транспортных расходов)

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

X_опт = t*X_опт1+(1 - t)*X_опт2

где 0 ≤ t ≤ 1.

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

Пример 1. На трех складах имеется мука в количестве 60, 130 и 90 т, которая должна быть в течение месяца доставлена четырем хлебозаводам в количестве: 30, 80, 60, 100 т соответственно.

Составить оптимальный план перевозок, имеющий минимальные транспортные расходы, если стоимость доставки 1 т муки на хлебозаводы задана матрицей

.

РЕШЕНИЕ. Составим распределительную таблицу в виде табл. 5.10.

Таблица 5.10

bj ai					ui
						-1
vj

По методу минимального тарифа найдем исходное решение. Определим потенциалы строк и столбцов. Найдем оценки свободных клеток:

D₁₂ = 4, D₁₃ = -12, D₂₁ = -4,

D₂₂ = - 4 D₃₃ = -4, D₃₄ = -6.

Так как D₁₂ = 4 > 0, то перераспределим грузы относительно клетки (1,2):

- + - +  

20 20

10 80 30 60

Занесем полученное перераспределение грузов в распределительную таблицу и вычислим потенциалы занятых и оценки свободных клеток (табл. 5.11).

Таблица 5.11

bj ai					ui
						-1
vj

Получим

D₁₁ = -4, D₁₃ = -12, D₂₁ = -8,

D₂₂ = -8, D₃₃ = 0, D₃₄ = -2.

Так как D₃₃ = 0, то задача имеет альтернативный оптимум и одно из решений равно

Х_опт1 .

Стоимость транспортных расходов составляет: L(Х_опт1) = 1550 усл. ед.

Произведем перераспределение грузов относительно клетки (3,3):

20 ₊ - 40 60

- + 70 20 110

60 - + 60 20 40

Занесем в распределительную таблицу полученное перераспределение грузов, вычислим потенциалы занятых и оценки свободных клеток (табл. 5.12):

Таблица 5.12

bj ai					ui
						-1
vj

D₁₁ = -4, D₁₃ = -12, D₁₄ = 0,

D₂₁ =-8, D₂₂ = -8, D₃₃ = -2.

Так как D₁₄ = 0, получили еще одно решение:

Х_опт2

Стоимость транспортных расходов составит L(Х_опт2) = 1550 усл. ед.

Данная задача имеет два оптимальных решения Х_опт1 и Х_опт2, общее решение находится по формуле

X_опт = tX_опт1+(1 - t)X_опт2

где 0 ≤ t ≤ 1.

Найдем элементы матрицы общего решения:

x₁₁= 0, x₁₃ = 0, x₂₁ = 0,

x₂₃ = 60t + (1 – t)20 = 20 + 40t,

x₃₁ = 30t + (1 – t)30 = 30,

x₃₃ = 0t + (1 – t)40 = 40 – 40t,

x₁₂ = 20t + (1 – t)60 = 60 – 40t,

x₁₄ = 40t + (1 – t)0 = 40t,

x₂₂ = 0, x₂₄ = 70t + (1– t)110 = 110 – 40t,

x₃₂ = 60t + (1 – t)20 = 20 + 40t, x₃₄ = 0.

Итак,

Х_опт

Стоимость транспортных расходов составляет 1550 усл. ед.

Приложение транспортных моделей к

Дата добавления: 2014-12-27