Методы линейного программирования

Алгоритм  симплекс-метода: 

     1). Записать задачу в канонической  форме;

     2). Разделить переменные на базисные  и свободные: перенести свободные  переменные в правую часть  ограничений-неравенств.

     3). Выразить базисные переменные  через свободные: решить систему линейных уравнений (ограничений-неравенств) – относительно базисных переменных;

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

     5). Выразить функцию цели через  свободные переменные: базисные  переменные, входящие в функцию,  выразить через свободные переменные;

     6). Вычислить полученное базисное решение и функцию цели на нем: приравнять к 0 свободные переменные;

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

     8). Определить включаемую в базис  и исключаемую из базиса переменные: если не все коэффициенты при  свободных переменных в функции  цели положительны (отрицательны), то  следует выбрать свободную переменную, входящую в функцию цели с максимальным по модулю отрицательным (положительным) коэффициентом, и увеличивать ее до тех пор, пока какая-нибудь из базисных переменных не станет равной 0. Свободную переменную рассматриваем как новую базисную переменную (включаемую в базис), а базисную переменную рассматриваем как новую базисную переменную (исключаемую из базиса);

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

Формальная модель задачи линейного программирования обычно задается в форме, так называемой, симплекс-таблицы, удобной для выполнения операций симплекс-метода: 

 
 

Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует  определенному ограничению-равенству  задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X₁, ..., X_m). Сверху от таблицы приведен набор всех переменных задачи, где X_m+1, ..., X_n - свободные переменные задачи. 

На начальном  шаге алгоритма симплекс-метода должно быть выбрано базисное допустимое решение (X₁, ..., X_m) ≥ 0 при X_j = 0 (j = m+1, ..., n), следовательно, все свободные члены ограничений A_i,0 ≥ 0 (i = 1, ..., m). Когда это условие выполнено, симплекс-таблица называется прямо-допустимой, так как в этом случае базисные переменные, равные A_i,0 , определяют допустимое решение прямой задачи линейного программирования. Если все коэффициенты целевой функции A_0,j ≥ 0 (j = 1, ..., m), то симплекс-таблица называется двойственно-допустимой, поскольку соответствующее решение является допустимым для двойственной задачи линейного программирования. Если симплекс-таблица является одновременно прямо и двойственно допустимой, т.е. одновременно все A_i,0 ≥ 0 и A_0,j ≥ 0, то решение оптимально. 

Поскольку допустимыми являются лишь неотрицательные значения управляемых параметров, то изменение целевой функции за счет вариации свободных переменных, через которые она выражена, возможно только в сторону увеличения, т.e. будет ухудшаться. Если среди ее коэффициентов имеются A_0,j < 0, то значение целевой функции еще можно уменьшить (т.e. улучшить), увеличивая значение любой свободной переменной X_j с отрицательным коэффициентом A_0,j при побочном уменьшении базисных переменных, чтобы оставались справедливы ограничения задачи. Вообще можно использовать любую свободную переменную X_j с A_0,j <0, но на практике обычно действуют в соответствии со стратегией наискорейшего спуска, выбирая минимальный элемент A_0,p < 0 из всех отрицательных A_0,j : 

Столбец p симплекс-таблицы, соответствующий выбранному коэффициенту A_0,p < 0, называется ведущим столбцом. Свободная переменная ведущего столбца должна быть введена в базис вместо одной из текущих базисных переменных. Очевидно, из базиса следует исключить такую переменную X_q, которая раньше других обращается в нуль при увеличении переменной X_p ведущего столбца. Ее индекс легко определить, если среди положительных элементов ведущего столбца p найти элемент, удовлетворяющий условию:

.    

Элемент A_q,p называется ведущим элементом, cтрока q симплекс-таблицы, содержащая ведущий элемент, называется, соответственно, ведущей строкой. Переменная ведущей строки X_q заменяется в базисе переменной ведущего столбца X_p и становится свободной переменной с значением 0, в то время как новая базисная переменная X_p достигнет максимально возможного значения, равного:

  .      

После указанного взаимообразного обмена переменными X_p и X_q между наборами свободных и базисных переменных нужно модифицировать исходную каноническую модель задачи путем приведения ее к диагональной форме относительно нового множества базисных переменных. Для указанного преобразования можно формально использовать процедуру исключения Гаусса, которая состоит из двух элементарных операций, применяемых к системе алгебраических уравнений:

• умножение уравнения E₁(x) = 0 на константу K₁ и замена уравнения E₁(x) = 0 уравнением K₁*E₁(x) = 0;
• сложение уравнений E₁(x) = 0 и E₂(x) = 0 c последующей заменой уравнения E₂(x) = 0 уравнением E₁(X) + E₂(x) = 0.

 

Исключения  Гаусса позволяют привести систему  уравнений к диагональной форме  относительно желаемого множества  переменных. В данном случае исключение Гаусса применяется так, чтобы все  элементы симплекс-таблицы в ведущем столбце, кроме ведущего элемента A_q,p, стали нулевыми, а ведущий элемент стал равным единице:

           A_i,p = 0,  если i ≠ q ,

           A_i,p = 1,  если i = q. 

Указанные шаги симплекс-метода повторяются, пока не будет получена симплекс-таблица, которая одновременно является прямо и двойственно допустимой. Если в такой симплекс-таблице текущие базисные переменные будут равными A_i,0, а свободные - нулю, то будет получено оптимальное решение. 

Определение значения целевой функции и переменных в одной вершине называется итерацией. Число итераций, требуемых для решения задачи линейного программирования, обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс-метода превращаются в прямой перебор базисных допустимых решений. Однако трудные для симплекс-метода задачи на практике встречаются крайне редко, что объясняет широкое распространение и большую популярность данного метода линейного программирования по сравнению с другими подходами. 

     Метод потенциалов 

Метод потенциалов впервые предложили Л. В. Канторович и М. К. Гавурин в 1949 г. Позже аналогичный метод  разработал Г. Данциг, исходя из общих  идей ЛП.

Метод потенциалов позволяет, исходя из некоторого опорного плана, построить за конечное число итераций решение задачи. 

На предварительном  этапе строят начальный опорный  план и составляют матрицу:

,

где - предварительные потенциалы пунктов:

. 

Предварительный этап. С помощью известного метода (например северо-западного угла или минимального элемента) определяют начальный опорный план Х₀ и вычисляют предварительные потенциалы:

.

По найденному опорному плану Х₀ строят схему из основных коммуникаций плана. Основные коммуникации P_ij  плана - это те, которым отвечают базисные компоненты плана, т.е. коммуникации для которых > 0. Далее образуют следующие множества: J₁ - множество индексов всех пунктов B_j, которые связаны с пунктом А₁ основными коммуникациями; І₁ - множество индексов тех пунктов А_і, которые связаны основными коммуникациями с множеством J₁; J₂ - множество пунктов B_j, которые связаны основными коммуникациями с множеством І₁ и т.д. Образование таких множеств І_к продолжаем до тех пор, пока не получим пустое множество.

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

Полагаем  для определенности и вычислим систему потенциалов относительно А₁. Тогда   где . После того как потенциалы всех пунктов найдены, строим матрицу:

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

(k+1)-ая итерация. Каждая итерация, кроме первой, где отсутствует первый этап, состоит из двух этапов. Предположим, что уже проведено k итераций (k=1,2,...), в результате которых получен план Х_k и вспомогательная матрица С_k. Цель (k+1)-й итерации - построение матрицы С_k+1, а также либо установление оптимальности плана Х_k, либо нахождение более экономичного плана X_k+1. 

Первый  этап. Вычисляют матрицу С_k+1. Преобразование матрицы С_k в матрицу С_k+1 состоит в следующем. Выбирают наибольший по модулю отрицательный элемент С_k. Пусть это элемент . Тогда вычеркивают (или выделяют) строку λ, в которой он содержится. Просматривают эту строку и отыскивают множество существенных его элементов. Х_k -существенными элементами называют те элементы , которые отвечают базисным элементам плана Х_k т.е. для которых . Вычеркивают столбцы, которые содержат эти элементы. Далее просматривают вычеркнутые столбцы и ищут в них новые существенные элементы, которые лежат в строках отличных от уже вычеркнутых ранее. Если такие элементы имеются, то вычеркивают строки, в которых они содержатся. Процесс выделения продолжают до тех пор,  пока очередное множество новых существенных элементов не окажется пустым. Поскольку каждые строка и столбец не могут быть выделены дважды, то весь процесс заканчивается не более чем за шагов. Далее строят матрицу С_k+1. Для этого величину прибавляют ко всем элементам выделенных строк и вычитают из элементов всех выделенных столбцов матрицы С_k. При этом все существенные элементы матрицы С_k остаются равными нулю, а кроме того, в нуль превращается и элемент . 

Если  все элементы матрицы С_k+1 окажутся неотрицательными, то X_k - оптимальный план, и на этом процесс заканчивается. В противном случае переходят ко второму этапу. 

Второй  этап. Цель этого этапа - построить более экономичный план Х_k+1. Выбирают наибольший по модулю отрицательный элемент матрицы С_k+1. Пусть это элемент . Строят цепочку из положительных элементов плана, которая замыкается на . После того, как цепочка построена, в ней находят минимальный нечетный по порядку следования элемент:

 

Прибавляют  ко всем четным элементам (по порядку следования) цепочки и к элементу и вычитают из всех нечетных элементов. Остальные элементы Х_k оставляют без изменения.

Новый план Х_k+1 построен. Он является базисным, так как число его ненулевых элементов не изменилось.

Пусть L_k - транспортные издержки, отвечающие плану Х_k. Тогда новое значение целевой функции, отвечающее плану X_k+1, находят по соотношению

  .                            

Так как  и , то . Поэтому Х_k+1 - улучшенный опорный план.