Реферат: Графический метод и симплекс-метод решения задач линейного программирования

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

Множество планов канонической задачи – выпуклое многогранное множество, имеющее конечное число угловых точек. И если эта задача имеет оптимальное решение, то оно достигается хотя бы в одной угловой точке.

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

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

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

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

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

Общая схема симплекс-метода состоит из следующих основных шагов.

· шаг 0 . Определение начального базиса и соответствующей ему начальной угловой точки (базисного плана) .

· шаг 1 . Проверка текущего базисного плана на оптимальность. Если критерий оптимальности выполнен,топлан оптимален и решение закончено. Иначе переход на шаг 2.

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

· шаг 3 . Нахождение переменной, исключаемой из состава базисных переменных (Из условия сохранения ограничений задачи).

· шаг 4 . Нахождение координат нового базисного плана (смежной угловой точки). Переход на шаг 1.

Повторяющиеся шаги 1–4 образуют одну итерацию симплекс-метода.

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

Определение . Будем говорить, что каноническая задача ЛП имеет "предпочтительный вид", если

1. правые части уравнений , .

2. матрица условий содержит единичную подматрицу размера

.

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

Пример 2.1.

Матрица условий A и вектор правых частей ограничений b имеют вид

, ,

а целевой вектор с = (1, -3, 0, 4, 2).

Сразу очевидна одна базисная матрица: с единичными векторами условий.

Следовательно, выбирая в качестве базисных переменных x₁ , x₃ ,x₅ ^, и полагая в системе уравнений x₂ = x₄ = 0 (небазисные переменные), немедленно находим x₁ = 10,x₃ = 20,x₅ = 8, так что начальный базисный план x⁰ = (10, 0, 20, 0, 8).Видим, что значения базисных переменных равны правым частям ограничений. Из этого понятно требование положительности правых частей b_i .

В дальнейшем, базисные переменные будем объединять в вектор x_Б.