Алгоритм метода ветвей и границ для решения одномерных задач целочисленного программирования

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

(Национальный Исследовательский Университет)

Факультет №3«Системы управления,
информатика и электроэнергетика»

Кафедра №308«Информационные технологии»

Курсовая работа

по курсу «Технический контроль и диагностика систем ЛА»

Вариант II (2)

Выполнила: Пахомова Вероника Юрьевна

Группа: 03-417

Проверил:доцент, к.т.н. Пискунов Вячеслав Алексеевич

Москва 2012 г.

Содержание

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

1. Алгоритм метода ветвей и границ для решения одномерных задач целочисленного программирования ……………………………………………………………………………………………..………4

1.1. Теоретическая часть…………………………………………..……………………………………………...4

1.2. Практическая часть…………………………………………………………………………………………….8

1.3. Программные расчеты и сравнение результатов………………………………….……….15

2. Алгоритм метода динамического программирования…………………………….…….……….17

2.1. Теоретическая часть…………………………………………………………………………………………17

2.2. Практическая часть………………………………………………………………………………….……….22

2.3. Программные расчеты и сравнение результатов……………………………………….….24

Выводы………………………………………………………………………………………….……………………………25

Список используемой литературы…………….………………………………………………………………26

Приложение 1……………………………………………………………………………………………………………………….27

Приложение 2……………………………………………………………………………………………………………………….38

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

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

· метод ветвей и границ;

· метод динамического программирования.

Написать программы для реализации решения поставленной задачи.

Сравнить результаты при ручном расчёте и программном.

Сделать выводы.

Алгоритм метода ветвей и границ для решения одномерных задач целочисленного программирования

1.1 Теоретическая часть

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

Рассмотрим следующую задачу целочисленного программирования. Тре­буется максимизировать выражение

(1.1)

при ограничениях

(1.2)

x_j {0;1}, j=1,…,n, (1.3)

причем p_j ≥0, c_j≥0.

Решение задачи может быть получено с помощью метода ветвей и границ.

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

Эффективность вычислительных алгоритмов зависит от точности и простоты способа определения верхней границы возможных решений и точности определения приближенного решения. Чем точнее способ опреде­ления верхней границы целевой функции, тем больше бесперспективных ветвей отсекается в процессе оптимизации. Однако увеличение точности расчета верхних границ связано с возрастанием объема вычислений. Напри­мер, если для оценки верхней границы использовать симплекс-метод, то результат будет достаточно точным, но потребует большого объема вы­числительной работы.

Рассмотрим алгоритм решения задачи (1.1) — (1.3) методом ветвей и границ с простым и эффективным способом оценки верхней границы целевой функции.

Множество U переменных x_j рассматривается как три множества.

S -множество фиксирован­ных переменных, вошедших в допустимое решение; E_s — множество за­висимых переменных, которые не могут быть включены в множество S, так как для них выполняется неравенство

G_S — множество свободных переменных, из которых производится выбор для включения в S очередной переменной.

Обозначим h_1j = p_j/c_j и допустим, что x_j S (j= 1, . .., k < п), вычисляется указанное отношение и параметры номеруются (ранжируются) в соответствии с ранжировкой:

h_1,k+1 ≥h_1,k+2≥ ...≥h_1l, l≤n, (1.4)

(1.5)

(1.6)

Условия (1.5), (1.6) означают, что в множество S без нарушения нера­венства (1.2) можно дополнительно ввести элементы х_к+1, х_{к +2},..., х_l-1. При введении в множество S элементов х_к+1, х_{к +2},..., х_l неравенство (1.2) не выполняется.

Для определения верхней границы решения может быть использовано
выражение:

(1.7)

где

(1.8)

(1.9)

Из условий (1.1)-(1.3) следует, что L'_s не меньше максимального значения величины

при ограничениях

Поясним процесс определения L'_S графиком (рис. 1.1). Строим кусочнолинейную функцию L(с) с убывающим значением градиента h. Вычисля­ем с'₁ и по графику находим L'_S.

Выбор очередной переменной для включения в множество S производит­ся с помощью условия:

(1.10)

Для выбранной переменной х_r определяются величины Р_S(x_r) и Р_S( x_r), т.е. в S включается х_r = 1 или х_r = 0.

Если в процессе решения окажется, что в множестве G_S нет элементов, которые могут быть введены в множество S без нарушения ограничения (1.5), то полученное решение принимается в качестве первого приближенного решения L₀.

Все вершины дерева возможных вариантов, для которых выполняются условия Q_S ≤ L₀ из дальнейшего рассмотрения исключаются.

Из оставшихся ветвей выбирается ветвь с максимальным значением Р_S, и процесс поиска оптимального варианта продолжается. Если в процессе решения будет найдено , то полученное решение принимается в качестве нового приближенного результата. Вычислительная процедура заканчивается, если для всех оставшихся ветвей выполняется условие Р_S ≤ L₀.

1.2 Практическая часть

Дано:

Нормированные вероятности отказов для элементов Q_i, затраты на контроль i-ого параметра C(x_i).

№
Qi	0,04	0,15	0,13	0,08	0,02	0,09	0,06	0,08	0,03	0,04
C(xi)

Найти: Выбрать такие параметры, чтобы C≤18 при Q=Q_max.

Решение:

Для удобства расчетов проранжируем таблицу 4 в порядке убывания и присвоим новые номера элементам, следующим образом:

№(i)
№(j)
Qj	0,15	0,08	0,04	0,13	0,09	0,06	0,03	0,08	0,04	0,02
C(xj)
hj	0,15	0,04	0,04	0,0325	0,03	0,03	0,03	0,0267	0,008	0,0033

Значение l определяет сумма q₁+ q₂+ q₃+ q₄+ q₅+ q₆+ q₇ + q₈ =17, отсюда l=9

при l = 9, , ,

Первый шаг

Выбор очередной переменной для включения в множество S производится с помощью условия:

Второй шаг

Третий шаг

Выбираем очередную переменную:

Четвертый шаг

Выбираем очередную переменную:

Пятый шаг

Выбираем очередную переменную:

Шестой шаг

Выбираем очередную переменную:

Седьмой шаг

Выбираем очередную переменную:

Восьмой шаг

Выбираем очередную переменную:

Девятый шаг

Во множестве G_S нет элементов, которые могут быть введены в множество S без нарушения ограничения , то полученное решение L_s принимается в качестве первого приближенного решения L₀.

Так как все вершины дерева, для которых выполняется условие Q_s£ L₀, из дальнейшего рассмотрения исключаются, а так же данный набор параметров обеспечивает максимальную вероятность, то процесс расчета прекращается. Результаты всех расчетов приведены в табл. 1.

Таблица 1

№	S	Es	Gs	Рs	xr	Рs(xr)	Рs( r)	L0
	ø	ø	1-10	0.668	x1	0.668	0.526
	x1	ø	2-10	0.668	x2	0.668	0.604
	x1, x2	ø	3-10	0.668	x3	0.668	0.636
	x1, x2, x3	ø	4-10	0.668	x4	0.668	0.57
	x1, x2, x3, x4	ø	5-10	0.668	x5	0.668	0.602
	x1, x2, x3, x4, x5	ø	6-10	0.668	x6	0.668	0.624
	x1, x2, x3, x4, x5, x6	ø	7-10	0.668	x7	0.668	0.646
	x1, x2, x3, x4, x5, x6, x7	9,10	8,	0.668	x8	0.668	0.612
	x1, x2 , x3 , x4, x5,, x6 , x7, x8	9,10	ø	-	-	-	-	0.66

Таким образом, в состав контролируемых параметров входит набор X₁; X₂; X₃: X₄; X₅; X₆; X₇; X₈ или, если смотреть первоначальную нумерацию X₂; X₃; X₄; X₆; X₇; X₈; X₉; X₁₀.

1.3 Программные расчеты и сравнение результатов

Наряду с ручным расчётом, решение задачи реализовано с помощью программного алгоритма, написанного на языке программирования Delphi 7.0.

Листинг программы представлен в приложении 1.

Результаты программного расчёта сохраняются в текстовый файл kr1.txt и представлены на рисунке 1 для первых 4-ёх шагов, а итоговое решение на рисунке 2.

Рис. 1. Результат работы программы для 4-х шагов

Рис.2. Результат работы программы

Результаты программы и результаты ручного расчета совпали.