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

Линейное программирование — это частный раздел оптимального программирования. В свою очередь оптимальное (математическое) программирование — раздел прикладной математики, изучающий задачи условной оптимизации. В экономике такие задачи возникают при практической реализации принципа оптимальности в планировании и управлении. Необходимым условием использования оптимального подхода к планированию и управлению (принципа оптимальности) является гибкость, альтернативность производственно-хозяйственных ситуаций, в условиях которых приходится принимать планово-управленческие решения. Именно такие ситуации, как правило, и составляют повседневную практику хозяйствующего субъекта (выбор производственной программы, прикрепление к поставщикам, маршрутизация, раскрой материалов, приготовление смесей и т. д.). Суть принципа оптимальности состоит в стремлении выбрать такое планово-управленческое решение где — его компоненты, которое наилучшим образом учитывало бы внутренние возможности и внешние условия производственной деятельности хозяйствующего субъекта. Слова «наилучшим образом» здесь означают выбор некоторого критерия оптимальности, т. е. некоторого экономического показателя, позволяющего сравнивать эффективность тех или иных планово-управленческих решений. Традиционные критерии оптимальности: «максимум прибыли», «минимум затрат», «максимум рентабельности» и др. Слова «учитывало бы внутренние возможности и внешние условия производственной деятельности» означают, что на выбор планово-управленческого решения (поведения) накладывается ряд условий, т. е. выбор X осуществляется из некоторой области возможных (допустимых) решений D; эту область называют также областью определения задачи. Таким образом, реализовать на практике принцип оптимальности в планировании и управлении — это значит решить экстремальную задачу вида: где — математическая запись критерия оптимальности — целевая функция.

В задаче линейного программирования (ЗЛП) требуется найти экстремум (максимум или минимум) линейной целевой функции :

(1.1).

При ограничениях (условиях):

.

(1.2).

…

.

(1.3).

где — заданные постоянные величины.

Так записывается общая задача линейного программирования в развернутой форме; знак означает, что в конкретной ЗЛП возможно ограничение типа равенства или неравенства (в ту или иную сторону). Систему ограничений (1.2) называют функциональными ограничениями ЗЛП, а ограничения (1.3) — прямыми.

Вектор X =, удовлетворяющий системе ограничений (1.2), (1.3), называется допустимым решением, или планом ЗЛП, т. е. ограничения (1.2), (1.3) определяют область допустимых решений, или планов задачи линейного программирования (область определения ЗЛП).

План (допустимое решение), который доставляет максимум или минимум целевой функции (1.1), называется оптимальным планом (оптимальным решением) ЗЛП.

Канонической формой записи задачи линейного программирования (КЗЛП) называют задачу вида (запись с использованием знаков суммирования):

Найти.

(1.4).

при ограничениях.

(1.5).

(1.6).

Симплексный метод решения:

Среди универсальных методов решения задач линейного программирования наиболее распространен симплексный метод (или симплекс-метод), разработанный американским ученым Дж. Данцигом. Суть этого метода заключается в том, что вначале получают допустимый вариант, удовлетворяющий всем ограничениям, но необязательно оптимальный (так называемое начальное опорное решение); оптимальность достигается последовательным улучшением исходного варианта за определенное число этапов (итераций). Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения рассмотренного выше метода Жордана-Гаусса для системы линейных уравнений в канонической форме, в которой должна быть предварительно записана исходная ЗЛП; направление перехода от одного опорного решения к другому выбирается при этом на основе критерия оптимальности (целевой функции) исходной задачи. Симплекс-метод основанна следующих свойствах ЗЛП:

• 1. Не существует локального экстремума, отличного от глобального. Другими словами, если экстремум есть, то он единственный.
• 2. Множество всех планов задачи линейного программирования выпукло.
• 3. Целевая функция ЗЛП достигает своего максимального (минимального) значения в угловой точке многогранника решений (в его вершине). Если целевая функция принимает свое оптимальное значение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек.
• 4. Каждой угловой точке многогранника решений отвечает опорный план ЗЛП.

Рассмотрим две разновидности симплексного метода: симплекс-метод с естественным базисом и симплекс-метод с искусственным базисом (или М-метод).

Симплекс-метод с естественным базисом. Для применения этого метода ЗЛП должна быть сформулирована в канонической форме (1.4) — (1.6), причем матрица системы уравнений должна содержать единичную подматрицу размерностью. В этом случае очевиден начальный опорный план (неотрицательное базисное решение).

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

Проверка на оптимальность опорного плана проходит с помощью критерия оптимальности, переход к другому опорному плану — с помощью преобразований Жордана-Гаусса и с использованием критерия оптимальности.

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

Признак оптимальности заключается в следующих двух теоремах.

Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие то можно получить новый опорный план, для которого значение целевой функции будет больше исходного; при этом могут быть два случая:

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

Теорема 2. Если для всех векторов выполняется условие, то полученный план является оптимальным.

На основании признака оптимальности в базис вводится вектор A_k, давший минимальную отрицательную величину симплекс-разности:

Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор, который дает минимальное положительное отношение Строка называется направляющей, столбец и элемент — направляющими (последний называют также разрешающим элементом).

Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формулам, а элементы любой другой i-й строки пересчитываются по формулам:

Значения базисных переменных нового опорного плана (показатели графы «план») рассчитываются по формулам:

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

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

Для использования приведенной выше процедуры симплекс-метода к минимизации линейной формы следует искать максимум функции, затем полученный максимум взять с противоположным знаком. Это и будет искомый минимум исходной ЗЛП.

В пункте 2.2.1 рассмотрим применение данного метода на примере анализа деятельности ОАО «Ростелеком».