Преобразование Жордана-Гаусса и симплекс-метод в 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 [38263 просмотра]