Материал: 4-1

xj = β > 0. Тогда решение системы x1 = f1 − hijβ, ..., xm = fm − hmjβ, xm+1 = 0, ..., xj = β, xj+1=0, ..., xn = 0 будет неотрицательным, то есть дает план при любом β > 0. По (12) F (X) = F (X0) − jβ и при

β → +∞ будет F (X) → +∞). Форма принимает сколь угодно большие значения и максимума не имеет. Утверждение доказано.

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

Каноническая задача линейного программирования называется невырожденной, если все ее опорные планы невырожденные.

Предположим, что найден невырожденный опорный план

Xo = (x01, ..., x0m, 0, ..., 0), то есть допустимое базисное решение системы ограничений. Ранее было показано, как можно переходить от одного допустимого базисного решения к другому. Пусть ключевой столбец имеет номер s, а ключевая строка - номер r.

Тогда новый план X0 будет иметь компоненты, задаваемые формулами (90), и остальные компоненты равные нулю.

По формуле (12)

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

Указанный метод нахождения оптимального плана называется симплексным методом.Этот метод в основном и применяется на практике.

Опишем подробно содержание симплексного метода.

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

4) оценки для нового опорного плана.

Напомним, что оценка свободной неизвестной xj вычисляется так:

m

X

j = cihij−cj. Здесь суммирование ведется по всем номерам базисных

i=1

неизвестных. В новом плане введена базисная неизвестная xs и выведена неизвестная xr, поэтому новая оценка 0j будет иметь вид

Здесь использованы формулы (13). Если в скобке, стоящей под знаком

Поэтому, добавляя к сумме нуль, можно считать что в ней имеется и слагаемое с i = r. Тогда, раскрывая скобки, находим

Если все оценки неотрицательны, то новый план X0 оптимальный и F (X0) = maxF (X). Если имеются отрицательные оценки и существует оптимальный план, следует повторить шаг процесса.

Однотипная структура всех формул (13) - (16) подсказывает удобную запись результатов всех вычислений в таблице (см. таблицу 3).

Объясним составление этой таблицы, называемой симплексной.

Во втором столбце Б выписаны базисные неизвестные, в первом С - коэффициенты линейной формы, стоящие при этих неизвестных. В

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

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

Опишем получение последней строки таблицы: в ней записывают оценки свободных неизвестных, то есть суммы произведений ci на элементы

столбца, сложенные с величинами −cj, стоящими в самой верхней строке,

m

X

а F (X) = cifi.

i=1

После того как таблица составлена и выбран ключевой элемент hrs, следующий шаг симплексного метода делается так: 1) в первом столбце cr заменяется на cs, во втором xr -на xs; 2) коэффициенты ключевой строки во всех остальных столбцах, кроме последнего, делятся на hrs; 3) каждый новый коэффициент в остальных строках вычисляется как определитель второго порядка, у которого в левом верхнем углу записан старый коэффициент, в правом верхнем углу - коэффициент из той же строки и ключевого столбца, в левом нижнем углу - коэффициент из того же столбца и преобразованной ключевой строки, в правом нижнем углу 1 (правило прямоугольника); 4) контролируется правильность вычислений; 5) если среди оценок есть отрицательные, то выбирается новый ключевой столбец, заполняется последний столбец таблицы и находится ключевая строка. После чего начинается следующий шаг процесса.

Отметим, что в случае вырожденного опорного плана, метод замещения базисных неизвестных может привести к тому же плану. Этот случай мы не рассматриваем.

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

Пример 4. Решить каноническую задачу линейного программирования

которые являются базисными переменными. Составим симплексную таблицу

В последней строке таблицы оценка переменной x1 равна -3. Первый столбец выберем ключевым. Третья строка является ключевой, так как

Ответ: F (X2) = max F (X) = 11. Оптимальным планом является

X2 = (5, 0, 0, 11, 4, 0).