Линейное целочисленное программирование.
Метод ветвей и границ — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. Метод ветвей и границ относится к комбинаторным методам решения целочисленных задач и применим как к полностью, так и к частично целочисленным задачам.
Метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).
Ветвление производится последовательным введением дополнительных ограничений. Процедура ветвления состоит в разбиении области допустимых решений на подобласти меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево, называемое деревом поиска или деревом ветвей и границ. Узлами этого дерева являются построенные подобласти. Процедура нахождения оценок заключается в поиске верхних и нижних границ для оптимального значения на подобласти допустимых решений.
Каждая подзадача решается как задача линейного программирования с исходной целевой функцией. После конечного числа шагов будет найдено целочисленное оптимальное решение.
Для решения целочисленных задач оптимизации широкое применение находят различные средства Excel.
Основной командой для решения оптимизационных задач в Excel является команда Сервис/Подбор параметра. Эта команда определяет неизвестную величину, приводящую к требуемому результату.
Для решения сложных задач, требующих применения линейного и нелинейного программирования, а также методов исследования операций применяется надстройка - Поиск решения. Чтобы использовать надстройку Поиск решения не обязательно знать методы программирования и исследования операций, но необходимо определять, какие задачи можно решать этими методами. Общие свойства, которые характерны для задач, решаемых с помощью надстройки Поиск решения:
Существует единственная целевая ячейка, содержащая формулу, значение которой должно быть сделано максимальным, минимальным или же равным, какому-то конкретному значению.
Формула в этой целевой ячейке содержит ссылки на ряд изменяемых ячеек. Поиск решения заключается в том, чтобы подобрать такие значения переменных в изменяемых ячейках, которые бы обеспечили оптимальное значение для формулы в целевой ячейке.
Может быть задано некоторое количество ограничений — условий или соотношений, которым должны удовлетворять некоторые из изменяемых ячеек.
Постановка задачи
Первым шагом при работе с командой Поиск решения является создание специализированного листа. Для этого необходимо создать целевую ячейку, в которую вводится основная формула. Кроме того, лист может включать другие значения и формулы, использующие значения целевой и переменных ячеек. Формула в целевой ячейке должна опираться в вычислениях на значения переменных ячеек. После того, как задача оптимизации будет подготовлена на листе, можно приступать к работе. 1. Выделите на листе целевую ячейку, в которую введена формула. 2. Выполните команду Сервис/Поиск решения. Открывается окно диалога Поиск решения. Поскольку была выделена ячейка, в текстовом поле «Установить целевую ячейку» появится правильная ссылка на ячейку. В группе «Равной» переключатель по умолчанию устанавливается в положение «Максимальному значению».
3. Перейдите к полю "Изменяя ячейки" и введите переменные ячейки листа 4. Добавьте ограничения на переменные в изменяемых ячейках. Для ввода ограничений нажмите кнопку Добавить, чтобы задать первое ограничение в окне диалога, затем можно ввести второе, третье и т.д. 5. Когда оптимизационная задача будет готова к выполнению, можно нажать кнопку Выполнить для получения ответа. Появится окно диалога с описанием результатов процесса оптимизации. 6. Чтобы отобразить найденное решение в ячейках листа, установите переключатель "Сохранить найденное решение" и нажмите кнопку ОК. Найденная максимальная величина помещается в целевую ячейку, а переменные ячейки заполняются оптимальными значениями переменных, которые удовлетворяют установленным ограничениям.
При работе с командами Подбор параметра и Поиск решения не существует удобного способа сравнения результатов вычислений – при каждом изменении данных предыдущее значение пропадает. Чтобы устранить эти ограничения, разработчики Excel создали Диспетчер сценариев, помогающий работать с несколькими моделями «что – если». Командой Сервис/Сценарии можно создавать новые и просматривать существующие сценарии для решения задач, и отображать консолидированные отчеты. Решение задач с булевыми переменными
Под задачей целочисленного программирования понимается задача, в которой все или некоторые переменные должны принимать целые значения. В том случае, когда ограничения и целевая функция задачи представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования. В противном случае, когда хотя бы одна зависимость будет нелинейной, это будет целочисленной задачей нелинейного программирования.
Часто задачу целочисленного программирования решают без учета условий целочисленности переменных, а затем округляют полученное решение с избытком или недостатком. Это не гарантирует получение оптимального целочисленного решения задачи. Поэтому для нахождения оптимального решения целочисленных задач применяют специальные методы, в которых учитывается, что число возможных решений любой целочисленной задачи является конечным.
Понятие «булевая переменная» - это понятие является предметом изучения раздела математики – алгебра Буля, которая изучает высказывания и логические операции над высказываниями.
Высказыванием называется предложение, о котором имеет смысл утверждать, истинно оно или ложно. Множество всех высказываний разбивается на два класса: класс истинных высказываний (обозначается переменной «1») и класс ложных высказываний (обозначается переменной «0»).
Анализ задач с булевыми переменными.
В задачах с булевыми переменными могут быть выполнены все виды анализа. С точки зрения вариантного анализа наибольший практический интерес представляет структурный анализ, под которым понимается поиск оптимального решения при различных ограничениях.
Использование булевых переменных в задачах дискретного программирования.
С помощью булевых переменных можно решать еще один очень важный класс практических задач оптимизации. Суть задач этого класса заключается в том, что решением задачи оптимизации может быть не любое число в назначенных граничных условиях (неважно какое: целочисленное или непрерывное), а лишь такое число, которое входит в заданный набор возможных вариантов значений данной искомой переменной.
Дискретное программирование (дискретная оптимизация) — раздел программирования.
Задача дискретной оптимизации сводится к задача варианта сложного технического изделия на этапе его создания.
Задача дискретной оптимизации относится к классу трудно решаемых задач, т. е. допускает нахождение решения в общем случае только с помощью экспоненциальных алгоритмов, которые строятся на основе свойств целевой функции и ограничений. Наиболее эффективный метод поиска оптимального решения — это метод последовательного анализа и отсеивания вариантов, который является развитием метода "ветвей и границ" для задачи дискретной оптимизации с рекурсивно-монотонными функциями. Метод позволяет по анализу некоторого числа вариантов отсеивать большее число, последовательно уменьшая множество вариантов до размеров, удовлетворительных для использования прямого перебора.
Дискретные задачи оптимизации:
Размещение ( соединение, которое можно образовать из n элементов, собирая в каждое соединение по k элементов, при этом соединения могут отличаться друг от друга как самими элементами, так и порядком их расположения. Число всех возможных размещений равно n(n-1)(n-2)...(n-k+1));
Перестановка( соединение из n элементов, содержащее все n элементов, отличающееся от других соединений только порядком расположения элементов. Число всех возможных перестановок равно n!);
Сочетание ( соединение из n элементов по k, отличающееся от других только самими элементами (различие порядка их расположения во внимание не принимается). Число всех возможных сочетаний равно числу размещений, разделенному на число перестановок);