(Нет отзывов)
29 страниц
2019-08-18

Модели целочисленного булевого программирования. Алгоритм последовательного анализа вариантов решения

В наличии
1640 ₽

Если прекратить вычисления непосредственно перед тем, как алгоритм сходится (т.е. еще тогда, когда основной список еще не пуст), то можно установить, какая часть из возможных решений подверглась перебору (явному или неявному). Для определения этого показателя после шагов 2 и 3 всякий раз возвращаются к шагу 1, подсчитывая значение дроби , где величина s равна числу переменных, содержащихся в частичном решении на шаге 1. Алгоритм частичного перебора можно модифицировать для решения частично целочисленных задач, в которых только переменные =1, j =1, 2, . . . , р (< n), должны быть равны нулю или единицы, а на остальные переменные наложено ограничение , j = р+1, . . ., n. Частичное решение должно включать только целочисленные переменные, однако к свободным переменным относятся любые переменные, не вошедшие в частичное решение. Проверка (1.9) и (1.10) сохраняются, если не считать того, что проверка (1.10) применяется только к свободным целочисленным переменным. Кроме того, вместо . Наконец, описание шага 5 изменяется следующим образом. Шаг 3. Если (расширенное) решение содержит все р целочисленные переменные, то нужно решить полученную задачу линейного программирования, отыскав тем самым соответствующие оптимальные значения остальных свободных переменных (при этом ограничения задачи линейного программирования формируются с учетом выбранных значений целочисленных переменных, вошедших в частичное решение). Если допустимого решения не существует, то принять = и вернуться к шагу 1. В противном случае необходимо зафиксировать полученное оптимальное решение, принять равным соответствующему оптимальному значению целевой функции и вернуться к шагу 1. Если (расширенное) частичное решение содержит менее р целочисленных переменных, перейти к шагу 4.

Введение . . . . . . . . . . . . . . . . . 5
1 Теоретическая часть. . . . . . . . . . . . 6
1.1 Метод частичного (неявного) перебора. .. . 6
1.1.1 Основные понятия . . . . . . . . . . . .6
1.1.2 Алгоритм частичного пер. . . . . . . . .10
1.2 Алгоритм частичного перебора для нелинейной задачи . . . . . . . .. . . . . .. . . . . . .11
2 Практическая часть . . . .. . . . . . . . .14
2.1 Постановка задачи. . . . . . . . . . . . .14
2.2 Решение задачи. . . . . . . . . . . . . . 14
Вывод . . . . . . . . . . . . . .. . . . . . .19
Список используемой литературы . . . . . . . 20
Приложения А . . . . . . . . . . . . . . . . .21
Приложение Б . . . . . . . . . . . . . . . . 28

1.Вагнер Г. Основы исследования операций, том2, М: Мир, 1973г., 488с.
2.Зайченко Ю.П. Исследования операций, Высшая школа, 1975г., 319с.
3.Зайченко Ю.П., Шумилова С.А. Исследования операций, Высшая школа, 1984г., 224с.

Список курсовых работ по предмету прикладная математика