Дадим сначала определение преобразования системы линейных уравнений методом полного жорданова исключения. Пусть имеется система линейных уравнений с неизвестными
Сопоставим системе уравнений следующую симплекс-таблицу
¼ | |||||
Назовем полным жордановым исключением переменной с помощью –го уравнения следующее эквивалентное преобразование симплекс-таблицы данной системы уравнений. Строку с номером назовем разрешающей строкой. Столбец с номером назовем разрешающим столбцом. Элемент, стоящий на пересечении разрешающей строки и столбца, назовем разрешающим элементом.
Шаг 1. Перепишем разрешающую строку без изменений, дополним разрешающий столбец нулями.
Шаг 2. Элементы остальных строк и столбцов преобразуем по правилу прямоугольника. Соединим элемент таблицы с разрешающим элементом и достроим полученную диагональ до прямоугольника. Теперь заменим на разность произведения элементов и и произведения элементов и :
|
|
®
Шаг 3. Поделим полученную таблицу на разрешающий элемент .
Пример.
Проведем полное жорданово исключение переменой с помощью первого уравнения. Запишем систему в виде симплекс-таблицы.
-1 | -1 |
В качестве разрешающего элемента выбираем элемент первой строки и первого столбца системы.
Шаг 1. Перепишем разрешающую строку без изменений, дополним разрешающий столбец нулями.
Шаг 2. Остальные элементы преобразуем по правилу прямоугольника. Для элементов второй строки последовательно получаем:
1 ®
1 ®
4 ®
1 ®
Для элементов третьей строки получаем
3 ®
-1 ®
2 ®
-1 ®
В результате получим
-5 | -5 |
Шаг 3. Поделим полученную таблицу на разрешающий элемент.
1/2 | 3/2 | 1/2 | 3/2 | |
3/2 | 5/2 | 9/2 | 5/2 | |
5/2 | -5/2 | 3/2 | -5/2 |
На этом преобразование жорданова исключения закончено.
Задача линейного программирования в стандартной форме записывается в следующем виде. Требуется найти максимальное значение функции ,
при ограничениях
в предположении, что все переменные неотрицательны
При этом все свободные переменные в правой части уравнений предполагаются также неотрицательными, .