Основы оптимизационных методов

Размещено на http://www.allbest.ru/

КОНТРОЛЬНАЯ РАБОТА

Вариант-34



Задача 1. Решить транспортную задачу по критерию стоимости.

Матрица цен: Емкость АТС: Потребность районов:

Решение:

Данная транспортная задача имеет открытый тип, так как суммарный запас (предложение) емкостей АТС больше суммарных потребностей районов:

Чтобы привести задачу к закрытому типу, вводим фиктивного потребителя B₆, потребность которого составляет 269-99=70, а стоимость перевозки равна 0.

Обозначим через - объем электроэнергии, переданной от поставщика (станции) потребителю (району) .

Тогда система ограничений примет вид:

Наша задача - составить такую схему распределения (из станции, в какой район и сколько единиц поставлять), чтобы все потребности были удовлетворены и общая стоимость всех распределений была минимальной (найти оптимальный план).

Тогда целевую функцию можно записать:

Условие неотрицательности объемов перевозок:

1) Найдем методом минимального элемента допустимый план перевозок:

Потребители Поставщики	B1	B2	B3	B4	B5	B6*	Запасы
A1	7 -	12 -	2 38	14 -	2 -	0 -	38
A2	19 -	23 -	8 4	13 7	13 11	0 16	38
A3	14 -	8 -	24 -	8 47	23 -	0 -	47
A4	8 47	6 -	8 -	12 -	9 -	0 -	47
A5	17 18	4 27	32 -	13 -	19	0 54	99
Потребности	65	27	42	54	11	70

Загрузку начинаем с клетки, которой соответствует наименьший тариф : транспортный гамильтонов контур программирование

Такой клеткой является клетка (1,3), для которой .

Помещаем в клетку . Из дальнейшего рассмотрения исключаем первую строку (запасы на станции А1 закончились).

Снова ищем клетку с минимальным тарифом: это клетка (5, 2), для которой с=4. Помещаем в нее . Исключаем второй столбец. И т.д.

В результате полного распределения, получаем исходное опорное решение:

,

F(x) = 2*38 + 8*4 + 13*7 + 13*11 + 0*16 + 8*47 + 8*47 + 17*18 + 4*27 + 0*54 = 1508

2) Проверим план X₀ на оптимальность методом потенциалов:

Поставщику ставим в соответствие потенциалы , а потребителю и определяем их.

Назначаем , и находим все остальные потенциалы из условия, что для занятых клеток должны выполняться условия:

u₁ + v₃ = 2; 0 + v₃ = 2; v₃ = 2

u₂ + v₃ = 8; 2 + u₂ = 8; u₂ = 6

u₂ + v₄ = 13; 6 + v₄ = 13; v₄ = 7

u₃ + v₄ = 8; 7 + u₃ = 8; u₃ = 1

u₂ + v₅ = 13; 6 + v₅ = 13; v₅ = 7

u₂ + v₆ = 0; 6 + v₆ = 0; v₆ = -6

u₅ + v₆ = 0; -6 + u₅ = 0; u₅ = 6

u₅ + v₁ = 17; 6 + v₁ = 17; v₁ = 11

u₄ + v₁ = 8; 11 + u₄ = 8; u₄ = -3

u₅ + v₂ = 4; 6 + v₂ = 4; v₂ = -2

	v1=11	v2=-2	v3=2	v4=7	v5=7	v6=-6
u1=0	7	12	2 38	14	2	0
u2=6	19	23	8[4	13 7	13 [11	0 16
u3=1	14	8	24	8 47	23	0
u4=-3	8 47	6	8	12	9	0
u5=6	17 18	4 27	32	13	19	0 54

Для всех свободных клеток находим оценки из соотношения

.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

(1;1): 0 + 11 > 7; ?₁₁ = 0 + 11 - 7 = 4

(1;5): 0 + 7 > 2; ?₁₅ = 0 + 7 - 2 = 5

max(4,5) = 5

Выбираем максимальную оценку свободной клетки (1;5): 2

Для этого в перспективную клетку (1;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	Запасы
1	7	12	2 38 [-]	14	2 [+]	0	38
2	19	23	8 4[+]	13 7	13 11[-]	0 16	38
3	14	8	24	8 [47	23	0	47
4	8 47	6	8	12	9	0	47
5	17 18	4 27	32	13	19	0 54	99
Потребности	65	27	42	54	11	70

Цикл приведен в таблице (1,5; 1,3; 2,3; 2,5; ).

Из х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 5) = 11. Прибавляем 11 к значениям, стоящих в плюсовых клетках и вычитаем 11 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	7	12	2 27	14	2 11	0	38
2	19	23	8 15	13 7	13	0 16	38
3	14	8	24	8 47	23	0	47
4	8 47	6	8	12	9	0	47
5	17 18	4 27	32	13	19	0 54	99
Потребности	65	27	42	54	11	70

Проверим оптимальность опорного плана. Находим потенциалы и оценки:

	v1=11	v2=-2	v3=2	v4=7	v5=2	v6=-6
u1=0	7	12	2 27	14	2 11	0
u2=6	19	23	8 15	13 7	13	0 16
u3=1	14	8	24	8 47	23	0
u4=-3	8 47	6	8	12	9	0
u5=6	17[18]	4[27]	32	13	19	0[54]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

(1;1): 0 + 11 > 7; ?₁₁ = 0 + 11 - 7 = 4

Выбираем максимальную оценку свободной клетки (1;1): 7

Для этого в перспективную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	Запасы
1	7 +	12	2 27 -	14	2 11	0	38
2	19	23	8 15 +	13 7	13	0 16 -	38
3	14	8	24	8 47	23	0	47
4	8 47	6	8	12	9	0	47
5	17[18] -	4[27]	32	13	19	0[54] +	99
Потребности	65	27	42	54	11	70



Цикл приведен в таблице (1,1; 1,3; 2,3; 2,6; 5,6; 5,1; ).

В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	7 16	12	2 11	14	2 11	0	38
2	19	23	8 31	13 7	13	0	38
3	14	8	24	8 47	23	0	47
4	8 47	6	8	12	9	0	47
5	17 2	4 27	32	13	19	0 70	99
Потребности	65	27	42	54	11	70

Проверим оптимальность опорного плана. Находим потенциалы и оценки

u₁ + v₁ = 7; 0 + v₁ = 7; v₁ = 7

u₄ + v₁ = 8; 7 + u₄ = 8; u₄ = 1

u₅ + v₁ = 17; 7 + u₅ = 17; u₅ = 10

u₅ + v₂ = 4; 10 + v₂ = 4; v₂ = -6

u₅ + v₆ = 0; 10 + v₆ = 0; v₆ = -10

u₁ + v₃ = 2; 0 + v₃ = 2; v₃ = 2

u₂ + v₃ = 8; 2 + u₂ = 8; u₂ = 6

u₂ + v₄ = 13; 6 + v₄ = 13; v₄ = 7

u₃ + v₄ = 8; 7 + u₃ = 8; u₃ = 1

u₁ + v₅ = 2; 0 + v₅ = 2; v₅ = 2

	v1=7	v2=-6	v3=2	v4=7	v5=2	v6=-10
u1=0	7 16	12	2 11	14	2 11	0
u2=6	19	23	8 31	13 7	13	0
u3=1	14	8	24	8 47	23	0
u4=1	8 47	6	8	12	9	0
u5=10	17 2	4 27	32	13	19	0 70



Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

(5;4): 10 + 7 > 13; ?₅₄ = 10 + 7 - 13 = 4

Выбираем максимальную оценку свободной клетки (5;4): 13

Для этого в перспективную клетку (5;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

	1	2	3	4	5	6	Запасы
1	7 16 +	12	2 11 -	14	2 11	0	7 16
2	19	23	8 31 +	13 7 -	13	0	19
3	14	8	24	8 47	23	0	14
4	8 47	6	8	12	9	0	8 47
5	17 2 -	4 27	32	13 +	19	0 70	17 2
Потребности	65	27	42	54	11	70

Цикл приведен в таблице (5,4; 5,1; 1,1; 1,3; 2,3; 2,4; ).

В результате получим новый опорный план.

	1	2	3	4	5	6	Запасы
1	7 18	12	2 9	14	2 11	0	38
2	19	23	8 33	13 5	13	0	38
3	14	8	24	8 47	23	0	47
4	8 47	6	8	12	9	0	47
5	17	4 27	32	13 2	19	0 70	99
Потребности	65	27	42	54	11	70

Проверим оптимальность опорного плана. Находим потенциалы и оценки:

u₁ + v₁ = 7; 0 + v₁ = 7; v₁ = 7

u₄ + v₁ = 8; 7 + u₄ = 8; u₄ = 1

u₁ + v₃ = 2; 0 + v₃ = 2; v₃ = 2

u₂ + v₃ = 8; 2 + u₂ = 8; u₂ = 6

u₂ + v₄ = 13; 6 + v₄ = 13; v₄ = 7

u₃ + v₄ = 8; 7 + u₃ = 8; u₃ = 1

u₅ + v₄ = 13; 7 + u₅ = 13; u₅ = 6

u₅ + v₂ = 4; 6 + v₂ = 4; v₂ = -2

u₅ + v₆ = 0; 6 + v₆ = 0; v₆ = -6

u₁ + v₅ = 2; 0 + v₅ = 2; v₅ = 2

	v1=7	v2=-2	v3=2	v4=7	v5=2	v6=-6
u1=0	7 18	12	2 9	14	2 11	0
u2=6	19	23	8 33	13 5	13	0
u3=1	14	8	24	8 47	23	0
u4=1	8 47	6	8	12	9	0
u5=6	17	4 27	32	13 2	19	0 70

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Запишем оптимальный план:

Минимальные затраты составят:

F(x) = 7*18 + 2*9 + 2*11 + 8*33 + 13*5 + 8*47 + 8*47 + 4*27 + 13*2 + 0*70 = 1381

Ответ: , F(x) = = 1381

Задача 2. Найти гамильтонов контур минимальной длины методом динамического программирования

Матрица расстояний:

Решение:

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

Пусть xi - произвольная вершина (i =1,2…6), а V - любое подмножество вершин, не содержащее вершины x1 и вершины xi. Через М(i, V) обозначим совокупность путей, каждый из которых начинается из xi, завершается в x1 и проходит в качестве промежуточных только через города множества V, заходя в каждый из них ровно по одному разу. Через В(i, V ) обозначим длину кратчайшего пути множества М(i, V ). Для решаемой задачи В(i, V) - функция Беллмана. Как очевидно, В(1, {2, 3, …, n}) - искомая минимальная длина простого (без самопересечений) замкнутого пути, проходящего через все вершины.

Если V - одноэлементное множество, V ={j}, где j ? 1 и j ? i, то совокупность М (i, V) состоит из единственного пути µ = (i, j, 1). Поэтому

i N, j {2, 3,…, n}, j ? i. (1)

Предположим, что значения функции В(i, V ) для всех i N\{1} и всех возможных k-элементных (k < n - 1) множеств V уже вычислены. Тогда значение В(i, V'), где V' - произвольное (k + 1)-элементное подмножество совокупности N \ {1, i}, вычисляется по формуле



(2)

Уравнения (1)-(2) - рекуррентные соотношения динамического программирования для решения задачи коммивояжера, они обеспечивают реализацию обратного метода Беллмана.

Сначала, пользуясь формулой (1), определяем значения В(i, {j}):

В(2, {3}) = s23 + s31 = 5 + 15 =20

В(2, {4}) = s24 + s41 = 12 + 4 =16

В(2, {5}) = s25 + s51 = 19 + 17 =36

В(2, {6}) = s26 + s61 = 9 + 16 =25

В(3, {2}) = s32 + s21 = 7 + 12 =19

В(3, {4}) = s34 + s41 = 8 + 4 =12

В(3, {5}) = s35 + s51 = ? + 17 =?

В(3, {6}) = s36 + s61 = 12 + 16 =28

В(4, {2}) = s42 + s21 = 12 + 12 =24

В(4, {3}) = s43 + s31 = 11 + 15 =26

В(4, {5}) = s45 + s51 = 3 + 17 =20

В(4, {6}) = s46 + s61 = 11 + 16 =27

В(5, {2}) = s52 + s21 = 3 + 12 =15

В(5, {3}) = s53 + s31 = 12 + 15 =27

В(5, {4}) = s54 + s41 = 18 + 4 =22

В(5, {6}) = s56 + s61 = 16 + 16 =32

В(6, {2}) = s62 + s21 = 8 + 12 =20

В(6, {3}) = s63 + s31 = 13 + 15 =28

В(6, {4}) = s64 + s41 = 11 + 4 =15

В(6, {5}) = s65 + s51 = 19 + 17 =36

Далее по формуле (2) последовательно получаем :

В(4, {2, 3}) = min [s42 + B(2,{3}); s43 + B(3,{2})] = min(12 + 20; 11 + 19)=30 /432;

В(5, {2, 3}) = min [s52 + B(2,{3}); s53 + B(3,{2})] = min(3 + 20; 12 + 19)=23 /523;

В(6, {2, 3}) = min [s62 + B(2,{3}); s63 + B(3,{2})] = min(8 + 20; 13 + 19) =28 /623 ;

В(3, {2, 4}) = min [s32 + B(2,{4}); s34 + B(4,{2})] = min(7 + 16; 8 + 24)=23 /324;

В(5, {2, 4}) = min [s52 + B(2,{4}); s54 + B(4,{2})] = min(3 + 16; 18 + 24)=19 /524;

В(6, {2, 4}) = min [s62 + B(2,{4}); s64 + B(4,{2})] = min(8 + 16; 11 + 24)=24 /624;

В(3, {2, 5}) = min [s32 + B(2,{5}); s35 + B(5,{2})] = min(7 + 36; ? + 15)=43 /325;

В(4, {2, 5}) = min [s42 + B(2,{5}); s45 + B(5,{2})] = min(12 + 36; 3 + 15)=18 /452;

В(6, {2, 5}) = min [s62 + B(2,{5}); s65 + B(5,{2})] = min(3 + 36; 19 + 15)=34 /652;

В(3, {2, 6}) = min [s32 + B(2,{6}); s36 + B(6,{2})] = min(7 + 25; 12 + 20)=32 /(326 или 362);

В(4, {2, 6}) = min [s42 + B(2,{6}); s46 + B(6,{2})] = min(12 + 25; 11 + 20)=31 /462;

В(5, {2, 6}) = min [s52 + B(2,{6}); s56 + B(6,{2})] = min(3 + 25 ; 16 + 20)=28 /526;

В(2, {3, 4}) = min [s23 + B(3,{4}); s24 + B(4,{3})] = min(5 + 12; 12 + 26)=17 /234;

В(5, {3, 4}) = min [s53 + B(3,{4}); s54 + B(4,{3})] = min(12 + 12;18 + 26)=24 /534;

В(6, {3, 4}) = min [s63 + B(3,{4}); s64 + B(4,{3})] = min(13 +12; 11 + 26)=25 /634;

В(2, {3, 5}) = min [s23 + B(3,{5}); s25 + B(5,{3})] = min(5 + ?; 19 + 27)=46 /253;

В(4, {3, 5}) = min [s43 + B(3,{5}); s45 + B(5,{3})] = min(11 + ?; 3 + 27)=30 /453;

В(6, {3, 5}) = min [s63 + B(3,{5}); s65 + B(5,{3})] = min(13 + ?; 19 + 27)=46 /653;

В(2, {3, 6}) = min [s23 + B(3,{6}); s26 + B(6,{3})] = min(5 + 28; 9 + 28)=33 /236;

В(4, {3, 6}) = min [s43 + B(3,{6}); s46 + B(6,{3})] = min(11 + 28; 11 + 28)=39 /(436 или 463);

В(5, {3, 6}) = min [s53 + B(3,{6}); s56 + B(6,{3})] = min(12 + 28; 16 + 28)=40 / 536;

В(2, {4, 5}) = min [s24 + B(4,{5}); s25 + B(5,{4})] = min(12 + 20; 19 + 22)=32 /245;

В(3, {4, 5}) = min [s34 + B(4,{5}); s35 + B(5,{4})] = min(8 + 20; ? + 22)=28 /345;

В(6, {4, 5}) = min [s64 + B(4,{5}); s65 + B(5,{4})] = min(11 + 20; 19 + 22)=31 /645;

В(2, {4, 6}) = min [s24 + B(4,{6}); s26 + B(6,{4})] = min(12 + 27; 9 + 15)=24 /264;

В(3, {4, 6}) = min [s34 + B(4,{6}); s36 + B(6,{4})] = min(8 + 27; 12 + 15)=27 /364;

В(5, {4, 6}) = min [s54 + B(4,{6}); s56 + B(6,{4})] = min(18 + 27; 16 + 15)=31 /564;

В(2, {5, 6}) = min [s25 + B(5,{6}); s26 + B(6,{5})] = min(19 + 32; 9 + 36)=45 /265;

В(3, {5, 6}) = min [s35 + B(5,{6}); s36 + B(6,{5})] = min(? + 32; 12 + 36)=48 /365;

В(4, {5, 6}) = min [s45 + B(5,{6}); s46 + B(6,{5})] = min(3+ 32; 11 + 36)=35 /456;

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

Выполняем по формуле (2) следующий шаг:

В(5, {2,3,4}) = min [s52 + B(2,{3,4}); s53 + B(3,{2,4}); s54 + B(4,{2,3})] = min(3+17 /234 ; 12+23 /324 ; 18+30 /432)=20 /5234;

В(6, {2,3,4}) = min [s62 + B(2,{3,4}); s63 + B(3,{2,4}); s64 + B(4,{2,3})] = min(8+17 /234 ; 13+23 /324; 11+30 /432 )=25 /6234;

В(4, {2,3,5}) = min [s42 + B(2,{3,5}); s43 + B(3,{2,5}); s45 + B(5,{2,3})] = min(12+46 /253; 11+43 /325; 3+23 /523)=26 /4523;

В(6, {2,3,5}) = min [s62 + B(2,{3,5}); s63 + B(3,{2,5}); s65 + B(5,{2,3})] =min(8+46 /253; 13+43 /325; 19+23 /523)=42 /6523;

В(4, {2,3,6}) = min [s42 + B(2,{3,6}); s43 + B(3,{2,6}); s46 + B(6,{2,3})] =min(12+33 /236; 11+32 /(326 или 362); 11+28 /623)=39 /4623;

В(5, {2,3,6}) = min [s52 + B(2,{3,6}); s53 + B(3,{2,6}); s56 + B(6,{2,3})] =min(3+33 /236; 12+32 /(326 или 362); 16+28 /623)=36 /5236;

В(3, {2,4,5}) = min [s32 + B(2,{4,5}); s34 + B(4,{2,5}); s35 + B(5,{2,4})] = min(7+32 /245; 8+18 /452; ?+19 /524)=26 /3452;

В(6, {2,4,5}) = min [s62 + B(2,{4,5}); s64 + B(4,{2,5}); s65 + B(5,{2,4})] = min(8+32 /245; 11+18 /452; 19+19 /524)=29 /6452;

В(3, {2,4,6}) = min [s32 + B(2,{4,6}); s34 + B(4,{2,6}); s36 + B(6,{2,4})] =min(7+24 /264; 8+31 /462; 12+24 /624)=31 /3264;

В(5, {2,4,6}) = min [s52 + B(2,{4,6}); s54 + B(4,{2,6}); s56 + B(6,{2,4})] =min(3+24 /264; 18+31 /462; 16+24 /624)=27 /5264;

В(3, {2,5,6}) = min [s32 + B(2,{5,6}); s35 + B(5,{2,6}); s36 + B(6,{2,5})] = min(7+45 /265; ?+28 /526; 12+34 /652)=46 /3652;

В(4, {2,5,6}) = min [s42 + B(2,{5,6}); s45 + B(5,{2,6}); s46 + B(6,{2,5})] =min(12+45 /265; 3+28 /526; 11+34 /652)=31 /4526;

В(2, {3,4,5}) = min [s23 + B(3,{4,5}); s24 + B(4,{3,5}); s25 + B(5,{3,4})] =min(5+28 /345; 12+30 /453; 19+24 /534)=33 /2345;

В(6, {3,4,5}) = min [s63 + B(3,{4,5}); s64 + B(4,{3,5}); s65 + B(5,{3,4})] = min(13+28 /345; 11+30 /453; 19+24 /534)=41 /(6345 или 6453);

В(2, {3,4,6}) = min [s23 + B(3,{4,6}); s24 + B(4,{3,6}); s26 + B(6,{3,4})] = min(5+27 /364; 12+39 /(436 или 463); 9+25 /634)=32 /2364;

В(5, {3,4,6}) = min [s53 + B(3,{4,6}); s54 + B(4,{3,6}); s56 + B(6,{3,4})] =min(12+27 /364; 18+39 /(436 или 463); 16+25 /634)=39 /5364;

В(2, {3,5,6}) = min [s23 + B(3,{5,6}); s25 + B(5,{3,6}); s26 + B(6,{3,5})] = min(5+48 /365; 19+40 / 536; 9+46 /653)=53 /2365;

В(4, {3,5,6}) = min [s43 + B(3,{5,6}); s45 + B(5,{3,6}); s46 + B(6,{3,5})] = min(11+48 /365; 3+40 / 536; 11+46 /653)=43 /4536;

В(2, {4,5,6}) = min [s24 + B(4,{5,6}); s25 + B(5,{4,6}); s26 + B(6,{4,5})] = min(12+35 /456; 19+31 /564; 9+31 /645)=40 /2645;

В(3, {4,5,6}) = min [s34 + B(4,{5,6}); s35 + B(5,{4,6}); s36 + B(6,{4,5})] = min(8+35 /456; ?+31 /564; 12+31 /645)=43 /(3456 или 3645);

Выполняем по формуле (2) следующий шаг:

В(6,{2,3,4,5})=min [s62+B(2,{3,4,5}); s63+B(3,{2,4,5}); s64+B(4,{2,3,5});s65+B(5,{2,3,4})] = min(8+33 /2345; 13+26 /3452; 11+26 /4523; 19+20 /5234)=37 /64523;

В(3,{2,4,5,6})=min [s32+B(2,{4,5,6}); s34+B(4,{2,5,6}); s35+B(5,{2,4,6});s36+B(6,{2,4,5})] = min(7+40 /2645; 8+31 /4526; ?+27 /5264; 12+29 /6452)=39 /34526;

В(2,{3,4,5,6})=min [s23+B(3,{4,5,6}); s24+B(4,{3,5,6}); s25+B(5,{3,4,6});s26+B(6,{3,4,5})] = min(5+43/(3456 или 3645);12+43 /4536;19+39/5364; 9+41/(6345 или 6453))=48/(23456 или 23645);

Итак, все шаги метода динамического программирования выполнены: оптимальное значение критерия равно 37.

Оптимальный маршрут следующий:

1 ® 6 ® 5 ® 2 ® 3® 1.

Длина маршрута: 37+s31=37+15=52

Ответ: 1 > 6 > 5 > 2 > 3> 1, S=52

Размещено на Allbest.ru