Назначение и принцип работы методов искусственного базиса

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

или равно», «меньше или равно», «равно». При решении задачи линейного программирования для построения начального опорного плана необходимо,

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

единице, и не входящая ни в одно из других ограничений.

В ограничениях «меньше или равно» в качестве таких переменных используются остаточные переменные, добавляемые в ограничение при его приведении к стандартной форме. Для приведения к стандартной форме ограничений «больше или равно» вводятся избыточные переменные

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

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

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

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

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

обычных процедур симплекс - метода. В окончательном (оптимальном) решении задачи все искусственные переменные должны быть равны

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

Рассмотрим общий метод отыскания опорного плана (или исходной K -матрицы) основной задачи линейного программирования – метод искусственного базиса.

Идея метода состоит в том, что наряду с исходной (2.52)-(2.54) задачей линейного программирования рассматривается следующая вспомогательная задача линейного программирования:

найти вектор пространства , максимизирующий линейную форму (2.85)

при условиях

(2.86)

(2.87)

(2.88)

Переменные

Будем называть искусственными переменными вспомогательной задачи линейного программирования в отличие от основных переменных

задачи.

Обозначим

P_M - множество всех планов вспомогательной задачи линейного программирования;

P´ _M - множество тех планов вспомогательной задачи линейного программирования, все искусственные компоненты которых, являющиеся значениями искусственных переменных

равны нулю.

Очевидно, между множествами P_M и P´ _M существует взаимно-однозначное соответствие и если вектор является планом вспомогательной задачи линейного программирования, то вектор есть соответствующий ему план основной задачи, и наоборот.

Так как линейная форма ограничена сверху нулем на непустом множестве P_M, то конечное решение вспомогательной задачи линейного программирования существует, а в силу того, что расширенная матрица

системы линейных уравнений (2.86) является K -матрицей вспомогательной задачи, определяющей ее исходный опорный план, это решение можно в принципе найти симплексным методом. Предположим, что вспомогательная задача линейного программирования решена симплексным методом, на S – й итерации которого получен ее оптимальный опорный план: определяемый K – матрицей.

.

При этом матрица

(2.89)

является расширенной матрицей системы линейных уравнений, равносильной системе (2.86)