Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

1.4. Симплекс-алгоритм. Принцип организации переходов

Пусть задача линейного программирования дана в следующей постановке: найти значения x1 ≥ 0, x2 ≥ 0,..., xn ≥ 0 доставляющие минимум функции z = nΣj = 1 cjxj при

(1.9)

Считая каноническую форму (1.9) допустимой рассмотрим очевидное базисное решение (∀∀Bi≥0) x1 = B1, ...., xm = Bm, xm+1 = ... = xn = 0. Ответ на вопрос, является ли оно оптимальным, можно получить, проведя несложные преобразования выражения z.

Умножим каждую строку (1.9) на коэффициент cj, номер которого совпадает с номером этой строки, что позволяет прийти (после суммирования строк) к равенству z = z0 + nΣj = m+1jxj где z0 - некоторая константа; c̃j - коэффициенты при свободных переменных рассматриваемого базисного решения. По своему смыслу z0 есть значение z, получаемое в точке с координатами x1 = B1 = ,..., xm = Bm, xm+1 = .... = xn = Очевидно, z0 и все c̃j определяются теми Aij, Вj (i = 1,...,m; j = m + 1,...,n), которые присутствуют в (1.9), а также теми cj (j = 1,...,m), которые входят в первые m слагаемых исходного выражения z.

Обратимся теперь к теореме (4):допустимое базисное решение xi = Вi (i = 1,...,m), xj = 0 (j = m + 1,....,n) является оптимальным тогда, когда коэффициенты cj при не базисных переменных в выражении z = z0 + nΣj = m+1jxj не отрицательны.

Доказательство: обратим внимание на то, что в предлагаемой задаче нужно минимизировать z и что z - z0 = nΣj = m+1jxj. Если c̃m+1 ≥ 0,...,c̃n ≥ 0 то при любых xj ≥ 0 (j = m + 1,..,n) разность z - z0 не отрицательна, т. е. ее минимум есть 0. Следовательно, минимум z не будет меньше (иначе найдется отрицательное значение разности z - z0, равное min z = z0, а этого не должно быть). Для рассматриваемого базисного решения z = z0, поэтому предыдущее утверждение можно сохранить, положив min z = z0, что и доказывает теорему.□

Из проведенного доказательства следует: всякое решение системы (1.9), которому соответствует нулевая сумма c̃m+1xm+1 +...+ c̃nxn при ∀c̃j≥0 и ∀xj≥0 (j = m + 1,..., n), также будет оптимальным. Наконец, допустимое оптимальное базисное решение окажется единственным, если ∀c̃j>0 (в этом случае свести к нулю разность z - z0 можно, лишь приняв хm+1 = ... = хn = 0).

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

Пусть базисное решение вида x1 = В1, х2 = В2, ... .. ,хm = Вm, xm+1 = .... = хn = 0 оказалось не оптимальным (среди коэффициентов c̃j j = m + 1,...,n, есть отрицательные) . Чтобы перейти к другому допустимому решению, нужно сделать строго положительной (ввести в базис) какую-то из переменных xm+1,...,xn обратив в нуль одну из x1, x2,...,xn Имея в виду ограничение ∀xj≥0, можно сказать, что при таком переходе z уменьшится только тогда, когда вводимая переменная будет иметь в выражении z отрицательный коэффициент.

Обозначим через р тот номер j из {m+1,..., n}, для которого величина cj, во-первых, отрицательна и, во-вторых, максимальна по модулю, т. е. c̃p = min{c̃j < 0}. Решив дать положительное приращение величине хр = 0, представим базисные переменные иге помощью (1.9) в виде

x1 = B1 - A1pxp,..,xm = Bm - Ampxp;
z = z0 + c̃pxp (c̃p < 0; m + 1 ≤ p ≤ n)

Поскольку c̃p < 0, нужно как можно больше увеличивать хр в стремлении минимизировать z, однако возрастание хр будет продолжаться до тех пор, пока какая-то из переменных x1, х2,...,хm не обратится в нуль. Это произойдет, если хотя бы один коэффициент Aip (i = 1,...,m) в (1.10) положителен (по исходному условию Вi ≥ 0). Если же Aip > 0 для нескольких номеров i из {1, 2,...,m}, то первой в нуль обратится та базисная переменная из (1.10), которой отвечает наименьшая величина отношения Bi/Aip Таким образом, предельное значение xр, до которого можно увеличивать x̂р, найдется как x̂p = mini{Bi/Aip}. Необходимо подчеркнуть, что равенство нулю хотя бы одного Bi при соответствующем Aip > 0 (случай вырожденного базисного решения) означает невозможность ввода xр в базис с соблюдением требований ∀xj ≥ 0.

Указанная процедура перехода может быть повторена, если новое базисное решение допускает дальнейшее улучшение z. Симплекс-алгоритм состоит в последовательных повторениях подобных операций до тех пор, пока не будет найдено либо оптимальное решение исходной задачи линейного программирования, либо множество допустимых ее решений, для которых |z| → ∞ Полезно обратить внимание на то, что рассмотренный процесс поиска X*, z* закончится за конечное число шагов, если ни на одном из них не возникают вырожденные базисные решения.

Обратимся теперь к более подробному описанию этапов реализации симплекс-метода применительно к стандартной форме (1.2) условий задачи линейного программирования. Без потери общности можно считать здесь все bi ≥ 0 (i = 1,...,m) (в противном случае достаточно умножить на -1 обе части соответствующих строк).

Этап I: система (1.2) искусственно расширяется путем введения переменной xn+i ≥ 0 в i-ю строку (i = 1,...,m) и принимает вид

a11x1 + a12x2 + ..... +a1nxn + xn+1 = b1,
a21x1 + a22x2 + ..... +a2nxn + xn+2 = b2
.... ..... ..... ....
am1x1 + am2x2 + ..... +amnxn + xn+m = bm (1.11)
∀xj ≥ 0 (j = 1,....,n), ∀xn+i ≥ 0 (i = 1,...m)

Если существует решение исходной системы (1.2), то оно допустимо и для (1.11) при xn+1 = ... = xn+m = 0; наоборот, если удастся получить решение (1.11), содержащее нулевые xn+i (i = 1,...,m), то оно будет допустимым для (1.2);

- рассматривается сумма


наименьшее возможное значение которой есть нуль вследствие не отрицательности xn+1 именно оно будет достигнуто, если (1.2) имеет решение, причем проверка достижимости min w = 0 осуществляется в рамках следующей вспомогательной задачи линейного программирования: найти xj ≥ 0 (j = 1,...,n), xn+i ≥ 0 (i = 1,...,m)


- решается задача минимизации w с использованием стандартного симплекс-алгоритма; в качестве начального базисного решения, как это следует из (1.11), принимается xj = 0 (j = 1,...,n), xn+i = bi (i = 1,...,m). Если окажется min w > 0, то процесс вычислений можно прекратить, так как исходная задача с условиями (1.2) неразрешима; если же min w = 0, то соответствующее базисное решение фиксируется и используется на втором этапе исследований.

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

Этап II: оценивается решение вспомогательной линейной задачи, полученное в конце этапа I; в лучшем случае оно является невырожденным и содержит все xn+i в числе свободных переменных; в худшем случае некоторые xn+i войдут в базис (вырожденность), и тогда необходимо начинать этап II, сохраняя их нулевые значения; пусть в рассматриваемом решении свободными оказались xj(j∈J1, J1 ⊂ {1, 2, ..., n}) и xn+i (i ∈ J2, J2 ⊂ {1, 2, ...,m}), причем выражение w через эти переменные имеет вид


коэффициенты kj,hi здесь неотрицательны, поскольку речь идет об оптимальном решении, доставляющем min w = 0; чтобы на любом шаге этапа II сохранить w = 0, достаточно отбросить те xj, xn+i (j∈J1, i∈J2), которые имеют kj, hi > 0 в приведенном выше выражении w и сосредоточить внимание на оставшихся xj, xn+i с нулевыми коэффициентами kj, hi; решениям, состоящим только из таких xj, xn+i, всегда соответствует w = 0, что допустимо;

- после отбрасывания указанных xj, xn+i в рассмотрение вводится z и решается исходная задача линейного программирования; в результате либо отыскивается совокупность значений х*1, х*2,...,х*n, доставляющих экстремум z, либо обнаруживается, что |z| → ∞.

Ниже дан пример, иллюстрирующий возможности симплекс-метода.

Пример: найти x1, х2, ...,х6 → min {z = -7х1 - 5х2} при

1 + 3х2 + х3 = 19;
3х, + x5 = 15;
1 + х2 = 13;
1 + x6 = 18;
∀xj ≥ 0 (j = 1,...,6)

Решение: для простоты задача представлена сразу в канонической форме (относительно х3,..., х6); очевидное исходное базисное решение есть х3 = 19, х4 = 13, х5 = 15, х6 = 18, х1 = х2 = 0 и z = -7х1 - 5х2; обе не базисные переменные x1, х2 входят в выражение z с отрицательными коэффициентами, причем первый из них больше по -модулю, и согласно рекомендациям § 1.4 переменную x1 нужно вводить в базис; для этого выпишем с помощью (1) ряд соотношений: x3 = 19 - 2х1, х4 = 13 - 2х1, x5 = 15, х6 = 18 - 3x1; при возрастании x1 первой обратится в нуль величина х6, поэтому новое базисное решение есть х6 = 0, x1 = 6, х3 = 7, х4 = 1, x5 = 15, х2 = 0; z = -42 + 7x6/3 - 5х2 (ему соответствует величина z = -42, предыдущему безисному решению отвечало z = 0).

В новом выражении z отрицательный коэффициент имеет только х2, и теперь необходимо рассмотреть соотношения x1 = 6 - х6/3, х3 = 7 - 3х2, х4 = 1 - х2, x5 = 15 - 3х2, которые показывают, что увеличивать х2 можно лишь до единицы (при этом х4 обращается в нуль); следовательно, новое (третье по счету) базисное решение есть x4 = 0, х2 = 1, х6 = 0, x1 = 6, x3 = 4, x5 = -12, z = -47 + 5x4 - х6 (ему соответствует z = -47).

Теперь в выражении z отрицательный коэффициент имеет х6; введем эту переменную в базис, используя соотношения

х1 = 6 - x6/3, х2 = 1 + 2x6/3,
x33 = 4 - 4x6/3, x5 = 12 - 2x6,

полученные, как обычно, из (I); здесь при увеличении х6 в нуль обращается прежде всего x3, поэтому четвертое базисное решение есть x3 = 0, х6 = 3, х5 = 6, х1 = 5, х2 = 3, х4 = 0, z = - 50 +4x3/3 + 11x4/4.

Нетрудно видеть, что найденное решение оптимально: не базисные переменные х3 и х4 входят в выражение z с положительными коэффициентами; таким образом, x*1 = 5, х*2 = 3, х*3 = 0, х*4 = 0, х*5 = 6, х*6 = 3, z* = -50.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"