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

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

• Вместо базисной переменной x_k записываем x_l; вместо небазисной переменной x_l записываем x_k.  

• ведущий элемент заменяется на обратную величину a_k,l'= 1/a_k,l

• все элементы ведущего столбца (кроме a_k,l) умножаются на -1/a_k,l

• все элементы ведущей строки (кроме a_k,l) умножаются на 1/a_k,l

• оставшиеся элементы симплекс-таблицы преобразуются по формуле a_i,j'= a_i,j- a_i,lx a_k,j/ a_k,l

Правило оценки плана на оптимальность

В оптимальном плане при решении задачи на максимум все оценки в строке z_j-c_j должны быть положительными. При решении на минимум – отрицательными.

44. Правила составления исходной матрицы и первого (опорного, базисного) плана симплексного м-метода линейного программирования.

Если задача линейного программирования задана в каноническом виде. Составим расширенную матрицу и выделим с помощью метода Жордана-Гаусса базисные переменные. Примем в качестве базисных – переменные х1 и х2.

• Заполняем шапку таблицы: в шапке первых трёх столбцов пишем соответственно СБ, БП и ХБ; в нижних половинах строки, разделённой пополам, запишем все имеющиеся в последней записанной ЗЛП переменные (включая дополнительные и искусственные); в шапке последнего столбца запишем Q.

• Заполняем строку над переменными в каждую верхнюю ячейку строки, разделённой пополам, запишем коэффициент целевой функции 𝑧 при переменной, стоящей в соответствующей нижней (зелёной) ячейке (при этом считаем, что если какая- то переменная отсутствует в целевой функции 𝑧, то соответствующий этой переменной коэффициент равен нулю).

• Заполняем столбец БП («базисные переменные») для заполнения первой ячейки столбца БП внимательно рассмотрим левую часть первого уравнения; если в ней присутствует искусственная переменная 𝑤𝑖, то эту переменную 𝑤𝑖 запишем в первую ячейку столбца БП, а если в левой части первого уравнения искусственная переменная 𝑤𝑖 отсутствует, то в первую ячейку столбца БП запишем дополнительную переменную 𝑢1. Аналогично заполняются все остальные ячейки столбца БП.

• Заполняем столбец СБ справа от 𝑤𝑖 (см. столбец БП) запишем −𝑀, а справа от 𝑢𝑖 запишем 0.

• Заполняем столбец ХБ: в него запишем правые части уравнений.

• Заполняем столбцы, соответствующие всем имеющимся переменным: в столбец, соответствующий первой переменной 𝑥1, запишем коэффициенты при этой переменной 𝑥1 в левых частях уравнений, в столбец, соответствующий следующей переменной 𝑥2′ запишем коэффициенты при этой переменной 𝑥2′ в левых частях уравнений, и т.д. до тех пор, пока не заполним столбец, соответствующий последней переменной, записанной в шапке таблицы. При этом учтём, что если данная переменная в некотором уравнении отсутствует, то соответствующий коэффициент равен нулю.

• Заполним последнюю строку столбца ХБ: туда запишем сумму произведений соответствующих элементов столбцов СБ и ХБ;

• Заполним все остальные ячейки последней строки от суммы произведений соответствующих элементов столбца СБ и рассматриваемого столбца - отнимем число, стоящее в рассматриваемом столбце над переменной.

• Q – заполняется после оценки симплекс таблицы на оптимальность.