По решению линейных задач. Построение М-задачи в методе искусственного базиса

Симплексный метод. Алгоритм. Признак оптимальности опорного плана.

Из геометрической интерпретации ЗЛП видно, максимум или минимум функции достигается в угловой точке выпуклого многогранника – ОДР – системы ограничений. Поэтому в основу симплекс-метода положена идея рассмотрения и испытания на оптимальность только угловых точек – вершин многогранника, а не всего бесконечного множества его точек.

Рис. Геометрическая интерпретация идеи симплекс-метода

в случае двух (рис а) и трех (рис б) переменных.

Симплекс – это выпуклый многоугольник в n – мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости (гиперплоскость делит пространство на 2 полупространства).

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

Базисное решение – это одно из допустимых решений, находящихся в ОДР.

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

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

Алгоритм симплексного метода:

1. Построить математическую модель задачи.

Преобразовать полученную математическую модель в каноническую форму, у которой: правые части условий неотрицательны; условия являются равенствами (при необходимости ввести искусственные переменные).
Построить симплекс таблицу и найти начальный опорный план решения задачи. Множество переменных, которые являются базисными , принимаются за начальное базисное решение. Значения этих переменных равны свободным членам. Все остальные переменные равны нулю.
Проверка базисного решения на оптимальность осуществляется с помощью специальных оценок коэффициентов целевой функции (смотреть последнюю строку таблицы). Если задача решается на max, то все оценки должны быть неотрицательными, если на min, то все оценки должны быть неположительные.
Переход к новому базисному решению. Очевидно, что в оптимальный план должна быть введена такая переменная, которая в наибольшей степени увеличит целевую функцию. При решении задач на max в оптимальный план вводится продукция, производство которой наиболее выгодно. Это определяется по max положительному значению оценки коэффициентов целевой функции. Столбец таблицы, который содержит эту оценку, называется генеральным столбцом. Если хотя бы один элемент столбца положительный, то отыскивается генеральная строка (в противном случае задача не имеет оптимального решения). Если в этом столбце есть нули, то нужно брать другой столбец. Для отыскания генеральной строки все свободные члены (ресурсы) делятся на соответствующие элементы генерального столбца (норма расхода ресурса на единицу изделия). Из полученных результатов выбирается наименьший, соответствующая строка называется генеральной. Она соответствует ресурсу, который ограничивает производство на данном шаге. Элемент симплекс таблицы, находящийся на пересечении генеральной строки и столбца, называется генеральный элемент. Все элементы генеральной строки, включая свободный член, делятся на генеральный элемент. В результате генеральный элемент становится равным 1. Далее необходимо чтобы все другие элементы генерального столбца стали равными 0. генеральный столбец должен стать единичным. Все строки кроме генеральной преобразуют следующим образом: полученные элементы новой строки умножим на соответствующие элементы генерального столбца, и полученное произведение вычитаем из элементов старой строки. Значение новых базисных переменных получим в соответствующих ячейках столбца свободных членов (правило прямоугольников).
Полученное базисное решение проверяется на оптимальность (шаг №4). Если оно оптимально, то вычисления прекращаются, в противном случае находится новое базисное решение (шаг №5).

Признак оптимальности опорного плана

Если решаем задачу на max то все оценки должны быть неотрицательными.

Если решаем задачу на min то все оценки должны быть неположительными.

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

Θ (столбец симплекс-отношений) не рисуется для строчек с отрицательными и нулевыми значениями. Из всех θ выбираем наименьшее, так делается всегда неважно на min или на max исходная задача.

Разрешающая строка всегда показывает, какой элемент надо вывести из базиса, а разрешающий столбец – какой элемент надо ввести в базис.

Табличный вид ЗЛП. Симплекс - таблицы.

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗЛП

3.1. Общая характеристика и основные этапы симплекс – метода

Основоположниками симплекс-метода являются советский математик Л.В. Канторович и американский математик Дж. Данциг.

Симплекс-методом можно решить любую ЗЛП или обнаружить ее неразрешимость. Многие специальные классы ЗЛП можно решить другими, более эффективными для этих классов методами. Однако преимущество симплекс-метода - его универсальность. Почти для всех ЭВМ разработаны стандартные программы для решения ЗЛП симплекс - методом.

Опишем общую идею симплекс-метода.

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

При решении ЗЛП симплекс-методом можно выделить следующие этапы:

1) приведение ЗЛП к каноническому виду;

2) приведение системы линейных уравнений к жордановой форме с неотрицательными правыми частями с одновременной проверкой на неразрешимость ЗЛП из-за противоречивости системы линейных ограничений;

3) исследование опорного плана на оптимальность;

4) исследование ЗЛП на неразрешимость из-за неограниченности снизу на ОДР целевой функции;

5) переход к новому, "лучшему" опорному плану.

Для сокращения и упорядочения записей при решении ЗЛП симплекс-методом используются так называемые симплекс-таблицы. Чтобы воспользоваться симплекс-таблицей, ЗЛП нужно привести к табличному виду. Делается это так.

Пусть ЗЛП записана в каноническом виде (2.3-2.5). Для приведения ЗЛП к табличному виду систему (2.4) следует сначала привести к жордановой форме с неотрицательными правыми частями. Предположим, что эта жорданова форма имеет вид (2.6). Выразим из (2.6) базисные переменные через свободные:

Подставив в целевую функцию (2.3) вместо базисных переменных их выражения через свободные переменные по формулам (3.1), исключим тем самым из целевой функции базисные переменные. Целевая функция примет вид:

В табличном виде целевая функция записывается так:

где .

Отметим следующие особенности табличного вида ЗЛП:

а) система линейных уравнений приведена к жордановой форме с неотрицательными правыми частями;

б) из целевой функции исключены базисные переменные и она записана в форме (3.3).

Перейдем теперь к описанию симплекс-таблицы. Пусть ЗЛП записана в табличном виде:

(3.4)

Тогда заполненная симплекс-таблица выглядит так.

Таблица 3.1.

Базис	Переменные	Свободные члены
			...	x k			...
			...				...
			...				...
. . .	. .	. .	...	. .	. .	. .	...	. .	. . .
			...				...
f			...				....

Опорный план ЗПЛ: ..., называется опорным планом, соответствующим этой симплекс-таблице. Как видно из формулы (3.2), значение целевой функции при этом опорном плане равно γ 0 .

Рассмотрим пример. Привести к табличному виду следующую ЗЛП и заполнить симплекс-таблицу:

Вначале ЗЛП следует привести к каноническому виду. Для этого функцию f нужно заменить на - f:

Система уравнений должна быть записана в жордановой форме с неотрицательными правыми частями. Общий прием, с помощью которого это достигается, будет рассмотрен позднее (параграф 3.7). В нашем примере такая жорданова форма уже есть с базисными переменными и . Исключим базисные переменные из целевой функции - f. Для этого выразим их через свободные и подставим эти выражения в целевую функцию.

Табличный вид ЗЛП таков:

Заполним симплекс-таблицу (для сокращения записей первый столбец озаглавлен "Б", последний столбец - "Q").

Таблица 3.2.

Б			Q
		-5
	-7	-2
-f	-4		-20

Опорный план, соответствующий этой симплекс-таблице, имеет вид:

Значение функции - f при этом опорном плане равно - 20.

Пусть имеется заполненная симплекс-таблица. Сформулируем условие оптимальности опорного плана.

Если в нижней строке симплекс-таблицы все числа, кроме, быть может, самого правого, неположительны , то опорный план, соответствующий этой таблице, оптимален.

Для простоты обоснуем справедливость этого утверждения на примере. Пусть заполненная симплекс-таблица имеет вид:

Таблица 3.3.

Б				Q
		-1
			-1
f	-5	-3	-1

Значение целевой функции при опорном плане, соответствующем симплекс-таблице, равно 6. Выпишем целевую функцию в табличном виде:, откуда . Так как при любом допустимом решении ЗЛП переменные принимают только неотрицательные значения, то из последней записи целевой функции видно, что ее значение в любой точке ОДР не меньше 6. Следовательно, минимальное значение целевой функции на ОДР равно 6 и оно достигается при опорном плане, соответствующем симплекс-таблице, .

3.4. Условие неразрешимости ЗЛП из-за неограниченности снизу на ОДР целевой функции.

Если для ЗЛП заполнена симплекс-таблица, то ОДР задачи непуста, так опорный план, соответствующий симплекс-таблице, принадлежит ОДР. Однако ЗЛП может быть неразрешимой из-за неограниченности снизу на ОДР целевой функции.

Условие неразрешимости формулируется так.

Если симплекс-таблица содержит хотя бы один столбец, отличный от самого правого, у которого в нижней строке стоит положительное число, а во всех остальных строках столбца - неположительные числа, то ЗЛП неразрешима из-за неограниченности снизу на ОДР целевой функции.

Для обоснования снова воспользуемся примером.

Таблица 3.4.

Б				Q
			-2
	-3		-1
f		-1

Столбец в нижней строке содержит положительное число, а в остальных строках - неположительные числа. Докажем неразрешимость ЗЛП.

Выпишем жорданову форму, соответствующую симплекс-таблице, и перенесем члены, содержащие , в правую часть. Получим

Пусть а - произвольное положительное число. Очевидно, ЗЛП имеет следующее допустимое решение:. Вычислим значение целевой функции при этом допустимом решении. Из таблицы 3.4 имеем:

. При указанном допустимом решении f = 4 - 2а. Отсюда видим, что значение целевой функции может стать как угодно малым при достаточно большом значении а. Иначе говоря, целевая функция не ограничена снизу на ОДР. Следовательно, ЗЛП неразрешима.

3.5. Переход к новому опорному плану.

Предположим, что условия оптимальности и неразрешимости не выполняются. Тогда симплекс-метод переходит к новому опорному плану. Этот переход совершается за счет выведения из базиса одной из базисных переменных и введения в базис одной из свободных переменных. При этом должны выполняться следующие два условия:

1) новый базис должен быть по-прежнему допустимым, т.е. правые части соответствующей жордановой формы должны быть по-прежнему неотрицательными;

2) при новом опорном плане значение целевой функции не должно превышать ее значения при прежнем опорном плане.

Столбец симплекс-таблицы, в котором стоит переменная, вводимая в базис, называется генеральным столбцом . Строка, в которой стоит переменная, выводимая из базиса, называется генеральной строкой . Элемент, стоящий на пересечении генеральной строки и генерального столбца, называется генеральным элементом .

Правило выбора генерального элемента.

В качестве генерального столбца выбирается любой столбец симплекс-таблицы, отличный от самого правого, у которого в нижней строке стоит положительное число. Затем рассматриваются только те строки симплекс-таблицы, отличные от самой нижней, у которых на пересечении с генеральным столбцом стоят положительные числа. Для каждой из таких строк вычисляется отношение свободного члена к элементу, стоящему в генеральном столбце. Строка, для которой это отношение минимально, выбирается в качестве генеральной. Элемент, стоящий на пересечении генеральной строки и генерального столбца, и будет генеральным элементом.

Проиллюстрируем это правило на примере.

Таблица 3.5.

Б			Q
	2	-1

	-2
F

В качестве генерального столбца можно выбрать либо столбец , либо столбец . Выберем (чаще всего выбирают тот столбец, у которого внизу большее положительное число). Теперь приступим к выбору генеральной строки. Для этого рассмотрим две строки - и . Составляем отношения 4:2 и 8:3. Меньшее значение имеет отношение 4:2, поэтому первую строку выбираем в качестве генеральной. Следовательно, генеральный элемент равен 2 - он стоит на пересечении столбца и строки .

После выбора генерального элемента нужно перейти к новому опорному плану, при котором переменная становится базисной, а переменная х 1 - свободной. Коэффициент при в новой жордановой форме должен быть равен 1. Поэтому первая строка таблицы 3.5 делится на 2. Умножив затем полученную первую строку на (-3) и прибавив ко второй строке, исключим из второго уравнения. Аналогично, с помощью жордановой процедуры исключаем из третьего уравнения и из целевой функции (последнее требует табличный вид ЗЛП).

В результате получим следующую таблицу.

Таблица 3.6

Б						Q



f						-2

Обратим внимание, что в столбце Q в первых трех строках стоят неотрицательные числа, т.е. новый базис по-прежнему является допустимым. Это не случайный факт: так будет всегда при точном соблюдении правила выбора генеральной строки. Далее, значение целевой функции при новом опорном плане равно -2, при старом оно было равно 12. "Улучшение" опорного плана гарантирует правило выбора генерального столбца. Хотя эти факты мы строго не доказываем, следует иметь в виду, что они всегда имеют место.

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

3.6. Табличный симплекс-алгоритм.

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

1. Если в нижней строке симплекс-таблицы все числа, кроме, быть может, самого правого, неположительны, то опорный план, соответствующий симплекс-таблице, оптимален, и алгоритм останавливается. В противном случае - переход пункту 2.

2. Если симплекс-таблица содержит столбец, отличный от самого правого, у которого в нижней строке стоит положительное число, а во всех остальных строках - неположительные числа, то ЗЛП неразрешима из-за неограниченности снизу на ОДР целевой функции, и алгоритм останавливается. В противном случае - переход к пункту 3.

3. Выбираем любой столбец, отличный от самого правого, у которого в нижней строке стоит положительное число - назовем его генеральным. Затем рассматриваем строки симплекс-таблицы, отличные от самой нижней, у которых в генеральном столбце стоят положительные числа. Для каждой из таких строк вычисляем отношение свободного члена к элементу, стоящему в генеральном столбце. Строка, для которой это отношение минимально, является генеральной строкой. Элемент, стоящий на пересечении генерального столбца и генеральной строки, будет генеральным элементом. Переход к пункту 4.

4. Составляем новую симплекс-таблицу, в которой:

1) из базиса выведена переменная, стоящая в генеральной строке; в базис введена переменная, стоящая в генеральном столбце;

2) генеральная строка поделена на генеральный элемент;

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

Пример I. Решить симплекс-методом

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

x 3 =10 - 2x 1 - x 2

x 4 = 8 - x 1 - 2x 2

и подставим в целевую функцию

Для получения табличного вида функцию запишем так:

Теперь имеем табличный вид ЗЛП:

Заполним первую симплекс-таблицу

Таблица 3.7

Б					Q


F

В таблице 3.7 условия оптимальности и неразрешимости не выполняются. Выберем в качестве генерального столбец , у которого в нижней строке стоит положительное число. Затем, сравнивая отношения 10:3 и 8:1, выберем первую строку в качестве генеральной. В таблице генеральный элемент 2 .

Действуя в соответствии с пунктом 4 табличного симплекс-алгоритма, перейдем к таблице 3.8.

Таблица 3.8

Б		Q


F	-5	-22

Условия оптимальности и неразрешимости не выполняются. Выбираем в таблице 3.8 генеральный элемент и переходим к следующей таблице

Таблица 3.9

Б					Q


F					-24

Таблица 3.9 удовлетворяет условию оптимальности.

Ответ: оптимальный план

Минимальное значение целевой функции f min = - 24.

Пример 2 . Решить симплекс-методом:

Прежде всего, ЗЛП нужно привести к каноническому виду

Теперь приводим ЗЛП к табличному виду. Видим, что система уравнений записана в жордановой форме с неотрицательными правыми частями (и z- базисные переменные). Однако в целевую функцию входит базисная переменная. Имеем:

Следовательно, табличный вид ЗЛП таков:

Заполняем симплекс-таблицу (таблица 3.10).

Таблица 3.10

Б			z	Q
	-1
z		-2
g				-1

После выбора генерального элемента переходим к таблице 3.11

Табличный вид ЗЛП. Симплекс - таблицы.

СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗЛП

3.1. Общая характеристика и основные этапы симплекс – метода

Опишем общую идею симплекс-метода.

При решении ЗЛП симплекс-методом можно выделить следующие этапы:

1) приведение ЗЛП к каноническому виду;

3) исследование опорного плана на оптимальность;

4) исследование ЗЛП на неразрешимость из-за неограниченности снизу на ОДР целевой функции;

5) переход к новому, "лучшему" опорному плану.

В табличном виде целевая функция записывается так:

где .

Отметим следующие особенности табличного вида ЗЛП:

а) система линейных уравнений приведена к жордановой форме с неотрицательными правыми частями;

б) из целевой функции исключены базисные переменные и она записана в форме (3.3).

Перейдем теперь к описанию симплекс-таблицы. Пусть ЗЛП записана в табличном виде:

(3.4)

Тогда заполненная симплекс-таблица выглядит так.

Признак оптимальности опорного плана

Если в симплекс-таблице, содержащей некоторый опорный план, все элементы f-строки (не считая свободного члена) неотрицательны, то этот опорный план является оптимальным.. Пусть в f-строке табл. 2.b 0j > (i=1, ..., n m). В опорном плане х 0 , содержащемся в этой таблице, значения всех свободных переменных x m+j равны нулю и f(х 0) =b 00 . Если же увеличивать какую-либо из свободных переменных x m+ j, то, как видно из равенства (2.5), в силу неотрицательности b 0j значение f(х) начнет уменьшаться. Следовательно, при x о функция f(х) достигает наибольшей величины, а значит, х 0 действительно является оптимальным опорным планом.

Возможность переход от одного опорного плана к другому

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

Докажем этот признак. Установим правила выбора переменных для такого преобразования начального базиса Б о с опорным планом х 0 в новый базис Б 1 с опорным планом х 1 при котором; значение функции f увеличивается, т. е. f(x i)>f(x 0). Тогда по правилу пересчета элементов из симплекс-таблицы преобразуем к новому базису, что позволит найти компоненты нового опорного плана.

Допустим, что в табл. 2.1, например, b 0s <0, а среди элементов b is s-го столбца есть хотя бы один положительный. Полагая в равенстве (2.5) все свободные переменные х m+j кроме x m+s , равными нулю, получаем f = b oo -- b os xm+s . Из этого равенства видно, что при увеличении x m+s значение f тоже возрастает. Таким образом, при указанных в признаке условиях действительно есть возможность увеличить f(x), переходя к планам, в которых x m+s принимает положительные значения, а все остальные компоненты x m+j по-прежнему равны нулю. Покажем, что среди таких планов существует и опорный. Тем самым будет найден путь направленного преобразования базиса Б о в новый базис Б 1 . В самом деле, если переменная x m+s принимает положительное значение в некотором опорном плане, значит, она является в нем базисной компонентой (в опорном плане x о она была свободной компонентой и равнялась нулю). Поэтому прежний базис следует преобразовать за счет включения в него переменной x m+s . Но здесь предстоит решить два вопроса:

1) какую из переменных следует вывести из прежнего базиса, чтобы освободить место для переменной x m+s ;

2) какое значение должна принимать новая базисная переменная x m+s в новом опорном плане.

Для решения поставленных вопросов допустим, что в равенствах (2.4) все x m+j , кроме x m+s , равны нулю. Тогда

x i = b io -b is x m+s (i=l, ..., m)

Из этих равенств видно, что с возрастанием x m+s значения тех базисных переменных х i для которых коэффициенты b is <0, тоже будут расти, оставаясь положительными. Значит, на отрицательные коэффициенты b is можно внимания не обращать, так как они не влияют на знак базисных переменных. Иначе обстоит дело с базисными переменными, у которых b is >0. С увеличением x m+s значения этих переменных станут уменьшаться, и наступит момент, после которого они будут принимать отрицательные значения и перестанет выполняться условие (2.3). Этого допустить нельзя. Поэтому выясним, до какого предельного значения можно увеличивать x m+s , не нарушая условия неотрицательности базисных переменных. С этой целью выпишем из системы (2.6) те равенства, в которых b is >0. Допустим, что это касается равенств с номерами i=d,…,k,…,p:

x d =b do -- b ds x m+s ,

…………………..

x k =b k0 - b ks x m+s ,

………………….

x p =b p0 - b ps x m+s .

Базисные переменные х d , ..., x k , ..., x p будут оставаться неотрицательными до тех пор, пока x m+s удовлетворяет системе неравенств

b do - b ds x m+s >0, x m+s

……………… ………………

b k0 - b ks x m +s >0 или x m+s < b ko /b ks

……………… ………………

b p0 - b ps x m+s >0 x m+s < b po /b ps

т. е. при x m+s
Пусть наименьшая из дробей b io /b is соответствует i = k, т.е.

min { b io /b is }= b k0 /b ks .

Тогда можно сказать, что пока x m+s не превышает величины b k0 /b ks , т. е. x m+s 0, то переменная х k станет равной пулю: x k = b k0 -- b ks b ko /b ks =0, и тем самым будет произведено преобразование базиса Б о = {х 1 ; ...; x k ; ...; х m } в новый базис, при котором переменная x m+s из группы свободных переходит в базисные, а переменная х k занимает место x m+s в группе свободных. При этом все остальные свободные переменные по-прежнему равны нулю, а остальные базисные переменные по-прежнему положительны. Следовательно, базисный план х 1 в новом базисе Б 1 ={х 1 ; ...; x m+s ; ...; x m } будет иметь m положительных компонент и m-n нулевых. В плане x 1 некоторые базисные переменные могут принять нулевые значения в двух случаях:

1) когда в плане х 0 имеются базисные переменные, равные нулю;

2) когда наименьшая из дробей b io /b is будет соответствовать двум или нескольким номерам i.В нашем же случае она соответствует только i = k.

Переменная, подлежащая включению в базис, определяется отрицательным элементом f-строки. Из равенства f =b oo - b os x m+s ясно, что при b 0s <0 и фиксированном x m+s >0, значение f(х) зависит от абсолютной величины коэффициента b 0s: чем больше |b 0s |, тем большее значение получит f(х) в новом базисе. Но из этого равенства видно также, что значение целевой функции в новом базисе зависит и от величины, принимаемой новой базисной переменной x m+s . Будем выбирать переменную, вводимую в базис, ориентируясь лишь на отрицательные элементы f-строки. Поэтому, когда в f-строке несколько отрицательных элементов, в базис будем вводить переменную x m+j ,соответствующую отрицательному элементу с наибольшей абсолютной величиной. Столбец коэффициентов при переменной, включаемой в базис, называют разрешающим. Таким образом, выбирая переменную, вводимую в базис (или выбирая разрешающий столбец) по отрицательному элементу f-строки, мы обеспечиваем возрастание функции f.

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

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

Отметим, что нам уже известно значение новой базисной переменной x m+s в новом опорном плане: оно равно b ko /b ks . Что же касается численных значений остальных базисных переменных в новом опорном плане и соответствующего значения f(х), то их можно найти лишь после того, как измененная система базисных переменных х 1 ;..., x m+s ; ...,х m будет выражена через измененную систему свободных переменных x m+1 ,…,x k ,…, х n . Для этого установим; правила, по которым осуществляется преобразование условий задачи от одного базиса к другому.

Коэффициент b ks = 0 при x m+s в этом уравнении называют разрешающим элементом. В равенстве (2.7) новая базисная переменная x m+s выражена через свободные переменные, среди которых находится теперь и бывшая базисная переменная х k . Таким образом, переменные x m+s и x k поменялись ролями.

Аналогично выразим через новый набор свободных переменных и остальные базисные переменные. С этой целью значение x m+s из подставим в остальные равенств (обозначим f через x 0 ,тогда равенство будет входить в систему при i= 0)

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