Автор работы: Пользователь скрыл имя, 16 Декабря 2012 в 20:32, контрольная работа
Бомбить аэродром отправляются 3 самолета, 2 из них – бомбардировщики. Противник может выстрелить по двум самолетам. При выстреле по самолету он поражает летящий первым с вероятностью 0,4, летящий вторым или третьим – с вероятностью 0,5. Аэродром разбомблен, если хотя бы один бомбардировщик уцелел. Сформулировать задачу как задачу теории игр. Найдите решение или укажите алгоритм нахождения решения.
Разрешающий элемент равен (60) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
min |
x5 |
400 |
-2 |
0 |
18 |
15 |
1 |
0 |
0 |
-0.2 |
0 |
26.67 |
x6 |
1000 |
40 |
0 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
- |
x7 |
455.56 |
-13.33 |
0 |
-2.22 |
60 |
0 |
0 |
1 |
-0.22 |
0 |
7.59 |
x2 |
22.22 |
0.67 |
1 |
0.11 |
0 |
0 |
0 |
0 |
0.0111 |
0 |
- |
x9 |
6777.78 |
13.33 |
0 |
-1.11 |
5 |
0 |
0 |
0 |
-0.11 |
1 |
1355.56 |
F(X2) |
18555.56 |
-273.33 |
0 |
-267.22 |
-450 |
0 |
0 |
0 |
9.28 |
0 |
0 |
После преобразований получаем новую таблицу:
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
|
x5 |
286.11 |
1.33 |
0 |
18.56 |
0 |
1 |
0 |
-0.25 |
-0.14 |
0 |
x6 |
1000 |
40 |
0 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
x4 |
7.59 |
-0.22 |
0 |
-0.037 |
1 |
0 |
0 |
0.0167 |
-0.0037 |
0 |
x2 |
22.22 |
0.67 |
1 |
0.11 |
0 |
0 |
0 |
0 |
0.0111 |
0 |
x9 |
6739.81 |
14.44 |
0 |
-0.93 |
0 |
0 |
0 |
-0.0833 |
-0.0926 |
1 |
F(X2) |
21972.22 |
-373.33 |
0 |
-283.89 |
0 |
0 |
0 |
7.5 |
7.61 |
0 |
Итерация №2.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (40) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
min |
x5 |
286.11 |
1.33 |
0 |
18.56 |
0 |
1 |
0 |
-0.25 |
-0.14 |
0 |
214.58 |
x6 |
1000 |
40 |
0 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
25 |
x4 |
7.59 |
-0.22 |
0 |
-0.037 |
1 |
0 |
0 |
0.0167 |
-0.0037 |
0 |
- |
x2 |
22.22 |
0.67 |
1 |
0.11 |
0 |
0 |
0 |
0 |
0.0111 |
0 |
33.33 |
x9 |
6739.81 |
14.44 |
0 |
-0.93 |
0 |
0 |
0 |
-0.0833 |
-0.0926 |
1 |
466.6 |
F(X3) |
21972.22 |
-373.33 |
0 |
-283.89 |
0 |
0 |
0 |
7.5 |
7.61 |
0 |
0 |
После преобразований получаем новую таблицу:
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
|
x5 |
252.78 |
0 |
0 |
17.89 |
0 |
1 |
-0.0333 |
-0.25 |
-0.14 |
0 |
x1 |
25 |
1 |
0 |
0.5 |
0 |
0 |
0.025 |
0 |
0 |
0 |
x4 |
13.15 |
0 |
0 |
0.0741 |
1 |
0 |
0.00556 |
0.0167 |
-0.0037 |
0 |
x2 |
5.56 |
0 |
1 |
-0.22 |
0 |
0 |
-0.0167 |
0 |
0.0111 |
0 |
x9 |
6378.7 |
0 |
0 |
-8.15 |
0 |
0 |
-0.36 |
-0.0833 |
-0.0926 |
1 |
F(X3) |
31305.56 |
0 |
0 |
-97.22 |
0 |
0 |
9.33 |
7.5 |
7.61 |
0 |
Итерация №3.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее:
Следовательно, 1-ая строка является ведущей.
Разрешающий элемент равен (17.89) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
min |
x5 |
252.78 |
0 |
0 |
17.89 |
0 |
1 |
-0.0333 |
-0.25 |
-0.14 |
0 |
14.13 |
x1 |
25 |
1 |
0 |
0.5 |
0 |
0 |
0.025 |
0 |
0 |
0 |
50 |
x4 |
13.15 |
0 |
0 |
0.0741 |
1 |
0 |
0.00556 |
0.0167 |
-0.0037 |
0 |
177.5 |
x2 |
5.56 |
0 |
1 |
-0.22 |
0 |
0 |
-0.0167 |
0 |
0.0111 |
0 |
- |
x9 |
6378.7 |
0 |
0 |
-8.15 |
0 |
0 |
-0.36 |
-0.0833 |
-0.0926 |
1 |
- |
F(X4) |
31305.56 |
0 |
0 |
-97.22 |
0 |
0 |
9.33 |
7.5 |
7.61 |
0 |
0 |
После преобразований получаем новую таблицу:
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
|
x3 |
14.13 |
0 |
0 |
1 |
0 |
0.0559 |
-0.00186 |
-0.014 |
-0.00807 |
0 |
x1 |
17.93 |
1 |
0 |
0 |
0 |
-0.028 |
0.0259 |
0.00699 |
0.00404 |
0 |
x4 |
12.1 |
0 |
0 |
0 |
1 |
-0.00414 |
0.00569 |
0.0177 |
-0.00311 |
0 |
x2 |
8.7 |
0 |
1 |
0 |
0 |
0.0124 |
-0.0171 |
-0.00311 |
0.00932 |
0 |
x9 |
6493.84 |
0 |
0 |
0 |
0 |
0.46 |
-0.38 |
-0.2 |
-0.16 |
1 |
F(X4) |
32679.35 |
0 |
0 |
0 |
0 |
5.43 |
9.15 |
6.14 |
6.83 |
0 |
Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план
Окончательный вариант симплекс-таблицы:
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
|
x3 |
14.13 |
0 |
0 |
1 |
0 |
0.0559 |
-0.00186 |
-0.014 |
-0.00807 |
0 |
x1 |
17.93 |
1 |
0 |
0 |
0 |
-0.028 |
0.0259 |
0.00699 |
0.00404 |
0 |
x4 |
12.1 |
0 |
0 |
0 |
1 |
-0.00414 |
0.00569 |
0.0177 |
-0.00311 |
0 |
x2 |
8.7 |
0 |
1 |
0 |
0 |
0.0124 |
-0.0171 |
-0.00311 |
0.00932 |
0 |
x9 |
6493.84 |
0 |
0 |
0 |
0 |
0.46 |
-0.38 |
-0.2 |
-0.16 |
1 |
F(X5) |
32679.35 |
0 |
0 |
0 |
0 |
5.43 |
9.15 |
6.14 |
6.83 |
0 |