Аналитическое введение в симплекс-метод

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

Итак, если мы решаем ЗЛП в канонической форме, то система ограничений - это обычная система линейных уравнений. При решении задач ЛП получаются системы линейных уравнений, имеющие, как правило, бесконечно много решений.

Например, пусть дана система

Здесь число уравнений равно 2, а неизвестных - 3, уравнений меньше. Выразим x1 и x2 через x3:

Это общее решение системы. если переменной x3 придавать произвольные числовые значения, то будем находить частные решения системы. Например, x3 = 1 x1 = 1 x2 = 6. Имеем (1, 6, 1) - частное решение. Пусть x3 = 2 x1 = -3, x2 = 1, (-3, 1, 2) - другое частное решение. Таких частных решений бесконечно много.

Переменные x1 и x2 называются базисными, а переменная x3 - не базисная, свободная.

Совокупность переменных x1 и x2 образует базис: Б (x1x2). Если x3 = 0, то полученное частное решение (5, 11, 0) называется базисным решением, соответствующим базису Б (x1, x2).

Базисным называется решение, соответствующее нулевым значениям свободных переменных.

В качестве базисных можно было взять и другие переменные: (x1, x3) или (x2, x3).

Как переходить от одного базиса Б (x1x2) к другому базису Б (x1, x3)?

Для этого надо переменную x3 перевести в базисные, а x2 - в небазисные т. е. в уравнениях надо x3 выразить через x2 и подставить в 1-е:

 

Базисное решение, соответствующее базису Б (x1, x3), таково: (-19/5; 0; 11/5).

Если теперь от базиса Б (x1, x3) нам захочется перейти к базису Б (x2, x3), то

Базисное решение, соответствующее базису Б (x2, x3): (0;19/4; 7/8).

Из трех найденных базисных решений решение, соответствующее базису Б (x1, x3) - отрицательное x1  0, нас в ЗЛП интересуют только неотрицательные решения.

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

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

Пример 4.

Решить задачу ЛП.

Функцию F = x2 - x1 min необходимо минимизировать при заданной системе ограничений:

-2x1 + x2 + x3 = 2;

x1 + x2 + x5 = 5;

x1 - 2x2 + x4 = 12;

xi ≥ 0, i = 1, 5.

Эти ограничения могут рассматриваться как произошедшие из неравенств, а переменные x3, x5, x4 - как дополнительные.

Запишем ограничения, выбрав базис из переменных Б{ x3, , x4, x5}:

Этому базису соответствует базисное неотрицательное решение

x1 = 0, x2 = 0, x3 = 2, x4 = 2, x5 = 5 или (0, 0, 2, 2, 5).

Теперь нужно выразить F через небазисные переменные, в нашем случае это уже сделано: F = x2 - x1.

Проверим, достигла ли функция F своего минимального значения. Для этого базисного решения F = 0 - 0 = 0 - значение функции равно 0. Но его можно уменьшить, если x1 будет возрастать, т. к. коэффициент в функции при x1 отрицателен. Однако при увеличении x1 значения переменных x4, x5 уменьшаются (смотрите второе и третье равенство системы ограничений). Переменная x1 не может быть увеличена больше чем до 2, иначе x4 станет отрицательной (ввиду равенства 2), и не больше, чем до 5, иначе x5 - отрицателен. Итак, из анализа равенств следует, что переменную x1 можно увеличить до 2, при этом значение функции уменьшится.

Перейдем к новому базису Б2, введя переменную x1 в базис вместо x4.

Б2{x1, x3, x5}.

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

Имеем:

F = -2 - x2 + x4.

 

Базисное решение, соответствующее базису Б2{x1, x3, x5}, имеет вид (2, 0, 6, 0, 3), и функция принимает значение F = -2 в этом базисе.

Значение функции можно и дальше уменьшать, увеличивая x2. Однако, глядя на систему, x2 можно увеличивать лишь до 1, т. к. иначе из последнего равенства x5 = 3 - 3x2 + x4 следует, что при x2 > 1 x5 станет отрицательной. А у нас все переменные в ЗЛП предполагаются неотрицательными. Остальные уравнения системы не дают ограничений на x2. Поэтому увеличим x2 до 1, введя его в базис вместо x5: Б3{x1, x2, x3}.

Выразим x2 через x5 и подставим во все уравнения:

.

Базисное решение, соответствующее базису Б3{х1, х2, х3}, выписывается (4, 1, 9, 0, 0), и функция принимает значение F = -3. Заметим, что значение F уменьшилось, т. е. улучшилось по сравнению с предыдущим базисом.

Посмотрев на вид целевой функции , заметим, что улучшить, т. е. уменьшить значение F нельзя и только при x4 = 0, x5 = 0 значение F = -3. как только x4, x5 станут положительными, значение F только увеличится, т. к. коэффициенты при x4, x5 положительны. Значит, функция F достигла своего оптимального значения F* = -3. Итак, наименьшее значение F, равное -3, достигается при x1* = 4, x2* = 1, x3* = 9, x4* = 0, x5* = 0.

Пример завершен.

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

загрузка...