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

Этот метод имеет ограниченную область применения. Этим методом можно решать следующие задачи:

  1. Задачи с двумя переменными, имеющими симметричную форму записи.
  2. Задачи с n переменными, имеющие каноническую форму записи, если выполняется условие n-r≤2, где n – число неизвестных, r – ранг системы линейных уравнений (1).

Задача типа 2 сводится к задаче типа 1, для чего нужно перейти от канонической к симметричной форме записи.

Рассмотрим решение задач типа 1.

Найти X=(x1,x2), который является решением (1), удовл. (2),

Графический метод решения задачи линейного программирования. - student2.ru

(2) x1≥0, x2≥0

и на котором целевая функция f(X)=c1x1+c2x2 (3) достигает экстремума (максимума или минимума).

Решение задачи содержит два этапа:

I. Построим ОДР

Графический метод решения задачи линейного программирования. - student2.ru

Графический метод решения задачи линейного программирования. - student2.ru

ОДР находится в 1-й координатной четверти

система (1) содержит линейные неравенства с двумя переменными

(7) Графический метод решения задачи линейного программирования. - student2.ru

Решением такого неравенства является любая пара чисел (x1;x2), которая при подстановке в (7) обращает его в верное числовое равенство.

На координатной плоскости (x1;x2) – точка .

Множество решений (7) – некоторое множество точек на x1Ox2.

Выясним, какую область на плоскости x1Ox2 образуют точки, которые являются решением ограничений (1) и (2).

Заменим неравенство (7) соответствующим ему равенством.

Графический метод решения задачи линейного программирования. - student2.ru - (8)

это уравнение определяет на плоскости x1Ox2 прямую линию. Эта линия делит плоскость x1Ox2 на 2 полуплоскости π1 и π2.

Утверждение. Точки одной из этих полуплоскостей являются решением

Графический метод решения задачи линейного программирования. - student2.ru , (*)

а точки другой полуплоскости являются решением неравенства Графический метод решения задачи линейного программирования. - student2.ru . (**)

Докажем это утверждение.

Доказательство:

Возьмём т. M1 (x1’, x2’), М1 Графический метод решения задачи линейного программирования. - student2.ru m

М0 – проекция т. М1

Графический метод решения задачи линейного программирования. - student2.ru ={x1’- x10; x2’- x20}

Графический метод решения задачи линейного программирования. - student2.ru

М0 Графический метод решения задачи линейного программирования. - student2.ru m; Графический метод решения задачи линейного программирования. - student2.ru

Выясним знак выражения Графический метод решения задачи линейного программирования. - student2.ru в зависимости от того, в какой из полуплоскостей (π12) находится данная точка.

т. Графический метод решения задачи линейного программирования. - student2.ru

Графический метод решения задачи линейного программирования. - student2.ru (*)

Знак выражения зависит от знака Графический метод решения задачи линейного программирования. - student2.ru

1) Графический метод решения задачи линейного программирования. - student2.ru

Графический метод решения задачи линейного программирования. - student2.ru

2) Графический метод решения задачи линейного программирования. - student2.ru

Тогда Графический метод решения задачи линейного программирования. - student2.ru

Графический метод решения задачи линейного программирования. - student2.ru

Графический метод решения задачи линейного программирования. - student2.ru

Для того, чтобы определить полуплоскость, в которой выполняются соответствующие неравенства, достаточно подставить в неравенство координаты какой-либо одной точки, не лежащей на граничной прямой.

Если неравенство удовлетворяется, то областью решения будет полуплоскость, в которой находится эта точка; если нет – то в другой.

Чтобы построить ОДР на координатной плоскости x10x2, нужно построить граничные прямые и области решений каждого неравенства системы; пересечение областей решения этих неравенств, взятое в первом квадранте и будет областью решений данной задачи.

II. Нахождение ОДР оптимального решения задачи.

Рассмотрим уравнение Графический метод решения задачи линейного программирования. - student2.ru (3) При конкретном значении f это уравнение определяет на плоскости прямую линию. При изменении f мы получим семейство параллельных прямых (прямые ||, т.к. они все имеют один угловой коэффициент Графический метод решения задачи линейного программирования. - student2.ru ). Каждую из этих прямых называют линией уравнения, т.к. согласно равенству (3) на каждой такой прямой функция f сохраняет постоянное значение.

Графический метод решения задачи линейного программирования. - student2.ru

Графический метод решения задачи линейного программирования. - student2.ru - это вектор, перпендикулярный линиям уровня, и он показывает направление, по которому нужно перемещать линию уровня, чтобы значение f возрастало. Обозначим Графический метод решения задачи линейного программирования. - student2.ru

Определение.

Линия уровня, имеющая общие точки с ОДР и расположенная так, что ОДР целиком находится в одной из полуплоскостей, на которые данная линия уровня делит координатную плоскость, называется опорной прямой.

Чтобы найти ОДР оптимального решения, выполним:

1. Строим Графический метод решения задачи линейного программирования. - student2.ru в начале координат.

2. Перпендикулярно Графический метод решения задачи линейного программирования. - student2.ru проводим одну из линий уровня, имеющую общие точки с ОДР.

3. Перемещая эту линию уровня в направлении Графический метод решения задачи линейного программирования. - student2.ru в задаче на max или в противоположном направлении в задаче на min, находим опорную прямую.

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

Пример.

Графический метод решения задачи линейного программирования. - student2.ru

Решим совместно уравнения прямых BC и DC, и имеющих общую точку с опорной прямой, найдём оптимальное решение.

§5. Преобразование однократного замещения.

Пусть дана система линейных уравнений

(1) Графический метод решения задачи линейного программирования. - student2.ru

r<n (ранг системы)

Приведём эту систему к разрешённому виду методом Жордано-Гаусса и выпишем общее решение системы (общее решение системы – это формулы, выражающие базисные неизвестные через свободные).

Общее решение

(1’) Графический метод решения задачи линейного программирования. - student2.ru

Положив в этих формулах значение всех свободных неизвестных, равных нулю, мы найдём базисное решение системы.

Графический метод решения задачи линейного программирования. - student2.ru

Исходная система (1) будет иметь не одно базисное решение, т.к. из n неизвестных можно составить разные наборы из r неизвестных, но не каждый такой набор из r неизвестных можно взять за базисные неизвестные, т.к. среди r векторов коэффициентов при этих неизвестных могут быть линейно зависимые и, следовательно, базиса из них составить нельзя. Если мы знаем какое-либо одно базисное решение, то, преобразовав систему от одного единичного базиса к другому, можем найти любое другое базисное решение системы.

Пример.

Дана система линейных уравнений, приведённая к единичному базису. Требуется преобразовать её к какому-либо другому единичному базису.

Графический метод решения задачи линейного программирования. - student2.ru Графический метод решения задачи линейного программирования. - student2.ru Графический метод решения задачи линейного программирования. - student2.ru Графический метод решения задачи линейного программирования. - student2.ru Графический метод решения задачи линейного программирования. - student2.ru

Базисные неизвестные x1 x2 x3 x4 x5 bi Базисное решение
x1,x4,x5       -3   Графический метод решения задачи линейного программирования. - student2.ru Графический метод решения задачи линейного программирования. - student2.ru         Графический метод решения задачи линейного программирования. - student2.ru Графический метод решения задачи линейного программирования. - student2.ru
    Графический метод решения задачи линейного программирования. - student2.ru   -3 Графический метод решения задачи линейного программирования. - student2.ru Графический метод решения задачи линейного программирования. - student2.ru           Графический метод решения задачи линейного программирования. - student2.ru  
x3,x4,x5 Графический метод решения задачи линейного программирования. - student2.ru Графический метод решения задачи линейного программирования. - student2.ru                         Графический метод решения задачи линейного программирования. - student2.ru Графический метод решения задачи линейного программирования. - student2.ru

Для того чтобы найти какой-либо другой единичный базис, возьмём за разрешающий элемент любой неравный нулю коэффициент при каком-либо свободном неизвестном и выполним одну итерацию методом Жордано-Гаусса.

Свободное неизвестное x3 стало базисным, а базисное неизвестно x1 стало свободным. Такое преобразование называется преобразованием однократного замещения, т.к. произошло замещение базисного неизвестного x1 свободным неизвестным x3. Т.о. данная система уравнений преобразована к новому единичному базису, в котором вектор-коэффициенты при x3,x4,x5. Последовательно выполняя преобразования однократного замещения, можно найти все базисы векторов коэффициентов и все базисы решений данной системы.

Замечание.

Для данной системы уравнений нельзя в качестве базисных неизвестных взять набор x1,x2,x4, т.к. им соответствуют вектор-коэффициенты Графический метод решения задачи линейного программирования. - student2.ru , которые линейно зависимы, т.к. А12-3А4=θ.

Наши рекомендации