Автор работы: Пользователь скрыл имя, 16 Декабря 2012 в 20:32, контрольная работа
Бомбить аэродром отправляются 3 самолета, 2 из них – бомбардировщики. Противник может выстрелить по двум самолетам. При выстреле по самолету он поражает летящий первым с вероятностью 0,4, летящий вторым или третьим – с вероятностью 0,5. Аэродром разбомблен, если хотя бы один бомбардировщик уцелел. Сформулировать задачу как задачу теории игр. Найдите решение или укажите алгоритм нахождения решения.
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию 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