33. Симплекс таблицы, их заполнение. Формы расчета коэффициентов индексной строки

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

строке шапки симплекс-таблицы указаны векторы исходной системы ограничений задачи, во второй – коэффициенты при переменных в целевой функции задачи. В первом столбце (столбец 1Б ) указаны векторы, образующие базис заданной системы векторов, во втором – коэффициенты целевой функции при базисных переменных. Во всех остальных клетках таблицы кроме последней строки, стоят коэффициенты разложения соответствующих векторов по векторам базиса. Так как для нашей задачи выбран единичный базис, то в первой симплексной таблице в столбцах B1, A1, A2, A3, A4, An будут стоять соответствующие коэффициенты системы ограничений. Последняя строка называется индексной. В третьем столбце этой строки стоит значение целевой функции при проверяемом опорном плане. Во всех остальных клетках индексной строки находятся оценки оптимальности z j − c j для векторов исходной системы. Здесь z j – значение целевой функции, если в неё вместо переменных подставить коэффициенты разложения вектора Aj по векторам базиса, а c j – коэффициенты целевой функции при соответствующих переменных. по данной формуле вычисляются оценки оптимальности.

Индексная строка рассчитывается следующим образом:

34.Теорема оптимальности плана задач линейного программирования, следствие из теоремы. Оценки оптимальности при решении задачи симплекс-методом.

Если хотя бы для одного вектора Аj в разложении А1х1+А2х2+А3х3+…=В, А=(А1,А2,А3,…) – переменные модели выполняется условие Zj-Cj>0, то X_Б1 (начальный опорный план) не явл. opt и можно построить любой др. opt план, где будет выполнятся условие Z(Х_Б2) ≤ Z(X_Б1). Zj-Cj – оценкиоптимальности, Zj – значение целевой ф-ии, если в нее вместо переменных подставить коэф. разложения j-вектора по векторам базиса, Cj- коэф. при j-той переменной. Следствие из теоремы: Если для всех Аj в разложении вып. условие Zj-Cj≤0, j=1,n, то проверяемый опорный план – оптимальный.

Замечание. В теореме и следствии предполагается, что задача находится в кан.форме с целевой функцией на минимум.Однако симплекс-методом можно решать и задачи с целевой функцией на максимум. В этом случае при анализе значений оценок используется их противоположный смысл, то есть план будет оптимальным, если все оценки оптим.будут не отрицательными(положит. И нулевые)

35.Выбор вектора, вводящегося в базис и выводящегося из базиса.Стимплекс отношение.

Если в индексной строке стоят отрицат. или – 0-ые оценки, то проверяемы опорный план – оpt, если положительные, то необходимо пересчитать С-Т. Для этого необх. выделить векторы, которые вводятся и выводятся из базиса. На их пересечении будет стоять разрешающий эл-т таблицы. В базис вводится вектор, которому соответствует положительная оценка оpt, если их несколько, то вводится вектор с наибольшей положительной оценкой Opt. Из базиса выводится вектор, которому соответствует симплексное отношение, опред. по ф.: Q=min (b_i/Xij). Пересчет С-Т проводят по правилу полных Жордановых исключений: 1 метод: с помощью элементарных преобразований Гауса делают так, чтобы направляющий столбец стал единичным, т.е. таким как столбец, соответствующий вектору выводимому из базиса. Используют 2 элемент.преобразования – 1) направляющая строка умножается на любое число, отличное от «0», 2) направляющ. строка умножается на любое число и векторно складывается с любой др. строкой табл.2 метод (правило четырехугольника): 1) направляющая строка делится на разрешающий эл-т табл., 2) направляющий столбец записывается как единичный, 3) Те строкии столбцы, кот. имеют в направляющей строке/столбце «0» переносятся без изменений, остальные числа табл. пересчитываются так: эл-т новойсимпл. табл.= эл-ту, стоящему на этом же месте в старой табл. минус произведение эл-тов, стоящих на диагонале противоположной к разрешающему эл-ту, деленное на разрешающий эл-т табл.