Особенности задач линейного программирования, на которых основаны методы решения ЗЛП, можно проиллюстрировать с помощью графической интерпретации. Это возможно, когда вектор X содержит две переменные. Рассмотрим графическую интерпретацию ЗЛП на следующем примере.
Пример. Дана следующая задача линейного программирования:
3 x 1 2 х 2 → max,
2 х 1 + 4 х 2 ≤ 16,
x 1 ≤ 6,
x 2 ≤ 8, х 1, х 2 ≥ 0.
Для графической интерпретации задачи построим систему координат x 1O x 2 (рис. 7). Любая точка в этой системе задается своими координатами на осях О х 1 и О х 2 – (х 1, х 2), т. е. так же, как и вектор X. Таким образом, решени- ем задачи будет некоторая точка в пространстве X 1O х 2.
Если учитывать требование неотрицательности переменных и не учиты-
вать другие ограничения ЗЛП, то решением задачи может быть любая точка из той части плоскости, которая расположена выше и левее осей O х 1 и О х 2. Определим в этой части плоскости область допустимых решений данной за- дачи (говорят также – область допустимых значений переменных вектора X). Для этого нарисуем прямые, заданные уравнениями 2 х 1 + 4 х 2 = 16, х 1 = 6, х 2 = 8 (см. рис. 7). Относительно ограничения х 1 ≤ 6 допустимыми будут те реше- ния (точки), которые лежат левее прямой х 1 = 6 или на ней, относительно ограничения x 2 ≤ 8 – те решения, которые лежат ниже прямой х 2 = 8 или на ней. Относительно ограничения 2 х 1 + 4 х 2 ≤ 16 допустимыми будут те реше- ния, которые лежат левее или на прямой 2 х 1 + 4 х 2 = 16. Область допустимых решений задачи есть та область в х 1О х 2, точки которой удовлетворяют всем этим ограничениям, включая требования неотрицательности. Такой областью на рис. 7 является область OABD, которая есть пересечение перечисленных областей, и решением заданной ЗЛП является точка этой области. Решим эту задачу графическим методом, т. е. по рисунку.
Рис. 7. Система координат для графической интерпретации задачи линейного программирования при поиске области допустимых значений
Алгоритм решения следующий.
Шаг 1. Построить графическую интерпретацию ЗЛП, определить и ука-
зать на рисунке область допустимых решений.
Шаг 2. Построить вектор ОС с координатами (c 1, с 2). Здесь с 1, с 2 – коэф- фициенты при переменных в выражении целевой функции. В нашем примере это вектор ОС = (3, 2), который изображен на рис. 7.
Шаг 3. Провести линию, перпендикулярную вектору ОС. Это есть линия уровня целевой функции (на рис. 7 она показана штрихпунктиром).
Шаг 4. Для поиска оптимального решения перемещать линию уровня по направлению вектора ОС при поиске максимума, или против направления вектора ОС – при поиске минимума. Линию перемещать до тех пор, пока она не достигнет последней точки области допустимых решений. Эта точка и будет оптимальным решением задачи (на рис. 7 оптимальное решение – точка В).
Примечание. Линию уровня следует перемещать изнутри области допусти- мых решений к ее краю. В нашем примере это замечание неактуально, однако в других задачах может получиться так, что, рисуя перпендикуляр вектору ОС в конце вектора, мы получим линию вне области допустимых решений. В этом слу- чае ее необходимо переместить внутрь области, а потом уже осуществлять по- иск оптимума.
Шаг 5. Определить координаты оптимального решения. Это делается или по рисунку, или путем решения системы уравнений тех прямых, на пересече- нии которых лежит точка оптимального решения. В нашем примере это была
бы система уравнений:
2 х 1 + 4 х 2= 16,
х 1 = 6.
Для данной задачи решением будет точка В с координатами (6, 1). Иначе говоря, решением задачи являются значения переменных х 1 = 6, х 2 = 1. Под- ставляя эти значения в выражение для целевой функции, можно определить оптимальное значение критерия, в нашем случае I = f (X opt) = 27. Если бы в нашем примере необходимо было найти минимум целевой функции, то ре- шением была точка (0, 0).
На основе анализа примера можно сформулировать следующие особенно-
сти ЗЛП:
– область допустимых решений задачи линейного программирования ограничена прямыми линиями, т. е. является многогранником;
– решение ЗЛП, если оно является единственным, лежит на одной из вершин многогранника (точка В в примере). Если решений множество, то они лежат на грани многогранника (это могло бы получиться, если бы в при- мере вектор ОС оказался перпендикулярным прямой 2 х 1 + 4 х 2 = 16, тогда бы- ло бы бесконечное множество решений – точек на отрезке АВ);
– в ЗЛП может и не существовать решений, если область допустимых решений не замкнута. Так, если в примере убрать ограничения 2 х 1 + 4 х 2 ≤ 16 и х 2 ≤ 8, и убрать соответствующие прямые на рис. 7, то двигать линию уров- ня можно было бы до бесконечности, т. е. решение бы отсутствовало.
На этих особенностях основан наиболее известный метод решения ЗЛП – симплекс-метод. Сущность его сводится к следующему: по определенным пра- вилам при решении задачи ищутся так называемые базисные решения (сим- плексы). Эти базисные решения совпадают с вершинами многогранника обла- сти допустимых решений (на рис. 7 это точки О, А, В, D). В процессе поиска ба- зисных решений оценивается их оптимальность по правилам, позволяющим определить, можно ли улучшить значение целевой функции, если выбрать ка- кое-то другое базисное решение. Если можно – выбирается новое базисное ре- шение (новая вершина многогранника) и проверка повторяется. Это делается до тех пор, пока найденное базисное решение не окажется оптимальным.