Алгоритм решения системы (3.21)–(3.22) симплекс-методом

Шаг 1.Получение начального решения.

Выбираются т переменных, называемых базисными и обладающих следующим свойством: они входят с коэффициентом 1 только в одно уравнение и с коэффициентом 0 в остальные уравнения системы (3.22).

Остальные п – т переменных называют свободными.

Все свободные переменные полагаются равными 0, а базисные переменные — равные правым частям соответствующих ограничений системы (3.22).

Пусть т базисных переменных — это переменные x₁, x₂,..., x_m (в противном случае переменные всегда можно перенумеровать).Тогда начальное решение Х ₀имеет следующий вид:

Х _о={ x₁= b₁, х₂=b₂,..., х_т = b_m, x_m+l = 0 ,..., х_n = 0}.

Если все b_i 0, то начальное решение является допустимым. Переходят к шагу 3. В противном случае используют алгоритм нахождения начального решения.

Шаг 3.Выражение функции f только через свободные переменные.

Значения коэффициентов c_j, , естественно, отличны от значений коэффициентов в формуле (3.21), но для простоты обозначены той же буквой.)

Переход к шагу 3.

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

Составляется симплекс-таблица (табл. 3.3). В левой колонке симплекс-таблицы находятся базисные переменные, в колонке свободных членов – правые части соответствующих ограничений. В i -й строке,
j-м столбце стоит коэффициент при j- й переменной в i -м ограничении (3.22), , . В последней строке (f – строке) стоит коэффициент с противоположным знаком при j -ой переменной в целевой функции f.
В последнем столбце стоят значения свободных членов, входящего в ограничения.

Таблица 3.3

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

Шаг 5.Получение нового решения.

Шаг 5.1.Выбор переменной, вводимой в список базисных переменных.

Просматривается последняя строка симплекс-таблицы. Среди элементов этой строки выбирается максимальный по абсолютной величине отрицательный элемент. Столбец, в котором стоит этот элемент, называется разрешающим. Пусть, например, это p -й столбец. Переменная х_р, стоящая в этом столбце, вводится в список базисных переменных.

Шаг 5.2.Выбор переменной, выводимой из списка базисных переменных.

Находят отношение элементов столбца свободных членов к элементам разрешающего столбца. При делении на отрицательный элемент и 0 результат полагают равным . Среди этих отношений находят минимальное. Строка, соответствующая минимальному отношению, называется разрешающей. Пусть, например, это q-я строка. Базисная переменная x_q, стоящая в этой строке, выводится из списка базисных переменных. Элемент симплекс – таблицы a_qp, стоящий на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом.

Шаг 5.3.Выполнение симплекс – преобразования и переход к новой симплекс-таблице.

Элемент a_ij новой симплекс-таблицы вычисляется с помощью следующего симплекс – преобразования:

(3.23)

(3.24)

Таким образом, при переходе к новой симплекс-таблице все элементы разрешающей строки делятся на разрешающий элемент (3.23), а все остальные элементы симплекс – таблицы, включая коэффициенты
целевой функции и свободные члены, пересчитываются по формуле (3.24).

Новое решение имеет следующий вид: все свободные переменные в нем полагаются равными 0, а все базисные переменные – свободным членам, стоящим в одной строке с ними.

После построения новой симплекс-таблицы следует перейти к шагу 3

Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи (32) – (34) задается на максимум, а целевая функция двойственной (35) – (37) – на минимум.

2. Матрица

(38)

составленная из коэффициентов при неизвестных в системе ограничений (33) исходной задачи (32) – (34), и аналогичная матрица

(39)

в двойственной задаче (35) – (37) получаются друг из друга транспонированием (т. е. заменой строк столбцами, а столбцов – строками).

3. Число переменных в двойственной задаче (35) – (37) равно числу ограничений в системе (33) исходной задачи (32) – (34), а число ограничений в системе (36) двойственной задачи – числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (35) двойственной задачи (35) – (37) являются свободные члены в системе (33) исходной задачи (32) – (34), а правыми частями в соотношениях системы (36) двойственной задачи – коэффициенты при неизвестных в целевой функции (32) исходной задачи.

5. Если переменная x_j исходной задачи (32) – (34) может принимать только лишь положительные значения, то j –е условие в системе (36) двойственной задачи (35) – (37) является неравенством вида “? ”. Если же переменная x_j может принимать как положительные, так и отрицательные значения, то 1 – соотношение в системе (54) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (33) исходной задачи (32) – (34) и переменными двойственной задачи (35) – (37). Если i – соотношение в системе (33) исходной задачи является неравенством, то i –я переменная двойственной задачи . В противном случае переменная у_j может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (33) прямой задачи и соотношения (36) двойственной задачи являются неравенствами вида “ ”. Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.