8. Решение слу методом ж-г. Общее решение, частное, базисное и опорное.

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

1. X₁+0X₂+…+0X_n=B_i, (Bi≠0)

сист. несовместна – решений нет

2. 1 0 … B’1

0 1 …. B’2

…

0 0 … B’n

сист. имеет единственное решение Xn=Bn

3. 1 0 … A’_1r+1 … A’_1n | B’₁

0 1 … A’_2R+1 … A’_2n | B’₂

…

0 0 … 1 A’_rr+1 … A’_rn | B’_r

расширенная матрица – сист. имеет мн-во решений:

X_r=B’_r-A’_rr+1X_r+1-…-A’_rnX_n

Придавая каждой из стоящих в правых частях равенств переменных X_n произвольные значения получим частные решения. Неизвестные X_r – базисные (основные); соотв. линейно-независимым векторам A_r. Т.о. r переменные – базисные (основные), если определитель матрицы коэф. при них отличен от 0, а остальные (n-r) – свободные (неосновные). Базисное решение – частное решение, в котором неосновные переменные имеют нулевые значения. Каждому разбиению на основные и неосновные переменные соотв. одно базисное решение, а кол-во способов разбиения не превышает величины

_m n!

С =__________

ⁿ m!(n-m)!

Если все компоненты базисного решения неотр. – решение опорное.

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

В основе математического метода получения оптимального решения лежат основные свойства ЗЛП:

1.Не существует локального экстремума отличного от глобального. Если экстремум есть, то он единственный.

2.Множество всех планов ЗЛП является выпуклой многогранной областью (многогранником решения).

3.ЦФ в ЗЛП достигает своего max (min) значения в угловой точке многогранника решения (в вершине). Если ЦФ принимает max решение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек.

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

Суть симплекс-метода состоит в том, что вначале получают допустимый вариант, удв. всем ограничениям, но обязательно оптимальный (начальное опорное решение); оптимальность достигается последовательным улучшением исходного варианта за опред. число этапов. Нахождение начального опорного решения и переход к сл. проводятся на основе применения метода Жордана-Гаусса для сист. линейных уравнений в канонической форме, в которой должна быть предварительно записана исходная ЗЛП; направление перехода от одного опорного решения к др. выбирается при этом на основе критерия оптимальности ЦФ. Этапы:

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

2. переход к нехудшему решению

3. проверка оптимальности допустимого базисного решения

10. Симплекс-метод с естественным базисом, алгоритм метода.

Для его применения КЗЛП должна содержать единичную подматрицу M*N. В этом случае очевиден начальный опорный план (неотр. базисное решение системы ограничений КЗЛП). Проверка на оптимальность опорного плана происходит с помощью признака оптимальности. Переход к другому опорному плану проводится с помощью преобразований Жордана-Гаусса. Полученный новый опорный план проверяется снова на оптимальность и т.д. Процесс заканчивается за конечное число шагов, причем на последнем шаге либо выявляется неразрешимость задачи, либо получается оптимальный опорный план и соответствующее ему оптимальное значение ЦФ. Признак оптимальности состоит из двух теорем:

1.Если для всех векторов А₁,А₂,…,А_n системы ограничений выполняется условие ∆j = Z_j – C_j ≥ 0, где Z_j = ∑ C_i A_ij, то полученный опорный план является оптимальным.

2.Если для некоторого вектора, не входящего в базис, выполняется условие ∆j = Z_j – C_j < 0, то можно получить новый опорный план, для которого значение ЦФ будет больше исходного, при этом могут быть два случая:

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

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

На основании признака оптимальности в базис вводится вектор A_k, давший мин. отрицат. величину симплекс-разности: ∆k = min (Z_j – C_j), j = 1,‾n.

Чтобы выполнялось условие не отрицат. значений опорного плана, выводится из базиса вектор A_r, который дает мин. положит. оценочное отношение: Q = min B_i/A_ik = B_r/A_rk, A_ik >0, i = 1,m. Строка A_r - направляющая, столбец A_k и элемент A_rk - направляющими.

Элементы направляющей строки в новой симплекс-таблице вычисляются по формулам:

a’_rj = a_rj / a_rk, j = 1,n.

Элементы i-той строки:

a’_ij = (a_ij a_rk – a_rj a_ik) / a_rk, i = 1,m, j = 1,n, i ≠ r.

Значения нового опорного плана:

b’_r = b_r / a_rk для i=r;

b’_i = (b_i a_rk – b_r a_ik) / a_rk для i≠r.

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