Реферат: Решение задач симплексным методом

am1 x1 + am2 x2 + . . . + amn xn Ј bm ;

x1 і 0, x2 і 0, . . . , xn і 0 .

Эти ограничения называются условиями неотрицательности. Если все ограничения заданы в виде строгих равенств, то данная форма называется канонической.

В матричной форме задачу линейного программирования записывают следующим образом. Найти max cT x

при условии

A x Ј b ;

x і 0 ,

где А - матрица ограничений размером ( mґn), b(mґ1) - вектор-столбец свободных членов, x(n ґ 1) - вектор переменных, сТ = [c1, c2, ... , cn ] - вектор-строка коэффициентов целевой функции.

Решение х0 называется оптимальным, если для него выполняется условие сТ х0 і сТ х , для всех х О R(x).

Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.

Для решения задач данного типа применяются методы:

1) графический;

2) табличный ( прямой, простой ) симплекс - метод;

3) метод искусственного базиса;

4) модифицированный симплекс - метод;

5) двойственный симплекс - метод.

1.2 Табличный симплекс - метод

Для его применения необходимо, чтобы знаки в ограничениях были вида “ меньше либо равно ”, а компоненты вектора b - положительны.

Алгоритм решения сводится к следующему :

Приведение системы ограничений к каноническому виду путём введения дополнительных переменных для приведения неравенств к равенствам.

Если в исходной системе ограничений присутствовали знаки “ равно ” или “ больше либо равно ”, то в указанные ограничения добавляются

искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.

Формируется симплекс-таблица.

Рассчитываются симплекс-разности.

Принимается решение об окончании либо продолжении счёта.

При необходимости выполняются итерации.

На каждой итерации определяется вектор, вводимый в базис, и вектор, выводимый из базиса. Таблица пересчитывается по методу Жордана-Гаусса или каким-нибудь другим способом.

1.3 Метод искусственного базиса

Данный метод решения применяется при наличии в ограничении знаков “ равно ”, “ больше либо равно ”, “ меньше либо равно ” и является модификацией табличного метода. Решение системы производится путём ввода искусственных переменных со знаком, зависящим от типа оптимума, т.е. для исключения из базиса этих переменных последние вводятся в целевую функцию с большими отрицательными коэффициентами m , а в задачи минимизации - с положительными m . Таким образом из исходной получается новая m - задача.