Динамическое программирование. Классические задачи динамического программирования. Функциональное уравнение Беллмана.

 

Ответы МО практика

1. Сформулировать алгоритм и произвести расчет двух итераций нахождения точки экстремума функции f(x) = 2x (3 - x) + 4 ® max; L₀ = [-2, 6]; l₀ = 0.7; l₀ > e ³ l₀/2 методами дихотомии и золотого сечения.

 

 

2. Сформулировать алгоритм и произвести расчет двух итераций нахождения точки экстремума функции f(x) = 2 + x (5 + 3x) ® min; L₀ = [-2, 3]; l₀ = 0.4; l₀ > e ³ l₀/2 методами дихотомии и Фибоначчи.

 

3. Сформулировать алгоритм и произвести расчет двух итераций нахождения точки экстремума функции f(х)=x²+2х ® min; L₀ = [-3, 5]; e ≤ 0,2 методами дихотомии и золотого сечения.

 

4. Сформулировать алгоритм и произвести расчет двух итераций нахождения точки экстремума функции f(х)=x²+2х ® min; L₀ = [-3, 5]; e ≤ 0,2 методами дихотомии и Фибоначчи.

 

10. Сформулировать алгоритм и произвести расчет двух итераций для нахождения экстремума (| min |) целевой функции f (x) = x ₁² – 4 x ₁ + 2 х ₂² + 2 х ₂, используя метод пропорционального градиентного поиска, начиная с точки Х⁰ = (1, 0).

 

11. Сформулировать алгоритм и произвести расчет двух итераций для нахождения экстремума (| min |) целевой функции f (x) = x ₁² – 4 x ₁ + 2 х ₂² + 2 х ₂, используя метод наискорейшего подъема (спуска), начиная с точки Х⁰ = (1, 0).

 

15. Построить двойственную задачу и осуществить расчет двух шагов решения:

4 x ₁ + x ₂ + x ₃ + 2 x ₄ + x ₅ ® max

4 x ₁ + x ₂ - x ₃ - x ₄ + x ₅ ³ 9

x ₁ + x ₂ - x ₃ + x ₄ - 6 x ₅ = 10

- x ₁ - x ₃ + 5 x ₅ £ 1

x ₁, x ₂, x ₃, x ₄, x ₅ ³ 0

 

 

Так как исходная задача на максимизацию, то приведем все неравенства системы ограничений к виду £ для чего обе части первого неравенства умножим на (-1) Получим:

 

-4 x ₁ - x ₂ + x ₃ + x ₄ - x ₅ £ -9

x ₁ + x ₂ - x ₃ + x ₄ - 6 x ₅ = 10

- x ₁ - x ₃ + 5 x ₅ £ 1

Составим расширенную матрицу системы

 

-4	-1			-1	-9
		-1		-6
-1		-1
					F

 

 

Транспонируем матрицу

 

-4		-1
-1
	-1	-1
-1	-6
-9			Z

 

Сформулируем двойственную задачу:

 

Z=9y1+10y2+y3 min

 

4y1+y2-y3 ³ 4

y1+y2 ³ 1

-y1-y2-y3 ³ 1

-y1+y2 ³ 2

y1-6y2+5y3 ³ 1

y1<=0 y2><0 y3>=0

 

4y1+y2-y3+y4 = 4

y1+y2 +y5 = 1

-y1-y2-y3 +y6 = 1

-y1+y2 +y7= 2

y1-6y2+5y3 +y8= 1

 

 

y4=4; y5=1; y6=1; y7=2; y8=1 первое допустимое решение

 

Составим симплекс таблицу

 

 

Базис	Своб	Y1	Y2	Y3	Y4	Y5	Y6	Y7	Y8
Y4	-4	-4	-1
Y5	-1	-1	-1
Y6	-1
Y7	-2		-1
Y8	-1	-1		-5
Z		-9	-10	-1

 

.

-4 минимальный свободный элемент

-9/-4

Y4 в свободные, y1 в базис

 

Составим симплекс таблицу

 

 

Базис	Своб	Y1	Y2	Y3	Y4	Y5	Y6	Y7	Y8
Y1			0,25	-0,25	-0,25
Y5			-0,75	-0,25	-0,25
Y6	-2		0,75	1,25	0,25
Y7	-3		-1,25	0,25	0,25
Y8			6,25	-5,25	-0,25
Z			-7,75	-3,25	-2,25

 

 

Y7 мин своб элемент

 

Y7 в свободные

Y2 в базис

 

Базис	Своб	Y1	Y2	Y3	Y4	Y5	Y6	Y7	Y8
Y1	0,4			-0,2	-0,2			0,2
Y5	1,8			-0,4	-0,4			-0,6
Y6	-3,8			1,4	0,4			0,6
Y2	2,4			-0,2	-0,2			-0,8
Y8	-15			-4
Z	27,6			-4,8	-3,8			-6,2

16. Сформулировать алгоритм и осуществить расчет (не более 2-х итераций) решения транспортной задачи методом потенциалов. Исходный опорный план - методом северо-западного угла. Вектор поставок - (10, 3, 7); Вектор потребления - (1, 8, 7, 4); Матрица стоимости:

 

 

Методом северо-западного угла найти начальный план перевозок в транспортной задаче, заданной матрицей перевозок (табл. 4.2).Таблица 4.2

Пункты	B1	B2	B3	B4	Запасы
А1	1	7	3	8	10
А2	3	4	2	2	3
А3	5	6	9	10	7
Потребности	1	8	7	4	20

Решение:

Начинаем вычисления по формуле (4.6) с северо-западного угла, т. е. с удовлетворения потребностей первого потребителя В₁ за счет запасов первого поставщика А₁: х₁₁ =min[10,1]=1. Потребности в пункте В₁ удовлетворены и, следовательно, х₂₁ = х₃₁ =0 (ставим точки, табл. 4.3). Первый столбец выбывает из рассмотрения. Остаток груза в пункте А₁ составит (10–1)=9.Таблица 4.3

Пункты	B1	B2	B3	B4	Запасы
А1	11	78	31	8•	10
А2	3•	4•	23	2•	3
А3	5•	6•	93	104	7
Потребности	1	8	7	4	20

Продолжаем заполнение таблицы с текущего северо-западного угла. Удовлетворены потребности В₂ и исчерпаны запасы А₁. Это случай вырождения: выбывают первая строка и второй столбец: х₁₃ = х₁₄ = х₂₂ = х₃₂= 0. Базисный нуль ставим в клетку (2,2) с наименьшей стоимостью. В остальных клетках выбываемых из дальнейшего рассмотрения столбца и строки ставим точки (табл. 4.4).Исчерпаны запасы А₂: х₂₄ =0 (ставим точку). Из рассмотрения выбывает вторая строка Осталось заполнить последнюю клетку: х₄₄ =4; Проверяем правильность решения: число заполненных (базисных) клеток табл. 4.6 равно 6, что соответствует рангу системы ограничений: m+n- 1=3+4-1=6. Выписываем начальный план перевозок: х₁₁ =1, х₁₂ =8, х₁₃ =1, х₁₄ =0, х₂₁ =0, х₂₂ =0, х₂₃ =3, х₂₄ =0, х₃₁ =0, х₃₂ =0, х₃₃ =3, х₃₄ =4.Подсчитаем суммарную стоимость перевозок: f =1∙1+7∙8+3∙1+2∙3+9∙3+10∙4=133. 2¹. Находим потенциалы, составляя для каждой базисной клетки уравнение α_i + β_j = c_ij. Полагаем β₃ =0. Тогда для базисных клеток (1,3), (2,3) и (3,3) имеем: α₁ + β₃ =3, α₂ + β₃ =2, α₃ + β₃ =9, откуда α₁ =3, α₂ =2, α₃ =9.Далее для базисных клеток (1,3), (2,1) и (3,2) имеем: α₁ + β₁ =1, β₁ =1 – α₁ =1 – 3= -2; α₁ + β₂ =4, β₂ =7 – α₂ =7–3= 4; α₃ + β₄ =2, β₄ =10 – α₃ =10–9= 1. 3¹. Для каждой свободной клетки вычисляем относительные оценки:∆_ij= c_ij –(α_i + β_j)= c_ij – α_i – β_j ∆₁₄==8–(3+1)=4, ∆₂₁==3–(2–2)=3, ∆₂₂==4–(2+4)=-2, ∆₂₄=2–(2+1)=-1,∆₃₁==5–(9-2)=-2, ∆₃₂=6–(9+4)= -7.

4¹. Проанализируем относительные оценки. Среди оценок имеется одна отрицательная: ∆₃₂=–7. Поэтому данный план не является оптимальным. Его можно улучшить перераспределением поставок.

5¹. Для клетки (3,1) построим означенный цикл.Таблица 4.14

Пункты	B1	B2	B3	B4	Запасы	αi
А1	11	78	31	8•	10	α1 =3
А2	3•	4•	23	2•	3	α2 =2
А3	5•	– + + – 6•	93	104	7	α3 =9
Потребности	1	8	7	4	20
βj	β1 =–2	β2 =4	β3 =0	β4 =1

6¹. Находим число θ, равное наименьшему из чисел, стоящих в отрицательных вершинах цикла: θ=min[8,3]=3. Выполним сдвиг по циклу на число θ=3: числа, стоящие в положительных вершинах цикла, увеличиваются на 3, а числа, стоящие в отрицательных вершинах, уменьшаются на 3. Результат сдвига (новый план перевозок) представлен в табл.

Пункты	B1	B2	B3	B4	Запасы
А1	11	75	34	8•	10
А2	3•	4•	23	2•	3
А3	5•	63	9•	104	7
Потребности	1	8	7	4	20

Чтобы проверить план на оптимальность, переходим к шагу 2 второй итерации.

 

2². Находим потенциалы, составляя для каждой базисной клетки уравнение α_i + β_j = c_ij. Полагаем α₁ =0. Тогда для базисных клеток (1,1), (1,2) и (1,3) имеем: α₁ + β₁ =1, α₁ + β₂ =7, α₁ + β₃ =3, откуда β ₁ =1, β ₂ =7, β ₃ =3.Далее для базисных клеток (1,3), (2,1) и (3,2) имеем: α₂ + β₃ =2, α₂ =2 – β₃ =2 – 3= -1; α₃ + β₂ =6, α₃ =6 – β₂ =6–7= -1; α₃ + β₄ =10, β₄ =10 – α₃ =10+1= 11. 3². Для свободных клеток вычисляем относительные оценки:∆₁₄==8–(11)=-3, ∆₂₁==3–(1-1)=3, ∆₂₂==4–(7-1)=-2, ∆₂₄==2–(11-1)=-8,∆₃₁==5–(1-1)=5, ∆₃₃=9–(3-1)= 7.

4². Условие окончания ∆_ij>0 не выполнено: ∆₂₄= –8.

 

5². Для клетки (2,2) построим означенный цикл (табл. 4.16).

Пункты	B1	B2	B3	B4	Запасы	αi
А1	11	75	– + + – 34	8•	10	α1 =0
А2	3•	4•	23	2•	3	α2 =-1
А3	5•	63	9•	104	7	α3 =-1
Потребности	1	8	7	4	20
βj	β1 =1	β2 =7	β3 =3	β4 =11

6². Находим число θ, равное наименьшему из чисел, стоящих в отрицательных вершинах цикла: θ=min[5,4]=4. Выполним сдвиг по циклу на число θ=4. Результат сдвига (новый план перевозок) представлен в табл. 4.17.Таблица 4.17

Пункты	B1	B2	B3	B4	Запасы	α
А1	11	71	34	84	10	0
А2	3•	4•	23	2•	3	-1
А3	5•	67	9•	10•	7	-1
Потребности	1	8	7	4	20
β	1	7	3	8

Чтобы проверить план на оптимальность, переходим к шагу 2 третьей итерации. 2³. Находим потенциалы, полагая α₁ =0. α₁ + β₁ =1, α₁ + β₂ =7, α₁ + β₃ =3, α₁ + β₄ =8: β₁ =1, β₂ =7, β₃ =3, β₄ =8; α₂ + β₃ =2: α₂ =-1; α₃ + β₂ =6: α₃ =-1; 3³. Вычисляем относительные оценки для свободных клеток:∆₂₁=3, ∆₂₂=-2, ∆₂₄=-5, ∆₃₁=5, ∆₃₃=7, ∆₃₄=3.Условие окончания ∆ij>0 не выполнено: ∆₂₄= –8. Рассчитываем минимальные затраты на транспортировку продукции:

f =1∙1+7∙1+3∙4+8∙4+3∙2+7∙6=100.

Этот план не является максимально оптимальным, но является оптимальнее предыдущих.

 

 

17. Сформулировать алгоритм и осуществить расчет (не более 2-х итераций) решения транспортной задачи методом потенциалов. Исходный опорный план - методом Фогеля. Вектор поставок - (10, 10, 20); Вектор потребления - (10, 8, 2, 20); Матрица стоимостей:

 

 

Штраф — это разность между двумя наименьшими стоимостями в текущей строке(столбце).

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

 

 

Пункты	B1	B2	B3	B4	Запасы	Штр.
А1	8•	1•	3•	3•	10	2
А2	2•	7•	2•	6•	10	0
А3	4•	6•	5•	8•	20	1
Потребности	10	8	2	20	40
Штрафы	2	5	1	3

 

Сравним значения а1 и b2 Т.к. b2<=a1, то получим X_1,2=b₂=8

A1=a1-X_1,2=10-8=2

Вычеркиваем столбец 2 (потребителя B2 исключаем из рассмотрения)

Найдем штрафы.

 

 

Пункты	B1	B2	B3	B4	Запасы	Штр.
А1	8•	8	3•	3•	2	0
А2	2•	•	2•	6•	10	0
А3	4•	•	5•	8•	20	1
Потребности	10	0	2	20
Штрафы	2		1	3

Сравним значения а1 и b4 Т.к. a1<=b4, то получим X_1,2=a1=2

 

B4=b4-X_1,4=20-2=18 a1=0

Вычеркиваем строку 1 (производителя a1 исключаем из рассмотрения)

Найдем штрафы.

 

 

Пункты	B1	B2	B3	B4	Запасы	Штр.
А1	•	8	•	2	0
А2	2•	•	2•	6•	10	0
А3	4•	•	5•	8•	20	1
Потребности	10	0	2	18
Штрафы	2		3	2

 

Сравним значения а2 и b3 Т.к. b3<=a2, то получим X_1,2=b3=2

 

A2=a2-X_2,3=10-2=8 b3=0

Вычеркиваем столбец 3 (потребителя b3 исключаем из рассмотрения)

Найдем штрафы.

 

Пункты	B1	B2	B3	B4	Запасы	Штр.
А1	•	8	•	2	0
А2	2•	•	2	6•	8	0
А3	4•	•	•	8•	20	1
Потребности	10	0	0	18
Штрафы	2			2

 

 

Сравним значения а2 и b1 Т.к. a2<=b1, то получим X_1,2=a2=8

 

B1=b1-X_2,1=10-8=2 a2=0

Вычеркиваем строку 2 (производителя a2 исключаем из рассмотрения)

Найдем штрафы.

 

Пункты	B1	B2	B3	B4	Запасы	Штр.
А1	•	8	•	2	0
А2	8	•	2	•	0
А3	4•	•	•	8•	20
Потребности	2	0	0	18
Штрафы

 

Поскольку в таблице осталась одна невычеркнутая строка, то перенесём значения из соответствующих Bj в оставшиеся незаполненные клетки таблицы, при этом значение a3 станет равным 0.

 

 

Пункты	B1	B2	B3	B4	Запасы	Штр.
А1	•	8	•	2	0
А2	8	•	2	•	0
А3	2	•	•	18	0
Потребности	0	0	0	0
Штрафы

 

Все строки и столбцы таблицы вычеркнуты. Значит, получено допустимое базисное решение. Решение является базисным. Среди заполненных клеток нет нулевых элементов, это значит, что решение является невырожденным.

 

Суммарные затраты данного решения F=186.

 

Пункты	B1	B2	B3	B4	Запасы
А1	8•	18	3•	32	10
А2	28	7•	22	6•	10
А3	42	6•	5•	818	20
Потребности	10	8	2	20	40

 

Решение методом потенциалов.

 

 

2¹. Находим потенциалы, составляя для каждой базисной клетки уравнение α_i + β_j = c_ij. Полагаем β₁ =0. Тогда для базисных клеток (2,1) и (3,1) имеем: Α₂ + β₁ =3, α₃ + β₁ =2, откуда α₂ =2, α₃ =4Далее для базисных клеток (1,3), (2,1) и (3,2) имеем: Α₂ + β₃ =2, β₃ =2 – α₂ =2–2= 0. Α₃ + β₄ =8, β₄ =8 – α₃ =8–4= 4. α₁ + β₄ =3, α₁ =3 – β₄ =3–4= -1; α₁ + β₂ =1, β₂ =1 – α₁ =1 +1= 2; 3¹. Для каждой свободной клетки вычисляем относительные оценки:∆_ij= c_ij –(α_i + β_j)= c_ij – α_i – β_j ∆₁₁==8–(0-1)=9, ∆₁₃==3–(0-1)=4, ∆₂₂==7–(2+2)=3, ∆₂₄=6–(4+2)=0,∆₃₂==6–(2-4)=8, ∆₃₃=5–(0+4)= 4.

4¹. Проанализируем относительные оценки. Среди оценок нет отрицательных. Поэтому данный план является оптимальным.

Минимальные затраты на транспортировку продукции:

f =186.

 

 

18. Сформулировать алгоритм и произвести расчет двух итераций для нахождения экстремума (|max|) целевой функции f(x) = 3x₁³ – x₁ – х₂³ – 3х₂² – 1, используя метод пропорционального градиентного поиска, начиная с точки Х⁰ = (0, 0).

Решение:

Начальный этап. Зададим координаты начальной точки x ⁽⁰⁾ =(0;0). Выражение для градиента функции в произвольной точке gradf(x₁,x₂)= (9x₁²-1;-3x₂²-6x₂)., начальный шаг h₀ =1, дробление шага 0,5

Присваиваем k =0.

Значение функции в начальной точке f( x⁽⁰⁾ )=f (0;0)=-1. Присваиваем k =0.

Основной этап:

Шаг 1⁰. gradf( x ⁽⁰⁾)= (-1;0).

Шаг 2⁰. Критерия останова нет. | gradf( x ^(k)) |=1, переходим к шагу 3⁰.

Шаг 3⁰. Значение шага h₀ =1.

Шаг 4⁰. Вычисляем координаты следующей точки:

x ⁽¹⁾= x ⁽⁰⁾–h₀*gradf( x ⁽⁰⁾) =(0;0)-1*(-1:0)=(1;0).

Значение функции в точке x ⁽¹⁾ f( x⁽¹⁾ ) = f (0,5;0)=1.

Шаг 5⁰. Проверяем выполнение условия f( x⁽¹⁾ )> f( x⁽⁰⁾ ).

Условие для k =0 выполнено (1>-1), поэтому не уменьшаем (дробим) шаг

Шаг 1¹. В точке x ⁽¹⁾ =(0,5;0) вычисляем градиент:

gradf( x ⁽¹⁾ = (-0,44;0)

и его длину | gradf( x ⁽¹⁾) |≈0,44.

Шаг 2¹. Критерия останова нет:.

переходим к шагу 3.

Шаг 3¹. Значение шага h₁ = h₀= 1.

Шаг 4¹. Вычисляем координаты следующей точки:

x ⁽²⁾= x ⁽¹⁾–h₁*gradf( x ⁽¹⁾) =(1; 0) –1*(-0,44;0))=(1,44;0).

Значение функции f( x⁽²⁾ ) = f (1,44;0)≈6,51.

Шаг 5¹. Проверяем выполнение условия f( x⁽²⁾ )< f( x⁽¹⁾ ).

Условие для k =1 выполнено (6,51<1), Присваиваем k:=k+1 =2 и переходим к шагу 1².

Готово. Данная задача не выполняется нормальным образом при дроблении шага. Например возьмем начальный шаг 0,5. Тогда значение функции будет не удовлетворять условию и придется дробить шаг. При 0,25 будет также и т.д. При шаге равном единице условие всегда будет удовлетворяться без дробления, но(!) при следующем шаге значение градиента будет 17,6. И при дроблении никогда не будет выполняться условие для продолжения действий. При шаге равном 0,5, но дроблению равном 2 также не будет выполняться условие, т.к. функция бесконечно растет.

 

19. Сформулировать алгоритм и произвести расчет двух итераций для нахождения экстремума (| max |) целевой функции f (x) = 3 x ₁³ – x ₁ – х ₂³ – 3 х ₂² – 1, используя метод наискорейшего подъема (спуска), начиная с точки Х⁰ = (0, 0).

Решение:

Начальный этап. Зададим координаты начальной точки x ⁽⁰⁾ =(0;0). Выражение для градиента функции в произвольной точке gradf(x₁,x₂)= (9x₁²-1;-3x₂²-6x₂) (см. пример 1).

Присваиваем k =0.

Основной этап:

Шаг 1⁰. В точке х^{( 0)} значение функции f(x^{( 0)})=-1, gradf( x ⁽⁰⁾)= (-1;0).

Шаг 2⁰. Критерия останова нет. | gradf( x ^(k)) |=1, переходим к шагу 3⁰.

Шаг 3⁰. Определяем величину шага h₀, для чего определим функцию φ(h₀). = f ((0;0) -h₀* (-1;0))= f (h₀;0) =

3 h₀ ³-h₀-1.

Найдем минимум функции φ(h₀) по h₀:

Отсюда h₀@ 0,33.

// это не понял Так как то найденное значение шага обеспечивает минимум функции φ(h₀) по h₀.

Шаг 4⁰. Определяем координаты точки x ⁽¹⁾:

x ⁽¹⁾= x ⁽⁰⁾–h₀*gradf( x ⁽⁰⁾) = (0;0) –0,33*(-1;0)=(0,33;0).

Присваиваем k:=k+1= 1 и переходим к шагу 1¹.

Шаг 1¹. В точке x ⁽¹⁾= (0,33;0) значение функции

f(x^{( 1)}) @-1,22,

значение градиента gradf( x ⁽¹⁾)= (0,49;0).

Шаг 2¹. Критерия останова нет. | gradf( x ^(k)) |=0,49, переходим к шагу 3⁰.

Шаг 3¹. Определяем величину шага h₁, для чего определим функцию φ (h₁). = f ((0,33;0)– h₁* (0,49;0))=

= f( 0,33-0,49 h₁;0) =

=3(0,33-0,49h₁)³-(0,33-0,49h₁)-1.

Найдем минимум функции φ(h₁) по h₁:

Отсюда h₁@ 1,35.

Шаг 4¹. Определяем координаты точки x ⁽²⁾:

x ⁽²⁾= x ⁽¹⁾–h₁*gradf( x ⁽¹⁾) = (0,33;0)–1,35*(0,49;0)@(-0,33;0).

Присваиваем k:=k+ 1 = 2 и переходим к шагу 1².

Шаг 1². В точке x ⁽²⁾ = (-0,33;0) значение функции f(x^{( 2)}) @-0,77,

 

20. Сформулировать алгоритм и решить задачу о назначениях венгерским методом (не более 2-х итераций). Матрица эффективности:

Исходная матрица имеет вид:

Шаг №1.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

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

После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 5). Другие нули в строке 1 и столбце 5 вычеркиваем.
Фиксируем нулевое значение в клетке (2, 1). Другие нули в строке 2 и столбце 1 вычеркиваем.
Фиксируем нулевое значение в клетке (3, 2). Другие нули в строке 3 и столбце 2 вычеркиваем.
Фиксируем нулевое значение в клетке (4, 3). Другие нули в строке 4 и столбце 3 вычеркиваем.
Фиксируем нулевое значение в клетке (5, 4). Другие нули в строке 5 и столбце 4 вычеркиваем.
В итоге получаем следующую матрицу:

				[0]
[0]		[-0-]
	[0]
		[0]
	[-0-]		[0]

Количество найденных нулей равно k = 5. В результате получаем эквивалентную матрицу Сэ:

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

				[0]
[0]		[-0-]
	[0]
		[0]
	[-0-]		[0]

Cmin = 3 + 3 + 2 + 2 + 5 = 15

 

 

21. Сформулировать алгоритм и решить задачу о назначениях венгерским методом (не более 2-х итераций). Матрица эффективности:

 

Исходная матрица имеет вид:

Шаг №1.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

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

После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 3). Другие нули в строке 1 и столбце 3 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 1).
Фиксируем нулевое значение в клетке (2, 2). Другие нули в строке 2 и столбце 2 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 1).
Фиксируем нулевое значение в клетке (3, 5). Другие нули в строке 3 и столбце 5 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 1).
Фиксируем нулевое значение в клетке (4, 4). Другие нули в строке 4 и столбце 4 вычеркиваем. Для данной клетки вычеркиваем нули в клетках (4; 1).
В итоге получаем следующую матрицу:

		[0]
	[0]
	[-0-]			[0]
[-0-]			[0]
		[-0-]

Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 4), то решение недопустимое.
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов:
строку 3, столбец 3, строку 4, столбец 2
Получаем сокращенную матрицу (элементы выделены):

Минимальный элемент сокращенной матрицы (min(7, 2, 5, 4, 4, 4, 5, 2, 2) = 2) вычитаем из всех ее элементов:

Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:

Шаг №2.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент.
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетке (1, 3). Другие нули в строке 1 и столбце 3 вычеркиваем.
Фиксируем нулевое значение в клетке (2, 2). Другие нули в строке 2 и столбце 2 вычеркиваем.
Фиксируем нулевое значение в клетке (3, 5). Другие нули в строке 3 и столбце 5 вычеркиваем.
Фиксируем нулевое значение в клетке (4, 1). Другие нули в строке 4 и столбце 1 вычеркиваем.
Фиксируем нулевое значение в клетке (5, 4). Другие нули в строке 5 и столбце 4 вычеркиваем.
В итоге получаем следующую матрицу:

		[0]	[-0-]
	[0]
				[0]
[0]			[-0-]
		[-0-]	[0]	[-0-]

Количество найденных нулей равно k = 5. В результате получаем эквивалентную матрицу Сэ:

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

		[0]	[-0-]
	[0]
				[0]
[0]			[-0-]
		[-0-]	[0]	[-0-]

Cmin = 1 + 2