Белорусский национальный технический университет
Repository of the Belarusian National Technical University
ISSN: 2310-7405
Repository of the Belarusian National Technical University
View Item 
  •   Repository BNTU
  • Сериальные издания
  • Наука и Техника
  • 2021
  • № 2
  • View Item
  •   Repository BNTU
  • Сериальные издания
  • Наука и Техника
  • 2021
  • № 2
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

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

Thumbnail
DOI
10.21122/2227-1031-2021-20-2-179-184
Authors
Матвеева, Л. Д.
Date
2021
Publisher
БНТУ
Another Title
Direct Method for Solving Bilinear Programming Problem
Bibliographic entry
Матвеева, Л. Д. Прямой метод решения задачи билинейного программирования = Direct Method for Solving Bilinear Programming Problem / Л. Д. Матвеева // Наука и техника. – 2021. – № 2. – С. 179-184.
Abstract
Рассматривается задача билинейного программирования, в которой столбец, соответствующий одной из переменных величин, не фиксированный, а может выбираться из некоторого выпуклого множества. Данная задача известна как задача Данцига – Вулфа. Раннее предлагался модифицированный опорный метод ее решения, использующий декомпозицию ограничений задачи метода Данцига – Вулфа. Автором статьи разработан прямой точный метод решения сформулированной задачи. Метод основан на идее решения задачи линейного программирования с обобщенными прямыми ограничениями и на общей концепции адаптивного метода решения задачи линейного программирования. Введены понятия опоры, опорного плана, оптимального и субоптимального (Ԑ-оптимального) плана, который является заданным приближением по целевой функции к оптимальному плану задачи. Сформулированы и доказаны критерии оптимальности и субоптимальности опорного плана. Поиск оптимального решения основан на идее максимизации приращения целевой функции. Данный подход позволяет полнее учитывать основную цель и структуру задачи. Улучшение опорного плана состоит из двух частей: замены плана и замены опоры. Для поиска подходящего направления решается специальная производная задача с учетом основных ограничений задачи. Замена опоры основана на поиске оптимального плана двойственной задачи. За конечное число итераций (в случае невырожденности) метод приводит к оптимальному решению задачи.
Abstract in another language
The bilinear programming problem is considered, where a column, which corresponds to one of the variables, is not fixed but can be chosen from a convex set. This problem is known as the Dantzig – Wolfe problem. Earlier, a modified support method was proposed to solve the problem, using the decomposition of the problem constraints of the Dantzig – Wolfe method. The author of the paper has developed a direct exact method for solving the formulated problem. The method is based on the idea of the solving a linear programming problem with generalized direct constraints and a general concept of an adaptive solution method. The notions of support, support plan, optimal and suboptimal (Ԑ-optimal) plan are introduced which is a given approximation of the objective function to the optimal plan of the problem. Criteria for optimality and suboptimality of the support plan have been formulated and have been proved in the paper. The search for the optimal solution is based on the idea of maximizing the increment of the objective function. This approach allows more fully to take into account the main target and structure of the problem. Improving a support plan consists of two parts: replacing the plan and replacing the support. To find a suitable direction, a special derived problem is solved while taking into account the main constraints of the problem. The replacement of the support is based on the search for the optimal plan of the dual problem. The method leads to an optimal solution to the problem in a finite number of iterations (in the case of a non-degenerate value).
URI
https://rep.bntu.by/handle/data/90022
View/Open
Статья (424.2Kb)
Collections
  • № 2[12]
Show full item record
CORE Recommender

Belarusian National Technical University | Science Library | About Repository | Размещение в Репозитории | Contact Us
Яндекс.МетрикаIP Geolocation by DB-IP
Science Library | About Repository | Размещение в Репозитории | Contact Us
 

Browse

All of Repository BNTUCommunities & CollectionsAuthorsTitlesBy Issue DatePublisherBy Submit DateTypeThis CollectionAuthorsTitlesBy Issue DatePublisherBy Submit DateType

My Account

LoginRegister

Belarusian National Technical University | Science Library | About Repository | Размещение в Репозитории | Contact Us
Яндекс.МетрикаIP Geolocation by DB-IP
Science Library | About Repository | Размещение в Репозитории | Contact Us