Автор работы: Пользователь скрыл имя, 28 Ноября 2013 в 21:17, контрольная работа
Задание № 1 Решить следующую задачу о рюкзаке ...
Задание № 2 Решить задачу коммивояжера по таблице расстояний между городами. Привести экономическую интерпретацию данной задачи.
Задание № 3 Решить матричную игру, заданную ниже платёжной матрицей, сведя ее к парам двойственных задач линейного программирования:....
№, |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Итого |
Вес, (кг) |
3 |
4 |
3 |
4 |
5 |
4 |
4 |
|
Стоимость, (у.е.) |
6 |
2 |
7 |
6 |
2 |
5 |
3 |
|
Цена, (у.е./кг) |
2 |
½ |
7/3 |
3/2 |
2/5 |
4/5 |
3/4 |
|
Очередность укладки |
4 |
6 |
3 |
1 |
2 |
5 |
||
|
1 |
½ |
1 |
0 |
0 |
1 |
||
Вес взятой части предмета |
3 |
2 |
3 |
4 |
12 | |||
Стоимость взятой части |
6 |
1 |
7 |
3 |
17 |
8) Предмет №1 берем обязательно.
Не берем 4-й, но берем 6-1 предметы. Следующий по ценности предмет № 3. Их стоимость составляет 12 у.е. Оставшиеся 5 у.е. восполняем 5/6 предмета №1. Оценка множества вариантов равна кг.
№, |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Итого |
Вес, (кг) |
3 |
4 |
3 |
4 |
5 |
4 |
4 |
|
Стоимость, (у.е.) |
6 |
2 |
7 |
6 |
2 |
5 |
3 |
|
Цена, (у.е./кг) |
2 |
½ |
7/3 |
3/2 |
2/5 |
4/5 |
3/4 |
|
Очередность укладки |
4 |
3 |
1 |
2 |
||||
|
5/6 |
1 |
0 |
1 |
||||
Вес взятой части предмета |
5/2 |
3 |
4 |
|||||
Стоимость взятой части |
5 |
7 |
5 |
17 |
Посмотрим на дерево вариантов
Наименьшей является оценка множества 8) , значит рассмотрим это множество и продолжим дальше. Поскольку на самом деле предмет №1 на части делить нельзя, разделим все возможные варианты на два множества, в первом из которых мы не используем этот предмет, во втором – предмет №1 обязательно должен быть в рюкзаке.
9) Предмет №1 не берем.
Берем 6-й, но не берем 4-й и 1-й предметы. Следующий по ценности предмет №3, 7 и 2. В данном случае стоимость уже составит 17 у.е. Получили точную оценку множества вариантов, которая равна 15 кг.
№, |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Итого |
Вес, (кг) |
3 |
4 |
3 |
4 |
5 |
4 |
4 |
|
Стоимость, (у.е.) |
6 |
2 |
7 |
6 |
2 |
5 |
3 |
|
Цена, (у.е./кг) |
2 |
½ |
7/3 |
3/2 |
2/5 |
4/5 |
3/4 |
|
Очередность укладки |
3 |
6 |
4 |
1 |
2 |
5 |
||
|
0 |
1 |
1 |
0 |
1 |
1 |
||
Вес взятой части предмета |
4 |
3 |
4 |
4 |
15 | |||
Стоимость взятой части |
2 |
7 |
5 |
3 |
17 |
10) Предмет №1 берем.
Берем 6-й и 1-й, но не берем 4-й предметы. В данном случае стоимость составляет 11 у.е. Оставшиеся 6 у.е. восполняем 6/7 предмета №3. Оценка множества вариантов равна кг.
№, |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Итого |
Вес, (кг) |
3 |
4 |
3 |
4 |
5 |
4 |
4 |
|
Стоимость, (у.е.) |
6 |
2 |
7 |
6 |
2 |
5 |
3 |
|
Цена, (у.е./кг) |
2 |
½ |
7/3 |
3/2 |
2/5 |
4/5 |
3/4 |
|
Очередность укладки |
3 |
4 |
1 |
2 |
||||
|
1 |
6/7 |
0 |
1 |
||||
Вес взятой части предмета |
3 |
18/7 |
4 |
|||||
Стоимость взятой части |
6 |
6 |
5 |
17 |
Посмотрим на дерево вариантов
Наименьшей является оценка множества 10) , значит рассмотрим это множество и продолжим дальше. Поскольку на самом деле предмет №3 на части делить нельзя, разделим все возможные варианты на два множества, в первом из которых мы не используем этот предмет, во втором – предмет №3 обязательно должен быть в рюкзаке.
11) Берем предметы №6, 1 и 3. В данном случае стоимость уже составит 5+6+7=18 у.е. Таким образом, в данном множестве вариантов мы нашли точную оценку: берем 6-й, 1-й и 3-й предметы, вес рюкзака при этом составит 4+3+3=10 кг.
12) Предмет №3 не берем.
Берем 6-й и 1-й, но не берем 4-й и 3-й предметы. В данном случае стоимость уже составит 11 у.е. Следующие по стоимости предметы № 7 и 2. Ценность уже составляет 16 у.е. Оставшуюся 1 у.е. восполняем 1/2 предмета №5. Оценка множества вариантов равна кг.
№, |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Итого |
Вес, (кг) |
3 |
4 |
3 |
4 |
5 |
4 |
4 |
|
Стоимость, (у.е.) |
6 |
2 |
7 |
6 |
2 |
5 |
3 |
|
Цена, (у.е./кг) |
2 |
½ |
7/3 |
3/2 |
2/5 |
4/5 |
3/4 |
|
Очередность укладки |
3 |
6 |
4 |
1 |
7 |
2 |
5 |
|
|
1 |
1 |
0 |
0 |
½ |
1 |
1 |
|
Вес взятой части предмета |
3 |
4 |
5/2 |
4 |
4 |
|||
Стоимость взятой части |
6 |
2 |
1 |
5 |
3 |
17 |
У нас есть точные оценки (отмеченые звездочкой). Так оценки множеств 11 и 6 одинаковые, то наилучшей будет та, у которой ценность больше, а именно множество с номером 6.
Теперь можно сказать, что вариант укладки рюкзака, полученный во множестве 6 ( ) является наилучшим, так как оценки всех остальных хуже.
Таким образом, минимальная масса рюкзака составит 10 кг. Для этого в рюкзак нужно положить 1-й, 3-й и 4-й предметы, общая стоимость рюкзака составит при этом 6+7+6=19 у.е.
Решить задачу коммивояжера по таблице расстояний между городами. Привести экономическую интерпретацию данной задачи.
1 |
2 |
3 |
4 |
5 |
6 | |
1 |
∞ |
1 |
7 |
8 |
4 |
3 |
2 |
3 |
∞ |
2 |
2 |
4 |
8 |
3 |
9 |
5 |
∞ |
4 |
3 |
8 |
4 |
6 |
0 |
2 |
∞ |
0 |
9 |
5 |
2 |
8 |
2 |
3 |
∞ |
5 |
6 |
9 |
2 |
0 |
7 |
1 |
∞ |
Возьмем в качестве произвольного
маршрута: X0 = (1,2);(2,3);(3,4);(4,5);(5,6);
Тогда F(X0) = 1 + 2 + 4 + 0 + 5 + 9 = 21
Для определения нижней
границы множества
i j |
1 |
2 |
3 |
4 |
5 |
6 |
di |
1 |
∞ |
1 |
7 |
8 |
4 |
3 |
1 |
2 |
3 |
∞ |
2 |
2 |
4 |
8 |
2 |
3 |
9 |
5 |
∞ |
4 |
3 |
8 |
3 |
4 |
6 |
0 |
2 |
∞ |
0 |
9 |
0 |
5 |
2 |
8 |
2 |
3 |
∞ |
5 |
2 |
6 |
9 |
2 |
0 |
7 |
1 |
∞ |
0 |
Затем вычитаем di из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент: dj = min(i) dij
i j |
1 |
2 |
3 |
4 |
5 |
6 |
1 |
∞ |
0 |
6 |
7 |
3 |
2 |
2 |
1 |
∞ |
0 |
0 |
2 |
6 |
3 |
6 |
2 |
∞ |
1 |
0 |
5 |
4 |
6 |
0 |
2 |
∞ |
0 |
9 |
5 |
0 |
6 |
0 |
1 |
∞ |
3 |
6 |
9 |
2 |
0 |
7 |
1 |
∞ |
dj |
0 |
0 |
0 |
0 |
0 |
2 |
Информация о работе Экономико-математические методы и иодели