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

 

Графическим методом в основном решаются задачи с малым числом переменных. Он включает следующие этапы:

1. Строится многогранник решений.

Геометрический смысл системы ограничений состоит в следующем: уравнение а₁₁х₁+…+а_1nх_n=b₁ представляет собой гиперплоскость в n-мерном пространстве, неравенство же есть точки подпространства, лежащие по одну сторону от гиперплоскости и образующие выпуклое множество. Следовательно, система ограничений (1.2) задачи линейного программирования есть множество точек n-мерного пространства, причем это множество выпуклое и каждая точка является решением системы неравенств.

2. Находятся вектор = grad z=(1,...,n)и вершина многоугольника решений, на которой достигается mах z.

Известно, что вектор-градиент функции z показывает направление наибольшего роста функции. Строится линия уровня с₁х₁+...+с_nх_n =h, проходящая через начало координат. Линия уровня обладает замечательным свойством: после подстановки координат лю6ой ее точки в выражение целевой функции z последняя принимает постоянное значение. Далее перемещаем линию уровня в направлении вектора до тех пор, пока не будет достигнута угловая вершина многоугольника решений либо установлена неограниченность функции на множестве решений.

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

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

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

Отметим, что нахождение минимального значения целевой функции отличается от нахождения её максимального значения лишь тем, что линия уровня c₁x₁+...+с_nх_n=hперемещается не в направлении вектора с, а в противоположном направлении.

 

 

3. Алгоритм симплекс-метода решения общей задачи линейного программирования.

Метод искусственного базиса.

 

1.4.2. Симплекс-метод

 

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

- среди векторов Р₁,...,Р_n выбрать k линейно независимых;

- найти опорный план, связанный с этой системой векторов;

- вычислить значение целевой функции для опорного плана.

Перебирая, таким образом, все опорные планы данной задачи и сравнивая между собой полученные значения целевой функции, найдем оптимальный план. Количество всех переборов определяется по следующей формуле: .

При достаточно большом количестве переменных исходной задачи такой перебор крайне затруднителен. В 40-х гг. ХХ в. американский математик Данциг предложил алгоритм разумного перебора опорных планов, получивший название симплекс-метода. Он позволяет найти вершину многогранника решений и определить, является ли она точкой экстремума целевой функции. Если нет, то обеспечивается переход в соседнюю вершину, где значе­ние целевой функции больше предыдущего. Через конечное чис­ло подобных шагов точка экстремума функции z либо оказывается найденной, либо признается несуществующей. Симплекс-метод используется тогда, когда уже получено некоторое допустимое решение для ограничений (1.2), что равносильно приведе­нию общей задачи линейного программирования к каноническому виду.

Рассмотрим общую схему симмекс-метода применительно к невырожденному случаю. Пусть известен некоторый опорный план . Для простоты изложения, не нарушая общности, будем полагать:=(₁, ₂,..., _k,0,...,0) с системой нeзависимых векторов

Определение 1.9. Если из некоторой системы векторов можно составить единичную матрицу, то такую систему векторов называют базисом.

Система единичных векторов Рj является базисом. Соответствующие базису переменные будем называть базисными переменными, а остальные - свободными перемеными.

Из (1.3) имеем:

₁P₁ +_2Р2...+_kР_k =Р₀.                                        (1.4)

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

=c11 +с22 +...+c_kk.                                   (1.5)

Разложение векторов Рj (j= ) по базису имеет вид:

Рj =а_1j Р₁ +а_2j Р₂ ...+a_kjP_k .                                         (1.6)

Для фиксированногo j Е выберем некоторое числоi > 0 и вычтемi x (l.6) из (1.4), тогда получим :

Р₀ =(₁-_ia_ij)P₁ +...+(_k -_ia_kj)Р_k+_iР_j.

Введем обозначение

=(₁-_ia_1j,...,_k-_iak_j,0,...,_i,0,...0).

Если i выбрать из условия

i =min{/аij:аij > 0,i=},                                   (1.7)

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

=c₁(₁-_iа_1j)+...+c_k(_k -_iak_j)+с_ji                                (1.8)

Обозначим через z(j) следующее выражение:

z(J)=c₁a_1j +...+c_ka_kj.

Вычтем i х z(j) из (1.5), получим :

Отсюдa и (1.8) имеем: =-i(z(j)-cj)= -ijгде j=z(j)-cj

 

Таким образом, пришли к следующему условию оптимальности.

Теорема 1.5. Опорный план =(1,2,...,k,0,...,0) задачи линейного программирования являетсяоптимальным, если выполняется неравенство j>= 0 для любого номера j= .

Пусть для некоторого номера j= выполняется соотношение

Если среди чисел а_i (i =) нет положительных, то планне является опорным, так как содержит k+1 отличную от нуля компонeнтy. В зтом случае целевая функция ислодной задачи не oгpaничена на множестве ее планов.

Если же для некоторых индексов i Е : а_i > 0, то покажем, что план - опорный план. Для этого достаточно показать, чтo система векторов Рj(J=1,...,-1,+1,...,k),Рлинейно независима (- индекс i, на котором достигается минимум в(1.7)).

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

Подставляя в эту формулу разложение вектора Риз (1.6}, получим следующее:

Система векторов Р₁,...,P,...,P_k линейно независима, а а> 0. Это значит, что последнее coотношение выполняется лишь при . Получили противоречие.