Экономико-математические методы и иодели
Содержание
Задание № 1
Решить следующую задачу о рюкзаке
№, |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Вес, (кг) |
3 |
4 |
3 |
4 |
5 |
4 |
4 |
Стоимость, (у.е.) |
6 |
2 |
7 |
6 |
2 |
5 |
3 |
Ценность не менее 17.
Решение
Для нахождения первоначальной оценки для каждого предмета вычислим цену, т.е. стоимость одного кг предмета. При этом мы допускаем возможность деления предметов на части. При таком допущении оптимальный способ наполнения рюкзака становится очевидным: сначала наполняем рюкзак самым ценным предметом (с самой большой ценой). Когда он закончится, продолжаем заполнять рюкзак следующим по цене предметом и т.д. (до тех пор, пока не наберется указанная стоимость). В таблице указана очередность такой укладки. Величина указывает, какую часть предмета мы укладываем в рюкзак.
№, |
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 |
|
Очередность укладки |
2 |
1 |
3 |
|||||
|
1 |
1 |
2/3 |
|||||
Вес взятой части предмета |
3 |
3 |
8/3 |
|||||
|
Стоимость взятой части |
6 |
7 |
4 |
17 |
Сначала берем самый ценный предмет №3. Он дает 7 у.е. стоимости. Добавляем следующий по ценности предмет №1. Суммарная стоимость обоих предметов 7+6=13. Нам осталось добавить 4 у.е. стоимости. Это составляет 2/3 от стоимости следующего по ценности предмета – №4. Поэтому мы объявляем, что условно берем 2/3 предмета №4 (вес этой части составляет 4*2/3=8/3) и заканчиваем укладку рюкзака. Мы получили начальную оценку, которая утверждает, что вес рюкзака в наших условиях не может быть меньше кг.
Поскольку на самом деле предмет №4 на части делить нельзя, разделим все возможные варианты на два множества, в первом из которых мы не используем этот предмет, во втором – предмет №4 обязательно должен быть в рюкзаке.
1) Не берем предмет №4.
№, |
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 |
2 |
1 |
4 |
||||
|
1 |
1 |
0 |
4/5 |
||||
Вес взятой части предмета |
3 |
3 |
16/5 |
|||||
|
Стоимость взятой части |
6 |
7 |
4 |
17 |
Действуем аналогично предыдущему случаю. Теперь после предметов №3 и №1 наибольшую ценность из доступных предметов имеет №6. Таким образом, недостающую 4 у.е восполняем 4/5 предмета №6. Получаем, что при отказе от предмета №4 вес рюкзака ценностью не менее 17 у.е. не может быть меньше, чем кг.
2) Предмет №4 берем обязательно. В этом случае укладку рюкзака начинаем с обязательных предметов, а затем продолжаем по прежнему принципу максимальной цены.
Укладываем 4-й и 3-й предметы. Оставшиеся 4 единицы стоимости восполняем 2/3 предмета №1. Получаем, что в нашем случае, вес рюкзака не будет меньше 9 кг.
№, |
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 |
2 |
1 |
|||||
|
2/3 |
1 |
1 |
|||||
Вес взятой части предмета |
2 |
3 |
4 |
9 | ||||
Стоимость взятой части |
4 |
7 |
6 |
17 |
Посмотрим на дерево вариантов.
Поскольку вариант (берем 4-й предмет) имеет наименьшую оценку, рассматриваем в первую очередь его. Поскольку при оценке этого варианта нам пришлось делить на части 1-й предмет, ставим вопрос именно об этом предмете.
3) Предмет №1 не берем.
Начнем с обязательных, а именно вначале берем предмет №4, но не берем №1, затем следующий по стоимости №3. После 4 и 3 предметов остается 4 единицы стоимости, которые заполняем 4/5 самого ценного предмета №6. Оценка данного множества вариантов равна кг.
№, |
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 |
|
Очередность укладки |
2 |
3 |
1 |
4 |
||||
|
0 |
1 |
1 |
4/5 |
||||
Вес взятой части предмета |
3 |
4 |
16/5 |
|||||
|
Стоимость взятой части |
7 |
6 |
4 |
17 |
4) Предмет № 1 берем обязательно.
Начнем с обязательных, а именно вначале берем предмет №4, затем предмет № 1. После 4-го и 1-го предметов остается 5 единиц стоимости, восполняем их 5/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 |
|
Очередность укладки |
2 |
3 |
1 |
|||||
|
1 |
5/7 |
1 |
|||||
Вес взятой части предмета |
3 |
15/7 |
4 |
|||||
|
Стоимость взятой части |
6 |
5 |
6 |
17 |
Оценим перспективность вариантов. Из всех актуальных оценок ( , и ) наименьшей является оценка множества с , поэтому в первую очередь рассмотрим его.
В 4 пункте мы делили на части 3-й предмет. Поскольку на самом деле предмет №3 на части делить нельзя, разделим все возможные варианты на два множества, в первом из которых мы не используем этот предмет, во втором – предмет №3 обязательно должен быть в рюкзаке.
5) Предмет № 3 не берем.
После обязательных 4 и 1 предметов и исключения 3-го, остается 5 у.е., восполняем ее следующим по стоимости, то есть № 6. Оценка множества вариантов равна 11 кг. Таким образом в данном множестве вариантов, получили точную оценку.
№, |
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 |
|
Очередность укладки |
2 |
3 |
1 |
4 |
||||
|
1 |
0 |
1 |
1 |
||||
Вес взятой части предмета |
3 |
4 |
4 |
11 | ||||
Стоимость взятой части |
6 |
6 |
5 |
17 |
6) Берем предметы №4, 1 и 3. В данном случае стоимость уже составит 6+6+7=19 у.е. Таким образом, в данном множестве вариантов мы нашли точную оценку: берем 4-й, 1-й и 3-й предметы, вес рюкзака при этом составит 4+3+3=10 кг.
Посмотрим на дерево вариантов
Наименьшей является оценка множества 1) , значит рассмотрим это множество и продолжим дальше. Поскольку на самом деле предмет №6 на части делить нельзя, разделим все возможные варианты на два множества, в первом из которых мы не используем этот предмет, во втором – предмет №6 обязательно должен быть в рюкзаке.
7) Предмет №6 не берем.
Не берем 4-й и 6-й предметы. Следующие по ценности предметы №3, 1 и 7. В данном случае стоимость уже составит 16 у.е. Оставшуюся 1 единицу стоимости, восполняем 1/2 предмета №2. Оценка множества вариантов равна 12 кг.
№, |
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 у.е.
Задание № 2
Решить задачу коммивояжера по таблице расстояний между городами. Привести экономическую интерпретацию данной задачи.
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 |
