17. Математическая модель задачи линейного программирования. Графическое решение задачи.

Составляющие математической модели

Основой для решения экономических задач являются математические модели.

Математической моделью задачи называется совокупность математических соотношений, описывающих суть задачи.

Составление математической модели включает:

• выбор переменных задачи
• составление системы ограничений
• выбор целевой функции

Переменными задачи называются величины Х1, Х2, Хn, которые полностью характеризуют экономический процесс. Обычно их записывают в виде вектора: X = (X1, X2, ..., Xn).

Системой ограничений задачи называют совокупность уравнений и неравенств, описывающих ограниченность ресурсов в рассматриваемой задаче.

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

В общем случае задача линейного программирования может быть записана в таком виде:

Данная запись означает следующее: найти экстремум целевой функции (1) и соответствующие ему переменные X=(X1, X2,...,Xn) при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3).

Допустимым решением (планом) задачи линейного программирования называется любой n-мерный вектор X=(X1, X2,...,Xn), удовлетворяющий системе ограничений и условиям неотрицательности.

Множество допустимых решений (планов) задачи образует область допустимых решений (ОДР).

Оптимальным решением (планом) задачи линейного программирования называется такое допустимое решение (план) задачи, при котором целевая функция достигает экстремума.

Задачу линейного программирования с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в пространствах, размерность которых больше трех, графическое решение, вообще говоря, невозможно.

P.S. Если ограничения и целевая функция содержит более двух переменных, тогда необходимо задачу линейного программирования решать симплекс-методом (или методом последовательного улучшения решения) - он универсален и им можно решить любую ЗЛП. Для некоторых прикладных задач линейного программирования, таких как транспортная задача, разработаны специальные методы решения.

Каждоеиз ограничений задает на плоскости x_1Ox_2некоторую полуплоскость. Их пересечение является областью допустимых решений задачи.

На представлены возможные ситуации, когда область допустимых решений задачи линейного программирования – выпуклый многоугольник(а), неограниченная выпуклая многоугольная область (б), единственная точка (в), прямая (г), пустое множество (д).

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

1. На плоскости X_1OX_2 строят прямые.
2. Определяются полуплоскости.
3. Определяют многоугольник решений;
4. Строят вектор N(c1, c2), который указывает направление целевой функции (grid, градиент и т.д.);
5. Передвигают прямую целевую функцию c1x2 + c2x2 = 0 в направлении вектора N до крайней точки многоугольника решений. (Прямая является перпендикуляром целевой функции, которую передвигают по её направлению, если находим максимум и против направления, если находим минимум).
6. Вычисляют координаты точки и значение целевой функции в этой точке.

При этом могут возникать следующие ситуации: