.
Этот план лучше, но утверждать, что он оптимален, нельзя.
Определение 1. Набором называется произвольная совокупность перевозок транспортной таблицы.
Определение 2. Цепью называют такие наборы, когда каждая пара соседних клеток в цепи расположены либо в одном столбце, либо в одной строке.
Определение 3. Циклом называется цепь, крайние элементы которой находятся либо в одной строке, либо в одном столбце.
Как показывает практика, белее удобным методом является метод потенциалов, он позволяет находить оптимальный план перевозок транспортной таблицы. Алгоритм метода потенциалов состоит из предварительного этапа и повторяющегося основного этапа.
Предварительный этап включает следующие шаги:
1. Каким-либо способом ищется допустимый план 
(методом северо-западного угла или минимального элемента).
2. Для полученного плана строится система m+n чисел 
, 
, таких, что 
, 
.
3. Построенная система 
и 
исследуется на потенциальность, т. е. план 
исследуется на оптимальность. Для этого проверяется 
, 
. Если система не потенциальна, то переходят к основному этапу (т. к. план не оптимален), иначе оптимальный план найден.
Основной этап в методе потенциалов:
1. Улучшаем план, то есть от плана переходим к плану 
такому, что 
.
2. Для плана строим новую систему 
, 
, 
, такую, что 
, .
3. Исследуем систему 
на потенциальность. Если система не потенциальна, то переходим на п.1, иначе найден оптимальный план.
Найдем методом потенциалов оптимальное решение задачи, взяв в качестве опорного план, построенный методом северо-западного угла (1-й шаг предварительного этапа).
|
|
|
|
|
|
| |
|
| ||||||
|
|
2 30 |
4 80 |
2 10 |
3 |
8 | |
|
|
3 |
5 |
6 10 |
– 6 20 |
+ 2 | |
|
|
6 |
8 |
7 |
+ 4 10 |
– 5 30 | |
|
|
3 |
4 |
2 |
1 |
4 60 |
2. Строим систему потенциалов:
, 
, 
,
, 
, 
,
, 
.
Число неизвестных больше числа уравнений, поэтому можем взять, например, 
и найти значения остальных потенциалов, 
, 
, 
, 
, 
, 
, 
, 
.
3. Проверяем систему на потенциальность:
, 
, 
,
, 
, 
,
, 
, 
,
, 
, 
,
Система не потенциальна, переходим к общему этапу.
1. Выбираем клетку, для которой неравенство вида 
нарушается в наибольшей степени, то есть, находится число 
среди тех клеток, для которых условие не выполняется: 
.
Начиная с клетки 
, в направлении против часовой стрелки строится цепь из заполненных клеток таблицы (цикл). Совершая обход по цепи, помечаем клетки, начиная с , попеременно знаками «+» и «-». Клетки со знаками «+» образуют положительную полуцепь, а со знаками «-» отрицательную полуцепь. В клетках отрицательной полуцепи ищем минимальную перевозку
.
Теперь улучшаем план следующим образом: перевозки отрицательной полуцепи уменьшаем на величину 
, а перевозки положительной полуцепи увеличиваем на . Новые
В нашем примере =20.
1. Новому плану соответствует таблица.
|
|
|
|
|
|
| |
|
| ||||||
|
|
2 30 |
4 80 |
2 10 |
3 |
8 | |
|
|
3 |
5 |
– 6
|
6 0 |
+ 2 20 | |
|
|
6 |
8 |
7 |
4 30 |
5 10 | |
|
|
3 |
4 |
+ 2 |
1 |
– 4 60 |
10
Затраты на перевозку по построенному плану равны:
.
2. Строим систему потенциалов
, 
, 
,
, 
, 
,
, .
Полагаем 
и находим значения остальных потенциалов: 
, 
, 
, , , , 
, 
.
3. Проверяем систему на потенциальность:
, 
, 
,
, 
, 
,
, 
, 
,
, 
, 
,
Система непотенциальна.
1. Находим 
, строим цикл, =10. Улучшаем план. Новому плану соответствует таблица.
|
|
|
|
|
|
| |
|
| ||||||
|
|
2 30 |
4 80 |
2 10 |
3 |
8 | |
|
|
3 |
5 |
6 0 |
6 0 |
2 30 | |
|
|
6 |
8 |
7 |
30 |
+ 5 10 | |
|
|
3 |
4 |
2 10 |
+ 1 |
– 4 50 |
– 4Затраты на перевозку по построенному плану равны:
.
2. Строим систему потенциалов
, 
, 
,
, 
, 
,
, 
.
Полагаем 
и находим значения остальных потенциалов: 
, 
, 
, 
, 
, 
, 
, 
.
3. Проверяем систему на потенциальность:
, 
, 
,
, 
, 
,
, 
, 
,
, 
, 
,
Система непотенциальна.
1. Находим 
, строим цикл, =30. Улучшаем план. Новому плану соответствует таблица.
|
|
|
|
|
|
| |
|
| ||||||
|
|
2 30 |
4 80 |
2 10 |
3 |
8 | |
|
|
3 |
5 |
6 |
6 |
2 30 | |
|
|
6 |
8 |
7 |
4 0 |
5 40 | |
|
|
3 |
4 |
2 10 |
1 30 |
4 20 |
Затраты на перевозку по построенному плану равны:
.
2. Строим систему потенциалов
, , 
,
, , 
,
, .
Полагаем и находим значения остальных потенциалов: , , , , , , 
, .
3. Проверяем систему на потенциальность:
, , ,
, , ,
, , 
,
, , 
,
Система потенциальна, следовательно, план оптимален и окончательные затраты 
790. Данный метод широко применяется в экономических исследованиях для определения оптимального размера перевозки.
Задачи для контроля и самопроверки
Транспортные потоки некоторого предприятия представлены в виде сводных таблиц, определяющих общие затраты на перевозку груза. Необходимо определить является ли система потенциальной и рассчитать оптимальные затраты на перевозку при использовании предложенной схемы маршрутов.
Задача №1
|
bj ai |
7 |
7 |
7 |
7 |
2 |
|
4 |
16 |
30 |
17 |
10 |
16 |
|
6 |
30 |
27 |
26 |
9 |
23 |
|
10 |
13 |
4 |
22 |
3 |
1 |
|
10 |
3 |
1 |
5 |
4 |
24 |
Задача №2
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 |
