Пусть дана задача линейного программирования в канонической форме

f (x) = ,

а_ij x_j = b_{i ,} i = 1: m, (6.8)

x_j ≥ 0, j = 1: n,

где число переменных на два больше числа ограничений − равенств, т.е. n - m = 2, причем ранг матрицы А = m. Тогда две переменные в указанной системе уравнений, скажем х ₁ и х ₂, являются свободными, т.е. через них можно выразить все остальные переменные:

, (6.9)

где − некоторые числа. Подставляя эти выражения в целевую функцию, получаем

f = γ₁ х ₁ + γ₂ х ₂ +δ, (6.10)

где γ₁, γ₂, δ − некоторые числа.

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

f = γ₁ х ₁ + γ₂ х ₂ → max,

Используя геометрические построения, находим ее решение (). Подставляя эти числа в (6.9), (6.10), получаем решение и значение исходной задачи (6.8).

Пример 6.2. Используя графический метод, найти решение

¦(х) = - х ₁ - 2 х ₂ ® min,

х ₁+2 х ₂ £ 7,

2 х ₁+ х ₂ £ 8,

х ₂ £ 3,

х ₁, х ₂ ³ 0.

Рис. 6.2. Допустимое множество задачи 6.2

Решение. Изобразим на плоскости (х ₁, х ₂) допустимое множество C данной задачи (многоугольник ABCDE, рис. 6.2) и одну из линий уровня - х ₁ -2 х ₂ = - 3 целевой функции ¦(х). Направление убывания ¦(x) указывает вектор l = (1,2). Совершая параллельный перенос линии уровня вдоль направления l, находим ее крайнее положение. В этом положении прямая - х ₁ - 2 х ₂ = - 3 проходит через сторону CD полиэдра ABCDE. Таким образом, все точки отрезка CD являются точками минимума функции ¦(х) на множестве X. Так как концы C и D этого отрезка имеют координаты (1,3) и (3,2) соответственно, то любая точка минимума функции ¦(х) представима в виде

где . Минимальное значение целевой функции ¦^*= ¦(х *) = –7.

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

Рис. 6.3. Неограниченное многоугольное множество

Решение. Допустимое множество этой задачи представляет собой неограниченное многоугольное множество (рис. 6.3). Функция f (x) убывает в направлении l = (1,2). При параллельном переносе линии уровня вдоль направления l она всегда пересекает множество Х, а целевая функция f (x) неограниченно убывает. Поэтому рассмотренная задача не имеет решений.

Пример 6.4. Найти максимальное значение функции

f (x) = -16 x ₁ - x ₂ + x ₃ + 5 x ₄ + 5 x ₅

при условиях:

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

Из целевой функции исходной задачи исключаем переменные x ₃, x ₄, x ₅ с помощью подстановки их значений из соответствующих уравнений системы ограничений. Получаем постановку задачи в стандартной форме:

f (x) = 2 x ₁ + 3 x ₂,

при условиях:

	Рис. 6.4. Многоугольник решений

Построим многоугольник решений полученной задачи (рис. 6.4). Как видно из рис. 6.4., максимальное значение целевая функция задачи принимает в точке С пересечения прямых I и II. Вдоль каждой из граничных прямых значение одной из переменных, исключенной при переходе к соответствующему неравенству, равно нулю. Поэтому в каждой из вершин полученного многоугольника решений последней задачи по крайней мере две переменные исходной задачи принимают нулевые значения. Так, в точке С имеем x ₃ = 0 и x ₄ = 0. Подставляя этизначения в первое и второе уравнения системы ограничений исходной задачи, получаем систему двух уравнений

решая которую, находим x ₁* = 3, x ₂* = 4.

Подставляя найденные значения x ₁ и x ₂ в третье уравнение системы ограничений исходной задачи, определяем значение переменной x ₅ равное 14.

Следовательно, оптимальным планом рассматриваемой задачи является x * = ( 3; 4; 0; 0; 14). При этом плане значение целевой функции есть _max = 18.