Основные теоремы линейного программирования

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

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

Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными, если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные m-n переменных называются неосновными (или свободными).

Базисным решением системы m линейных уравнений c n переменными (m < n) называется всякое ее решение, в котором все неосновные переменные имеют нулевые значения.

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

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

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

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

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

Следствием из теорем 2 и 3 является утверждение о том, что оптимальное решение (оптимальные решения) задачи линейного программирования, заданной (или приведенной) ограничениями-уравнениями, совпадает с допустимым базисным решением (допустимыми базисными решениями) системы ограничений.

Таким образом, оптимальное решение ЗЛП следует искать среди конечного числа допустимых базисных решений.

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

Если математическая модель задачи линейного программирования имеет вид:

Основные теоремы линейного программирования - student2.ru
Основные теоремы линейного программирования - student2.ru
Основные теоремы линейного программирования - student2.ru

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

Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалента минимизации той же функции, взятой с противоположным знаком, и наоборот.

Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:

  • если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
  • если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;
  • если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
  • если некоторая переменная xj не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными:
    x3 = x3+ - x3-, где x3+, x3- ≥ 0.

Пример 1. Приведение к канонической форме задачи линейного программирования:

min L = 2x1 + x2 - x3;
2x2 - x3 ≤ 5;
x1 + x2 - x3 ≥ -1;
2x1 - x2 ≤ -3;
x1 ≤ 0; x2 ≥ 0; x3 ≥ 0.

Введем в каждое уравнение системы ограничений выравнивающие переменные x4, x5, x6. Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x4, x6 вводятся в левую часть со знаком "+", а во второе уравнение переменная x5 вводится со знаком "-".

2x2 - x3 + x4 = 5;
x1 + x2 - x3 - x5 = -1;
2x1 - x2 + x6 = -3;
x4 ≥ 0; x5 ≥ 0; x6 ≥ 0.

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:

2x2 - x3 + x4 = 5;
-x1 - x2 + x3 + x5 = 1;
-2x1 + x2 - x6 = 3.

В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть отрицательными. Допустим, что x1 = x1' - x7, где x1' ≥ 0, x7 ≥ 0.

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

Lmin = 2x1' + x2 - x3 - 2x7;
2x2 - x3 + x4 = 5;
-x1' - x2 + x3 + x5 + x7 = 1;
-2x1' + x2 - x6 + 2x7 = 3;
x1' ≥ 0; xi ≥ 0, i=2, 3, 4, 5, 6, 7.

12)1. Графический метод решения задач линейного программирования.
Задание:

1.Построить многоугольник решений.

2.Найти координаты вершин области.

3.Построить вектор Основные теоремы линейного программирования - student2.ru и Основные теоремы линейного программирования - student2.ru .

4.Найти Основные теоремы линейного программирования - student2.ru и Основные теоремы линейного программирования - student2.ru .

Основные теоремы линейного программирования - student2.ru - целевая функция (1)

Основные теоремы линейного программирования - student2.ru - ограничения функции (2)

Основные теоремы линейного программирования - student2.ru (3)


Решение:

1.
Построить многоугольник решений.


Каждое из неравенств системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми Основные теоремы линейного программирования - student2.ru ; ( Основные теоремы линейного программирования - student2.ru ; х1 = 0; х2 = 0). В том случае, если система неравенств (2) – (3) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых значений является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств.

Основные теоремы линейного программирования - student2.ru

Основные теоремы линейного программирования - student2.ru

Строим многоугольник решений (рис.1):

Основные теоремы линейного программирования - student2.ru ; Основные теоремы линейного программирования - student2.ru

Основные теоремы линейного программирования - student2.ru ; Основные теоремы линейного программирования - student2.ru

Основные теоремы линейного программирования - student2.ru ; Основные теоремы линейного программирования - student2.ru

Основные теоремы линейного программирования - student2.ru

Основные теоремы линейного программирования - student2.ru


2.
Найти координаты вершин области.


Для этого решаем систему уравнений для пересекающихся прямых


  • Для точки А:


Основные теоремы линейного программирования - student2.ru Основные теоремы линейного программирования - student2.ru , значит координаты вершины А(0;7);


  • Для точки С:


Основные теоремы линейного программирования - student2.ru Основные теоремы линейного программирования - student2.ru , значит координаты вершины С(8;3);


  • Для точки Д:


Основные теоремы линейного программирования - student2.ru Основные теоремы линейного программирования - student2.ru , значит координаты вершины Д(3;0)


  • Координаты точки О(0;0) совпадают с началом координат.

3.
Построить вектор Основные теоремы линейного программирования - student2.ru и Основные теоремы линейного программирования - student2.ru (у нас это Z0 ).


Целевая функция Основные теоремы линейного программирования - student2.ru определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значений Z.

В нашем случае с1=1, с2=4, т.к. Основные теоремы линейного программирования - student2.ru

Вектор Основные теоремы линейного программирования - student2.ru с координатами с1=1, с2=4 и выходящий из начала координат, перпендикулярный к этим прямым, указывает направление наискорейшего возрастания Z, а противоположный вектор – направление убывания Z

Строим прямую Основные теоремы линейного программирования - student2.ru , Основные теоремы линейного программирования - student2.ru (рис.3)

4.
Находим Основные теоремы линейного программирования - student2.ru и Основные теоремы линейного программирования - student2.ru .


Если в одной и той же системе координат изобразить область допустимых решений системы неравенств Основные теоремы линейного программирования - student2.ru ; Основные теоремы линейного программирования - student2.ru и семейство параллельных прямых Основные теоремы линейного программирования - student2.ru , то задача определения максимума функции Z сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z = const, и которая соответствует наибольшему значению параметра Z.

Для определения Основные теоремы линейного программирования - student2.ru построим линию уровня Основные теоремы линейного программирования - student2.ru перпендикулярную вектору Основные теоремы линейного программирования - student2.ru , и будем передвигать ее в направлении вектора Основные теоремы линейного программирования - student2.ru до тех пор, пока она не коснется последней крайней (угловой) точки многоугольника решений. Координаты этой точки точки и определяет Основные теоремы линейного программирования - student2.ru .

Для определения Основные теоремы линейного программирования - student2.ru построим линию уровня перпендикулярную вектору Основные теоремы линейного программирования - student2.ru , и будем передвигать ее против направления вектора Основные теоремы линейного программирования - student2.ru до тех пор, пока она не коснется последней крайней (угловой) точки многоугольника решений. Координаты этой точки точки и определяет Основные теоремы линейного программирования - student2.ru .


Из рисунка 4 видно, что Основные теоремы линейного программирования - student2.ru находится в точке А(0;7), а Основные теоремы линейного программирования - student2.ru в точке О(0;0).

Чтобы найти значение Основные теоремы линейного программирования - student2.ru подставим координаты точки А в целевую функцию: Основные теоремы линейного программирования - student2.ru ;

Чтобы найти значение Основные теоремы линейного программирования - student2.ru подставим координаты точки О в целевую функцию:

Основные теоремы линейного программирования - student2.ru
Ответ: Основные теоремы линейного программирования - student2.ru

Основные теоремы линейного программирования - student2.ru .

13) стемой m линейных уравнений с n неизвестными называется система вида

Основные теоремы линейного программирования - student2.ru

где aij и bi (i=1,…,m; b=1,…,n) – некоторые известные числа, а x1,…,xn – неизвестные. В обозначении коэффициентов aij первый индекс iобозначает номер уравнения, а второй j– номер неизвестного, при котором стоит этот коэффициент.

Коэффициенты при неизвестных будем записывать в виде матрицы Основные теоремы линейного программирования - student2.ru , которую назовём матрицей системы.

Числа, стоящие в правых частях уравнений, b1,…,bm называются свободными членами.

Совокупность n чисел c1,…,cn называется решением данной системы, если каждое уравнение системы обращается в равенство после подстановки в него чисел c1,…,cn вместо соответствующих неизвестных x1,…,xn.

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

  1. Система может иметь единственное решение.
  2. Система может иметь бесконечное множество решений. Например, Основные теоремы линейного программирования - student2.ru . Решением этой системы является любая пара чисел, отличающихся знаком.
  3. И третий случай, когда система вообще не имеет решения. Например, Основные теоремы линейного программирования - student2.ru , если бы решение существовало, то x1 + x2 равнялось бы одновременно нулю и единице.

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

14)Симплекс-метод — алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в многомерном пространстве. Метод был разработан советским математиком Канторовичем Л. В. в 1937 году.

Содержание [убрать] · 1 Описание · 2 Алгоритм симплекс-метода o 2.1 Усиленная постановка задачи o 2.2 Алгоритм · 3 Двухфазный симплекс-метод o 3.1 Причины использования o 3.2 Модификация ограничений § 3.2.1 Различия между дополнительными и вспомогательными переменными o 3.3 Фазы решения · 4 Модифицированный симплекс-метод · 5 Мультипликативный вариант симплекс-метода · 6 Другие варианты симплекс-метода · 7 Двойственный симплекс-метод · 8 Вычислительная эффективность · 9 Примечания · 10 Литература · 11 Ссылки

Править]Описание

Основные теоремы линейного программирования - student2.ru

Основные теоремы линейного программирования - student2.ru

Переход от одной вершины к другой

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

Заметим, что каждое из линейных неравенств на переменные ограничивает полупространство в соответствующем линейном пространстве. В результате все неравенства ограничивают некоторый многогранник (возможно, бесконечный), называемый такжеполиэдральным комплексом. Уравнение W(x) = c, где W(x) — максимизируемый (или минимизируемый) линейный функционал, порождает гиперплоскость L(c). Зависимость от c порождает семейство параллельных гиперплоскостей. Тогда экстремальная задача приобретает следующую формулировку — требуется найти такое наибольшее c, что гиперплоскость L(c) пересекает многогранник хотя бы в одной точке. Заметим, что пересечение оптимальной гиперплоскости и многогранника будет содержать хотя бы одну вершину, причём, их будет более одной, если пересечение содержит ребро или k-мерную грань. Поэтому максимум функционала можно искать в вершинах многогранника. Принцип симплекс-метода состоит в том, что выбирается одна из вершин многогранника, после чего начинается движение по его рёбрам от вершины к вершине в сторону увеличения значения функционала. Когда переход по ребру из текущей вершины в другую вершину с более высоким значением функционала невозможен, считается, что оптимальное значение c найдено.

Последовательность вычислений симплекс-методом можно разделить на две основные фазы:

1. нахождение исходной вершины множества допустимых решений,

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

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

Наши рекомендации