Тема 18. Решение задачи лп. Симплекс-метод. Понятие об м-методе.

Выше был описан графический способ решения задачи ЛП, основанный на указанном геометрическом представлении области допустимых планов. Для этого потребуется выразить одни переменные через другие. Допустим, в системе ограничений (4.6) число строк не меньше числа переменных (m < n). Тогда m переменных из общего числа переменных n, которые будут выражены через другие переменные, образуют базисные переменные (основные), а остальные (n – m) – свободные переменные (неосновные). [20] Представив систему ограничений в таком виде, возможно выразить все базисные переменные через свободные. Система уравнений (неравенств) ограничений в этом случае будет иметь бесчисленное множество решений, так как свободным переменным можно давать любые значения, для которых определяют базисные. Решение системы называют базисным[21], если все свободные переменные равны нулю.

Указанная геометрическая интерпретация задачи ЛП будет возможна лишь при наличии (n – m) ? 3 числа свободных переменных. Уже при трех переменных наглядное графическое представление существенно усложняется, т. к. в этом случае имеет место многогранник в 3-мерном пространстве, соответствующем объему допустимых значений Х. Для (n – m) > 3, а также больших n оно теряет свою наглядность, а, следовательно, и практическую пользу.

Для решения задачи ЛП существуют более общие методы. Самым часто используемым и наиболее известным из них является симплекс-метод.

Симплекс (от лат. semplex – простой) – это простейший выпуклый многогранник данного числа измерений n. Количество точек вершин, определяющих симплекс, равно (n+1).[22] Симплекс-метод, таким образом, является алгебраической формой решения задачи ЛП, непосредственно вытекающей из приведенного выше геометрического представления.

В его непосредственной форме симплекс-метод предназначен для решения канонической задачи ЛП ((4.5) – (4.6)). [23]

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

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

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

Для этого нужно выразить одни переменные в системе ограничений (4.6) через другие. Система в этом случае примет вид:

х1 = ?4х4 + ?5х5 + ?

х2 = b4х4 + b5х5 + b (4.9)

х3 = g4х4 + g5х5 + g

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

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

Симплекс-метод основан на следующих свойствах задачи ЛП:

1) Не существует локального экстремума, отличного от глобального. Другими словами, если экстремум есть, то он единственный;

2) Множество всех допустимых планов задачи ЛП выпукло;

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

4) Допустимые базисные (опорные) планы совпадают с угловыми точками многогранника решений;

5) Число положительных элементов допустимого базисного решения меньше или равно числу ограничений m;

6) Число угловых точек и число допустимых базисных решений конечно;

7) Число положительных элементов невырожденного (т. е. такого, где число нулевых значений соответствует n – m, а ненулевых значений – m) [24] допустимого базисного решения равно числу ограничений m.

Возможность выразить m базисных переменных через остальные, свободные, существует лишь в случае, если определитель

а1, а12 … а1m

……………… ? 0 .[25] (4.10)

аm1, аm2 … аmm

Если это условие выполняется, то величины х1, х2 , …, хm – базисные, а образуемое ими решение – опорный базисный план. Не вошедшие в базис переменные называются свободными (независимыми). Далее все необходимые преобразования производятся с матрицей коэффициентов системы уравнений ограничений А. С помощью метода Жордана-Гаусса можно найти значения базисных переменных, соответствующих некоторому базисному решению. Для этого коэффициенты при них должны быть равны 1, причем в каждом уравнении системы должна оставаться лишь одна базисная величина (матрица коэффициентов А будет содержать в себе после преобразования единичную подматрицу размера m x n). В преобразуемую матрицу также включается столбец свободных членов. После преобразования она будет выглядеть подобным образом:

1 0 0 a4 a5 a (4.11) 0 1 0 b4 b5 b 0 0 1 g4 g5 g

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

Далее остается определить, является ли допустимый план, соответствующий найденной вершине симплекса, оптимальным.

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

f = d4х4 + d5х5 +d . (4.12)

Тогда возможны три случая: [26]

I. Все коэффициенты при свободных неизвестных в выражении для целевой функции неотрицательны: d4, d5 ? 0. В этом случае базисное решение является оптимальным, – задача решена.

II. Имеется свободная переменная, коэффициент при которой в выражении f отрицателен, а все коэффициенты при этом неизвестном в системе (4.9)

х1 = a4х4 + a5х5 + a

х2 = b4х4 + b5х5 + b

х3 = g4х4 + g5х5 + g

неотрицательны.

В этом случае задача решения не имеет.

III. Имеется свободное неизвестное, коэффициент при котором в f отрицателен, но и среди коэффициентов при этом неизвестном в уравнениях (4.9) также есть отрицательные. В этом случае производится шаг, а именно от базиса Б мы переходим к базису Б? с таким расчетом, чтобы значение fБ приблизилось к оптимуму.

Наиболее естественным путем решения этой задачи был бы сплошной перебор всех вершин области допустимых планов, определение в каждой из них значений переменных хj (j = 1, n) и вычисление по ним в каждой вершине величины целевой функции.

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

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

Описание приведем для (4.9), (4.12), где функцию (4.12) требуется минимизировать при хj? 0 (j = 1, 2, …, 5).

Для заполнения первой таблицы необходимо в каждом из уравнений (4.9) перенести все члены, кроме свободного, из правой части в левую, то есть:

х1 – a4х4 – a5х5 = a

х2 – b4х4 – b5х5 = b (4.13)

х3 – g4х4 – g5х5 = g

Аналогично следует поступить и с (4.12):

f – d4х4 – d5х5 = d . (4.14)

Теперь можно заполнить симплекс-таблицу (табл. 4.2):

Таблица 4.2

?

Базисные переменные х1 х2 х3 х4 х5 Свободные члены ? х1 1 0 0 –a4 –a5 a х2 0 1 0 –b4 –b5 b х3 0 0 1 –g4 –g5 g f 0 0 0 –d4 –d5 d

Нужно, прежде всего, выяснить, имеется ли в первоначальном выражении для

f = d4х4 + d5х5 +d

хотя бы один отрицательный коэффициент при х4 и х5. Поскольку при внесении в таблицу 4.2 коэффициенты d4 и d5 поменяли знаки, то мы должны, следовательно, выяснить, имеются ли в последней строке таблицы (не считая свободного числа d) положительные числа. Если таковых нет, то базисное решение (a, b, g, 0, 0), отвечающее данному базису, является оптимальным, а min f = d – задача решена.

Предположим, что в последней строке имеется, (не считая d) положительное число d4. Отмечаем столбец, в котором оно находится, вертикальной стрелкой. Далее просматриваем остальные числа этого столбца. Если среди них нет положительных чисел (это означает, что a4, b4, g4 ? 0), то мы имеем случай II. Тогда min f = – ?, и процесс снова прекращается.

Пусть, наконец, среди чисел отмеченного столбца, кроме последнего (d4), имеются положительные числа. Это означает, что имеет место случай III, и, следовательно, должно сделать шаг. Например, пусть –a4 > 0, –b4 > 0 (это означает, что a4 < 0, b4 < 0), а –g4 ? 0 (g4 ? 0). В этом случае следует составить отношения

a и b

–a4 –b4

и выбрать из них наименьшее.

Пусть, например, таковым будет отношение , отвечающее строке таблицы с базисной переменной х1. Отметим эту строку горизонтальной стрелкой. Элемент таблицы, стоящий в пересечении отмеченных строки и столбца, называется разрешающим. [27] В данном случае это обведенный в таблице элемент –a4.

С этого момента начинается перестройка таблицы с целью перехода к новому базису {х4 х2 х3}. Элемент –a4 указывает на переменную, которая должна быть введена в базис. Шаг можно осуществить при помощи метода Жордана-Гаусса. А именно: умножить выделенную строку на такое число, чтобы на месте разрешающего элемента появилась единица, а именно на . Это соответствует тому, что первое из уравнений системы (4.13) разрешается относительно новой базисной переменной х4. Полученную таким образом новую строку вписываем уже в новую таблицу снова в виде первой строки. Затем к каждой из остальных строк таблицы 4.2 прибавляем вновь полученную строку, умноженную на такое число, чтобы в клетке отмеченного столбца появился нуль. Этим х4 будет исключена из остальных уравнений, а также из выражения для f. Преобразованные таким образом строки впишем в новую таблицу на место прежних строк. В результате получаем новую таблицу.

К новой таблице применяется та же процедура. В результате или находится оптимальное решение (случай I), или обнаруживается, что min f = –? (случай II), или же производится следующий шаг (случай III). И так далее, пока процесс не остановится.

Этот процесс можно записать в виде следующего алгоритма. [28]

1) Выделяем исходный допустимый базис и заполняем первую таблицу.

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

3) Пусть среди указанных в п. 2 чисел имеется положительное число (скажем, в столбце хj). Отмечаем такой столбец, просматриваем остальные числа этого столбца. Если среди них нет положительных, то min f = – ? – задача решения не имеет. Если их несколько – выбираем наибольшее.

4) Пусть среди просмотренных в п. 3 чисел имеются положительные. Для каждого из таких чисел а составляем отношение , где b – свободный член, являющийся первым числом в той же строке. Из всех таких отношений выбираем наименьшее. Пусть оно соответствует строке базисной переменной хi. Отмечаем эту строку. Число а, стоящее в пересечении отмеченных строки и столбца, есть разрешающий элемент таблицы.

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

6) С новой таблицей возвращаемся к пункту 2.

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

х1 = ?4х4 + ?5х5 + ?,

х2 = b4х4 + b5х5 + b, (4.15)

х3 = g4х4 + g5х5 + g,

а целевая функция – вид y = c0 + с1х1 + с2х2 + с3х3 + с4х4 + с5х5 > min. (4.16)

Чтобы получить такое выражение для целевой функции, в котором у будет выражена только через независимые переменные х4 и х5, следует в равенстве (4.16) заменить х1, х2, х3 выразив их через х4 и х5 (взяв эти выражения из системы (4.9)):

y = c0 + с1(?4х4 + ?5х5 + ?) + с2(b4х4 + b5х5 + b) + с3(g4х4 + g5х5 + g) + с4х4 + с5х5.

После приведение подобных членов получаем:

f = d4х4 + d5х5 +d

где

d4 = с1?4 + с2b4 + с3g4 + с4, d5 = с1?5 + с2b5 + с3g5 + с5, d = c0 + с1? + с2b + с3g.

Обозначим:

= (с1, с2, с3) – вектор коэффициентов при базисных переменных в (4.16);

= (?, b, g) – вектор свободных членов в системе (4.15);

= (?4, b4, g4) – вектор из коэффициентов при х4 в системе (4.15);

= (?5, b5, g5) – вектор из коэффициентов при х5 в системе (4.15).

Тогда предыдущие равенства можно переписать в виде

d4 = ( , ) + с4, d5 = ( , ) + с5, d = c0 + ( , ).

Перепишем формулы в следующем виде:

– d4 = ( , – ) – с4, – d5 = ( , – ) – с5, d = ( , )+ c0,

учитывая, что – это столбец свободных членов из симплекс-таблицы, соответствующей (4.15), – – столбец для неизвестного х4 из той же таблицы, – – столбец для неизвестного х5. Обозначим эти столбцы , , . Тогда

d4 = ( , ) – с4, d5 = ( , ) – с5, (4.17) d = ( , )+ c0,

В этих формулах выражение в скобках – скалярное произведение векторов. Теперь с помощью формул (4.17) можно воспользоваться для заполнения симплекс-таблицы. Над неизвестными х1, …, х5 в заглавии симплекс-таблицы пишут числа с1, …, с5 (коэффициенты из равенства (4.16)), а слева от базисных неизвестных пишут с1, с2, с3 (коэффициенты при базисных переменных из (4.16)). Далее, пользуясь формулами (4.17), заполняют последнюю строку симплекс-таблицы.

Таблица 4.3

с1 с2 с3 с4 с5 с0 Базисные переменные х1 х2 х3 х4 х5 Свободные члены с1 х1 1 0 0 –a4 –a5 a с2 х2 0 1 0 –b4 –b5 b с3 х3 0 0 1 –g4 –g5 g f 0 0 0

Применим этот симплекс-алгоритм для нахождения решения задачи о распределении ресурсов между предприятиями различных типов. В этой задаче n – m = 2, то есть возможно выразить 4 переменные через 2 независимые переменные. Преобразуем исходную систему уравнений так, чтобы приравнивая две переменные нулю (например, х5 и х6), можно было получить значения х1, х2, х3, х4 – координаты одной из вершин симплекса, описывающего область допустимых решений, которые будут являться первоначальным опорным планом – базисом (не обязательно оптимальным). Предварительно надо убедиться, что определитель матрицы, составленной из коэффициентов при базисных переменных в исходных уравнениях, не равен нулю:

4 0 0 1 = –8 ? 0 0 2 0 0 0 0 1 2 4 3 0 0

Следовательно, величины х1, х2, х3, х4 могут являться базисными и система может быть разрешена относительно них.

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

4 0 0 1 0 0 16 0 2 0 0 1 0 10 0 0 1 2 6 0 76 4 3 0 0 0 1 24

Последний столбец матрицы содержит значения свободных членов системы.

Теперь, произведя над этой матрицей ряд элементарных преобразований, нам необходимо привести ее к такому виду, чтобы ее первые четыре столбца (соответствующие переменным х1, х2, х3, х4), если записать их отдельно от остальных, представляли собой единичную матрицу. Элементарные преобразования, которые мы можем произвести над этой матрицей, это:

1) перестановка строк;

2) вычеркивание нулевой строки (если таковая имеется);

3) умножение любой строки на некоторое число ? ? 0;

4) прибавление к одной из строк другой строки, умноженной на любое число.

Начнем с коэффициента при х1. Чтобы сделать его в первом уравнении (первой строке матрицы) равным 1, разделим все элементы первой строки на 4. Затем, чтобы исключить переменную х1 из остальных уравнений системы, нам надо обратить все остальные элементы первого столбца матрицы коэффициентов в нуль. Для этого вычтем из остальных строк матрицы первую строку, умноженную на какое-либо число. Для строк 2 и 3 этот множитель – нуль, для строки 4 – 4. Получим

1 0 0 0 0 4 0 2 0 0 1 0 10 0 0 1 2 6 0 76 0 3 0 –1 0 1 8

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

1 0 0 0 0 4 0 1 0 0 0 5 0 0 1 2 6 0 76 0 0 0 –1 1 –7

Для коэффициентов при переменной х3 таких преобразований проводить не требуется, остаются коэффициенты при переменной х4 в четвертой и остальных строках матрицы:

1 0 0 0 0 1 0 0 0 5 0 0 1 0 3 2 62 0 0 0 1 –1 7

Приравняв переменные х5 и х6 нулю, можем найти значения базисных переменных в начальном опорном плане, которые будут в данном случае равны свободным членам соответствующих уравнений:

х1 = ; х2 = 5; х3 = 62; х4 = 7.

В целевой функции выразим базисные переменные х1, х2, х3, х4 через свободные х5 и х6. Получим

у = –1,3•х5 + 0,6х6 + 21,4,

у + 1,3•х5 – 0,6х6 =21,4.

Занесем данные значения в симплекс-таблицу:

Таблица 4.4

0,4 0,5 0,2 0,8 0,6 0,3 0 Базисные переменные х1 х2 х3 х4 х5 х6 Свободные члены 0,4 х1 1 0 0 0 – 0,5 х2 0 1 0 0 0 5 0,2 х3 0 0 1 0 3 2 62 0,8 х4 0 0 0 1 –1 7 у 0 0 0 0 1,3 –0,6 21,4

Значения, стоящие в последней строке таблицы, были найдены так:

j5 = 0,4 • – – 0,6 = 1,3 ; 0,5 0,2 3 0,8

j6 = 0,4 • – 0,3 = – 0,6 . 0,5 0 0,2 2 0,8 –1

Аналогично находим свободный член в преобразованном выражении целевой функции:

j = 0,4 • – 0 = 21,4 . 0,5 5 0,2 62 0,8 7

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

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

Таблица 4.5

0,4 0,5 0,2 0,8 0,6 0,3 0 Базисные переменные х1 х2 х3 х4 х5 х6 Свободные члены 0,4 х1 1 0 0 0 0 4 0,5 х2 0 1 0 – 0 2 0,2 х3 0 0 1 –2 0 4 48 0,6 х5 0 0 0 1 – 4 у 0 0 0 – 0 15

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

Данный план по сравнению с предыдущим уже дает значительное улучшение значения целевой функции, однако, и он не является оптимальным. В таблице 4.5 отмечены столбец х6, в последней строке которого находится положительное число, и строка х2, которой соответствует наименьше значение отношения свободного члена к положительному значению элемента, находящегося на пересечении столбца х6 и строк таблицы (кроме последней): против . Значит, переменная х6 должна быть введена в базис, а переменная х2 – выведена из базиса. Очередная симплекс-таблица будет выглядеть так:

Таблица 4.6

0,4 0,5 0,2 0,8 0,6 0,3 0 Базисные переменные х1 х2 х3 х4 х5 х6 Свободные члены 0,4 х1 1 0 0 0,25 0 0 4 0,3 х6 0 3 0 –1 0 1 8 0,2 х3 0 –12 1 2 0 0 16 0,6 х5 0 2 0 0 1 0 10 у 0 –0,8 0 –0,6 0 0 13,2

В данной таблице все значения последней строки (кроме стоящего в последнем столбце) меньше нуля, то есть соответствующее этой таблице базисное решение оптимально. Значение целевой функции в данном случае равно 13,2 и является наименьшим. Обратившись к геометрической интерпретации задачи (см. рисунок 4.3), обнаружим, что этому значению целевой функции соответствует уже найденная ранее точка C симплекса ABCDEF.

Во многих задачах исходный допустимый базис может быть выделен непосредственно. Однако, в ряде случаев его приходится искать. Одним из способов нахождения допустимого базиса является метод искусственного базиса или М-метод.[30]

М-метод решения задачи линейного программирования. Пусть дана задача ЛП размерности 3х4 (три уравнения с четырьмя неизвестными):

(4.18) a1x1 + a2x2 + a3x3 + a4x4 + a = 0,

b1x1 + b2x2 + b3x3 + b4x4 + b = 0,

(4.19) c1x1 + c2x2 + c3x3 + c4x4 + c = 0,

(4.20) xj ? 0, j = 1, 2, …, 5,

f = d1x1 + d2x2 + d3x3 + d4x4 + d > max.

Пусть a, b, c ? 0. Если это условие не выполняется, то умножаем обе части соответствующего уравнения на –1.

Наряду с задачей (4.18) – (4.20) (исходной) рассмотрим задачу

(4.21) a1x1 + a2x2 + a3x3 + a4x4 + a = y1,

b1x1 + b2x2 + b3x3 + b4x4 + b = y2,

(4.22) c1x1 + c2x2 + c3x3 + c4x4 + c = y3,

(4.23) xj ? 0, j = 1, 2, …, 5, уi ? 0, i = 1, 2, 3,

f = d1x1 + d2x2 + d3x3 + d4x4 + d – M•y1 – M•y2 – M•y3 > max.

где М – некоторое число.

Сформулированная задача называется М-задачей. В ней неизвестные: x1, x2, …, x4; y1, y2, y3. Неизвестные y1, y2, y3 называют искусственными.

Для решения М-задачи можно воспользоваться симплекс-методом. Исходным допустимым базисом будет базис {y1, y2, y3}.

При этом может возникнуть три ситуации:

1. Если при каком-то достаточно большом значении М , является оптимальным решением М-задачи, при чем все значения искусственных переменных равны нулю, то является оптимальным решением исходной задачи;

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

3. Если М-задача не имеет допустимого решения, то и исходная задача неразрешима.

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

С помощью М-метода решена оптимизационная задача на основе матрицы коэффициентов межотраслевого баланса в теме 6.1.