Постановка и решение транспортной параметрической задачи (стр. 3 из 4)

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 Проверка второго опорного решения на оптимальность методом потенциалов

заполненные			незаполненные
№	vi + uj = cij	значения	№	vi + uj ≤ cij	условие
А1В1	v1+u1=2	v1=0, u1=2	А1В3	v3+u1<=2	соблюдается
А1В2	v2+u1=4	v2=2	А2В1	v1+u2<=5	соблюдается
A2B2	v2+u2=5	u2=3	А2В3	v3+u2<=6	соблюдается
A3B1	v1+u3=4	u3=4	А3В2	v2+u3<=7	соблюдается
A3B3	v3+u3=3	v3= -1	A4B2	v2+u4<=8	соблюдается
A4B1	v1+u4=6	u4=6	A4B3	v3+u4<=1+k	соблюдается

Решение, полученное при 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 и

.

4.4 Решение задачи средствами MsExcel

Создадим в окне программы MsExcel две матрицы «План перевозок» и «Стоимость перевозок», согласно вышеизложенным правилам (рис 4.4.1). Также нужно указать ячейку содержащую изменяемый параметр k. При этом в клетке A₄B₃ матрицы «Стоимость перевозок» устанавливаем формулу, отображающую зависимость данного тарифа от параметра k: L7=1+L9.

Рис. 4.4.1. Фрагмент окна программы MsExcel: Матрицы «План перевозок» и «Стоимость перевозок» с изменяемым тарифом C₄₃.

В ячейки, которые должны отображать запасы поставщиков и потребности потребителей в матрице «План перевозок» вводим формулы суммирующие значения всех возможных поставок данных поставщиков и потребителей, например: B4=СУММ(C4:E4), C3=СУММ(С4:С7).

В ячейку целевой функции (N7) введем =СУММПРОИЗВ(C4:E7;J4:L7).

Метод решения параметрической транспортной задачи средствами Ms Excel заключается в нахождении оптимального решения при каждом значении параметра k, с сохранением сценария для каждой процедуры «Поиск решения». После этого необходимо из всего диапазона изменения параметра k выделить отдельные промежутки, на которых сохраняется оптимальное решение задачи и минимальная стоимость затрат.

В диалоговом окне «Поиск решения», согласно вышеуказанным правилам установим все необходимые ограничения и ссылки на необходимые ячейки (рис. 4.4.2). Также необходимо в ограничениях указать пределы изменения параметра k, т.е. 0≤k≤9.

Рис. 4.4.2. Диалоговое окно «Поиск решения»

В диалоговом окне «Параметры поиска решения» установить необходимые параметры (рис. 4.4.3).

Рис. 4.4.3. Диалоговое окно «Параметры поиска решения»

После нажатия на кнопку «Выполнить» в диалоговом окне «Результаты поиска решения» (рис. 4.4.5) нажать «Сохранить сценарий…» и в появившемся диалоговом окне «Сохранение сценария» задать имя данному сценарию и нажать «ОК» (рис. 4.4.4.).

Рис. 4.4.4. Диалоговое окно «Сохранение сценария»

После сохранения сценария в диалоговом окне «Результаты поиска решения» выделить необходимые типы отчетов и нажать «OK» (рис. 4.4.5.).

Рис. 4.4.5. Диалоговое окно «Результаты поиска решений

После выполнения всех операций в матрице «План перевозок» получим оптимальный план перевозок при k=0 (рис. 4.4.6.).

Рис. 4.4.6. Фрагмент окна программы MsExcel: Результат поиска решения при k=0.

Полученное значение целевой функции F(x₁)_min=830.

Теперь аналогичным способом найдем оптимальный план перевозок при k=1. Проведя повторный расчет, получим новый план перевозок и значение целевой функции (рис 4.4.7.).

Рис. 4.4.7. Фрагмент окна программы MsExcel: Результат поиска решения при k=1

Полученное значение целевой функции F(x₂)_min = 850.

Как видно из рисунков 4.4.5. и 4.4.6 планы перевозок в обоих случаях (k=0, k=1) одинаковы. После дальнейших расчетов при всех остальных значениях параметра kобнаружим, что при

план перевозок остается неизменным, изменяется лишь значение целевой функции. При значении параметра «Поиск решения» выдает другой план перевозок, и значение целевой функции на данном промежутке остается неизменным F(x)_min = 910. Полученный план перевозок при значении k=4 изображен на рисунке 4.4.8.

Рис. 4.4.8. Фрагмент окна программы MsExcel: Результат поиска решения при k=4

Значения целевой функции, соответствующие параметру k в каждой итерации представлены в таблице 4.4.1.

Из представленных в таблице 4.4.1 данных можно вывести определенную закономерность изменения значения целевой функции на промежутке

:

F(x₁)_min = 830, (k=0);

F(x₂)_min = F(x₁)_min +20 = 830+20, (k=1);

F(x₃)_min = F(x₂)_min +20 = 830 + 20*2 = 870, (k=2).

Следуя по той же цепочке, найдем:

F(x₄)_min = 830 + 20*3, (k=3).

F(x₅)_min = 830 + 20*4, (k=4).

Исходя из подобной логики можно представить F(x₁)_min = 830 + 20*0.

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

:

.

Для значений

значение функции постоянно F(x)=910.

Таблица 4.4.1. Значения целевой функции в каждой итерации

номер итерации i	значение параметра ki	значение функции F(xi)min
1	0	830
2	1	850
3	2	870
4	3	890
5	4	910
6	5	910
7	6	910
8	7	910
9	8	910
10	9	910

Команда «Сервис → Сценарии» открывает диалоговое окно «Диспетчер сценариев», которое отображает сохраненные сценарии каждой итерации нахождения оптимального плана перевозок (рис 4.4.9.).