基于求解器设置线性规划 -凯发k8网页登录

基于求解器设置线性规划

将问题转换为求解器形式

此示例说明如何使用基于求解器的方法将问题从数学形式转换为 optimization toolbox™ 求解器语法。虽然这里的示例是线性规划问题，但这些方法适用于所有求解器。

问题中的变量和表达式表示一家化工厂的运作模型，该模型来自 edgar 和 himmelblau 合著的 [1] 中的一个示例。我们提供了两个视频来说明该问题。

以图形形式展示该问题。它用图形说明如何生成模型说明的数学表达式。
说明如何将这些数学表达式转换为 optimization toolbox 求解器语法。此视频说明如何求解该问题，以及如何解释结果。

此示例的其余部分只涉及将问题转换为求解器语法。此示例与视频的内容相近。视频和示例的主要区别在于，此示例说明如何使用命名变量或索引变量，这些变量类似于哈希键。这种差异体现在将变量合并成一个向量中。

模型说明

视频建议将问题转换为数学形式的一种方法是：

全面了解问题
确定目标（最大化或最小化某个函数）
确定（命名）变量
确定约束
确定可以控制哪些变量
用数学表示法指定所有量
检查模型的完整性和正确性

有关本节中变量的含义，请观看视频。

此优化问题是在约束条件下最小化目标函数，问题和约束均以表达式列出。

目标函数是：

0.002614 hps 0.0239 pp 0.009825 ep。

约束是：

2500 ≤ p1 ≤ 6250
i1 ≤ 192,000
c ≤ 62,000
i1 - he1 ≤ 132,000
i1 = le1 he1 c
1359.8 i1 = 1267.8 he1 1251.4 le1 192 c 3413 p1
3000 ≤ p2 ≤ 9000
i2 ≤ 244,000
le2 ≤ 142,000
i2 = le2 he2
1359.8 i2 = 1267.8 he2 1251.4 le2 3413 p2
hps = i1 i2 bf1
hps = c mps lps
lps = le1 le2 bf2
mps = he1 he2 bf1 - bf2
p1 p2 pp ≥ 24,550
ep pp ≥ 12,000
mps ≥ 271,536
lps ≥ 100,623
所有变量均为正。

求解方法

要求解优化问题，请执行以下步骤。

关于这些步骤，还可观看视频。

选择求解器

要找到求解此问题的合适求解器，请参考优化决策表。该表要求您根据目标函数的类型和约束的类型对问题进行分类。对于此问题，目标函数是线性的，约束也是线性的。决策表推荐使用求解器。

如由 optimization toolbox 函数处理的问题或函数参考页中所述，linprog 求解器可求解以下形式的问题

\min_{x} f^{t} x such that {\begin{matrix} a \cdot x \leq b, \\ a e q \cdot x = b e q, \\ l b \leq x \leq u b . \end{matrix}

(1)

f^tx 表示由常量组成的行向量 f 乘以由变量组成的列向量 x。换言之，
f^tx = f(1)x(1) f(2)x(2) ... f(n)x(n)，
其中，n 是 f 的长度。
a x ≤ b 表示线性不等式。a 是 k×n 矩阵，其中 k 是不等式的数目，n 是变量的数目（大小为 x）。b 是长度为 k 的向量。有关详细信息，请参阅。
aeq x = beq 表示线性等式。aeq 是一个 m×n 矩阵，其中 m 是等式的个数，n 是变量的个数（大小为 x）。beq 是长度为 m 的向量。有关详细信息，请参阅。
lb ≤ x ≤ ub 表示向量 x 中的每个元素必须大于 lb 的对应元素，并且必须小于 ub 的对应元素。有关详细信息，请参阅。

如函数参考页所示，求解器的语法是

[x fval] = linprog(f,a,b,aeq,beq,lb,ub);

linprog 求解器的输入是公式 1 中的矩阵和向量。

将变量合并成一个向量

模型说明的方程中有 16 个变量。将这些变量放入一个向量中。由变量组成的向量的名称在公式 1 中是 x。决定阶次，并基于变量构造 x 的分量。

以下代码使用变量名称组成的元胞数组来构造向量。

variables = {'i1','i2','he1','he2','le1','le2','c','bf1',...
    'bf2','hps','mps','lps','p1','p2','pp','ep'};
n = length(variables); 
% create variables for indexing 
for v = 1:n 
   eval([variables{v},' = ', num2str(v),';']); 
end

执行这些命令会在工作区中创建以下命名变量：

listing of variables: bf1 = 8, bf2 = 9, and so forth

这些命名变量表示 x 分量的索引编号。您不必创建命名变量。视频显示如何使用 x 分量的索引编号来轻松求解问题。

编写边界约束

在模型说明的方程中有四个变量包含下界，六个变量包含上界。下界：

p1 ≥ 2500
p2 ≥ 3000
mps ≥ 271,536
lps ≥ 100,623。

此外，所有变量均为正，这意味着其下界为零。

创建由 0 组成的下界向量 lb，然后添加其他四个下界。

lb = zeros(size(variables));
lb([p1,p2,mps,lps]) = ...
    [2500,3000,271536,100623];

具有上界的变量有：

p1 ≤ 6250
p2 ≤ 9000
i1 ≤ 192,000
i2 ≤ 244,000
c ≤ 62,000
le2 ≤ 142000。

创建由 inf 组成的上界向量，然后添加六个上界。

ub = inf(size(variables));
ub([p1,p2,i1,i2,c,le2]) = ...
   [6250,9000,192000,244000,62000,142000];

编写线性不等式约束

模型说明的方程中有三个线性不等式：

i1 - he1 ≤ 132,000
ep pp ≥ 12,000
p1 p2 pp ≥ 24,550。

为了使方程具有 a x≤b 形式，需要将所有变量放在不等式的左侧。所有这些方程均已采用该形式。在适当情况下，通过乘以 –1，确保每个不等式均为“小于”形式：

i1 - he1 ≤ 132,000
-ep - pp ≤ -12,000
-p1 - p2 - pp ≤ -24,550。

在您的 matlab^® 工作区中，将 a 矩阵创建为 3×16 零矩阵，对应于采用 16 个变量的 3 个线性不等式。创建具有三个分量的 b 向量。

a = zeros(3,16);
a(1,i1) = 1; a(1,he1) = -1; b(1) = 132000;
a(2,ep) = -1; a(2,pp) = -1; b(2) = -12000;
a(3,[p1,p2,pp]) = [-1,-1,-1];
b(3) = -24550;

编写线性等式约束

模型说明的方程中有八个线性方程：

i2 = le2 he2
lps = le1 le2 bf2
hps = i1 i2 bf1
hps = c mps lps
i1 = le1 he1 c
mps = he1 he2 bf1 - bf2
1359.8 i1 = 1267.8 he1 1251.4 le1 192 c 3413 p1
1359.8 i2 = 1267.8 he2 1251.4 le2 3413 p2。

为了使方程具有 aeq x=beq 形式，需要将所有变量放在方程的一侧。方程变为：

le2 he2 - i2 = 0
le1 le2 bf2 - lps = 0
i1 i2 bf1 - hps = 0
c mps lps - hps = 0
le1 he1 c - i1 = 0
he1 he2 bf1 - bf2 - mps = 0
1267.8 he1 1251.4 le1 192 c 3413 p1 - 1359.8 i1 = 0
1267.8 he2 1251.4 le2 3413 p2 - 1359.8 i2 = 0。

现在编写对应于这些方程的 aeq 矩阵和 beq 向量。在您的 matlab 工作区中，将 aeq 矩阵创建为 8×16 零矩阵，对应于包含 16 个变量的 8 个线性方程。创建具有八个分量且值均为零的 beq 向量。

aeq = zeros(8,16); beq = zeros(8,1);
aeq(1,[le2,he2,i2]) = [1,1,-1];
aeq(2,[le1,le2,bf2,lps]) = [1,1,1,-1];
aeq(3,[i1,i2,bf1,hps]) = [1,1,1,-1];
aeq(4,[c,mps,lps,hps]) = [1,1,1,-1];
aeq(5,[le1,he1,c,i1]) = [1,1,1,-1];
aeq(6,[he1,he2,bf1,bf2,mps]) = [1,1,1,-1,-1];
aeq(7,[he1,le1,c,p1,i1]) = [1267.8,1251.4,192,3413,-1359.8];
aeq(8,[he2,le2,p2,i2]) = [1267.8,1251.4,3413,-1359.8];

编写目标

目标函数是

f^tx = 0.002614 hps 0.0239 pp 0.009825 ep。

将此表达式写成由 x 向量的乘数组成的向量 f：

f = zeros(size(variables));
f([hps pp ep]) = [0.002614 0.0239 0.009825];

使用 linprog 求解问题

您现在已经有 linprog 求解器所需的输入。调用该求解器并以设定的格式打印输出：

options = optimoptions('linprog','algorithm','dual-simplex');
[x fval] = linprog(f,a,b,aeq,beq,lb,ub,options);
for d = 1:n
  fprintf('.2f \t%s\n',x(d),variables{d}) 
end
fval

结果为：

optimal solution found.
   136328.74 	i1
   244000.00 	i2
   128159.00 	he1
   143377.00 	he2
        0.00 	le1
   100623.00 	le2
     8169.74 	c
        0.00 	bf1
        0.00 	bf2
   380328.74 	hps
   271536.00 	mps
   100623.00 	lps
     6250.00 	p1
     7060.71 	p2
    11239.29 	pp
      760.71 	ep
fval =
  1.2703e 03

检查解

fval 输出提供目标函数在任何可行点的最小值。

解向量 x 是目标函数具有最小值的点。请注意：

bf1、bf2 和 le1 为 0，该值是它们的下界。
i2 为 244,000，该值是它的上界。
f 向量的非零分量为
- hps — 380,328.74
- pp — 11,239.29
- ep — 760.71

视频根据原始问题给出这些特征的解释。

参考书目

[1] edgar, thomas f., and david m. himmelblau. optimization of chemical processes. mcgraw-hill, new york, 1988.

基于求解器设置线性规划 -凯发k8网页登录