Определение вводимой в базис переменной

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

В методе потенциалов строке i и столбцу j транспортной таблицы (таблица 2) ставятся в соответствие некоторые числа, называемые потенциалами u_i и vj. Для каждой базисной переменной Х_ij текущего решения сумма потенциалов должна быть равна соответствующему коэффициенту целевой функции:

 

(4)

 

Уравнения (4), число которых соответствует числу базисных переменных (m + n — 1), составляют систему, в которой (m + n) неизвестных. Значения потенциалов u_i и vj определяются из этой системы, если придать одному из неизвестных (удобно наиболее часто встречающемуся) произвольное значение, например равное нулю. После этого для каждой небазисной X_pq переменной определяются оценки (критерии) оптимальности:

(5)

 

В базис включается та переменная X_pq, которая имеет наибольшую положительную оценку оптимальности. Если среди оценок d_pq нет положительных, то данный опорный план — оптимальный.

Уравнения, связанные с базисными переменными, имеют вид:

Пусть u₁= 0. Тогда значения потенциалов: v₁= 3, u₂=1, v₂=5, u₃= 3,v₃=12, v₄= 6.

Оценки d_qp для небазисных переменных:

Наибольшую положительную оценку имеет , которую следует включить в базис.

Простая структура уравнений позволяет, не записывая систему уравнений, находить потенциалы непосредственно по транспортной таблице. Вначале в левых верхних углах ячеек, соответствующих каждой базисной переменной х_ij на текущей итерации, проставляются символы 0. Выбирается любая величина — u_iили vj. Ей присваивается произвольное значение, проставляемое у строки или столбца, которым принадлежит выбранное u_iили vj. Строка или столбец анализируется с целью выявления базисных переменных данной итерации. Если выбрана строка i и базисные переменные в ней х_il, x_ir и x_is, то уравнение (4) позволяет найти значения потенциалов соответствующие столбцам, на пересечении которых с i-й строкой находятся базисные переменные. Полученные значения v_i используются по аналогии для вычисления оставшихся потенциалов.

После этого можно вычислить по (5) оценки оптимальности d_pq для всех небазисных переменных x_pq и проставить их в соответствующих левых углах ячеек таблицы 5.

 

Таблица 5 – Потенциалы u_i и v_j и оценки оптимальности первой операции, полученной по упрощенной схеме

 

Заводы	Объекты строительства	ui	Объем производства, м3/ч
1	Ø 3	3 2	2 10	-1 7	-3
	Ø 4	Ø 6	13 0	5 2	-2
	­ 1 5	Ø 8	Ø 15	Ø 9
vj					-----
Спрос

 

Требуется найти значения потенциалов u_i и v_j, первой итерации решения задачи, пользуясь упрощенной схемой. Согласно таблице 4, выбирается u₃ = 0. Справа от 3-й строки можно проставить значение u₃. Строка (столбец), соответствующая u₃, просматривается для выявления базисных переменных. В строке 3 базису принадлежат x₃₂, x₃₃, x₃₄. С помощью уравнения (4) находятся значения потенциалов: v₂ = p₃₂ –u₃ = 8, v₃ ⁼ p₃₃ – u₃ = = 15-0 =15, v₄= p₃₄-u₃ = 9-0 = 9. Вычисление остальных потенциалов проводится по вышеизложенной схеме (u₂=-2, u₁=-3, v₁ = 6) и заносится в таблицу 5. Теперь можно вычислить оценки d_pq для небазисных x_pq и занести их в соответствующие ячейки. Как видно из таблицы 5, значения потенциалов u_i и v_j, а также оценки d_pq отличаются от значений, полученных при непосредственном решении системы уравнений (4), (5). Это вызвано выбором в качестве свободного потенциала переменной u₂ вместо u_1. Однако по критерию оптимальности наибольшее положительное значение d_pq по-прежнему имеет небазисная переменная х₂₃ которая и включается в базис.