8.6. Методы нахождения опорного решения задачи линейного программирования

Метод искусственного базиса

Сформированный выше алгоритм симплекс-метода можно при­менять лишь в том случае, если выделено первое допустимое реше­ние, т. е. исходная задача линейного программирования приведена к виду

При этом , тогда, положив свободные неизвест­ные равными нулю, получаем опорное решение .

Рассмотрим метод нахождения опорного решения, основанный на введении искусственных переменных. Для этого запишем зада­чу линейного программирования в общем виде. Будем рассматри­вать задачу с числом неизвестных «n» и «r» ограничениями:

(8.42)

Перепишем систему (7.42) в другом виде. Для этого введем ис­кусственные переменные так, чтобы был выделен ба­зис. Тогда система примет вид

(8.43)

Системы (8.42) и (8.43) будут эквивалентны в том случае, если все у_i для будут равны 0. Кроме того, мы считаем, что все для . В противном случае соответствующие ограниче­ния из системы (8.42) умножим на — 1. Для того чтобы у_i, были равны 0, мы должны преобразовать задачу таким образом, чтобы все искусственные переменные y₁ перешли в свободные неизвестные.

В этом случае система (8.43) после преобразования примет вид

(8.44)

От системы (8.43) к системе (8.44) всегда можно перейти шага­ми симплекс-метода. При таком переходе в качестве линейной формы рассматривают функцию

(8.45)

равную сумме искусственных переменных. Переход заканчивают, когда F_min = 0 и все искусственные переменные у_i,- переведены в свободные неизвестные.

Анализ вариантов решений

1. Если , а все y_i переведены в свободные переменные, то задача не имеет положительного решения.

2. Если , а часть y_i, осталась в базисе, то для перевода их в свободные переменные необходимо применять специальные приемы.

В симплекс-таблице, соответствующей системе (8.44), после того как F_min = 0, а все y_i; — свободные, вычеркивают строку для F_min и столбцы для у_i. и решают задачу для исходной линейной формы Z_min

Рекомендуется вводить минимум искусственных переменных.

Пример 8.13. Решение задачи линейного программирования симплекс-методом. Для нахождения опорного плана использовать метод искусственных переменных.

Ограничения:

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

В базис можно выделить переменную x₃. Введем две искусственные переменные — y₁ и y₂.

Составим симплекс – таблицу:

Наименьший положительный элемент в строке линейной формы F_min = 2. Разрешающий элемент находится на пересечении столбца переменной x₅ и строки переменной y₁.

Заполним следующую симплекс – таблицу:

Наименьший положительный элемент в строке линейной формы F_min = 1. Минимальное симплекс – отношение соответствует строке переменной y₂.

Заполним новую симплекс – таблицу:

Так как F_min = 0, а у₁ и у₂ переведены в число свободных, пе­реход к первому опорному решению завершен. Строку, соответст­вующую F_min, и столбцы переменных у_] и у₂ вычеркиваем в послед­ней таблице и переписываем ее в новом виде:

Решим задачу для исходной линейной формы Z_mln. В послед­ней таблице находим разрешающий элемент. Он равен 8. Выполняя действия согласно алгоритму симплекс-метода, получим следующую таблицу:

В последней строке (Z_min) положительных элементов нет, сле­довательно, оптимальное решение найдено.

Значение целевой функции Z_min равно 10/8. Оптимальный план = (6/8; 2/8; 0; 0; 5).

Второй алгоритм отыскания опорного плана

Пусть задача линейного программирования записана в канони­ческом виде:

(8.46)

(8.47)

Построим первую таблицу Жордана – Гаусса для задач (8.46) и (8.47). Для единообразия вычислительной процедуры к исходной таблице приписываем строку целевой функции:

(8.48)

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

Алгоритм метода следующий.

1. Запишем задачу в форме таблицы (8.48), при этом все элементы столбца свободных членов b_i должны быть неотрицательны . Уравнения системы (8.46), в которых свободные члены отрицательны, предварительно нужно умножить на — 1.

2. Таблицу (8.48) преобразуем шагами Жордана— Гаусса исклю­чений. При этом на каждом шаге разрешающим может быть вы­бран любой столбец, содержащий хотя бы один положительный элемент. Строка целевой функции на выбор разрешающих столб­цов влияние не оказывает.

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

4. В процессе преобразований вычеркиваем строки, состоящие из одних нулей.

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

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

Теорема. Если разрешающий элемент выбирать по наименьшему положительному симплекс-отношению, то после шага Жордана—Га­усса свободный член в разрешающей строке становится положитель­ным, а остальные члены сохраняют свой знак.

Выбор разрешающего элемента производят иначе, а именно.

8. Просматриваем строку, соответствующую какому-либо отри­цательному свободному члену. Выбираем в ней какой-либо отри­цательный элемент — соответствующий этому элементу столбец бу­дет разрешающим.

9. Выбор разрешающего элемента производится по минималь­ному положительному симплекс-отношению. Если задача разре­шима, то через конечное число шагов получают первое допустимое решение и можно применять симплекс-метод.

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

Пример8.14. Определение опорного плана.

Дана следующая система:

(8.49)

(8.50)

Два свободных члена в системе ограничений отрицательны, по­этому перед тем, как записать задачу в виде таблицы (8.48), умно­жим соответствующие уравнения (8.49) на -1:

Запишем данную задачу в виде таблицы (8.48).

Выберем произвольно столбец с положительным элементом. Затем по минимальному положительному отношению находим раз­решающий элемент. В нашем примере он равен I и находится на пересечении столбца переменной х₄ и первой строки (элемент от­мечен квадратом). Выполняя преобразования Жордана-Гаусса, по­лучим следующую таблицу:

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

На данном этапе расчетов в последней таблице мы получили три нулевых столбца, что соответствует количеству ограничений в примере. Здесь необходимо закончить преобразования Жордана—Гаусса.

Запишем нашу задачу из последней таблицы так:

Получено первое допустимое решение, выделим его. Для этого положим х₁, = 0; х₂= 0, тогда = (0; 0; 2; 2; 5); Z_max = 5.

Задача решена.