2. Транспортная задача

Для решения задачи 3.2 необходимо изучить следующую литературу:

[1] Раздел D. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ, глава 6, стр. 597…637.

[3] Раздел 1. МОДЕЛИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ЕГО ПРИЛОЖЕНИЯ, глава 7, стр. 123…152.

[4] Глава 3. Транспортная задача, стр. 43…55.

Учебно-методическая литература

[4] Главы 1, 2, стр. 5…37.

Задача3.2. Найти оптимальный план перевозок товара с двух баз: A₁ и A₂ в три магазина: B₁, B₂, B₃. Запасы на базах, потребности магазинов, а также тарифы на перевозку товаров между базами и магазинами даны в таблице (справа та же таблица, но без заголовков).

П лан перевозок запишем в виде матрицы: .

Требуется найти план с минимальной общей стоимостью перевозок товара:

Z = 3x₁₁ + 2x₁₂ + x₁₃ +5x₂₁ + 3x₂₂ + 6x₂₃ (min).

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

Введём обозначения:

c_ij - тариф на перевозку единицы товара с базы A_i в магазин B_j;

m - число баз (строк таблицы);

n - число магазинов (столбцов);

p - число занятых клеток в таблице.

З аполняем клетки методом наименьшего тарифа:

min c_ij = c₁₃ = 1;  x₁₃ = min{50; 40} = 40;

записываем 40 в клетку (1; 3); третий столбец вычёркиваем, т.к. потребности B₃ удовлетворены; запасы на складе A₁ уменьшились до 10(ед.).

Далее ищем наименьший тариф среди не вычеркнутых клеток: min c_ij = c₁₂ = c_{21 =} 2. Заполним клетку (1, 2): x₁₂ = min{10; 20} = 10. Первую строку вычёркиваем, т.к. запасы на складе A₁ исчерпаны; потребности B₂ уменьшились до 10(ед.).

3	2 10	1 40	u1
5 30	3 10	6	u2
v1	v2	v3

Остались не вычеркнутыми клетки только одного ряда – второй строки, которые заполняются однозначно в любом порядке: x₂₁ = 30; x₂₂ = 10.

Первый план: X₁ = .

Стоимость перевозок по этому плану:

Z₁ = 210 + 1 40 + 530 + 310 = 240.

Проверим условие опорности плана: p = r, где r = m + n –1 - ранг системы уравнений. Заполненных клеток – четыре, т.е. р = 4; ранг:

r = 3 + 2 –1 = 4.

p = r = 4;  план опорный!

Проверка оптимальности плана методом потенциалов.

Пусть u_i - потенциалы строк, v_j - потенциалы столбцов (смотри последнюю таблицу). Для всех занятых клеток должно выполняться условие:

u_i + v_j = c_ij (1)

Для всех свободных клеток должно выполняться условие:

y_ij = c_ij - (u_i + v_j)  0. (2)

Здесь yij - оценки клеток (двойственные переменные).

По формуле (1) составим систему уравнений для нахождения потенциалов:

; Пусть u₁ = 0;  (v₂ = 2; v₃ = 1;)  (u₂ = 3 - v_{2 = 1};) 

(v₁ = 5 - u_{2 = 4};)

П

3	2 10	1 40	u1 = 0
5 30	3 10	6	u2 = 1
v1= 4	v2 = 2	v3 = 1

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

По формуле (2) оценим свободные клетки:

y₁₁ = c₁₁ - (u₁ + v₁) = 3 – (0 + 4) = -1 < 0;

y₂₃ = c₂₃ - (u₂ + v₃) = 6 – (1 + 1) = 4 > 0;

Полученный план не оптимален, т.к. оценка y₁₁ отрицательна. Эту пустую клетку (1, 1) следует заполнить, не нарушая баланса по рядам и сохраняя количество заполненных клеток. Такой переход к другому опорному плану возможен только по циклу (цикл существует и единственный!): + (1, 1) – (2, 1) + (2, 2) – (1, 2).

О тразим цикл в таблице (попутно вместо тарифов запишем оценки). Клетки: (1, 1) и (2, 2) помечены знаком + (прибавляется: +). Клетки: (2, 1) и (1, 2) помечены знаком – (отнимается: -), одна из них – с наименьшей поставкой – становится пустой:

 = min(x₂₁, x₁₂) = min(30, 10) = 10.

Подставив  в предыдущую таблицу, получим новую:

У

-1 10	0	0 40	-1
0 20	0 20	4
		+1

вновь заполненной клетки оценка должна быть нулевой, для этого припишем потенциал строки u₁ = -1;  v₃ = +1. Проверьте: для всех заполненных клеток сумма потенциалов равна прежним оценкам! После вычитания потенциалов получим новый опорный план с новыми оценками:

Э

0 10	1	0 40
0 20	0 20	3

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

y_11 = (-1)10 = -10;  Z₂ = Z₁ -10 = 240 -10 = 230.

Ответ.

Стоимость перевозок согласно плану X = будет наименьшей и составит 230(д.е.). При этом потребности магазинов будут полностью удовлетворены и товарные запасы с баз полностью вывезены.