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

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

Задача линейного программирования записана в основном виде, если при задании допустимого множества U отсутствуют ограничения-равенства:

где с и aⁱ=(a_i1,…,a_in) – фиксированные векторы в En; I₁ и I₂ – некоторые множества индексов;I1I2={1,…,m}.

Задача линейного программирования в основном виде при xE² допускает простую геометрическую интерполяцию и может быть решена графически.

Из курса аналитической геометрии известно, что линейное неравенство вида a1x1+a2x2b определяет на плоскости (х₁,х₂) одну из двух полуплоскостей, на которые прямая a1x1+a2x2=b разбивает эту плоскость. Таким образом, допустимое множество задачи линейного программирования является пересечением m+2 полуплоскостей, соответствующих ограничениям-неравенствам, и представляет собой либо выпуклый многоугольник (a), либо неограниченное многоугольное множество (б), либо пустое множество (в).

Для решения задачи рассматривают линии уровня целевой функции f(x), т.е. семейство параллельных прямых <с,х>=const. Нормальный к этим прямым вектор –f’(x)=-c указывает направление убывания целевой функции. Поэтому решение задачи будет найдено, если построить какую-либо линию уровня целевой функции, проходящую через допустимое множество U, и перемещать ее параллельно самой себе в направлении вектора –с до тех пор, пока она пересекает множество U. Если существует крайнее положение линии уровня по отношению к множеству U, то оно и определяет точку минимума х^*.

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

Особенности задачи линейного программирования:

• их допустимые множества U являются многоугольниками, т.е. множествами с конечным числом угловых точек (вершин);

• если множество U не пусто и ограничено, то задача линейного программирования обязательно имеет решение;

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

2. Симплекс-метод (идея, условие оптимальности). Алгоритм симплекс-метода.

Задача линейного программирования в общем случае может быть сформулирована следующим образом: найти такие значения действительных переменных х₁, х₂,…,х_n, для которых целевая функция Q(x)=p₁x₁+p₂x₂+…+p_nx_n принимает минимальное значение на множестве точек, координаты которых удовлетворяют условиям

a₁₁x₁+a₁₂x₂+…+a_1nx_n=b₁

a₁₂x₁+a₂₂x₂+…+a_2nx_n=b₂

………………………………………………………

am1x₁+a_m2x₂+…+a_mnx_n=b_m

x10, x20, …. ,bm0 (канонический вид)

Так как решение задачи линейного программирования достигается (по крайней мере) в вершинах допустимой области, то достаточно рассмотреть значения целевой функции только в вершинах. Данной допустимой симплекс таблице соответствует только одно базисное решение, т.е. только одна вершина. Проверка выделяет ту вершину, которую следует считать оптимальной. В других случаях способ ведет или к заключению, что задача неразрешима (т.е. минимальное значение целевой функции в допустимой области равно -), или к новому базисному решению, в котором значении целевой функции не больше, чем в первом. В общем случае после конечного числа шагов достигается вершина, в которой целевая функция имеет оптимальное значение. При наличии вырожденных вершин в очень редких, исключительных случаях может оказаться, что мы снова и снова будем проходить один и тот же цикл базисных решений, относящихся к одной и той же вырожденной вершине. Допустимой симплекс-таблице соответствует точка минимума, если все коэффициенты целевой функции неотрицательны: . Тогда минимальное значение целевой функции равно Q₀. Если все коэффициенты целевой функции положительны, то вершина, соответствующая таблице, является единственной оптимальной точкой. Если критерий не выполнен, т.е. не все коэффициенты целевой функции неотрицательны, то следует перейти от одного допустимого базисного решения к соседнему допустимому, т.е. такому. В котором множества базисных и свободных переменных изменены на один элемент. В невырожденном случае этому геометрически соответствует переход от одной вершины к другой вдоль ребра допустимой области (обе вершины принадлежат одному ребру). Этот процесс называют также симплекс-шагом или заменой базиса. Его этапы:

• Выбор разрешающего столбца: среди элементов последней стоки таблицы выбирается любой p_j* и соответствующий столбец называется разрешающим. В качестве p_j* рекомендуется выбирать минимальное p_j.

• Выбор разрешающей строки: если a_ij*0 для всех элементов разрешающего столбца, то минимума не существует (целевая функция в допустимой области не ограничена снизу). Если это не так, то для всех положительных a_ij* нужно вычислить отношение b_i/a_ij*. Строка i, для которой отношение минимально, называется разрешающей строкой i^*:

общий элемент a_i*j* разрешающего столбца и разрешающей строки называется разрешающим элементом.

• Замена базиса при помощи разрешающего элемента a_i*j* - процесс, производящий в таблице преобразования канонического вида, при котором базисное переменное x_i* становится свободным и одновременно свободное переменное x_j* становится базисным. Если w – какое-либо значение в таблице, то через будем обозначать значение, стоящее в новой таблице на том же самом месте:

  • 

  • 

  • 

Элементы правого столбца и нижней строки пересчитываются по тому же принципу, что и элементы в центральной части таблицы. То же имеет место и в г) и д).

• 

При вычислении вручную рекомендуется проделать вычисления г) по столбцам для каждого jj^*. Заметим, что (новый столбец)=(старый столбец)-(то, что уже стоит в новом столбце после выполнения в)-это - постоянное при пересчете каждого столбца)*(разрешающий столбец).

• 

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

Всегда должно получаться