Методы оптимизации. Часть 2. Линейное программирование
.pdfФедеральное агентство по образованию
Томский государственный университет систем управления и радиоэлектроники
Ю.И. Параев
МЕТОДЫ ОПТИМИЗАЦИИ
(Часть 2. Линейное программирование)
Методические указания для проведения практических занятий для студентов направлений 230100 «Информатика и вычислительная техника»,
230400 «Информационные системы и технологии»
Томск
ТУСУР
2010
УДК 519.85 (076)
Параев Ю.И.
Методы оптимизации (Часть 2. Линейное программирование) – Методические указания для проведения практических занятий для студентов направления 230100 «Информатика и вычислительная техника». 2010. – 46 с.
©Параев Юрий Иванович, 2010
©Томский государственный университет систем управления и радиоэлектроники, 2010
Содержание |
|
Тема 5. Линейное программирование................................................................................. |
3 |
5.1. Постановка задачи........................................................................................... |
3 |
5.2. Решение задач линейного программирования. Симплекс-метод.................. |
4 |
5.3. Выбор начального плана................................................................................. |
8 |
5.4. Геометрическое решение задач линейного программирования.................. |
10 |
Тема 6. Транспортная задача ............................................................................................. |
13 |
6.1. Постановка задачи......................................................................................... |
13 |
6.2. Структура решения........................................................................................ |
14 |
6.3. Выбор начального плана............................................................................... |
15 |
6.4. Метод потенциалов....................................................................................... |
17 |
Тема 7. Задача о назначениях............................................................................................. |
21 |
7.1. Постановка задачи......................................................................................... |
21 |
7.2. Решение задачи.............................................................................................. |
21 |
Задания для самостоятельной работы............................................................................... |
26 |
ТЕМА 5. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
5.1. Постановка задачи Найти экстремум линейной функции
i 1
n |
|
|
amixi |
bm, |
|
i 1 |
|
|
n |
|
|
a1ixi |
b1, |
|
i 1 |
|
|
n |
|
|
a2ixi |
b2, |
(5.4) |
i 1 |
|
|
n |
|
|
F(x) cixi |
(5.1) |
|
i 1 |
|
|
на линейном многообразии S, задаваемом условиями: |
|
|
I. Все xi≥0, i=1,…,n. |
|
(5.2) |
II. Должны выполняться либо равенства |
|
|
n |
|
|
a1ixi |
b1, |
|
i 1 |
|
|
n |
|
|
a2ixi |
b2, |
(5.3) |
либо неравенства |
|
|
|
|
|
n |
|
|
amixi |
bm. |
|
i 1 |
|
|
Задача с ограничениями типа (5.3) называется основной. Замечания.
1.Ограничения (5.3) или (5.4)должны быть совместны.
2.Задача с ограничениями типа неравенств сводится к задаче с ограничениями типа равенств с помощью введения новых переменных
n
a1ixi xn 1 b1,
i 1 |
|
n |
|
a2ixi xn 2 b2, |
(5.5) |
i 1 |
|
n
amixi xn m bm. i 1
Такой подход называется методом искусственного базиса.
3. Перечисленные соотношения удобно записать в матричной форме, если ввести в рассмотрение
вектор-строку СТ с1,с2,...,сn (Т – означает транспонирование),
векторы-столбцы
x1 |
|
|
b1 |
||
|
|
|
|
|
|
x x |
2 , |
b b2 |
|||
|
|
|
|
||
|
|
|
|
|
|
xn |
|
|
bm |
||
a11 |
a12 |
|
a1n |
||
|
|
|
|
|
|
А a21 |
a22 |
|
|
a2n . |
|
|
|
|
|
|
|
|
an2 |
|
|
|
|
an1 |
|
ann |
|||
и матрицу |
|
|
|
|
|
В результате вместо (5.1) получаем |
|
|
|
|
|
F(x) cT x . |
(5.6) |
||||
Вместо (5.2) и (5.3) – |
|
|
|
|
|
|
x 0, |
|
|
(5.7) |
|
|
Ax b. |
|
(5.8) |
||
4. Предполагается, что rang A m n, |
rang A,b rang A . Последнее есть |
||||
условие совместности системы уравнений (5.8). |
|
|
5. Обычно предполагается, что b 0. Это можно всегда получить, умножая при необходимости уравнения (5.1) на – 1.
5.2. Решение задач линейного программирования. Симплекс-метод
Условия (5.7) и (5.8) задают линейное многообразие S, угловыми точками которого являются вектора x, у которых n-m координат обязательно равны 0, а m координат ≠0. Решением задачи, если оно существует, является одна из таких угловых точек. Такие точки еще называют планом решения.
Симплекс-метод решения задач линейного программирования состоит в последовательном переборе этих угловых точек. Для определенности будем искать минимум функции F(x).
Пусть x – некоторая угловая точка, которая взята в качестве начального приближения или начального плана. Вопрос о выборе начального приближения будет рассмотрен ниже. Эта точка удовлетворяет условиям (5.7) и (5.8).
Обозначим через I(x) набор индексов ненулевых координат вектора x и через O(x) набор индексов нулевых координат этого вектора. Множество I(x) сдержит m
чисел, а множество O(x) – n-m чисел. Очевидно, что I(x) O(x) {1,2,...,n}. |
|
||
Введем новую угловую точку |
|
||
x |
x x , |
(5.9) |
|
где θ(>0) – некоторое число, x – некоторый произвольный вектор. Вектор |
x |
должен |
удовлетворять условиям (5.7) и (5.8). Подставляя (5.9) в (5.8), получаем, что вектор x должен удовлетворять уравнению
A x 0. |
(5.10) |
Обозначим через xI – вектор порядка m, составленный из элементов вектора х с
номерами из множества I(x), и через xO – вектор порядка n-m, составленный из эле-
ментов вектора х с номерами из множества О(x). Очевидно, что xO 0. Аналогично разделим строку сT на сTI и cOT . В результате вместо (5.6) получаем
|
|
|
F(x) cTI |
xI . |
(5.11) |
|||||
Аналогично разделим вектор |
x |
|
на векторы |
x |
I |
и |
x |
O , и вектор x |
на векторы xI и |
|
xO . |
|
|
|
|
|
|
|
|
||
При этом получается |
|
|
|
|
|
|
|
|
||
x |
I |
xI xI , |
x |
O xO. |
(5.12) |
Из последнего выражения следует необходимость условия xO 0.
Матрицу А можно записать в виде двух блоков AI , куда входят столбцы с номе-
рами из множества I(x) и AO , куда входят столбцы с номерами из множества O(x).
Блок AI имеет размерность m×m, блок AO – m×(n-m) соответственно. Тогда уравнение(5.10) можно переписать в виде
|
|
|
|
AI xI AO xO |
|
0 |
или AI xI |
AO xO. |
|
|
(5.13) |
||||||||||||||||||
Если блок AI невырожденный, то |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
x |
I |
A 1A x |
|
P x . |
|
|
|
(5.14) |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I |
O O |
|
O |
|
|
|
|
|
||||||
(P A 1A .) Элементы вектора |
|
x назовем независимыми переменными, а вектора |
|||||||||||||||||||||||||||
|
|
I |
O |
|
|
|
|
|
|
|
|
O |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
xI – зависимыми. Подставляя (5.14) в (5.12), получаем |
|
|
|
|
|
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
x |
I |
|
xI |
P xO, |
|
|
|
|
|
(5.15) |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
O xO. |
|
|
|
|
|
(5.16) |
||||||
Подставим последнее в (5.6). В результате получим |
|
|
|
|
|
|
|
||||||||||||||||||||||
|
|
|
F( |
x |
) cT |
x |
I |
cT |
x |
|
cT (x |
I |
P x |
O |
) cT x |
O |
|
|
|
||||||||||
|
|
|
|
|
I |
|
|
|
|
O O |
|
I |
|
|
|
|
|
O |
|
|
|
||||||||
|
|
|
F(x) (cT cT P) x |
|
F(x) T x , |
|
|
|
|
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
O |
|
I |
|
|
O |
|
|
|
|
|
|
O |
|
|
|
|
|||
где |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
T |
cOT cTI P. |
|
|
|
|
|
(5.17) |
|||||||||
Элементы строки T [ , |
2 |
,..., |
n m |
] |
– называются коэффициентами замещения. |
|
|||||||||||||||||||||||
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
Учитывая, |
что θ>0 и xO 0, получаем следующий результат. Если все |
j 0, |
то |
||||||||||||||||||||||||||
F( |
x |
) F(x) и, следовательно, |
вектор x дает минимальное значение функции F(x). |
Та- |
ким образом, решение задачи заканчивается. Если имеются j 0, то можно получить вектор x , для которого F(x) F(x). Для этого выберем наименьшее из j 0. Пусть это будет k k O x . Тогда положим xk 1, а все остальные xi 0 k,i O x . В
результате в векторе xO появляется k-ый элемент, равный . В этом случае вектор
(5.15) примет вид
xI xI pk ,
где pk – k-ый столбец матрицы Р. Вектор x должен удовлетворять условию (5.7), т.е.
должно выполняться
|
|
xi pik 0, i I x . |
|
|||||||
Поскольку xi 0, i I x , то эти неравенства выполняются всегда, когда |
pik 0. Поэто- |
|||||||||
му рассматриваются неравенства, где |
pik 0. |
Параметр выбирается так, чтобы одно |
||||||||
из неравенств, например, |
x |
l xl plk |
0 , а остальные |
x |
i xi pik 0, i I x \l. Таким |
|||||
образом, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xl |
|
. |
|
|
(5.18) |
|
|
|
|
plk |
|
|
|||||
|
|
|
|
|
|
|
|
|||
В результате получается, |
что для вектора |
x |
|
набор индексов ненулевых координат |
I x I x \l,k , нулевых координат – O x O x \k,l .
Далее процедура повторяется для вектора x . Вычисления продолжаются до тех пор, пока не окажется, что на каком-то этапе все коэффициенты замещения j 0, т.е.
получается окончательное решение. |
|
|
|
|
|
|
|
|
|
Пример 5.1. Найти минимум функции |
|
|
|
|
|
|
|||
|
F(x) x2 3x3 2x5, |
|
|
|
(5.19) |
||||
при условиях |
|
|
|
|
|
|
|
|
|
I. Все xi 0,i 1,...,6. |
|
|
|
|
|
|
|
|
|
II. Должны выполняться уравнения |
|
|
|
|
|
|
|
||
x1 3x2 |
x3 |
|
|
2x5 |
|
|
7, |
|
|
2x2 |
4x3 |
x4 |
|
|
|
|
12, |
(5.20) |
|
4x2 |
3x3 |
|
|
8x5 |
x6 |
|
10. |
|
|
В данном примере n=6,m=3. Матрица |
|
|
|
|
|
|
|
|
|
|
1 |
3 |
1 |
0 |
2 |
0 |
|
|
|
|
|
2 4 1 0 |
|
|
|
|
|||
|
А 0 |
0 |
|
|
|
||||
|
|
4 |
3 |
0 |
8 |
|
|
|
|
|
0 |
1 |
|
|
|
Решение. Начальное приближение выберем в виде
70
0
x.12
0
10
Видно, что этот вектор удовлетворяет уравнениям (5.20). Для проведения решения удобно составить таблицу (см. таблица 2.1).
Таблица 2.1. Первая итерация |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
ci |
x |
|
x2 |
x3 |
x5 |
|
x x |
|
|
|
x |
|
|
|
|
|
|
|
|
|
|||||||
1 |
0 |
7 |
|
3 |
1 |
2 |
|
7 |
10 |
|||||
2 |
1 |
0 |
|
1 |
0 |
0 |
|
0 |
0 |
|||||
3 |
3 |
0 |
|
0 |
1 |
0 |
|
|
3 |
|||||
4 |
0 |
12 |
|
2 |
4 |
0 |
|
12 4 |
0 |
|||||
5 |
2 |
0 |
|
0 |
0 |
1 |
|
0 |
0 |
|||||
6 |
0 |
10 |
|
4 |
3 |
8 |
|
10 3 |
1 |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
1 |
3 |
2 |
|
3 |
|
|
|
|
|
|
|
|
F(x) 0 |
|
|
|
|
|
|
F( |
x |
) 9 |
В 1-й столбец заносятся коэффициенты сi согласно с (5.19), во 2-й – начальный план x.
Следующий шаг состоит в записи и решении уравнения (5.13). Из вида вектора x следует, что независимые переменные x2, x3, x5, зависимые x1, x4, x6. Поэтому уравнение (5.13) следует записать в виде
x1 |
3 x2 |
x3 |
2 x5 |
|
x4 |
|
2 x2 |
4 x3 |
|
x6 |
|
4 x2 |
3 x3 |
8 x5 |
Это решение заносится в 3,4,5-й столбцы таблицы 2.1. Далее вычисляются коэффициенты замещения j . Для этого вычисляются суммы попарных произведений элементов
1-го и 3,4,5-го столбцов. Получается, что 3 0. Это отмечается с помощью *. Поэто-
му полагается: x2 0, x3 1, x5 0. В 6-й столбец заносится вектор x x , кото-
рый равен сумме 2-го столбца и 4-го, умноженного на . Параметр выбирается как min 12/4,10/3 3. В 7-й столбец заносится окончательный план, т.е. 6-й столбец при
3. В нижней строке таблицы приведены значения F x и F x . Видно, что
F x F x .
Далее выполняется вторая итерация, результаты которой заносятся в таблицу 2.2.
Таблица 2.2. Вторая итерация |
|
|
|
|
|
|
|
|
|
|
||||
|
|
ci |
x |
|
x2 |
x4 |
x5 |
|
x x |
|
|
|
x |
|
|
|
|
|
|
|
|
|
|||||||
1 |
0 |
10 |
5 2 |
1 4 |
2 |
|
10 5 2 |
|
|
0 |
||||
2 |
1 |
0 |
|
1 |
0 |
0 |
|
|
4 |
|||||
3 |
3 |
3 |
|
1 2 1 4 0 |
|
3 2 |
5 |
|||||||
4 |
0 |
0 |
|
0 |
1 |
0 |
|
0 |
0 |
|||||
5 |
2 |
0 |
|
0 |
0 |
1 |
|
0 |
0 |
|||||
6 |
0 |
1 |
|
5 2 |
3 4 8 |
|
1 5 2 |
11 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
1 2 3 4 |
2 |
|
4 |
|
|
|
|
|
|
|
|
|
F x 9 |
|
|
|
|
|
F |
x |
11 |
Теперь независимые переменные x2, x4, x5 , зависимые x1, x3, x6 .
Уравнения(5.13) для них имеют вид
x1 |
x3 |
|
3 x2 |
2 x5 |
|
|
4 x3 |
|
|
2 x2 |
x4 |
|
3 x3 |
x6 |
|
4 x2 |
8 x5 |
Их решение заносится в 3,4,5-й столбцы таблицы 2.2. Вычисляя коэффициенты замещения, получаем, что 2 0. Поэтому полагаем: x2 1, x4 0, x5 0. В 6-й столбец заносится вектор x x.
Из требования, чтобы первый элемент равнялся 0, получаем 4. В 7-й столбец заносится окончательный план. В нижней строке таблицы приведены значения F x и
F |
x |
. Видно, что F |
x |
F x , т.е. план |
x |
лучше, чем план x. |
||||||||||
Таблица 2.3. Третья итерация |
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
ci |
x |
|
x1 |
x4 |
x5 |
|
x x |
x |
|
|||
|
|
|
|
|
|
|
||||||||||
1 |
0 |
0 |
|
1 |
|
0 |
0 |
|
|
|
|
|||||
2 |
1 |
4 |
|
2 5 |
110 |
4 5 |
|
|
|
|
||||||
3 |
3 |
5 |
|
1 5 |
3 10 |
2 5 |
|
|
|
|
||||||
4 |
0 |
0 |
|
0 |
|
1 |
0 |
|
|
|
|
|||||
5 |
2 |
0 |
|
0 |
|
0 |
1 |
|
|
|
|
|||||
6 |
0 |
11 |
1 |
1 2 |
10 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
i |
|
1 5 |
8 10 |
9 |
|
|
|
|
|
|
|
|
|
|
|
|
F x 11 |
|
|
|
|
|
|
|
|
Теперь независимые переменные x1, x4, x5, зависимые x2, x3, x6 .
Уравнения(5.13) для них имеют вид
3 x2 |
x3 |
|
x1 |
2 x5 |
2 x2 |
4 x3 |
|
|
x4 |
4 x2 |
3 x3 |
x6 |
|
8 x5 |
Их решение заносится в 3,4,5-й столбцы таблицы 2.3. Вычисляя коэффициенты замещения, получаем, что все i 0. Следовательно, дальнейшее улучшение плана уже не-
возможно. Решением задачи является план, стоящий во 2-м столбце таблицы 2.3.
5.3. Выбор начального плана
Начальный план легко получить, если в матрице А можно выделить блок, состоящий из единичной матрицы. Тогда соответствующие элементы плана приравниваются к элементам вектора b . Так получен начальный план в примере 5.1. В общем случае для выбора начального плана вводятся новые переменные, которые добавляются также в функцию F x с очень большими коэффициентами. В результате после ряда применений симплекс-метода эти новые переменные будут исключены их плана, так как в функцию F x , которая минимизируется, они входят с большими коэффициентами. После этого получается начальный план для основного решения задачи.
Пример 5.2. Минимизировать функцию |
|
F(x) x1 2x2 3x3 x4 |
(5.21) |
при условиях
I. Все xi 0,i 1,...,4. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
II. Должны выполняться уравнения |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
x1 |
2x2 |
3x3 |
|
|
|
15, |
|
|
|
|
|
|
|
|
|||||
|
|
|
|
2x1 |
x2 |
5x3 |
|
|
|
20, |
|
(5.22) |
|||||||||||
|
|
|
|
x1 |
2x2 |
x3 |
x4 |
|
10. |
|
|
|
|
|
|
|
|||||||
В данном примере n=4, m=3. Введем новые переменные x5 |
и x6, и вставим их в функ- |
||||||||||||||||||||||
цию F x и уравнения (5.22). В результате получим |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
F(x) x1 2x2 3x3 x4 wx5 wx6, |
|
|
|
|
|
|
||||||||||||||
и |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x1 |
2x2 |
3x3 |
|
|
x5 |
|
|
|
|
|
15, |
|
|
|
|
|
|
|||
|
|
|
2x1 |
x2 |
5x3 |
|
|
|
|
x6 |
|
20, |
|
|
|
|
|
|
|||||
|
|
|
x1 2x2 |
x3 |
|
x4 |
|
|
|
|
|
|
10. |
|
|
|
|
|
|
||||
Здесь w – какое-то большое число. При этом матрица |
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
1 |
2 |
3 |
0 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
А |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2 1 5 |
0 0 1 . |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
2 |
1 |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
||||
Отсюда легко получить начальный план. Он занесен во 2-й столбец таблицы 3.1 |
|||||||||||||||||||||||
Таблица 3.1. Первая итерация |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
ci |
x |
|
|
x1 |
|
|
x2 |
|
x3 |
|
|
x x |
|
|
x |
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
1 |
1 |
0 |
|
|
1 |
|
|
0 |
|
|
0 |
|
|
|
|
0 |
0 |
|
|||||
2 |
2 |
0 |
|
|
0 |
|
|
1 |
|
|
0 |
|
|
|
|
0 |
0 |
|
|||||
3 |
3 |
0 |
|
|
0 |
|
|
0 |
|
|
1 |
|
|
|
|
4 |
|
||||||
4 |
1 |
10 |
|
|
1 |
|
|
2 |
|
|
1 |
|
|
10 |
6 |
|
|||||||
5 |
w |
15 |
|
|
1 |
|
|
2 |
|
|
3 |
|
|
15 3 |
3 |
|
|||||||
6 |
w |
20 |
|
|
2 |
|
|
1 |
|
5 |
|
|
20 5 |
0 |
|
||||||||
|
|
|
i |
|
2 3w 4 3w 4 8w |
|
|
4 |
|
|
|
|
|
|
|||||||||
|
|
|
F x x |
|
|
|
|
|
|
|
|
|
|
|
|
|
F |
x |
|
|
|||
|
|
|
10 35w |
|
|
|
|
|
|
|
|
|
|
|
|
6 3w |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
Теперь независимые переменные – |
x1, x2, x3, |
зависимые – |
x4, x5, x6 . |
||||||||||||||||||||
Уравнения(5.13) для них имеют вид |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
x4 |
|
x1 |
2 x2 |
x3 |
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
x5 |
|
x1 |
2 x2 |
3 x3 |
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
x6 |
2 x1 |
x2 |
5 x3 |
|
|
|
|
|
|
|
|
Их решение заносится в 3,4,5-й столбцы таблицы 3.1. В результате вычисления коэффициентов замещения, получаем, что наименьшим является коэффициент 3 4 8w.
Поэтому полагается: x1 |
x2 0, x3 1. В 6-й столбец заносится вектор x x. |
Параметр выбирается |
как min 10,15/3,20/5 4. В 7-й столбец заносится оконча- |