Preview

НАУКА и ТЕХНИКА

Расширенный поиск

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

https://doi.org/10.21122/2227-1031-2021-20-2-179-184

Полный текст:

Аннотация

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

Об авторе

Л. Д. Матвеева
Белорусский национальный технический университет
Беларусь

Кандидат физико-математических наук, доцент

Адрес для переписки: Матвеева Людмила Дмитриевна – Белорусский национальный технический университет, ул. Б. Хмельницкого, 9, корп. 11, 220013, г. Минск, Республика Беларусь. Тел.: +375 17 292-82-73
millamatveeva@gmail.com



Список литературы

1. Орлов, А. В. Биматричные игры и билинейное программирование / А. В. Орлов, А. С. Стрекаловский. М.: Физматлит, 2007. 223 с.

2. Васин, А. А. Теория игр и модели математической экономики / А. А. Васин, В. В. Морозов. М.: МГУ, 2005. 278 с.

3. Мухамадиев, Б. М. О решении задачи билинейного программирования и отыскания всех ситуаций равновесия в билинейных матричных играх / Б. М. Мухамадиев // Журнал вычислительной математики и математической экономики. 1978. Т. 18, № 2. С. 211–240.

4. Габасов, Р. Методы линейного программирования: в 3 ч. / Р. Габасов, Ф. М. Кириллова. Минск: Изд-во БГУ, 1980. Ч. 3. 368 с.

5. Орлов, А. В. Численное решение задач билинейного программирования / А. В. Орлов // Журнал вычислительной математики и математической физики. 2008. Т. 48, № 2. С. 237–254.

6. Данцинг, Дж. Линейное программирование, его применение и обобщение / Дж. Данцинг. М.: Прогресс, 1964. 600 с.

7. Габасов, Р. Методы линейного программирования: в 3 ч. / Р. Габасов, Ф. М. Кириллова. Минск: Изд-во БГУ, 1977. Ч. 1. 176 с.

8. Габасов, Р. Методы линейного программирования: в 3 ч. / Р. Габасов, Ф. М. Кириллова. Минск: Изд-во БГУ, 1978. Ч. 2. 240 с.

9. Матвеева, Л. Д. Об одной задаче билинейного программирования / Л. Д. Матвеева // Материалы 53-й Междунар. науч.-техн. конф. Минск: БГПА, 1999. Ч. 2. 340 с.

10. Матвеева, Л. Д. Решение задачи билинейного программирования с переменным вектором условий / Л. Д. Матвеева // Наука – образованию, производству, экономике: материалы II Междунар. науч.-техн. конф.: в 4 т. Минск: БНТУ, 2011. Т. 3. С. 375.


Для цитирования:


Матвеева Л.Д. Прямой метод решения задачи билинейного программирования. НАУКА и ТЕХНИКА. 2021;20(2):179-184. https://doi.org/10.21122/2227-1031-2021-20-2-179-184

For citation:


Matveyeva L.D. Direct Method for Solving Bilinear Programming Problem. Science & Technique. 2021;20(2):179-184. (In Russ.) https://doi.org/10.21122/2227-1031-2021-20-2-179-184

Просмотров: 28


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2227-1031 (Print)
ISSN 2414-0392 (Online)