线性规划

问题描述

  • 已知
    • 变量向量 $\boldsymbol{x}$
    • 上约束 $A_{\mathrm{ub}}\boldsymbol{x}\leq \boldsymbol{b}_{\mathrm{ub}}$
    • 等约束 $A_{\mathrm{eq}}\boldsymbol{x} \leq \boldsymbol{b}_{\mathrm{eq}}$
    • 变量约束 bounds (l, u) $:=$ $\boldsymbol{l} \leq \boldsymbol{x} \leq \boldsymbol{u}$
  • 欲求
    • 线性表达式 $\boldsymbol{c}^{T}\boldsymbol{x}$ 的最值

求解

1
2
3
from scipy.optimize import linprog

res = linprog(c, A_ub, b_ub, A_eq, b_eq, bounds) # 更多参数见manual
例子

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
from scipy.optimize import linprog
import numpy as np

def main():
    c = np.array([-2,-3,5]).transpose()    #行列向量不影响求解
    A = np.array([[-2,5,-1],[1,3,1]])
    b = np.array([-10,12])
    Aeq = np.array([[1,1,1]])    # 单个约束也要表示为矩阵形式
    beq = np.array([7])
    x = linprog(c,A,b,Aeq,beq,method='highs',bounds=np.array([[0,None],[0,None],[0,None]]))
    print(x)