Симплекс-метод решения канонической задачи линейного программирования

ФГБОУ ВО РГАТУ. Лекции доцента А.Ф.Владимирова Направление подготовки 23.05.01-НТТС. Дисциплина «Математика» Напр. подгот. 23.04.03-ЭТТМК. Дисциплина «Математические методы управления техническим состоянием» Симплекс-метод решения канонической задачи линейного программирования Задачи линейного программирования (ЛП) с целевой функцией и ограничениями в виде нестрогих неравенств сводятся к канонической задаче ЛП добавлением балансовых переменных xn 1 , xn  2 , , xn  m к исходным переменным x1 x2 , , xn : n  L   c j x j  max min ,  j 1  n  (1)   aij x j  xn  i  bi , i  1, m, j  1   x j  0, j  1, n  m.   Знак «+» перед балансовыми переменными ставится для исходного неравенства «≤», знак «–» для неравенства «≥». Величины bi  0 ; c j , aij – постоянные, L – переменная целевой функции. Балансовые переменные со знаком «+» являются базисными, балансовые переменные со знаком «–» базисными не являются в том смысле, что базисные решения с их участием не принадлежат области допустимых решений. Область допустимых решений есть выпуклое линейное m -мерное многообразие (множество)  в той части n  m  -мерного пространства R n  m , в которой значения всех переменных неотрицательны. Главными элементами множества  являются вершины (точки) и соединяющие их рёбра (отрезки прямых). Вершинам соответствуют допустимые базисные решения, для которых значения свободных переменных равны нулю, а значения базисных переменных неотрицательны. Оптимальное решение достигается в одной из вершин множества  . В остальных вершинах достигаются допустимые опорные решения. Число вершин множества  не превышает числа сочетаний n  m ! . Предполагается, что найдено нулевое опорное решение. C nm m  m!n! Симплекс-метод является универсальным аналитическим методом решения канонической задачи ЛП. Он был предложен в 1947 году американским математиком Джорджем Данцигом1 [1]. В нашей стране приоритет в постановке и поисках решения принадлежит Л.В. Канторовичу2, который ещё в 1939 году увидел проблему оптимизации линейных задач в экономике и предложил метод 1 Данциг Джордж Бернард (1914 – 2005) – американский математик. Ему принадлежит термин «Линейное программирование». Его отец, Тобиас Данциг, латвийский математик, учился в Париже у Анри Пуанкаре, эмигрировал в США. 2 Канторович Леонид Витальевич (1912 – 1986) – советский математик, экономист, пионер и создатель линейного программирования, лауреат Нобелевской прими по экономике 1975 года. 1 разрешающих множителей для их решения, который лишь в деталях отличается от симплекс-метода. Суть симплекс-метода состоит в итерационном переходе к другому улучшенному опорному решению, от одной вершины к другой. Наглядно это представляется как движение по ребру, соединяющему соответствующие вершины. При этом за несколько шагов (итераций) достигается оптимальное опорное решение, если оно существует, либо отмечается отсутствие конечного решения задачи ЛП. Симплекс-метод содержит правила оптимального перехода от одного опорного решения к другому. Будем рассматривать неориентированный граф, составленный из вершин и рёбер множества  . Этот многомерный граф можно изобразить на аффинной плоскости Π с учётом того, что точка многомерного пространства на плоскости Π будет точкой, отрезок (ребро) – отрезком (не точкой при подходящем ракурсе). На плоскости Π передаётся параллельность прямых многомерного пространства. Для наглядности изображений введём дополнительные понятия. Часть пространства R n  m с неотрицательными координатами назовём красным углом (red angle) этого пространства. Граф множества  назовём красным графом (red graph) и будем изображать его красным цветом на рисунках. Далее будем оперировать также всеми базисными решениями, значения которых могут быть и отрицательными при равенстве значений свободных переменных нулю. Назовём отрицательные базисные решения синими. Расширим красный граф добавлением синих вершин и синих рёбер, соответствующих переходам из синих базисных решений. Граф, соответствующий всем базисным решениям и переходам между ними, назовём сине-красным графом (blue-red graph). Заметим, что полное число вершин сине-красного графа равно n  m ! , при этом кратность каждой вершины равна m  n . Примеры поC nm m  m!n! строения красных и сине-красных графов базисных решений задач ЛП приведены в нашей статье [2]. Сведения о количестве рёбер графа даны в конце данной лекции. Перепишем задачу (1) для нулевого шага в следующей форме: nm    c j , j  1, n, L   c j0  x j  L0  , L0   0, c j0     j 1 0, j  n  1, n  m,    a ij , j  1, n, n  m 0   0  0  0  (2)  1, j  n  i,   a ij x j  bi , i  1, m, bi  bi , a ij    j 1 0, j  n  1, n  m, j  n  i,    x j  0, j  1, n  m.   При отсутствии допустимого базисного решения (и наличии при этом недопустимого базисного решения) предполагается, что на этом же нулевом шаге после одной или нескольких попыток найдено какое-либо допустимое базисное 2 решение. Геометрически это означает, что из синих вершин по синим рёбрам удаётся попасть в одну из красных вершин. Далее будет рассмотрен алгоритм симплекс-метода. В конце шага с номером k k  1 система (2) будет иметь вид: nm  k  k   L  c j x j  L , j 1  n  m  k  k  (3)   aij x j  bi , i  1, m,  j 1  x j  0, j  1, n  m.   При этом в системе (3) будет m базисных переменных из набора x j , на каждом шаге происходит замена одной из базисных переменных по алгоритму так, что выполнено неравенство Lk 1  Lk  в задаче на максимум и Lk 1  Lk  в задаче на минимум. Эта замена осуществляется процедурой метода Гаусса. Переменная L всегда является базисной, значения постоянных bik   0 . Процедура поиска оптимального решения завершается, если для всех j  1, n  m выполнено неравенство c jk   0 или же c jk   0 . В первом случае найдено максимальное значение целевой функции Lmax  Lk  , а во втором – минимальное значение Lmin  Lk  . Свободные коэффициенты bik   0 на каждом шаге k для каждого ограничения с номером i . Опишем сам алгоритм симплекс-метода, состоящий из пяти пунктов. При этом система (3) представляется расширенной матрицей с верхней L строкой. Столбец для базисной переменной L всегда неизменен, поэтому его можно не писать. Расширенная матрица на каждом шаге представляется в таблице, где перед строками указаны базисные переменные (см. примеры). 1) Пусть для всех номеров j в L -строке выполнены неравенства c jk   0 ( c jk   0 ). Тогда на данных базисных переменных при равенстве свободных переменных нулю достигнуто максимальное (минимальное) значение целевой функции Lmax  Lk  ( Lmin  Lk  ). Задача решена. 2) Пусть для некоторого номера j в L -строке выполнены неравенства c jk   0 ( c jk   0 ). При этом для элементов j -го столбца и для всех i выполнено неравенство aijk   0 . Тогда значение целевой функции не ограничено сверху (снизу) и Lmax   ( Lmin   ). Задача не имеет решения. 3) Пусть для некоторого номера j в L -строке выполнены неравенства c jk   0 ( c jk   0 ). При этом для некоторых элементов j -го столбца, т.е. для некоторых i , выполнено неравенство aijk   0 . Тогда значение целевой функции Lmax ( Lmin ) не достигнуто, и следует сделать очередной шаг итерации. 3 4) Выделенный j -й столбец называем разрешающим. Для всех aijk   0 в разрешающем столбце находим так называемое симплексное отношение bik  . aijk  Выбираем i -ю строку с минимальным симплексным отношением и называем её разрешающей. Заменяем базисную переменную разрешающей строки новой базисной переменной x j . Прежняя базисная переменная переходит в разряд свободных. 5) Коэффициент на пересечении разрешающего столбца и разрешающей строки – разрешающий элемент – делаем равным 1. Остальные элементы разрешающего столбца процедурой метода Гаусса делаем равными 0, включая элемент L -строки. Возвращаемся к пункту 1. Пример 1. Решить симплекс-методом задачу:  L  3 x1  2 x2  max,  2 x1  x2  12,  x1  x2  7,   x1  3 x2  15,   x1 , x2  0. Решение примера 1. Сделаем задачу канонической, вводя балансовые переменные x3 , x4 , x5 . Перепишем её в форме (2) для решения по алгоритму:  0,  L  3 x1  2 x2  2 x1  x2  x 3  12,  x1  x2  x4  7,   x1  3 x2  x5  15,   x1 , x2 , x3 , x4 , x5  0. Составим симплексную таблицу, в которой балансовые переменные x3 , x4 , x5 сначала являются базисными (смотрите таблицу 1). Действуем по алгоритму для максимума: Итерация 1. 1) Коэффициенты в L -строке отрицательны, решение не завершено. 2) Нет столбца со всеми неположительными коэффициентами, задача может иметь решение. 3) Выполнено условие положительности коэффициентов для столбца 1. Выделяем его (серым цветом). Переменная x1 становится базисной. 4) Для трёх строк находим симплексные отношения и выделяем строку 1 с минимальным отношением, равным 6. Переменная x3 переводится из базисных переменных в свободные. 5) Умножаем разрешающую строку 1 на число ½ и помещаем результат во второй строке следующей части таблицы. Умножаем эту строку последовательно на (-1), (-1) и 3 и прибавляем результаты соответственно к 3-ей строке, 2-ой строке и L -строке таблицы первой итерации. Результаты действий помещаем в соответствующие строки таблицы для второй итерации с базисными переменными x1 , x4 , x5 . 4 Итерация 2. 1) Коэффициент перед x2 в L -строке отрицателен, решение не завершено. 2) Коэффициенты второго столбца положительны, задача может иметь решение. 3) Выполнено условие положительности коэффициентов для столбца 2. Выделяем его. Переменная x2 становится базисной. 4) Для трёх строк находим симплексные отношения и выделяем строку 2 с минимальным отношением, равным 2. Переменная x4 переводится из базисных переменных в свободные. 5) Умножаем разрешающую строку 2 на число 2 и помещаем результат во второй строке следующей части таблицы. Умножаем эту строку последовательно на (-5/2), (-½), ½ и прибавляем результаты соответственно к 3-ей строке, 1-ой строке и L -строке таблицы второй итерации. Результаты действий помещаем в соответствующие строки следующей части таблицы с базисными переменными x1 , x2 , x5 . Итерация 3. 1) Коэффициенты в L -строке неотрицательны, решение завершено. Видим, что Lmax  x1 , x2   L5, 2   19 . 12 7 15 L x1 x4 x5 18 6 1 9 19 5 2 4 L x1 x2 x5 x1 x2 x4 x5 -3 -2 2 1 1 1 1 1 3 0 -1/2 3/2 1 1/2 1/2 0 1/2 -1/2 0 5/2 -1/2 1 1 1 1 1 1 -1 2 -5 1 1 x3 1 1 -1 2 Процедура метода Гаусса Симплексное отношение bik  aijk  1/2 -1/2 -1/2 3/2 2 -5 -1 1 6 7 15 12 2 18/5 Итерация 1 L x3 x4 x5 Матрица коэффициентов при всех переменных Итерация 2 Базисные переменные Значения базисных переменных Таблица 1. Симплексная таблица решения задачи примера 1. Lmax  x1 , x2   L5, 2   19 Решение завершено на первом пункте третьей итерации Пример 2. Решить симплекс-методом задачу:  L  6 x1  4 x 2  min,  x1  3 x 2  9,  2 x1  x 2  8,   6 x1  x 2  12,   x1 , x 2  0. 5 Решение примера 2. Сделаем задачу канонической, введя балансовые переменные x3 , x4 , x5 , переписав её в форме (2) для решения по алгоритму:  0,  L  6 x1  4 x2  x1  3 x2  x 3  9,   x4  8,  2 x1  x2  6x  x  x5  12, 1 2   x1 , x2 , x3 , x4 , x5  0. Составим симплексную таблицу, в которой балансовые переменные x3 , x4 , x5 сначала не являются базисными (смотрите таблицу 2). Поэтому сначала ищем базисные переменные в два этапа. Затем действуем по алгоритму для минимума, завершая задачу на второй итерации: Lmin  x1 , x2   L3, 2   26 . Комментарии опускаем. Знач.баз. перемен. L 9 8 12 нет нет нет L x1 - x4 - x5 L x1 x4 x5 L x1 x2 x5 54 9 -10 -42 54 9 10 42 26 3 2 8 Матрица коэффициентов при Процедура метода Гаусса всех переменных x1 -6 1 2 6 x2 -4 3 1 1 x3 -1 x4 -1 x5 -1 1 1 14 3 -5 -17 14 3 5 17 -6 -1 2 6 -6 -1 -2 -6 -1 1 -1 1 1 1 -2/5 -14/5 1/5 -3/5 -2/5 1/5 4/5 -17/5 1 6 -2 -3/5 aijk  Делаем x1 базисной переменной -6 Делаем x4 , x5 базисными переменными   1   1 :5 Симпл.отнош. bik  -17/5 -14/5 3 2 42/17 Итерация 1 Базисн. перемен. Таблица 2. Симплексная таблица решения задачи примера 2. Lmin  x1 , x2   L3, 2   26 Решение за- вершено на первом пункте второй итерации Возвращаясь к сине красным графам, отметим, что их можно отнести к геометрическим графам, теория которых дана в учебном пособии [3]. Выделим два положения из этой книги. 6 1) На странице 25 [3] утверждается: «Оказывается, что для геометрической реализации любого конечного графа, или графа со счётным числом вершин и рёбер, вполне достаточно трёхмерного пространства». Другими словами, граф из пространства R n  m может быть изображён в трёхмерном пространстве без пересечения рёбер графа. 2) Пусть V – множество вершин, E – множество рёбер графа. На странице 18 [3] приведена формула, связывающая кратность вершин   xi  , x i  V с числом рёбер графа E :    xi   2 E . Тогда для сине-красного графа выполнено равенство xi V m mn  C m  n  2 E , откуда следует формула для количества рёбер m  n ! . сине красного графа: E  2  m  1! n  1! Библиографический список 1. Данциг, Дж. Линейное программирование, его применения и обобщения [Текст] / Дж. Данциг; пер. с англ. Г.Н. Андрианова, Л.И. Горькова, А.А. Корбута, А.Н. Ляпунова; общ. ред. и предисловие Н.Н. Воробьева. – М.: Изд-во «Прогресс», 1966. – 600 с. 2. Владимиров, А.Ф. Плоскостное изображение графа всех базисных решений и подграфа допустимых базисных решений задачи линейного программирования [Текст] / А.Ф. Владимиров // Принципы и технологии экологизации производства в сельском, лесном и рыбном хозяйстве: Материалы 68-ой международной научно-практической конференции 26-27 апреля 2017 года. – Часть 3. – Рязань: Издательство Рязанского государственного агротехнологического университета, 2017. – С.397-403. 3. Клековкин, Г.А. Геометрическая теория графов: учеб. пособие для академического бакалавриата / Г.А. Клековкин, Л.П. Коннова, В.В. Коннов. – 2-е изд., испр. и доп. – М.: Издательство Юрайт, 2017. – 240 с. 7