Метод ветвей и границ: пример задачи численного программирования. Общий алгоритм методов решения задач программирования. Описание программного продукта для решения задач разработанного на языке программирования С , в среде разработке C Builder 6.0.
Рассмотрим сначала простую практическую задачу, которая сводится к ЦЛП. Для удобства задачи, в которых все переменные должны быть целочисленными, называются полностью целочисленными, а задачи, в которых лишь некоторые переменные должны принимать целочисленные значения, - частично целочисленными.Методы решения задач целочисленного линейного программирования основаны на использовании вычислительных возможностей методов линейного программирования.Рассмотрим следующую задачу целочисленного линейного программирования. Так как оптимальное решение задачи ЛП0 не удовлетворяет условия целочисленности, метод ветвей и границ изменяет пространство решений задачи линейного программирования так, что в конечном счете получается оптимальное решение задачи целочисленного линейного программирования. Это эквивалентно замене исходной задачи ЛП0 двумя новыми задачами линейного программирования ЛП1 и ЛП2, которые определяются следующим образом: Пространство допустимых решений ЛП1 = пространство допустимых решений ЛП0 ( ), пространство допустимых решений ЛП2 = пространство допустимых решений ЛП0 ( ).Предположим, что рассматривается задача максимизации. Зададим нижнюю границу оптимального значения целевой функции z задачи ЦЛП равной -?. Шаг 1. Выбираем i-ю подзадачу линейного программирования ЛПІ для исследования.Для разработки программного продукта, использовался язык программирования C . Перед пользователем появится окно программы (Рис.5).
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
