Главная
страница 1
Московский Физико-технический институт

(государственный университет)

Факультет радиотехники и кибернетики

Отчет


Лабораторная № 3

Решение задачи «О рюкзаке»




  1. базовая задача о рюкзаке (алгоритм Данцига )

  2. эвристический алгортм для многокриториальной задачи.



Выполнили студенты 111 группы Яковлев Алексей и Лукин Дмитрий

Москва, 2005г.


Содержание


Содержание 2

1. Задача о рюкзаке: постановка 3

1.1. Простой случай 3

1.2. Многокритериальный случай 3

2. Алгоритм Дантцига (Dantzig) для простейшего случая 3

3. Эвристический алгоритм для случая многокритериального сравнения альтернатив 4

3.1. Описание алгоритма 4

3.2. Численный пример 4

4. Выводы из проделанной работы 5

5. Литература 5

6. Приложение 5



1. Задача о рюкзаке: постановка




1.1. Простой случай


Имеются элементы, обладающие весом и полезностью, из которых необходимо составить набор («собрать рюкзак») . Данный набор должен обладать максимальной полезностью при условии соблюдения ограничений («по допустимому весу рюкзака»).

Компоненту aj ставим в соответствие полезность и «массу» .

Максимально допустимый вес рюкзака M. Задача составить набор компонент максимизирующий суммарную полезность U при условии ∑vj<= M .

1.2. Многокритериальный случай


Поставим задачу в многомерном случае. Компоненту aj ставим в соответствие вектор полезности uj =(u1…..) и «массу» .

2. Алгоритм Дантцига (Dantzig) для простейшего случая


Каждому компоненту ставим в соответствие «приведенную полезность» j.

,

Множество всех альтернатив сортируется по убыванию приведенной полезности, и затем в «рюкзак» последовательно помещаются компоненты с натбольшей приведенной полезностью до заполнения рюкзака.

3. Эвристический алгоритм для случая многокритериального сравнения альтернатив




3.1. Описание алгоритма


Приведенный выше алгоритм можно непосредственно обобщить на многокритериальный случай. В данном случае есть некоторая функция полезности от вектора полезности uj =(u1…..).

3.2. Численный пример



1) В одномерном случае

Задача:

Имеется 10 элементов с полезностью 12, 53, 14, 73, 33, 51, 53, 50, 54, 78 и массой 6, 2, 5, 6, 4, 8, 7, 8, 2, 2 (соответственно).

В результате выполнения программы (program 1) получили:

рюкзак необходимо заполнять следующими компонентами 10, 9, 2 , 4 , 5



2) В многомерном случае
Полезность отдельного элемента на основе его оценок по k критериям оцениваем как , где xij есть оценка j элемента по i критерию.
Объем рюкзака: 12




Масса

Вектор оценок

Приведенная

Полезность



1

6

34

5

67

70

17,13508

2

4

41

34

39

84

26,70908

3

5

91

16

73

19

23,8554

4

6

33

55

77

13

16,84241

5

9

38

57

16

93

12,95672

6

3

37

89

15

15

32,89715

7

4

28

6

84

60

26,78152

8

9

85

40

50

20

12,03134

9

1

53

73

5

70

114,2935

10

2

12

21

74

71

52,68301

В резльтате выполнения Program 2 получено, что рюкзак необходимо заполнять следующими компонентами:



9 10 6 7

(суммарный объем: 10).



4. Выводы из проделанной работы


В данной работе мы рассмотрели работу алгоритма Дантцига для решения задачи «О рюкзаке» в одномерном и многомерном случаях, его реализацию в Матлабе.

Ясно, что данный модуль может быть использован для решения задач разного типа. Например



  1. разработка наборов продуктов питания

  2. планирование бизнес-процессов, где в качестве веса будет выступать время

5. Литература


1. Internet site of the course “Design of Systems: Structural Approach”:

http://www.iitp.ru/mslevin/

2.S. Martello and P. Toth, Knapsack Problem: Algorithms and Computer Implementation.

New York: J.Wiley & Sons, 1990.

3. M.R. Garey and D.S. Johnson, Computers and Intractability.

The Guide to the Theory of NP-Completeness. San Francisco:

W.H.Freeman and Company, 1979.

6. Приложение

Matlab program 1 (одномерный случай)


function [] = knapsack(n,RB)

%*****************************************************************

% Dec. 10, 2004

% EXAMPLE OF PROGRAM: knaapsack problems

% Author: M.Sh. Levin, A.A. Yakovlev, D.V. Lukin

%*****************************************************************

% n is dimension of initial list of elements

% c[n] is vector for initial set of element's utilities

% b[n] is vector for initial set of element's resource requirements

% RB is total resource constraint

% cb[n] is is vector of c / b (relative utility)

% r is resultant vector with numbers of selected elements

% example: knapsack(10,500)

%--------------------------------------------------------------------------

%

% input of initial data



'UTILITY OF ELEMENTS'

c=[ 12, 53, 14, 73, 33, 51, 53, 50, 54, 78]

'RESOURCE REQUIREMENTS OF ELEMENTS'

b=[ 6, 2, 5, 6, 4, 8, 7, 8, 2, 2]

%computing rate c / b (relative utility)

for i=1:n,

cb(i)=c(i)/ b(i);

end,


figure

'RELATIVE UTILITY OF ELEMENTS'

cb

bar(cb);


title('RELATIVE UTILITY OF ELEMENTS');
for k=1:n,

nb(k)=k;


end,
%======================= ordering of elements via c / b

[ncb,nnb] = lord(10,cb,nb);


% integrated resource requirement (must be <= B)

ww=0;


ii=1;

for i=1:n,

r(i)=0;

end,
for i=1:n,

ww=ww+b(nnb(i));

if ( ww <= RB)

r(ii)= nnb(i);

ii=ii+1;


end,

end,
'resultant set of selected elements'

r

bar(r);


title('RESULTANT SET OF SELECTED ELEMENTS');
Matlab program 2(многомерный случай)
function [] = knapsack2(n,m,RB)

%*****************************************************************

% Dec. 10, 2004

% EXAMPLE OF PROGRAM: knapsack problems

% Author: M.Sh. Levin, A.A. Yakovlev, D.V. Lukin

%*****************************************************************

% n is dimension of initial list of elements

% c[n] is vector for initial set of element's utilities

% b[n] is vector for initial set of element's resource requirements

% RB is total resource constraint

% cb[n] is is vector of c / b (relative utility)

% r is resultant vector with numbers of selected elements

% example: knapsack2(10,4,12)

%--------------------------------------------------------------------------

%

% input of initial data



'UTILITY OF ELEMENTS'

c=[34,5,67,70; 41,34,39,84; 91,16,73,19; 33,55,77,13; 38,57,16,93; 37,89,15,15; 28,6,84,60; 85,40,50,20; 53,73,5,70; 12,21,74,71]


%computing U
U=[0, 0, 0, 0, 0 ,0, 0, 0, 0, 0];

for i=1:n,

for j=1:m,

U(i)=U(i)+c(i,j)*c(i,j);

end,

U(i)=sqrt(U(i));



end,

U

'RESOURCE REQUIREMENTS OF ELEMENTS'



b=[ 6, 4, 5, 6, 9,3, 4, 9, 1, 2]

%computing rate Ui/bi (relative utility)

for i=1:n,

cb(i)=U(i)/ b(i);

end,

figure


'RELATIVE UTILITY OF ELEMENTS'

cb

bar(cb);



title('RELATIVE UTILITY OF ELEMENTS');
for k=1:n,

nb(k)=k;


end,
%======================= ordering of elements via c / b

[ncb,nnb] = lord(10,cb,nb);


% integrated resource requirement (must be <= B)

ww=0;


ii=1;

for i=1:n,

r(i)=0;

end,
for i=1:n,

ww=ww+b(nnb(i));

if ( ww <= RB)

r(ii)= nnb(i);

ii=ii+1;


end,

end,
'resultant set of selected elements'



r

bar(r);


title('RESULTANT SET OF SELECTED ELEMENTS');


Смотрите также:
Отчет Лабораторная №3 Решение задачи
66.42kb.
1 стр.
Лабораторная работа по химии, физике, биологии, т е. по естественно-научным предметам. На уроках русского языка и литературы термин «лабораторная работа»
261.84kb.
1 стр.
Решение логических задач при помощи таблиц
183.04kb.
1 стр.
Решение задачи в рабочей тетради и в электронном виде. Электронное решение своевременно сдать учителю
197.64kb.
1 стр.
Решение задачи решение проблемы. Алгоритмизация и творческий подход. О рейтинге, домашних заданиях и результатах работы на ск
121.87kb.
1 стр.
Лабораторная Работа №1 Отчет:"сервер" Корнилов В. А. 13. 09. 2012
118.03kb.
1 стр.
Задача Коши, теорема о существовании и единственности решения. Общее, частное решение (интеграл)
61.89kb.
1 стр.
Отчет о лабораторной работе №1 Барнаул 2011 Лабораторная №1 Вариант 6 Задача
278.51kb.
1 стр.
1. Информация и управление. Назначение и функции обратной связи
68.29kb.
1 стр.
Решение задачи на листке, удобном для сканирования или в электронном виде
192.22kb.
1 стр.
Методическая разработка учитель начальных классов моу белосельской сош пошехонского мо ярославской Области
937.92kb.
5 стр.
Предпосылки постановки диагноза
41.88kb.
1 стр.