Решение систем линейных уравнений методом жордана-гаусса. Линейное программирование. Симплекс-метод

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

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

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

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

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

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

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

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

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

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

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

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

Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.

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

В основу симплексного метода положена идея последовательного улучшения получаемого решения.

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

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

Процесс применения симплексного метода предполагает реализацию трех его основных элементов:

1) способ определения какого-либо первоначального допустимого базисного решения задачи;

2) правило перехода к лучшему (точнее, не худшему) решению;

3) критерий проверки оптимальности найденного решения.

Симплексный метод включает в себя ряд этапов и может быть сформулирован в виде четкого алгоритма (четкого предписания о выполнении последовательных операций). Это позволяет успешно программировать и реализовывать его на ЭВМ. Задачи с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.

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

Шаг 1 . Формулировка ЗЛП (формирование целевой функции и системы ограничений).

Рассмотрим подробно, как производится пересчет симплекс-таблиц (на примере одной итерации). Пусть имеется симплекс-таблица представленная на Рис.1 . Решается задача максимизации целевой функции. Разрешающий столбец соответствует переменной x 2 , а разрешающая строка переменной x 3 (красные числа), на их пересечении находится разрешающий элемент (клетка с серым фоном). Первое, что нам необходимо сделать - это заменить. Разрешающая строка показывает, какая переменная должна быть выведена из базиса (в нашем случае x 3 ), а разрешающий столбец показывает какая переменная должна войти в базис (в нашем случае x 2 ). На Рис.2 факт замены акцентирован синей линией.

Теперь пересчитаем элементы стоящие в разрешающей строке. Для этого просто разделим каждый из них на разрешающий элемент (в нашем примере 4 ). А все элементы разрешающего столбца обнулим, кроме элемента стоящего в разрешающей строке. (Смотри Рис.2 )

Рисунок 1

Остальные ячейки таблицы (кроме столбца "Отношение") пересчитываются по так называемому правилу прямоугольника , смысл которого проще всего понять на примере. Пусть нужно пересчитать элемент обведенный на Рис.1 красным контуром. Мысленно проводим от него вертикальную и горизонтальную линии до пересечения, с разрешающей строкой и разрешающим столбцом. Элементы стоящие в местах пересечения обведены синими контурами (Смотри Рис.1 ). Новое значение "красного" элемента будет равно нынешнему значению элемента минус произведение "синих" деленное на разрешающий ("серый") элемент (Смотри Рис.1 ). То есть: 18 - (64 * -1) / 4 = 34 , здесь знаком "* " показана операция умножения.
Записываем новое значение на прежнее место (Смотри Рис.2 красный контур).

Рисунок 2

Пользуясь данным правилом, заполняем все пустые элементы таблицы (кроме столбца "Отношение") Смотри Рис.3 . После этого определим новый разрешающий столбец. Для этого проанализируем строку "Q" и так как наша задача на максимум, то найдем в ней максимальный положительный элемент , он и определит разрешающий столбец. В нашем случае это 3/2 . Все элементы разрешающего столбца показаны красным шрифтом (Смотри Рис.3 ). Если после очередной итерации в строке "Q" не окажется положительных элементов - это значит что оптимальное решение достигнуто, итерации прекращаются. Если бы наша задача была на минимум, то разрешающий столбец определялся бы по минимальному отрицательному элементу, и если после очередной итерации в строке "Q" не окажется отрицательных элементов, значит достигнуто оптимальное решение.

Рисунок 3

Теперь заполним столбец "Отношение". Для этого нужно соответствующий (стоящий в той же строке) элемент столбца "Решение" разделить на соответствующий элемент разрешающего столбца (Смотри Рис.3 ). Обратите внимание , что данная операция проводится только для положительных элементов разрешающего столбца и строка "Q" в данной операции не участвует. Если после некоторой итерации в разрешающем столбце не окажется положительных элементов, то данная задача неразрешима ввиду неограниченности целевой функции, итерации прекращаются.

После заполнения столбца "Отношение" определим новую разрешающую строку. Она определяется минимальным элементом из столбца "Отношение". В нашем случае это 32 , все элементы разрешающей строки показаны красным шрифтом (Смотри Рис.3 ). На этом очередная итерация заканчивается, на следующей итерации переменная x 2 будет выведена из базиса (об этом нам говорит новая разрешающая строка), ее место займет переменная x 1 (об этом нам говорит новый разрешающий столбец) и все вычисления повторятся снова.

Для начала работы требуется, чтобы заданная система ограничений выражалась равенствами, причём в этой системе ограничений должны быть выделены базисные неизвестные. Решение задачи симплекс-методом распадается на ряд шагов. На каждом шаге от данного базиса Б переходят к другому, новому базису Б 1 с таим расчётом, чтобы значение функции Z уменьшилось, т.е. . Для перехода к новому базису из старого базиса удаляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый базис Б (k) , для которого есть искомый минимум для линейной функцииZ, а соответствующее базисное решение является оптимальным либо выясняется, что задача не имеет решения.

4.1 Алгоритм симплекс-метода.

Рассмотрю систему ограничений и линейную форму вида:

(4.1)

Используя метод Жордана-Гауса, приведём записанную систему к виду, где выделены базисные переменные.

Введём условные обозначения:

–базисные переменные;

–свободные переменные.

(4.4)

По последней системе ограничений построим табл. 4.1.

Таблица 4.1

Симплекс-таблица

Данная таблица называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменением содержания этой таблицы.

Алгоритм симплекс-метода сводится к следующему.

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

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

3. На пересечении разрешающих строки и столбца находится разрешающий элемент.

4. Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них, то выбирают любое из них. То же самое относится к положительным элементам последней строки симплекс-таблицы.

5. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей стоке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной, и наоборот. Симплекс таблица преобразована следующим образом

Таблица 4.2

Симплекс-таблица

6. Элемент табл. 4.2 соответствующий разрешающему элементу табл. 4.1, равен обратной величине разрешающего элемента.

7. Элементы строки табл. 4.2, соответствующие элементам разрешающей стоки табл. 4.1, получаются путём деления соответствующих элементов табл. 4.1 на разрешающий элемент.

8. Элементы столбца табл. 4.2, соответствующие элементам разрешающего столбца табл. 4.1, получаются путём деления соответствующих элементов табл. 4.1 на разрешающий элемент и берутся с противоположным знаком.

9. Остальные элементы вычисляются по правилу прямоугольника: мысленно вычерчиваем прямоугольник в табл.4.2, одна вершина которого совпадает с разрешающим элементом, а другая – с элементом, образ которого мы ищем; остальные две вершины определяются однозначно. Тогда искомый элемент табл. 4.2 будет равен соответствующему элементу табл. 4.1 минус дробь в знаменателе который стоит разрешающий элемент, а в числителе произведение элементов из двух неиспользованных вершин прямоугольника.

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

11. Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается).

5. Методы нахождения опорного решения задачи линейного программирования.

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

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

При этом , тогда, положив свободные неизвестныеравными нулю, получаем опорное решение.

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

(5.1)

Перепишем систему (5.1) в другом виде. Для этого введём искусственные переменные так, чтобы был выделен базис. Тогда система примет вид

(5.2)

Системы (5.1) и (5.2) будут эквивалентны в том случае, если все , длябудут равны 0. Кроме того, считаю, что вседля. В противном случае соответствующие ограничения из системы (5.1) умножим на – 1. Для того чтобыбыли равны 0, мы должны преобразовать задачу таким образом, чтобы все искусственные переменныеперешли в свободные неизвестные.

В этом случае система (5.2) после преобразования примет вид:

(5.3)

От системы (5.2) к системе (5.3) всегда можно перейти шагами симплекс-метода. При таком переходе в качестве линейной формы рассматривают функцию

равную сумме искусственных переменных. Переход заканчивают, когда и все искусственные переменныепереведены в свободные неизвестные.

Анализ вариантов решений

1. Если , а всепереведены в свободные переменные, то задача не имеет положительного решения.

2. Если , а частьосталась в базисе, то для перевода их в свободные необходимо применять специальные приёмы.

В симплекс-таблице, соответствующей системе (5.3), после того как , а все- свободные, вычёркивают строку дляи столбцы дляи решают задачу для исходной линейной формы.

5.2. Второй алгоритм отыскания опорного плана.

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

(5.5)

Построим первую таблицу Жордана-Гаусса для задач (5.5) и (5.6). Для единообразия вычислительной процедуры к исходной таблице приписываем строку целевой функции:

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

Алгоритм метода

1. Запишем задачу в форме (5.7), при этом все элементы столбца свободных членов должны быть неотрицательны,. Уравнения системы (5.5), в которых свободные члены отрицательны, предварительно нужно умножить на – 1.

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

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

4. В процессе преобразований вычёркиваем строки, состоящие из одних нулей.

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

Пояснение. В п.1.1 алгоритма предполагается, что все элементы столбца свободных членов неотрицательны. Это требование необязательно. В случае когда в столбце свободных членов встречаются отрицательные числа, будем пользоваться теоремой.

Теорема. Если разрешающий элемент выбирать по наименьшему положительному симплекс-отношению, то после шага Жордана-Гаусса свободный член в разрешающей строке становится положительным, а остальные члены сохраняют свой знак.

Выбор разрешающего элемента производят иначе, а именно.

1. Просматривают строку, соответствующую какому-либо отрицательному свободному члену. Выбирают в ней какой-либо отрицательный элемент – соответствующий этому элементу столбец будет разрешающим.

2. Выбор разрешающего элемента производится по минимальному положительному симплекс-отношению. Если задача разрешима, то через конечное число шагов получают первое допустимое решение и можно применять симплекс-метод.

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

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

Общая характеристика разрешенной системы уравнений

Дать характеристику системе уравнений .

Решение :

1. Входит ли в состав противоречивое уравнение? (Если коэффициенты, в этом случае уравнение имеет вид: и называется противоречивым .)

• Если система содержит противоречивое, то такая система несовместна и не имеет решения

2. Найти все разрешенные переменные . (Неизвестная называется разрешенной для системы уравнений, если она входит в одно из уравнений системы с коэффициентом +1, а в остальные уравнения не входит (т.е. входит с коэффициентом, равным нулю).

3. Является ли система уравнений разрешенной? (Система уравнений называется разрешенной , если каждое уравнение системы содержит разрешенную неизвестную, среди которых нет совпадающих)

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

Разрешенные неизвестные, входящие в полный набор, называют также базисными (), а не входящие в набор — свободными ().

На данном этапе главное понять что такое разрешенная неизвестная (входящая в базис и свободная).

Общее Частное Базисное решения

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

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

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

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

Теорема (1)

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

Решение :

1. Проверяем является ли система разрешенной?

• Система является разрешенной (т.к. каждое из уравнений содержит в себе разрешенную неизвестную)

2. Включаем в набор разрешенные неизвестные — по одному из каждого уравнения .

3. Записываем общее решение в зависимости от того какие разрешенные неизвестные мы включили в набор .

4. Находим частное решение . Для этого приравниваем свободные переменные, которые мы не включили в набор приравнять к произвольным числам.

Ответ: частное решение (один из вариантов)

5. Находим базисное решение . Для этого приравниваем свободные переменные, которые мы не включили в набор к нулю.

Элементарные преобразования линейных уравнений

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

Теорема (2)

Если какое-либо уравнение системы умножить на некоторое отличное от нуля число , а остальные уравнения оставить без изменения, то . (то есть если умножить левую и правую часть уравнения на одно и то же число то получится уравнение, равносильное данному)

Теорема (3)

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

Следствие из Теорем (2 и 3)

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

Формулы пересчета коэффициентов системы

Если у нас есть система уравнений и мы хотим преобразовать ее в разрешенную систему уравнений в этом нам поможет метод Жордана-Гаусса.

Преобразование Жордана с разрешающим элементом позволяет получить для системы уравнений разрешенную неизвестную в уравнении с номером . (пример 2).

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

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

Чтобы исключить из уравнения с номером , нужно уравнение с номером умножить на и прибавить к этому уравнению.

Теорема (4) О сокращении числа уравнений системы.

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

Теорема (5) О несовместимости системы уравнений.

Если система уравнений содержит противоречивое уравнение, то она несовместна.

Алгоритм метода Жордана-Гаусса

Алгоритм решения систем уравнений методом Жордана-Гаусса состоит из ряда однотипных шагов, на каждом из которых производятся действия в следующем порядке:

1. Проверяется, не является ли система несовместной. Если система содержит противоречивое уравнение, то она несовместна.
2. Проверяется возможность сокращения числа уравнений. Если в системе содержится тривиальное уравнение, его вычеркивают.
3. Если система уравнений является разрешенной, то записывают общее решение системы и если необходимо — частные решения.
4. Если система не является разрешенной, то в уравнении, не содержащем разрешенной неизвестной, выбирают разрешающий элемент и производят преобразование Жордана с этим элементом.
5. Далее заново переходят к пункту 1

Найти : два общих и два соответствующих базисных решения

Решение :

Вычисления приведены в нижеследующей таблице:

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

В первых трех строках таблицы помещены коэффициенты при неизвестных и правые части исходной системы. Результаты первого преобразования Жордана с разрешающим элементом равным единице приведены в строках 4, 5, 6. Результаты второго преобразования Жордана с разрешающим элементом равным (-1) приведены в строках 7, 8, 9. Так как третье уравнение является тривиальным, то его можно не учитывать.