Задача. На двух складах А и В имеются соответственно 50 и 40 т груза

На двух складах А и В имеются соответственно 50 и 40 т груза. Требуется спланировать перевозки к трем потребителям С, Д и Е так, чтобы потребитель С получил 30 т, Д – 20 т, Е – 40 т, а затраты на перевозку были минимальными. Стоимость перевозок от складов к потребителям заданы в табл.1.

Таблица 1

Стоимость перевозок

потребители склады	С	Д	Е
А	x11	x12	x13
В	x21	x22	x23

1. Составим математическую модель задачи

На множестве решений системы:

При этом количество пунктов отправления m = 2, а количество пунктов назначения n =3.

Найти минимальное значение целевой функции F = 3 x₁₁ + 2 x₁₂ + x₁₃ +

3 x₂₁ + 5 x₂₂ + 6 x₂₃ .

2. Составим первое распределение поставок методом “северо-западного угла”, начиная заполнение транспортной таблицы с левого верхнего (“северо-западного”) угла.

Потребитель С подал заявку на 30 т груза, выполним эту заявку из запасов склада А. При этом, заказ потребителя С полностью выполнен и его можно исключить из дальнейшего рассмотрения.

Найдем новый северо-западный угол – это клетка АД. Из условий задачи известно, что потребитель Д заказал 20 т груза. На складе А осталось: 50 – 30 = 20 т груза. Направим этот груз потребителю Д. В этом случае, весь груз со склада А перевезен, и первую строчку можно исключить из дальнейшего рассмотрения. Заказ потребителя Д также полностью выполнен и столбик Д транспортной таблицы можно исключить из дальнейшего рассмотрения.

В оставшейся части таблицы найдем новый северо-западный угол – это клетка ВЕ. Заказ потребителя Е – 40 т груза полностью удовлетворим со склада В. Тогда исходным распределением поставок будет: x₁₁ = 30; x₁₂ = 20; x₂₃ = 40 и транспортная таблица примет следующий вид (табл.2).

Таблица 2

потребители склады	С	Д	Е
А
В

По таблице определим значение целевой функции F₁ = 30·3 +20·2 + 40·5 = 370 руб.

Данный план является допустимым, т.к. сумма перевозок по строке равна запасу соответствующего пункта отправления (склада), а сумма перевозок по столбцу – заявке соответствующего пункта назначения (потребителя).

Проверим, является ли план перевозок опорным. Определим величину

m + n – 1 = 2 + 3 – 1 = 4, и сравним ее со значение с количеством базисных перевозок, отличных от нуля (p = 3). Условие m + n – 1 ≥ p выполняется, т.е. план перевозок является опорным.

3. Проверим, является ли полученный план оптимальным. Сформулируем математическую модель задачи, двойственной исходной. Для этого введем пять переменных: u₁, u₂ (по числу складов) и v₁, v₂, v₃ (по числу потребителей). Результаты внесем в таблицу 3.

Таблица 3

1 план
	x11	x12	x13	x21	x22	x23
u1
u2
v1
v2
v3

Теперь двойственную задачу можно сформулировать так: требуется найти максимальное значение целевой функции F = 50u₁ + 40u₂ + 30v₁ + 20v₂ + 40v₃, на множестве решений системы:

u₁ + v₁ ≤ 3

u₁ + v₂ ≤ 2

u₁ + v₃ ≤ 1

u₂ + v₁ ≤ 3

u₂ + v₂ ≤ 5

u₂ + v₃ ≤ 6.

Заметим, что если все ограничения исходной задачи имели вид равенств, то переменные двойственной задачи (u₁, u₂, v₁, v₂, v₃) могут принимать и отрицательные значения.

Проверка оптимальности полученного плана перевозок состоит в следующем:

если некоторые переменные исходной задачи строго больше нуля (x_ij>0), то соответствующие им условия двойственной задачи выполняются как строгие равенства. При этом получаем систему из (m + n -1) уравнений с (m + n) переменными: u₁, u₂,…, u_m; v₁, v₂,…, v_n;

если найти одно из решений полученной системы и подставить его в оставшиеся неравенства системы ограничений двойственной задачи, не вошедшие в систему (m + n – 1) уравнений, и эти неравенства выполняются, то проверяемый план является оптимальным;

если часть неравенств системы ограничений двойственной задачи не выполняются, то возможно дальнейшее улучшение плана.

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

u₁ + v₁ = 3

u₁ + v₂ = 2

u₂ + v₃ = 6.

Положим u₁ равным нулю и решим данную систему. Из первого уравнения находим v₁ = 3, из второго - v₂ = 2. Третье уравнение не имеет однозначного решения, так как в рассматриваемой системе три уравнения, но четыре переменных. Поэтому введем так называемую “условную подстановку”, для чего будем считать клетку x₁₃ (или x₂₂) занятой, поместив в нее число “0”.

Получим следующую систему уравнений:

u₁ + v₁ = 3 Решением данной системы будет следующее:

u₁ + v₂ = 2 u₁ = 0; u₂ = 5; v₁ = 3; v₂ = 2; v₃ = 1.

u₁ + v₃ = 1

u₂ + v₃ = 6.

Подставим полученные значения в оставшиеся неравенства системы ограничений двойственной задачи:

u₂ + v₁ ≤ 3 5 + 3 ≤ 3 8 ≤ 3

u₂ + v₂ ≤ 5 5 + 2 ≤ 5 7 ≤ 5

Условия не выполняются, т.е. первоначальный план можно улучшить.

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

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

При этом нечетные вершины цикла (1, 3, 5 и т.д.) отмечаются знаком “+” – это значит, что перевозки в этих клетках увеличиваются. А четные вершины (2, 4, 6 и т.д.) отмечаются знаком “-“, так как перевозки в них уменьшаются.

Так как свободных клеток в таблице несколько, то и возможных циклов также будет несколько. Приступая к оптимизации и выбирая цикл (контур) перераспределения поставок, необходимо определить “цену цикла”, подсчитав сумму стоимостей перевозок, стоящих в вершинах цикла, учитывая знак (+ или -), которым данная вершина отмечена.

Для нашего примера существует две свободные клетки (ВС и ВД) в транспортной таблице и, соответственно два возможных цикла (табл.4).

Таблица 4

потребители склады	С	Д	Е
А	--	--	+ +
В	+	5 +	-- --

Первый цикл: ВД АД АЕ ВЕ ВД, его цена: 5 – 2 + 1 – 6 = -2.

Второй цикл: ВС АС АЕ ВЕ ВС, его цена: 3 – 3 + 1 – 6 = -5.

Поэтому выбираем второй цикл и проводим перераспределение поставок. Результат показан в таблице 5.

Таблица 5

потребители склады	С v1	Д v2	Е v3
А u1
В u2

Из таблицы видно, что решением является: x₁₂ = 20; x₁₃ = 30; x₂₁ = 30;

x₂₃ = 10. F₂ = 20·2 +30·1 + 10·6 +30·3 = 220 рублей.

Можно рассчитать и иначе: F₂ = F₁ – (цена цикла х величина перемещаемых перевозок) = 370 - 5·30 = 220 рублей.

5. Проверим оптимальность полученного плана. Для этого решим систему уравнений:

u₁ + v₂ = 2 Решением данной системы будет следующее:

u₁ + v₃ = 1 u₁ = 0; u₂ = 5; v₁ = -2; v₂ = 2; v₃ = 1.

u₂ + v₁ = 3

u₂ + v₃ = 6.

Проверим выполнение неравенств:

u₁ + v₁ ≤ 3 0 + (-2) ≤ 3 -2 ≤ 3

u₂ + v₂ ≤ 5 5 + 2 ≤ 5 7 ≤ 5

Условия не выполняются, т.е. план можно улучшить.

6. Проведем вторую циклическую перестановку в транспортной таблице.

Возможны два цикла (табл.6).

Первый цикл: ВД АД АЕ ВЕ ВД, его цена: 5 – 2 + 1 – 6 = -2.

Второй цикл: АС АЕ ВЕ ВС АС, его цена: 3 – 1 + 6 – 3 = 5, т.е. он увеличит общую цену перевозки.

Таблица 6

потребители склады	С	Д	Е
А	+	--	-- +
В	--	5 +	-- +

Поэтому выбираем первый цикл и проводим перераспределение поставок. Результат перераспределения приведен в таблице 7.

Таблица 7

потребители склады	С v1	Д v2	Е v3
А u1
В u2

Из таблицы видно, что решением является: x₁₂ = 10; x₁₃ = 40; x₂₁ = 30;

x₂₂ = 10. F₃ = 10·2 +40·1 + 30·3 +10·5 = 200 рублей.

7. Проверим оптимальность плана. Для этого решим систему уравнений:

u₁ + v₂ = 2 Решением данной системы будет следующее:

u₁ + v₃ = 1 u₁ = 0; u₂ = 3; v₁ = 0; v₂ = 2; v₃ = 1.

u₂ + v₁ = 3

u₂ + v₂ = 5.

Проверим выполнение неравенств:

u₁ + v₁ ≤ 3 0 + 0 ≤ 3 0 ≤ 3

u₂ + v₃ ≤ 6 3 + 1 ≤ 6 4 ≤ 6.

Условия выполняются, т.е. план является оптимальным.

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