БлогNot. Преобразование Жордана-Гаусса и симплекс-метод в Excel

Преобразование Жордана-Гаусса и симплекс-метод в Excel

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

Метод базируется на элементарных преобразованиях (переводящих систему в эквивалентную), к которым относятся:

  • прибавление к обеим частям уравнения системы другого уравнения той же системы, умноженного на число, отличное от нуля;
  • перестановка местами уравнений в системе;
  • удаление из системы уравнений вида 0 = 0.

В отличие от метода Гаусса, на каждом шаге одна переменная исключается из всех уравнений, кроме одного.

Шаг метода состоит в следующем:

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

Алгоритмизировать это можно так:

Для СЛАУ в матричном виде A*x=b (матрица A размерности m*n, совсем необязательно квадратная) составляется следующая таблица:

Таблица с системой уравнений для преобразования Жордана-Гаусса
Таблица с системой уравнений для преобразования Жордана-Гаусса

В таблице выбран разрешающий элемент ar,s≠0, тогда r - разрешающая строка, s - разрешающий столбец.

Переход к следующей таблице выполняется по правилам:

1. вычисляются элементы разрешающей строки: a'r,j=ar,j/ar,s - то есть, r-строка таблицы делится на разрешающий элемент;

2. все элементы разрешающего столбца, кроме ar,s, равного единице, становятся равны нулю;

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

Формула преобразования Жордана-Гаусса для элементов вне разрешающих строки и столбца
Формула преобразования Жордана-Гаусса для элементов вне разрешающих строки и столбца

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

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

Возможны следующие случаи:

1. В процессе исключений левая часть уравнения системы обращается в 0, а правая b≠0, тогда система не имеет решения.

2. Получается тождество 0 = 0 - уравнение является линейной комбинацией остальных и строка нулей может быть вычеркнута из системы.

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

Запрограммируем метод в Excel одной формулой, изменять которую должно быть не слишком трудоёмко. Например, для решения СЛАУ

Тестовая СЛАУ
Тестовая СЛАУ

заполним коэффициентами системы ячейки листа от A1 до D4 включительно, выберем разрешающий элемент a1,1=1, а первый шаг метода сделаем в ячейке A6, куда загоним "универсальную" формулу для преобразования Жордана-Гаусса:

=ЕСЛИ(СТРОКА($A$1)=СТРОКА(A1);A1/$A$1;
ЕСЛИ(СТОЛБЕЦ($A$1)=СТОЛБЕЦ(A1);0;(A1*$A$1-
ДВССЫЛ(АДРЕС(СТРОКА(A1);СТОЛБЕЦ($A$1)))*
ДВССЫЛ(АДРЕС(СТРОКА($A$1);СТОЛБЕЦ(A1))))/$A$1))

Здесь ссылка $A$1 показывает разрешающий элемент, а ссылка на текущий элемент не закреплена. Остаётся только растянуть формулу на ячейки A6:D9:

Вид листа для расчёта преобразования Жордана-Гаусса
Вид листа для расчёта преобразования Жордана-Гаусса

На следующем шаге разрешающим элементом может быть, например, a2,2=1 (ячейка B7). Нам останется скопировать формулу из A6 в A11 (по пустой строке оставляем, чтоб визуально разделить шаги метода), войти в режим редактирования формулы (двойной щелчок по ячейке или выбрать её и нажать клавишу F2) и поправить (аккуратно перетащить мышкой за границу) все закреплённые ссылки с ячейки A1 на B7.

Конечно, можно заменить везде в формуле закреплённую ссылку $A$1 на конструкцию вида ДВССЫЛ(ЯЧЕЙКА), образующую динамический адрес ссылки. Скажем, ДВССЫЛ(F8), а в ячейке F8 будет автоматически формироваться адрес ячейки разрешающего элемента по заданным пользователем номеру строки и столбца. Тогда для этих номеров строки и столбца придётся предусмотреть отдельные ячейки, например, так:

Попытка обойтись без перетаскивания ссылки...
Попытка обойтись без перетаскивания ссылки...

Увы, всё это ничего не даст - вместо $A$1 мы просто вынуждены будем закрепить в формуле ДВССЫЛ($F$8) и всё равно потом перетаскивать столько же ссылок при копировании формулы. Кроме того, "вручную" введённые номера строки и столбца придётся ещё и проверять на допустимость (хотя бы как на рисунке), так что, не будем умножать сущностей.

Посмотреть метод в работе можно на двух первых листах приложенного файла Excel (2 разных примера).

На преобразовании Жордана-Гаусса основан и такой универсальный метод решения линейных задач оптимизации, как симплекс-метод. Описания его обычно страшны, длинны и перегружены теоремами. Попробуем сделать простое описание и разработать пригодный для расчёта в Excel алгоритм. На самом деле, симплекс-метод уже встроен в стандартную надстройку Пакет анализа, и программировать его "вручную" не нужно, так что наш код имеет, скорее, учебную ценность.

Сначала минимум теории.

Если вектор-столбцы СЛАУ линейно независимы, соответствующие им переменные являются базисными, а остальные – свободными. Например, в СЛАУ

Базисные и свободные переменные в СЛАУ
Базисные и свободные переменные в СЛАУ

переменные x2 и x4 - базисные, а x1 и x3 - свободные. Базисные переменные между собой независимы, а свободные можно сделать, например, нулями и получить { x2=2, x4=1 }базисное решение системы.

Выбирая различные разрешающие элементы, можно получить решения СЛАУ с различными базисами. Любое неотрицательное базисное решение СЛАУ называется опорным.

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

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

1. Задача ЛП преобразуется к каноническому виду:

Канонический вид задачи линейного программирования
Канонический вид задачи линейного программирования

Это всегда можно сделать следующим образом: к задаче, записанной в стандартной постановке

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

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

2*x1+3*x2≤20
3*x1+x2≤15
4*x1≤16
3*x2≤12
x1,x2≥0

примет вид

2*x1+3*x2+x3=20
3*x1+x2+x4=15
4*x1+x5=16
3*x2+x6=12
x1,x2,...,x6≥0

То есть, "экономический" смысл балансовых переменных очень прост – это "остатки" неиспользованных ресурсов каждого вида.

Если в исходной задаче искался не минимум, а максимум, целевая функция Z заменятся на Z1 = -Z. Решения задач совпадают, при этом min Z = - max Z1. Например, цель

Z(x1,x2)=2*x1+5*x2 (max)

переписывается в виде

Z1(x1,x2)=-2*x1-5*x2 (min)

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

3*x1+x2+x4≥15

превращается в

-3*x1-x2-x4≤15

Канонический вид модели получен, для него выписывается симплекс-таблица:

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

В левом столбце записываются базисные переменные (БП), если они ещё не выделены – пусто.

2. С помощью шагов Жордана–Гаусса ищется первоначальный опорный план, т.е. СЛАУ приводится к базисному виду с неотрицательными свободными членами bi>0. При этом целевая функция Z должна быть выражена только через свободные неизвестные (нулевые коэффициенты в Z-строке стоят только под переменными xi, которые есть в базисе). При выборе разрешающего элемента ar,s в строку r столбца БП выписываем переменную xs, если там уже была переменная – вычеркиваем её (выводим из базиса).

3. Выписываем под столбцами xi опорный план X*: под свободными переменными - нули, под базисными – соответствующие базисной переменной коэффициенты из столбца b.

Ниже выписываем вектор R по правилу: под базисными переменными – нули, под свободными Ri=Zi.

Если все Ri≥0, найдено оптимальное решение X* и значение цели Zmin = -q, иначе нужен новый план, а у вас он есть, товарищ Жюков? (п. 4).

4. Для выбора разрешающего столбца s выбираем максимальную по модулю отрицательную компоненту вектора R, разрешающий столбец s выбран. Затем анализируем коэффициенты s-го столбца матрицы системы ограничений. Если все ai,s≤0, решения нет и Zmin стремится к минус бесконечности, иначе переходим к п.5.

5. Для выбора разрешающей строки r составляем неотрицательные отношения bi/Ai,s≥0 , i=1,2,...,m, и выбираем среди них наименьшее. Если минимум достигается для нескольких строк, за разрешающую можно принять любую из них, при этом, в новом опорном плане значения некоторых базисных переменных станут равными 0, т.е., получаем вырожденный опорный план.

6. Выполняем преобразование Жордана-Гаусса с разрешающим элементом ar,s и переходим к п.3

Геометрически симплекс-методу соответствует кратчайший обход вершин n-мерного выпуклого многогранника, образующего область допустимых решений задачи:

Геометрический смысл симплекс-метода
Геометрический смысл симплекс-метода

Здесь мы перешли от опорного плана C, представляющего собой одну из вершин многомерного многоугольника, к оптимальному плану E=X*.

Запрограммировать это всё в Excel нелегко, но можно. В прилагаемом документе приведены 3 примера, реализующие решение задач симплекс-методом. Правда, при выполнени шага менять уже придётся 3 формулы, на листе первого примера на симплекс-метод они выделены жёлтым цветом: расчёт отношений для выбора разрешающей строки в ячейке I2, заполнение столбца БП в ячейке A12, шаг преобразования Жордана-Гаусса в ячейке B12. Как и в примере на преобразование Жордана-Гаусса, изменение формул связано только с необходимостью сослаться на новую строку, содержащую адрес ячейки с разрешающим элементом (для первого шага - ячейка C9).

 Скачать примеры на преобразование Жордана-Гаусса и симплекс-метод в архиве .ZIP с документом Excel (73 Кб)

23.03.2014, 08:18 [39102 просмотра]


теги: математика excel алгоритм

К этой статье пока нет комментариев, Ваш будет первым