【学习笔记】Matlab和python双语言的学习(最大最小化规划）

文章目录

• 前言
• 一、最大最小化规划
• 二、选址问题
• 三、代码实现----Matlab
• • 1.Matlab 的 `fminimax` 函数
  • 2.Matlab 代码
• 四、代码实现----python
• 总结

前言

通过模型算法，熟练对Matlab和python的应用。
学习视频链接：
https://www.bilibili.com/video/BV1EK41187QF?p=28&vd_source=67471d3a1b4f517b7a7964093e62f7e6

一、最大最小化规划

• 在博弈论中有一个经典理论 ——— 最大最小策略（Minimax strategy)，是由博弈论奠基人约翰·冯·诺伊曼（John von Neumann）在1928年提出的一种在理性行为基础上做的保守博弈策略：使得博弈者的最小收入最大化的策略。由此衍生出了最大最小算法（Minimax算法），是一种找出失败的最大可能性中的最小值的算法（即最小化对手的最大得益）。在实际问题中也有许多求最大值的最小化问题，例如急救中心选址问题就是要规划其到所有地点最大距离的最小值，在投资规划中要确定最大风险的最低限度等，为此，对每个，我们先求出目标值 f i ( x ) f_i(x) fi​(x) 的最大值，然后再求这些最大值中的最小值。
• 最大最小化问题的一般数学模型：
  m i n { m a x [ f 1 ( x ) ] , m a x [ f 2 ( x ) ] , … , m a x [ f m ( x ) ] } s . t . { A x ≤ b A e q ⋅ x = b e q C ( x ) ≤ 0 C e q ( x ) = 0 V L B ≤ X ≤ V U B min\left\{max\Big[f_1\left(x\right)\Big],max\Big[f_2\left(x\right)\Big],\ldots,max\Big[f_m\left(x\right)\Big]\right\}\\s.t.\begin{cases}Ax\leq b\\Aeq\cdot x=beq\\C\left(x\right)\leq0\\Ceq\left(x\right)=0\\VLB\leq X\leq VUB\end{cases} min{max[f1​(x)],max[f2​(x)],…,max[fm​(x)]}s.t.⎩ ⎨ ⎧​Ax≤bAeq⋅x=beqC(x)≤0Ceq(x)=0VLB≤X≤VUB​

二、选址问题

• 设某城市有某种物品的 10 个需求点，第 i 个需求点 P I P_I PI​ 的坐标 ( a i , b i ) (a_i,b_i) (ai​,bi​)，道路网与坐标轴平行，彼此正交，现打算建一个该物品的供应中心，且由于受到城市某些条件的限制，该供应中心只能设在 x 界于 [3,8]，y 界于 [4,10] 的范围之内，问该中心应建在何处为好？

• 设供应中心的位置为 ( x , y ) (x,y) (x,y)，要求它到最远需求点的距离尽可能小，由于道路网与坐标轴平行，彼此正交，故采用沿道路行走计算距离，可知每个需求点 P i P_i Pi​, 到该中心的距离为 ∣ x − a i ∣ + ∣ y − b i ∣ |x-a_i|+|y- b_i| ∣x−ai​∣+∣y−bi​∣，于是模型为： min ⁡ ( x , y ) { max ⁡ i [ ∣ x − a i ∣ + ∣ y − b i ∣ ] } s . t . { 3 ≤ x ≤ 8 4 ≤ y ≤ 10 \min_{(x,y)}\left\{\max_i\left[\left|x-a_i\right|+\left|y-b_i\right|\right]\right\}\\s.t.\begin{cases}3\leq x\leq8\\4\leq y\leq10\end{cases} (x,y)min​{imax​[∣x−ai​∣+∣y−bi​∣]}s.t.{3≤x≤84≤y≤10​

三、代码实现----Matlab

1.Matlab 的 fminimax 函数

fminimax 函数的基本语法如下：

[x, fval] = fminimax(fun, x0, A, b, Aeq, beq, lb, ub, nonlcon)

输入参数基本与非线性规划 fmincon 函数几乎一致，但目标函数需要用函数向量表示。

2.Matlab 代码

%% 最大最小化规划的函数
% [x,fval] = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,noncon,options)
% x0 表示给定的初始值(用行向量或者列向量表示),必须得写
% A b 表示线性不等式约束
% Aeq beq 表示线性等式约束
% lb ub 表示上下界约束
% fun 表示目标函数,需要用函数向量表示
% nonlcon 表示非线性约束的函数
% option 表示求解非线性规划使用的方法

x0 = [5,5]; % 在给定范围内
lb = [3,4];
ub = [8,10];
[x,fval] = fminimax(@fun,x0,[],[],[],[],lb,ub)

function f = fun(x)
    f = zeros(10,1);
    a = [1 4 3 5 9 12 6 20 17 8];
    b = [2 10 8 18 1 4 5 10 8 9];
    for i = 1:10
        f(i) = abs(x(1) - a(i)) + abs(x(2) - b(i));
    end
end

运行结果：

即：中心应建在 (8.0，8.5) 处，最远需求点的距离为 13.5。

四、代码实现----python

在Python中，有几个库可以用于求解类似于MATLAB中 fminimax 的多目标优化问题。fminimax 是用于求解最小化最大目标函数值的问题。在Python中，SciPy 和 CVXPY 等库可以用来进行这种类型的优化。

本文使用 SciPy，SciPy 库中的 minimize 函数可以通过自定义目标函数来实现类似 fminimax 的功能。我们可以定义一个目标函数，该函数返回多个目标函数的最大值，然后使用 minimize 进行优化。

import numpy as np
from scipy.optimize import minimize

# 定义要最小化的目标函数：目标是最小化多个目标函数的最大值
def fun(x):
    f = np.zeros((10,))
    a = np.array([1, 4, 3, 5, 9, 12, 6, 20, 17, 8])
    b = np.array([2, 10, 8, 18, 1, 4, 5, 10, 8, 9])
    for i in range(10):
        f[i] = abs(x[0] - a[i]) + abs(x[1] - b[i])
    return np.max(f)

# 初始猜测
x0 = np.array([7, 7])

bounds = [(3,8),(4,10)]

# 使用SLSQP优化器进行优化
result = minimize(fun, x0, bounds=bounds , method='SLSQP')

print("Optimal value:", result.fun)
print("Optimal solution:", result.x)

运行结果：

总结

本文介绍了最大最小化规划，并通过选址问题作为示例建立模型，分别使用Matlab和python进行代码编写。