Решение задач линейного программирования приведением к виду с очевидным ответом

В статье рассматривается способ решения задачи линейного программирования (ЗЛП), которая требует найти минимум или максимум линейного функционала на множестве неотрицательных решений системы линейных алгебраических уравнений с теми же неизвестными. Способ получен при усовершенствовании классического симплекс-метода, который, привлекая геометрические соображения фактически обобщает метод полных исключений Гаусса решения систем уравнений. Предлагаемый способ, как и метод полных исключений, исходит из чисто алгебраических соображений. Он заключается в преобразовании всей ЗЛП, включая целевую функцию, в эквивалентную задачу с очевидным ответом. Ради удобства преобразования целевого функционала, уравнения записываются как линейные функционалы в левой части и нули в правой. Из коэффициентов упомянутых функционалов составляется матрица, которая называется матрицей ЗЛП. Нулевая строка матрицы -- коэффициенты целевого функционала, $a_{00}$ -- его свободный член. Описание и обоснование алгоритмов ведется в терминах преобразования этой матрицы. При вычислениях матрица является расчетной таблицей. Рассматриваемый метод, по аналогии с симплекс-методом, состоит из трех этапов. На первом этапе матрица ЗЛП приводится к специальному 1-каноническому виду. При таких матрицах одно из базисных решений системы очевидно, и на нем целевой функционал равен $a_{00}$, что очень удобно. На втором этапе полученная матрица преобразуется в аналогичную матрицу с неположительными элементами нулевого столбца (кроме $a_{00}$), что влечет неотрицательность базисного решения. На третьем этапе матрица преобразуется в матрицу, обеспечивающую неотрицательность и оптимальность базисного решения. Для второго этапа, аналог которого в симплекс-методе использует искусственный базис и является наиболее трудоемким, приводятся два варианта без искусственных переменных. При описании первого из них, попутно, получен очень простой для понимания и запоминания аналог знаменитой леммы Фаркаша. Другой вариант совсем прост в применении, но его полное обоснование сложно и будет опубликовано отдельно.

линейное программирование, метод Гаусса, симплекс-метод, матрица ЗЛП, разрешающий элемент, правило выбора, лемма Фаркаша, системы линейных уравнений, неотрицательное решение

1. S. I. Gass, Linear Programming: Methods and Applications. McGraw-Hill: New York, 1958.

2. A. Schrijver, Theory of linear and integer programming. Moscow: Mir, 1991.

3. D. B. Yudin and E. G. Holstein, Linear Programming: Theory and finite methods . Moscow: Fizmatlit, 1963.

4. G. B. Dantzig, Linear Programming and Extensions. Princeton University Press, 1963.

5. T. S. Hu, Integer programming and network flows. Addison-Wesley , 1969.

6. S. A. Ashmanov, Linear Programming. Moscow: Nauka, 1981.

7. C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithms and complexity. Prentice-Hall, 1982.

8. F. P. Vasiliev and A. Y. Ivanitsky, Linear Programming. MCCME, 2020.

9. E. Stiefel, “Note on Jordan elimination, linear programming and Tchebycheff approximation,” Numerische Mathematik, vol. 2, no. 1, pp. 1-17, 1960.

10. S. I. Zukhovitsky and L. I. Avdeeva, Linear and Convex Programming . Moscow: Nauka, 1967.

11. A. Charnes, “Optimality and degeneracy in linear programming,” Econometrica: Journal of the Econometric Society, vol. 20, no. 2, pp. 160-170 , 1952.

12. R. G. Bland, “New finite pivoting rules for the simplex method,” Mathematics of Operations Research, vol. 2, no. 2, pp. 103-107, 1977.

13. H. W. Kuhn, Class Notes. Princeton University, 1976.

14. A. S. Barsov, What is Linear Programming . Moscow: Fizmatgiz, 1959.

15. V. G. Karmanov, Mathematical Programming. Moscow: Fizmatlit, 2004.

16. Y. G. Evtushenko, A. A. Tret'yakov, and E. E. Tyrtyshnikov, “New approach to Farkas' theorem of the alternative ,” in Doklady Mathematics , 2019, vol. 99 , pp. 208-210.

17. G. D. Stepanov, “A Simple Algorithm for Finding a Non-negative Basic Solution of a System of Linear Algebraic Equations,” Modeling and analysis of information systems, vol. 28, no. 3, pp. 234-237 , 2021.