Симплекс-метод задачи линейного программирования

Определения

Линейное программирование – раздел математики, занимающийся поиском экстремумов на множестве пространства, заданном системой линейных уравнений и неравенств.

Целевая функция – функция нескольких переменных, подлежащая оптимизации в целях решения какой-либо оптимизационной задачи.

Алгоритм симплекс-метода

В начале исходную задачу линейного программирования приводят к каноническому виду, затем составляют симплекс-таблицу вида

Базис	B	x1	...	xk	...	xj	...	xn
...	...			...
xi	bi		...	aik	...	aij	...
...	...			...
xr	br		...	ark	...	arj	...
...	bm			...
f(x)	0		...	–ck = –Δk	...	–cj = –Δj	...

где в столбце «Базис» указываются базисные переменные (в последней строке – f(x)). В столбец B записываются свободные члены ограничений b_i и значение целевой функции (на первом этапе оно равно 0). В столбцах x_j для небазисных переменных указываются коэффициенты при небазисных переменных из ограничений задачи. В столбцах базисных переменных содержится только 0 или 1 на пересечении столбца с соответствующей строкой базисной переменной. c_j – коэффициенты при переменных целевой функции (взяты с противоположным знаком).

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

1. Выполняется проверка полученного базисного плана на оптимальность по условию: если при каком-либо допустимом базисном решении в симплекс-таблице все –c_j неотрицательны, то данное решение оптимально (конец алгоритма). Иначе:

2. Переход к новому базисному плану. Для этого из числа небазисных переменных с –c_j < 0 выбирается вводимая в базис переменная x_k (ей соответствует наибольшая по модулю отрицательная оценка, т.е. |Δ_k| = max |Δ_j|, где Δ_j < 0). Столбец, отвечающий переменной x_k, является ведущим (его элементы обозначаются через a_ik).

3. Выбирается выводимая (исключаемая) из базиса переменная r, которая находится из соотношения (b_r / a_rk) = min по j (b_i / a_ik), где a_ik > 0. Строка таблицы, в которой получено наименьшее отношение элемента столбца В к соответствующему положительному элементу ведущего столбца, является ведущей (её элементы обозначаются через a_rj). a_rk – ведущий элемент (стоит на пересечении ведущего столбца и ведущей строки).

4. Для определения нового базисного плана элементы симплекс-таблицы пересчитываются, результаты заносятся в новую таблицу. Выбранные переменные среди базисных и небазисных, лежащих на главной строке и главном столбце, меняются местами. Пересчёт элементов выполняется следующим образом:

   • элементы главной строки делятся на ведущий элемент: b_k = b_r / a_rk, a_kj = a_rj / a_rk.
   • элементы полученной строки умножаются на –a_ik и складываются с i-ой строкой (i ≠ k): a'_ij = a_ij – (a_rj ⋅ a_ik / a_rk); b'_i = b_i – (b_r ⋅ a_ik / a_rk); f '(x) = f(x) – (b_r ⋅ Δ_k / a_rk); Δ'_j = Δ_j – (a_rj ⋅ Δ_k / a_rk).

   Для новой симплекс-таблицы выполняется та же последовательность шагов.

Особенности реализации

Входные данные: файл формата '.txt' с симплекс-таблицей без базисных переменных в столбцах (элементы строк должны быть разделены табом '\t'). Предполагется, что во входной симплекс-таблице сформулирована задача по минимизации целевой функции.