Постановка и решение транспортной параметрической задачи

 

Рис. 3.1. Фрагмент окна программы Ms Excel: Модель таблицы «Стоимость перевозок».

 

2. В таблице «Стоимость перевозок» в ячейках запасов поставщиков и потребностей потребителей записать количество запасов поставщиков и потребностей потребителей соответственно, указанное в условии задачи.

3. Таблицу "План  перевозок" создать с пустыми  полями (заполненными единицами), заранее заданного числового формата. В ячейках запасов (потребностей) каждого поставщика (потребителя) ввести формулу, выполняющую суммирование всех возможных поставок этого поставщика (потребителя).

Рис. 3.2. Фрагмент окна программы Ms Excel: Модель таблицы «План перевозок».

 

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

5. В диалоговом окне функции "Поиск решения" установить необходимые ограничения, в целевой ячейке указать адрес ячейки с формулой целевой функции и установить ее равной минимальному значению, в качестве изменяемых ячеек выбрать диапазон всех элементов матрицы "План перевозок". Ограничения в "Поиске решений" заключаются в необходимости равенства запасов (потребностей), в матрице "План перевозок" соответствующим запасам и потребностям, указанным в матрице "Стоимость перевозок". Также все элементы матрицы "План перевозок" должны быть неотрицательными и целочисленными.

6. В диалоговом окне "Параметры поиска решения" установить параметр "Линейная модель" и число итераций, равное 100.

7. Выполнить функцию "Поиск решения" нажатием на кнопку "Выполнить". В качестве отчета по результатам выбрать необходимый пункт в списке "Тип отчета" диалогового окна «Результаты поиска решения».

После выполнения вышеуказанных  действий при условии, что задача имеет решение, в матрице «План  перевозок» запишется оптимальное  решение задачи, т.е. оптимальный  план перевозок с указанием объемов  поставок в каждой ячейке. В ячейке с целевой функцией запишутся совокупные затраты поставок.

 

 

 

 

 

 

 

 

 

 

4. Решение параметрической  транспортной задачи

 

4.1 Постановка параметрической транспортной задачи

 

Имеется четыре поставщика однородного груза с объемами поставок 100, 70, 70, 20 т. и три потребителя с объемами потребления 120, 80, 60 т. Стоимость транспортных расходов задана матрицей

причем стоимость перевозки  груза от четвертого поставщика до третьего потребителя изменяется в  диапазоне 0≤k≤9.

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

Изобразим матричную  запись задачи (табл. 4.1.1)

 

Табл. 4.1.1. Матричная запись задачи

Bj   Ai		B1	B2	B3
		120	80	60
A1	100	2	4	2
		X11	X12	X13
A2	70	5	5	6
		X21	X22	X23
A3	70	4	7	3
		X31	X32	X33
A4	20	6	8	1+k
		X41	X42	X43

 

 

4.2. Математическая  модель задачи

 

Целевая функция

.

где X_ij – объем поставок груза,

при ограничениях:

X_ij≥0,

 

Подробные ограничения  по потребностям и запасам каждого потребителя и поставщика соответственно отражены  в Таблице 4.2.1.

 

Табл. 4.2.1. Ограничения  по потребностям и запасам

По потребностям		По запасам
B1	X11+X21+X31+X41=120	A1	X11+X12+X13=100
B2	X12+X22+X32+X42=80	A2	X21+X22+X23=70
B3	X13+X23+X33+X43=60	A3	X31+X32+X33=70
		A4	X41+X42+X43=70

 

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

 

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

заполненные			незаполненные
№	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	A4B1	v1+u4<=6	соблюдается
A4B3	v3+u4=1+k	u4=2+k	A4B2	v2+u4<=8	соблюдается

 

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

заполненные			незаполненные
№	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. Решение  задачи средствами Ms Excel

 

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

 

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

 

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

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

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

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