1.4. Метод минимального элемента в матрице.

Алгоритм:

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

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

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

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

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

bj ai	30	26	53	46
47	8 4,2	5,3	6,1	39 7,0
48	22 2,9	26 2,6	5,4	3,8
60	6,2	5,0	53 3,6	7 4,5

Клетка Х₂₂=min(48;26)=26

Х₂₁=min(48-26;30)=22

Х₃₃=min(60;53)=53

Х₁₁=min(47;30-22)=8

Х₃₄=min(60-53;46)=7

Х₁₄=min(47-8;46-7)=39

Проверим план на допустимость: подставим все Х_ij в системы ограничений

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

8+0+0+39=47

22+26+0+0=48

0+0+53+7=60

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

8+22+0=30

0+26+0=26

0+0+53=53

39+0+7=46

Ограничения выполняются, значит, план является допустимым.

Рассчитаем целевую функцию:

F= у.е.

Найдем оптимальное решение методом потенциалов

1.5. Метод потенциалов.

1. Составляется начально допустимый вариант решения.

2. Вариант решения проверяется на невырожденность. Оптимальное решение находится среди невырожденных вариантов

Z=m+n-1,

где Z – количество базисных клеток,

m,n –количество строк и столбцов матицы

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

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

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

с_ij- оценочные величины

4. По рассчитанным потенциалам рассчитываются характеристики (для свободных клеток , где Х_ij=0)

5 . Вариант решения проверяется на оптимальность: если F min, то , для всех i и j .

6 . Если вариант решения не является оптимальным, находится максимальный элемент неоптимальности плана: если F min C_min=max

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

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

9. Находится минимальный элемент контура перераспределения Х_min=min(X_ij) разгружаемых клеток. Строится матрица следующей итерации, в которой Х_ij не принадлежащие контуру остаются прежними. Х_ij разгружаемых клеток:

(Х_ij)_р=Х_ij-X_min,

(Х_ij)_з=Х_ij+X_min.

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

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

47+48+60=30+26+53+46 следовательно модель имеет закрытый вид.

		30		26		53		46
		4,2		5,8		6,1		7,0
47	0	30						17
			4,2		5,3		6,1		7,0
48	-3,2			26				22
			2,9		2,6		5,4		3,8
60	-2,5					53		7
			6,2		5,0		3,6		4,5

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

1. 0+ =4,2

=4,2

2. 0+ =7,0

=7,0

3. 

= -3,2

4)

5) +7,0=4,5

= -2,5

6)-2,5+ =3,6

=6,1

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

= 0+5,8-5,3= 0,5

= 0+6,1-6,1=0

= -3,2+4,2-2,9= -1,9

= -3,2+6,1-5,4= -2,5

= -2,5+4,2-6,2= -4,5

= -2,5+5,8-5,0= -1,7

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

Выбираем максимальный элемент неоптимальности плана: =0,5.

Строим контур перераспределения ресурсов, вершина с максимальным элементом неоптимальности- загружаемая. Минимальный разгружаемый элемент контура Х_min=17.

Строим следующую матрицу, пересчитываем элементы контура:

Х₁₂=0+17=17

Х₁₄=17-17

Х₂₄=22+17=39

Х₂₂=26-17=9

		30		26		53		46
		4,2		5,3		5,6		6,5
47	0	30		17
			4,2		5,3		6,1		7,0
48	-2,7			9				39
			2,9		2,6		5,4		3,8
60	-2,0					53		7
			6,2		5,0		3,6		4,5

Проверим план на допустимость: подставим все Х_ij в системы ограничений

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

30+17+0+0=47

0+9+0+39=48

0+0+53+7=60

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

30+0+0=30

17+9+0=26

0+0+53=53

0+39+7=46

Ограничения выполняются, значит, план является допустимым.

Рассчитаем целевую функцию:

F₂= у.е.

( величина экономии ресурсов на единицу груза, полученная в результате перераспределения).

Z=m+n-1= 4+3-1=6 вариант не вырожден

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

1. 0+ =4,2

=4,2

2. 0+ =5,3

=5,3

3. +5,3=2,6

= -2,7

4) -2,7 + =3,8

= 6,5

5) +6,5 = 4,5

= -2

6)-2,0 + = 3,6

= 5,6

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

= 0 + 5,6 - 6,1 = -0,5

= 0 + 6,5 -7,0 = -0,5

= -2,7 + 4,2 – 2,9 = - 1,4

= -2,7 +5,6 – 5,4 = - 2,5

= -2,0 +4,2 – 6,2 = -4,0

= -2,0 +5,3 – 5,0 = -1,7

Характеристики не положительны, значит, данный план перевозок является оптимальным при F min.