0. 绪论

运筹优化的基本模型思路通常分为两部，需要解决"确定最佳方案""求出最佳的配比"此类的"最值"问题。对于优化类的问题,如何建模与如何算法求解也是最重要的部分。两个核心内容: 优化建模,下降算法。

我们涉及的优化模型由三个基本组成:

• 决策变量 $x_1,x_2,\cdots ,x_n$——影响目标的自变量$,$

• 目标函数 $f(x_1,x_2,\cdots ,x_n)$——确定最佳决策的指标依据$,$

• 约束条件 $c_i(x_1,x_2,\cdots ,x_n)⩽(=,⩾)0$——现实中的限制.

通常尽可能多的采用向量语言: 如利用向量 $\mathbf{x}=(x_1,x_2,\cdots ,x_n{)}^T$ 表示决策变量$,$ 或利用矩阵来表达如下的约束

A x ⩽ b ⇔ { a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n ⩽ b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n ⩽ b 2 ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n ⩽ b m , A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m n ] . A\boldsymbol{x}\leqslant \boldsymbol{b}\Leftrightarrow

,A=. Ax⩽b⇔⎩ ⎨ ⎧​a11​x1​+a12​x2​+⋯+a1n​xn​⩽b1​a21​x1​+a22​x2​+⋯+a2n​xn​⩽b2​⋮am1​x1​+am2​x2​+⋯+amn​xn​⩽bm​​,A=⎣ ⎡​a11​a21​⋮am1​​a12​a22​⋮am2​​⋯⋯⋱⋯​a1n​a2n​⋮amn​​⎦ ⎤​.

此外$,$ 我们用 $R,R^n$ 代表实数域以及 $n$ 维实数 (向量) 空间$,f:R^n\to R$ 代表 $n$ 元实值函数.

用规范化的语言$,$ 我们现实中遇到的所有优化问题都可描述为如下的形式:

  min ⁡ f ( x ) s . t . { c i ( x ) ⩽ 0 , i = 1 , 2 , ⋯   , m c j ( x ) = 0 , j = 1 , 2 , ⋯   , k

 s.t.​minf(x){ci​(x)⩽0,i=1,2,⋯,mcj​(x)=0,j=1,2,⋯,k​​(0.1)(0.2)​

其中$,\mathbf{x}\in R^n,f:R^n\to R,$ 并且我们不要求目标函数 $f$ 以及约束函数 $c_i,c_j$ 有什么多余的性质如可微 (这一点对刚入门的初学者而言是比较反直觉的)$,$ 对于求极大值的问题$,$ 可以等价写为

$$\max f(\mathbf{x})\iff \min -f(\mathbf{x}).$$

优化问题 $0.1$ 中$,$ 约束 $0.2$ 构成的子集称为可行域 $D,$ $D$ 中的点是符合 $0.1$ 要求的点$,$ 称为可行解$,$ 令 $f(\mathbf{x})$ 最小的可行解 ${\mathbf{x}}_0$ 称为最优解$,$ 我们一般用

a r g m i n { f ( x ) ∣ x ∈ D } \mathrm{argmin} \{f(\boldsymbol{x})\mid \boldsymbol{x}\in D\} argmin{f(x)∣x∈D}

记为 $0.1$ 的最优解. 当 $D=R^n$ 时 $0.1$ 称为无约束优化问题$,$ 相应地 $D⊊R^n$ 时称之为约束优化问题.

我们涉及的下降算法基本思想是生成一列递减的点 { x n } n = 1 ∞ \{\boldsymbol{x}_n\}_{n=1}^{\infty} {xn​}n=1∞​ 来逼近 $0.1$ 的最优解$,$ 一般由以下几步组成:

1. 确定初始解 ${\mathbf{x}}_1$.

2. 确定迭代方式 ${\mathbf{x}}_{n+1}=g({\mathbf{x}}_n)$ 使得 $f({\mathbf{x}}_{n+1})⩽f({\mathbf{x}}_n),n=1,2,\cdots$.

3. 确定终止准则 (计算机只能迭代有限点$,$ 我们希望在有限步能尽可能接近最优解)——当 ${\mathbf{x}}_n$ 与 $f({\mathbf{x}}_n)$ 满足什么条件时$,$ 认为 ${\mathbf{x}}_n$ 最小值的近似点$,$ 终止算法.

迭代方式是下降算法最核心的一步$,$ 它决定算法生成的点列能否收敛得到最优解$,$ 迭代步长决定算法收敛的速度 (即算法运行的时间)$,$ 这在求解实际的优化问题过程中是非常关键的内容.

本课程介绍的是最简单的一类优化问题: 目标函数与约束条件都是线性的$,$ 称为线性规划问题(模型)$,$ 在日常生活中蕴含着非常多地线性规划问题$,$ 如生产策略$,$ 工作指派等等$,$ 所以建立线性规划模型事实上是在现实生活中非常常见的$,$ 而由于性质的优越$,$ 线性规划问题的下降算法设计也是非常简单的——即我们接下来要学习的单纯形法与分支定界法.

1. 线性规划（上）

🎯作业二：请你仿照上面代码，尝试求解以下模型？

$$\min W_{order}+W_{trans}$$
s . t . { x 3 = z 3 , 9 + + z 3 , 10 + + z 3 , 10 − , x 4 = z 4 , 10 + + z 4 , 10 − + z 4 , 11 − , x i ⩽ s i , i = 3 , 4 , x 3 + x 4 = 780 , z 3 , 9 + ⩾ 0 , z 4 , 11 − ⩾ 0 , z i , 10 + ⩾ 0 , z i , 10 − ⩾ 0 , i = 3 , 4 , s.t.

s.t.⎩ ⎨ ⎧​x3​=z3,9+​+z3,10+​+z3,10−​,x4​=z4,10+​+z4,10−​+z4,11−​,xi​⩽si​,i=3,4,x3​+x4​=780,z3,9+​⩾0,z4,11−​⩾0,zi,10+​⩾0,zi,10−​⩾0,i=3,4,​
其中
$$W_{order}=155x_3+160x_4,$$
$$W_{trans}=73.3z_{3,9+}+101.1(z_{3,10+}+z_{3,10-})+93.1(z_{4,10+}+z_{4,10-})+78.9z_{4,11-}.$$

# 代码如下

## 导入线性求解器，线性和整数求解的API都在其中
from ortools.linear_solver import pywraplp


## 声明求解器
solver = pywraplp.Solver.CreateSolver('GLOP')


## 创建变量 
infinity = solver.infinity()

x2 = solver.IntVar(0.0, infinity, 'z3_9ad')
x7 = solver.IntVar(0.0, infinity, 'z4_11re')

x4 = solver.IntVar(0.0, infinity, 'z3_10ad')
x6 = solver.IntVar(0.0, infinity, 'z4_10ad')

x3 = solver.IntVar(0.0, infinity, 'z3_10re')
x5 = solver.IntVar(0.0, infinity, 'z4_10re')

x0 = solver.IntVar(0.0, 1000, 'x3')
x1 = solver.IntVar(0.0, 2000, 'x4')

print('`NumVar`说明该变量是连续型变量，前面两个参数分别是该变量取值的上下界.如果没有上界的话设置为`solver.infinity()`. ')
print('变量个数 =', solver.NumVariables())


## 添加约束
solver.Add(x0 + x1 == 780)
solver.Add(x2 + x4 + x3 == x0)
solver.Add(x6 + x5 + x7 == x1)

print('约束个数 =', solver.NumConstraints())


## 定义目标函数
solver.Minimize( (155 * x0 +160 * x1) + (73.3 * x2 + 101.1 * (x3 + x4) + 93.1*(x5 + x6) + 78.9*x7) )


## 调用求解器
status = solver.Solve()

if status == pywraplp.Solver.OPTIMAL:
    print('\n最优值 =', solver.Objective().Value())
    print('x3', x0.solution_value())
    print('x4', x1.solution_value())
    print('z3_9ad', x2.solution_value())
    print('z3_10re', x3.solution_value())
    print('z3_10ad', x4.solution_value())
    print('z4_10re', x5.solution_value())
    print('z4_10ad', x6.solution_value())
    print('z4_11re', x7.solution_value())
else:
    print('The problem does not have an optimal solution.')
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

没有上界的话设置为`solver.infinity()`. 
变量个数 = 8
约束个数 = 3

最优值 = 178074.0
x3 780.0
x4 0.0
z3_9ad 780.0
z3_10re 0.0
z3_10ad 0.0
z4_10re 0.0
z4_10ad 0.0
z4_11re 0.0
1
2
3
4
5
6
7
8
9
10
11
12
13

参考内容

Github课程链接