线性规划
在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济
效益的问题。若目标函数及约束条件均为线性函数,则称为线性规划(Linear Programming 简记 LP)。
可行解:满足约束条件的解。
可行预:所有可行解构成的集合称为问题的可行域,记为R。
图解法:
图解法简单直观,有助于了解线性规划问题求解的基本原理。可得到如下结论:
(1)可行域 R 可能会出现多种情况。 R 可能是空集也可能是非空集合,当 R 非空
时,它必定是若干个半平面的交集。 R 既可能是有界区域,也可能是无界区域。
(2)在 R 非空时,线性规划既可以存在有限最优解,也可以不存在有限最优解(其
目标函数值无界)。
(3)若线性规划存在有限最优解,则必可找到具有最优目标函数值的可行域 R 的“顶点”。
整数规划
规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,变量限制为整数,则称为整数线性规划。目前所流行的求解整数规划的方法,往往只适用于整数线性规划。
如不加特殊说明,一般指整数线性规划。对于整数线性规划模型大致可分为两类:
- 变量全限制为整数时,称纯(完全)整数规划。
- 变量部分限制为整数的,称混合整数规划。
整数规划特点
- 原线性规划有最优解,当自变量限制为整数后,其整数规划解出现下述情况:
①原线性规划最优解全是整数,则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
③有可行解(当然就存在最优解),但最优解值变差。 - 整数规划最优解不能按照实数最优解简单取整而获得。
求解方法分类
- 分枝定界法—可求纯或混合整数线性规划。
- 割平面法—可求纯或混合整数线性规划。
- 隐枚举法—求解“0-1”整数规划:
①过滤隐枚举法;
②分枝隐枚举法。 - 匈牙利法—解决指派问题(“0-1”规划特殊情形)。
- 蒙特卡洛法—求解各种类型规划。
(1)分枝定界法
对有约束条件的最优化问题(其可行解为有限数)的所有可行解空间恰当地进行系统搜索,这就是分枝与定界内容。通常,把全部可行解空间反复地分割为越来越小的子集,称为分枝;并且对每个子集内的解集计算一个目标下界(对于最小值问题),这称为定界。在每次分枝后,凡是界限超出已知可行解集目标值的那些子集不再进一步分枝,这样,许多子集可不予考虑,这称剪枝。
设有最大化的整数规划问题 A ,与它相应的线性规划为问题 B ,从解问题 B 开始,若其最优解不符合 A 的整数条件,那么 B 的最优目标函数必是 A 的最优目标函数z* 的上界,记作 z- ;而 A 的任意可行解的目标函数值将是z* 的一个下界 z_ 。分枝定界法就是将 B 的可行域分成子区域的方法。逐步减小 z- 和增大 z_ ,最终求到z* 。
(2) 割平面法
(3) 隐枚举法(“0-1”整数规划)
(i) 先试探性求一个可行解,易看出(1,0,0)满足约束条件,故为一个可行解,且 z= 3 。
(ii) 因为是求极大值问题,故求最优解时,凡是目标值 z<3 的解不必检验是否满足约束条件即可删除,因它肯定不是最优解,于是应增加一个约束条件(目标值下界):
(iii) 改进过滤条件。
(iv) 由于对每个组合首先计算目标值以验证过滤条件,故应优先计算目标值 z 大的组合,这样可提前抬高过滤门槛,以减少计算量。
(4) 匈牙利法
匈牙利算法python代码:
import numpy as np
from scipy.optimize import linear_sum_assignment
cost = np.array([[3,5,8,4], [6,8,5,4], [2,5,8,5],[9,2,5,2]])
row_ind, col_ind = linear_sum_assignment(cost)
print(row_ind) # 开销矩阵对应的行索引
print(col_ind) # 对应行索引的最优指派的列索引
print(cost[row_ind, col_ind]) # 提取每个行索引的最优指派列索引所在的元素,形成数组
print(cost[row_ind, col_ind].sum()) # 数组求和
'''
输出:
[0 1 2 3]
[3 2 0 1]
[4 5 2 2]
13
'''
(5) 蒙特卡洛法(随机取样法)
是指使用随机数(或更常见的伪随机数)来解决很多计算问题的方法。
尽管整数规划由于限制变量为整数而增加了难度;然而又由于整数解是有限个,于是为枚举法提供了方便。当然,当自变量维数很大和取值范围很宽情况下,企图用显枚举法(即穷举法)计算出最优值是不现实的,但是应用概率理论可以证明,在一定的计算量的情况下,完全可以得出一个满意解。
指派问题的计算机求解
整数规划问题的求解可以使用 Lingo 等专用软件。对于一般的整数规划问题,无法
直接利用 Matlab 的函数,必须利用 Matlab 编程实现分枝定界解法和割平面解法。但对
于指派问题等 1 0− 整数规划问题,可以直接利用 Matlab 的函数 bintprog 进行求解。
非线性规划
如果目标函数或约束条件中包含非线性函数,就称这种规划问题为非线性规划问
题。
线性规划与非线性规划的区别:
如果线性规划的最优解存在,其最优解只能在其可行域的边界上达到(特别是可行
域的顶点上达到);而非线性规划的最优解(如果最优解存在)则可能在其可行域的任意一点达到。文章来源:https://www.toymoban.com/news/detail-458766.html
- FUN是用M文件定义的函数f(x)
- x0是x的初始值
- A,B,Aeq,Beq定义了线性约束,若没有则为空
- LB和UB是变量x的下界和上界
- NONLCON是用M文件定义的非线性向量函数C(x),Ceq(x)
- OPTIONS定义了优化参数,可以使用Matlab 缺省的参数设置。
二次规划
若某非线性规划的目标函数为自变量 x 的二次函数,约束条件又全是线性的,就称
这种规划为二次规划。
返回值 X 是决策向量 x 的值,返回值 FVAL 是目标函数在 x 处的值。文章来源地址https://www.toymoban.com/news/detail-458766.html
到了这里,关于数学建模整理-线性规划、整数规划、非线性规划的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!