1.原理介绍

♥原理解释均来此百度百科

1)单纯形法

一般线性规划问题中当线性方程组的变量数大于方程个数,这时会有不定数量的解,而单纯形法是求解线性规划问题的通用方法。
具体步骤是,从线性方程组找出一个个的单纯形,每一个单纯形可以求得一组解,然后再判断该解使目标函数值是增大还是变小了,决定下一步选择的单纯形。通过优化迭代,直到目标函数实现最大或最小值。
换而言之,单纯形法就是秉承“保证每一次迭代比前一次更优”的基本思想:先找出一个基本可行解,对它进行鉴别,看是否是最优解;若不是,则按照一定法则转换到另一改进后更优的基本可行解,再鉴别;若仍不是,则再转换,按此重复进行。因基本可行解的个数有限,故经有限次转换必能得出问题的最优解。如果问题无最优解,也可用此法判别。

2)大M法

在线性规划问题的约束条件中加人工变量后,要求在目标函数中相应地添加认为的M或一M为系数的项。在极大化问题中,对人工变量赋于一M作为其系数;在极小化问题中,对人工变量赋于一个M作为其系数,M为一任意大(而非无穷大)的正数。把M看作一个代数符号参与运算,用单纯形法求解,故称此方法为大M法。
应用单纯形法在改进目标函数的过程中,如果原问题存在最优解,必然使人工变量逐步变为非基变量,或使其值为零。否则,目标函数值将不可能达到最小或最大。在迭代过程中,若全部人工变量变成非基变量,则可把人工变量所在的列从单纯形表中删去,此时便找到原问题的一个初始基可行解。若此基可行解不是原问题的最优解,则继续迭代,直至所有的检验数都小于等于0,求得最优解为止。

3)拉格朗日乘法

在数学最优问题中,拉格朗日乘数法(以数学家约瑟夫·路易斯·拉格朗日命名)是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。这种方法将一个有n 个变量与k 个约束条件的最优化问题转换为一个有n + k个变量的方程组的极值问题,其变量不受任何约束。这种方法引入了一种新的标量未知数,即拉格朗日乘数:约束方程的梯度(gradient)的线性组合里每个向量的系数。此方法的证明牵涉到偏微分,全微分或链法,从而找到能让设出的隐函数的微分为零的未知数的值。
设给定二元函数z=ƒ(x,y)和附加条件φ(x,y)=0,为寻找z=ƒ(x,y)在附加条件下的极值点,先做拉格朗日函数 ,其中λ为参数。
令F(x,y,λ)对x和y和λ的一阶偏导数等于零,即
F'x=ƒ'x(x,y)+λφ'x(x,y)=0
F'y=ƒ'y(x,y)+λφ'y(x,y)=0
F'λ=φ(x,y)=0
由上述方程组解出x,y及λ,如此求得的(x,y),就是函数z=ƒ(x,y)在附加条件φ(x,y)=0下的可能极值点。
若这样的点只有一个,由实际问题可直接确定此即所求的点。

2.Excel求解

1)大M法求解


2)使用规划求解包求解


算出x1,x2,x3的值:

看出来与大M法结果是相同的。

3.python的编程求解

1)单纯法求解线性规划

代码直接给出:

import numpy as np
def pivot():
    l = list(d[0][:-2])
    jnum = l.index(max(l)) #转入编号
    m = []
    for i in range(bn):
        if d[i][jnum] == 0:
            m.append(0.)
        else:
            m.append(d[i][-1]/d[i][jnum])
    inum = m.index(min([x for x in m[1:] if x!=0]))  #转出下标
    s[inum-1] = jnum
    r = d[inum][jnum]
    d[inum] /= r
    for i in [x for x in range(bn) if x !=inum]:
        r = d[i][jnum]
        d[i] -= r * d[inum]
def solve():
    flag = True
    while flag:
        if max(list(d[0][:-1])) <= 0: #直至所有系数小于等于0
            flag = False
        else:
            pivot()
def printSol():
    for i in range(cn - 1):
        if i in s:
            print("x"+str(i)+"=%.2f" % d[s.index(i)+1][-1])
        else:
            print("x"+str(i)+"=0.00")
    print("objective is %.2f"%(-d[0][-1]))
d = np.loadtxt("data1.txt", dtype=np.float)
(bn,cn) = d.shape
s = list(range(cn-bn,cn-1)) #基变量列表
solve()
printSol()

填写好需要的数据:

在nodejupyter中运行代码:cmd运行jupyter notebook
结果如下:

相同约束条件下,再次运行:

from scipy import optimize
import numpy as np
#确定c,A_ub,B_ub
c = np.array([1,14,6])
A_ub = np.array([[1,1,1],[1,0,0],[0,0,1],[0,3,1]])
B_ub = np.array([4,2,3,6])
res =optimize.linprog(-c,A_ub,B_ub)
print(res)

结果:

2)scipy求解线性规划

from scipy import optimize as op
import numpy as np
c=np.array([2,1,1])
A_ub=np.array([[0,-2,-1],[0,1,-1]])#不等式的系数
B_ub=np.array([2,1])#不等式的结果
A_eq=np.array([[1,-1,1]])#等式的系数
B_eq=np.array([2])#等式的结果
x1=(0,5)
x2=(0,5)
x3=(0,5)
res=op.linprog(c,A_ub,B_ub,A_eq,B_eq,bounds=(x1,x2,x3))
print(res)

结果:

3)非线性规划

如下代码:

# coding=utf-8
from scipy.optimize import minimize
import numpy as np
# demo 2
#计算  (2+x1)/(1+x2) - 3*x1+4*x3 的最小值  x1,x2,x3的范围都在0.1到0.9 之间
def fun(args):
    a,b,c,d=args
    v=lambda x: (a+x[0])/(b+x[1]) -c*x[0]+d*x[2]
    return v
def con(args):
    # 约束条件 分为eq 和ineq
    #eq表示 函数结果等于0 ; ineq 表示 表达式大于等于0  
    x1min, x1max, x2min, x2max,x3min,x3max = args
    cons = ({'type': 'ineq', 'fun': lambda x: x[0] - x1min},\
              {'type': 'ineq', 'fun': lambda x: -x[0] + x1max},\
             {'type': 'ineq', 'fun': lambda x: x[1] - x2min},\
                {'type': 'ineq', 'fun': lambda x: -x[1] + x2max},\
            {'type': 'ineq', 'fun': lambda x: x[2] - x3min},\
             {'type': 'ineq', 'fun': lambda x: -x[2] + x3max})
    return cons
if __name__ == "__main__":
    #定义常量值
    args = (2,1,3,4)  #a,b,c,d
    #设置参数范围/约束条件
    args1 = (0.1,0.9,0.1, 0.9,0.1,0.9)  #x1min, x1max, x2min, x2max
    cons = con(args1)
    #设置初始猜测值
    x0 = np.asarray((0.5,0.5,0.5))
    res = minimize(fun(args), x0, method='SLSQP',constraints=cons)
    print(res.fun)
    print(res.success)
    print(res.x)

结果:

完成!!!!!!

对比单纯法和调用库

直接调用python库采用了与单纯法相同的约束条件,对比出来结果是相同的,基本没有误差!
参考博客:波波
- 觉得不错的记得点个赞再走哦!!