9.Аналитический метод решения злп mxn (симплекс-метод). Для задач на минимум и максимум.

Это общий аналитический метод решений ЗЛП.

Симплексом на плоскости или в пространстве является простой выпуклый многоугольник или многогранник, который строится на основе ограничений.

В трёхмерном пространстве простейший симплекс – тетраэдр.

Геометрически симплекс-метод состоит в последовательном переходе от 1 вершины многогранника решений к другой, в которой линейная функция F(x) принимает нехудшее значение по отношению цели задачи, до тех пор пока не будет найдено оптимальное решение. Т.е. будет найдена вершина, где достигается оптимум задачи.

Для реализации симплекс-метода необходимо установить 3 основы:

1)Способ определения какого-либо начального допустимого базисного решения.

2)Правило перехода к лучшему по сравнению с предыдущем решению

3)Критерий проверки оптимального найденного решения

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

)(под макс и мин икс с чертой нарисуйте)

Считаем, что rang системы ограничений равен: r = r(A|B) n

В дальнейшем: r = m n система совместна

Выберем какие-либо m базисных переменных из x₁…x_n, остальные – свободные.

x₁…x_m – базис, x_m+1…x_n – свободные.

Выразим базисные через свободные при помощи системы ограничений.

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

Если среди есть равное нулю, то

Если ЗЛП разрешима, то оптимум F(x) достигается хотя бы в одной из угловых точек допустимого множества решений.

Т.к. базисное решение соответствует различным вариантам выбора m базисных переменных из общего числа n x_j, то количество ДБР .

Идея метода в направлении перебора угловых точек с последующим увеличением, если ищется max(F(x)), или уменьшением, если ищется min(F(x)).

10.Симплекс-таблицы в симплекс-методе для задач на максимум и минимум

Рассмотрим реализацию алгоритма симплекс-метода при помощи симплекс-таблиц. В симплекс-таблице записываются:

1)Коэффициенты С_i при x_i

2)допустимое базисное решение

(n-m)

x_m+1=…=x_n=0

3)Коэффициенты

Симплекс-таблица:

δ	Сб	β	X1	Xk	…	Xm	Xm+1	…	Xn
X1	C1		1	0	…	0		…
…	…	…	…	…		…
Xk	Ck		0	1	…	0		…
…	…	…	…	…		…
Xm	Cm		0	0	…	1		…
			0	0		0

C_б = (С₁…С_n) =>

(это вид коэффициента в случае задач на min)

В случае задач на max:

Признак оптимальности для ЗЛП: Если все коэффициенты (для задач на min и на max), то полученное допустимое базисное решение является оптимальным.

Предположим, что не все .

Пусть такой, что

x_l нужно сделать базисной

Соответствующий столбец в симплекс таблице – разрешающий. В разрешающем столбце нужно проанализировать коэффициенты α_il.

Если среди них нет положительных, то в этом случае ЗЛП не имеет решений. Если такое число найдётся, то решение существует.

“-“, ”∞”

i=k

k – номер разрешающей строки

Min надо искать среди ненулевых коэффициентов.

K – показывает номер базисной переменной x_k, которую нужно сделать свободной.

При переходе к новому базису(новой симплекс-таблице) нужно произвести следующие замены:

1)В 1ом столбце x_k заменить на x_l и соответствующие коэффициенты C_k на C_l. Это делается чисто формально.

2)В столбцах, соответствующих базисных переменных ставим нули и единицу. При чём единицу напротив соответствующей главной переменной. В последней строке ставим нули.

3)В k-ой строке все остальные элементы нужно поделать на опорный элемент:

- опорный(разрешающий) элемент

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