Задача о ранце

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ

(НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ) Отчет

по курсовой работе за курс:

" Теория Оптимального Планирования и Управления"

Тема

" Задача о ранце"

Москва 2012

• 1. Постановка задачи
• 2. Метод решения
• 3. Общее описание программного модуля
• 4. Алгоритм метода
• 5. Определение данных
• 6. Входной файл
• 7. Выходной файл
• 8. Тестовая проверка
• 9. Листинг программы
• Выводы

1. Постановка задачи

Задача о ранце.

Алгоритм неявного лексикографического перебора.

Разработать структуру данных, реализацию алгоритма с её использованием и программную реализацию.

Провести тестовую проверку.

2. Метод решения

Дается набор из N предметов. Пусть MaxW — объем рюкзака, Pi — стоимость i-го предмета, Wi — вес i-го предмета. Value [W, i] - максимальная сумма, которую надо найти.

На каждом шаге по весу 1

Если мы уже нашли Value [1. W, 1. i-1], то есть для веса меньше либо равного W и с предметами, взятыми из 1. N-1.

Рассмотрим предмет N, если его вес WN меньше W проверим стоит ли его брать.

Если мы его берем, то вес становится W-Wi, тогда Value [W, i] = Value [W — Wi, i-1] + Pi (для Value [W — Wi, i-1]) решение уже найдено остается только прибавить Pi.

Если его не брать то вес останется тем же и Value [W, i] = Value [W — Wi, i-1].

Из двух вариантов выбирается тот, который дает наибольший результат.

листинг программа алгоритм

3. Общее описание программного модуля

3.1 Назначение модуля.

Модуль предназначен для решения задачи о ранце.

3.2 Ограничения.

При работе с модулем для корректной работы программы требуется, чтобы входной файл находился в каталоге, из которого был вызван исполняемый модуль.

Если файл не будет найден или содержит некорректные данные, то загрузка не будет произведена.

3.3 Язык программирования.

Программа написана на языке программирования Delphi7

3.4 Тип и версия требуемой операционной системы.

Для выполнения программы необходима операционная система MS-DOS 3.0 и выше.

4. Алгоритм метода

Задача о ранце.

Турист готовится к длительному переходу. Он может нести груз весом b, который может включать n типов предметов. Каждый отдельный предмет типа j весит a [j] (j=1,n), а полезность его использования в переходе оценивается числом c [j]. Необходимо определить, сколько предметов каждого типа турист должен положить в рюкзак, чтобы суммарная ценность снаряжения была максимальной. Формальная запись задачи имеет следующий вид:

. (3.3)

К задаче такого рода в первом приближении может быть сведена задача комплектации оборудованием многоцелевого летательного аппарата.

Метод лексикографического неявного перебора (МЛНП)

Этот метод основан на процедуре перебора отдельных точек области возможных решений, аналогичной упорядочению слов в словаре и называемой поэтому лексикографической. Все переменные исходной задачи упорядочиваются по быстроте изменения. Если никаких дополнительных соображений при этом не использовать, то этот порядок будет соответствовать естественному порядку нумерации переменных исходной формализованной записи оптимизационной задачи: самой медленноменяющейся переменной будет x [1], а самой быстроменяющейся — x [n]. B процессе перебора каждая переменная принимает последовательно целочисленные значения, начиная с (как правило,) и кончая. Но прежде чем увеличить значение переменной x [j] на единицу, необходимо перебрать все возможные комбинации переменных x [j+1],., x [n]. Для этого каждая из них должна пробежать все свои значения от наименьшего до наибольшего возможного. Рассмотрим эту процедуру на примере. Пусть n= 3, а переменные x [j] могут принимать последовательно следующие значения:

x =A, B; x =1, 2; x =,, .

Тогда при естественном упорядочении переменных по быстроте изменения последовательность рассматриваемых точек будет следующей:

1) A 1, 4) A 2, 7) B 1, 10) B 2 ,

2) A 1, 5) A 2, 8) B 1, 11) B 2 ,

3) A 1, 6) A 2, 9) B 1, 12) B 2 .

В самом простейшем варианте рассматриваемого метода уменьшение объема вычислений осуществляется за счет использования так называемого «фильтрующего» ограничения. Применение метода лексикографического перебора с использованием только фильтрующего ограничения не требует, как это будет видно из дальнейших рассуждений, выполнения условий линейности целевой функции и ограничений задачи целочисленного программирования. Однако мы будем рассматривать именно этот случай, так как ряд дополнительных возможностей сокращения объема вычислений реализуются только для него.

Предполагается, что исходная задача приведена к виду, когда направление оптимизации целевой функции определено следующим образом:

. (3.30)

Фильтрующее ограничение первый раз может быть сформировано либо до начала решения задачи, если из априорных соображений известно хотя бы одно ее допустимое решение, либо в процессе поиска, как только такое решение найдено. Это ограничение формируется на основе записи целевой функции и ее значения для лучшего найденного к текущему шагу перебора допустимого решения xД:

. (3.31)

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

Для сокращения объема вычислений, прежде чем проверять принадлежность некоторого решения допустимой области, проверяют выполнение фильтрующего ограничения. Если оно не выполняется, то переходят к рассмотрению следующего решения. Обоснование такого правила состоит в том, что после нахождения допустимого решения в дальнейшем с точки зрения решения оптимизационной задачи имеет смысл рассматривать лишь такие x, для которых значение целевой функции меньше z (xД).

Каждый раз при нахождении лучшего допустимого решения правая часть фильтрующего ограничения корректируется (уменьшается). При этом фильтрующее ограничение становится более жестким.

Еще одной возможностью, которая в некоторых задачах может обеспечить дополнительное сокращение объема вычислений, является использование упорядочения переменных по быстроте изменения в соответствии с величинами коэффициентов целевой функции: самая быстроменяющаяся переменная — та, которой соответствует наименьшее значение коэффициента целевой функции. При таком упорядочении, как правило, раньше будут рассмотрены решения с меньшими значениями целевой функции. Если среди них найдется допустимое, то в более ранний момент будет введено более жесткое фильтрующее ограничение, что и должно привести к сокращению объема вычислений.

И еще одна возможность. Проверка принадлежности некоторого решения области допустимых решений осуществляется последовательно по каждому ограничению. Как только найдено не выполняющееся ограничение, дальнейший анализ решения заканчивается и осуществляется переход к следующему. На этой основе может быть реализовано правило упорядочения ограничений задачи «по жесткости»: в первую очередь целесообразно проверять более жесткие ограничения. Более жесткими являются те ограничения, которые для большего числа возможных решений не выполняются. Информация о жесткости ограничений может быть получена либо на основе априорного анализа оптимизационной задачи, либо может быть реализована адаптивная процедура упорядочения и переупорядочения ограничений непосредственно в процессе перебора по реализовавшимся частотам их выполнения. По аналогии с фильтрующим ограничением применение этого правила может дать дополнительное сокращение объема вычислений.

В линейных задачах возможным также является проведение анализа значений отдельных коэффициентов целевой функции, ограничений и направления изменения при переборе соответствующих оптимизационных переменных с целью пропуска некоторых последовательностей точек, среди которых либо нельзя найти допустимых решений, либо решений, лучших по значению целевой функции.

Алгоритм МЛНП

Шаг 1. Выбор очередной рассматриваемой точки х в соответствии с лексикографическим порядком и с учетом упорядочения компонент x [j] по быстроте изменения.

Шаг 2. Если фильтрующее ограничение сформировано, то — проверка выполнения его в точке х: если оно не выполняется, то — переход на шаг 7.

Шаг 3. Проверка выполнения в точке х очередного ограничения оптимизационной задачи (в порядке их ранжирования по степени активности): если оно не выполняется, то — переход на шаг 7.

Шаг 4. Если рассмотрены не все ограничения, то — на шаг 3.

Шаг 5. Вычисление целевой функции в очередной найденной допустимой точке: z (x).

Шаг 6. Если фильтрующее ограничение еще не введено, то ввести его с правой частью =z (x), зафиксировать =x. Если фильтрующее ограничение уже сформировано и выполняется условие z (x) <, то переопределить его правую часть (=z (x)) и зафиксировать =x.

Шаг 7. Если еще не все точки рассмотрены, то — на шаг 1.

Шаг 8. Если (,) определено, то это — оптимальное решение, иначе D=.

5. Определение данных

Программа поддерживает решение задачи с данными, находящимися в файле input. txt. При запуске программы данные будут считаны из указанного файла.

Исходные данные:

N — количество предметов

MaxWeight — мах объём

W [i] - вес i-го предмета

P [i] - стоимость i-го предмета

6. Входной файл

7. Выходной файл

8. Тестовая проверка

Если вес предмета больше чем объём сумки, (хоть его стоимость и высокая), то предмет не берется. В данном случае это предмет 2 (вес 31, стоимость 4000)

Если все предметы больше чем объём сумки, то ни один из предметов взят не будет

9. Листинг программы

program DP2;

{$APPTYPE CONSOLE}

uses SysUtils;

Const MaxW = 200; MaxN = 100;

var Value: array [0. MaxW, 0. MaxN] of integer; {массив значений (сколько можно набрать для 1. W весов в 1. N предметов) }

Take: array [0. MaxW, 0. MaxN] of boolean; {массив значений брали предмет или нет}

W, P: array [0. MaxN] of integer; {Массив весов, массив цен}

i, N, Weight, MaxWeight: integer;

procedure Init;

begin

assign (input,'input. txt');

reset (input);

readln (N, MaxWeight);

for i: =1 to N do readln (W [i], P [i]);

close (input);

end;

procedure Solve;

begin

fillchar (Take, sizeof (Take), false); {обнуляем строку}

fillchar (Value, sizeof (Value), 0);

for Weight: =1 to MaxWeight do begin {выбираем оптимум для веса Weight}

for i: =1 to N do {берем предметы с 1 по N}

if (W [i] > Weight) or (Value [Weight, i-1] >= Value [Weight-W [i], i-1] +P [i]) then

{если вес предмета больше чем текущий вес рюкзака}

{или предыдущий набор дороже выбираемого}

begin

Value [Weight, i]: = Value [Weight, i — 1];

{тогда берем предыдущий набор}

Take [Weight, i]: = false; {говорим что вещь i не взята}

end

else begin {иначе добавляем к предыдущему набору текущий предмет}

Value [Weight, i]: = Value [Weight — W [i], i-1] +P [i];

Take [Weight, i]: = true; {говорим что вещь i взята}

end;

end;

end;

procedure Done;

begin

assign (output,'output. txt');

rewrite (output);

Writeln ('Наилучший набор ', Value [MaxWeight, N]);

Weight: = MaxWeight;

for i: = N downto 1 do if Take [Weight, i] then begin

Write (i,' ');

Weight: = Weight-W [i];

end;

close (output);

end;

begin

Init;

Solve;

Done;

end.

Выводы

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