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

Название «симплекс-метод» связано с тем, что он впервые разрабатывался применительно к задачам линейного программирования, в которых допустимое множество представляло собой симплекс:

Другое название симплекс-метода – метод последовательного улучшения плана.

Рассмотрим каноническую задачу линейного программирования:

(2.2.1)

Допустимое множество задачи (2.2.1) может быть задано выражением:

. (2.2.2)

Столбцы матрицы размерности образуют -мерные векторы

,…, ,…, ; (2.2.3)

Условие в (2.2.1), , означает, что Рас-

смотрим множество

, (2.2.4)

т.е. множество, состоящее из индексов при положительных координатах вектора . Тогда

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

Точка называется опорной точкой в задаче (2.2.1), если векторы линейно независимы.

Справедливы следующие утверждения:

1) если в задаче (2.2.1) множество не пусто, то оно имеет опорные точки и число их конечно;

2) если множество решений задачи (2.2.1) не пусто, то оно содержит хотя бы одну опорную точку из множества .

Пример 2.2.1. Найти опорные точки и решение задачи:

Здесь , , ,

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

(2.2.5)

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

Рассмотрим набор . В этом случае система (2.2.5) имеет вид:

– решений нет.

Такой же результат дает рассмотрение наборов . Это означает, что ни один из столбцов матрицы не коллинеарен вектору . Рассмотрим набор . В этом случае система (2.2.5) может быть записана в виде:

и имеет решение

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

Ее решение содержит отрицательное значение, поэтому опорную точку в данном случае сформировать невозможно. Перейдем к рассмотрению набора . Система уравнений типа (2.2.5) в этом случае имеет вид:

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

– дает опорную точку , в которой ;

– не позволяет сформировать опорную точку, так как решение системы уравнений содержит отрицательное значение;

– дает опорную точку , в которой

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

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

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

(2.2.6)

В рассмотренном выше примере 2.2.1 Для вычисления факториала при больших значениях можно воспользоваться приближенным выражением, полученным из формулы Стирлинга:

Тогда, считая значения и также большими, из (2.2.6) получим:

Например, при получим

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

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

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

Опорная точка (см. (2.2.2)) называется невырожденной, если

(2.2.7)

(мощность множества равна ). Если в задаче линейного программирования (2.2.1) все опорные точки невырождены, то задача называется невырожденной. Симплекс-метод будем рассматривать применительно к невырожденным задачам. Вырожденная задача может быть сведена к невырожденной путем алгебраических преобразований.

Пусть – очередная опорная точка, рассчитываемая в соответствии с алгоритмом работы симплекс-метода. Возможен один из трех вариантов:

1) является решением задачи (2.2.1);

2) задача (2.2.1) не имеет решений;

3) рассчитывается следующая опорная точка , причем

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

Поскольку – опорная точка и задача невырождена, столбцы линейно независимы и выполнено (2.2.7). Столбцы образуют базис в . Разложение произвольного вектора по базису имеет вид:

, (2.2.8)

где – коэффициенты разложения.

Введем в рассмотрение величину

(2.2.9)

Здесь – координаты вектора из целевой функции рассматриваемой задачи (2.2.1); – коэффициенты из (2.2.8).

Если , то

(2.2.10)

(2.2.11)

Теорема 2.2.1 (правило оптимальности).

Если то – решение задачи (2.2.1).

Доказательство. Используя (2.2.1), (2.2.3) и (2.2.4), запишем:

(2.2.12)

Последняя сумма в (2.2.12) не содержит нулевых слагаемых. Рассмотрим произвольную точку , где – допустимое множество задачи (2.2.1), определяемое согласно (2.2.2). Эта точка удовлетворяет уравнению

, (2.2.13)

правую часть которого преобразуем следующим образом:

Сравнивая полученное выражение с (2.2.12) и учитывая, что точку можно разложить по базису единственным образом, приходим к выводу о справедливости равенства

(2.2.14)

Подчеркнем, что (2.2.14) справедливо Найдем значение целевой функции в точке :

(2.2.15)

Из условия теоремы, а также из (2.2.9) и (2.2.11) следует:

Подстановка правой части последнего неравенства в (2.2.15) вместо приводит к неравенству

В процессе преобразований использовано выражение (2.2.14). Таким образом, . Следовательно, – решение задачи (2.2.1). Теорема доказана.

Допустим, что условие теоремы 2.2.1 не выполнено, т.е. . По аналогии с (2.2.8) имеем

(2.2.16)

Используя (2.2.16), запишем:

, (2.2.17)

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

(2.2.18)

Используя (2.2.18), преобразуем выражение (2.2.17):

(2.2.19)

Найдем значение целевой функции в точке :

(2.2.20)

Теорема 2.2.2 (правило отсутствия решения у задачи).

Если и если , то задача (2.2.1) не имеет решения.

Доказательство. Рассмотрим вектор , , определенный в соответствии с (2.2.18); , так как , и . Кроме того, согласно (2.2.19), . Таким образом, . Из (2.2.20) следует, что

(2.2.21)

Если задать последовательность значений в виде , то , т.е. все точки будут принадлежать допустимому множеству (2.2.2) задачи, при этом в соответствии с (2.2.21) значения целевой функции будут стремиться к бесконечности:

т.е. максимум не достигается и, следовательно, задача не имеет решения. Теорема доказана.

Теорема 2.2.3.

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

Доказательство. Введем величину , которую определим следующим образом:

(2.2.22)

Отметим, что в силу (2.2.22) и (2.2.4). Подстановка в (2.2.18)

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

Очевидно, что (2.2.19) выполнено. Осталось показать, что . Это следует из (2.2.18) с учетом того, что , а также

Итак, при переходе к очередной опорной точке ее координаты определяются в соответствии с (2.2.18), где в качестве величины используется значение (2.2.22). В этом случае выражение (2.2.18) можно записать в более подробном виде:

(2.2.23)

Рассмотрим множество Очевидно, что Покажем, что векторы образуют базис в пространстве . Произвольный вектор может быть представлен в виде разложения по базису :

(2.2.24)

Согласно (2.2.8), . Отсюда находим:

(2.2.25)

Подставив это выражение в (2.2.24), получим:

, (2.2.26)

где .

Итак, в соответствии с (2.2.26), произвольный вектор выражен через . Следовательно, множество векторов образует базис в пространстве и, таким образом, векторы линейно независимы. Отсюда следует, что точка , координаты которой определяются в соответствии с (2.2.23), является опорной, причем . Теорема доказана.

После определения новой опорной точки и множества формулы (2.2.8) и (2.2.9) приобретают вид:

(2.2.27)

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

Теорема 2.2.4 (связь между параметрами итераций).

справедливы соотношения:

(2.2.28)

(2.2.29)

Доказательство. Используя соотношения (2.2.8) и (2.2.25), выполним следующие преобразования:

(2.2.30)

где

Таким образом, справедливость соотношений (2.2.28) доказана, причем их единственность следует из единственности разложения (2.2.30) вектора по базису .

Перейдем к доказательству соотношения (2.2.29). Запишем:

(2.2.31)

где в соответствии с (2.2.9). Используя полученный результат (2.2.31), а также формулу (2.2.9), преобразуем второе выражение в (2.2.27):

Таким образом, подтверждена справедливость формулы (2.2.29). Теорема

доказана.

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

Пример 2.2.2

Здесь

Первую опорную точку найдем с помощью метода, использованного в примере 2.2.1. Набору соответствует линейно независимая совокупность столбцов . В этом случае система (2.2.5) имеет вид:

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

Таблица 2.2.1 Таблица 2.2.1а

1	0	-3	-3	1
0	1	1	2	1
0	0	-7	-4	-2

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

Аналогично для коэффициентов разложения вектора , также входящего в базис (), получаем , . В соответствии с (2.2.11) . Коэффициенты , находим из системы:

По формуле (2.2.9) вычислим значение :

Определяем значения коэффициентов и :

Находим значение :

Значение целевой функции в рассматриваемой опорной точке :

Анализ табл. 2.2.1а показывает, что выполнены условия теоремы 2.2.3. Для выполнения следующей итерации определим, используя выражение (2.2.22), значения величины и индекса . В таблице имеется два отрицательных значения : и . Можно выбрать любое из них. Выберем , соответственно . В результате просмотра столбца табл. 2.2.1а от значения вверх находим единственное положительное значение . Поэтому в данном случае при определении минимума в (2.2.22) нет альтернативы, следовательно:

Используя (2.2.23), определим координаты следующей опорной точки:

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

Таблица 2.2.2 Таблица 2.2.2а

1	3	0	3	4
0	1	1	2	1
0	7	0	10	5

чения и уже определены. Коэффициенты разложения векторов и по базису, который из них и состоит, можно определить сразу: ; . Соответственно . Разумеется, такие же результаты для этих величин дает применение формул (2.2.28) и (2.2.29), по которым также рассчитаны значения 2-го и 4-го столбцов таблицы:

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

Работая с симплекс-таблицей, можно сократить объем вычислений. Заполнить строку новой таблицы – это значит получить вектор вида

или вида При получении вектора первого вида значения рассчитываются в соответствии с (2.2.28):

при , где , ; при .

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

, где .

Для вычисления значения целевой функции используем формулу (2.2.21), преобразовав ее следующим образом:

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

Пример 2.2.3

Здесь

Для отыскания первой опорной точки рассмотрим набор , которому соответствует линейно независимая совокупность столбцов , . В этом случае система (2.2.5) записывается в виде:

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

Таблица 2.2.3 Таблица 2.2.3а

1	-1	1	0	1
2	1	0	1	3
-4	-3	0	0	-2

Коэффициенты разложения векторов по базису, который из них состоит, записываем сразу: ; . В соответствии с (2.2.11) . Коэффициенты находим из системы:

Используя формулу (2.2.9), найдем значение :

Получим значения :

Находим значение :

Значение целевой функции в рассматриваемой опорной точке : .

Из анализа табл. 2.2.3а следует, что выполнены условия теоремы 2.2.3. В таблице имеется два отрицательных значения : и . Выберем , тогда . В результате просмотра столбца табл. 2.2.3а от значения вверх находим два положительных значения: и . Затем, используя (2.2.22), определяем значение индекса :

Таким образом, используемый на следующей итерации новый базис формируется из старого путем замены столбца (так как ) столбцом (так как ). При этом в новой симплекс-таблице будут представлены коэффициенты разложения векторов () по новому базису. Состав новой симплекс-таблицы отражает табл. 2.2.4, а значения входящих в нее величин – табл. 2.2.4.а. Значения величин в табл. 2.2.4а получены следующим образом.

Таблица 2.2.4 Таблица 2.2.4а

1	-1	1	0	1
0	3	-2	1	1
0	-7	4	0	2

Поскольку , а , первую строку табл. 2.2.4а получаем путем деления первой строки табл. 2.2.3а на число, которое обеспечит получение единицы на -м, т.е. на первом месте новой строки. Это число равно единице, поэтому в данном случае первые строки таблиц 2.2.3а и 2.2.4а совпадают. Вторая строка табл. 2.2.4а получена путем вычитания из второй строки табл. 2.2.3а ее первой строки, умноженной на такое число, которое обеспечивает получение нуля на -м, т.е. на первом месте новой строки. Легко убедиться в том, что это число равно 2. Третья строка табл. 2.2.4а получена путем вычитания из третьей строки табл. 2.2.3а ее первой строки, умноженной на такое число, которое обеспечивает получение нуля на -м, т.е. на первом месте третьей строки новой таблицы. Это число равно –4. Опорная точка, полученная на данной итерации: .

Анализ полученной табл. 2.2.4а показывает, что условия теоремы 2.2.3 выполнены и поэтому возможна очередная итерация. В последней строке таблицы имеется одно отрицательное значение : . Поэтому . В результате просмотра столбца таблицы от значения вверх находим одно положительное значение: . Следовательно, . Поэтому очередной новый базис формируется из предыдущего путем замены столбца (так как ) столбцом (так как ).

Состав величин, характеризующий содержание очередной симплекс-таблицы, отражает табл. 2.2.5. Значения этих величин, представленные в табл. 2.2.5.а, получены следующим образом. Поскольку , а , первая строка табл. 2.2.5а получена путем вычитания из первой строки табл. 2.2.4а ее второй строки, умноженной на такое число, которое обеспечивает получение нуля на -м, т.е. на втором месте новой строки. Это число равно . Вторая строка табл. 2.2.5а получена в результате деления второй строки табл. 2.2.4а на число, обеспечивающее получение единицы на -м, т.е. на втором месте новой строки. Это число равно . Наконец, третья строка табл. 2.2.5а получена путем вычитания из третьей строки табл. 2.2.4а ее второй строки, умноженной на число, при котором обеспечивается получение нуля на -м, т.е. втором месте новой строки. Требуемый результат получается при использовании числа . Опорная точка, по лученная на данной итерации: .