Сущность и особенности выполнения метода динамического программирования. Решение математической задачи, принцип оптимальности по затратам, ручной счёт и листинг программы. Применение метода ветвей и границ, его основные преимущества и недостатки.
Аннотация к работе
Выбор параметров контроля с использованием метода динамического программирования и метода ветвей и границ при непересекающихся элементах объекта контроля и ограничениях по затратам на контроль С?16.Проверка всех параметров из S влечет контроль всех N элементов системы и дает однозначный ответ: объект исправен, если все N элементов исправны, или неисправен, если по крайней мере один из элементов отказал. Для "xi определено подмножество R(xi) элементов, проверяемых при контроле i-го параметра, причем предполагаем, что эти подмножества могут пересекаться, т.е. Тогда вероятность того, что отказ будет обнаружен при проверке k-го параметра, можно вычислить по формуле: Qk=?Pk Рассмотрим наряду с интересующей нас исходной задачей множество аналогичных задач f(Y)=max ?(x), Y Є [0,C], ХЄХУ где через XY обозначено множество неотрицательных целочисленных векторов ?, отвечающих наборам, в которых общая стоимость проверки параметров не превосходит величины ?. При этом, если УКЄ ?l, то на данном шаге этот параметр исключается из рассмотрения, так как каждый параметр может включаться в набор не более одного раза.Первоначально ищут допустимый план и для каждого возможного варианта определяют верхнюю границу целевой функции. Ветви дерева возможных вариантов, для которых верхняя граница ниже приближенного решения, из дальнейшего рассмотрения исключают. Обозначим: U - множество переменных xj; S - множество фиксированных переменных, вошедших в допустимое решение; Es - множество зависимых переменных, которые не могут быть включены в множество S, так как для них выполняется неравенство aij> bi - ?aij•xj, i=1, …,m Если в процессе решения окажется, что во множестве GS нет элементов, которые могут быть введены во множество S без нарушения ограничения (5), то полученное решение Ls =?cj•xj принимается в качестве первого приближенного XJЄS решения L0. {exit;} end else begin for q:=1 to maxmatrix do if matrix[q]=nil then break;При решении поставленной задачи оба метода дали одинаковый результат, что показывает правильность понимания и выполнения курсовой работы.
План
Содержание
Задание
1. Метод динамического программирования
1.1 Теоретическая часть
2.2 Практическая часть
- ручной счет
- листинг программы
2. Метод ветвей и границ
2.1 Теоретическая часть
2.2 Практическая часть
- ручной счет
- листинг программы
Вывод
Литература
Вывод
При решении поставленной задачи оба метода дали одинаковый результат, что показывает правильность понимания и выполнения курсовой работы. Таким образом, необходимо использовать следующие параметры контроля: x9,x4,x10,x3,x7,x1,x2.
Метод динамического программирования достаточно прост для выполнения, но имеет существенный недостаток: при его использовании для счета вручную возникают вычислительные трудности даже для простых систем.
Метод ветвей и границ является более сложным для понимания, но он оказался проще при ручном счете. Недостатком является большая сложность программирования метода.
Список литературы
1. Селезнев А.В., Добрица Б.Т., Убар Р.Р. «Проектирование автоматизированных систем контроля бортового оборудования летательных аппаратов» стр. 90-95
2. Алексеев О.Г. «Комплексное применение методов дискретной оптимизации» стр. 18-25