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

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

(1)

При ограничениях

(2)

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

Крайние точки – вершины этой области.

Область допустимых решений – данная область.

Область допустимых решений может представлять собой:

Пустое множество

Одна точка

О граниченный многоугольник

 

 

Неограниченная область

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

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

Построить многоугольник допустимых решений;

Построить прямую , положив Z конкретное значение (обычно Z=0);

построить из начала координат вектор N;

передвигать прямую в направлении вектора N (или в направлении –N, если ищем min) до тех пор, пока область допустимых значений D не окажется по одну сторону от прямой, и будет иметь с прямой хотя бы одну общую точку (такая прямая – опорная прямая или гиперплоскость)

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

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

1) в т. A

на отрезке BC

 

2)

решений

нет

3)

 

в т. А

 

4)

в т. A

 

5) в т. A в т. В

 

 

6)

 

 

25.

Симплекс метод

Когда число переменных больше двух, то графический метод не работает, и переходят к другим аналитическим методам решения. Одним из основных аналитических методов решения задач линейного программирования является симплекс метод. Свое название он получил от латинского слова “простой”. Теория и алгоритм симплекс метода строятся для канонической формы задач линейного программирования.

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

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

отыскание какой-либо крайней точки;

проверка оптимальности;

указание процедуры целенаправленного перехода к следующей крайней точке.

В этом состоит эвалистическое обоснование симплекс метода.

Рассмотрим основные понятия симплекс метода. Пусть задача линейного программирования задана в канонической форме: (1) при ограничениях Ax=b (2), . Здесь матрица представляет собой набор векторов условий.

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

Базисный план - план векторы условий , соответствующие ненулевым компонентам, которого являются линейно независимыми.

Невырожденный базисный план – базисный план, содержащий ровно m ненулевых компонентов.

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

 

25

Первый этап: построение первоначального базисного плана.

Пусть задача линейного программирования задана в канонической форме, причем среди векторов условий найдутся m линейно независимых единичных векторов, образующих единичный базис. Соответствующие им компоненты вектора x – базисные компоненты, а оставшиеся – свободные компоненты. И пусть вектор . Неограничивая общности, будем считать, что единичными базисными векторами будут первые m векторов. Тогда задача линейного программирования примет следующий вид:

(3)

(4)

Другими словами матрица условий имеет вид:

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

25