Геометрический метод решение задач

Свойства основной задачи линейного программирования связаны со свойствами выпуклых множеств.

Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит и их произвольную выпуклую комбинацию.

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

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

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

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

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

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

,

при условиях

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

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

системы ограничений заменой знаков неравенств на знаки точных равенств.

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

1. На плоскости строят прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

2. Находят полуплоскости, определяемые каждым из ограничений задачи.

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

4. Строят вектор , который указывает направление возрастания целевой функции.

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

6. Определяют координаты точки максимума функции и вычисляют значение целевой функции в этой точке. Минимальное значение линейной функции цели находится путем передвижения начальной прямой в направлении, противоположном вектору .

Пример 1.Найдите максимум и минимум линейной функции

при условиях-ограничениях:

Решение.Построим на плоскости многоугольник решений (рис. 1). Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств.

Рисунок 1. Построение многоугольника решений

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

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

Для нахождения точек экстремума построим начальную прямую и вектор (—2, 4). Передвигая прямую в направлении вектора , найдем точку С, в которой начальная прямая принимает положение опорной прямой. Следовательно, в точке С целевая функция имеет максимальное значение. Так как точка С получена в результате пересечения прямых 1

и 2 из системы, то ее координаты удовлетворяют уравнениям этих прямых:

Решив систему уравнений, получим: =3,4; =4,2; откуда найдем максимальное значение целевой функции =(-2)*3,4 + 4*4,2=10.

По условию задачи начальная прямая параллельна прямой (2), так как коэффициенты при переменных , пропорциональны: (—2)/(-1)=4/2=2. Следовательно, начальная прямая займет положение опорной прямой в точках В, С и в любой точке отрезка ВС, в которых принимает одно и то же максимальное значение. Для определения координат точки В решим систему двух линейных уравнений:

Максимальное значение целевой функции в точке В равно:

=(-2)*0 + 4*2,5=10.

Запишем множество оптимальных решений как линейную выпуклую комбинацию углов точек отрезка ВС: где .

Подставив координаты угловых точек, получим:

Тогда где .

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

Для нахождения минимального значения целевой функции задачи перемещаем начальную прямую в направлении, противоположном вектору . Начальная прямая займет положение опорной прямой в вершине D, где =2, =0, а минимальное значение целевой функции равно: =(- 2)*2 + 4*0=-4.

Пример 2.Геометрический метод решения задачи линейного программирования рассмотрим на примере поставленной задачи и построенной модели коммерческой деятельности предприятия, представленной в п. 2.2.1. Так как модель имеет только две переменные,

то данную задачу можно решить геометрическим методом.

Решение.

Построим на плоскости (рис. 1) многоугольник допустимых решений задачи. Для этого в неравенствах системы ограничений знаки неравенств заменим на знаки точных равенств:

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

Рис.1 Построение области допустимых решений

Направление стрелок от каждой граничной прямой определяется путем непосредственной подстановки в неравенство координат произвольно взятой точки, например (0;0), и при удовлетворении данного неравенства направляем стрелки в сторону контрольной точки, в противном случае — наоборот.

Полученная область решений есть многоугольник ABCDEF.

Угловые точки многоугольника решений имеют следующие координаты:

А (0,25; 0,5), В (0,25; 1,75), С (0,5; 2), D (2; 2), Е (3 ; 1 ), F(3,75; 0,5).

Для нахождения минимума и максимума целевой функции строим начальную прямую и вектор-градиент (2; 3) (рис. 2). Координатами вектора являются коэффициенты линейной целевой функции при переменных и . Для построения графика целевой функции задаем произвольное значение .Если =О, то прямая проходит через начало координат. Для ее построения, полагая =1, получим =-2/3, а при =1, получим =-3/2 (рис. 2). Полагая =6, таким же образом построим линию целевой функции.

Затем для =0,25 и =0,5 определяем минимальное значение =2. Таким образом, построим на графике ряд параллельных прямых (рис. 2), где вектор-градиент (2; 3) показывает направление роста целевой функции.

Максимальное значение будет в точке Е. Так как точка Е получена в результате пересечения прямых (1) и (2), то для определенияее координат решим систему уравнений:

Максимальное значение целевой функции

(тыс. руб.).

Целевая функция пересекает ось в точке = , а ось в точке = .