Методы оптимизации
Контрольная работа, 16 Декабря 2012, автор: пользователь скрыл имя
Краткое описание
Бомбить аэродром отправляются 3 самолета, 2 из них – бомбардировщики. Противник может выстрелить по двум самолетам. При выстреле по самолету он поражает летящий первым с вероятностью 0,4, летящий вторым или третьим – с вероятностью 0,5. Аэродром разбомблен, если хотя бы один бомбардировщик уцелел. Сформулировать задачу как задачу теории игр. Найдите решение или укажите алгоритм нахождения решения.
Вложенные файлы: 1 файл
Мет.опт.реш.Вариант 1.doc
— 601.50 Кб (Скачать файл)
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.
Минимальные затраты составят:
F(x) = 11*2 + 5*15 + 0*18 + 2*4 + 9*1 = 114
б) решим задачу методом наименьшей стоимости.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной
задачи.
1 |
2 |
3 |
||
|
1 |
15 |
11[2] |
5[15] |
17 |
2 |
2 |
0[18] |
11 |
18 |
3 |
2[4] |
9[1] |
30 |
5 |
4 |
21 |
15 |
В результате получен первый опорный
план, который является допустимым,
так как все грузы из баз вывезены, потребность
удовлетворена, а план соответствует системе
ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы,
их 5, а должно быть m + n - 1 = 5. Следовательно,
опорный план является невырожденным.
Значение целевой функции для этого опорного
плана равно:
Проверим оптимальность опорного плана.
Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых
ui + vi = cij, полагая, что u1 = 0.
v1=4 |
v2=11 |
v3=5 | |
u1=0 |
15 |
11[2] |
5[15] |
u2=-11 |
2 |
0[18] |
11 |
u3=-2 |
2[4] |
9[1] |
30 |
Опорный план является оптимальным, так
все оценки свободных клеток удовлетворяют
условию ui + vi <= cij.
Минимальные затраты составят:
F(x) = 11*2 + 5*15 + 0*18 + 2*4 + 9*1 = 114