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

Геометрическая интерпретация решения задачи ЛП.

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

на множестве решений системы

Решение. Здесь - свободные переменные. Перепишем систему ограничений (1) в виде

Исходным базисным решением является решение (7; 0; 0; 12; 0; 10), при котором значение функции равно нулю. Целевая функция уже выражена через небазисные переменные. Значение целевой функции может быть уменьшено за счет увеличения. Среди коэффициентов при в системе (2) имеются отрицательные: и. Находим отношения (из второго уравнения системы (2)):. Элемент – разрешающий. Из старого базиса исключими введем в него из небазисных переменных. Для этого выразим через и из второго уравнения и найденное выражение подставим вместо в первое и третье уравнения системы (2), а также в выражение F.

Получим систему (3), где - свободные переменные.

Новое базисное решение имеет вид: (10; 0; 3; 0; 0; 1).. Значение F можно уменьшить за счет увеличения. Среди коэффициентов при в системе (3) только один отрицательный: Элемент разрещающий. Перейдем к новому базису:

Новое базисное решение имеет вид:, Дальнейшее уменьшение значения целевой функции невозможно.

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

Дана задача линейного программирования:

или в краткой форме:

Среди допустимых решений системы (1.2) найти то, которое обращает в максимум линейную форму (1.1).

Уравнение

на плоскости х₁Ох₂ определяет прямую, разбивающую всю плоскость на две полуплоскости, каждая из которых лежит по одну сторону от прямой. Прямая (1.4) называется граничной и принадлежит обеим полуплоскостям.

Координаты точек, лежащих в одной полуплоскости, удовлетворяют неравенству
,

а координаты точек, лежащих в другой полуплоскости, удовлетворяют неравенству

Следовательно, системе неравенств (1.2) удовлетворяет множество точек Х (х₁, х₂ ), лежащих в пересечении полуплоскостей, заданных неравенствами системы.

Пересечение конечного числа полуплоскостей есть некоторая выпуклая многоугольная область Ω, которая называется областью решения системы (1.2). Если система (1.2) противоречива, область Ω пуста. Поставленную задачу (1.1) - (1.3) можно теперь сформулировать следующим образом: среди всех точек многоугольной области Ω найти ту, которая обращает в максимум линейную форму

Выбрав произвольное с ₀, запишем уравнение прямой из семейства параллельных прямых, нормальных вектору

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

в положительном направлении вектора.

Очевидно, решением задачи на максимум линейной формы является наиболее удаленная крайняя точка, в которой прямая (1.8) встречается с областью Ω. Если же задача линейного программирования сформулирована на минимум линейной формы, то решением задачи будет первая точка, в которой прямая

встречается с областью Ω при параллельном перемещении в направлении вектора

Аналогично геометрически интерпретируется задача линейного программирования и в n -мерном пространстве

Каждое неравенство a_i1x₁+a_i2x₂+…+a_inx_n ≤ b_i определяет в n-мерном пространстве полупространство, состоящее из точек X(x₁, x₂, …x_n), расположенных по одну сторону от граничной гиперплоскости a_i1x₁+a_i2x₂+…+a_inx_n ≤ b_i и на самой этой гиперплоскости. Пересечение конечного числа полупространств есть выпуклая многогранная область Ω, которая является множеством всех решений системы ограничений записанной задачи.

Значение линейной формы в точке Х' (x'₁, x'₂, …, x'_n) можно рассматривать как уклонение точки Х'(x'₁, x'₂, …, x'_n) от гиперплоскости

= 0,

где под уклонением данной точки от гиперплоскости следует понимать число, полученное в результате подстановки в левую часть уравнения (1.9) вместо x₁, x₂, …, x_n координат точки Х'. Геометрическая интерпретация задачи линейного программирования заключается в отыскании на множестве решений Ω* такой крайней точки, которая наименее (наиболее) уклонена от гиперплоскости (1.9).

Схема решения задачи (1.1) - (1.3) графическим методом.

1. Записывают уравнения граничных прямых.

2. Строят графики граничных прямых на плоскости.

3. Выделяют область решения неравенств системы (1.2).

4. Строят многоугольник решений.

5. Строят график линейно формы (1.1).

6. Определяют экстремальную точку многоугольника.

7. Вычисляют значение линейной формы в полученной точке.

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

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

Решение. Записывают уравнения граничных прямых и их графики строят на плоскости в выбранной системе координат:

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

Прямая (1.13) проходит через начало координат и еще через одну точку, координаты которой легко определить.

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

Параллельно перемещая прямую Z в направлении вектора, видим, что экстремальной точкой является точка С (5, 3) – точка пересечения прямых.

Известно, что, система двух линейных уравнений с двумя неизвестными записывается в следующем виде:

где - заданные числа из К.

Матрицы

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

Если, то из этого уравнения и аналогичного уравнения, получающегося путем исключения, получим

Знаменатели выражений для неизвестных здесь одинаковы и представляют собой многочлен от элементов основной матрицы А. Значение этого многочлена называют определителем или детерминантом матрицы А и обозначают или.

В нашем случае получим

Ответ: max Z = 50, x₁ = 5, x₂ = 3.

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

Рис 1). Задача имеет единственное решение

Рис..2). Задача имеет бесконечное множество решений

Рис.3). Линейная форма не ограничена Рис.4). Система ограничений несовместна

Дана общая задача ЛП:

(1)

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

;

;

;

;

Вводя 4 добавочных неизвестных получим каноническую систему уравнений (базис):

Базис; свободные переменные положим их равными 0.

Пусть тогда В выражении для F можно увеличивать при этом F будет уменьшаться. Примем будет увеличивать до 5, т.к. при этом Поскольку «ненадежнее» всех в базисе, выведем его из базиса, а в базис введем Выразим F и новые базисные переменные через найдём и подставим его в выражения (1), (2), (3).

В итоге получим:

min(*)

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

.

Допустимое базисное решение следующее:Свободные переменные. Положим их равными 0. Решая пример далее, видим, что увеличивать нельзя, так как будет возрастатать (а нам нужно минимизировать). Значит. Свободную переменную можно увеличивать, но до иначе будет отрицательна.)

Итак, самая «ненадёжная» переменная Выводим из базиса, а вместо её в базис вводим «провокатора» переменную Свободные переменные.

Из «ненадёжного» уравнения для

находим

и подставляем *). Получим:

min

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

Допустимое базисное решение:

Здесь можно увеличивать до 6, так как

При этом

Достигнуто оптимальное решение: В процессе перехода от одного базисного решения к другому значение F постоянно уменьшалось.

Покажем решение данного примера графически.

Рис.2

На координатные оси нанесем систему неравенств (см. пример). Выпуклая область (рис.2) соответствует совокупности решений системы неравенств. Минимальное и максимальное значения целевой функции достигаются в точках пересечения этого многогранника решений с «опорными» прямыми, проведенными перпендикулярно вектору Выпишем из базисных решений:

Вектор указывает положительное направление, при движении в котором F увеличивается. Целевая функция задачи ЛП достигает минимума (максимума) в крайней точке выпуклой области. Если F принимает оптимальное значение в нескольких точках, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек (случай, когда целевая функция достигает минимума на грани многогранника) [1]. Множество всех планов задачи ЛП выпукло [1-4]. Отыскание оптимума целевой функции сводится к перебору крайних точек выпуклого многогранника.

Дата добавления: 2014-01-04