Для связи в whatsapp +905441085890

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

На каждом шаге симплекс-метода требуется определять новые «наборы» базисных и свободных переменных, т.е. решать системы линейных алгебраических уравнений. Задачи линейного программирования решают с помощью стандартных симплекс-таблиц, формализующих алгоритм перевода базисных переменных в свободные. Этот алгоритм и определяет конкретный вид симплекс-таблиц. Рассмотрим симплекс-таблицы, преобразуемые с помощью метода полного исключения Жордана, получившего наибольшее распространение в линейном программировании.

Рассмотрим систему Метод полного исключения Жордана для решения систем линейных алгебраических уравнений линейных алгебраических уравнений с Метод полного исключения Жордана для решения систем линейных алгебраических уравнений неизвестными:

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

В методе ‘полного’ исключений Жордана делают такие преобразования, в результате которых в каждой строке и в каждом столбце матрицы системы линейных алгебраических уравнений остаются по одному неизвестному с коэффициентами, равными единице. Например, мы хотим исключить переменную Метод полного исключения Жордана для решения систем линейных алгебраических уравнений из всех строк за исключением Метод полного исключения Жордана для решения систем линейных алгебраических уравнений-й строки. Элемент Метод полного исключения Жордана для решения систем линейных алгебраических уравнений — коэффициент, стоящий перед переменной Метод полного исключения Жордана для решения систем линейных алгебраических уравнений, называют генеральным элементом, Метод полного исключения Жордана для решения систем линейных алгебраических уравнений-ю строку и Метод полного исключения Жордана для решения систем линейных алгебраических уравнений-й столбец — разрешающими. Прежде всего разрешающую строку делят на Метод полного исключения Жордана для решения систем линейных алгебраических уравнений, и она остается неизменной. Чтобы исключить Метод полного исключения Жордана для решения систем линейных алгебраических уравнений из первого уравнения, умножим разрешающую строку на Метод полного исключения Жордана для решения систем линейных алгебраических уравнений и сложим с первой строкой. В результате получим первую строку с нулевым элементом на месте Аналогично исключаем Метод полного исключения Жордана для решения систем линейных алгебраических уравнений в остальных строках. Получим новую эквивалентную запись системы алгебраических уравнений. В ней Метод полного исключения Жордана для решения систем линейных алгебраических уравнений-я строка имеет прежний вид, но все коэффициенты у нее поделены на Метод полного исключения Жордана для решения систем линейных алгебраических уравнений;Метод полного исключения Жордана для решения систем линейных алгебраических уравнений-й столбец состоит из нулевых элементов (кроме единицы, стоящей в Метод полного исключения Жордана для решения систем линейных алгебраических уравнений-й строке). Остальные элементы матрицы системы и столбец свободных членов пересчитываются по правилу прямоугольника. Например, новое значение элемента Метод полного исключения Жордана для решения систем линейных алгебраических уравнений будет равна

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

а новое значение Метод полного исключения Жордана для решения систем линейных алгебраических уравнений столбца свободных членов —

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

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

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

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

Существуют алгоритмы, где автоматически предусмотрены меры против зацикливания — «расклеивание» слипшихся вершин.

Как спланировать выпуск продукции пошивочному предприятию

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

Задача:

Намечается выпуск двух видов костюмов — мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 чел.-день трудозатрат; для мужского костюма — 3,5 м шерсти, 0,5 м лавсана и тоже I чел.-день трудозатрат. На пошив этих костюмов имеется 350 м шерсти, 240 м лавсана и 150 чел.-дней трудозатрат. По плану костюмов не должно быть менее 110 штук и необходимо обеспечить прибыль не менее 1400 руб. Требуется определить оптимальное число костюмов каждого вида, обеспечивающее максимальную прибыль, если прибыль от реализации женского костюма составляет 10 руб., а от мужского — 20 руб.

Решение. Пусть Метод полного исключения Жордана для решения систем линейных алгебраических уравнений — число женских костюмов, а Метод полного исключения Жордана для решения систем линейных алгебраических уравнений — мужских. Прибыль от женских костюмов составляет 10Метод полного исключения Жордана для решения систем линейных алгебраических уравнений руб., а от мужских 20Метод полного исключения Жордана для решения систем линейных алгебраических уравнений руб., т.е. необходимо максимизировать целевую функцию

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

Расход шерсти составляет Метод полного исключения Жордана для решения систем линейных алгебраических уравнений лавсана Метод полного исключения Жордана для решения систем линейных алгебраических уравнений трудовых ресурсов Метод полного исключения Жордана для решения систем линейных алгебраических уравнений. Поэтому ограничения задачи имеют вид:

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

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

Для решения задачи симплекс-методом сведем систему ограничений к равенствам путем введения неотрицательных слабых переменных Метод полного исключения Жордана для решения систем линейных алгебраических уравнений (в первом и втором ограничениях проведем умножение на 2, а в пятом сократим обе части неравенства на 10):

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

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

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

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

Данные табл. 2.1 соответствуют системе ограничений-равенств (2.2). Так, согласно этой таблице

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

что соотносится с системой уравнений (2.2). Согласно табл. 2.1

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

Последний контрольный столбец содержит сумму всех чисел в строке, в процессе пересчетов сумма всех чисел в строках должна быть равной числу в контрольном столбце.

Проведем максимизацию функции Метод полного исключения Жордана для решения систем линейных алгебраических уравнений. Среди элементов строки Метод полного исключения Жордана для решения систем линейных алгебраических уравнений есть отрицательные. Берем меньший отрицательный коэффициент, равный -3; он указывает, что переменную Метод полного исключения Жордана для решения систем линейных алгебраических уравнений надо перевести в базисные. Чтобы определить, какую переменную следует из базисных перевести в свободные, рассмотрим положительные отношения Метод полного исключения Жордана для решения систем линейных алгебраических уравнений к соответствующим элементам столбца Метод полного исключения Жордана для решения систем линейных алгебраических уравнений: 700/7= 100; 480/1=480; 150/1 = 150;-110/(-1) = 110;-140/(-2)= 70. Минимальное значение, равное 70, указывает, что Метод полного исключения Жордана для решения систем линейных алгебраических уравнений надо перевести в свободные, а генеральным {разрешающим) элементом является (-2) (обведен). Для получения следующей симплекс-таблицы применим метод полного исключения Жордана (табл. 2.2).

Разрешающую строку (для Метод полного исключения Жордана для решения систем линейных алгебраических уравнений) делим на (-2) и заносим в табл. 2.2; столбец Метод полного исключения Жордана для решения систем линейных алгебраических уравнений заполняем нулями. Столбцы для Метод полного исключения Жордана для решения систем линейных алгебраических уравнений переносим без изменения, так как они пересекают нулевые элементы раз-

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

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

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

Из табл. 2.3 видно, что достигнут максимум фиктивной целевой функции (Метод полного исключения Жордана для решения систем линейных алгебраических уравнений = 0), и все коэффициенты в строке Метод полного исключения Жордана для решения систем линейных алгебраических уравнений равны

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

нулю, т.е. получено опорное решение

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений
Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

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

Продолжаем улучшать решение симплекс-методом. Строку Метод полного исключения Жордана для решения систем линейных алгебраических уравнений исключаем. Генеральным будет элемент (1, 7), равный 5; Метод полного исключения Жордана для решения систем линейных алгебраических уравнений переводим в базис (вместо Метод полного исключения Жордана для решения систем линейных алгебраических уравнений). Получим табл. 2.4, затем табл. 2.5. В табл. 2.4 отмечен генеральный элемент.

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

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

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

Таким образом, максимальная прибыль составит 2300 руб. при производстве 70 женских и 80 мужских костюмов. Слабые переменные оказались равными

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений
Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

Что же они показывают? Значения Метод полного исключения Жордана для решения систем линейных алгебраических уравненийМетод полного исключения Жордана для решения систем линейных алгебраических уравнений показывают остатки ресурсов: шерсть и трудовые ресурсы израсходованы полностью, лавсана осталось 120 м; Метод полного исключения Жордана для решения систем линейных алгебраических уравнений и Метод полного исключения Жордана для решения систем линейных алгебраических уравнений показывают, на сколько перевыполнены плановые задания по числу костюмов и по прибыли (имеем в виду, что Метод полного исключения Жордана для решения систем линейных алгебраических уравнений = 90 • 10 = 900 руб.).

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

Рассмотрим графическое решение этой задачи. Поскольку задача двумерная, то решим ее графически. Система ограничений-неравенств определяет многоугольник допустимых решений (рис. 2.3). Определим полуплоскости, задаваемые неравенствами-ограничениями задачи. Для этого построим прямые, заменив в ограничениях знаки неравенств на знаки равенств. Чтобы выяснить, какую часть плоскости описывает неравенство, подставляем в него пробную точку, например (0, 0), и устанавливаем, удовлетворяет ли она неравенству. Если неравенство удовлетворяется, то искомая полуплоскость включает точку (0, 0). В противном случае берут другую половину плоскости.

Для первого неравенства прямую

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

строим по точкам

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

Пробная точка (0, 0) удовлетворяет неравенству 0 < 350, т.е. точка (0, 0) входит в искомую полуплоскость (она отмечена стрелочками у прямой Метод полного исключения Жордана для решения систем линейных алгебраических уравнений). Прямую

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

строим аналогично: при Метод полного исключения Жордана для решения систем линейных алгебраических уравненийМетод полного исключения Жордана для решения систем линейных алгебраических уравнений и при Метод полного исключения Жордана для решения систем линейных алгебраических уравнений. Точка (0, 0)

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

принадлежит искомой полуплоскости. Рассмотрим последнее неравенство Метод полного исключения Жордана для решения систем линейных алгебраических уравнений, ему соответствует прямая Метод полного исключения Жордана для решения систем линейных алгебраических уравненийМетод полного исключения Жордана для решения систем линейных алгебраических уравнений: при Метод полного исключения Жордана для решения систем линейных алгебраических уравнений и при Метод полного исключения Жордана для решения систем линейных алгебраических уравнений. Точка (0, 0) не удовлетворяет неравенству Метод полного исключения Жордана для решения систем линейных алгебраических уравнений (ложно), т е. надо взять полуплоскость, не содержащую точку (0,0). Пересечение полуплоскостей дает выпуклый многоугольник Метод полного исключения Жордана для решения систем линейных алгебраических уравнений. Для нахождения максимума функции Метод полного исключения Жордана для решения систем линейных алгебраических уравнений надо построить линию уровня. Пусть Метод полного исключения Жордана для решения систем линейных алгебраических уравнений = 0, тогда уравнение линии уровня Метод полного исключения Жордана для решения систем линейных алгебраических уравнений будет Метод полного исключения Жордана для решения систем линейных алгебраических уравнений — прямая, проходящая через начало координат параллельно прямой Метод полного исключения Жордана для решения систем линейных алгебраических уравнений. Градиент целевой функции Метод полного исключения Жордана для решения систем линейных алгебраических уравнений показывает направление ее возрастания. Прямую Метод полного исключения Жордана для решения систем линейных алгебраических уравнений перемещаем параллельно самой себе в направлении Метод полного исключения Жордана для решения систем линейных алгебраических уравнений до тех пор, пока она «не выйдет» из области Метод полного исключения Жордана для решения систем линейных алгебраических уравнений. Получаем точку Метод полного исключения Жордана для решения систем линейных алгебраических уравнений, которая является точкой пересечения прямых Метод полного исключения Жордана для решения систем линейных алгебраических уравнений и Метод полного исключения Жордана для решения систем линейных алгебраических уравнений:

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

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

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

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

Метод полного исключения Жордана для решения систем линейных алгебраических уравнений

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

Эта теория взята со страницы лекций по предмету «математическое программирование»:

Предмет математическое программирование

Возможно эти страницы вам будут полезны:

Математическая постановка задачи линейного программирования
Симплекс-метод — основной метод решения задач линейного программирования
Двойственность в задачах линейного программирования
Геометрическая интерпретация теории двойственности в задачах линейного программирования