Прямой метод решения задачи билинейного программирования

Abstract

Рассматривается задача билинейного программирования, в которой столбец, соответствующий одной из переменных величин, не фиксированный, а может выбираться из некоторого выпуклого множества. Данная задача известна как задача Данцига – Вулфа. Раннее предлагался модифицированный опорный метод ее решения, использующий декомпозицию ограничений задачи метода Данцига – Вулфа. Автором статьи разработан прямой точный метод решения сформулированной задачи. Метод основан на идее решения задачи линейного программирования с обобщенными прямыми ограничениями и на общей концепции адаптивного метода решения задачи линейного программирования. Введены понятия опоры, опорного плана, оптимального и субоптимального (Ԑ-оптимального) плана, который является заданным приближением по целевой функции к оптимальному плану задачи. Сформулированы и доказаны критерии оптимальности и субоптимальности опорного плана. Поиск оптимального решения основан на идее максимизации приращения целевой функции. Данный подход позволяет полнее учитывать основную цель и структуру задачи. Улучшение опорного плана состоит из двух частей: замены плана и замены опоры. Для поиска подходящего направления решается специальная производная задача с учетом основных ограничений задачи. Замена опоры основана на поиске оптимального плана двойственной задачи. За конечное число итераций (в случае невырожденности) метод приводит к оптимальному решению задачи.