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

Решение задач по методам оптимальных решений. Защитил на 100 баллов, работа была заказана. ...

1. Транспортная задача
2. Решение транспортной задачи в среде Microsoft Exсel
3. Задача теории игр
4. Задача динамического программирования

Решение транспортной задачи различными видами, задачи теории игр, динамическое программирование и т.д

1
22
2
2
15
13
-
2
12
27
-
10
12
4
-
24
-
-12
3
17
3
17
16
-
25
-
5
-
-18
4
13
28
-
11
1
17
-
10
12
-11
vj
21
22
2
21
Вычисляем оценки свободных клеток:
14 = u1 + v4  c14 = 0 + 21 – 13 = 8 > 0,
21 = u2 + v1  c21 = -12 + 21 – 27 = -18 < 0,
23 = u2 + v3  c23 = -12 + 2 – 4 = -14 < 0,
24 = u2 + v4  c24 = -12 + 21 – 24 = -15 < 0,
32 = u3 + v2  c32 = -18 + 22 – 16 = –12 < 0,
33 = u3 + v3  c33 = -18 + 2 – 25 = –41 < 0,
34 = u3 + v4  c34 = -18 + 21 – 5 = –2 < 0,
41 = u4 + v1  c41 = -11 + 21 – 28 = -18 < 0.
43 = u4 + v3  c43 = -11 + 2 – 17 = -26 < 0.
В распределительной таблице оценки клеток проставлены в нижнем левом углу в скобках:
bj
ai
1
2
3
4
ui
18
15
15
12
1
18
21
1
22
2
2
15
13
(8)
2
12
27
(-18)
10
12
4
(-14)
24
(-15)
-12
3
17
3
17
16
(-12)
25
(-41)
5
(-2)
-18
4
13
28
(-18)
11
1
17
(-26)
10
12
-11
vj
21
22
2
21
Получили положительную оценку свободных клеток: 14 = 8 > 0. Следовательно, исходное опорное решение не является оптимальным и его можно улучшить.
Переход к следующему опорному решению.
Выбираем клетку, от которой начнем построение цикла перераспределения поставок, по правилу , или , т.е. максимальную величину оценки имеет свободная клетка (1, 4). Для этой клетки можно построить следующий цикл: 09480 (все вершины цикла, кроме первой, находятся в занятых клетках, углы прямые, число вершин четное). У вершин цикла с соответствующими значениями поставок по правилу чередования знаков ставим знаки (+) и (–).У вершин со знаком (–) выбираем минимальный груз  = min[9, 8] = 8.
.
Значение целевой функции:
= 1*21 + 15*2 + 2*13 + 12*10 + 17*3 + 3*11 + 10*10 = 381
Значение целевой функции уменьшилось на 16 ед.
Проверка решения Х1 на оптимальность выполняется аналогично предыдущему шагу. Расчет потенциалов для занятых клеток. Расчет оценок свободных клеток.
Результаты расчета представлены в распределительной таблице:
bj
ai
1
2
3
4
ui
18
15
15
12
1
18
21
1
22
(-8)
2
15
13
2
2
12
27
(-10)
10
12
4
(-6)
24
(-15)
-4
3
17
3
17
16
(-20)
25
(-41)
5
(-10)
-18
4
13
28
(-10)
11
3
17
(-18)
10
10
-3
vj
21
14
2
13
Все оценки свободных клеток отрицательные, следовательно, решение Х1 оптимально.
Так как в свободных клетках нет нулевых оценок, значит, что задача не имеет альтернативные решения.
Таким образом, решение транспортной задачи:
, , L(X*) = 381.
5. Решение транспортной задачи в среде Microsoft Exсel
Ввод исходных данных (в области C3:F6 – тарифы на перевозку продукции; в столбце G3:G6 – запасы; в ячейках С7, D7, E7, F7 – потребности).
В области решения в ячейке G10 введите формулу стоимости перевозок:
=СУММПРОИЗВ(C12:F15;C3:F6). Для этого необходимо нажать на значок f(x) на панели инструментов, выбрать математическую функцию СУММПРОИЗВ и ввести два массива C12:F15 и C3:F6. Далее в области C12:F15 проставьте любое первоначальное решение (например, единицы)/
В ячейке С16 записывается формула: =СУММ(C12:C14), т.е. сумма значений по столбцу (можно выделить значения столбца и нажать на знак автосуммы Σ на панели инструментов). Аналогично в D16, E16, F16. Автоматически суммируются значения по столбцам.
В ячейке G12 записывается формула: =СУММ(C12:F12), т.е. сумма значений по строке (можно выделить значения строки и нажать на знак автосуммы Σ на панели инструментов). Аналогично в G13, G14, G15. Автоматически суммируются значения по строкам:
Далее выполняют команду Поиск решения (вкладка Сервис или Данные).
Установить целевую ячейку G10, равной минимальному значению.
В поле ввода Изменяя ячейки установить C12:F15
В поле ввода Ограничения установить C12:F15 >= 0
C16:E16 = C7:E7
G12:G15 = G3:G6
Далее нажимают на кнопку Параметры и устанавливают флажок на метод поиска сопряженных градиентов:
Вычисления производятся при нажатии кнопки Выполнить два раза. Получим решение задачи:
2. Задача теории игр
Теория игр
Вариант 5
Решение
Определим нижнюю цену игры – α. Нижняя цена игры α — это максимальный выигрыш, который мы можем гарантировать себе, в игре против разумного противника, если на протяжении всей игры будем использовать одну и только одну стратегию (такая стратегия называется "чистой").
Найдем в каждой строке платежной матрицы минимальный элемент и запишем его в дополнительный столбец
Затем найдем максимальный элемент дополнительного столбца (отмечен звездочкой), это и будет нижняя цена игры.
Стратегии "A"
Стратегии "B"
Минимумы строк
B1
B2
B3
B4
A1
2
-2
5
-1
-2
A2
5
6
-1
-1
A3
2
-1
2
2
-1
А4
2
2
7
0*
В нашем случае нижняя цена игры равна: α = 0, и для того чтобы гарантировать себе выигрыш не хуже чем 0 мы должны придерживаться стратегии A4
Определим верхнюю цену игры - β
Верхняя цена игры β — это минимальный проигрыш, который может гарантировать себе игрок "В", в игре против разумного противника, если на протяжении всей игры он будет использовать одну и только одну стратегию.
Найдем в каждом столбце платежной матрицы максимальный элемент и запишем его в дополнительную строку снизу
Затем найдем минимальный элемент дополнительной строки (отмечен плюсом), это и будет верхняя цена игры.
Стратегии "A"
Стратегии "B"
Минимумы строк
B1
B2
B3
B4
A1
2
-2
5
-1
-2
A2
5
6
-1
-1
A3
2