Методы оптимальных решений. 9
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
РОССИЙСКАЯ АКАДЕМИЯ НАРОДНОГО ХОЗЯЙСТВА и ГОСУДАРСТВЕННОЙ СЛУЖБЫ
при ПРЕЗИДЕНТЕ РОССИЙСКОЙ ФЕДЕРАЦИИ
СИБИРСКИЙ ИНСТИТУТ УПРАВЛЕНИЯ – ФИЛИАЛ РАНХиГС
ЦЕНТР ПЕРЕПОДГОТОВКИ СПЕЦИАЛИСТОВ
Кафедра ___Информатики и математики_______
Методы оптимальных решений
(дисциплина)
Письменное контрольное задание
для студентов дистанционного обучения
Задача 1. Составьте задачу линейного программирования о минимальных издержках на аренду верблюдов и дромадеров. Сколько потребуется верблюдов и дромадеров, чтобы арендная плата пастуху была минимальной? Решить задачу линейного программирования графическим методом, либо с помощью MicrosoftOfficeExcel (20 баллов).
Караван Марко Поло использует для перевозки сухого инжира из Багдада в Мекку дромадеров (одногорбых верблюдов) и обычных (двугорбых) верблюдов. Верблюд может нести 1000 фунтов груза, а дромадер — 500 фунтов. За время пути верблюд потребляет 3 тюка сена и 100 галлонов воды, а дромадер — 4 тюка сена и 80 галлонов воды. Вдоль пути Марко Поло имеются пункты снабжения, расположенные в оазисах. Общая емкость запасов на этих участках 1600 галлонов воды и 60 тюков сена. Верблюды и дромадеры нанимаются у пастуха около Багдада. Стоимость аренды верблюда составляет 11 монет, а дромадера — 5 монет. Караван должен доставить из Багдада в Мекку не менее 10000 фунтов инжира.
Решение.
Дромадер х1 |
верблюд х2 |
Ограничение | |
Груз, фунтов |
500 |
1000 |
≥10000 |
Сено, тюков |
4 |
3 |
≤ 60 |
Вода, галлонов |
80 |
100 |
≤ 1600 |
Математическая модель задачи:
Целевая функция: - стоимость перевозки
Решим задачу графическим методом.
Область ABC есть область допустимых значений.
Точка области, которую линия уровней целевой функции, двигающая вдоль вектора с, пересекает первой, есть точка А(12;4), то есть для минимизации расходов нужно взять 12 дромадеров и 40 обычных верблюда.
Расходы при этом составят 5*12+11*4 = 104 монет.
Задача 2. Построить экономико-математическую модель и решить транспортную задачу
qj pi |
70 |
30 |
20 |
40 |
90 |
1 |
3 |
4 |
5 |
30 |
5 |
3 |
1 |
2 |
40 |
2 |
1 |
4 |
2 |
Для решения
задачи использовать либо метод потенциалов,
либо свести задачу к задаче линейного
программирования и воспользоваться средствамиMicrosoftOfficeExcel
Решение:
Составим экономико-математическую модель задачи.
Задача заключается в минимизации общих транспортных расходов
При ограничениях
Здесь — количество груза, перевозимого от поставщика к потребителю.
Задача имеет закрытый тип, т.к. равна
Составим опорный план по правилу минимального элемента.
qj
pi |
70 |
30 |
20 |
40 | ||||
90 |
1 |
3 |
4 |
5 | ||||
0 |
0 |
0 |
0 |
|||||
30 |
5 |
3 |
1 |
2 | ||||
0 |
0 |
0 |
0 |
|||||
40 |
2 |
1 |
4 |
2 | ||||
0 |
0 |
0 |
0 |
|||||
Находим незанятую клетку с минимальным тарифом : (1; 1). Помещаем туда меньшее из чисел 70 и 90.
Находим незанятую клетку с минимальным тарифом : (2; 3). Помещаем туда меньшее из чисел 30 и 20.
Находим незанятую клетку с минимальным тарифом : (3; 2). Помещаем туда меньшее из чисел 40 и 30.
Далее заполняем
(1;4) : 90-70 = 20
(2; 4): 30 – 20 = 10
(3;4): 40 – 30 = 10
Получили исходный опорный план
qj
pi |
70 |
30 |
20 |
40 |
остаток | ||||
90 |
1 |
3 |
4 |
5 |
0 | ||||
70 |
20 |
||||||||
30 |
5 |
3 |
1 |
2 |
0 | ||||
20 |
10 |
||||||||
40 |
2 |
1 |
4 |
2 |
0 | ||||
30 |
10 |
||||||||
остаток |
0 |
0 |
0 |
0 |
|||||
Стоимость перевозок составит 70*1+20*5+20*1+10*2+30*1+10*2 = 70+100+20+20+30+20 = 260 (ден.ед.)
Перейдем к построению новых опорных решений, для этого применим метод потенциалов.
Так как 3+4-1=6 и имеем 6 загруженных клеток, план ацикличный.
Пусть ui и vj — потенциалы i – го склада и j-го магазина соответственно.
u1 + v1 = 1
u1 + v4 = 5
u2 + v3 = 1
u2 + v4 = 2
u3 + v2 = 1
u3 + v4= 2
Полагая потенциал u1 = 0, определим остальные потенциалы из соотношения ui + vj = сij, просматривая все занятые клетки. Получим :
u1 = 0
v1 = 1
v4 = 5
v3 = 4
u2 = -3
v2 = 4
u3 = -3
Для свободных клеток определим значения оценок (разностей между прямыми и косвенными тарифами).
S12= c12 – (u1 + v2) = 3-(4) = -1–клетка с отр.оценкой
S13= c13 – (u1 + v3) = 4- 4= 0
S21= c21 – (u2 + v1) = 5 – (-2) = 7
S22= c22 – (u2 + v2) = 3 – 1 = 2
S31= c31 – (u3 + v1) = 2 – (-2) = 4
S33= c33 – (u3 + v3) = 4 – 1 = 3
Имеем одну клетку с отрицательной оценкой: (1;2). Строим для нее цикл.
qj
pi |
70 |
30 |
20 |
40 |
остаток | ||||
90 |
1 |
3 |
4 |
5 |
0 | ||||
70 |
20 |
20-20 =0 |
|||||||
30 |
5 |
3 |
1 |
2 |
0 | ||||
20 |
10 |
||||||||
40 |
2 |
1 |
4 |
2 |
0 | ||||
30-20 =10 |
10+20 =30 |
||||||||
остаток |
0 |
0 |
0 |
0 |
|||||
Стоимость перевозок составит = 70*1+20*3 +20*1+10*2+10*1+30*2 = 70+60+20+20+10+60 = 240 (ден.ед.)
qj
pi |
70 |
30 |
20 |
40 |
остаток | ||||
90 |
1 |
3 |
4 |
5 |
0 | ||||
70 |
20 |
||||||||
30 |
5 |
3 |
1 |
2 |
0 | ||||
20 |
10 |
||||||||
40 |
2 |
1 |
4 |
2 |
0 | ||||
10 |
30 |
||||||||
остаток |
0 |
0 |
0 |
0 |
|||||
Проверим полученный план на оптимальность. Посчитаем потенциалы.
u1 + v1 = 1 u1 + v2 = 3 u2 + v3 = 1 u2 + v4 = 2 u3 + v2 = 1 u3 + v4= 2
Полагая потенциал u1 = 0, получим :
u1 = 0 u2 = -2 u3 = -2 v1 = 1 v2 = 3 v3 = 3 v4 = 4
Для свободных клеток определим значения оценок (разностей между прямыми и косвенными тарифами).
S13= c12 – (u1 + v2) = 4 - 3 = 1
S14= c13 – (u1 + v3) = 5 – 3 = 2
S21= c21 – (u2 + v1) = 5 + 1 = 6
S22= c22 – (u2 + v2) = 3 – 1 = 2
S31= c31 – (u3 + v1) = 2 +1 = 3
S33= c33 – (u3 + v3) = 4 – 1 = 3
Отрицательных оценок нет. Значит, последний план – оптимальный. Стоимость перевозок составит 240 ден. ед.
Задача 3. Используя графический метод,
найти глобальные экстремумы функции
при ограничениях
.
(20 баллов).
Решение:
Построим область, заданную системой неравенств
Многоугольник АВСDE — область допустимых значений.
Целевая функция — значит, линиями уровня будут окружности с центром в точке F (4; 3).
Минимальное значение целевая функция имеет в точке F:
Максимальное значение целевая функция достигает в точке C.
Точка C есть точка пересечения прямых Ряд2 и Ряд3. Найдем ее координаты.
Решив эту систему уравнений, получим:
Значит, С (13; 10,5)
Ответ. Глобальный минимум целевой функции достигается в точке F (4; 3);
глобальный максимум — в точке С (13; 10,5).
Задача 5. Годовой абонемент в яхт-клубе стоит 100 ден.ед. Цена одной яхты равна 170 ден.ед. Аренда помещения и хранение яхт (от одной до семи штук) обходится в 530 ден.ед. Сколько стоит закупить яхт из расчета одна яхта на пять человек, если предполагаемое число членов клуба колеблется от 10 до 25 человек. Ответ обоснуйте, используя критерии Байеса, Вальда, Сэвиджа и Гурвица(20 баллов).
Решение:
Проанализируем для начала допустимые альтернативы решений, используя для этого информацию о возможных состояниях внешней среды. Легко заметить, что имеет смысл рассматривать количество приобретаемых яхт в диапазоне от двух до пяти (чтобы обслужить от 10 до 25 человек), т. е. 4 варианта. Перебор вариантов количества потенциальных яхтсменов ограничим также четырьмя вариантами: 10, 15, 20 и 25 человек (если полученные выводы для смежных вариантов будут существенно различаться, проведем дополнительный, уточняющий расчет).
количество яхт
количество посетителей
Составим платежную матрицу игры. Рассчитаем ее элементы. Например, элемент рассчитаем при условии, что имеется 2 яхты и 10 членов клуба,
Аналогичным образом рассчитаем остальные элементы матрицы и получим результат
Результаты расчетов будем заносить в таблицу:
S1 |
S2 |
S3 |
S4 |
Лапласа Байеса |
Вальда |
Сэвиджа |
Гурвица | |
x1 |
130 |
130 |
130 |
130 |
130 |
130 |
990 |
130 |
x2 |
-40 |
460 |
460 |
460 |
335 |
-40 |
660 |
360 |
x3 |
-210 |
290 |
790 |
790 |
415 |
-210 |
340 |
590 |
x4 |
-380 |
120 |
620 |
1120 |
370 |
-380 |
510 |
820 |
Выбранная по критерию стратегия |
X3 |
X1 |
X3 |
X4 | ||||
1. Критерий недостаточного
Находим среднее значение элементов каждой строки по формуле
Найденные значения заносим в соответствующий столбец и выбираем максимальное , значит оптимальной по данному критерию является стратегия x3.
2. Максиминный критерий Вальда
В каждой строке находим минимальный элемент: и выбираем максимальное , значит оптимальной по данному критерию является стратегия x1.
3. Критерий минимаксного риска Сэвиджа
Рассчитаем матрицу рисков. В каждом столбце находим максимальный элемент bj.
S1 |
S2 |
S3 |
S4 | |
x1 |
130 |
130 |
130 |
130 |
x2 |
-40 |
460 |
460 |
460 |
x3 |
-210 |
290 |
790 |
790 |
x4 |
-380 |
120 |
620 |
1120 |
bj |
130 |
460 |
790 |
1120 |
Заполним матрицу рисков по столбцам. Для этого вычитаем из bj все остальные элементы столбца, результаты записываем на соответствующих местах (в каждом столбце на месте максимального будет 0).
S1 |
S2 |
S3 |
S4 | |
А1 |
0 |
330 |
660 |
990 |
А2 |
170 |
0 |
330 |
660 |
А3 |
340 |
170 |
0 |
330 |
A4 |
510 |
340 |
170 |
0 |
В каждой строке матрицы рисков находим максимальный элемент: и выбираем минимальное значение , значит, оптимальной по данному критерию является стратегия x3.
4. Критерий пессимизма-оптимизма Гурвица
Для каждой строки рассчитываем значение критерия по формуле:
. Пусть l=0,2.
S1 |
S2 |
S3 |
S4 |
|
| |
А1 |
130 |
130 |
130 |
130 |
130 |
130 |
А2 |
-40 |
460 |
460 |
460 |
-40 |
460 |
А3 |
-210 |
290 |
790 |
790 |
-210 |
790 |
A4 |
-380 |
120 |
620 |
1120 |
-380 |
1120 |
Выбираем максимальное , значит оптимальной по данному критерию является стратегия x4.
Список использованной литературы
- Осипов, А.Л. Методы оптимальных решений : учеб. пособие / А.Л. Осипов, Е.А. Рапоцевич; РАНХиГС, Сиб.ин-т упр. — Новосибирск : Изд-во СибАГС, 2013.
- Данко, П.Е. Высшая математика в упражнениях и задачах. В 2 ч. Ч. 1: Учеб. пособие для вузов / П.Е. Данко, А.Г. Попов, Т.Я. Кожевникова. — 6-е изд. — М.: ООО «Издательский дом «ОНИКС 21 век»:ООО «Издательство «Мир и образование», 2003.
