Решение транспортной задачи методом минимального элемента в матрице

Алгоритм:

1. Рассматриваются значения оценочной величины С_ij всей матрицы и выбирается минимум, если , максимум, если .

.   Соответствующий элемент загружается из стандартного условия

 

.

 

3. Из рассмотрения исключается столбец или строк, где ресурсы исчерпаны.

4. Алгоритм повторяется без учёта исключённых столбцов и строк до исчерпания всех ресурсов.

.   Вариант решения проверяется на допустимость т рассчитывается значение целевой функции.

 

 

Проверка ограничений:

По поставщикам

По потребителям

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

у.е.

Решение транспортной задачи методом потенциалов

Алгоритм:

1. Составляется начально допустимый вариант решения (можно любым приближённым методом или любым известным способом, например способ северо-западного угла).

2. Вариант проверяется на не вырожденность. Оптимальный вариант находится среди невырождённых вариантов. Количество базисных клеток должно равняться

 

.

 

Для базисного элемента ;

Для свободных и небазисных ;

Если вариант решения вырожденный, то от вырожденности избавляются (например при помощи заведения значащего нуля).

3. Рассчитывается потенциалы по базисным клеткам

 

;

где  - потенциал i-ой строки,

 - потенциал j-го столбца.

4. Рассчитываются характеристики для каждой свободной слетки, где Хij=0 по формуле

 

;

 

Характеристика означает величину экономии ресурсов на единицу груза, полученную в результате перераспределения ресурсов в данную свободную клетку, поэтому может выступать в качестве дополнительного критерия оптимальности.

.   Вариант решения проверяется на оптимальность. Для оптимального варианта, если  для всех i,j; если  для всех i,j.

.   Если вариант не является оптимальным находится максимальный элемент не оптимальности плана

 

 

7. На основании максимального элемента не оптимальности строится контур перераспределения ресурсов.

Правила построения контура

1. Все углы контура прямые.

2. Одна вершина находится в клетке с максимальным элементом не оптимальности, все другие в базисных клетках

8. Вершины контура последовательно разделяются на загружаемые и разгружаемые. В клетки с максимальным элементом загружаемая вершина.

9. Находится минимальный элемент контура перераспределения ресурсов кА минимум Х_ij в разгружаемых клетках.

.   Строится матрица следующей итерации Х_ij в которой остаются прежними, если не принадлежали контуру перераспределения

 

;

.

 

11. Алгоритм повторяется до получения оптимального варианта решения.

12. На каждой итерации вариант решения проверяется на допустимость и рассчитывается значение целевой функции. Для двух соседних итераций разница между целевыми функциями равна максимальному элементу не отрицательности умноженному на минимальный элемент контура перераспределения.

 

 

Рассмотрим пример варианта решения которого были получены ранее и в качестве начально допустимого варианта выберем план, полученный методом минимального элемента в матрице, так как при  имеет наименьшую целевую функцию.

 

Рассчитываем потенциалы:

 клетка 21:

;

клетка 24:

;

клетка 14:

;

клетка 12:

;

клетка 34:

;

клетка 33:

;

Рассчитаем характеристики для свободных клеток:

-

максимальный элемент неоптимальности плана при

 

Данный вариант решения не является оптимальным, т.к. присутствует положительная характеристика при .

На основании максимального элемента не оптимальности строим контур перераспределения ресурсов

 

 

Рассчитываем потенциалы:

 клетка 21:

;

клетка 11:

;

клетка 12:

;

клетка 24:

;

клетка 34:

;

клетка 14:

;

 у.е.

Данный вариант решения является оптимальным, так как для всех i и j; F=Fopt

у.е.

Результаты решения транспортной задачи занесём в таблицу

 

Пункт добычи	Клиент	Количество перевозок, тыс. т	Расстояние перевозок, км *10-2	Грузооборот, млн. ткм	Стоимость перевозок, у.е.
Д 1	В 1	12	50	60	51,6
Д 1	В 2	40	60	240	144
Д 2	В 1	9	24	21,6	28,8
Д 2	В 4	39	39	152,1	117
Д 3	В 3	28	70	196	89,6
Д 3	В 4	6	45	27	22,8
				Итого:	453,8

Распределительная задача

Исходные данные

По сформированным участкам грузовой работы расставить наличное количество флота трех типов так, чтобы эксплуатационные расходы оказались при этом наименьшими.

Для работы с клиентами порт располагает флотом трёх типов Ф₁, Ф₂, Ф₃ в количестве

 

;

.

Имеются матрицы эксплуатационных расходов по одному за расчётный период Э и провозной способности различных типов флота по участкам работы :

Имеются участки грузовой работы с грузооборотом:

А=(60; 240; 21,6; 152,1; 196; 27).

ЭММ распределительной задачи:

1. Критерий эффективности - минимальные эксплуатационные расходы

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

 

,

 

где Х_ij - количество i-го типа флота, работающего на j-м участке.

 

Система ограничений:

По флоту:

 

 

По грузообороту:

 

 

Дополнительные условия: