УДК 004.021
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ДВОЙСТВЕННОГО СИМПЛЕКС-МЕТОДА
Р.С. Фоменко студент гр. 345А
Национальный аэрокосмический университет им. Н.Е. Жуковского "ХАИ"
В последнее время в прикладной математике большое внимание уделяется классу задач оптимизации, заключающихся в нахождении в заданной области точек наибольшего или наименьшего значения некоторой функции, которая зависит от большого числа переменных. Такие задачи возникают в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства («Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», «Транспортная задача» и т.д.). Для их решения используются различные методы линейного программирования, программная реализация которых является в данный момент актуальной задачей.
Одним из методов линейного программирования является двойственный симплекс-метод. Как и симплекс-метод, он используется при нахождении решения задачи линейного программирования, записанной в канонической форме, для которой среди векторов, составленных из коэффициентов при неизвестных в системе уравнений, имеется m единичных. Вместе с тем двойственный симплекс-метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными)Двойственный симплекс-метод удобен тем, что его можно применять в том случае, когда решается не одна, а несколько задач линейного программирования с возрастающим количеством дополнительных ограничений.
В результате исследований был разработан программный продукт, в котором реализован алгоритм двойственного симплекс-метода для решения задачи линейного программирования. Он позволил значительно уменьшить размеры симплексной таблицы и количество преобразований системы ограничений.
Список используемых источников
1. Карташов, А.В. Методы условной оптимизации [Текст] / А.В. Карташов, А.В. Бабкина, РА. Пудпо // Комп'ютерні системи та інформаційні технології: сб. науч. тр. Над. аэрокосм, ун-та им. Н.Е. Жуковского «ХАИ». - С. 37-94.
Нет похожих статей