Правила заполнения первой симплекс-таблицы

В первую строку с_j вносятся значения коэффициентов при переменных из целевой функции. В столбец базисных переменных вносим дополнительные переменные х_j.

В столбец с_i вносят значения коэффициентов при переменных из целевой функции, которые вошли в базис.

Рабочее поле таблицы (столбцы под переменными х_j заполняют коэффициентами при соответствующих переменных из системы равенств канонической формы записи ПЗЛП. Отсутствие той или иной переменной в равенстве означает, что ей соответствует коэффициент, равный нулю.

В столбец b_i вносят свободные члены системы равенств.

Индексная строка (_j) для переменных находится по формуле:

,

где h_ij – соответствующий элемент, стоящий на пересечении i-й строки и j-го столбца рабочего поля симплекс таблицы.

Индексная строка (_j) для свободного члена находится по формуле

, где l_i – соответствующий элемент, из столбца b_i.

Рабочее поле таблицы (столбцы под переменными х₁, х₂,…. х₈) заполняем коэффициентами при соответствующих переменных из системы равенств канонической формы записи ПЗЛП.

Поскольку, в первом равенстве отсутствуют переменные х₆ –х₈, поэтому в первой рабочей строке симплекс-таблицы этим переменным

соответствует коэффициент «0».

сi	сj	3	4	1	3	2	0	0	0
	Базисные переменные (БП)	х1	х2	х3	х4	х5	х6	х7	х8	bi
0	х6	1	3	2	3	6	1	0	0	3
0	х7	2	3	1	6	0	0	1	0	5
0	х8	3	1	2	6	4	0	0	1	4
j		-3	-4	- 1	- 3	-2	0	0	0	0

Заполняем индексную строку:

₁ = 01 + 02 + 03 – 3 = -3; ₂ = 03 + 02 + 03 – 4 = - 4;

₃ = 02 + 01 + 02 – 1 = -1 ₄ = 03 + 06+ 06 – 3= - 3; ₅ = -2; ₆ = 0;

₇ = 0; ₈ = 0 .

Первое опорное решение имеет вид: = (0, 0, 0, 0, 0, 3, 5, 4), = 0. Следует проверить первое опорное решение на оптимальность.

Проверка первого опорного решения на оптимальность

Возможны следующие случаи решения задачи на максимум:

- если все оценки _j  0, то найденное решение оптимальное;

- если хотя бы одна оценка _j  0, но при соответствующей переменной нет ни одного положительного коэффициента, решение задачи прекращают, так как f(X)  , т.е. целевая функция не ограничена в области допустимых решений;

- если хотя бы одна оценка отрицательная, а при соответствующей переменной есть хотя бы один положительный коэффициент, то нужно перейти к другому опорному решению;

- если отрицательных оценок в индексной строке несколько, то в столбец базисной переменной (БП) вводят ту переменную, которой соответствует наибольшая по абсолютной величине отрицательная оценка.

В рассматриваемом случае первое опорное решение не оптимальное, поскольку имеются пять отрицательных оценок ₁ = - 3, ₂ = - 4, ₃ = - 1,₄ = - 3, ₅ = - 2. Следовательно, необходимо перевести в базис переменную, которую нужно улучшить.