Целочисленное программирование

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

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

Модель целочисленной задачи линейного программирования:

(3.6)

(3.7)

(3.8)

(3.9)

Условие - условие целочисленности. Если n₁ = n, то задачу называют полностью целочисленной; если n₁ < n, то - частично целочисленной.

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

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

Метод ветвей и границ

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

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

Шаг 1. Задача линейного программирования решается без учета целочисленности. Если все компоненты оптимального плана целые, то он является оптимальным планом.

Шаг 2. Далее рассматривают одну из переменных x_j, на которую накладывают ограничение целочисленности, но которая получила дробное значение. На основе полученного решения составляют дополнительные ограничения:

х_j ≤ [ х_j ^*] и х_j ≥ [ х_j ^*] + 1,

где [ х_j ^*] - целая часть нецелочисленного значения переменной х_j в оптимальном решении.

Шаг 3. Из исходной задачи формируются две задачи линейного программирования, в каждую из которых вошли все исходные ограничения и одно из дополнительных.

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

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

- на одной из ветвей недопустимое решение;

- на одной из ветвей целочисленное решение. Тогда значение целевой функции сравнивается с (верхним - при max, нижним - при min); если полученное значение хуже, оно отбрасывается; если лучше, то принимается за граничное;

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

На первом цикле расчета

Пример 3. Решить задачу методом ветвей и границ.

Решение. В результате решения задачи симплекс-методом найдем оптимальное решение: , где верхний индекс переменных - номер задачи. В полученном решении х₂ - нецелочисленное. Поэтому для дальнейшего решения составляем две новые задачи с различными граничными условиями.

Задача 2 Задача 3

Результаты решения симплекс-методом

задачи 2: ; ;

задачи 3: .

В задаче 1 переменная х₁ = 1 - целочисленная, а в последующих задачах при целочисленности х₂ перестала быть целочисленной х₁. Затем следует накладывать ограничения целочисленности на х₁ и т. д. (рис. 3.4).

Рисунок 3.4 – Схема решения задачи ЛП методом ветвей и границ

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

Решение целочисленных задач с использованием MS Excel

Решение целочисленных задач с использованием MS Excel осуществляется аналогично, как и решение задач линейного программирования, с использованием пакета «Поиск решения». Отличие состоит в том, что для данного типа задач необходимо добавить ограничение целочисленности на используемые в задаче переменные. Это делается при добавлении ограничений (рис. 3.5). В диалоговом окне «Добавление ограничения» в поле «Ссылке на ячейку» ввести адреса ячеек, рядом ввести цел.

Рисунок 3.5 – Добавление условия целочисленности переменных

В диалоговом окне «Поиск решения», нажать кнопку Параметры, поставить флажок на Показывать результаты итераций (рис. 3.6), затем Выполнить.

Рисунок 3.6– Окно «Параметры поиска решения»

На экране появится результат решения на первой итерации и диалоговое окно «Текущее состояние поиска решения» (рис. 3.7).

Рисунок 3.7 – Окно «Текущее состояние поиска решения»

Щелкнуть Сохранить сценарий, затем Продолжить, ввести номер итерации как имя сценария, повторять до появления диалогового окна «Результат поиска решения» (рис. 3.8).

Рисунок 3.8 – Окно «Результаты поиска решения»

Для целочисленных задач возможен только Отчет по результатам (рис. 3.9).

Рисунок 3.9 – Отчет по результатам

Дата добавления: 2014-10-22