Методическая помощь бизнес-аналитику для изучения случаев вырождения и зацикливания задач линейного программирования

Автор: Дагмирзаев О.А.

Журнал: Экономика и бизнес: теория и практика @economyandbusiness

Статья в выпуске: 8 (90), 2022 года.

Бесплатный доступ

Изучение методики планирования экономических проектов с применением линейных оптимизационных моделей входит в образовательную программу подготовки бизнес-аналитиков. В перечне тем обучения есть и рассмотрение нестандартных ситуаций, которые могут возникнуть в ходе решения линейных моделей, такие как случаи вырождения и зацикливания. Для возникновения вероятности зацикливания задачи сначала должно иметь место её вырождение. У линейных моделей, способных к вырождению, есть внешние признаки. Вырожденность линейной модели не всегда приводит к зацикливанию задачи. Случаи неизбежного зацикливания линейной модели можно избежать путем внесения соответствующих изменений в алгоритм решения задачи. Таким образом: а) от вырожденности задач линейного программирования мы не застрахованы; б) при выявлении высокой вероятности зацикливания вырожденных задач необходимо корректировать алгоритм решения.

Еще

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

Короткий адрес: https://sciup.org/170195341

IDR: 170195341 | DOI: 10.24412/2411-0450-2022-8-103-108

Текст научной статьи Методическая помощь бизнес-аналитику для изучения случаев вырождения и зацикливания задач линейного программирования

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

Основная часть. В данной статье нами рассмотрены явления вырождения и зацикливания задач линейного программирования. Сначала выяснили, что материалы основных литературных источников по линейному программированию [2, 4, 5] адресованы для обучающихся и специалистов с повышенной математической подготовкой. Мы существенно упростили форму изложения заимствованного материала. Надеемся, что подобный подход поможет бизнес-аналитикам с базовым прикладным образованием понять природу вырождения и зацикливания задач линейного программирования.

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

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

Для возникновения вероятности зацикливания линейной модели сначала должно иметь место её вырождение. Попробуем разобраться. Каждый очередной шаг алгоритма симплексного метода предусматривает поиск разрешающего элемента (сначала выбор разрешающего столбца, далее поиск наименьшего отношения свободных членов к соответствующим положительным коэффициентам выбранного столбца). Если выясниться, что одинаковых наименьших отношений больше, чем одно, то после выполнения текущей итерации все свободные члены (за исключением элемента выбранной разрешающей строки) обратятся в нуль. Графическое объяснение случая (для задач с двумя переменными): в одной вершине многоугольника пересекаются более двух прямых, т.е. одна или несколько сторон многоугольника условий (связанных с ограничениями задачи) образуют точку. Это и есть графическое описание ситуации вырождения.

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

Хотя зацикливание встречается редко, но современные компьютерные программы для решения задач линейного программирования должны учитывать данное явление [3, с. 53].

Для иллюстрации явления зацикливания линейной модели выбрали пример [4, с. 147], который описан в книге Саула Гасс «Линейное программирование (методы и приложения)». В рассмотренном примере задача линейного программирования изначально является вырожденной.

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

Еще один момент: из линейной модели, записанной в канонической форме [4, с. 151], восстановили постановку задачи в первоначальном виде:

требуется минимизировать целевую функцию f = - 3/4 х1 + 150 х2 - 1/50 х3 + 6 х4 -> min при соблюдений следующих ограничений: 1/4 х1 - 60 х2 - 1/25 х3 + 9 х4 <= 0

1/2 х 1 - 90 х 2 - 1/50 х 3 + 3 х 4 <= 0

х 3 <= 1

х i >=0, i = 1…4.

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

а) систему ограничений необходимо преобразовать в систему равенств путем добавления трех дополнительных переменных s 1 , s 2 , s 3 :

1/4 х1 - 60 х2 - 1/25 х3 + 9 х4 + s1 =0

1/2 х1 - 90 х2 - 1/50 х3 + 3 х4 + s2

х3 + s3

s j >=0, j = 1…3.

б) целевая функция записывается в виде эквивалентной функции на максимум (поскольку у нас задача минимизации):

f = 3/4 х 1 - 150 х 2 + 1/50 х 3 - 6 х 4 -> max

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

Таблица 1.

Базисные переменные	Небазисные (нулевые) переменные							Решение
Базисные переменные	х 1	х 2	х 3	х 4	s 1	s 2	s 3	Решение
s 1	1/4	-60	-1/25	9	1	0	0	0
s 2	1/2	-90	-1/50	3	0	1	0	0
s 3	0	0	1	0	0	0	1	1
Функция	3/4	-150	1/50	-6	0	0	0	0

В результате симплексных преобразований получается таблица 2.

Таблица 2.

Базисные переменные	Небазисные (нулевые) переменные							Решение
Базисные переменные	s 1	х 2	х 3	х 4	s 1	s 2	s 3	Решение
х 1	1	-240	-4/25	36	4	0	0	0
s 2	0	30	3/50	-15	-2	1	0	0
s 3	0	0	1	0	0	0	1	1
Функция	0	30	7/50	-33	-3	0	0	0

В последующих таблицах выводимые из базиса и включаемые в базис переменные не комментируем.

Таблица 3.

Базисные переменные	Небазисные (нулевые) переменные							Решение
Базисные переменные	s 1	s 2	х 3	х 4	s 1	s 2	s 3	Решение
х 1	1	0	8/25	-84	-12	8	0	0
х 2	0	1	1/500	-1/2	-1/15	1/30	0	0
s 3	0	0	1	0	0	0	1	1
Функция	0	0	2/25	-18	-1	-1	0	0

Таблица 4.

Базисные переменные	Небазисные (нулевые) переменные							Решение
Базисные переменные	s 1	s 2	х 1	х 4	s 1	s 2	s 3	Решение
х 3	25/8	0	1	-525/2	-75/2	25	0	0
х 2	-1/160	1	0	1/40	1/120	-1/60	0	0
s 3	-25/8	0	0	525/2	75/2	-25	1	1
Функция	-1/4	0	0	3	2	-3	0	0

Таблица 5.

Базисные переменные	Небазисные (нулевые) переменные							Решение
Базисные переменные	s 1	s 2	х 1	х 2	s 1	s 2	s 3	Решение
х 3	-125/2	21/2	1	0	50	-150	0	0
х 4	-1/4	40	0	1	1/3	-2/3	0	0
s 3	125/2	-21/2	0	0	-50	150	1	1
Функция	1/2	-120	0	0	1	-1	0	0

Таблица 6.

Базисные переменные	Небазисные (нулевые) переменные							Решение
Базисные переменные	s 1	s 2	х 1	х 2	х 3	s 2	s 3	Решение
s 1	-5/4	210	1/50	0	1	-3	0	0
х 4	1/6	-30	-1/150	1	0	1/3	0	0
s 3	0	0	1	0	0	0	1	1
Функция	7/4	-330	-1/50	0	0	2	0	0

Таблица 7.

Базисные переменные	Небазисные (нулевые) переменные							Решение
Базисные переменные	s 1	s 2	х 1	х 2	х 3	х 4	s 3	Решение
s 1	1/4	-60	-1/25	9	1	0	0	0
s 2	1/2	-90	-1/50	3	0	1	0	0
s 3	0	0	1	0	0	0	1	1
Функция	3/4	-150	1/50	-6	0	0	0	0

В седьмой итерации получается полностью идентичная начальному варианту таблица: а) с одинаковой структурой базисных и небазисных переменных; б) с аналогичными значениями ячеек. Если продолжить вычисления с использованием стандартного алгоритма симплексного метода, то новые таблицы в конечном итоге приведут к варианту, как в таблице 7. Т.е., имеет место зацикливание.

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

Приводим особое правило выбора разрешающей строки в случае вырождения, изложенное в [2]. Если при выборе разрешающей строки имеет место несколько равных минимальных отношений, то:

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

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

Таблица 8.

Базисные переменные	Небазисные (нулевые) переменные							Решение
Базисные переменные	s 1	s 2	х 3	х 4	s 1	s 2	s 3	Решение
х 1	1	0	8/25	-84	-12	8	0	0
х 2	0	1	1/500	-1/2	-1/15	1/30	0	0
s 3	0	0	1	0	0	0	1	1
Функция	0	0	2/25	-18	-1	-1	0	0

Таблица 9.

Базисные переменные	Небазисные (нулевые) переменные							Решение
Базисные переменные	s 1	s 2	х 2	х 4	s 1	s 2	s 3	Решение
х 1	1	-160	0	-4	-4/3	8/3	0	0
х 3	0	500	1	-250	-100/3	50/3	0	0
s 3	0	-500	0	250	100/3	-50/3	1	1
Функция	0	-40	0	2	5/3	-7/3	0	0

Таблица 10.

Базисные переменные	Небазисные (нулевые) переменные							Решение
Базисные переменные	s 1	s 2	х 2	s 3	s 1	s 2	s 3	Решение
х 1	1	-168	0	0	-4/5	12/5	2/125	2/125
х 3	0	0	1	0	0	0	1	1
х 4	0	-2	0	1	2/15	-1/15	1/250	1/250
Функция	0	-36	0	0	7/5	-11/5	-1/125	-1/125

Таблица 11.

Базисные переменные	Небазисные (нулевые) переменные							Решение
Базисные переменные	s 1	s 2	х 2	s 3	х 4	s 2	s 3	Решение
х 1	1	-180	0	6	0	2	1/25	1/25
х 3	0	0	1	0	0	0	1	1
s 1	0	-15	0	15/2	1	-1/2	3/100	3/100
Функция	0	-15	0	-21/2	0	-3/2	-1/20	-1/20

В таблице № 11 достигается оптимум: x 1 = 1/25, x 2 = 0, x 3 = 1, x 4 = 0, значение целевой функции -1/20 (фактическое значение функции будет 1/20). Вывод: в рассмотренном примере применение альтернативной методики выбора разрешающей строки позволило избегать зацикливания в ходе решения задачи.

Существуют и чисто теоретические подходы для защиты от зацикливания, например, в источнике [5, с. 76] анализируется метод возмущения задачи. Идея данного метода проста:

а) путем соответствующего сдвига каждой прямой, слившиеся вершины как бы отклеиваются друг от друга;
б) решается новая, уже невырожденная задача с получением оптимума;
в) сдвинутые прямые возвращаются в

Более краткий обзор случаев вырождения и зацикливания выполнен и в более ранней работе автора данной статьи [6].

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

первоначальное положение.

Список литературы Методическая помощь бизнес-аналитику для изучения случаев вырождения и зацикливания задач линейного программирования

[Электронный ресурс]. - Режим доступа: https://ru.wikipedia.org/wiki/Данциг,_Джордж.
Юдин Д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования. - М.: "Советское радио", 1961. - 494 с.
Банди Б. Основы линейного программирования. - М.: Радио и связь, 1989. - 176 с.
Гасс С. Линейное программирование (методы и приложения). - М.: "Физматгиз", 1961. - 304 с.
Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. - М.: "Наука", 1967. - 460 с.
Дагмирзаев О.А. Нестандартные ситуации при решении задач линейного программирования // Colloquim-journal. - 2019. - №6 (30), часть 1. - С. 10-12.

Статья научная