2629
.pdf3.ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
3.1.Задача линейного программирования
Пример. Пусть техническое задание на проектирование системы управления сформулировано следующим образом.
Разность между значением показателя качества 2 и удвоенным значением показателя качества 1 была не больше 2. Разность между значением показателя качества 1 и удвоенным значением показателя качества 2 была не больше 2. Сумма показателей 1,2 не больше 5.
Разница между показателями 1,2 была минимальной. Найти соответствующие неотрицательные значения показателей 1,2.
Формализуем техническое задание в виде системы ограни-
чений [19, 20]:
2x x |
2, |
|
|
||
|
1 |
|
2 |
|
|
x1 |
2x2 |
2, |
|
(3.1) |
|
x |
x |
5, |
|
||
1 |
2 |
|
|
|
|
|
x1 |
|
|
|
|
x2 |
min. |
|
Введём дополнительные неизвестные с целью получения системы равенств:
2x1 x2 x3 2, |
|
|
||||
x |
2x |
2 |
x 2, |
|
|
|
1 |
|
|
4 |
|
|
|
|
x2 |
x5 |
5, |
|
(3.2) |
|
x1 |
|
|||||
q |
(x |
x ) min, |
|
|
||
|
2 |
|
1 |
|
|
|
|
q (x2 x1 ) x1 x2 |
|
|
|||
q' |
max. |
|
Имеем три уравнения и пять неизвестных. Выразим переменные х3, х4, х5 через х1, х2:
51
x 2 2x x , |
|
|
||||
|
3 |
1 |
2 |
|
|
|
x4 2 x1 2x2 , |
|
(3.3) |
||||
x |
5 x x , |
|
|
|||
|
5 |
1 |
2 |
|
|
|
|
|
q x1 |
x2 |
|
|
|
q' |
max. |
|
3.2. Графическое решение задачи линейного программирования
Приняв х3, х4, х5 = 0 в (3.3), переобозначим переменные для получения геометрической интерпретации задачи оптимизации на плоскости:
x |
2 |
2x ; |
|
||||
|
21 |
|
2 x |
1 |
|
|
|
x22 |
|
1 |
; |
(3.4) |
|||
|
|
|
|
2 |
|
|
|
x |
|
5 |
x ; |
|
|
||
|
23 |
|
|
1 |
|
|
|
x |
x . |
|
|
|
|||
|
24 |
|
1 |
|
|
|
Графическая (геометрическая) интерпретация (4) представлена на рис. 3.1:
а) с указанными областями значений х3, б) с указанными областями значений х3, х4, х5 и выделенным «пятиугольником» допустимых решений
Красная линия – график x21 2 2x1 соответствует условию х3=0. Что будет при нарушении этого условия?
Для x21 2 2x1 на рис. 3.1 выделена цветом область,
где х3<0.
Проверим:
1 2 2x1 x2 , x2 3 2x1.
При нулевом значении x1 получаем 3, а не 2, т.е. красная линия смещается вверх.
52
а
б
Рис. 3.1. Геометрическая интерпретация задачи оптимизации
53
Невыделенная цветом область соответствует х3>0:
1 2 2x1 x2 , x2 1 2x1.
Следовательно, красная линия смещается вниз. |
|
|
|
|||
Аналогично ведут себя линии |
x |
2 x1 |
(х4 = 0) и |
x |
23 |
5 x |
|
||||||
|
22 |
2 |
|
|
1 |
|
|
|
|
|
|
|
(х5 = 0).
Линия четвёртого уравнения x24 x1 может «двигаться»,
пересекая пятиугольник, образованный рассмотренными выше тремя уравнениями (рис. 3.2).
а) x24 (x1 ) x1
б) x24 (x1 ) x1 3
в) x24 (x1 ) x1 3
Рис. 3.2. Максимизация x1 x2 : а – x24 (x1 ) x1 ,
б – x24 (x1 ) x1 3 , в – x24 (x1 ) x1 3
54
Таким образом, максимальное значение x1 x2 при ограничениях
x3 2 2x1 x2 , x4 2 x1 2x2 , x5 5 x1 x2 .
достигается при x1 4, x2 1 (рис. 3.3).
Рис. 3.3. Нахождение максимального значения разности x1 x2 , x1 4, x2 1
Мы решили задачу линейного программирования графически- получили неотрицательные значения переменных при заданных ограничениях, т.е. техническое задание на проектирование системы выполнено.
Для решения оптимизационной задачи алгебраически предложен так называемый симплекс-метод (simplex algorithm). Метод был разработан американским математиком Джорджем Данцигом (George Dantzig) в 1947 г. [21].
3.3. Симплекс-метод решения задачи линейного программирования
Существо симплекс-метода (Simplex Algorithm) состоит в следующем [19–21]. Прежде всего находится некоторое допустимое – базисное решение. Его можно найти, приняв какие-либо n–m переменных за свободные, приравняв их к нулю и решив получившуюся систему уравнений. Напомним, что n – число неизвестных, а m – число уравнений.
55
Если после этого некоторые базисные переменные окажутся отрицательными, то нужно выбрать другие свободные переменные, т.е. перейти к новому базису.
После того, как найдено допустимое базисное решение, проверяется, не достигнут ли максимум целевой функции. Если нет, то ищут новое допустимое базисное решение, но не любое, а такое, которое увеличивает значение целевой функции. После чего процедура повторяется.
Рассмотрим ту же систему уравнений, для которой надо найти неотрицательное решение:
2x x x |
2, |
|
|||
|
1 |
2 |
3 |
|
|
x1 |
2x2 x4 2, |
|
|||
x |
x |
x |
5, |
|
|
1 |
2 |
5 |
|
|
|
|
|
|
|
x1 ) x1 x2 |
|
q ' q (x2 |
max. |
Поскольку n – m = 2, то в качестве свободных можно взять, например, х1, х2.
Приняв их равными нулю, находим базисное решение:
x1
x2
x3
x4x5
q '
0; |
|
|
0; |
|
|
|
|
|
2; |
|
|
|
|
|
2; |
|
|
|
|
|
5; |
|
|
x |
x |
|
0. |
||
1 |
2 |
|
Это решение допустимо, поскольку переменные неотрицательны. Проверку того, не достигнут ли максимум, можно выполнить путём поиска нового допустимого базисного решения, при котором целевая функция будет больше.
Для перехода к новому допустимому базисному решению одну из свободных переменных х1, х2 следует сделать базисной. В нашем примере переменная х1 входит в выражение целевой
56
функции со знаком +. Значит, максимум целевой функции не достигнут, и переменную х1 следует сделать базисной. Возьмём систему уравнений:
x3x4
x5q '
2 2x1 x2 , |
|
2 x1 2x2 , |
|
|
|
5 x1 x2 , |
|
|
|
q x1 x2 |
|
max. |
Из этой системы видно, что при х2 = 0 увеличение х1 не приводит к уменьшению х3, но уменьшает х4, х5. Так что при х1 = 2 получим:
x1
x2
x3
x4x5
q '
2; |
|
|
0; |
|
|
|
|
|
6; |
|
|
|
|
|
0; |
|
|
|
|
|
3; |
|
|
x |
x |
|
2. |
||
1 |
2 |
|
Таким образом, делаем свободной х4 и переходим к новому базису х1, х3, х5.
Выразим систему уравнений относительно нового базиса. В правой части уравнений должны остаться х2, х4.
Из второго уравнения получим х1:
x1 2 x4 2x2 .
Подставим это уравнение в первое и третье вместо х1:
x3 2 2(2 x4 2x2 ) x2 ,x5 5 (2 x4 2x2 ) x2 .
Получим:
x3 6 2x4 3x2 ,x5 3 x4 3x2 .
57
Выполним подстановку и в целевую функцию:
q' 2 x4 2x2 x2 2 x2 x4 max .
Получаем следующую систему:
x 2 |
2x |
x |
|
, |
|
1 |
2 |
|
4 |
|
|
x3 6 3x2 2x4 , |
|
||||
x 3 |
3x |
x |
|
, |
|
5 |
2 |
4 |
|
|
|
|
x2 x4 |
|
|
|
|
q ' 2 |
max. |
Анализируем результат.
Переменная х2 входит в выражение целевой функции со знаком +. Значит, максимум целевой функции не достигнут, и переменную х2 следует сделать базисной. Пусть х2 = 1:
x1
x2
x3
x4x5
q '
2;
1;
9;
0;
0;
3.
Новый базис х1, х2, х3. Поэтому в правой части должны остаться х4, х5. Возвращаемся к исходной системе уравнений:
2x1 x2 x3 2,x1 2x2 x4 2,x1 x2 x5 5,
q ' q (x2 x1 ) x1 x2
Выражаем х1, х2, х3 через х4, х5:
x |
2x x 2, |
||
1 |
2 |
4 |
|
x3 2 x2 2x1, |
|
||
x |
5 x |
x . |
|
2 |
5 |
1 |
|
max.
58
Подставляем выражение х2 в х1:
x1 2(5 x5 x1 ) x4 2
10 2x5 2x1 x4 2 12 2x5 2x1 x4 2.
Отсюда
3x1 12 x4 2x5
или
|
4 |
1 |
x4 |
|
2 |
x5 |
|
x1 |
3 |
3 |
. |
||||
|
|
|
|
|
|
Подставим это выражение в выражение для х2:
|
5 |
x5 4 |
|
1 |
x4 |
2 |
x5 |
|
|||
x2 |
3 |
3 |
. |
||||||||
|
|
|
|
|
|
|
|
|
|
||
Получим |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
1 |
x4 |
1 |
x5 |
|
|
|
|
|
x2 |
3 |
3 |
. |
|
||||||
|
|
|
|
|
|
|
|
|
|
Наконец, выражения для х1 и х2 подставим в выражение для х3:
|
2 1 |
1 |
x4 |
|
1 |
x5 2(4 |
1 |
x4 |
|
2 |
|
x3 |
3 |
3 |
3 |
3 |
x5 ) . |
||||||
|
|
|
|
|
|
|
|
Тогда
x3 9 x4 x5 ) ,
т.е.
x1 4 13 x4 23 x5 ;
x 1 1 x 1 x ;2 3 4 3 5
x3 9 x4 x5 .
59
Определим целевую функцию через х4, х5:
q ' x x |
|
4 |
1 x |
|
2 x |
1 |
1 x |
|
|
1 x |
|
||||||
|
1 |
|
2 |
|
|
3 |
4 |
|
3 |
5 |
|
3 |
4 |
|
3 |
5 |
|
|
2 x |
|
|
1 x . |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
3 |
4 |
|
3 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таким образом, при увеличении х4, х5 целевая функция уменьшается.
Поэтому при данном базисе достигается максимум целевой функции и решение имеет вид:
x1
x2
x3
x4x5
q '
4;
1;
9;
0;
0;
3.
3.4. Табличный симплекс-метод решения задачи линейного программирования [19, 20]
Преобразуем систему уравнений
x 2 2x x , |
|
|
|
|||||
|
3 |
|
|
1 |
2 |
|
|
|
x4 2 x1 2x2 , |
|
|
|
|||||
x |
|
5 x x , |
|
|
|
|||
|
5 |
|
|
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
q ' |
q x1 x2 max. |
|
||||||
к виду |
|
|
|
|
|
|
|
|
|
q ' 0 ( x x ), |
|
|
|||||
|
|
|
|
|
1 |
2 |
|
|
|
x3 |
2 ( 2x1 x2 ), |
(3.5) |
|||||
|
x |
2 |
(x |
2x ), |
|
|||
|
|
4 |
|
1 |
|
2 |
|
|
|
x |
5 |
(x |
x |
). |
|
|
|
|
|
5 |
|
1 |
2 |
|
|
60