Линейное программирование (Графический метод. Симплексный метод) (стр. 6 )

где ,

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

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

 

Рисунок 3 – Пример угловой точки (точка А) и выпуклой линейной комбинации угловых точек (отрезок СD)

Теорема о представлении Любую точку многогранника решений можно представить как выпуклую линейную комбинацию его угловых точек [4].

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

Итак, непустое множество решений задачи линейного программирования образует выпуклый многогранник. В одной из вершин многогранника решений целевая функция принимает оптимальное значение. Если оптимальное значение функция принимает более чем в одной вершине, то это же значение она принимает в любой точке, являющей выпуклой линейной комбинацией данных вершин. Рассмотренные теоремы позволяют сделать вывод, что поиски оптимального решения можно ограничить перебором конечного числа угловых точек. Однако для отыскания угловых точек требуется построение области решений системы ограничений. Это построение возможно только для 2-х и 3-х мерного пространства.

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

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

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

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

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

Перейдем к геометрической интерпретации целевой функции. Уравнение при фиксированном значении z=h () определяет на плоскости прямую . При изменении h получаем семейство параллельных прямых, которое называется линиями уровня. В каждой точке этой прямой (линии уровня) целевая функция принимает фиксированное значение, равное h.

Рассмотрим функцию , дифференцируемую в некоторой точке .

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

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

Вектор - показывает направление наибольшего убывания целевой функции.

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

 

Рисунок 1 – Многоугольник допустимых решений и исходная линия уровня пересекаются, вектор лежит во втором квадранте

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

 

Рисунок 2 – Многоугольник допустимых решений и исходная линия уровня не пересекаются, вектор лежит в первом квадранте

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

 

Рисунок 3 – Система ограничений задачи линейного программирования несовместна

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