§ 5. Метод последовательного улучшения плана (симплексный метод)

Метод последовательного улучшения плана (далее для краткости мы будем называть этот метод общепринятым названием симплексный метод) позволяет найти решение любой задачи линейного программирования, проделав ограниченное число шагов, каждый из которых является алгебраическим преобразованием, производимым и установленным правилам.

1. Основная идея симплексного метода. Прежде всего для начала вычислений требуется, чтобы система уравнений (1.1) была приведена к такому виду, в котором какие-либо m неизвестных выражены через остальные n-m. Будем считать, что ранг матрицы А равен m (n>m). Предположим также, что свободные члены b_i неотрицательны. В противном случае можно умножить правую и левую части уравнения, у которого свободный член отрицателен, на -1. Далее допустим, что неизвестные, которые выражены через остальные, есть x₁, ..., x_m. Таким образом, система (1.1) может быть записана в виде

(1.7)

где b₁≥0, ..., b_m≥0 и коэффициенты α_1,m+1, ..., α_mn выражаются через a₁₁, ..., a_mn. Неизвестные x₁, ..., x_m, которые находятся в левой части системы (1.7), образуют некоторый базис, поэтому эти неизвестные называются базисными. Остальные неизвестные являются небазисными (или свободными).

Будем считать для определенности, что требуется найти такое решение системы (1.1), которое обращает целевую функцию f = c₁x₁ + ... + c_nx_n в минимум.

Подставляя в функцию f вместо базисных неизвестных их выражения через небазисные, записанные в виде (1.7), представим функцию f с помощью свободных неизвестных x_m+1, ..., x_n в виде

(1.8)

где все λ - постоянные коэффициенты.

Поскольку неизвестные x_m+1, ..., x_n свободные, то их можно положить равными 0. Тогда из системы (1.7) находим значения базисных неизвестных:

Решение системы (1.7) (b₁, ..., b_m, 0, ..., 0) будет являться базисным решением, для которого значение функции f₀ = λ₀. Очевидно, здесь возможны два случая:

1. Все числа λ_m+1, ..., λ_n неположительны, Тогда минимум функции f достигается при x_m+1 = ... = x_n = 0, т. е. полученное базисное решение является оптимальным, и задача решена.
2. Среди чисел λ_m+1, ..., λ_n имеются положительные, например, λ_j>0, (m+1<j<n). В этом случае можно попробовать, не изменяя нулевых значений всех небазисных неизвестных, кроме x_j, уменьшить функцию f за счет увеличения x_j. При этом необходимо следить, чтобы ни одно из значений базисных переменных x₁, ..., x_m не было отрицательным.

Полагая в (1.7) и (1.8) все свободные переменные, кроме x_j, равными 0, получаем

Если все числа α_1j, ..., α_mj неположительные, то очевидно, что при всех x_j≥0, x₁, ..., x_m также положительные числа и при x_j→∞, f→-∞, т. е. минимум функции f не достигается.

Если среди чисел α_1j, ..., α_mj есть положительные, то x_j нельзя увеличивать беспредельно. Пусть α_kj = 0, где k = 1, 2, ..., m. Очевидно, что число x_k = b_k - α_kjx_j станет отрицательным, когда будет дано значение x_j>^b_k/_αkj. Поскольку x_j входит во все числа x₁,..., x_m, среди этих чисел найдется по крайней мере одно x_i, которое при увеличении x_j станет отрицательным ранее других. Для того чтобы определить x_i, найдем среди всех отношений ^b_k/_αkj наименьшее, которое обозначим ^b_i/_αij (α_ij>0).

Таким образом, ^b_i/_αij = min ^b_k/_αkj, где берутся все k, для которых a_kj>0. Обозначим это минимальное значение через δ. Очевидно, что δ>0. Если минимум достигается сразу при нескольких k, то за i можно брать любое из этих значений k.

Теперь x_j можно увеличивать до величины δ, не опасаясь, что какое-нибудь x_i станет отрицательным.

Положим

(1.9)

и найдем значения остальных неизвестных

(1.10)

и целевой функции

Итак, в результате проведенных преобразований получен новый базис x₁, ..., x_i-1x_j, x_i+1, ..., x_n, в котором неизвестное x_i заменено на x_j (x_j = δ), и при этом функция f уменьшилась, т. е. мы приблизились к искомому минимуму целевой функции.

Чтобы завершить первый шаг преобразований, остается только записать систему (1.7) и функцию (1.8) через новый базис. Для этого из уравнения для x_i (старого базисного неизвестного) в системе (1.7) находим x_j (новое базисное неизвестное):

и подставляем это выражение вместо x_j в остальные уравнения. В результате система оказывается разрешенной относительно нового базиса:

(1.12)

Правила для определения коэффициентов α'_kl системы (1.12) через коэффициенты системы (1.7) будут даны позднее. Здесь выпишем только выражения для свободных членов системы (1.12):

Все b'₁, ..., b'_m - числа неотрицательные, что следует из определения величины δ.

Целевую функцию также выразим через новые базисные переменные:

(1.13)

На этом заканчивается процесс вычислений первого шага.

Если искомое оптимальное решение не найдено, т. е. если среди коэффициентов λ'_m+1, ..., λ'_n имеются положительные, то процесс вычислений необходимо продолжить, производя аналогично вышеизложенному новую замену базиса. Второй шаг заканчивается новым выражением для функции f, из которого становится ясно, получено ли решение задачи или следует переходить к третьему шагу.

Приведенное выше описание основной идеи симплексного метода было дано конкретно для случая нахождения минимума целевой функции f. Небольшое изменение характера действий позволяет обобщить это описание также на случай отыскания максимума f. Для этого необходимо попытаться увеличить f₀, если среди чисел λ_m+1, ..., λ_n есть неположительные. Определяя δ точно так же, как для случая минимизации f, из выражения (1.11) получим величину f₁ = λ₀ - λ_jδ>f₀ (так как λ_j<0). Далее приходим к системе (1.12) и выражению (1.13), на которых заканчиваются вычисления первого шага.

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

и целевая функция

Требуется найти такое решение системы, которое обращает в максимум функцию f.

Запишем эту систему и функцию f в виде

Здесь неизвестные x₁ и x₂ образуют базис. Соответствующее базисное решение есть (1, 2, 0). Для этого решения значение функции f = 5. Поскольку x₃ входит в f с положительным коэффициентом, можно попытаться увеличить f, увеличивая x₃.

Из первого уравнения системы следует, что максимальное значение x₃ = 1 (при x₃>1 становится отрицательным x₁).

Переходим к новому базису (x₂, x₃):

Увеличить f больше нельзя, так как x₁ входит в f с отрицательным коэффициентом. Решение x₁ = 0, x₂ = 3, x₃ = 1 является оптимальным базисным решением. Функция цели достигает максимума: f = 9.

Ввиду простоты задачи можно убедиться в этом непосредственными вычислениями.

Итак, мы описали основную идею симплексного метода. Однако проведение преобразований в общем случае все же требует выполнения довольно громоздких вычислений. Ниже будут даны общие правила и методы, позволяющие до некоторой степени упростить и формализовать расчеты, а также будут указаны возможные затруднения, которые могут при этом встретиться.

2. Выделение первого базиса. Предыдущий раздел начинался с предположения о том, что система уравнений (1.1) приведена к виду (1.7), в котором какие-либо m неизвестных (например, 1, 2, ..., m неизвестные) выражены через остальные (n - m) неизвестных. При этом предполагалось, что все свободные члены b_i неотрицательны.

Предположение о возможности приведения системы (1.1) к системе (1.7) равносильно предположению о том, что из системы (1.1) можно непосредственно выделить базисное решение. В некоторых случаях это действительно легко сделать. Например, очень просто выделяется первый базис в том случае, если в каждое из m линейно-независимых уравнений одно из неизвестных x₁, x₂, ..., x_n входит с коэффициентом +1, причем в остальных (m-1) уравнениях оно не встречается (как это имело место в примере, приведенном в предыдущем разделе). В том случае, если коэффициенты при этих неизвестных отличны от +1, очевидно, можно всегда сделать их равными +1, разделив левую и правую части уравнений на эти коэффициенты.

Первое базисное решение легко также получить для тех задач, в которых ограничения заданы в виде системы линейных неравенств вида

Для этого нужно превратить эту систему неравенств в систему уравнений таким образом, как было описано в § 1 этой главы. Добавив к левой части этих неравенств неотрицательные переменные x_n+1, x_n+2, ..., x_n+m, мы получаем возможность сразу выделить базис.

Итак, в некоторых частных случаях процедура выделения первого базиса, т. е. возможность проведения преобразования системы (1.1) к системе (1.7), представляется весьма простой. Однако в большинстве случаев не всегда удается сразу найти путь для такого преобразования. Рассмотрим один из методов выделения первого базиса, называемый обычно "методом искусственного базиса".

Пусть система ограничений задана в виде (1.1), где все b_i>0. Введем вспомогательные или так называемые искусственные неизвестные y₁, y₂, ..., y_m, связанные с x₁, x₂, ..., x_n уравнениями

(1.14)

Очевидно, система (1.14) имеет то же самое решение, что и система (1.1), при условии y₁ = 0, y₂ = 0, ..., y_m = 0. В системе (1.14) искусственные переменные y₁, ..., y_m образуют базис. Используя этот базис, можно перейти к другому базису, не содержащему ни одной искусственной неизвестной, например к x₁, ..., x_m.

Допустим, что после некоторых преобразований система (1.14) приведена к виду

(1.15)

где β₁≥0, ..., β_m≥0. В системе (1.15) мы имеем право положить y₁ = 0, ..., y_m = 0; тогда эта система становится эквивалентной системе (1.7). В системе (1.15) неизвестные x₁, ..., x_m образуют базис, т. е. тем самым задача выделения первого базиса решена.

Оказывается, что для перехода от системы (1.14) к системе (1.15) можно применить симплексный метод. Действительно, будем при помощи этого метода решать задачу о минимизации функции

при ограничениях, заданных системой (1.14) и при условиях

Система (1.14) записана в таком виде (выделен базис y₁, ..., y_m), что к ней может быть непосредственно применен симплексный метод. После некоторого числа шагов искомый минимум, очевидно, будет получен, причем так как F≥0, то и min F≥0.

Однако, если min F≥0, система (1.15) не может иметь неотрицательных решений, для которых все y₁ = 0, ..., y_m = 0. Следовательно, и исходная система (1.14) также не может иметь неотрицательных решений, т. е. эта система не удовлетворяет условиям, которым должна удовлетворять система ограничений задачи линейного программирования, и эта задача в данном случае не имеет решения (система (1.14) несовместна).

Если min F = 0, то вследствие неотрицательности y₁, y₂, ..., y_m должны быть равны 0 все искусственные неизвестные y₁, ..., y_m, входящие в базисное решение x₁, ..., x_m, y₁, ..., y_m, которое минимизирует функцию F. Это означает, что в случае min F = 0 данная система ограничений (1.14) совместна. Далее необходимо убедиться, что искусственные неизвестные не входят в базис. В противном случае следует проделать дальнейшие преобразования (описанные в предыдущем разделе), чтобы вывести их из базиса.

Таким образом, мы показали, как выделить первый базис для любой совместной системы ограничений, используемых в задачах линейного программирования. Укажем теперь некоторые формальные правила, облегчающие вычисления по алгоритму симплексного метода.

3. Алгоритм симплексного метода и симплексные таблицы. В настоящем разделе достаточно подробно излагается общий алгоритм симплексного метода, т. е. указывается совокупность математических операций, которые, будучи выполнены в определенной последовательности, обеспечивают получение решения задач данного класса.

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

Для простоты предположим, что нам известно первое базисное решение, т. е. систему уравнений задачи можно записать в виде

(1.7')

где все b_i≥0.

Учитывая все сказанное в предыдущем разделе, можно считать, что это предположение нисколько не снижает общности изложения. Функцию цели будем пока записывать как в виде f₁ = c₁x₁ + c₂x₂ + ... + c_nx_n, так и в виде

где f₁ - значение функции f, соответствующее первой симплексной таблице.

Составим первую симплексную таблицу.

В эту таблицу записываются в определенном порядке все величины, которые требуются в процессе решения задачи.

Метод составления таблиц представляется вполне очевидным, а ее форма является достаточно общепринятой. Последнюю строку этой таблицы принято называть "индексной" строкой.

Таблица 1

В том случае, если все элементы индексной строки (кроме λ₀) табл. 1 при решении задач на минимум отрицательны (или при решении задач на максимум - положительны), то полученное решение является оптимальным. Этим решением будет x₁ = b₁, x₂ = b₂, ..., x_m = b_m, x_m+1 = 0, ..., x_n = 0. Значение функции цели при этом, очевидно, равно f₁ = c₁b₁ + c₂b₂ + ... + c_mb_m.

Если же среди элементов индексной строки есть положительные при решении задачи на минимум (отрицательные при решении задачи на максимум), то полученное решение не является оптимальным. В этом случае выбираем соответствующий наибольший по абсолютной величине элемент индексной строки. Выбранный элемент определяет ведущий столбец таблицы (например, столбец с номером s).

Далее составляем отношения свободных членов (третий столбец) к положительным элементам s-го столбца и выбираем из них наименьшее, как это было описано выше. Пусть этим наименьшим отношением будет ^b_r/_ars, т. е. ^b_r/_ars = min (^b_k/_aks) (все a_ks>0). Тогда r-я строка называется ведущей строкой. На пересечении r-й строки и s-го столбца находится элемент a_rs, который называется разрешающим элементом.

Следующим этапом является переход к новому базису, в котором неизвестное x_r из базисных переводится в небазисные, а неизвестное x_s делается базисным. Этот переход означает переход ко второй симплексной таблице. Получим формулы, с помощью которых следует вычислять элементы новой таблицы.

Переход к новой таблице эквивалентен переходу от системы (1.7) к системе (1.12), который осуществляется с помощью следующих тождественных преобразований, а именно r-е уравнение системы (1.7) следует разрешить относительно переменной x_s:

Это выражение для x_s подставляем во все остальные уравнения и функцию f. Например, подстановка значения x_s в k-е уравнение (k≠s) системы (1.7') приводит к уравнению

аналогично подстановка значения x_s в функцию цели f приводит к выражению

Таким образом, из выражения для ха следует, что элементы r-й строки новой таблицы равны соответствующим элементам старой таблицы, разделенным на разрешающий элемент

Элементы s-uj столбца новой таблицы все равны 0, за исключением a'_rs = 1, так как xs стало базисным переменным и больше не входит в правую часть системы уравнений.

Чтобы получить любой другой элемент новой симплексной таблицы, нужно от соответствующего элемента прежней таблицы отнять произведение элемента ведущей строки на элемент ведущего столбца, разделенное на разрешающий элемент, т. е.

Как легко видеть, по этой формуле могут быть также вычислены коэффициенты функции f или все элементы индексной строки новой симплексной таблицы, т. е.

Вторая симплексная таблица (табл. 2) имеет такой же вид, как и симплексная табл. 1.

Таблица 2

Только теперь переменная x_s стала базисной переменной и коэффициенты b_i, a_ij, λ_j заменены на b'_i, a'_ij, λ'_i.

Если сразу все эти элементы оказались отрицательными (при задаче на минимум) или положительными (при задаче на максимум), то оптимальное решение получено, и функция цели принимает значение

где f₂ - значение функции цели, полученное из второй симплексной таблицы.

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

Укажем дополнительно еще одну возможность вычисления элементов индексной строки исходя из представления функции f в виде f = c₁x₁ + c₂x₂ + ... c_nx_n. Для этого преобразуем данное выражение следующим образом:

Объединив свободные члены и коэффициенты при x_m+1, x_m+2, ..., x_n, получим

Таким образом, мы получили явное выражение для I коэффициентов функции цели через коэффициенты a_ij, b_i и c_i:

где f = m + 1, m + 2, ..., n.

Обозначим c₁a_1j + c₂a_2j + ... c_ma_mj через γ_j. Тогда λ_j = γ_j - c_j и элементы индексной строки могут вычисляться по этой формуле после того, как получены все элементы a_ij (i = 1, 2, ..., m). При этих вычислениях используются элементы c₁, c₂, ..., c_n, повторяющиеся в каждой симплексной таблице.

Итак, после конечного числа шагов будет либо получено оптимальное решение, или установлено, что задача не имеет решения. При этом, однако, иногда могут встретиться так называемые случаи вырождения и зацикливания.

Случай вырождения встретится, если свободный член уравнения, содержащего разрешающий элемент, равен нулю. В этом случае после очередного шага значение функции цели не увеличится (или не уменьшится). Поскольку значения базисных неизвестных решения равны свободным членам соответствующих уравнений (небазисные неизвестные мы полагаем равными нулю), то случай вырождения равносилен тому, что одна или несколько базисных неизвестных равны 0. В этом случае (l + 1)-е значение функции цели совпадает с l-й ее значением, т. е. f_l+1 = f_l. Ясно, что это произойдет в том случае, если в последовательности базисов некоторые из них будут повторяться. При этом может случиться, что на каждом из последующих шагов имеет место вырождение, т. е. f_l = f_l+1 = f_l+2 = ... . В этом случае говорят, что в процессе решения задачи произошло зацикливание. Отметим, однако, что при решении конкретных экономических задач случаи зацикливания крайне редки, причем его всегда можно избежать, если изменить последовательность выбора базисов.

Указанная выше последовательность операций определяет алгоритм симплексного метода. Этот алгоритм позволяет решать задачи линейного программирования на ЭВМ.

Проиллюстрируем симплексный метод решения на примере задачи распределения ресурсов. Допустим, предприятие может выпускать два вида изделий, на изготовление которых идет три вида ресурсов, выделяемых этому предприятию в количествах, ограниченных величинами b₁ = 100, b₂ = 120 и b₃ = 150 единиц. На изготовление тысячи штук изделий первого вида расходуется a₁₁ = 10 единиц ресурсов b₁, a₂₁ = 20 единиц ресурсов b₂ и a₃₁ = 20 единиц ресурсов b₃. Соответственно на изготовление тысячи изделий второго вида расходуется a₁₂ = 20 единиц ресурсов b₁, a₂₂ = 10 единиц ресурсов b₂ и a₃₂ = 20 единиц ресурсов b₃. Известно, что оптовые цены изделий первого вида P₁ = 7 тыс. руб. и второго вида P₂ = 13 тыс. руб. (за тысячу штук), а себестоимость тысячи этих изделий соответственно C₁ = 5 тыс. и C₂ = 10 тыс. руб. Требуется составить оптимальный план выпуска изделий этих двух видов, обеспечивающий получение максимальной прибыли предприятия. Предполагается, что эти виды изделий могут производиться в любых соотношениях (сбыт обеспечен). Математически эта задача формулируется следующим образом: найти

при ограничениях

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

при ограничениях

Введем искусственные переменные x₃, x₄, x₅ и перепишем уравнения таким образом, чтобы выделить первое базисное решение и подойти к составлению первой симплексной таблицы:

Составим первую симплексную таблицу (в несколько упрощенном виде).

Таблица 1'

Выбираем столбец, отвечающий x₂ как ведущий, и находим разрешающий элемент, сравнивая отношения ¹⁰⁰/₂₀ = 5, ¹²⁰/₁₀ = 12 и ¹⁵⁰/₂₀ = 7,5. Разрешающим элементом будет a_rs = a₁₂ = 20. Далее по соответствующим формулам вычисляем коэффициенты a'_ij, b'_i и λ'_j, которые записываем во вторую симплексную таблицу.

Таблица 2'

Так как в индексной строке остался отрицательный элемент, то оптимальное решение еще не получено. В столбце, соответствующем x₁, разрешающим элементом является a'₂₁ = 15. Затем вычисляем коэффициенты a"_ij, b"_i, λ"_j переходим к следующей симплексной таблице.

Таблица 3'

Теперь получено оптимальное решение: x₁ = 4,667 и x₂ = 2,667 тыс. шт. При этих значениях x₁ и x₂ функция цели достигает максимума f₃ = f_max = 17,333 (тыс. руб.), в чем нетрудно убедиться непосредственно. При этом 3,333 единицы ресурсов b₃ окажутся неизрасходованными, т. е. предприятие от них может отказаться. Отметим, однако, что третий знак после запятой не является точным, так как в нем накапливается ошибка округления, производимого во время расчетов.