Автор работы: Пользователь скрыл имя, 16 Декабря 2012 в 20:32, контрольная работа
Бомбить аэродром отправляются 3 самолета, 2 из них – бомбардировщики. Противник может выстрелить по двум самолетам. При выстреле по самолету он поражает летящий первым с вероятностью 0,4, летящий вторым или третьим – с вероятностью 0,5. Аэродром разбомблен, если хотя бы один бомбардировщик уцелел. Сформулировать задачу как задачу теории игр. Найдите решение или укажите алгоритм нахождения решения.
Таблица 3
Стратегии "B" | |||||
Стратегии "A" |
B1 |
B2 |
B3 |
B4 |
Минимумы строк |
A1 |
2 |
0 |
0 |
-2 |
-2 |
A2 |
6 |
2 |
0*+ |
0*+ |
0* |
|
A3 |
4 |
7 |
0 |
-1 |
-1 |
A4 |
0 |
7 |
-1 |
-2 |
-2 |
Максимумы столбцов |
6 |
7 |
0+ |
0+ |
|
Еще одной особенностью данной игры является то, что она имеет не одну, а 2 седловые точки, которые определяют соответственно 2 решения (пар оптимальных стратегий). Причем все эти решения приводят нас к одной цене игры.
Ответ:
Нижняя цена игры, верхняя цена игры и чистая цена игры: α = β = v = 0;
Оптимальные стратегии (2 пары): A2B3; A2B4;
Показатели |
Д-1 |
Д-2 |
Д-3 |
Д-4 |
Однокомнатная квартира |
10 |
18 |
20 |
15 |
Двухкомнатная смежная |
40 |
- |
20 |
- |
Двухкомнатная несмежная |
- |
20 |
- |
60 |
Трехкомнатная квартира |
60 |
90 |
10 |
- |
Четырехкомнатная квартира |
20 |
10 |
- |
5 |
Себестоимость (тыс.руб.) |
830 |
835 |
360 |
450 |
Годовой план ввода жилой
площади составляет соответственно
800, 1000, 900, 2000 и 7000 квартир указанных
типов. Исходя из необходимости выполнения
плана ввода квартир и
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 830x1+835x2+360x3+450x4 при следующих условиях-ограничений.
10x1+18x2+20x3+15x4<=800
40x1+20x3<=1000
20x2+60x4<=900
60x1+90x2+10x3<=2000
20x1+10x2+5x4<=7000
10x1 + 18x2 + 20x3 + 15x4 + 1x5 + 0x6 + 0x7 + 0x8 + 0x9 = 800
40x1 + 0x2 + 20x3 + 0x4 + 0x5 + 1x6 + 0x7 + 0x8 + 0x9 = 1000
0x1 + 20x2 + 0x3 + 60x4 + 0x5 + 0x6 + 1x7 + 0x8 + 0x9 = 900
60x1 + 90x2 + 10x3 + 0x4 + 0x5 + 0x6 + 0x7 + 1x8 + 0x9 = 2000
20x1 + 10x2 + 0x3 + 5x4 + 0x5 + 0x6 + 0x7 + 0x8 + 1x9 = 7000
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
10 |
18 |
20 |
15 |
1 |
0 |
0 |
0 |
0 |
40 |
0 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
20 |
0 |
60 |
0 |
0 |
1 |
0 |
0 |
60 |
90 |
10 |
0 |
0 |
0 |
0 |
1 |
0 |
20 |
10 |
0 |
5 |
0 |
0 |
0 |
0 |
1 |
Решим систему уравнений относительно базисных переменных:
x5, x6, x7, x8, x9,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,800,1000,900,2000,
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
|
x5 |
800 |
10 |
18 |
20 |
15 |
1 |
0 |
0 |
0 |
0 |
x6 |
1000 |
40 |
0 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
x7 |
900 |
0 |
20 |
0 |
60 |
0 |
0 |
1 |
0 |
0 |
x8 |
2000 |
60 |
90 |
10 |
0 |
0 |
0 |
0 |
1 |
0 |
x9 |
7000 |
20 |
10 |
0 |
5 |
0 |
0 |
0 |
0 |
1 |
F(X0) |
0 |
-830 |
-835 |
-360 |
-450 |
0 |
0 |
0 |
0 |
0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
Следовательно, 4-ая строка является ведущей.
Разрешающий элемент равен (90) и находится на пересечении ведущего столбца и ведущей строки.
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
min |
x5 |
800 |
10 |
18 |
20 |
15 |
1 |
0 |
0 |
0 |
0 |
44.44 |
x6 |
1000 |
40 |
0 |
20 |
0 |
0 |
1 |
0 |
0 |
0 |
- |
x7 |
900 |
0 |
20 |
0 |
60 |
0 |
0 |
1 |
0 |
0 |
45 |
x8 |
2000 |
60 |
90 |
10 |
0 |
0 |
0 |
0 |
1 |
0 |
22.22 |
x9 |
7000 |
20 |
10 |
0 |
5 |
0 |
0 |
0 |
0 |
1 |
700 |
F(X1) |
0 |
-830 |
-835 |
-360 |
-450 |
0 |
0 |
0 |
0 |
0 |
0 |
После преобразований получаем новую таблицу:
Базис |
В |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
|
x5 |
400 |
-2 |
0 |
18 |
15 |
1 |
0 |
0 |
-0.2 |
0 |
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 |
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 |
F(X1) |
18555.56 |
-273.33 |
0 |
-267.22 |
-450 |
0 |
0 |
0 |
9.28 |
0 |
Итерация №1.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
В индексной строке F(x) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной x4, так как это наибольший коэффициент по модулю.
Вычислим значения Di по строкам как частное от деления: bi / ai4
и из них выберем наименьшее:
Следовательно, 3-ая строка является ведущей.