Методы оптимальных решений

Контрольная по предмету Методы оптимальных решений ...

1. Составьте задачу линейного программирования о минимальных издержках на аренду верблюдов и дромадеров. Сколько потребуется верблюдов и дромадеров, чтобы арендная плата пастуху была минимальной?Решить задачу линейного программирования графическим методом, либо с помощью MicrosoftOfficeExcel (20 баллов).
Караван Марко Поло использует для перевозки сухого инжира из Багдада в Мекку дромадеров (одногорбых верблюдов) и обычных (двугорбых) верблюдов. Верблюд может нести 1000 фунтов груза, а дромадер — 500 фунтов. За время пути верблюд потребляет 3 тюка сена и 100 галлонов воды, а дромадер — 4 тюка сена и 80 галлонов воды. Вдоль пути Марко Поло имеются пункты снабжения, расположенные в оазисах. Общая емкость запасов на этих участках 1600 галлонов воды и 60 тюков сена. Верблюды и дромадеры нанимаются у пастуха около Багдада. Стоимость аренды верблюда составляет 11 монет, а дромадера — 5 монет. Караван должен доставить из Багдада в Мекку не менее 10000 фунтов инжира.
2. Построить экономико-математическую модель и решить транспортную задачу
qj
pi 70 30 20 40
90 1 3 4 5
30 5 3 1 2
40 2 1 4 2
Для решения задачи использовать либо метод потенциалов, либо свести задачу к задаче линейного программирования и воспользоваться средствамиMicrosoftOfficeExcel(20 баллов).
3. Используя графический метод, найти глобальные экстремумы функции
при ограничениях
.
(20 баллов).
4. У игрока А две стратегии. У игрока В – четыре. Найти оптимальные стратегии игроков для матрицы игры . Решение в смешанных стратегиях найти либо графическим методом, либо свести задачу к задаче линейного программированияи воспользоваться средствамиMicrosoftOfficeExcel(20 баллов).
5. Годовой абонемент в яхт-клубе стоит 100 ден.ед. Цена одной яхты равна 170 ден.ед. Аренда помещения и хранение яхт (от одной до семи штук) обходится в 530 ден.ед. Сколько стоит закупить яхт из расчета одна яхта на пять человек, если предполагаемое число членов клуба колеблется от 10 до 25 человек. Ответ обоснуйте, используя критерии Байеса, Вальда, Сэвиджа и Гурвица(20 баллов).

Контрольная по предмету Методы оптимальных решений

2[10][+]
40
Потребности
70
30
20
40
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 4) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
1
2
3
4
Запасы
1
1[70]
3[20]
4
5
90
2
5
3
1[20]
2[10]
30
3
2
1[10]
4
2[30]
40
Потребности
70
30
20
40
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 1; 0 + v1 = 1; v1 = 1
u1 + v2 = 3; 0 + v2 = 3; v2 = 3
u3 + v2 = 1; 3 + u3 = 1; u3 = -2
u3 + v4 = 2; -2 + v4 = 2; v4 = 4
u2 + v4 = 2; 4 + u2 = 2; u2 = -2
u2 + v3 = 1; -2 + v3 = 1; v3 = 3
v1=1
v2=3
v3=3
v4=4
u1=0
1[70]
3[20]
4
5
u2=-2
5
3
1[20]
2[10]
u3=-2
2
1[10]
4
2[30]
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Минимальные затраты составят:
F(x) = 1*70 + 3*20 + 1*20 + 2*10 + 1*10 + 2*30 = 240
Анализ оптимального плана.
Из 1-го склада необходимо груз направить в 1-й магазин (70), в 2-й магазин (20)
Из 2-го склада необходимо груз направить в 3-й магазин (20), в 4-й магазин (10)
Из 3-го склада необходимо груз направить в 2-й магазин (10), в 4-й магазин (30)
3. Используя графический метод, найти глобальные экстремумы функции
при ограничениях
.
(20 баллов).
Решение:
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Максимальное значене будет в точке
3х1-2х2=18
-х1+2х2=8
x2 = 21/2
x1 = 13
минимальное в точке (4,3)
глобальный минимум = 0
глобальный максимум = (13-4)2+(10,5 – 3)2= 137,25
4. У игрока А две стратегии. У игрока В – четыре. Найти оптимальные стратегии игроков для матрицы игры. Решение в смешанных стратегиях найти либо графическим методом, либо свести задачу к задаче линейного программированияи воспользоваться средствами MicrosoftOfficeExcel(20 баллов).
Решение:
Рассмотрим игру двух лиц, интересы которых противоположны. Такие игры называют антагонистическими играми двух лиц. В этом случае выигрыш одного игрока равен проигрышу второго, и можно описать только одного из игроков.
Предполагается, что каждый игрок может выбрать только одно из конечного множества своих действий. Выбор действия называют выбором стратегии игрока.
Если каждый из игроков выбрал свою стратегию, то эту пару стратегий называют ситуацией игры. Следует заметить, каждый игрок знает, какую стратегию выбрал его противник, т.е. имеет полную информацию о результате выбора противника.
Чистой стратегией игрока I является выбор одной из n строк матрицы выигрышей А, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы.
1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.
Игроки
B1
B2
a = min(Ai)
A1
2
4
2
A2
2
1
1
A3
1
6
1
A4
4
b = max(Bi)
4
6
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 2, которая указывает на максимальную чистую стратегию A1.
Верхняя цена игры b = min(bj) = 4.
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 2 ≤ y ≤ 4. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии).
Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получитьмаксимальный средний выигрыш.
Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I.
3. Находим решение игры в смешанных стратегиях.
Решим задачу геометрическим методом, который включает в себя следующие этапы:
1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии B1, правый - стратегии B2 (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S1 = (p1,p2).
2. На левой оси ординат откладываются выигрыши стратегии B1. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии B2.
Решение игры (m x 2) проводим с позиции игрока B, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет.
Максиминной оптимальной стратегии игрока B соответствует точка N, лежащая на пересечении прямых A1A1 и A3A3, для которых можно записать следующую систему уравнений:
y = 2 + (4 - 2)q2
y = 1 + (6 - 1)q2
Откуда
q1 = 2/3
q2 = 1/3
Цена игры, y = 8/3
Теперь можно найти минимаксную стратегию игрока A, записав соответствующую систему уравнений, исключив стратегию A2,A4, которая дает явно больший проигрыш игроку A, и, следовательно, p2 = 0,p4 = 0.
2p1+p3 = y
4p1+6p3 = y
p1+p3 = 1
или
2p1+p3 = 8/3
4p1+6p3 = 8/3
p1+p3 = 1
Решая эту систему, находим:
p1 = 5/3.
p3 = -2/3.
Ответ: 
Цена игры: y = 8/3, векторы стратегии игроков: 
P(5/3, 0, -2/3, 0), Q(2/3, 1/3)
4. Проверим правильность решения игры с помощью критерия оптимальности стратегии.
∑aijqj ≤ v
∑aijpi ≥ v
M(P1;Q) = (2•2/3) + (4•1/3) = 2.667 = v
M(P2;Q) = (2•2/3) + (1•1/3) = 1.667 ≤ v
M(P3;Q) = (1•2/3) + (6•1/3) = 2.667 = v
M(P4;Q) = (4•2/3) + (0•1/3) = 2.667 = v
M(P;Q1) = (2•12/3) + (2•0) + (1•-2/3) + (4•0) = 2.667 = v
M(P;Q2) = (4•12/3) + (1•0) + (6•-2/3) + (0•0) = 2.667 = v
Все неравенства выполняются как равенства или строгие неравенства, следовательно, решение игры найдено верно.
5. Годовой абонемент в яхт-клубе стоит 100 ден.ед. Цена одной яхты равна 170 ден.ед. Аренда помещения и хранение яхт (от одной до семи штук) обходится в 530 ден.ед. Сколько стоит закупить яхт из расчета одна яхта на пять человек, если предполагаемое число членов клуба колеблется от 10 до 25 человек. Ответ обоснуйте, используя критерии Байеса, Вальда, Сэвиджа и Гурвица(20 баллов).
Решение:
Поскольку по условию задачи известно, что предполагаемое число членов клуба колеблется от 10 до 25 человек, примем следующий вектор возможных исходов:
Т.к. известно, что покупать яхты необходимо из расчета одна яхта на 5 человек, то для возможных исходов количество закупаемых яхт (возможные решения) будет равны соответственно:
Составим таблицу, в которой отразим прибыль при каждом исходе и соответствующем варианте. Прибыль представляет собой разность между выручкой от продажи годовых абонементов в яхт-клуб и расходами (стоимость яхт, затраты на аренду помещения и хранение яхт).
Пусть количество членов клуба составляет 10 человек, количество закупленных яхт составляет 2 шт., тогда можно получить прибыль от использования этих двух яхт:
ден. ед.
При этом будут иметь место следующие расходы:
Стоимость яхт:
ден. ед.
Затраты на аренду и хранение яхт:
ден. ед.
Таким образом, чистый доход составит:
ден. ед.
Пусть количество членов клуба составляет 10 человек, количество закупленных яхт составляет 3 шт., тогда можно получить прибыль от использования только двух яхт, одна яхта не будет использоваться, тогда чистый доход составит:
ден. ед.
Пусть количество членов клуба составляет 15 человек, количество закупленных яхт составляет 2 шт., тогда можно получить прибыль от использования только двух яхт, 5 человек не будут иметь возможности купить абонемент, что также приведет к убыткам (недополученной прибыли), чистый доход составит:
ден. ед.
где ден. ед. – недополученный доход.
И т.д.
Результаты расчетов представлены в таблице (матрица доходов) – см. ниже.
Матрица доходов
Возможные исходы (число членов клуба)
возможные решения (число закупленных яхт)
2
3
4
5
10
130
-40
-210
-380
15
130
460
290
120
20
130
460
790
620
25
130
460