Метод проектирования и приращений при решении задач линейного программирования

В настоящее время проблема выбора оптимального решения является одной из самых важных и актуальных проблем в промышленности, экономике, сельском хозяйстве и военной сфере. Для решения многих прикладных задач оптимизации применяются методы и подходы теории линейного программирования. Основной метод линейного программирования – симплекс-метод – характеризуется большим объемом вычислительных действий и процедур. Поэтому для решения данной проблемы используются модификации основного метода, обладающие более высокой алгоритмической эффективностью. В данной статье разработан новый метод решения задач линейного программирования. Меньшая, чем у симплекс-метода, алгоритмическая сложность обеспечивается рассмотрением класса задач с полностью ограниченными областями допустимых решений. Новый метод обоснован результатами, анонсированными в доказанных утверждениях. Реализация метода описана двумя алгоритмами: 1) поиск квазиоптимального решения с помощью анализа координат проекций на гиперплоскости (алгоритм проектирования); 2) поиск оптимального решения путем задания приращений ограничениям (алгоритм приращений). Для пояснения работы алгоритмов рассмотрены конкретные числовые примеры. Оценка алгоритмической сложности разработанного метода осуществляется подсчетом количества использованных арифметических операций. Получены формульные выражения для расчета сложности вычислений.

1. Жевнеров В.А. Модификация симплекс-метода на основе принципа эволюции. Проблемы управления. 2004;1:28–31.

2. Базилевский М.П. Отбор информативных регрессоров с учетом мультиколлинеарности между ними в регрессионных моделях как задача частично-булевого линейного программирования. Моделирование, оптимизация и информационные технологии. 2018;2(22):104–118.

3. Базилевский М.П. Сведение задачи отбора информативных регрессоров при оценивании линейной регрессионной модели по методу наименьших квадратов к задаче частично-булевого линейного программирования. Моделирование, оптимизация и информационные технологии. 2018;1(20):108–117.

4. Сумин В.И., Кузнецова Л.Д., Лукин М.А. Определение коэффициентов математической модели управления качеством обучения методом линейного программирования. Моделирование, оптимизация и информационные технологии. 2018;3(22):214–222.

5. Шаповалов А.В., Преображенский А.П., Чопоров О.Н. Возможности применения методов оптимизации в управлении портфелями проектов. Моделирование, оптимизация и информационные технологии. 2020;8(1).

6. Жилина А.А., Кострова В.Н., Преображенский Ю.П. Разработка методики постановки задачи выбора управленческого решения на основе оптимизационного подхода. Моделирование, оптимизация и информационные технологии. 2018;6(1):243–253.

7. Ганичева А.В., Ганичев А.В. Математическое программирование. СПб.: Лань; 2020. 88 с.

8. Хасанов А.С. Об особенностях алгоритмов решения задач линейного программирования с неограниченными областями допустимых решений. Вестник Московского государственного областного университета. Серия: Физика-математика. 2017;1:113–123.

9. Ганичева А.В., Ганичев А.В. Метод решения некоторых классов оптимизационных задач. Моделирование, оптимизация и информационные технологии. 2019;7(2):43–54.

10. Березнев B.А. О полиномиальной сложности одной модификации симплекс-метода. Журнал вычислительной математики и математической физики. 2004;44(7):1244–1260.