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

 

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

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

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

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

 

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

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

 

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

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

 

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

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

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

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

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

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

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

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

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

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

min L = 2x₁ + x₂ - x₃;
2x₂ - x₃ ≤ 5;
x₁ + x₂ - x₃ ≥ -1;
2x₁ - x₂ ≤ -3;
x₁ ≤ 0; x₂ ≥ 0; x₃ ≥ 0.

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

2x₂ - x₃ + x₄ = 5;
x₁ + x₂ - x₃ - x₅ = -1;
2x₁ - x₂ + x₆ = -3;
x₄ ≥ 0; x₅ ≥ 0; x₆ ≥ 0.

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

2x₂ - x₃ + x₄ = 5;
-x₁ - x₂ + x₃ + x₅ = 1;
-2x₁ + x₂ - x₆ = 3.

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

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

L_min = 2x₁' + x₂ - x₃ - 2x₇;
2x₂ - x₃ + x₄ = 5;
-x₁' - x₂ + x₃ + x₅ + x₇ = 1;
-2x₁' + x₂ - x₆ + 2x₇ = 3;
x₁' ≥ 0; x_i ≥ 0, i=2, 3, 4, 5, 6, 7.

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

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

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

3.Построить вектор и .

4.Найти и .

- целевая функция (1)

- ограничения функции (2)

(3)

Решение:

 

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

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

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

;

;

;

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

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

 

• 
  Для точки А:

, значит координаты вершины А(0;7);

 

• 
  Для точки С:

, значит координаты вершины С(8;3);

 

• 
  Для точки Д:

, значит координаты вершины Д(3;0)

 

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

 

3.
Построить вектор и (у нас это Z₀).

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

В нашем случае с₁=1, с₂=4, т.к.

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

 

Строим прямую , (рис.3)

 

4.
Находим и .

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

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

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

Из рисунка 4 видно, что находится в точке А(0;7), а в точке О(0;0).

Чтобы найти значение подставим координаты точки А в целевую функцию: ;

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

Ответ:

.

 

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

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

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

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

Совокупность n чисел c₁,…,c_n называется решением данной системы, если каждое уравнение системы обращается в равенство после подстановки в него чисел c₁,…,c_n вместо соответствующих неизвестных x₁,…,x_n.

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

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

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

 

 

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 Ссылки

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

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

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

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

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

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

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

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