Набор задач N 9
Построить математическую модель следующей задачи о банковских кредитах.
Банк собирается выдать кредитов на сумму, не превышающую 12 млн. $.
Типы кредитов и информация о доходах по ним и рисках приведены в таблице.
|
Тип кредита |
Доля дохода |
Доля невозврата |
|
Личный |
0.140 |
0.10 |
|
Покупка авто |
0.130 |
0.07 |
|
Жилье |
0.120 |
0.03 |
|
С/х |
0.125 |
0.05 |
|
Бизнес |
0.100 |
0.02 |
Банк обязан разместить > 40% всех кредитов на нужды с/х и бизнеса, и > 50% от кредитов на личные нужды, авто и жилье - на жилье.
Общая доля невозврата по всем кредитам не должна превосходить 0.08.
Необходимо определить суммы кредитов по указанным видам так, чтобы максимизировать доход.
Найти множество Парето следующей двухкритериальной задачи.
при условии x{1, 2, 3,4, 5, 6, 7}.
Значения функций заданы таблицей.
|
x |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
F1(x) |
1 |
2 |
3 |
2 |
3 |
4 |
3 |
|
F2(x) |
6 |
6 |
6 |
5 |
5 |
5 |
3 |
Геометрически решить задачу линейного программирования: Перейти к двойственной и решить задачу линейного программирования: Решить задачу линейного программирования симплекс-методом
Решить транспортную задачу. Транспортная таблица имеет вид:
|
Ai / Bj |
B1 |
B2 |
B3 |
Запасы ai |
|
A1 |
3 |
2 |
4 |
100 |
|
A2 |
9 |
0 |
1 |
150 |
|
A3 |
2 |
7 |
5 |
80 |
|
Заявки bj |
80 |
140 |
110 |
|
Найти эйлеров цикл в графе. Вершина 5 отсутствует.
Найти кратчайшие пути из вершины 1 во все остальные вершины графа. Граф приведен в задаче 7. Дуги и их веса заданы в таблице.
Вес дуги (2,8) равен сумме дуг (2,5) и (5,8), а вес дуги (3,7) равен сумме весов дуг (3,5) и (5,7).
|
Дуги |
1,2 |
1,3 |
2,4 |
2,7 |
2,5 |
3,5 |
3,8 |
|
Веса |
3 |
1 |
4 |
2 |
5 |
3 |
2 |
|
Дуги |
3,6 |
4,7 |
5,7 |
5,8 |
6,8 |
7,9 |
8,9 |
|
Веса |
4 |
5 |
1 |
3 |
2 |
4 |
2 |
Решить задачу коммивояжера для 5 городов. Матрица расстояний (стоимостей переезда) представлена в виде\
|
|
1 |
2 |
3 |
4 |
5 |
|
1 |
2 |
4 |
10 |
4 |
|
|
2 |
1 |
15 |
6 |
4 |
|
|
3 |
6 |
3 |
14 |
2 |
|
|
4 |
5 |
21 |
10 |
5 |
|
|
5 |
14 |
3 |
4 |
7 |
Найти длину критического пути (длительность выполнения проекта) в сети, где дуги представляют собой работы проекта, начало и конец дуги - начало и конец работы, вес дуги - длительность работы.
Вычислить наиболее ранние и наиболее поздние моменты начала работ. Вершины s и t сопоставлены началу и завершению проекта соответственно.
Длительности выполнения работ (веса дуг) (2,7), (3,8), (8,5) равны 1, дуги (5,7) равна целой части от деления номера набора задач (N) на 15 (=), остальные равны 2.
Решить антагонистическую матричную игру.
Выигрыш 1 игрока в зависимости от выбранных стратегий игроков 1 и 2 задан следующей матрицей.
|
Ai \ Πj |
1 |
2 |
3 |
4 |
5 |
|
1 |
5 |
10 |
12 |
7 |
13 |
|
2 |
4 |
3 |
7 |
11 |
2 |
Найти оптимальные смешанные стратегии и цену игры в антагонистической матричной игре 2 х n.
|
Игрок 1 \ Игрок 2 |
1 |
2 |
3 |
|
1 |
0 |
3 |
5 |
|
2 |
6 |
18/4 |
3 |
В эксперименте 10 человек независимо друг от друга будут случайным образом выбирать одну из двух гирь - 1 кг или 2 кг. С помощью метода Монте-Карло определить предполагаемое значение суммарного выбранного веса. Использовать механизм случайного выбора типа "орел-решка". Число испытаний N = 15. Описать процесс получения решения. Решить с помощью динамического программирования:
при ограничениях:
Построить расписание обслуживания n = 10 требований m = 3 приборами, минимизирующее момент завершения обслуживания последнего требования
Требования готовы к обслуживанию в момент времени 0.
Прерывания обслуживания любого требования разрешены.
Требование не может обслуживаться 2 и более приборами одновременно. Длительности обслуживания pj заданы в таблице
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
40 |
12 |
30 |
50 |
7 |
4 |
10 |
21 |
9 |
14 |
Найдём общую сумму запасов: = 100+150+80 = 330
Найдём общую сумму заявок: =80+140+110 = 330
В нашем случае запасы поставщиков равны потребностям потребителей.
Построим начальный опорный план задачи минимального элемента.
Первый шаг. Клетка (2;3) имеет наименьший тариф, равный 1.
Максимально возможная поставка для этой клетки: х23=min(110; 150)=110.
Из рассмотрения исключаем 3-й столбец, т.к. заявка потребителя В3 выполнена.
Второй шаг. Просматриваем оставшиеся клетки. Клетка (1;2) имеет наименьший тариф, равный 2. Максимально возможная поставка для этой клетки: х12=min(100; 140)=100.
Третий шаг. Из оставшихся клеток меньший тариф имеет клетка (3;1), в нее загружаем х31=min(80; 80)=80. Из рассмотрения исключаем 1-й столбец, т.к. заявка потребителя В1 выполнена; также исключаем 3-ю строку, возможности поставщика А3 исчерпаны. В клетку (1; 1) впишем нулевую поставку.
Четвертый шаг.
Клетка (2;2) имеет наименьший тариф, равный 6.
Х22=min(150-110; 140-100)=40.
И т.д.
Для большей наглядности этапы построения опорного плана указаны индексами при поставках (таблица 2).
Попутно отметим, что план является невырожденным, т. к. число занятых клеток (6) равно m+ n-1=3+3-1=5.
Таблица 6.2
|
поставщики |
потребители |
Наличие ресурсов |
||
|
В1 |
В2 |
В3 |
||
|
А1 |
3 04 |
2
1002 |
4
|
100 |
|
А2 |
9
|
6
405 |
1
1101 |
150 |
|
А3 |
2 803 |
7
|
5
|
80 |
|
Потребность в ресурсах |
80 |
140 |
110 |
|
F1 = 0*3+100*2+40*6+110*1+80*2 = 710 д.е.
Для исследования плана ТЗ на оптимальность сначала по занятым клеткам для нахождения потенциалов поставщиков и потребителей составляется и решается система уравнений вида Ui + Vj = , далее для всех незанятых клеток вычисляются оценки Sij по формуле: ij = Сij - (Ui + Vj ).
Если хотя бы одна оценка отрицательна, то план не является оптимальным, его можно улучшить за счет загрузки клетки (k; l). Если таких клеток несколько, то наиболее перспективной для загрузки является клетка с наибольшей по абсолютной величине оценкой.
Экономически оценка показывает, на сколько денежных единиц уменьшатся транспортные расходы от загрузки данной клетки единицей груза.
Если все оценки S неотрицательны, то план является оптимальным. Если все оценки S, то оптимальный план единственен....
Список использованной литературы:
Балашевич В.А. Основы математического программирования. - Мн.: Выш. шк., 2002. Карасев А.Н., Кремер Н.Ш., Савельева Т.Н. Математические методы в экономике. - М., 1996. Лященко И.Н. Линейное и нелинейное программирования: И.Н.Лященко, Е.А.Карагодова, Н.В.Черникова. - К.: Высшая школа, 1992. - 372 с. Общий курс высшей математики для экономистов / под ред В.И. Ермакова.- М.: ИНФА - М., 1997. Федосеев В.В. и др. Экономико-математические методы и прикладные модели: учебное пособие для ВУЗов. - М.: Юнити, 2002.
