Автор работы: Пользователь скрыл имя, 16 Декабря 2012 в 20:32, контрольная работа
Бомбить аэродром отправляются 3 самолета, 2 из них – бомбардировщики. Противник может выстрелить по двум самолетам. При выстреле по самолету он поражает летящий первым с вероятностью 0,4, летящий вторым или третьим – с вероятностью 0,5. Аэродром разбомблен, если хотя бы один бомбардировщик уцелел. Сформулировать задачу как задачу теории игр. Найдите решение или укажите алгоритм нахождения решения.
Оптимальный план можно записать так:
x3 = 14.13
x1 = 17.93
x4 = 12.1
x2 = 8.7
x9 = 6493.84
F(X) = 830*17.93 + 835*8.7 + 360*14.13 + 450*12.1 = 32679.35
Таким образом, оптимальный объем капиталовложений в строительство квартир составит 32679.35 ден.единиц.
|
1 |
2 |
3 |
||
|
1 |
15 |
11 |
5 |
17 |
2 |
2 |
0 |
11 |
18 |
3 |
2 |
9 |
30 |
5 |
4 |
21 |
15 |
1). Найти начальный план методами: а) северо-западного угла и б) наименьшей стоимости.
2). Проверить, является
ли начальное решение,
Математическая модель транспортной задачи:
F = ∑∑cijxij, (1)
при условиях:
∑xij = ai, i = 1,2,…, m, (2)
∑xij = bj, j = 1,2,…, n, (3)
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов
1 |
2 |
3 |
||
|
1 |
15 |
11 |
5 |
17 |
2 |
2 |
0 |
11 |
18 |
3 |
2 |
9 |
30 |
5 |
4 |
21 |
15 |
Проверим необходимое
и достаточное условие
∑a = 17 + 18 + 5 = 40
∑b = 4 + 21 + 15 = 40
Занесем исходные данные в распределительную таблицу.
1 |
2 |
3 |
||
|
1 |
15 |
11 |
5 |
17 |
2 |
2 |
0 |
11 |
18 |
3 |
2 |
9 |
30 |
5 |
4 |
21 |
15 |
а) Используя метод северо-западного угла, построим первый опорный план транспортной задачи.
1 |
2 |
3 |
||
|
1 |
15[4] |
11[13] |
5 |
17 |
2 |
2 |
0[8] |
11[10] |
18 |
3 |
2 |
9 |
30[5] |
5 |
4 |
21 |
15 |
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность удовлетворена, а план соответствует системе ограничений транспортной задачи.
2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 5. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=15 |
v2=11 |
v3=22 | |
u1=0 |
15[4] |
11[13] |
5 |
u2=-11 |
2 |
0[8] |
11[10] |
u3=8 |
2 |
9 |
30[5] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (3;1): 2
Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
||
|
1 |
15[4][-] |
11[13][+] |
5 |
17 |
2 |
2 |
0[8][-] |
11[10][+] |
18 |
3 |
2[+] |
9 |
30[5][-] |
5 |
4 |
21 |
15 |
Цикл приведен в таблице (3,1; 3,3; 2,3; 2,2; 1,2; 1,1; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 4. Прибавляем 4 к объемам грузов, стоящих в плюсовых клетках и вычитаем 4 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
||
|
1 |
15 |
11[17] |
5 |
17 |
2 |
2 |
0[4] |
11[14] |
18 |
3 |
2[4] |
9 |
30[1] |
5 |
4 |
21 |
15 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=-6 |
v2=11 |
v3=22 | |
u1=0 |
15 |
11[17] |
5 |
u2=-11 |
2 |
0[4] |
11[14] |
u3=8 |
2[4] |
9 |
30[1] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (1;3): 5
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
||
|
1 |
15 |
11[17][-] |
5[+] |
17 |
2 |
2 |
0[4][+] |
11[14][-] |
18 |
3 |
2[4] |
9 |
30[1] |
5 |
4 |
21 |
15 |
Цикл приведен в таблице (1,3; 1,2; 2,2; 2,3; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 3) = 14. Прибавляем 14 к объемам грузов, стоящих в плюсовых клетках и вычитаем 14 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1 |
2 |
3 |
||
|
1 |
15 |
11[3] |
5[14] |
17 |
2 |
2 |
0[18] |
11 |
18 |
3 |
2[4] |
9 |
30[1] |
5 |
4 |
21 |
15 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.
v1=-23 |
v2=11 |
v3=5 | |
u1=0 |
15 |
11[3] |
5[14] |
u2=-11 |
2 |
0[18] |
11 |
u3=25 |
2[4] |
9 |
30[1] |
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vi > cij
Выбираем максимальную оценку свободной клетки (3;2): 9
Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 |
2 |
3 |
||
|
1 |
15 |
11[3][-] |
5[14][+] |
17 |
2 |
2 |
0[18] |
11 |
18 |
3 |
2[4] |
9[+] |
30[1][-] |
5 |
4 |
21 |
15 |
Цикл приведен в таблице (3,2; 3,3; 1,3; 1,2; ).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 1. Прибавляем 1 к объемам грузов, стоящих в плюсовых клетках и вычитаем 1 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
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 |
Проверим оптимальность опорного плана. Найдем предварительные потенциалы 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 |