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

Коэффициенты при свободных переменных				Значения базисных переменных
x(1)1	x(1)2	… … … …	x(1)n
а11	а 12	… … … …	а1n	b1 → у(1)1
а21	а22	… … … …	а2n	b2→ у(1)2
… … … …	… … … …	… … … …	… … … …	… … … …
аm1	аm2	… … … …	аmn	bm→ у(1)m
c1	c2	… … … …	cn	0 (значение фнкции цели)

6.2. Определяем центр нового базового решения. Для этого выполняем следующее:

а) выбираем любой столбец значений коэффициентов при свободных неизвестных, в последней строке которого число c₁, c₂, …, c_n положительно и не равно нулю; (например, столбец 2 в симплекс – таблице, при c₂ > 0 и c₂ ≠ 0)

б) в выбранном столбце (например, столбец 2) находим строки, в которых коэффициенты при свободных переменных а₁₂, а₂₂,…, а_m2 положительны и не равно нулю; (например, во всех строках столбца 2 выполняются условия а₁₂ > 0, а₂₂ > 0, …, а_m2 > 0 и а₁₂ ≠ 0, а₂₂ ≠ 0, …, а_m2 ≠ 0;

в) в найденных строках выбираем значение того коэффициенты при свободных переменных а₁₂, а₂₂,…, а_m2, для которого частное при делении соответствующего (в той же строке, что и коэффициент при свободных переменных) значения базисного переменного b₁, b₂,…, b_m положительное и минимальное: b₁ / а₁₂ = d₁, b₂ / а₂₂ =d₂ …, b_m / а_m2 =d_m ; при этом положительное и минимальное частное, например, d₁, то есть d₁ > 0 и d₁ < d₂ <, …, d_m;

Таким образом, центром нового базового решения является, например, значение коэффициента а₁₂, расположенного во втором столбце (см. п. а) и первой строке (см. п.п. б и в). В симплекс – таблице этот коэффициент выделен жирным шрифтом и обведен рамочкой.

6.3. Определяем свободные переменные второго опорного решения. Свободными переменными будут являться все переменные, расположенные справа и слева от центра в строке, в которой расположен центр. Например, в симплекс – таблице центром является а₁₂, поэтому свободными неизвестными будут

x⁽²⁾₁=0, x⁽²⁾₃ =0,…, x⁽²⁾_n =0, у⁽²⁾₁ =0 (71)

6.4. Определяем базисные переменные второго опорного решения. Базисными переменными будут являться все остальные переменные

x⁽²⁾₂ ≠ 0, у⁽²⁾₂ ≠ 0, у⁽²⁾₃ ≠ 0,…, у⁽²⁾_m≠ 0 (72)

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

Коэффициенты при свободных переменных				Значения базисных переменных
x(1)1	x(1)2	… … … …	x(1)n
а11	а 12	… … … …	а1n	b1 → у(1)1
а21	а22	… … … …	а2n	b2→ у(1)2
… … … …	… … … …	… … … …	… … … …	… … … …
аm1	аm2	… … … …	аmn	bm→ у(1)m
c1	c2	… … … …	cn	0 (значение фнкции цели)

6.5. Выражаем базисные переменные через свободные переменные из канонических уравнений (64)

x⁽²⁾₂ = (1/ а₁₂)*( b₁ - а₁₁х⁽²⁾₁ - а₁₃х⁽²⁾₃ - …- а_1nх⁽²⁾_n - у⁽²⁾₁) (73)

Остальные базисные переменные у⁽²⁾₂ , у⁽²⁾₃,…, у⁽²⁾_m выражаем из последующих уравнений системы (64) с подстановкой значения переменного x⁽²⁾₂ из выражения (73):

у⁽²⁾₂ = b₂ – (b₁ /a₁₂)+ [(а₁₁ /а₁₂)-а₂₁] x⁽²⁾₁ +[(а₁₃ /а₁₂) - а₂₃] x⁽²⁾₃ +…+ [(а_1n /а₁₂) –

- а_2n] x⁽²⁾₁+ (1/ а₁₂) у⁽²⁾₁

... … … … … … … … … … … … … … … … … … … … … … … … … …

у⁽²⁾_m = b_m – (b₁ /a₁₂)+ [(a ₁₁ /а₁₂)-а_m1] x⁽²⁾₁ +[(а ₁₃ /а₁₂) - а_m3] x⁽²⁾₃ +…+ [(а_1n /а₁₂)-

- а_mn] x⁽²⁾_n + (1/ а₁₂) у⁽²⁾₁ (74)

6.6. Определяем значения базисных переменных, подставляя в выражения (73), (74) нулевые значения свободных переменных

x⁽²⁾₂ = (1/ а₁₂)* b₁

у⁽²⁾₂ = b₂ – (b₁ /a₁₂)

………………………..

у⁽²⁾_m = b_m – (b₁ /a₁₂) (75)

6.7. Записываем новую систему канонических уравнений, используя выражения (73) – (75)

r₁₁х⁽¹⁾₁ + r₁₂х⁽¹⁾₂ + … + r_1nх⁽¹⁾_n + p₁ у⁽¹⁾₁ = t₁,

r₂₁х⁽¹⁾₁ + r₂₂х⁽¹⁾₂ + … + r_2nх⁽¹⁾_n + p₂ у⁽¹⁾₂ = t₂,

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

r_m1х⁽¹⁾₁ + r_m2х⁽¹⁾₂ + … + r_mnх⁽¹⁾_n + p_m у⁽¹⁾_m = t_m, (76)

6.8. Записываем уравнение функции цели, учитывая выражение (73)

- F⁽²⁾ (x⁽²⁾₁, x⁽²⁾₂,…, x⁽²⁾_n) = -[c₁ * x⁽²⁾₁ + c₂ * x⁽²⁾₂ +…+ c_n * x⁽²⁾_n] =

= - {[c₁ –( а₁₁ /а₁₂)c₂] x⁽²⁾₁ - [c₃ –( а₁₃ /а₁₂) c₂] x⁽²⁾₃ - … -[c_n –( а_1n /а₁₂) c₂] x⁽²⁾_n –

- + (1/ а₁₂) c₂ у⁽²⁾₁ + (b₁ /a₁₂) c₂} (77)

6.9. Определяем значение целевой функции, подставляя нулевые значения свободных неизвестных в выражение (77)

- F⁽²⁾ (x⁽²⁾₁, x⁽²⁾₂,…, x⁽²⁾_n) = - (b₁ /a₁₂) c₂ < - F⁽¹⁾ (x⁽¹⁾₁, x⁽¹⁾₂,…, x⁽¹⁾_n)= 0 (78)

7. Проводим исследование полученного выражения функции цели (77) – уменьшится ли (увеличится ли по абсолютной величине) значение функции, если переменные параметры x⁽²⁾₁, x⁽²⁾₃,…, x⁽²⁾_n, у⁽²⁾₁ будут иметь любое другое положительное значение, отличное от полученных в данном опорном решении (71), (75).