508
T
min
. .
,
,
1, ,
x
i
c x
s t
Ax
b l
x
u
x
Z i
k
" Î
=
L
≤
≤ ≤
(1)
式中,
n
c
Î R ,表示目标函数系数矩阵;
n
x
Î R ,表
示 决 策 变 量 , 决 策 变 量 的 前
k 个 值 取 整 数 ;
,
n
n
l
u
Î
Î
R
R 分别表示 x 取值的下、上界;
m n
A
´
Î R
,
m
b
Î R ,表示约束函数的系数矩阵。 不失一般性,
对式
(1)中的参数不确定集做如下假设:
假设 1
A 是不确定参数。令
i
J 表示矩阵 A 的第
i 行元素中不确定性系数集,即首先确定 A 的第 i 行
中有哪几列元素是不确定的,将这些列的系数构造成
一个集合。令
ij
a
% 表示矩阵 A 的第 i 行中不确定元素,
i
j J
Î
, 定 义
ij
a
% 为 对 称 有 界 的 随 机 变 量 , 则
ˆ
ˆ
[
,
]
ij
ij
ij
ij
ij
a
a
a a
a
Î
-
+
%
,
ij
a 为标称量, ˆ
ij
a 为扰动量。
假设 2
c 为不确定参数。与不确定参数 A 类似,
也可以给出
c 不确定元素的取值区间[ ,
]
j
j
j
c c
d
+
,即
j
c 表示不确定元素的标称值,
j
d 表示不确定元素相
对其标称值
j
c 的偏差。
2.2 鲁棒离散优化问题的模型转化 (Model Trans-
formation of RDO)
定理 1
考虑一个不确定线性离散优化问题(P):
T
( ) min
. .
,
,
,
1, ,
x
i
P
c x
s t
Ax
b l
x
u
x
Z i
k
" Î
=
L
≤
≤ ≤
(2)
各变量的定义符合定义
1 和假设 1, 2。则该问题
的鲁棒对等式
(P
*
)可表示成如下的优化问题
[6]
:
0
0
0
0
0
0
*
T
{ |
,| |
}
{
{ }|
,
,
\ }
( ) min
max
|
|
. .
max
ˆ
ˆ
|
| (
)
|
|
,
1
i
i
i
i
i
i
i
i
i
i
i
i
j
j
x
S S
J S
j S
ij
j
S
t S
J S
t J S
j
ij
j
i
i
it
t
i
j S
i
i
P
c x
d x
s t
a x
a x
a
x
b
l
x
u
x
Z
i
Í
G
Î
Í
= G
Î
ê ú
ë û
Î
"
ì
ü
+
í
ý
î
þ
+
ì
ü
+ G - G
ê ú
í
ý
ë û
î
þ
Î " =
å
å
å
U
≤
≤
≤ ≤
, , k
K
(3)
其中,目标函数中,
0
{ |
0}
j
J
j d
=
>
,
0
J 表示 c 内不
确 定 元 素 的 个 数 ,
0
0
[0,
]
J
G
Î
。 约 束 条 件 中 ,
ˆ
{ |
0}
i
ij
J
j a
=
>
,
i
J 表 示 不 确 定 元 素 的 个 数 ,
[0,
]
i
i
J
G
Î
,
i
G
ê ú
ë û 表示小于
i
G 的最大整数。
定理 2
RDO 模型转化定理。公式(3)所示的不
确定
RDO 问题,等价于下述确定性混合整数规划问
题
[6]
:
0
T
0
0
0
min
. .
i
j
j J
x
ij
j
i
i
ij
i
j
j J
c x z
p
s t
a x
z
p
b
i
G
G
Î
Î
+
+
+
+
"
å
å
å
≤
0
0
0
ˆ
0,
,
0
,
0,
0
1, ,
j
j
j
i
ij
ij
j
i
j
j
j
j
j
j
i
ij
j
i
i
z
p
d y
j J
z
p
a y
i
j J
y
x
y
j
l
x
u
j
i j J
p
i j
y
z
i
k
x
Z
+
" Î
+
" ¹
Î
-
"
"
"
Î
" "
=
Î
K
≥
≥
≤
≤
≤
≤
≥
≥
≥
(4)
式中,
y z p
, , 为松弛变量。
Bertsimas 理论最大的特点是鲁棒对等式的转化
不增加问题的求解复杂度,使得该理论更容易应用到
实际问题中。由于鲁棒对等式的等价式
(4)中引入了松
弛变量
, ,
y z p ,且取值是连续的,因此鲁棒离散优化
的对等问题是一个混合整数规划。
3 电梯群控调度问题的鲁棒离散优化模型
(RDO Model of Elevator Group Scheduling
Problem)
针对第一节所述的电梯群控调度中存在的不确
定性问题,本文将电梯群控调度建模为一个不确定优
化问题。考虑当前和未来交通流状况,把交通流作为
不确定因素,结合
RDO 理论,确定其决策变量、不
确定参数集、目标函数以及约束函数,从而建立电梯
群控调度问题的
RDO 模型,继而进行模型转化。
3.1 电 梯 群 控 鲁 棒 离 散 优 化 模 型 的 建 立 (RDO
Model Setup)
3.1.1
模型变量与参数定义(Variable List of Model)
为便于模型表达,按
4 部梯 16 层楼的电梯群控
系统配置,定义如下变量、参数:
m: 楼层数, 取
16
m
=
;
n: 电梯部数, 取
4
n
= ;
Ui
p : 当 前 时 刻 第 i 层 上 外 呼 乘 客 数 标 称 值 ,
1, 2, ,
1
i
m
=
-
L
;
ˆ
Ui
p : 当 前 时 刻 第 i 层 上 外 呼 乘 客 扰 动 值 ,
ˆ
0,
1, 2, ,
1
Ui
p
i
m
>
=
-
L
;
Dj
p : 当 前 时 刻 第 j 层 下 外 呼 乘 客 数 标 称 值 ,
2,3, ,
j
m
=
L ;
ˆ
Dj
p : 当 前 时 刻 第 j 层 下 外 呼 乘 客 数 扰 动 值 ,
ˆ
0,
2,3, ,
Dj
p
j
m
>
=
L ;
Ui
P :第 i 层上外呼数(不确定参数)
1, 2, ,
1
i
m
=
-
L
;
[
]
1
2
1
U
U
U
Um
P
P
P
P
-
=
L
;
:
Dj
P
第
j 层下外呼数(不确定参数)
2,3, ,
j
m
=
L ;
[
]
2
3
D
D
D
Dm
P
P
P
P
=
L
;
,
1, ,
1;
1, , ;
1
0
Ui k
x
i
m
k
n
k
i
k
i
ìï
= í
ïî
=
-
=
L
L
,表示派第 部电梯响应第 层上外呼
,表示不派第 部梯响应第 层上外呼