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

 

Линейное программирование – теоретический аппарат модельного исследования, направленного на отыскание наилучшего способа распределения ограниченных ресурсов. Целевая функция и ограничения математической модели линейного программирования представляются линейными уравнениями и неравенствами. Математическая модель линейного программирования имеет вид

 

              (1.1)

 

Симплекс метод

 

Симплекс-метод – метод обхода угловых точек области допустимых решений (симплекса) с проверкой на оптимальность.

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

Допустимое базисное решение – базисное решение, удовлетворяющее требованию неотрицательности правых частей.

Небазисные переменные – переменные, имеющие нулевое значение.

Базисные переменные – переменные, имеющие ненулевое значение.

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

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

Симплекс-алгоритм состоит из следующих шагов.

Шаг 1. Определение начального допустимого базисного решения.

Шаг 2. Определение включаемой переменной из числа небазисных переменных. Если такой переменной нет, то решение оптимально. Иначе осуществляется переход к шагу 3.

Шаг 3. Определение исключаемой переменной из числа базисных переменных.

Шаг 4. Определение нового базисного решения. Переход на шаг 2 [2].

 

Метод Гаусса-Жордана

 

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

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

Ведущий столбец – столбец симплекс-таблицы, соответствующий включаемой переменной.

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

Условие оптимальности. Включаемой переменной в задаче максимизации (минимизации) является небазисная переменная, имеющая в Z-уравнении наибольший отрицательный (положительный) коэффициент. В случае равенства коэффициентов для нескольких небазисных переменных выбор делается произвольно. Если все коэффициенты при небазисных переменных в Z-уранении неотрицательны (неположительны), полученное решение является оптимальным [2].

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

Метод Гаусса-Жордана включает две вычислительные процедуры.

1 Формирование новой ведущей строки.

Новая ведущая строка=Старая ведущая строка/Ведущий элемент.

2 Формирование остальных новых уравнений.

Новое уравнение=Старое уравнение–(Коэффициент ведущего столбца старого уравнения)*(Новая ведущая строка) [2]