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