Алгебраический симплексный метод

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

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

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

Допустимое множество базисных решений системы линейных уравнений образует в объеме многогранное тело, например тетраэдр, вершины которого — угловые точки.

Каждой угловой точке многогранника решений соответствует опорный план (допустимое базисное решение).

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

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

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

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

Для использования рассмотренного алгоритма симплексного метода к минимизации линейной формы связи Алгебраический симплексный метод - student2.ru следует искать максимум функции Алгебраический симплексный метод - student2.ru , а затем полученное решение взять с обратным знаком.

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

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

Коммерческое предприятие реализует nтоварных групп, располагая mограниченными материально-денежными ресурсами Алгебраический симплексный метод - student2.ru ( Алгебраический симплексный метод - student2.ru ). Известны расходы ресурсов каждого i-вида на реализацию единицы товара по каждой группе, представленной в виде матрицы A= Алгебраический симплексный метод - student2.ru , и прибыль Алгебраический симплексный метод - student2.ru получаемая предприятием от реализации единицы товара j-группы (таблица 2.4.1). Необходимо определить объем и структуру товарооборота Алгебраический симплексный метод - student2.ru ( Алгебраический симплексный метод - student2.ru ), при которых прибыль коммерческого предприятия была бы максимальной.

Математическую модель задачи запишем следующим образом.

Определить вектор Алгебраический симплексный метод - student2.ru , который удовлетворяет ограничениям вида

Алгебраический симплексный метод - student2.ru

и обеспечивает максимальное значение целевой функции

Алгебраический симплексный метод - student2.ru .

Алгоритм симплексного метода включает следующие этапы.

1. Составление первого опорного плана.Система ограничений задачи, решаемой симплексным методом, задана в виде системы неравенств смысла « Алгебраический симплексный метод - student2.ru », правые части которых Алгебраический симплексный метод - student2.ru . Перейдем от системы неравенств к системе уравнений путем введения неотрицательных дополнительных балансовых переменных. Векторы-столбцы при этих переменных представляют собой единичные векторы и образуют базис, а соответствующие им переменные называются базисными:

Алгебраический симплексный метод - student2.ru ,

где Алгебраический симплексный метод - student2.ru — дополнительные переменные, Алгебраический симплексный метод - student2.ru , Алгебраический симплексный метод - student2.ru — базисные переменные, Алгебраический симплексный метод - student2.ru .

Решим эту систему относительно дополнительных переменных:

Алгебраический симплексный метод - student2.ru ,

а функцию цели перепишем в виде уравнения

Алгебраический симплексный метод - student2.ru

Следует заметить, что опорным решением называется базисное неотрицательное решение.

Полагая, что основные переменные Алгебраический симплексный метод - student2.ru , получим допустимое базисное решение — опорный план Алгебраический симплексный метод - student2.ru ; Алгебраический симплексный метод - student2.ru , который заносим в симплексную таблицу. 2.4.2. Она состоит из коэффициентов системы ограничений и свободных членов. Последняя строка таблицы называется индексной и заполняется коэффициентами функции цели, взятыми с противоположным знаком.

2. Проверка плана на оптимальность.Если значение базисных переменных неотрицательны, то решение является допустимым. Если все коэффициенты индексной строки симплексной таблицы при решении задачи на максимум неотрицательны ( Алгебраический симплексный метод - student2.ru 0), то

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

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

Затем элементы столбца свободных членов симплексной таблицы делим на элементы того же знака (+/+;-/-) ведущего столбца. Результаты заносим в отдельный столбец Алгебраический симплексный метод - student2.ru , которые должны быть всегда положительны. Строка симплексной таблицы, соответствующая минимальному значению Алгебраический симплексный метод - student2.ru , является ведущей. Она и определяет переменную Алгебраический симплексный метод - student2.ru , которая на следующей итерации выйдет из базиса и станет свободной (обмен). Элемент симплексной таблицы, находящийся на пересечении ведущих столбца и строки, называют разрешающим и выделяют, например, кружком.

4. Построение нового опорного плана.Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана — Гаусса. Сначала заменим переменные в базисе, т.е. вместо Алгебраический симплексный метод - student2.ru в базис войдет переменная Алгебраический симплексный метод - student2.ru соответствующая ведущему столбцу (замена).

Разделим все элементы ведущей строки предыдущей симплексной таблицы на разрешающий элемент и результаты деления занесем в строку следующей симплексной таблицы, соответствующей введенной в базис переменной Алгебраический симплексный метод - student2.ru . В результате этого на месте разрешающего элемента в следующей симплексной таблице запишем 1, а в остальных клетках у столбца, включая клетку столбца индексной строки, записываем нули. Остальные новые элементы нового плана находятся по правилу прямоугольника:

НЭ=СТЭ-А*В/РЭ,

где СТЭ — элемент старого плана;

РЭ — разрешающий элемент;

А и В — элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Далее возвращаемся ко второму этапу алгоритма — проверке плана на оптимальность.

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

Если в ведущем столбце все коэффициенты Алгебраический симплексный метод - student2.ru <=0 , то функция цели Алгебраический симплексный метод - student2.ru не ограничена на множестве допустимых планов, т.е. Алгебраический симплексный метод - student2.ru и задача не имеет решения.

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

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

имеющие одинаковые наименьшие значения Алгебраический симплексный метод - student2.ru , делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам. Например, таблица, содержащая три равных значения Алгебраический симплексный метод - student2.ru =2, имеет следующий вид:

План Базисные перемен-ные Значения базисных переменных Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru
I Алгебраический симплексный метод - student2.ru 4/2=2
  Алгебраический симплексный метод - student2.ru 8/4=2
  Алгебраический симплексный метод - student2.ru -1 10/5=2

Допустим, разрешающим столбцом является Алгебраический симплексный метод - student2.ru , тогда разрешающим элементом может быть 2, 4 или 5. Следуя указанному правилу, получим таблицу:

Значения базисных переменных Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru
1.5 0.5
0.25 0.25
2.4 -0.2 0.2 0.2

Сравниваем последовательно слева направо полученные частные по столбцам. В первом и втором столбцах все частные одинаковы, а в третьем столбце наименьшее частное 1,5 в первой строке, следовательно, эта строка и будет разрешающей с разрешающим элементом 2.

Если в оптимальный план вошла дополнительная переменная Алгебраический симплексный метод - student2.ru , то при реализации такого плана имеются недоиспользованные ресурсы i-го вида в количестве, полученном в столбце свободных членов симплексной таблицы.

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

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

Пример 1.Коммерческое предприятие, располагающее материально-денежными ресурсами, реализует три группы товаров А, В и С. Плановые нормативы затрат ресурсов на 1 тыс. руб. товарооборота, доход от продажи товаров на 1 тыс. руб. товарооборота, а также объем ресурсов заданы в таблице 2.4.1.

Определите плановый объем продажи и структуру товарооборота так, чтобы доход торгового предприятия был максимальным.

Таблица 2.4.1

Виды материально- денежных ресурсов Норма затрат материально-денежных ресурсов на 1 тыс. руб. товарооборота Объём ресурсов Алгебраический симплексный метод - student2.ru
Группа А Группа В Группа С
Рабочее время продавцов, чел.-ч 0,1 0,2 0,4
Площадь торговых залов, кв. м 0,05 0,02 0,02
Площадь складских помещений, кв. м
Доход, тыс. руб max

Решение.Дадим математическую модель задачи.

Определим вектор Алгебраический симплексный метод - student2.ru , который удовлетворяет условиям

Алгебраический симплексный метод - student2.ru

и обеспечивает максимальное значение целевой функции

Алгебраический симплексный метод - student2.ru

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных Алгебраический симплексный метод - student2.ru , Алгебраический симплексный метод - student2.ru , Алгебраический симплексный метод - student2.ru :

Алгебраический симплексный метод - student2.ru .

Матрица коэффициентов A= Алгебраический симплексный метод - student2.ru этой системы уравнений имеет следующий вид:

Алгебраический симплексный метод - student2.ru

Векторы Алгебраический симплексный метод - student2.ru — линейно независимы, так как определитель, построенный на этих векторах, отличен от нуля. Следовательно, соответствующие этим векторам переменные Алгебраический симплексный метод - student2.ru , Алгебраический симплексный метод - student2.ru , Алгебраический симплексный метод - student2.ru являются базисными и в этой задаче определяют объемы неиспользованных ресурсов.

Решим систему уравнений относительно базисных переменных.

Алгебраический симплексный метод - student2.ru .

Функцию цели запишем в виде уравнения:

Алгебраический симплексный метод - student2.ru

Полагая, что свободные переменные Алгебраический симплексный метод - student2.ru , Алгебраический симплексный метод - student2.ru , Алгебраический симплексный метод - student2.ru , получим первый опорный план Алгебраический симплексный метод - student2.ru =(0, 0, 0, 1100, 120, 8000), Алгебраический симплексный метод - student2.ru , в котором базисные переменные Алгебраический симплексный метод - student2.ru =1100, Алгебраический симплексный метод - student2.ru =120, Алгебраический симплексный метод - student2.ru =8000. Следовательно, товары не продаются, доход равен нулю, а ресурсы не используются. Полученный первый опорный план запишем в симплексную таблицу 2.4.2.

Первый опорный план неоптимальный, так как в индексной строке находятся отрицательные коэффициенты: —3, —5, —4.

В качестве ведущего выберем столбец, соответствующий переменной Алгебраический симплексный метод - student2.ru , так как наибольший коэффициент по модулю: |-5|>{|-3|, Алгебраический симплексный метод - student2.ru }.

Вычислим значения Алгебраический симплексный метод - student2.ru по строкам как частное отделения Алгебраический симплексный метод - student2.ru и из них выберем наименьшее:

.

Таблица 2.4.2

План Базисные переменные Значения базисных переменных Значения коэффициентов при Алгебраический симплексный метод - student2.ru min
Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru
I Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru 0.1 0.2 0.4
  Алгебраический симплексный метод - student2.ru 0.05 0.02 0.02
  Алгебраический симплексный метод - student2.ru
Индексная срока Алгебраический симплексный метод - student2.ru   -3 Алгебраический симплексный метод - student2.ru -5   -4        
II Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru 0.5
  Алгебраический симплексный метод - student2.ru 0.04 -0.02 -0.1
  Алгебраический симплексный метод - student2.ru 2.5 -5
Индексная срока Алгебраический симплексный метод - student2.ru -0.5  
III Алгебраический симплексный метод - student2.ru 2.25 6.25 -12.5  
  Алгебраический симплексный метод - student2.ru -0.5 -2.5  
  Алгебраический симплексный метод - student2.ru 1.25 1.25 -62.5  
Индексная срока Алгебраический симплексный метод - student2.ru 5.75 23.75 12.5  

Следовательно, первая строка является ведущей.

Разрешающий элемент равен 0,2 и находится на пересечении ведущего столбца и ведущей строки и выделен в таблице 2.4.2.

Формируем следующую часть симплексной таблицы. Вместо переменной Алгебраический симплексный метод - student2.ru в план II войдет переменная Алгебраический симплексный метод - student2.ru .Строка, соответствующая переменной Алгебраический симплексный метод - student2.ru в плане II, получена в результате деления всех элементов строки Алгебраический симплексный метод - student2.ru плана I на разрешающий элемент РЭ = 0,2. На месте разрешающего элемента в плане II получаем 1. В остальных клетках столбца Алгебраический симплексный метод - student2.ru плана II записываем нули.

Таким образом, в новом плане II заполнены строка Алгебраический симплексный метод - student2.ru и столбец Алгебраический симплексный метод - student2.ru . Все остальные элементы нового плана II, включая элементы индексной строки, определяются по правилу прямоуголника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ = 0,2. Во второй вершине по диагонали находится старое значение элемента, например значение целевой функции Алгебраический симплексный метод - student2.ru =0=СЭ, которое указывает на место расположения нового НЭ в новом плане II. Третий элемент А=1100 и четвертый элемент В=—5 завершают построение прямоугольника в недостающих двух вершинах и расположены по другой диагонали. Значение нового элемента в плане II находится из выражения:

НЭ=СЭ-А*В/РЭ=0-(1100*(-5)/0.2)=27500.

Элементы строки определяются аналогично:

120-1100*0.02/0.2=10, 0.05-0.1*0.02/0.2=0.04,

0.02-0.4*0.02/0.2=-0.02, 0-0.02*1/0.2=-0.1.

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

Выполняя последовательно все этапы алгоритма, формируем план II.

На третьей итерации таблицы 4.2 получаем план III, который является оптимальным, так как все коэффициенты в индексной строке >=0.

Оптимальный план можно записать так:

Алгебраический симплексный метод - student2.ru =(250, 5375, О, О, О, 1875), Алгебраический симплексный метод - student2.ru = 27 625 тыс. руб.

Следовательно, необходимо продавать товаров первой группы А — 250 ед., а второй группы В — 5375 ед. При этом торговое предприятие получает максимальный доход в размере 27 625 тыс. руб. Товары группы С не реализуются. В оптимальном плане среди базисных переменных находится дополнительная переменная Алгебраический симплексный метод - student2.ru . Это указывает на то, что ресурсы третьего вида (площадь складских помещений) недоиспользована на 1875 кв. м, так как переменная Алгебраический симплексный метод - student2.ru была введена в третье ограничение задачи, характеризующее собой использование складских помещений этого ресурса.

В индексной строке оптимального плана в столбцах переменных Алгебраический симплексный метод - student2.ru , Алгебраический симплексный метод - student2.ru , Алгебраический симплексный метод - student2.ru , не вошедших в состав базисных, получены ненулевые элементы, поэтому оптимальный план задачи линейного программирования является единственным.

Пример 2.Рассмотрим применение симплексного метода на примере поставленной задачи анализа коммерческой деятельности предприятия в разделе 2.2.1 и уже полученного решения в разделе 2.4.1 геометрическим методом. Для упрощения процедуры решения оставим условия неотрицательности переменных Алгебраический симплексный метод - student2.ru .

Для построения первого опорного плана систему неравенств преобразуем к системе уравнений путем введения дополнительных балансовых переменных Алгебраический симплексный метод - student2.ru , определяющих объем неиспользованных ресурсов:

Алгебраический симплексный метод - student2.ru

а целевую функцию представим в виде уравнения

Алгебраический симплексный метод - student2.ru .

Полагая, что основные переменные Алгебраический симплексный метод - student2.ru , получим первый опорный план:

Алгебраический симплексный метод - student2.ru = (0; 0; 3; 4; 1,5; 2); F( Алгебраический симплексный метод - student2.ru )=0,

в котором базисные переменные равны:

Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru .

Первый опорный план заносим в симплексную таблицу 2.4.3, который не является оптимальным, поскольку в индексной строке находятся отрицательные коэффициенты (—2) и (—3). Затем, действуя в соответствии с изложенными выше правилами, переходим последовательно от одного плана к другому, пока не построим оптимальный план V, в котором в индексной строке отсутствуют отрицательные элементы. Запишем оптимальный план:

Алгебраический симплексный метод - student2.ru , Алгебраический симплексный метод - student2.ru тыс. руб.

Таким образом, для получения максимального дохода от дневной продажи краски Алгебраический симплексный метод - student2.ru тыс. руб. предприятию необходимо выпускать в сутки Алгебраический симплексный метод - student2.ru т краски наружных работ и Алгебраический симплексный метод - student2.ru т краски для внутренних работ. В оптимальный план вошли дополнительные переменные Алгебраический симплексный метод - student2.ru и Алгебраический симплексный метод - student2.ru ,то свидетельствует о величине недоиспользованных ресурсов третьего и четвертого вида. Следует заметить, что остальные ресурсы использованы полностью, поскольку Алгебраический симплексный метод - student2.ru .

Полученный оптимальный план является невырожденным, так как при расчете столбца Алгебраический симплексный метод - student2.ru отсутствуют одинаковые минимальные значения отношений и все значения базисных переменных в оптимальном плане отличны от нуля. Кроме того, поскольку в индексной строке в столбцах переменных Алгебраический симплексный метод - student2.ru , не вошедших в состав базисных, получены не нулевые элементы, то оптимальный план является единственным.

Пример 3.Рассмотрим решение предыдущей задачи примера 2 с учетом дополнительных ограничений другого вида Алгебраический симплексный метод - student2.ru , тогда получим:

Таблица 2.4.3

План Базисная переменная Значения базисной переменной Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru Алгебраический симплексный метод - student2.ru
I Алгебраический симплексный метод - student2.ru 0.5 +1
Алгебраический симплексный метод - student2.ru 0.5 +1
Алгебраический симплексный метод - student2.ru 1.5 -1 +1 1.5
Алгебраический симплексный метод - student2.ru +1
  Алгебраический симплексный метод - student2.ru -2 -3  
  Алгебраический симплексный метод - student2.ru   - - - - -  
II Алгебраический симплексный метод - student2.ru 2,75 1,5 +1  
Алгебраический симплексный метод - student2.ru 3,5 1,5 +1  
Алгебраический симплексный метод - student2.ru +1  
Алгебраический симплексный метод - student2.ru +1  
Алгебраический симплексный метод - student2.ru -0,25 -1  
Алгебраический симплексный метод - student2.ru 0,5  
  Алгебраический симплексный метод - student2.ru -3  
  Алгебраический симплексный метод - student2.ru   - +3 - - - -  
III Алгебраический симплексный метод - student2.ru 2,375 +1  
Алгебраический симплексный метод - student2.ru 3,125 +1  
Алгебраический симплексный метод - student2.ru +1  
Алгебраический симплексный метод - student2.ru 1,75 +1  
Алгебраический симплексный метод - student2.ru 0,25  
Алгебраический симплексный метод - student2.ru 0,5  
  Алгебраический симплексный метод - student2.ru 1,75  

Задачи

Решите задачи № 1-4 раздела 2.4.1 симплексным методом.

Наши рекомендации