Методы решения задач целочисленного программирования

Симплекс-метод

Симплекс-метод является универсальным методом решения задач линейного программирования. Суть данного метода заключается в построении допустимого ограничения (начало - опорное решение и последовательное улучшение этого плана при помощи определенного количества итераций). Симплекс-метод применяется для решения задач линейного программирования записанных в канонической форме. Нахождение начального опорного плана и переход к следующему опорному решению осуществляется при помощи метода Жордана-Гаусса для системы линейных уравнений.

Итак, рассмотрим задачу линейного программирования с ограничениями в форме уравнений. Дана система

(6)

m линейных уравнений с n неизвестными и линейная функция

(7)

Среди неотрицательных решений системы (6) нужно найти такое, которое минимизирует функцию (7).

Для начала работы по симплекс-методу требуется, чтобы заданная система уравнений была приведена к допустимому виду. Это означает, что какие-то из неизвестных должны быть выражены через остальные неизвестные, причем свободные члены этих выражений неотрицательны.

Пример допустимой системы:

(8)

здесь свободные члены равны соответственно 5,4 и 0.

Неизвестные в допустимом виде системы, которые выражены через остальные, называются базисными, а весь набор этих неизвестных - допустимым базисом неизвестных. Остальные неизвестные называются небазисными или свободными. Например, в системе (8) допустимый базис образован неизвестными х₁, х₂, х₃; неизвестные же х₄ и х₅ - свободные.

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

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

Например, если

а система ограничений приведена к виду (7), то новое выражение для f будет

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

пять неизвестных х_1, х₂, х₃, х₄, х₅ и система ограничений приведена к допустимому виду с базисом {x₁, х₂, х₃ }:

(9)

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

(10)

Напомним, что решается задача о минимизации f при ограничениях (9) и условиях

, , , ,

Положим все свободные неизвестные равными нулю:

,

и найдем из системы (4) значение базисных неизвестных:

Полученное таким путем решение системы (9):

(11)

будет неотрицательным. Оно называется базисным решением, отвечающим базису {х₁, х₂, х₃ }. Для базисного решения значение функции f равно f _В = .

Возможны три случая:

1. Все коэффициенты при свободных неизвестных в выражении для f неотрицательны:

Тогда для любого неотрицательного решения системы (9) имеем , значит, .Таким образом, , т. е. базисное решение является оптимальным — задача решена.

2. Имеется свободное неизвестное, коэффициент при котором в выражении f отрицателен, а все коэффициенты при этом неизвестном в уравнениях (9) - неотрицательны.

Пусть, например, а , . Тогда, отправляясь от базисного решения (11), будем наращивать значение х₄ (не меняя х₅=0). Значения базисных неизвестных также будут меняться; мы получим:

т. е. решение (х_1, х₂, х₃, х₄, 0,0) будет оставаться неотрицательным. При этом , и ввиду ₄<0 значение f с ростом х₄ будет неограниченно уменьшаться. Таким образом, в этом случае т. е. задача решения не имеет.

3. Имеется свободное неизвестное, коэффициент при котором в f отрицателен, но и среди коэффициентов при этом неизвестном в уравнениях (9) также есть отрицательные.

В этом случае производится шаг, а именно, от базиса В мы переходим к новому базису В', с таким расчетом чтобы значение f_в уменьшилось или по крайне мере не увеличилось: Разумеется, изменение базиса влечет за собой соответствующую перестройку системы (9) ограничений и выражений (10) для функций f.

Опишем конкретно содержание шага. Пусть, например, и отрицательны, а

- положительно или равно 0:

(12)

Если снова, как в случае II, наращивать значение х₄ то будем иметь:

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

, , , , (13)

для которого значение функции f будет , (поскольку и ).

Таким образом, с ростом х₄ первым из базисных неизвестных обращается в нуль неизвестное x₁. Это служит для нас сигналом к замене базиса B = {х₁, х₂, х₃ } на B' = {x₄, х₂, х₃ }, а именно: из старого базиса удаляется неизвестное х₁ и вместо него в базис вводится неизвестное х₄ (из числа прежних свободных).

Смена базиса, как уже говорилось, влечет за собой перестройку системы (9). Из первого уравнения (для х₁) выражаем:

(14)

и подставляем это выражение для х₄ в остальные два уравнения.

В итоге получаем систему вида:

(15)

с базисным решением:

, , , , (16)

которое должно совпадать с решением (13), поскольку, как видно из самой системы (14), двух разных решений с х₁,=0, х₅=0 быть не может. Таким образом, базисное решение (15) является снова неотрицательным. Что же касается нового значения функции f, то оно равно:

(17)

и, таким образом, (следует учесть, что и поэтому ). Итак, с переходом от базиса В к В' система ограничений сохранила допустимую форму (10), где а 0,b 0,с 0, а значение функции f для базисного решения уменьшилось или осталось прежним.

Переход от базиса В к новому базису В' и означает шаг, который делается в случае III. Разумеется, старое выражение для f, т. е. (10), должно быть теперь заменено новым:

(18)

которое получается из (10) заменой неизвестного х₄ по формуле (14).

Если для полученной задачи (15), (18) снова имеет место случай III, то делаем следующий шаг, т. е. переходим к новому базису В", для которого и так до тех пор, пока не придем к одному из случаев I или II. Тогда процесс заканчивается.

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

Описание симплекс - таблиц произведем на примере задачи (9), (10), где требуется минимизировать функцию (10) при ограничениях (9) и условиях х_j 0 (i=1,....,5).

Для заполнения первой таблицы необходимо в каждом из уравнений (4) перенести все члены, кроме свободного, из правой части в левую, т. е. записать (9) в виде:

(19)

Аналогичную работу следует проделать и с равенством (10):

Теперь можно заполнить симплекс-таблицу (таблица 1):

Таблица 1: Симплекс-таблица

Базисные неизвестные	Свободные члены
f

Заглавная строка таблицы и характер заполнения, не считая, стрелок, в комментариях не нуждаются. Расстановку стрелок поясним ниже.

В соответствии с ранее описанной методикой мы должны, прежде всего, выяснить, имеется ли в первоначальном выражении:

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

Предположим, что в последней строке имеется (не считая ) положительное число ₄. Отмечаем столбец, в котором оно находится, вертикальной стрелкой. Далее просматриваем остальные числа этого столбца. Если среди нет отрицательных чисел - это означает, что , и мы имеем случай II. Тогда ,и процесс снова прекращается.

Пусть, наконец, среди чисел отмеченного столбца, кроме последнего числа, имеются положительные числа. Это означает, что мы имеем случай III и, следовательно, должны сделать шаг. Например, как мы считали ранее, пусть – , (это означает ), а (т.е. ), в точном соответствии с предложением (17). В этом случае описанная ранее методика предписывает составить отношения:

и выбрать из них наименьшее.

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

С этого момента начинается перестройка таблицы, цель которой состоит в переходе к новому базису {х₄,х₂,х₃}. Ее можно осуществить при помощи все того же метода Гаусса. А именно умножаем выделенную строку на такое число, чтобы на месте разрешающего элемента появилась единица, т. е. умножаем на . Это соответствует тому, что первое из уравнений (19) разрешается относительно нового базисного неизвестного х₄. Полученную таким образом новую строку вписываем уже в новую таблицу снова в виде первой строки. Затем к каждой из остальных строк таблицы 1 прибавляем вновь полученную строку, умноженное на такое число, чтобы в клетке отмеченного столбца появился нуль - это соответствует исключению неизвестного х₄ из остальных уравнений, а также из выражения для f. Преобразованные таким образом строки пишем в новую таблицу на место прежних строк. В результате получаем новую таблицу.

[3]