Методы оптимальных решений

 

 

Задача 3

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

		Филиал 1	Филиал 2	Филиал 3
Предложение филиалов (ед.):		78	2	90
		потр.1	потр.2	потр.3	потр.4	потр.5
Спрос потребителей (ед.):		20	60	42	13	65
Известна матрица затрат на доставку единицы груза от каждого поставщика потребителю (руб.).
		потр.1	потр.2	потр.3	потр.4	потр.5
Поставщик 1		9	10	8	5	7
Поставщик 2		7	8	5	3	6
Поставщик 3		5	3	2	2	3

1. Составить ЭММ расчета  оптимального плана перевозок.

2. Определить исходный  опорный план методом северо-западного  угла.

3. Найти оптимальный план  перевозок методом потенциалов  и указать соответствующие ему  минимальные транспортные затраты.

 

Решение

1. Составление математической  модели задачи

Обозначим xij – величина поставки о поставщика к потребителю,

Z  - общая стоимость перевозок.

Составим ограничения модели:

Ограничение неотрицательности переменных модели:

Проверим сбалансированность задачи:

Объем поставок – 78+20+90=170

Объем потребностей –20+60+42+13+65=200

Задача несбалансированна, поэтому вводим дополнительного поставщика с объемом груза 200-170=30.

Составим балансы:

- поставщиков:

- потребителей:

Стоимость перевозок стремится к минимуму:

Математическая модель выглядит следующим образом:

        

Построим распределяющую таблицу:

 

Аi /Вj	20	60	42	13	65
78	9 х11	10 х12	8 х13	5 х14	7 х15
2	7 х21	8 х22	5 х23	3 х24	6 х25
90	5 х31	3 х32	2 х33	2 х34	5 х35
30	0 х41	0 х42	0 х43	0 х44	0 х45

 

Найдем опорный план методом северо-западного угла.

Аi /Вj	20	60	42	13	65
78	9 20	10 58	8 -	5 -	7 -
2	7 -	8 2	5 -	3 -	6 -
90	5 -	3 0	2 42	2 13	5 35
30	0 -	0 -	0 -	0 -	0 30

 

Стоимость перевозок составит:

Z=9·20+10·58+8·2+3·0+2·42+2·13+5·35=1061

Найдем оптимальный план методом потенциалов. На каждом шаге этого метода выполняются следующие действия:

1. вычисляются потенциалы, согласованные с построенным опорным планом;
2. производится проверка оптимальности текущего опорного плана;
3. если план оказывается неоптимальным, то строится новый опорный план с меньшим или, по крайней мере, таким же значением целевой функции.

Вычислим потенциалы поставщиков Ui и потребителей Vj, согласованные с найденным опорным планом. Потенциалы поставщиков Ui и потребителей Vj находятся путем решения системы уравнений:

Vj – Ui = Cij,

которые составляются для всех занятых клеток:

Занятая клетка	Уравнение
(1, 1)	V1 – U1 = 9
(1, 2)	V2 – U1 = 10
(2, 2)	V2 – U2 = 8
(3, 2)	V2 – U3 = 3
(3, 3)	V3 – U3 = 2
(3, 4)	V4 – U3 = 2
(3, 5)	V5 – U3 = 5
(4, 5)	V5 – U4 = 0

Например, положим U1 = 10, а затем последовательной подстановкой вычислим значения остальных потенциалов для опорного плана:

V1 = U1 + C11 = 10 + 9=19,   

V2 = U1 + C12 = 10 + 10 = 20,    

U2 = V2 – C22 =20 – 8 = 12,    

U3 = V2 – C32 = 20 – 3 = 17,      

V3 = U3 + C33 = 17 + 2 = 19,    

V4= U3 + C34 = 17 + 2 = 09,      

V5= U3 + C35 = 17 + 5 = 22,

U4 = V5 – C25 = 22 – 0 = 22.

 

Итак, найдены потенциалы, согласованные с начальным опорным планом Х0. Значения потенциалов Vj и Ui представлены соответственно в нижней строке и последнем столбце таблицы:

Аi /Вj	20	60	42	13	65	Ui
78	9 20	10        - 58	8 -	5 -	7           + -	10
2	7 -	8 2	5 -	3 -	6 -	12
90	5 -	3         + 0	2 42	2 13	5           - 35	17
30	0 -	0 -	0 -	0 -	0 30	22
Vj	19	20	19	19	22	1061

 

Проверим данный план на оптимальность. Для каждой свободной клетки (i, j) определим число ∆ij = Vj – Ui – Сij. Тогда ясно, что если ∆ij ≤ 0 для всех свободных клеток, то текущий опорный план является оптимальным. В противном случае этот план не оптимален.

Вычислим ∆ij для всех свободных клеток:

∆13= V3 – U1 – С13 =19-8-10=1,

∆14 = V4 – U1 – С14 =19-5-10=4,

∆15 = V5 – U1 – С15 =22-7-10=5,

∆21 = V1 – U2 – С21 =19-7-12=0,

∆23 = V3 – U2 – С23 =19-5-12=2,

∆24 = V4 – U2 – С24 =19-3-12=4,

∆25 = V5 – U2 – С25 =22-6-12=4,

∆31 = V1 – U3 – С31 =19-9-17= -3,

∆41 = V1 – U4 – С41=19-0-22 = -3,

∆42 = V2 – U4 – С42 = 20-22-0=0,

∆43 = V3 – U4 – С43 = 19-22-0=-3,

∆44 = V4 – U4 – С44 = 19-22-0=-3.

Анализ значений ∆ij показывает, что данный опорный план не оптимален, т.к. среди ∆ij имеются положительные значения. План может быть улучшен за счет перераспределения перевозок.

Из всех положительных значений ∆ij выбираем максимальное. В нашем случае оно соответствует свободной клетке (1, 5). В новом плане эта клетка будет занятой (введена в базис), т.е. будет осуществлена перевозка из пункта i в пункт j. Так как число занятых клеток меняться не должно, то одна из ранее занятых клеток освобождается. Освобождаемая (выводимая из базиса) клетка и новые объемы перевозок в занятых клетках определяются с помощью цикла.

Продолжим решение транспортной задачи методом потенциалов. Новый опорный план X1 проверяется на оптимальность. Для него снова рассчитываются потенциалы поставщиков Ui и потенциалы потребителей Vj. Пусть опять исходное значение U1 = 10.

Аi /Вj	20	60	42	13	65	Ui
78	9 20	10        23	8 -	5 -	7           35	10
2	7 -	8           - 2	5 -	3        + -	6 -	12
90	5 -	3         + 35	2 42	2         - 13	5           -	17
30	0 -	0 -	0 -	0 -	0 30	17
Vj	19	20	19	19	17

Вычислим ∆ij для всех свободных клеток:

∆13= V3 – U1 – С13 = 19-8-10=1,

∆14 = V4 – U1 – С14 = 19-5-10= 4,

∆21 = V1 – U2 – С21 =19-7-12=0,

∆23 = V3 – U2 – С23 =19-5-12=2,

∆24 = V4 – U2 – С24 =19-3-12=4,

∆25 = V5 – U2 – С25 =17-6-12=-1,

∆31 = V1 – U3 – С31 =21-9-15=-3,

∆35 = V5 – U3 – С35 =17-5-17=-5,

∆41 = V1 – U4 – С41=19-17-0=2,

∆42 = V2 – U4 – С42=20-0-17=3,

∆43 = V3 – U4 – С43 =19-17-0=2,

∆44 = V4 – U4 – С44 = 19-17-0=2.

Анализ значений ∆ij показывает, что данный опорный план не оптимален, т.к. среди ∆ij имеются положительные значения. План может быть улучшен за счет перераспределения перевозок.

Имеем опорный план Х3:

 

 

Аi /Вj	20	60	42	13	65	Ui
78	9 20	10       - 23	8 -	5        + -	7           35	10
2	7 -	8           -	5 -	3        2	6 -	16
90	5 -	3         + 37	2 42	2         - 11	5           -	17
30	0 -	0 -	0 -	0 -	0 30	17
Vj	19	20	19	19	17

Проверим данный план на оптимальность:

∆13= 19-8-10=1

∆14 = 19-5-10= 4,

∆21 =19-7-16= -4,

∆22 = 20-8-16= -4,

∆23 = 19-5-16= -2,

∆25 =17-6-16= -5,

∆31 =19-5-17= -3,

∆35 =17-5-17= -5,

∆41 =19-0-17=2,

∆42 =20-0-17=3,

∆43 =19-17-0= 2,

∆44 = 19-17-0=2.

Данный план не оптимален, производим его корректировку:

Аi /Вj	20	60	42	13	65	Ui
78	9 20	10        - 12	8 -	5        + 11	7           35	10
2	7 -	8           -	5         + -	3          - 2	6 -	12
90	5 -	3          + 48	2        - 42	2         -	5           -	17
30	0 -	0 -	0 -	0 -	0 30	17
Vj	19	20	19	15	17