Переходим к первому этапу решения задачи – отыскание опорного решения задачи.

1. Для удобства выполнения дальнейших вычислений в функции цели изменим знак на обратный следующим образом:

- F(x₁, x₂,…, x_n) = -[c₁x₁ + c₂x₂ +…+ c_nx_n] (67)

В этом случае будем искать не максимум, а минимум функции цели.

2. Назначаем первое опорное решение. Обычно первое опорное решение назначается из условия, что переменные параметры равны нулю, то есть

х⁽¹⁾₁ = 0, х⁽¹⁾₂ = 0, …, х⁽¹⁾_n = 0 (68)

Переменные параметры, равные нулю, называются свободными.

3. Определяем значения дополнительных переменных у ⁽¹⁾ ₁, у ⁽¹⁾ ₂ ,…, у ⁽¹⁾ _m, подставляя в канонические уравнения (64) значения свободных переменных (68). Получаем:

у ⁽¹⁾ ₁ = b₁, у ⁽¹⁾ ₂ = b₂,,…, у ⁽¹⁾ _m = b_m, (69)

Эти переменные положительны, что соответствует условию задачи (66).

Переменные параметры, неравные нулю, называются базисными.

4. Определяем значение функции цели, подставляя значение переменных параметров (68) в уравнение (67)

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

= -[c₁ *0 + c₂ *0 +…+ c_n *0] = 0 (70)

5. Проводим исследование полученного выражения функции цели (70) уменьшится ли (увеличится ли по абсолютной величине) значение функции, если переменные параметры x⁽¹⁾₁, x⁽¹⁾₂,…, x⁽¹⁾_n будут иметь любое другое положительное значение, отличное от полученных в данном опорном решении (68).

Если значение функции цели уменьшается, то переходим к новому опорному решению, если - нет, то переходим ко второму этапу решения задачи.

6. Переходим ко второму опорному решению, предполагая, что значение функции цели уменьшается при изменении значений переменных параметров.

6.1. Составляем симплекс – таблицу.

В симплекс – таблицу вводятся коэффициенты при свободных переменных из канонических уравнений (64) и значения базисных переменных (69) предыдущего опорного решения. В нижней строке вводятся коэффициенты при неизвестных из уравнения функции цели (62).

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

Коэффициенты при свободных переменных	Значения базисных переменных
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)

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).

Если значение функции цели уменьшается, то переходим к новому опорному решению (см. п.6), если - нет, то переходим ко второму этапу решения задачи.

Переходим ко второму этапу решения задачи – отыскание опорного решения задачи, считая, что функция цели не уменьшается, а увеличивается, например, при новых значения переменных параметров x^(k+1)₁, x^(k+1)₂,…, x^(k+1)_n.

В этом случае оптимальным решением будет последнее опорное решение, например, k - тое.

- F^(k) (x^(k)₁, x^(k)₂,…, x^(k)_n) < - F^(k-1) (x^(k-1)₁, x^(k-1)₂,…, x^(k-1)_n) → min (79)