Жолобов Ввведение в Математическое 2008
.pdf
|
|
n |
|
|
|
|
|
|
|
cj xj |
|
|
|
|
|
|
Z= |
j 1 |
max |
|
(1.105) |
||
|
n |
|
|||||
|
|
d j xj |
|
|
|
|
|
|
|
j 1 |
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
aij x j ai |
(i |
1, m |
) |
|
(1.106) |
|
|
j 1 |
|
|
|
|
|
|
|
xj 0 (j=1 n ). |
|
(1.107) |
||||
|
|
|
|
n |
|
|
|
При этом предполагается, |
что d j x j 0 |
и, кроме того, |
|||||
|
|
|
|
j 1 |
|
|
|
n |
|
|
|
|
|
|
|
d j x j 0 |
в области неотрицательных решений системы уравне- |
||||||
j 1 |
|
|
|
|
|
|
|
|
|
|
n |
|
|
||
ний (1.106). Заметим, что условие d j x j 0 |
в этой области не |
j 1
нарушает общности задачи, так как в противном случае знак минус всегда можно отнести к числителю.
Для этой задачи характерны следующие свойства. Как и в случае задачи ЛП, своего максимального значения ЦФ (1.105) достигает в одной из вершин выпуклого многогранника, определяемого ограничениями (1.106) и (1.107) (естественно, при условии, что задача имеет решение). Если же ЦФ принимает максимальное значение более, чем в одной вершине, то она достигает это значение в любой точке, являющейся выпуклой линейной комбинацией данных вершин.
Эти свойства хорошо иллюстрируются путем геометрической интерпретации задачи ДЛП.
1.5.1. Геометрическая интерпретация задачи дробно-линейного программирования
Рассмотрим случай двух переменных:
Z c1 x1 c2 x2 max d1 x1 d2 x2
ai1x1 ai2 x2 ai (i=1,2,...,m) x1, x2 0
181
Будем считать, что в области допустимых решений (D) имеет место d1x1+ d2x2 0.
Для того чтобы найти решение задачи, сначала построим многогранник решений, определенный ограничениями задачи
(рис.1.24).
x2 Z=Zmax
Z = h
Z=Zmin
x1
Рис.1.24. Геометрическая интерпретация задачи ДЛП
Положим значение ЦФ равным некоторому числу h. То есть ЦФ будет принимать одно и то же значение во всех точках прямой
c1 x1 c2 x2 h или d1 x1 d2 x2
(с1-d1h)x1+(с2-d2h)x2=0. (1.108)
Очевидно, что эта прямая проходит через начало координат. Для того чтобы найти допустимые решения, на которых ЦФ принимает значение h, прямая должна иметь общие точки с многоугольником.
Начнем увеличивать параметр h. Увеличение этого параметра приведет к вращению прямой (1.108) вокруг начала координат либо по, либо против часовой стрелки, в зависимости от сочетания параметров cj , dj (j=1,2).
Из геометрических соображений ясно, что если допустимое множество ограничено, при некотором значении h=h* прямая (1.108) станет опорной к допустимому множеству. При этом в точке (точках) касания будет достигнуто искомое оптимальное решение.
182
x2 |
Fmax |
|
B
A
x1
Рис.1.25. Случай бесконечного количества оптимальных решений
На рис. 1.25 представлен случай, когда максимум ЦФ достигается в любой точке отрезка [A,B].
Представляет интерес случай, когда допустимое множество не ограничено. Здесь возможны следующие ситуации.
A) Допустимое множество не ограничено, однако существуют вершины, в которых ЦФ принимает соответственно максимальное и минимальное значение (рис.1.26).
x2 Fmax
Fmin
x1
Рис.1.26. Пример задачи ДЛП для случая А
B) Допустимое множество не ограничено, и один из экстремумов не достигается. Например, минимум достигается в одной из вершин, а максимум не достигается вообще (рис.1.27).
183
x2 Fmax
Fmin
x1
Рис.1.27. Случай асимптотического максимума
Это – случай асимптотического максимума.14
В принципе, возможна ситуация, когда имеет место и асимптотический максимум и асимптотический минимум (рис.1.28).
Fmax
x2
Fmin
x1
Рис.1.28. Случай асимптотического максимума и минимума
14 Будет большой ошибкой, если этот случай считать случаем неограниченности ЦФ сверху. Здесь ЦФ ограничена сверху, но граница эта недостижима!
184
1.5.2. Сведение задачи ДЛП к задаче ЛП
Пусть дана задача ДЛП:
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
cj xj |
|
|
|
|
|
|
|
|
||
|
Z= |
j 1 |
|
max |
(1.109) |
|||||||
n |
|
|||||||||||
|
|
d j xj |
|
|
|
|
|
|
|
|
||
|
|
j 1 |
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
|
aij x j |
ai , |
(i |
|
|
) |
|
|
|
|||
1, m |
(1.110) |
|||||||||||
|
j 1 |
|
|
|
|
|
|
|
|
|
|
|
|
xj 0, (j=1 n). |
(1.111) |
||||||||||
Кроме того, предполагается, что в области неотрицатель- |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
n |
|
ных решений системы уравнений (1.110) имеет место d j x j 0 . |
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
j 1 |
|
Это предположение требует, чтобы имело место |
|
|
||||||||||
{x |
nj 1 d j x j 0 ; nj 1 aij x j ai , i |
|
; x j 0, j |
|
} , |
|||||||
1, m |
1, n |
|||||||||||
где x (x1, x2 ,..., xn ). |
|
|
|
|
|
|
|
|
|
|
||
Примем обозначение: |
|
|
1 |
|
|
|
|
|
|
|
||
|
y |
|
|
. |
|
|
|
|
|
|
||
|
n |
|
|
|
|
|
|
|
||||
0 |
|
|
|
|
|
|
|
(1.112) |
||||
|
|
|
|
d j xj |
||||||||
|
|
|
|
|
|
|||||||
|
|
|
|
j 1 |
|
|
|
|
|
|
|
|
Кроме того, введем новые переменные: |
|
|
||||||||||
|
yj=y0xj (j=1 n) |
(1.113) |
или |
xj |
y j |
. |
|
|||
|
|
y0 |
Из (1.112) имеем
n
y0 d j xj 1.
j 1
Подставим в это выражение xj y j y0
n
. Получим d j y j 1 .
j 1
185
Теперь исходная задача приобретает следующий вид:
|
n |
|
|
|
||
F* c j y j max |
||||||
|
j 1 |
|
|
|
||
n |
|
|
|
|
|
|
aij y j |
ai y0 0, |
(i |
|
) |
||
1, m |
||||||
j 1 |
|
|
|
|
|
|
|
n |
|
|
|
||
|
d j y j 1 |
|
|
|
||
|
j 1 |
|
|
|
||
y j 0 |
( j |
|
|
y0 0. |
||
1, n); |
Это – задача линейного программирования. Решив эту задачу любым известным методом, всегда можно восстановить оптимальное решение исходной задачи (1.109)-(1.111).
Пример 1.30
Решить задачу ДЛП:
|
2x1 |
3x2 |
max, |
|
|
x |
x |
2 |
|
|
|
|||
1 |
|
|
||
x1 |
-x3 |
|
=4, |
|
|
x2 |
+ x4=8, |
xj 0, j=1 4.
Вводим переменную y0 |
|
|
1 |
. |
|
|
|||
|
|
x1 |
x2 |
Производим замену переменных: yj = y0 xj .
Приходим к следующей эквивалентной задаче ЛП:
2y1+3y2 max |
|||
y1 |
- |
y3 |
- 4y0 = 0 |
y2 |
+ y4 |
- 8y0 = 0 |
|
y1 |
+ y2 |
|
= 1 |
yj 0, j=0 4.
Переходим к М-задаче (одновременно вектор A3 делаем единичным базисным вектором, умножая на "-1" первое уравнениеограничение):
2y1+3y2 |
- My5 max |
|||
-y1 |
+ y3 |
+ 4y0 = 0 |
||
y2 |
+ y4 |
- 8y0 |
= 0 |
|
y1 |
+ y2 |
+ y5 = 1 |
yj 0, j=0 5.
Решим эту задачу, для разнообразия придав M конкретное большое значение 100.
186
|
|
|
|
|
2 |
|
3 |
0 |
|
0 |
|
|
-100 |
0 |
Баз |
Сбаз |
|
A0 |
A1 |
|
A2 |
A3 |
|
A4 |
|
A5 |
A6 |
||
A3 |
0 |
|
0 |
|
-1 |
|
0 |
1 |
|
0 |
|
|
0 |
4 |
A4 |
0 |
|
0 |
|
0 |
|
1 |
0 |
|
1 |
|
|
0 |
-8 |
A5 |
-100 |
|
1 |
|
1 |
|
1 |
0 |
|
0 |
|
|
1 |
0 |
Табл. 1 |
|
|
-100 |
|
-102 |
|
-103 |
0 |
|
0 |
|
|
0 |
0 |
A3 |
0 |
|
0 |
|
-1 |
|
0 |
1 |
|
0 |
|
|
0 |
4 |
A2 |
3 |
|
0 |
|
0 |
|
1 |
0 |
|
1 |
|
|
0 |
-8 |
A5 |
-100 |
|
1 |
|
1 |
|
0 |
0 |
|
-1 |
|
|
1 |
8 |
Табл. 2 |
|
|
-100 |
|
-102 |
|
0 |
0 |
|
103 |
|
0 |
-824 |
|
A6 |
0 |
|
0 |
|
-1/4 |
|
0 |
1/4 |
|
0 |
|
|
0 |
1 |
A2 |
3 |
|
0 |
|
-2 |
|
1 |
2 |
|
1 |
|
|
0 |
0 |
A5 |
-100 |
|
1 |
|
3 |
|
0 |
-2 |
|
-1 |
|
|
1 |
0 |
Табл.3 |
|
|
-100 |
|
-308 |
|
0 |
206 |
|
103 |
|
0 |
0 |
|
A6 |
0 |
|
1/12 |
|
0 |
|
0 |
1/12 |
|
-1/12 |
1/12 |
1 |
||
A2 |
3 |
|
2/3 |
|
0 |
|
1 |
2/3 |
|
1/3 |
|
|
2/3 |
0 |
A1 |
2 |
|
1/3 |
|
1 |
|
0 |
-2/3 |
|
-1/3 |
|
1/3 |
0 |
|
Табл.4 |
|
|
8/3 |
|
0 |
|
0 |
2/3 |
|
1/3 |
|
|
308/3 |
0 |
Решение эквивалентной задачи: |
|
|
|
|
|
|
|
|||||||
|
|
|
y1=1/3, y2=2/3, y0=y6=1/12; Zопт=8/3. |
|
||||||||||
Решение исходной задачи: |
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
x1=y1/y0=1/3:1/12=4; |
|
|
|
||||||
|
|
|
|
|
x2=y2/y0=2/3:1/12=8; |
|
|
|
||||||
|
|
|
|
|
|
|
Zопт=8/3. |
|
|
|
|
|
|
|
Геометрическая интерпретация |
|
|
|
|
|
|
|
|||||||
|
|
|
x1 - x3 =4 |
|
|
x3 = x1 - 4 0 |
|
|||||||
|
|
|
x2 + x4 =8 |
|
|
x4 = 8 - x2 0 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
x1 |
4; |
|
||
|
|
|
|
|
|
|
|
|
|
x2 |
8. |
|
||
|
|
x2 |
Zmax=8/3 |
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
x1 |
|
187
1.5.3. Задача ДЛП со свободными членами в числителе и знаменателе
Задача со свободными членами имеет вид
n
c0 cj xj
Z= |
j 1 |
|
max |
(1.114) |
||
n |
|
|||||
|
d0 d j xj |
|
|
|
|
|
|
j 1 |
|
|
|
|
|
n |
|
|
|
|
|
|
aij x j ai |
(i |
|
) |
|
||
1, m |
(1.115) |
|||||
j 1 |
|
|
|
|
|
|
|
xj 0 (j=1 n ). |
(1.116) |
||||
Кроме того, предполагается, |
что в области неотрицательных |
n
решений системы уравнений (1.115) имеет место d0 d j x j 0 .
|
|
|
|
|
|
|
|
|
j 1 |
Примем обозначение: |
1 |
|
|
|
|||||
|
|
|
|
y0 |
|
|
. |
|
|
|
|
|
|
|
n |
|
(1.117) |
||
|
|
|
|
|
d0 d j xj |
||||
|
|
|
|
|
|
||||
|
|
|
|
|
|
j 1 |
|
|
|
Введем новые переменные: |
|
|
|
||||||
|
|
|
|
yj=y0xj |
(j=1 n) |
(1.118) |
|||
|
xj y . |
|
|
|
|
||||
или |
|
y j |
|
|
|
|
|
||
0 |
|
|
|
|
n |
. Подставим в это вы- |
|||
Из |
|
|
|
|
|||||
(1.117) имеем: d0 y0 |
y0 d j xj 1 |
||||||||
|
|
|
|
|
|
|
j 1 |
|
|
|
xj y j . Получим |
|
n |
|
|||||
ражение |
d0 y0 |
d j y j |
1 . Теперь исходная |
||||||
|
|
y0 |
|
|
j 1 |
|
задача приобретает следующий вид:
188
|
|
|
|
|
n |
|
|
|
|
|
|
|
F* c0 y0 cj y j |
max |
|||||||||||
|
|
|
|
|
j 1 |
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
ai y0 aij y j 0, |
(i |
1, m |
) |
|||||||||
|
|
|
j 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
d0 y0 d j y j |
1 |
||||||||||
|
|
|
|
j 1 |
|
|
|
|
|
|
||
y j 0 ( j |
|
|
|
y0 0. |
||||||||
1, n); |
|
|||||||||||
Рассмотрим геометрическую интерпретацию этой задачи, для |
||||||||||||
чего возьмем случай двух переменных: |
|
|
|
|
|
|
||||||
Z |
c0 |
c1 x1 |
c2 x2 |
max |
||||||||
|
d x |
|
||||||||||
|
d |
0 |
d |
2 |
x |
|
|
|
||||
|
|
1 |
1 |
|
|
|
2 |
|
|
|
||
ai1x1 ai2 x2 |
ai (i=1,2,...,m) |
|||||||||||
Будем считать, что в |
x1,x2 0. |
допустимых решений (D) |
||||||||||
области |
|
имеет место d0+ d1x1+ d2x2 0.
Положим значение ЦФ равным некоторому числу h. То есть ЦФ будет принимать одно и то же значение во всех точках прямой
c0 c1 x1 |
c2 x2 |
h или |
|
||||||
|
|
|
|||||||
d |
0 |
d x |
d |
2 |
x |
2 |
|
|
|
|
1 |
1 |
|
|
(с0-hd0)+(с1-d1 h)x1+(с2-d2 h)x2=0. |
|
|||
|
|
|
|
|
|
|
|
(1.119) |
Для того чтобы найти допустимые решения, на которых ЦФ принимает значение h, прямая должна иметь общие точки с многоугольником допустимых решений.
Начнем увеличивать параметр h. Увеличение этого параметра приведет к вращению прямой (1.119) вокруг некоторой точки
x (x1, x2 ) либо по, либо против часовой стрелки, в зависимости от сочетания параметров cj , dj (j=0,1,2).
189
Координаты точки x (x1, x2 ) определяются следующим образом15 (рис.1.29):
x1 c0 d2 c2 d0 ,
c1d2 c2 d1
x2 c1d0 c0 d1 .
c1d2 c2d1
x2
x ( x1 , x 2 )
x1
Рис.1.29. Геометрическая интерпретация задачи ДЛП со свободными членами
Из геометрических соображений ясно, что, если допустимое множество ограничено, при некотором значении h=h* прямая (1.119) станет опорной к допустимому множеству. При этом в точке (точках) касания будет достигнуто искомое оптимальное решение.
Контрольные вопросы и задачи к разделу 1.5
1. Как при решении задачи дробно-линейного программирования интерпретировать случай, когда перменная y0=0 в оптимальном решении эквивалентной задачи линейного программирования?
15 Действительно, если h=0, то c0 c1x1 c2 x2 0. Если h= , то d0 d1x1 d2 x2 0.
Решаем систему из двух уравнений с двумя неизвестными. Получаем решение.
190