Экономико-математические методы и иодели

№,	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	∞

 

Решение

Возьмем в качестве произвольного  маршрута: X₀ = (1,2);(2,3);(3,4);(4,5);(5,6);(6,1)

Тогда F(X₀) = 1 + 2 + 4 + 0 + 5 + 9 = 21

Для определения нижней границы множества воспользуемся  операцией редукции, для чего необходимо в каждой строке матрицы D найти минимальный элемент: d_i = min(j) d_ij

 

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

 

Затем вычитаем d_i из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

Такую же операцию редукции проводим по столбцам, для чего в  каждом столбце находим минимальный элемент: d_j = min(i) d_ij

 

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