Прямо-двойственный метод решения задачи энтропийно-линейного программирования

А. В. Чернов

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: Задачи энтропийно-линейного программирования часто возникают в различных приложениях (транспортные задачи, исследования химических реакций и др.). Такие задачи формулируются обычно как задачи максимизации энтропии (или минимизации минус энтропии) с аффинными ограничениями и линейными ограничениями-неравенствами. В работе исследуется метод решения такой задачи, в основе которого лежит решение двойственной задачи с восстановлением решения прямой задачи: каждой точке в двойственном пространстве, вычисляемой методом, ставится в соответствие определенная точка в прямом. Для указанного метода получена верхняя оценка числа итераций, необходимого для достижения решения с заданной точностью. Изложенный метод применим также к более широкому классу сильно выпуклых функционалов с аналогичным допустимым множеством.

Ключевые слова: энтропийно-линейное программирование, быстрый градиентный метод, двойственная задача, прямо-двойственный метод.