Транспортная параметрическая задача

Задача формулируется следующим образом: для всех значений параметра , где - произвольные действительные числа, найти такие значения , которые обращают в минимум функцию

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

Пользуясь методом потенциалов, решаем задачу при до получения оптимального решения. Признаком оптимальности является условие:

для незанятых клеток

и для занятых клеток,

где - потенциалы строк, столбцов распределительной таблицы.

Условие совместимости транспортной задачи записывается в виде

Значения и определяются из условия

где определяются из систем уравнений

Значения находятся в пределах :

Алгоритм решения.

1. Задачу решаем при конкретном значении параметра до получения оптимального решения.

2. Определяем и

3. Вычисляем значения параметра .

4. Если , производим перераспределение поставок и получаем новое оптимальное решение. Если , то процесс решения окончен.

Нахождение оптимальных путей транспортировки грузов при нестабильной загрузке дорог

Имеются три поставщика однородного товара с объёмами поставок: а₁ = 100 т, а₂ = 200 т, а₃ = 100 т и четыре потребителя с объёмами потребления b₁ = 80 т, b₂ = 120 т, b₃ = 150 т, b₄ = 50 т. Стоимость транспортных расходов изменяется в определённом диапазоне в зависимости от загрузки дороги и задана матрицей

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

РЕШЕНИЕ. В матрицу расходов введём параметр , где . Получим

.

Полагая , решаем задачу методом потенциалов, определим оптимальное решение перевозок. Распределительная таблица этого решения будет иметь вид:

bj ai	80	120	150	50	ui
100	30	4- 70	8		0
200	4 50	7	150
100	5	3 50	6	50
vj

В таблице u_i и v_j – потенциалы строк и столбцов. Для занятых клеток они определяются из условия

Полагая u₁ = 0, , получаем

, откуда

или откуда

или

Аналогично находим, что

Оценки свободных клеток находим по формуле

Имеем

Аналогично находим, что

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

или

Имеем

Так как по условию задачи , то оптимальное решение сохраняется при При этом минимальная стоимость транспортных расходов составляет

Таким образом, при и

.

Чтобы получить оптимальное решение при , перераспределим поставки товаров в клетку (3, 1), где . Вновь полученное распределение представлено в табл.:

bj ai	80	120	150	50	ui
100		4- 100	8		0
200	4 50	7	150
100	5 30	3 20	6	50
vj

Находим оценки свободных клеток:

.

Определим пределы изменения :

Полученное в таблице оптимальное решение сохраняется при При этом

.

Итак,

.

Перераспределим поставки грузов в клетку (3, 3), где . Получим новое распределение:

bj ai	80	120	150	50	ui
100		4- 100	8		0
200	4 80	7	120
100	5	3 20	6 30	50
vj

Находим оценки свободных клеток:

.

Определим пределы изменения :

Оптимальное решение сохраняется при При этом

.

Итак,

.

Перераспределим поставки грузов в клетку (1, 4), где .

bj ai	80	120	150	50	ui
100		4- 50	8	50	0
200	4 80	7	120
100	5	3 70	6 30
vj

Оценки свободных клеток:

.

Пределы изменения :

Полученное в предыдущей таблице оптимальное решение сохраняется при При этом

.

Итак,

.

Перераспределим поставки грузов в клетку (2, 4), где .

bj ai	80	120	150	50	ui
100		4- 100	8		0
200	4 80	7	70	50
100	5	3 20	6 80
vj

Оценки свободных клеток:

.

Пределы изменения :

Оптимальное решение сохраняется при При этом

.

Итак,

.