Санкт-Петербургский государственный университет
Направление: Математика, Механика
Специализация: Алгебра
Афанасьева Ольга Анатольевна
Точный симплекс-метод при целочисленных исходных данных
Дипломная работа
Научный руководитель:
кандидат физ-мат. наук, доцент
Агафонова И.В.
Рецензент:
кандидат физ.-мат. наук, доцент
Дмитриева О.M.
Санкт-Петербург
2016
SAINT-PETERSBURG STATE UNIVERSITY
Main Field of Study: Mathematics, Mechanics
Area of Specialisation: Algebra
Olga Afanaseva Anatolievna
Precise simplex-method under integer initial data
Graduation Thesis
Scientific supervisor:
Candidate of Physico-Mathematical Sciences, Docent
Agafonova I. V.
Reviewer:
Candidate of Physico-Mathematical Sciences, Docent
Dmitrieva O.M.
Saint-Petersburg
2016
Содержание
Основные обозначения
2
Введение
3
1 Q1.1
1.2
1.3
4
4
6
8
матрицы и действия с ними
Определение Q - матриц и их свойства . . . . . . . . . . . . . . . . . . .
Q - поворот с ведущим элементом . . . . . . . . . . . . . . . . . . . . . .
Q - матрица и присоединенная матрица . . . . . . . . . . . . . . . . . .
2 Целочисленная модификация симплекс-метода
10
2.1 Постановка задачи и основные обозначения . . . . . . . . . . . . . . . . 10
2.2 Описание алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Решение систем линейных уравнений без операции деления
14
3.1 Целочисленный метод решения систем линейных уравнений и целочисленный метод нахождения присоединенной матрицы . . . . . . . . . . . 14
3.2 Применение Q - матриц к решению систем линейных уравнений . . . . 17
4 Программная реализация алгоритмов решения задач
20
Заключение
26
Список литературы
27
Приложение 1 Примеры решения задач ЛП целочисленным симплексметодом
28
Приложение 2 Примеры решения системы линейных уравнений без
операции деления и нахождения присоединенной матрицы без операции деления
39
Приложение 3 Пример решения системы линейных уравнений точным
симплекс-методом
42
1
Основные обозначения
Q — множество рациональных чисел,
M и N — индексные множества, M = 1 : m, N = 1 : n,
A = A[M, N ] — матрица с элементами A[i, j],i ∈ M , j ∈ N ,
x = x[N ] — вектор-столбец переменных,
b = b[M ] — столбец свободных членов,
cT = cT [N ] — вектор-строка коэффициентов,
I = I[N, N ] — единичная матрица,
Aj = Aj [M ] = A[M, j] — j-ый столбец матрицы A[M, N ].
2
Введение
Решение задач линейного программирования или ЛП стандартным симплексметодом на каждом шаге приводит к вычислениям с действительными числами. Таким образом, на каждом шаге теряется точность, кроме того такие вычисления требуют больших затрат памяти компьютера. Одна из модификаций симплекс-метода
связана с тем, чтобы промежуточные вычисления на каждом шаге были целочисленные. Это стало возможным благодаря Q - матрицам. Q - матрицы, введенные Дж.
Эдмонсом [4], позволяют достаточно легко пройти различные шаги симплекс-метода
и использовать в решении системы линейных уравнений вместо действительных чисел целые.
В данной работе будет описан алгоритм симплекс-метода с целочисленными промежуточными вычислениями с применением Q - матриц.
Для достижения результата выполнения работы необходимо:
1. Поставить алгоритм решения задач линейного программирования модифицированным симплекс-методом с применением Q - матриц.
2. Реализовать алгоритм в виде компьютерной программы и протестировать ее
на различных примерах.
3. Использовать аналогичный алгоритм без операции деления для нахождения
решения систем линейных уравнений.
4. Реализовать алгоритм решения систем уравнений в кольце целых чисел в виде
компьютерной программы.
3
1
Q - матрицы и действия с ними
1.1
Определение Q - матриц и их свойства
Основой данной работы явлется определенный вид матриц. Элементы таких матриц зависят от соответствующих базисных матриц.
Введем понятие.
Определение. Q - матрица для некоторого базиса B матрицы A — это матрица
с элементами {qij }:
qij = det AB\{i}∪{j} ,
(1)
det AB 6= 0.
Обозначается Q(A, B).
По построению, Q - матрица состоит из определителей, поэтому если коэффициенты Q - матрицы целые, тогда и определитель всей матрицы тоже целый.
Свойство 1. Если для некоторого базиса B элементы матрицы A – целые числа,
то и элементы Q(A, B) – целые числа.
Если возьмем j ∈ B и i 6= j, то det AB\{i}∪{j} = 0, так как базисная матрица в этом
случае содержит два одинаковых столбца.
Если j ∈ B и i = j, то det AB\{i}∪{i} = det AB .
Пример вычисления Q - матрицы:
5 9 1 −2 0 7 0
A = 4 1 0 2 1 6 0 ,
6 3 0 3 0 1 1
Найти Q(A, {1, 2, 4}).
5 9 −2
B = {1, 2, 4} ⇒ AB = 4 1 2 .
6 3 3
Первый элемент первой строки:
q11
5 9 −2
= det 4 1 2 = −27,
6 3 3
Второй элемент первой строки:
q12
9 9 −2
= det 1 1 2 = 0,
3 3 3
4
так как первый и второй столбцы совпадают, тогда по свойству 1 определитель равен
0, об этом писали выше.
Третий элемент первой строки равен определителю матрицы AB\{i}∪{3} , полученной заменой первого столбца базисной матрицы на третий столбец матрицы A:
1 9 −2
q13 = det 0 1 2 = −3.
0 3 3
Аналогично, находятся другие элементы Q - матрицы:
−27 0 −3 0 −33 −199 20
0
27
144 −18 .
Q(A, {1, 2, 4}) = 0 −27 0
0
0
6 −27 39
245 −31
Следствие:
Каждая Q - матрица имеет подматрицу с диагональныии элементами равными
det(AB ) и
Q(A, B)B = det(AB ) × I.
Свойство 2. Если AB –единичная, то Q(A, B) = A.
Тривиально , если AB = I, тогда det(AB\{i}∪{j} ) = aij , AB\{i}∪{j} – единичная диагональная матрица за исключением столбца i.
Вернемся к примеру.
Пусть AB = I, B = {3, 5, 7}, получим нам уже знакомую матрицу:
5 9 1 −2 0 7 0
A = Q(A, {3, 5, 7}) = 4 1 0 2 1 6 0 .
6 3 0 3 0 1 1
5
1.2
Q - поворот с ведущим элементом
В этом разделе будут рассмотрены вычисления над Q - матрицами. Их в дальнейшем мы будем использовать для пересчета одного шага точного симплекс-метода.
Определение. Если B 0 получается из B заменой r - столбца столбцом c матрицы
A, то переход от матрицы Q = Q(A, B) к матрице Q0 = Q(A, B 0 ) осуществляется с
помощью одной итерации Q - поворота с ведущим элементом qrc :
qij0 =
qij qrc − qic qrj
,
det(AB )
qij0 = qij ,
i 6= r;
(2)
i = r.
Обозначение: Q(A, B) (r, c).
Строка r должна быть переименована в c.
По построению можем видеть, что qrc = det(AB\{r}∪{c} ) = det(AB 0 ) и qrc – определитель нового базиса Q0 . Можно заметить, что qrc будет общим делителем для
следующего преобразования.
Пример:
Пусть
A=
1 3 1
.
2 4 0
Известно, что
Q(A, {2, 3}) =
−2 −4 0
3 1
, B = {2, 3}, AB =
.
2
0 4
4 0
Пусть B 0 = {1, 3} получается заменой первого столбца базисной матрицы первым
столбцом матрицы A. Тогда переход к матрице Q(A, B 0 ) осуществим с помощью одной итерации по формуле:
(
qij q11 −qi1 q1j
, i 6= 1
0
det AB
,
qij =
qij ,
i=1
причем
det(AB 0 ) = q12 .
Первая строка не меняется. Пересчитаем элементы второй строки по формуле:
0
q2j
=
q2j q11 − q21 q1j
, j = 1, 2, 3.
det AB
0
j = 1 : q21
= 0;
0
j = 2 : q22
= −2;
0
j = 3 : q23
= −2.
6
Тогда
0
Q(A, B ) =
−2 −4 0
,
0 −2 −2
Определитель новой базисной матрицы равен q11 = −2.
Q - поворот, называемый также Q - преобразованием, дает матрицу той же размерности, что и исходная. Вычисления проводятся только с целыми числами. В результате мы получаем новую Q - матрицу с новым базисом и значением определителя
этого базиса.
Согласно Дж Энмондсу [4] вычислительная сложность одной итерации Q - преобразования составляет O(n2 ).
7
1.3
Q - матрица и присоединенная матрица
В модифицированном симплекс-методе при вычислении табличных значений используется обратная базисная матрица. В нашем случае мы ее обозначили A−1
B . Но
если AB - матрица с целочисленными элементами, то это не означает что обратная
ей также будет целой. Мы не можем использовать обратную матрицу, но можем ее
заменить присоединенной.
Определение. Присоединенная матрица — это матрица, составленная из алгебраических дополнений для соответствующих элементов исходной матрицы. ОбознаeB .
чение A
Так как алгебраические дополнения — это определители подматриц размера (m−
1) × (m − 1) и детерминант представляет собой сумму элементов матрицы, то присоединенная матрица матрицы с целочисленными элементами также будет целочисленной со следующими свойствами:
eB = det AB · A−1 ,
A
B
(3)
Можно установить связь Q - матрицы и обратной матрицы:
Q(A, B) = det AB A−1
B A
Пусть имеется базис B и определим базис B 0 = B ∪ {j} \ {s}, j ∈
/ B, s ∈ B.
Обозначим:
z = z[B] = Λj = A−1
B Aj
По выбору s выполняется z(s) > 0.
1
0 ···
0
1 ···
··· ··· ···
F = F [B, B 0 ] =
0
0 ···
· · · · · · · · ·
0
0 ···
z[•] 0 · · · 0
z[•] 0 · · · 0
· · · · · · · · · · · ·
−
z[s] 0 · · · 0
· · · · · · · · · · · ·
z[•] 0 · · · 1
матрица со столбцами Fj = z и Fp = Ip при p ∈ B, p 6= j.
F [s, j] = z[s] > 0.
При умножении базисной матрицы на F получим:
AB Fj = AB z = Aj ,
AB Fp = ABp , p ∈
/ j,
AB 0 = AB F.
8
(4)
Если взять определитель от левой и правой части получим равенство:
det AB 0 = det AB z[s].
Отсюда приходим к равенству:
Q(A, B) = det AB A−1
B A,
либо
eB · A.
Q(A, B) = A
(5)
Пример:
1 0
1 0
−1
AB =
⇒ AB =
,
2 4
− 12 41
тогда
eB =
A
4 0
.
−2 1
Метод вычисления присоединенной матрицы схож с методом нахождения обратной матрицы, только в случае присоединенной используется Q - преобразование вместо преобразования Гаусса.
Приведем пример вычисления присоединенной матрицы через Q - матрицу:
1 0
AB =
.
2 4
Записываем расширенную матрицу:
1 0 1 0
[AB |I] =
.
2 4 0 1
По свойству Q - матрицы:
4 0
Q(A, B)B = det AB × I =
.
0 4
Остальные компоненты:
1
q13 = det
0
1
q23 = det
2
0
0
= 4, q14 = det
4
1
1
1
= −2, q24 = det
0
2
0
= 0,
4
0
=1
1
Q - матрица расширенной системы:
4 0 4 0
4 0
e
Q([AB |I]) =
⇒ AB =
.
0 4 −2 1
−2 1
Тривиально, выполнив обратное действие по формуле (5), получим пример вычисления Q - матрицы через присоединенную и матрицу Q([AB |I]) из предыдущего
примера.
9
2
Целочисленная модификация симплекс-метода
2.1
Постановка задачи и основные обозначения
Рассматривается адача ЛП в канонической форме:
f (x) = cT x → min,
Ax = b,
x ≥ 0.
(6)
(7)
(8)
Предполагаем, что rank(A) = m.
Каноническая задача (6)–(8) равносильна следующей:
cT x → min,
Ax − w = 0,
w = b, x ≥ 0,
(9)
где w – вектор искусственных переменных. Такая запись c равной нулю правой частью ограничений требуется для применения алгоритма с Q-матрицами.
Для построения начального базисного плана задачи (9) решается задача:
X
−
wj → min,
(10)
j∈M
Ax − w = 0,
w ≤ b, x ≥ 0.
Метод рассматривается применительно к задачам вида:
cx → min,
Ax = 0,
l ≤ x ≤ u.
(11)
(12)
(13)
Пусть
B — множество индексов базисных переменных,
H — множество индексов небазисных переменных,
H = N \ B.
Базисным решением или базисным планом задачи (11)–(13) называется вектор
x[N ] системы (12), такой, что выполняются ограничения (13). Каждая небазисная
переменная xk равна либо нижней границе lk , либо верхней границе uk .
10
2.2
Описание алгоритма
Обозначение:
xB = x[B],
xH = x[H].
Систему ограничений (12) можно переписать в виде
AB xB + AH xH = 0,
откуда получаем базисное решение системы
xB = −A−1
B AH xH .
(14)
u = cB A−1
B ,
∆[H] = cB A−1
B A H − cH ,
(15)
(16)
Определим
где ∆[H] – оценка небазисных переменных, которая определяет, какую переменную
можно ввести в базис. Перепишем выражения в целочисленных значениях, для этого
введем обозначения
D = | det AB |,
e+ = A
eB · sign(det AB ).
A
B
Для приведения к целочисленному виду нужно умножить левую и правую часть
(14), (15), (16) на D, и в правой части обратную матрицу заменить на присоединенную матрицу со знаком определителя базисной матрицы:
e+ AH xH ,
x
eB = −A
B
u
e = cB A+
B,
e = cB A
e+ Aj − c[j] · D.
∆[j]
B
Подготовка к описанию шагов алгоритма:
Если все данные задачи принадлежат кольцу целых чисел, то можно приступать к
первому шагу.
Если числа рациональные, то приводим их очевидными преобразованиями, о которых говорится в статье [1], к целому виду и переходим к Шагу 1.
Шаг 1.
Вычисление оценок небазисных переменных:
e = cB A
e+ Aj − c[j] · D.
∆[j]
B
11
Шаг 2.
Проверка условий оптимальности.
План оптимален (для случая detAB > 0), если :
e ≤ 0 для всех небазисных xj = lj ,
• ∆[j]
e ≥ 0 для всех небазисных xj = uj .
• ∆[j]
e противоположны.
Для случая detAB < 0 знаки неравенств ∆[j]
Если условия оптимальности не выполнены, соответствующую переменную xj
вводим в базис. В том случае, когда переменных, которые не удовлетворяют условию
оптимальности, несколько, берут для ввода в базис переменную с максимальной по
модулю оценкой.
Шаг 3.
e+ Aj .
Вычислить вектор ze = ze(j) = A
B
Шаг 4.
e 1, Θ
e 2:
Вычислить Θ
e <0
∆[j]
e >0
∆[j]
Dli − Dxi
|e
z[i] < 0
i
ze[i]
Du
−
Dx
i
i
e 2 := min
Θ
|e
z[i] > 0
i
ze[i]
Dxi − Dli
|e
z[i] > 0
i
ze[i]
Dx
−
Du
i
i
e 2 := min
Θ
|e
z[i] < 0
i
ze[i]
e 1 := min
Θ
e 1 := min
Θ
Положить
e := min{uj − lj ; Θ
e 1; Θ
e 2 }.
Θ
e = +∞, то целевая функция не ограничена на множестве планов, оста• Если Θ
новка алгоритма.
e 6= +∞.
Предполагаем, что Θ
• Пусть i — индекс, на котором достигается минимум на шаге 4:
e = uj − lj базис не меняется и xj меняет значение с lj на uj ,
– В случае Θ
либо с uj на lj ,
e =Θ
e 1 переменная xi выходит из базиса и принимает значение
– В случае Θ
li ,
e =Θ
e 2 переменная xi выходит из базиса и принимает значение ui .
– В случае Θ
12
Шаг 5.
Пересчет компонент базисного плана xB :
e+ AH xH .
D · xB = −A
B
Шаг 6.
Составляем матрицу [AB |I|Aj ], которая состоит из трех подматриц.
Считаем для нее Q-матрицу:
eB |e
Q([AB |I|Aj ], B) = [detAB × I|A
z ].
Ее частью является присоединенная матрица.
Вычисляем Q-преобразование согласно [2] для полученной Q-матрицы:
. e ..
eB |e
[detAB × I|A
z ] (j, i) = [ . . |A
B 0 |.].
Каждая итерация точного СМ аналогична итерациям модифицированного симплексметода [3] с некоторыми изменениями.
Для записи итераций используем следующую таблицу:
f (e
x)
e
cB A +
B
e
∆[j]
x
e
e+
A
B
e+ Aj
A
B
В Приложении 1 приведены подробные примеры решения задач.
Вычислительная сложность рассмотренного алгоритма полиномиальна [6]. В сравнении с модифицированным симплекс-методом, компьютерная программа затрачивает больше времени на подсчет результатов точного модифицированного симплексметода. Но, поскольку большой вклад вносят целые вычисления, увеличивается точность подсчетов.
13
3
Решение систем линейных уравнений без операции деления
3.1
Целочисленный метод решения систем линейных уравнений и целочисленный метод нахождения присоединенной
матрицы
Рассмотрим систему линейных уравнений
Ax = b,
(17)
где A, b принадлежат кольцу целых чисел,
матрица A – квадратная матрица размерности m × m.
Систему (17) будем записывать с помощью расширенной матрицы :
[A|b].
(18)
Для удобства обозначим Am+1 = b и перепишем расширенную матрицу размерности m × (m + 1):
[A|Am+1 ] = {aij },
i = 1 : m, j = 1 : m + 1.
(19)
Алгоритм решения систем без операции деления
Обозначим C = [A|Am+1 ].
Предполагаем, что akk 6= 0, k = 1 : m.
Прямой ход.
1. Умножаем каждую строку расширенной матрицы C = C1 с номером i, i ≥ 2 на
a11 и вычитаем из нее первую строку, умноженную на ai1 . После преобразований
приходим к матрице C2 .
2. Пусть на предыдущем шаге получена матрица Ck , k = 2 : m − 1. Умножаем
каждую строку с номером i, i ≥ k +1 на akk и вычитаем из нее строку с номером
k, умноженную на aik . Делаем сокращение элементов строк k + 1 : n на ak−1,k−1
и приходим к матрице Ck+1 .
3. После прохождения (m−1)-го шага приходим к треугольной матрице Cm . В последней строке матрицы Cm находятся два не равных нулю элемента: amm = |A|
и am,m+1 = |m A|. Матрица m A получается из A заменой m-ого столбца столбцом
свободных членов Am+1 , а |A|, |m A| - обозначение определителей матриц A, m A
соответственно.
14
Обратный ход.
1. Пусть известны определители |m A|, |m+1 A|, ..., |k+1 A|, k = 1 : m − 1, тогда, используя элементы матрицы Cm , найдем |k A| по формуле
!
.
X
|k A| = |A|ak,m+1 −
|j A|akj
akk ,
(20)
j=k+1
дробная черта означает операцию деления нацело.
2. Решение системы находим по формулам Крамера:
xi =
|i A|
,
|A|
i = 1 : m.
Особенность этого метода состоит в том, что все элементы матрицы Ck на k-ом
шаге можно сократить на ведущий элемент и получить матрицу Ck+1 , что, согласно
статье [7], не нарушает целостности элементов матрицы.
Мы рассмотрели адаптацию алгоритма Гаусса, алгоритм решения системы уравнений в кольце целых чисел. В нем задействованы только операции сложения, вычитания и умножения. Поэтому на каждом этапе решения данный метод имеет точные
вычисления. Использование операции сокращения приводит к тому, что разрядность
элементов матрицы не возрастает. Вычислительная точность метода такая же, как
у алгоритма Гаусса [7].
Точный алгоритм решения систем линейных уравнений применяется главным образом для нахождения присоединенной матрицы, только вместо правой части мы
записываем справа единичную матрицу того же размера, что и исходная матрица.
Алгоритм нахождения присоединенной матрицы.
Систему линейных уравнений по статье [7] запишем в виде:
AP = |A|I,
где используем обозначения
A = {aij }, i = 1 : m, j = 1 : m, – квадратная матрица,
P = {pij }, i = 1 : m, j = 1 : m – присоединенная матрица для A.
Обозначим C = [A|I].
Прямой ход.
15
(21)
По аналогии с Прямым ходом алгоритма точного решения систем линейных уравнений преобразуем расширенную матрицу системы C.
В результате прямого хода получим матрицу, у которой все элементы ниже главной диагонали и выше последней диагонали равны нулю, а ненулевые элементы в
последней строке строке определяются по формуле:
ann = |A|,
an,n+j = pnj ,
j=1:m
Обратный ход:
Недостающие элементы присоединенной матрицы вычисляются по формуле:
!
.
X
pkj = |A|ak,n+j −
pij aki
akk , j = 1 : m.
(22)
j=k+1
Количество операций, необходимое для данного алгоритма нахождения присоединенной матрицы, имеет тот же порядок, что и для алгоритма Гаусса [7].
В Приложении 2 описаны примеры решения систем линейных уравнений без операции деления и нахождения присоединенной матрицы без операции деления.
16
3.2
Применение Q - матриц к решению систем линейных уравнений
В Главе 2.3 приведен алгоритм целочисленного симплекс-метода. Он решается в
два этапа: построение искусственного базиса и исключение вспомогательных переменных, и решение основной задачи.
Изучив точный алгоритм симплекс-метода и точный метод решения систем линейных уравнений, приходим к выводу, что можно переформулировать задачу решения
систем уравнений как задачу линейного программирования и получить решение с
помощью целочисленного симплекс-метода в один этап.
Запишем задачу
f (x) = 0x → min,
Ax = b.
(23)
(24)
(25)
Здесь, A – невырожденная квадратная матрица размера m × m .
Ограничения (23) равносильны:
Ax − w = 0,
w = b.
(26)
Для построения начального базисного плана задачи (22)-(24) по-прежнему решается задача:
X
−
wj → min,
(27)
j∈M
Ax − w = 0,
w ≤ b.
Метод рассматриваем для задач:
0x → min,
Ax = 0,
−∞ ≤ l ≤ x ≤ u ≤ +∞.
(28)
(29)
(30)
Шаги нового алгоритма аналогичны шагам точного симплекс-метода с небольшими изменениеми касательно Шага 2. Повторим алгоритм с упомянутыми изменениями.
Алгоритм
Подготовка: Если все данные задачи принадлежат кольцу целых чисел, то можно
приступать к первому шагу.
17
Если числа рациональные, то по 2.2. делаем преобразования и переходим к Шагу 1.
Шаг 1.
Вычисление оценок небазисных переменных:
e = cB A
e+ Aj − c[j] · D.
∆[j]
B
Шаг 2.
Проверка условий оптимальности.
План оптимален (для случая detAB > 0), если :
e ≤ 0 для всех небазисных xj = lj ,
• ∆[j]
e ≥ 0 для всех небазисных xj = uj ,
• ∆[j]
e 6= 0 для неограниченных небазисных переменных xj = 0.
• ∆[j]
e противоположны. Если условия оптиДля случая detAB < 0 знаки неравенств ∆[j]
мальности не выполнены, соответствующую переменную xj вводим в базис, обычно
это максимальная по модулю оценка.
Шаг 3.
e+ Aj .
Вычислить вектор ze = z(j) = A
B
Шаг 4.
e 1, Θ
e 2:
Вычислить Θ
e <0
∆[j]
e >0
∆[j]
Dl
−
Dx
i
i
e 1 := min
Θ
|e
z[i] < 0
i
ze[i]
Dui − Dxi
e
Θ2 := min
|e
z[i] > 0
i
ze[i]
Dx
−
Dl
i
i
e 1 := min
Θ
|e
z[i] > 0
i
ze[i]
Dxi − Dui
e
Θ2 := min
|e
z[i] < 0
i
ze[i]
Положить
e := min{uj − lj ; Θ
e 1; Θ
e 2 }.
Θ
e = +∞, то целевая функция не ограничена на множестве планов, оста• Если Θ
новка алгоритма.
• Пусть i — индекс, на котором достигается минимум на шаге 4:
e = uj − lj базис не меняется и xj меняет значение с lj на uj ,
– В случае Θ
либо с uj на lj ,
18
e =Θ
e 1 переменная xi выходит из базиса и принимает значение
– В случае Θ
li ,
e =Θ
e 2 переменная xi выходит из базиса и принимает значение ui .
– В случае Θ
Шаг 5.
Пересчет компонент базисного плана xB :
e+ AH xH .
D · xB = −A
B
Шаг 6.
Составляем матрицу [AB |I|Aj ], которая состоит из трех подматриц.
eB |e
Q([AB |I|Aj ], B) = [detAB × I|A
z ].
Вычисляем Q-преобразование для полученной Q-матрицы:
. e ..
eB |e
[detAB × I|A
z ] (j, i) = [ . . |A
B 0 |.].
Рассмотренный симплекс-метод проходит задачу в один этап, при этом вычисления ведутся только целочисленные, поэтому точность алгоритма не теряется. Важно, что переменные не имеют ограничений на знак. Ответ не обязательно должен
быть целым. Время прохождения алгоритма полиномиально, как в случае точного
симплекс-метода.
Приложение 3 содержит решенный пример на описанный выше симплекс-алгоритм.
19
4
Программная реализация алгоритмов решения задач
Общее описание
Для данной дипломной работы была разработана программа для точного симплексметода и точного решения систем линейных уравнений . Программа написана на
языке Python 2.7 .
Используются инструменты:
- Операционная система Ubuntu 14.04.
- Терминал GNOME 3.6.
- Текстовый редактор GEdit 3.10.4 с подсветкой синтаксиса python.
- Интерпретатор языка Python 2.7.
- Библиотека NumPy для Python.
Python - это язык высокого уровня. Python - это интерпретируемый язык, который не нуждается в предварительной компиляции в файлы. Интерпретаторы языка
доступны для разных операционных систем [9]. Python используется и в разработке
коммерческих проектов, и для научных расчетов.
Python 2 и Python 3
В текущее время две наиболее используемые версии языка Python - это версии 2
и 3, которые принадлежат одному языку, но совместимость между ними нарушена.
Python 3 - более новый язык, но ему не удалось вытеснить Python 2. Так как до сих
пор множество проектов и библиотек использует язык Python 2, поддержка версии
2 продлена до 2020 года.
Дипломная работа была реализована на языке Python 2.7 как более простой вариант.
Библиотека NumPy
Numpy - библиотека с открытым кодом [8]. Numpy предоставляет удобные инструменты для работы с массивами и матрицами. Библиотека так же содержит встроенные высокоуровневые математические функции и пакет для работы с алгоритмами
линейной алгебры. Преимущество этой библиотеки - быстродействие.
Инструкция по установке Python, NumPy
• Операционная система Linux.
20
- Открыть консоль (обычно ctrl+alt+t).
- Ввести в консоли - sudo apt-get install python2.7.
- Скачать
https://bootstrap.pypa.io/get-pip.py .
- Набрать команду в консоли python get-pip.py.
- Набрать команду в консоли sudo pip3 install numpy.
• Операционная система Windows.
- Скачать файл
https://www.python.org/downloads/release/python-2711/ .
- Запустить файл
- Установить setuptools
http://www.lfd.uci.edu/~gohlke/pythonlibs/#setuptools .
- Открыть консоль и набрать команду pip3 install numpy .
Интерфейс программы
Программа состоит из нескольких файлов, написанных на языке Python, и имеет
интерфейс командной строки. Для запуска программы используется команда
python main.py «args», где python - интерпретатор языка python 2.7.
Аргументы командной строки
- –h, - help - выводит описание программы и аргументов.
- –in - файл входных данных. Может быть регулярным файлом или директорией.
- –out - файл выходных данных. Может быть регулярным файлом, директорией
или несуществующим файлом.
- –method - метод решения задачи. Реализованные методы - 2-phase, 1-phase,
gauss.
Значения по умолчанию:
- –out - вывод в консоль,
- –in - файл data.txt,
- –method - 2-phase.
21
Ограничения на входные и выходные данные:
Если входной файл IN не указан, то по умолчанию будет использоваться регулярный файл data.txt.
• Если входной файл IN - регулярный файл.
– Выходной файл OUT не указан, тогда решение будет выводиться в консоль
терминала.
– Выходной файл OUT - существующий регулярный файл, тогда решение
будет записано в него.
– Выходной файл OUT - несуществующий файл, тогда будет создан регулярный файл с решением.
– Остальные варианты OUT недопустимы.
• Если входной файл IN - директория.
Программа трактует регулярные файлы, которые лежат в директории, как
файлы входных данных, и последовательно их решает. Директории и файлы
ниже уровнем игнорируются.
– Выходной файл OUT не указан, тогда решение для всех задач будет выводиться в консоль терминала.
– Выходной файл OUT - существующая директория, тогда будут созданы
соответствующие файлы с решениями в этой директории. Для каждого файла IN/ << f ile >> .txt будет создан файл (или перезаписан)
OU T / << f ile_out >> .txt.
– Выходной файл OUT - несуществующий файл, тогда будет создана директория с решениями как описанно выше.
– Остальные варианты OUT недопустимы.
• Остальные варианты IN недопустимы.
Поддержка дробных значений коэффициентов
Коэффициенты, которые задаются в файлах, должны быть следующих форматов:
- Целое число. Например: 2, 0, -2.
- Дробь в формате (-)A/(-)B. Например: 1/2, -1/2. Допустимы значения -1/-2,
1/-2.
Поддерживаемые методы решения
В программе поддержаны следующие методы целочисленного решения:
22
- Двухфазный симплекс-метод.
Заглавие дает краткое название точного симплекс-метода при целочисленных
исходных данных, он направлен на решение задач в два этапа без операции
деления и рассмотрен в Главе 2.2.
- Однофазный симплекс-метод.
Однофазный симплекс-метод или метод, который направлен на решение систем
линейных уравнений с помощью задач ЛП. Задача ЛП с помощью этого метода
решается в один этап. Описание метода находится в Главе 3.2..
- Метод Гаусса.
Целочисленным методом решения систем линейных уравнений, или кратко методом Гаусса, можно решить систему, не выходя за пределы кольца целых
чисел. Глава 3.1 содержит описание метода Гаусса.
Cимплекс-метод
Для запуска двухфазного симплекс-метода необходимо указать аргумент –method
со значением 2-phase. Для запуска однофазного симплекс-метода необходимо указать
аргумент –method со значением 1-phase.
Чтобы задать файл данных для симплекс-метода необходимо:
- В первой строке задать целевую функцию на минимум. Для этого нужно записать коэффициенты при функции через пробел. Целевая функция определяет
количество используемых переменных n.
- В следующих строках задать уравнения. Одно уравнение содержит n коэффициентов при переменных и 1 значение уравнения. Все значения разделяются
пробелами.
Если файл не соответствует указанным выше требованиям, то программа показывает сообщение об ошибке:
Error at line line_number : expected A elements, found B. Equation should consists
of n coefficients and 1 value.
Метод Гаусса
Для запуска метода Гаусса необходимо указать аргумент –method со значением
gauss.
Входные файлы должны удовлетворять: каждая строка должна содержать одинаковое количество коэффициентов, разделенных пробелом. Первые n коэффициентов соответствуют n переменным, последний коэффициент соответствует значению
уравнения в правой части.
Если файл не соответствует указанным выше требованиям, то программа показывает сообщение об ошибке:
23
- Если задано m уравнений с n переменными и m = n:
Error: file contains worng data: m equations and n variables.
- Если одно из уравнений содержит неверное количество коэффициентов, которое отличается от первого уравнения:
Error at line line_number : expected A elements, found B. Equations should have
the same number of elements.
Результат программы
Результат содержит итерационную запись шагов алгоритма. Ответ находится в
конце файла:
- Значения переменных и целевой функции, если решение существует.
- Сообщение ’No solution have been found: objective function is unbounded.’ в случае, если целевая функция не ограничена на множестве планов.
- Сообщение ’Linear system is inconsistent.’, если система уравнений несовместна.
Примеры запуска программы
- Двухфазный симплекс-метод:
Входные данные - файл data_example.txt:
−1
10
−1
1 −11/2 −7 −13
1
29/2
7
15
Для запуска программы необходимо набрать:
python main.py –in data_example.txt –out data_example_out.txt –method 2phase.
- Однофазный симплекс-метод:
Входные данные - файл data_example_square.txt:
3 −10 −3
1
0
2 2
2
1
0 6
−1 2
3 9
Для запуска программы необходимо набрать:
python main.py –in data_example_square.txt –out data_example_square_out.txt
–method 1-phase.
24
- Метод Гаусса
Входные данные - файл data_gauss.txt:
2 −1 −2 −3 2
1 2
3 −2 1
3 2 −1 2 −5
2 −3 2
1 11
Чтобы запустить программу, нужно набрать команду:
python main.py –in data_gauss.txt –out data_gauss_out.txt –method gauss.
Программа запакована в zip-архив. При распаковке программы должны присутствовать файлы:
- main.py,
- args.py,
- file_reader.py,
- common.py,
- simplex_2_phase.py,
- simplex_1_phase.py,
- gauss.py.
Также в архиве находятся:
- data_example.txt - данные для задачи из пункта 2.2 - для двухфазного симплексметода.
- data_example_square.txt - данные для задачи из пункта 3.2 - для однофазного
симплекс-метода.
- data_gauss.txt - данные для задачи из пункта 3.1 - для метода Гаусса.
- директория input_2_phase - содержит набор задач из сборника задач Заславского [5] - для двухфазного симплекс-метода.
25
Заключение
Дипломная работа посвящена точным методам решения задач. Точное решение
задач необходимо для получения на выходе точного результата (целого или рационального) и, соответственно, сокращения времени нахождения решения.
В ходе работы был выполнен ряд расчетов, а именно:
Численные примеры решения задач точным симплекс-методом решены при размерности m = 3, n = 5, m = 3, n = 4, m = 2, n = 4.
Система линейных уравнений была решена методом решения систем без операции
деления при размерности m = 4, n = 4 .
Прозводились описание, подсчет и введение Q - матриц в точный алгоритм симплексметода.
Точный алгоритм симплекс-метода реализован на языке Python. Используется библиотека numpy. Программу тестировали на задачах размерности m = 2, n = 5,
m = 3, n = 5, m = 4, n = 8, m = 10, n = 17, на задачах с коэффициентами выше
1000. Решение линейных систем без операции деления было запрограммировано на
языке Python. Программа была протестирована на примере m = 4, n = 4.
По результатам проделанной работы можно заключить, что методы решения задач без операции деления - это большая и интересная область для исследования.
26
Список литературы
[1] Azulay D., Pique J.F. A revised simplex method with integer Q-matrices ACM Transactions on
Mathematical Software,V. 27, No 3. P. 350–360, 2001
[2] Azulay D., Pique J.F. Optimized Q-pivot for exact linear solvers Principles and Practice of
Constraint Programming, Pisa, Italy, Springer, Berlin, P. 55–71, 1998
[3] Chvatal V. Linear Programming W. H. Freeman and Company, New York , 1983
[4] Edmonds J., Maurras J.F. Notes sur les Q-matrices d’Edmonds Recherche opérationelle , V. 31, No
2, P. 203–209, 1997
[5] Заславский Ю.Л. Сборник задач по линейному программированию М. Наука, 1969
[6] Золотых Н. Ю., Кубарев В. К. Полностью целочисленный разреженный симплекс-метод Вестник Нижегородского университета им. Н.И. Лобачевского , №4(1), с. 232-237, 2012
[7] Малашонок Г.И. Решение системы линейных уравнений в целостном кольце Журнал вычислительной математики и математической физики , Т. 23, No 6, С. 1497–1500, 1983
[8] NumPy URL: http://www.numpy.org/
[9] Python URL: https://www.python.org
27
Приложение 1
Примеры решения задач ЛП целочисленным симплексметодом
Задача 1:
3x1 − 10x2 + 5x3 − 3x4 + 2x5 → min,
x1 − 2x3 + 2x4 − 3x5 = 2,
2x1 + x2 + 4x3 + x5 = 6,
−x1 + 2x2 + 3x4 = 9,
xj ≥ 0, j = 1 : 5.
Этап I. Решаем вспомогательную задачу:
−x6 − x7 − x8 → min,
x1 − 2x3 + 2x4 − 3x5 − x6 = 0,
2x1 + x2 + 4x3 + x5 − x7 = 0,
−x1 + 2x2 + 3x4 − x8 = 0,
xj ≥ 0, j = 1 : 5, x6 ≤ 2, x7 ≤ 6, x8 ≤ 9.
Матрица ограничений, вектор правой части и вектор коэффициентов целевой функции выглядят следующим образом:
1 0 −2 2 −3 −1 0
0
0
0 −1 0 , b = 0 , c = 0 0 0 0 0 −1 −1 −1
A(1) = 2 1 4 0 1
−1 2 0 3 0
0
0 −1
0
Начальная симплекс-таблица:
f (e
x)
0
x
e6
x
e7
x
e8
0
0
0
1
1
−1
0
0
1
0
−1
0
0
0
−1
e+
A
B
Этап I.
Итерация 1.
f (e
x)
0
x
e6
x
e7
x
e8
0
0
0
1
−1
0
0
1
0
−1
0
e+
A
B
−1
AB = 0
0
0
−1
0
0
0
−1
e =5
∆[4]
−2
0
−3
e+ A4
A
B
0
0 , D = −1.
−1
e = 2;
∆[1]
28
1
e = 3;
∆[2]
e = 2;
∆[3]
e = 5;
∆[4]
e = −2.
∆[5]
-2
e+ A4 = 0
A
B
-3
⇒ переменная x4 входит в базис.
e = 5 > 0, ze < 0 ⇒ Θ = min
∆[4]
0−9
0−2
; +∞;
−2
−3
= 1,
что соответствует переменной x6 , она выходит из базиса.
Пересчет присоединенной матрицы.
Конкатенация трех частей: базисной матрицы,
базис:
−1
[AB |I|A4 ] = 0
0
единичной и столбца матрицы A, который войдет в
0
0 1 0 0 2
−1 0 0 1 0 0
0 −1 0 0 1 3
Вычисление Q–матрицы
−1
Q([AB |I|A4 ]) = 0
0
0
−1
0
0
0
−1
1 0 0 2
0 1 0 0
0 0 1 3
и делаем поворот вокруг элемента (1, 7), так как первый столбец соответствует выходящей из базиса
переменной x6 , а седьмой — входящей в базис переменной x4 .
После преобразования на месте единичной матрицы будет стоять присоединенная
1 0
0
eB = 0 −2 0
A
3 0 −2
x6 принимает значение своей верхней границы.
Небазисные переменные равны
x1 = 0, x2 = 0, x3 = 0, x5 = 0, x6 = 2.
Пересчет базисного решения.
x
e4
1
e+ AH xH = − 0
e7 = −A
x
eB = x
B
x
e8
3
0
−2
0
0
1
0 · 2
−2
−1
0 −2
1 4
2 0
x
e4
−2
2
e7 = − 0 = 0
x
eB = x
x
e8
−6
6
29
−3
1
0
x1
x2
−1
0 ·
x3
0
x5
x6
Итерация 2.
f (e
x)
−6
x
e4
x
e7
x
e8
2
0
6
−3
1
0
3
2
e = 14
∆[3]
0
0
−2
−2
−8
−6
2
0
−2
0
e+
A
B
2
AB = 0
3
0
−1
0
e+ A3
A
B
0
0 , D = 2.
−1
e = −1;
∆[1]
e = 6;
∆[2]
e = 14;
∆[3]
e = 11.
∆[5]
-2
e+ A3 = -8
A
B
-6
⇒ переменная x3 входит в базис.
e = 14 > 0,
∆[3]
3
0−D·6 6−D·9
;
= ,
ze < 0 ⇒ Θ = min ∞;
−8
−6
2
что соответствует переменной x7 , она выходит из базиса.
Пересчет присоединенной матрицы.
2
[AB |I|A3 ] = 0
3
0
−1
0
0
0
−1
1 0 0 −2
0 1 0 4
0 0 1 0
Вычисление Q - матрицы
2 0 0 1
Q([AB |I|A3 ]) = 0 2 0 0
0 0 2 3
0
−2
0
0
0
−2
−2
−8 .
−6
Чтобы найти новую присоединенную матрицу, мы делаем поворот вокруг элемента (2, 7), так как
второй столбец соответствует выходящей из базиса переменной x7 , а седьмой — входящей в базис
переменной x3 .
Присоединенная матрица
−4 −2 0
eB = 0
−2 0
A
−12 −6 8
x7 принимает значение верхней границы.
Текущие значения небазисных переменных
x1 = 0, x2 = 0, x5 = 0, x6 = 2, x7 = 6.
30
Пересчет базисного решения.
x
e4
−4 −2 0
1
e3 = 0
−2 0 · 2
x
eB = x
x
e8
−12 −6 8
−1
0 −3
1 1
2 0
−1
0
0
x1
x2
0
−1 ·
x5
x6
0
x7
x
e4
20
e3 = 12
x
eB = x
x
e8
60
Итерация 3.
f (e
x)
−60
−12
x
e4
x
e3
x
e8
20
12
60
4
0
12
−6
2
2
6
8
e = 30
∆[5]
e+
A
B
2
AB = 0
3
−2
4
0
−10
2
−30
0
0
−8
e+ A5
A
B
0
0 , D = −8.
−1
e = −32;
∆[1]
e = 10;
∆[2]
e = 30.
∆[5]
-10
e+ A5 = 2
A
B
-30
⇒ переменная x5 входит в базис.
12 − D · 0 60 − D · 9
2
Θ = min ∞;
;
= ,
2
−30
5
что соответствует переменной x8 , она выходит из базиса.
Пересчет присоединенной матрицы.
2
[AB |I|A5 ] = 0
3
−2
4
0
0
0
−1
1 0 0 −3
0 1 0 1 .
0 0 1 0
Вычисление Q - матрицы
−8
Q([AB |I|A5 ]) = 0
0
0
−8
0
0
0
−8
−4 −2 0
0
−2 0
−12 −6 8
После Q - поворота присоединенная матрица равна
0
0
10
eB = 3
9 −2 ,
A
−12 −6 8
31
−10
2 (3, 7).
−30
Пересчет небазисных переменных
x1 = 0, x2 = 0, x6 = 2, x7 = 6, x8 = 9.
Пересчет базисного решения.
x
e4
0
e3 = − 3
x
eB = x
x
e5
−12
0
9
−6
10
1
−2 · 2
8
−1
0 −1
1 0
2 0
0
−1
0
x1
x2
0
0 ·
x6
x7
−1
x8
x
e4
90
e3 = 42
x
eB = x
x
e5
12
Все искусственные переменные вышли из базиса, вектор cB = (0, 0, 0).
Итерация 4.
2
AB = 0
3
f (e
x)
0
x
e4
x
e3
x
e5
90
42
12
−3
1 , D = 30.
0
−2
4
0
0
0
3
−12
0
0
0
9
−6
10
−2
8
e+
A
B
e = 0 ⇒ план оптимален.
∆
Этап II.
Итерация 1.
f (e
x)
-36
−9
x
e4
x
e3
x
e5
90
42
12
0
3
−12
33
−24
e = 285
∆[2]
10
−2
8
20
5
10
0
9
−6
e+
A
B
2
AB = 0
3
−2
4
0
−3
1 , D = 30.
0
e = −9;
∆[1]
e = 285.
∆[2]
20
e+ A2 = 5
A
B
10
32
e+ A2
A
B
Переменная x2 входит в базис.
90 − D · 0 42 − D · 0 12 − D · 0
6
Θ = min
;
;
= ,
20
5
10
5
Переменная x5 выходит из базиса.
Пересчет присоединенной матрицы.
2
[AB |I|A2 ] = 0
3
−2
4
0
−3
1
0
0
0
30
0
3
−12
1 0 0 0
0 1 0 1 .
0 0 1 2
Вычисление Q - матрицы
30 0
Q([AB |I|A2 ]) = 0 30
0 0
0
9
−6
10 20
−2 5 (3, 7).
8 10
Присоединенная матрица равна
−2
−2 ,
8
8
4
eB = 3
4
A
−12 −6
x5 становится равной нижней границе.
Пересчет небазисных переменных
x1 = 0, x5 = 0, x6 = 2, x7 = 6, x8 = 9.
Пересчет базисного решения.
x
e4
8
4
e3 = − 3
4
x
eB = x
x
e2
−12 −6
1
−2
−2 · 2
−1
8
−3
1
0
−1
0
0
0
−1
0
x1
x5
0
0 ·
x6
x7
−1
x8
x
e4
22
e3 = 12 .
x
eB = x
x
e2
12
Итерация 2.
f (e
x)
-126
111
68
−84
e = 301
∆[1]
x
e4
x
e3
x
e2
22
12
12
8
3
−12
4
4
−6
−2
−2
8
18
13
−32
e+
A
B
2
AB = 0
3
−2
4
0
0
1 , D = 10.
2
e = 301;
∆[1]
33
e+ A1
A
B
e = −285.
∆[5]
18
e+ A1 = 13
A
B
-32
Переменная x1 входит в базис.
12
22 − D · 0 12 − D · 0 12 − D · ∞
;
;
=
,
Θ = min
18
13
−32
13
Переменная x3 выходит из базиса.
Пересчет присоединенной матрицы.
2
[AB |I|A1 ] = 0
3
0 1 0 0 1
1 0 1 0 2 .
2 0 0 1 −1
−2
4
0
Вычисление Q - матрицы
10
Q([AB |I|A1 ]) = 0
0
0
10
0
0
0
10
−2
−2
8
8
4
3
4
−12 −6
18
13 (2, 7).
−32
Присоединенная матрица равна
5
eB = 3
A
−6
−2
4
5
1
−2 ,
4
Пересчет небазисных переменных
x3 = 0, x5 = 0, x6 = 2, x7 = 6, x8 = 9.
Пересчет базисного решения.
x
e4
5
e1 = − 3
x
eB = x
x
e2
−6
−2
4
5
1
−2
−2 · 4
4
0
−3
1
0
−1
0
0
x
e4
7
e1 = 12 .
x
eB = x
x
e2
54
Итерация 3.
f (e
x)
-525
x
e4
x
e1
x
e2
7
12
54
2
AB = 0
3
54
5
3
−6
1
2
−1
34
−32
−49
−2
4
5
1
−2
4
e+
A
B
0
1 , D = 13.
2
0
−1
0
x3
x5
0
0 ·
x6
−1
x7
x8
e = −301;
∆[3]
e = −220.
∆[5]
e < 0. Решение оптимально.
∆
Ответ:
x1 =
12
,
13
x2 =
54
,
13
x3 = 0,
f (x) =
x4 =
7
,
13
x5 = 0,
−525
13
.
Задача 2:
−x1 + 4x2 − 3x3 − 10x4 → min,
x1 + x2 − x3 + x4 = 0,
x1 + 14x2 + 10x3 − 10x4 = 11,
xj ≥ 0, j = 1 : 4.
Вспомогательная задача:
−x5 − x6 → min,
x1 + x2 − x3 + x4 − x5 = 0,
x1 + 14x2 + 10x3 − 10x4 − x6 = 0,
xj ≥ 0, j = 1 : 4, x5 ≤ 0, x6 ≤ 11.
Этап I.
Итерация 1.
f (e
x)
0
1
x
e5
x
e6
0
0
−1
0
AB =
−1
0
1
e = 15
∆[2]
0
−1
−1
−14
e+
e+ A2
A
A
B
B
0
, D = −1.
−1
e = 2;
∆[1]
e = 15;
∆[2]
e = 9;
∆[3]
e = −9.
∆[4]
-1
+
e
AB A4 =
-14
⇒ переменная x2 входит в базис.
e = 15 > 0, ze < 0 ⇒ Θ = min
∆[2]
0 − 0 0 − 11
;
−1
−14
что соответствует переменной x5 , она выходит из базиса.
35
= 0,
Пересчет присоединенной матрицы.
Конкатенация трех частей: базисной матрицы, единичной и столбца матрицы A, который войдет в
базис:
−1 0 1 0 1
[AB |I|A2 ] =
0 −1 0 1 14
Вычисление Q - матрицы
1
Q([AB |I|A2 ]) =
0
−1
0
0
1
0
−1
−1
(1, 5).
−14
После преобразования на месте единичной матрицы будет стоять присоединенная
0
eB = −1
A
.
−14 −1
x5 принимает значение своей верхней границы.
Небазисные переменные равны
x1 = 0, x3 = 0, x4 = 0, x5 = 0.
Пересчет базисного решения.
x
eB =
x
e2
x
e6
e+ AH xH
= −A
B
−1
0
1
=−
·
−14 −1
1
x
eB =
x
e2
x
e6
f (e
x)
0
−14
x
e2
x
e6
0
0
−1
10
x1
1 −1
x3
·
x4 ,
10 0
x5
0
=
.
0
Итерация 2.
1
−14
1
e = 24
∆[3]
0
−1
−1
−24
e+
e+ A3
A
A
B
B
1
0
AB =
, D = −1.
14 −1
e = −13;
∆[1]
e = 24;
∆[3]
e = −24.
∆[4]
-1
+
e
AB A3 =
-24
⇒ переменная x3 входит в базис.
e = 24 > 0, ze < 0 ⇒ Θ = min ∞; 0 − 11 = 11 ,
∆[3]
−24
24
что соответствует переменной x6 , она выходит из базиса.
36
Пересчет присоединенной матрицы.
Конкатенация трех частей: базисной матрицы, единичной и столбца матрицы A, который войдет в
базис:
1
0 1 0 −1
[AB |I|A3 ] =
14 −1 0 1 10
Вычисление Q - матрицы
Q([AB |I|A3 ]) =
−1
0
−1 0 −1
(2, 5).
−14 1 −24
0
−1
После преобразования на месте единичной матрицы будет стоять присоединенная
eB = 10 1 .
A
−14 1
x6 принимает значение своей верхней границы.
Небазисные переменные равны
x1 = 0, x4 = 0, x5 = 0, x6 = 11.
Пересчет базисного решения.
x
eB =
x
e2
x
e3
e+ AH xH = −
= −A
B
10
−14
x
eB =
x
e2
x
e3
1
1
·
1
1
=
1
−1
−10 0
11
.
11
Итерация 3.
f (e
x)
0
0
x
e2
x
e3
11
11
10
−14
AB =
1
14
0
1
1
e+
A
B
−1
, D = 24.
10
e = 0.
∆
План оптимален.
Переходим к следующему этапу.
Этап I.
Итерация 1.
f (e
x)
11
82
1
e = 312
∆[4]
x
e2
x
e3
11
11
10
−14
1
1
0
−24
AB =
1
14
e+
e+ A4
A
A
B
B
−1
, D = 24.
10
37
x1
x4
0
· ,
−1 x5
x6
e = 107;
∆[1]
e = 312.
∆[4]
e = 312 > 0 ⇒ Θ = min ∞; 0 − ∞ = ∞.
∆[4]
−24
Ответ: задача не ограничена на множестве планов.
38
Приложение 2
Примеры решения системы линейных уравнений без
операции деления и нахождения присоединенной матрицы без операции деления
Пример:
Решить систему линейных алгебраических уравнений
2x1 − x2 − 2x3 − 3x4 = 2
x + 2x + 3x − 2x = 1
1
2
3
4
3x1 + 2x2 − x3 + 2x4 = −5
2x1 − 3x2 + 2x3 + x4 = 11
Прямой ход.
Составим расширенную матрицу системы
2
1
C = C1 =
3
2
−1
2
2
−3
−2
3
−1
2
−3
−2
2
1
.
2
1
.
−5
11
Умножим вторую строку на a11 = 2 и вычтем первую, помноженную на a21 = 1, умножим третью строку на a11 = 2 и вычтем первую, помноженную на a31 = 3, и, наконец, умножим четвертую
строку на a41 = 2 и вычтем первую строку, умноженную на a41 = 2.. Переходим после преобразований к матрице C2 :
2 −1 −2 −3
2
0 5
8 −1
0
.
C2 =
0 7
4
13 −16
0 −4 8
8
18
Аналогично, умножим третью строку на a22 = 5, вычтем из нее вторую, помноженную на
a32 = 7, умножим четвертую строку на a22 = 5 и вычтем из нее вторую, умноженную на a42 = −4:
2 −1 −2 −3
2
0 5
8
−1
0
0 0 −36 72 −80 .
0 0
72
36
90
Теперь можно сократить преобразованные
переходим к третьей матрице:
2 −1
0 5
C3 =
0 0
0 0
третью и четвертую строки на элемент a11 = 2,
−2 −3
8
−1
−18 36
36
18
2
0
.
−40
45
В матрице C3 преобразуем четвертую строку, для этого умножим ее на a33 = −18 и вычтем
третью строку, умноженную на a43 = 36. После преобразования переходим диагональной к матрице
2 −1 −2
−3
2
0 5
8
−1
0
.
0 0 −18
36
−40
0 0
0
−1620 630
39
На этом этапе можем сократить четвертую строку преобразованной выше матрицы на a22 = 5 :
2 −1 −2
−3
2
0 5
8
−1
0
.
C4 =
0 0 −18
36
−40
0 0
0
−324 126
Элементы матрицы C4 равны:
a44 = |A| = −324,
a45 = |4 A| = 126.
Обратный ход.
Используя найденные определители матриц A и 4 A и элементы диагональной матрицы C4 ,
находим остальные определители |3 A|, |2 A|, |1 A| по формулам
|3 A| = (|A|a35 − |4 A|a34 ) /a33 = −468,
|2 A| = (|A|a25 − |4 A|a24 − |3 A|a23 ) /a22 = 744,
|1 A| = (|A|a15 − |4 A|a14 − |3 A|a13 − |2 A|a12 ) /a11 = −216.
Определители найдены, записываем решение по формуле Крамера:
x1 =
−216
2
= ,
−324
3
43
744
=− ,
−324
18
13
−468
=
,
x3 =
−324
9
126
7
x4 =
=− .
−324
18
x2 =
Пример:
Вычислим присоединенную матрицу для матрицы
2 3 4
1 −2 3 .
3 −1 1
Прямой ход:
Составим расширенную матрицу системы
2 3 4 1 0 0
C = C1 = 1 −2 3 0 1 0 .
3 −1 1 0 0 1
Преобразуем вторую и третью строки. Для этого умножим вторую строку на a11 = 2 и вычтем
из нее первую строку, умноженную на a21 = 1, и, умножим третью строку на a11 = 2 и вычтем из
нее первую строку, умноженную на a31 = 3. После преобразования матрица имеет вид:
2
3
4
1 0 0
2
−1 2 0 .
C2 = 0 −7
0 −11 −10 −3 0 2
40
Аналогично, преобразуем третью строку и приходим к верхнетреугольной матрице:
2 3
4
1
0
0
0 −7 2 −1 2
0 .
0 0 92 10 22 −14
По алгоритму нужно сократить третью строку
2 3
4
C3 = 0 −7 2
0 0 46
на элемент a11 . Получаем матрицу C3 :
1
0
0
−1 2
0 .
5 11 −7
Элементы матрицы C3 равны:
a33 = |A| = 46,
a34 = p31 = 5,
a35 = p32 = 11,
a36 = p33 = −7.
Обратный ход:
По формуле (22) вычислим недостающие элементы присоединенной матрицы, используя результат Прямого хода:
p2j = (|A|a2,3+j − p3j a23 )/a22 , j = 1, 2, 3 :
j = 1 : p21 = 8,
j = 2 : p22 = −10,
j = 3 : p23 = −2.
p1j = (|A|a1,3+j − p2j a13 )/a11 , j = 1, 2, 3 :
j = 1 : p21 = 1,
j = 2 : p22 = −7,
j = 3 : p23 = 17.
Все элементы присоединенной матрицы найдены. Запишем результат:
1
P = 8
5
−7 17
−10 −2 .
11 −7
41
Приложение 3
Пример решения системы линейных уравнений точным симплекс-методом
Пример:
Решить систему уравнений:
x1 + 2x3 = 2,
2x1 + x2 = 6,
−x1 + 2x2 + 3x3 = 9.
Решаем задачу вида:
0x → min,
x1 + 2x3 = 2,
2x1 + x2 = 6,
−x1 + 2x2 + 3x3 = 9.
Решаем вспомогательную задачу:
−x4 − x5 − x6 → min,
x1 + 2x3 − x4 = 0,
2x1 + x2 − x5 = 0,
−x1 + 2x2 + 3x3 − x6 = 0,
x4 ≤ 2, x5 ≤ 6, x6 ≤ 9.
Итерация 1.
1
x
e4
x
e5
x
e6
−1
0
0
0
0
0
1
1
0
−1
0
e+
A
B
−1
AB = 0
0
0
−1
0
0
0
−1
e =5
∆[3]
−2
0
−3
e+ A3
A
B
0
0 , D = −1.
−1
e = 2;
∆[1]
e = 3;
∆[2]
e = 5.
∆[3]
Переменная x3 входит в базис.
e = 5 > 0, ze < 0 ⇒ Θ = min
∆[3]
Переменная x4 покидает базис.
Пересчет присоединенной матрицы.
42
0−2
0−9
; +∞;
−2
−3
= 1,
−1
[AB |I|A3 ] = 0
0
0
−1
0
1 0 0 2
0 1 0 0 .
0 0 1 3
0
0
−1
Вычисление Q - матрицы
−1
Q([AB |I|A3 ]) = 0
0
0
−1
0
0
0
−1
1 0 0 2
0 1 0 0 (1, 7).
0 0 1 3
1
eB = 0
A
3
0
−2
0
0
0 .
−2
Присоединенная матрица
Пересчет небазисных переменных
x1 = 0, x2 = 0, x4 = 2.
Пересчет базисного решения.
x
e3
1
e5 = − 0
x
eB = x
x
e6
3
0
1
0 · 2
−2
−1
0
−2
0
0 −1
x1
1 0 · x2 .
2 0
x4
Пересчет базисного решения.
x
e3
2
e5 = 0 .
x
eB = x
6
x
e6
Итерация 2.
−3
x
e3
x
e5
x
e6
2
0
6
1
0
3
2
e =6
∆[2]
0
0
−2
0
−2
−4
2
0
−2
0
e+
A
B
2
AB = 0
3
0
−1
0
e+ A2
A
B
0
0 , D = 2.
−1
e = −1;
∆[1]
e = 6.
∆[2]
Переменная x2 входит в базис.
0−D·6 6−D·9
Θ = min ∞;
;
= 3.
−2
−4
Переменная x6 выходит из базиса.
Пересчет присоединенной матрицы.
2
[AB |I|A2 ] = 0
3
0
−1
0
43
0
0
−1
1 0 0 0
0 1 0 1 .
0 0 1 2
Вычисление Q - матрицы
2 0 0 1
Q([AB |I|A2 ]) = 0 2 0 0
0 0 2 3
0
−2
0
0
−2 (3, 7).
−4
0
0
−2
Присоединенная матрица
−2
eB = 3
A
3
0 0
4 −2 .
0 −2
Пересчет небазисных переменных
x1 = 0, x4 = 2, x6 = 9.
Пересчет базисного решения.
x
e3
−2
e5 = − 3
x
eB = x
x
e2
3
0 0
1
4 −2 · 2
0 −2
−1
−1
0
0
0
x1
0 · x4 ,
−1
x6
Пересчет базисного решения.
x
e3
4
e5 = 12 .
x
eB = x
x
e2
12
Итерация 3.
3
x
e3
x
e5
x
e2
4
12
12
4
2
−3
−3
e = 13
∆[1]
−2
0
−4
0
0
2
2
2
−13
−5
e+
e+ A1
A
A
B
B
0 0
−1 1 , D = −4.
0 2
2
AB = 0
3
e = 13.
∆[1]
Переменная x1 входит в базис.
12 − 24
12
Θ = min ∞;
;∞ =
.
−13
13
Переменная x5 оставляет базис.
Пересчет присоединенной матрицы.
2
[AB |I|A1 ] = 0
3
0
−1
0
0 1 0 0 1
1 0 1 0 2 .
2 0 0 1 −1
Вычисление Q - матрицы
−4
Q([AB |I|A1 ]) = 0
0
0
−4
0
0 −2
0
3
−4 3
44
0 0
4 −2
0 −2
2
−13 (2, 7).
−5
После Q - поворота присоединенная матрица равна
5 −2 1
eB = 3
4 −2 ,
A
−6 5
4
Пересчет небазисных переменных
x4 = 2, x5 = 6, x6 = 9.
Пересчет базисного решения.
x
e3
5
e1 = − 3
x
eB = x
x
e2
−6
−2
4
5
1
−1
−2 · 0
4
0
0
−1
0
x
e3
7
e1 = 12
x
eB = x
x
e2
54
Новый базис
2
AB = 0
3
0
1 , D = 13.
2
1
2
−1
Вспомогательных переменных не осталось в базисе.
Оптимальное решение найдено.
Ответ:
x1 =
12
,
13
x2 =
54
,
13
45
x3 =
7
.
13
0
x4
0 · x5
−1
x6
Отзывы:
Авторизуйтесь, чтобы оставить отзыв