Решение задачи аналитическим методом

Полагая k=0, по известному алгоритму составим опорное решение методом Фогеля. Полученный опорный план перевозок и алгоритм выполнения с нахождением минимальных разностей стоимостей перевозок (C_ij) в каждом столбце и строке изображен на рисунке 4.3.1.

Рис. 4.3.1. Составление первого опорного решения задачи по методу Фогеля

Процесс выполнения получения опорного решения с последовательным назначением перевозок в ячейки: А₄В₃ - А₃В₃ - А₃В₁ - А₁В₁ - А₁В₂ - A₂B₂.

Проверка плана на вырожденность: m+n-1=6. План невырожденный.

Проверим опорное решение на оптимальность по методу потенциалов. Расчет потенциалов строк и столбцов для занятых из условия v_i + u_j = c_ijдля занятых клеток и проверка условия v_i + u_j ≤ c_ij для незанятых приведены в таблице 4.3.1.

Решение, полученное при k=0, является оптимальным для всех значений параметра k, удовлетворяющих условию .

Из условия для свободных клеток найдем:

∆₁₃ = v₃ + u₁ - c'₁₃ = -1 + 2 - 2 = -1

∆₂₁ = v₁ + u₂ - c'₂₁ = 0 + 3 - 5 = -2

∆₂₃ = v₃ + u₂ - c'₂₃ = -1 + 3 - 6 = -4

∆₃₂ = v₂ + u₃ - c'₃₂ = 2 + 4 - 7 = -1   

∆₄₁ = v₁ + u₄ - c'₄₁ = 0 + 2+k - 6 = -4 + k

∆₄₂ = v₂ + u₄ - c'₄₂ = 2 + 2+k - 8 = -4 + k

Табл. 4.3.1. Проверка первого опорного решения на оптимальность методом потенциалов

Определение значений k₁ и k₂:

k₁ = max(-a_ij/B_ij) =   т.к. все B_ij ≥ 0

k₂ = min(-a_ij/B_ij) = (-a₄₁/B₄₁; -a₄₂/B₄₂) = min(4;4) = 4. Все B_ij > 0.

Так как по условию задачи k≥0, то оптимальное решение сохраняется при 0≥k≥4.

При этом минимальная стоимость транспортных расходов составляет:

F(X₁)_min = 20*(1+k) + 40*3 + 30*4 + 90*2 + 10*4 + 70*5 = 830 + 20k

Таким образом, при , F(X₁)_min = 830 + 20k и

.

Чтобы получить оптимальное решение при k≥4 перераспределим поставки товаров в клетку (4,1), где k₂=4. Вновь полученное распределение с учетом изменения стоимости перевозки в ячейке A₄B₃ (k=4) представлено на рисунке 4.3.2.

Рис. 4.3.2. Составление второго опорного решения задачи по методу Фогеля

Процесс выполнения получения опорного решения с последовательным назначением перевозок в ячейки: А₄В₁ - А₃В₃ - А₃В₁ - А₁В₁ - А₁В₂ - A₂B₂.

Проверка плана на вырожденность: m+n-1=6. План невырожденный.

Проверим опорное решение на оптимальность по методу потенциалов. Расчет потенциалов строк и столбцов для занятых из условия v_i + u_j = c_ijдля занятых клеток и проверка условия v_i + u_j ≤ c_ij для незанятых приведены в таблице 4.3.2.

Табл. 4.3.2 Проверка второго опорного решения на оптимальность методом потенциалов

Решение, полученное при k=4, является оптимальным для всех значений параметра k, удовлетворяющих условию .

Из условия для свободных клеток найдем:

∆₁₃ = a₃ + b₁ - C'₁₃ = -1 + 2 - 2 = -1

∆₂₁ = a₁ + b₂ - C'₂₁ = 0 + 3 - 5 = -2 

∆₂₃ = a₃ + b₂ - C'₂₃ = -1 + 3 - 6 = -4

∆₃₂ = a₂ + b₃ - C'₃₂ = 2 + 4 - 7 = -1 

∆₄₂ = a₂ + b₄ - C'₄₂ = 2 + 6 - 8 = 0

∆₄₃ = a₃ + b₄ - (C'₄₃ + С''₄₃) = -1 + 6 - (1+k) = 4-k

Определение значений k₁ и k₂

k₁ = max(-a_ij/B_ij) = -a₄₃/B₄₃ = 4. Все B_ij < 0

k₂ = min(-a_ij/B_ij) =  т.к. все B_ij ≤ 0

Так как по условию задачи k ≤ 9, то оптимальное решение сохраняется при 4≥k≥9.

При этом минимальная стоимость транспортных расходов составит:

F(X₂)_min = 20*6 + 60*3 + 10*4 + 90*2 + 10*4 + 70*5 = 910

Таким образом, при  F(X₂)_min = 910 и

.