ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

GRAPHICAL METHOD FOR SOLVING LINEAR PROGRAMMING PROBLEMS

Ilicheva Nina Alekseevna

Student, Faculty of Engineering and Economics, Ulyanovsk State Technical University (USTU),

Russia, Ulyanovsk

Kireev Sergey Vladimirovich

Scientific Advisor, Candidate of Physical and Mathematical Sciences, Associate Professor, Associate Professor of the Department of Higher Mathematics, Ulyanovsk State Technical University (USTU),

Russia, Ulyanovsk

АННОТАЦИЯ

В статье рассматривается графический метод решения задач линейного программирования. Раскрываются сущность и геометрическая интерпретация метода, алгоритм построения области допустимых решений, поиск оптимального решения в вершинах многоугольника, а также возможные исходы задачи. Приводятся преимущества, недостатки графического метода и его практическое применение в экономике и менеджменте для оптимизации ресурсов и планирования производства. Статья предназначена для студентов экономических специальностей.

ABSTRACT

The article discusses the graphical method of solving linear programming problems. The essence and geometric interpretation of the method, the algorithm for constructing the domain of admissible solutions, the search for the optimal solution at the vertices of the polygon, and the possible outcomes of the problem are revealed. The advantages, disadvantages of the graphical method, and its practical application in economics and management for optimizing resources and planning production are presented. The article is intended for students of economic specialties.

Ключевые слова: линейное программирование, графический метод, область допустимых решений, целевая функция, оптимальное решение, вершины многоугольника, геометрическая интерпретация, система ограничений, математическая оптимизация, экономико-математические методы.

Keywords: linear programming, graphical method, feasible solution set, objective function, optimal solution, polygon vertices, geometric interpretation, constraint system, mathematical optimization, economic and mathematical methods.

Линейное программирование является разделом математического программирования, который изучает способы оптимизации линейной целевой функции с учётом системы линейных ограничений. Линейная функция называется целевой, а набор условий, оформленных уравнениями или неравенствами, определяет количественные связи между переменными и формулирует требования задачи, которые вместе составляют систему ограничений.

Главная задача линейного программирования -  найти максимальное или минимальное значение целевой функции при данных условиях [4, с. 95]. Общая форма задачи линейного программирования выглядит так:

 при ограничениях:

Здесь:

, , ...,  - переменные задачи;

c_j - коэффициенты целевой функции;

a_ij - коэффициенты ограничений;

b_i  - свободные члены ограничений [1, с. 24].

Методы линейного программирования часто используются в экономике и менеджменте, например, при распределении ресурсов и планировании, производства и оптимизации затрат и максимизации прибыли [4, с. 96].

Сущность графического метода. Графический метод является одним из самых простых и наглядных способов решения задач линейного программирования. Он используется для задач с двумя переменными, так как их можно показать на координатной плоскости [1, с. 26]. Суть метода заключается в геометрическом представлении системы ограничений и нахождении точки области допустимых решений, где целевая функция принимает оптимальное значение. Каждое ограничение в задаче линейного программирования можно выразить как линейное неравенство. Такое неравенство на координатной плоскости создаёт полуплоскость, которую ограничивает прямая линия [2].Область допустимых решений формируется пересечением всех полуплоскостей и включает в себя каждое возможное решение.

Геометрическая интерпретация задачи. Если задача состоит из двух переменных x₁ и x₂ , то её можно нарисовать на плоскости x₁Ox₂. Каждое неравенство a_i1x₁+a_i2x₂ ≤ b_i задаёт на графике  полуплоскость - то есть все точки, которые лежат по одну сторону от какой-то прямой. А если взять равенство a_i1x₁+a_i2x₂ = b_i, то получится та самая прямая - граница [3]. Область пересечения всех полуплоскостей называется областью допустимых решений. Эта область представляет собой выпуклый многоугольник или неограниченную область на координатной плоскости [1, с. 28]. Любая точка из этой области - это допустимое решение. А оптимальным называется то решение, которое даёт самое большое (или самое маленькое) значение целевой функции. Согласно теореме линейного программирования, если оптимальное значение существует, то оно обязательно находится в одной из вершин (углов) этой области. Поэтому искать его проще всего среди вершин [4, с. 99].

Алгоритм решения задачи графическим методом. Решение задачи линейного программирования графическим методом осуществляется в несколько этапов.

1. Запись системы ограничений. Сначала формируется математическая модель задачи, включающая целевую функцию и систему линейных ограничений [1, с. 27].
2. Построение граничных прямых. Каждое неравенство заменяется соответствующим равенством, полученная линейная функция изображается графически в виде прямой линии на плоскости.
3. Определение допустимых полуплоскостей. Для каждого ограничения определяется та часть плоскости, в которой выполняется соответствующее неравенство.
4. Построение области допустимых значений. Пересечение всех полуплоскостей образует область допустимых решений задачи [2].
5. Построение линии уровня целевой функции. Целевая функция представляется как семейство параллельных прямых c₁x₁ + c₂x₂ = C; где C - некоторое постоянное значение.
6. Определение оптимального решения. Линия уровня перемещается параллельно самой себе до тех пор, пока она не коснётся области допустимых решений. Точка касания определяет оптимальное решение задачи [1, с. 30].
7. Определение координат точки экстремума и соответствующего значения целевой функции. Для установления координат оптимальной точки решаем систему уравнений прямых, пересечение которых образует данную точку. Искомое оптимальное значение получается после подстановки полученных координат в целевую функцию.

Возможные исходы решения задачи. При использовании графического метода могут возникать различные ситуации:

• Единственное оптимальное решение – искомая точка экстремума находится в одной из вершин допустимого множества.
• Множество оптимальных решений - оптимум достигается на некотором участке границы области.
• Отсутствие допустимых решения - система ограничений несовместима.
• Неограниченность целевой функции - значение целевой функции может неограниченно возрастать/убывать при сохранении всех ограничений [3].

Преимущества и недостатки графического метода.

Преимущества:

• Возможность геометрической интерпретации задачи.
• Наглядность и простота понимания: решение представлено в виде чертежа, что позволяет увидеть соотношение переменных с помощью геометрических образов.
• Удобство при решении учебных задач, так как данный метод не требует сложных расчётов.

Недостатки:

• Применим только к задачам с двумя переменными. Решения задач выполняются на плоскости, из-за чего число возможных переменных не может быть более двух.
• Не подходит для сложных задач с большим числом ограничений. Таким образом, графический метод имеет узкие рамки применения.

Практическое применение. С помощью задач линейного программирования решается широкий круг вопросов планирования экономических процессов, где ставится цель поиска наилучшего решения. В качестве целевой функции могут рассматриваться, например, прибыль от реализации (должна быть максимальной) или издержки производства (должны быть минимальными). Графический метод преимущественно используется в рамках учебных задач, так как он обеспечивает наглядность при изучении принципов оптимизации.

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

1. Гераськин М. И. Линейное программирование: учебное пособие. — Самара: Самарский университет, 2019. — 120 с. [электронный ресурс] - URL: https://repo.ssau.ru/jspui/bitstream/123456789/58685/1/Гераськин%20М.И.%20Линейное.pdf?ysclid=mp5qnm3h7l721949861  (дата обращения: 25.03.2026)
2. Графический метод решения задач линейного программирования // [электронный ресурс] - URL: https://bstudy.net/926954/tehnika/graficheskiy_metod_resheniya_zadach_lineynogo_programmirovaniya (дата обращения: 23.03.2026)
3. Графический метод решения задач линейного программирования // Лекция по информатике. [электронный ресурс] - URL: https://ronl.org/lektsii/informatika/875482/
4. Красс М. С., Чупрынов Б. П. Математические методы и модели для магистрантов экономики: учеб. пособие. — Санкт-Петербург: Питер, 2010. — 496 с. [электронный ресурс] - URL:  https://ditimaths.wordpress.com/wp-content/uploads/2018/02/krass_chuprynov.pdf (дата обращения: 22.03.2026)