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

Автор работы: Пользователь скрыл имя, 28 Ноября 2013 в 21:17, контрольная работа

Краткое описание

Задание № 1 Решить следующую задачу о рюкзаке ...
Задание № 2 Решить задачу коммивояжера по таблице расстояний между городами. Привести экономическую интерпретацию данной задачи.
Задание № 3 Решить матричную игру, заданную ниже платёжной матрицей, сведя ее к парам двойственных задач линейного программирования:....

Прикрепленные файлы: 1 файл

ГОТОВЫЙ БА4.doc

— 1.01 Мб (Скачать документ)

№,

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);(6,1)

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

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

 

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

Информация о работе Экономико-математические методы и иодели