python编写凸函数 python函数编程200例

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

python实现资产配置(1)----Markowitz 投资组合模型

现假设有A, B, C, D, E五只股票的收益率数据((第二日收盘价-第一日收盘价)/第一日收盘价)), 如果投资人的目标是达到20%的年收益率,那么该如何进行资产配置,才能使得投资的风险最低?

更一般的问题,假设现有x 1 ,x 2 ,...,x n , n支风险资产,且收益率已知,如果投资人的预期收益为goalRet,那么该如何进行资产配置,才能使得投资的风险最低?

1952年，芝加哥大学的Markowitz提出现代资产组合理论(Modern Portfolio Theory，简称MPT)，为现代西方证券投资理论奠定了基础。其基本思想是，证券投资的风险在于证券投资收益的不确定性。如果将收益率视为一个数学上的随机变量的话，证券的期望收益是该随机变量的数学期望（均值），而风险可以用该随机变量的方差来表示。

对于投资组合而言，如何分配各种证券上的投资比例，从而使风险最小而收益最大？

答案是将投资比例设定为变量，通过数学规划，对每一固定收益率求最小方差，对每一个固定的方差求最大收益率，这个多元方程的解可以决定一条曲线，这条曲线上的每一个点都对应着最优投资组合，即在给定风险水平下，收益率最大，这条曲线称作“有效前沿” (Efficient Frontier)。

对投资者而言，不存在比有效前沿更优的投资组合，只需要根据自己的风险偏好在有效前沿上寻找最优策略。

简化后的公式为:

其中 p 为投资人的投资目标,即投资人期待的投资组合的期望值. 目标函数说明投资人资产分配的原则是在达成投资目标 p 的前提下,要将资产组合的风险最小化,这个公式就是Markowitz在1952年发表的'Portfolio Selection'一文的精髓,该文奠定了现代投资组合理论的基础,也为Markowitz赢得了1990年的诺贝尔经济学奖. 公式(1)中的决策变量为w i , i = 1,...,N, 整个数学形式是二次规划(Quadratic Programming)问题,在允许卖空的情况下(即w i 可以为负,只有等式约束)时,可以用拉格朗日(Lagrange)方法求解。

有效前缘曲线如下图:

我们考虑如下的二次规划问题

运用拉格朗日方法求解,可以得到

再看公式(1),则将目标函数由 min W T W 调整为 min 1/2(W T W), 两问题等价,写出的求解矩阵为:

工具包: CVXOPT python凸优化包

函数原型: CVXOPT.solvers.qp(P,q,G,h,A,b)

求解时,将对应的P,q,G,h,A,b写出,带入求解函数即可.值得注意的是输入的矩阵必须使用CVXOPT 中的matrix函数转化,输出的结果要使用 print(CVXOPT.solvers.qp(P,q,G,h,A,b)['x']) 函数才能输出。

这里选取五支股票2014-01-01到2015-01-01的收益率数据进行分析.

选取的五支股票分别为: 白云机场, 华夏银行, 浙能电力, 福建高速, 生益科技

先大体了解一下五支股票的收益率情况:

看来，20%的预期收益是达不到了。

接下来,我们来看五支股票的相关系数矩阵：

可以看出，白云机场和福建高速的相关性较高，因为二者同属于交通版块。在资产配置时，不利于降低非系统性风险。

接下来编写一个MeanVariance类，对于传入的收益率数据，可以进行给定预期收益的最佳持仓配比求解以及有效前缘曲线的绘制。

绘制的有效前缘曲线为：

将数据分为训练集和测试集，并将随机模拟的资产配比求得的累计收益与测试集的数据进行对比，得到：

可以看出，在前半段大部分时间用Markowitz模型计算出的收益率要高于随机模拟的组合，然而在后半段却不如随机模拟的数据，可能是训练的数据不够或者没有动态调仓造成的，在后面写策略的时候，我会加入动态调仓的部分。

股票分析部分：

Markowitz 投资组合模型求解

蔡立专：量化投资——以python为工具. 电子工业出版社

相关问答

Q1: python非线性规划用什么模块

python非线性规划用什么模块本文使用SciPy的optimize模块来求解非线性规划问题，结合实际例子，引入非线性规划问题的求解算法及相应函数的调用。

本文提纲一维搜索／单变量优化问题

无约束多元优化问题

非线性最小二乘问题

约束优化问题

非线性规划问题的目标函数或约束条件是非线性的。本文使用SciPy的optimize模块来求解非线性规划问题。

目标函数和约束条件是否连续光滑是非常重要的性质，这是因为如果光滑，则所有决策变量可微，多变量函数的偏导数组成的向量为梯度，梯度是指向目标函数增长最快的方向。将目标函数梯度作为搜索方向，对非线性规划问题的求解具有重要的意义。这些函数或其导数\梯度的不连续性给许多现有的非线性优化问题的求解带来了困难。在下文中，我们假设这些函数是连续且光滑的。

# Importing Modules

from scipy import optimize

import matplotlib.pyplot as plt

import numpy as np

import sympy

1、一维搜索／单变量优化问题(Univariate Optimization)

无约束非线性规划最简单的形式是一维搜索。一维搜索通常作为多维优化问题中的一部分出现，比如梯度下降法中每次最优迭代步长的估计。求解一维搜索常用的两类方法是函数逼近法和区间收缩法。其中函数逼近法是指用较简单的函数近似代替原来的函数，用近似函数的极小点来估计原函数的极小点，比如牛顿法；区间收缩法对于一个单谷函数通过迭代以不断缩小该区间的长度，当区间长度足够小时，可将该区间中的一点作为函数的极小点，比如黄金分割法。

e.g. 最小化一个单位体积的圆柱体的表面积。

r, h = sympy.symbols("r, h")

Area = 2 * sympy.pi * r**2 + 2 * sympy.pi * r * h

Volume = sympy.pi * r**2 * h

Q2: 入基变量可以是负数吗?

一般模型既有不等式约束，也有等式约束；既有非负的约束决策变量，也有整个实数域上的自由决策变量。

标准模型

引入冗余的决策变量，使得不等式约束转化为等式约束。这里的每个决策变量都具有非负性。

在这里插入图片描述

把上述模型用矩阵表示就是

m i n ( o r m a x ) C T X s . t A X = b ⃗ X ≥ 0 min(or\ max) C^TX\\ s.t \ AX=\vec{b}\\ \ X \geq 0

min(or max)C

s.t AX=

X≥0

线性规划问题的基本假设

系数矩阵A的行向量线性无关。

如果线性相关有2种可能，要么是增广矩阵的该行也线性相关，则该行约束冗余，可以删去。要么增广矩阵的该行线性无关，则方程无解，优化问题不存在。

系数矩阵A的行数小于列数

如果行数m大于列数n，则行向量是m个n维向量，不可能线性无关。吐过行数等于列数，且行向量线性无关，则约束条件确定了唯一解，无需优化。

一般模型与标准模型的转化

主要方式是增加决策变量。有两种情况需要增加

不等式变等式，每个不等式增加一个决策变量。

1个自由决策变量转化为2个约束的决策变量。

在这里插入图片描述

线性规划问题解的可能情况

唯一最优解

没有有限的最优目标函数

没有可行解

无穷多的最优解（一维问题中不会出现）

凸集

Def. 凸集：该集合中任意两个元素的凸组合仍然属于该集合。

在这里插入图片描述

注：此处的α \alphaα不能是0或1。

Thm. 线性规划的多面体模型是凸集。

Def. 凸集的顶点：顶点无法表示成集合中其他元素的凸组合。

在这里插入图片描述

顶点的等价描述

从系数矩阵中抽取m列线性无关的列向量，组成可逆方阵。则由此可求得m个决策变量的值，再令其余的决策变量为0即可。

推论

顶点中正分量对应的系数向量线性无关。

一个线性规划问题标准模型最多有C n m C_{n}^{m}C

个顶点。

定义总结

基矩阵§：系数矩阵中抽取m列线性无关的列向量组成可逆方阵。

基本解：m个基变量有基矩阵和b ⃗ \vec{b}

决定，剩余(n-m)个变量都置0，称之为非基变量。

基本可行解（顶点）：基本解中可行的，即满足非负性约束

Thm. 线性规划标准模型的基本可行解就是可行集的顶点。

Thm. 标准模型的线性规划问题如有可行解，则定有基本可行解。

Thm. 线性规划标准模型中顶点的个数是有限的。

Thm. 线性规划标准模型的最优目标函数值如果有有限的目标函数值，则总在顶点处取到。

单纯形法

在顶点中沿着边搜索最优解的过程。

按照上述的原理，我们固然可以求出所有的基矩阵，进入求出所有的顶点。计算每一个顶点的目标函数值，找出其中最大的那个，但是这样做的计算量未免太大，因此有了单纯行法，即沿着边搜索顶点。

在这里插入图片描述

单纯形法就是一个不断的选择变量入基出基的过程。

假定已知一个基本可行解。（问题4）

如何计算选定进基变量后的基本可行解。(问题1）

如何选择进基变量使得目标函数值改善。（问题2）

如何判断已经找到最优的目标函数值。（问题3）

计算选定进基变量的基本可行解

Def. 基本可行解的表示式：基变量只出现在一个等式约束中。如：

在这里插入图片描述

此处的x 3 , x 4 , x 5 x_3,x_4,x_5x

就是基变量。

选定出基变量：保可行性的最小非负比值原理

由上所述，一个顶点对应一个基本可行解，其中m个基变量，(n-m)个非基变量。假定我们要选择某个非基变量x i x_ix

入基，实际上就是通过对增广矩阵做初等行变化使得x i x_ix

仅仅出现在一个等式约束中。比如我们通过变换，使得x i x_ix

仅仅出现在第j个等式约束中，如果此时仍然满足可行性，那么x i x_ix

就取代了原来在此处的基变量，成为新的基变量。

在进行初等行变换的过程中，要保证可行性，即

b ⃗ ≥ 0 \vec{b} \geq 0

≥0

。因此要选择最小非负比值。请看下面的例子：

在这里插入图片描述

假设我们要选择x 2 x_2x

入基，那么就是要通过初等行变换，使得x 2 x_2x

的系数向量中某一行是1，其余行都是0。如我们选择x 2 x_2x

仅出现在第3个等式约束中，即

在这里插入图片描述

则此时无法保证可行性，因为b ⃗ \vec{b}

中第1个分量是负数。

为了避免等式右侧出现负数，只能选择比值最小的一行，即第1行。即化成如下的形式：

在这里插入图片描述

如果此时我们想让x 3 x_3x

入基，此时的最小比值是第2行，即让该行为1，其余行为0。但是，为了让x 3 x_3x

的第二行为1，该行两端必须同时乘以一个负数，此时仍然无法保证b ⃗ ≥ 0 \vec{b} \geq0

≥0，因此只能选择系数非负的一行。

注：这里的非负性是指系数非负，而不是比值非负。即当b中某行分量是0，而该行入基变量系数是负数，仍不能入基。

在这里插入图片描述

特殊情况：没有非负比值，即没有有限的目标函数值。

在这里插入图片描述

选择入基变量的原则

选择某个入基变量使得目标函数能改善，通过检验数选择。

此处假设优化目标是求最大值。通过等式约束，将目标函数表示成非基变量的线性组合。即

f ( X ) = c 1 x j ( m + 1 ) + c 2 x j ( m + 2 ) + . . . + c n x j ( n ) + c o n s t f(X)=c_1x_{j(m+1)}+c_2x_{j(m+2)}+...+c_nx_{j(n)}+const

f(X)=c

j(m+1)

j(m+2)

+...+c

j(n)

+const

只有选择检验数是正数的变量入基才有可能使得目标函数继续增大，因为入基之后变量只可能增大或者不变，而不可能减少。

如何确定已经找到了最优的目标函数值

此处假设优化目标是求最大值。

当每个非基变量的检验数都是负数时，目标函数已经达到了最大值。

退化情况

Thm. 收敛条件：每次迭代过程中，每个基本可行解的基变量都严格大于0，则每次迭代都能保证目标函数严格增加。而基本可行解的数目是有限的，因此上述过程不会一直进行下去，因此一定能在有限次迭代过程中找到最优解。

Def. 退化情况：某些基变量是0。则多个基矩阵对应同一个退化的顶点。

Thm. 循环迭代导致不收敛：多个基矩阵对应一个顶点，即每次出基入基都换了基矩阵，但是对应的退化顶点不变，即目标函数也不变。因此可能出现在几个基矩阵之间循环不止的情况。

避免退化：由于顶点的个数是有限的，我们只需标记那些已经迭代过的顶点，即可避免循环。

**bland法则：**始终选择下标最小的可入基和出基的变量。

当所有的基变量都严格大于0时，则这个基矩阵对应于非退化的顶点，此时可行基矩阵和顶点是一一对应的；

当某些基变量为0时，则这个基矩阵对应退化的顶点，一个退化的顶点对应数个可行基矩阵。

即给定一个可行基矩阵，一定能确定一个顶点，但是给定一个顶点时，其对应的基矩阵可能不唯一。

更一般地说，当顶点非退化时，可行基矩阵唯一；否则可行基矩阵不唯一。

如何确定初始的基本可行解

先将一般模型转化为标准模型，然后添加人工变量，在迭代过程中将人工变量都变成非基变量，则基变量就只剩下原来的变量。

在这里插入图片描述

大M法在这里插入图片描述

两阶段法

在这里插入图片描述

例题

本质就是不断的迭代单纯型表

在这里插入图片描述

一般线性规划问题总结

一般模型转化为标准型

在这里插入图片描述

基于单纯型表迭代的实质

求出非基变量的检验数

σ j ( k ) = c j ( k ) − C B T B − 1 P j ( k ) m + 1 ≤ k ≤ n \sigma_{j(k)}=c_{j(k)}-C_{B}^{T}B^{-1}P_{j(k)}\ m+1 \leq k \leq n

j(k)

−C

−1

j(k)

m+1≤k≤n

确定进基变量

σ j ( t ) = m a x { σ j ( m + 1 ) , σ j ( m + 2 ) , . . . σ j ( n ) } \sigma_{j(t)} = max\{\sigma_{j(m+1)},\sigma_{j(m+2)},...\sigma_{j(n)}\}

j(t)

=max{σ

j(m+1)

,σ

j(m+2)

,...σ

j(n)

}

确定出基变量

在这里插入图片描述

得到新的可行基矩阵

在这里插入图片描述

基于逆矩阵的单纯形法

在这里插入图片描述

核心问题：如何基于B − 1 B^{-1}B

−1

计算出B − 1 ~ \tilde{B^{-1}}

−1

。这两个矩阵仅仅有1列不一样，这是一个线性代数问题，与本课程的主要内容无关，此处不再赘述。

总结：单纯形法中可能遇到的3中特殊情况。

1. 退化问题：某些基变量为0

退化问题的现象是某些基变量为0，本质是一个退化的顶点对应多个可行基矩阵，后果是可能使得单纯形法不收敛。

在选择入基变量时，应该遵循blend法则，即每次选择可入基变量下标最小的那个。

2. 没有最小非负比值。

当选定入基变量后，需要根据“保证可行性的最小非负比值原理”选定出基变量，如果没有非负比值，则说明该变量可以趋于无穷，则该问题没有有限的最优目标函数值。

3. 某个非基变量的检验数为0.

在选择入基变量时，需要将目标函数表示成非基变量的表达式。以目标值是求最大问题的为例，此时应该选择检验数大于0的非基变量入基才能改善目标函数值。

当所有非基变量的检验数都为小于等于0的时候，无论选择谁入基，都会值得目标函数变得更差，因此这时候就达到了最优条件。

有一种特殊情况是某个非基变量的检验数为0，如果选取该变量入基，则目标函数值和原来一样，但是我们得到另一组不同的基本可行解，即最优目标函数值对应了多个基本可行解，这说明原问题有无穷多最优解。

4. 退化问题和非基变量检验数为0.

前者是一个顶点对应多个可行基矩阵，后者是最优目标函数值对应多个顶点。

前者可能导致单纯形法不收敛，后者说明该问题有无穷多解。

文章知识点与官方知识档案匹配

算法技能树首页概览

31789 人正在系统学习中

打开CSDN，阅读体验更佳

最优化技术——线性规划

最优化技术——线性规划线性规划基本概念线性规划问题就是在一组线性约束条件下，求解目标函数最优解的问题标准形式线性规划问题的标准形式：目标函数求最大值所有约束条件均由等式表示每个约束条件右端常数常为非负值所有决策变量为非负值改造方法所有的情况与改造方法目标函数求最小值则应该改为求最大值：方法——添加负号： minF=Σcjxj→maxF=−Σcjxj min F ...

继续访问

线性规划和对偶规划学习总结

在学习列生成和分解算法的时候，会频繁用到线性规划和对偶的知识，可以说LP和DP是基础。因此理解线性规划和对偶的本质是很重要的。单纯形法是纯代数运算，从一个顶点跳到另一个顶点；且我们知道最优解一定在顶点取得，可是为什么在顶点一定会取得最优解？为什么从一个顶点跳到另一顶点，通过进基出基就可以实现，它俩为什么是一一对应的？除此以外，在分解算法中的极点和极射线和LP的解是什么样的对应关系？这些问题，应该说必须了解了线性规划和对偶的本质才能够深刻理解，而不至于陷入机械无脑的计算。大概看了慕课的课程，感觉山东大

继续访问

最新发布 03 线性规划模型

03 线性规划模型

继续访问

第五章线性规划方法 Linear Programming

第五章线性规划方法 Linear Programming5.1 线性规划问题的一般形式5.2 线性规划问题的解5.2.1 基本解的产生与转换5.2.2 基本可行解的产生与转换5.2.3 基本可行解的变换条件1. 最优性条件2. 非负性条件5.3 单纯形算法 The Simplex Method 5.1 线性规划问题的一般形式 5.2 线性规划问题的解基本解：只满足约束方程的解。基本可行解：同时满足约束方程和变量非负约束的解。最优解：使目标函数取得最小值的基本可行解。 5.2.1 基本解的产生与

继续访问

关于数学建模中线性规划总结

一、python方法解决 from scipy import optimize as op import numpy as np c=np.array([2,3,-5]) c = np.array([2,3,-5]) A = np.array([[-2,5,-1],[1,3,1]]) b= np.array([-10,12]) Aeq = np.array([[1,1,1]]) beq = np.array([7]) #求解 res = op.linprog(-c,A,b,Aeq,beq) print(

继续访问

八、线性规划顶点、极值点和基本可行解决方案

假设我们正在求解方程形式的一般线性程序：这里，是一个的矩阵，，，今天，我们将假设的行是线性独立的。（如果不是，那么系统没有解，或者某些方程是多余的。在第一种情况下，我们只是忘记分析这样的线性程序；在第二种情况下，我们可以从删除冗余行。）我们已经非正式地说过，基本可行的解决方案是“尽可能多的变量”为0。这不是很精确：在某些情况下（由于退化），可能有异常多的0值，并且我们不希望这与我们的定义混淆。相反，我们进行如下定义。选择一些列（或变量）的做为

继续访问

【算法设计zxd】第3章迭代法04 线性规划

线性规划研究线性约束条件下线性目标函数的极值问题的数学理论和方法。线性规划问题形式化表达目标函数约束条件线性规划问题的可行性解线性规划问题的可行区域线性规划问题的最优解（x1,x2,……，xn的值）线性规划问题的最优值  单纯形算法特点 (1) 只对约束条件的若干组合进行测试，测试的毎一步都使目标函数的值向期望值逼近； (2) 一般经过不大于m或n次迭代就可求得最优解。 线性规划标准形式 (1)它必须是一个最大化问题。如果是..

继续访问

线性规划部分概念及重要性质（运筹学导论笔记）

模型解的术语可行解：满足所有约束条件的解非可行解：至少一个约束条件不被满足的解可行域：所有可行解的集合最优解：目标函数取得最有价值的可行解顶点可行解（CPF）：位于可行域顶点的解顶点可行解与最优解的关系：考虑任意具有可行解与有界可行域的线性规划问题，一定具有顶点可行解和至少一个最优解，而且，最优的顶点可行解一定是最优解；因此，若一个问题恰有一个最优解，它一定是顶点可行解，若一个问题有多个最优解，其中至少两个一定是顶点可行解比例性假设：每个活动对于目标函数值Z的贡献与活动级别xj成比例的可加性

继续访问

Mathematics for Machine Learning--学习笔记(线性无关)

1.5 Linear Independence（线性无关）接下来就要学习如何处理向量了。首先，我们先介绍线性组合和线性无关的概念。 Linear Combination(线性组合)：存在一个向量空间V和有限的x1,⋯ ,xk∈Vx_1,\cdots,x_k\in Vx1,⋯,xk∈V.每一个元素vvv都有如下形式：v=λ1x1+⋯+λkxk=∑i=1kλixi∈Vv=\lambda_1 x_1+\cdots+\lambda_k x_k=\sum_{i = 1}^{k} {\lambda_i x_i

继续访问

线性规划——规范型，标准型，基阵、基本解、基本可行解、基变量、非基变量.... 概念梳理

文章目录前言最优化—线性规划模型问题线性规划模型的一般形式（min）线性规划规范形式线性规划标准型模型的转换线性规划中的规律规范形式顶点的数学描述标准形式顶点的数学描述标准形式顶点的等价描述之一标准形式顶点的等价描述之二线性规划标准形式的一些基本概念线性规划标准形式的基本定理前言此总结参考清华王焕刚老师的教程。最优化—线性规划模型问题线性规划模型的一般形式（min） min⁡∑j=1ncjxj s.t. ∑j=1naijxj=bi,∀1≤i≤p∑j=1naijxj≥bi,∀

继续访问

最优化——线性规划总结1(线性规划标准型，规范型，顶点)

线性规划的形式标准型规范型线性规划的求解思路前提条件线性规划：凸优化（凸集上的凸函数的优化）线性规划的可行集是凸集，优化函数是凸函数（仿射函数嘛）总有顶点是最优解，所有顶点组成的集合总是有限集，所以可以在顶点集中找到最优解。主要思路根据前提条件来看，我们求解线性规划的思路：找到所有的顶点，在顶点中找到最优的那个，就是最优解。相当于缩小了搜索范围。怎么搞首先计算顶点：顶点是改点所有起作用约束构成的线性方程组的唯一解。因为所有的线性规划形式都能转换成标准型，所以这里只考虑标准型的

继续访问

线性规划图解法求最优解_高考数学【线性规划】知识点相关解析~

一、知识梳理1、目标函数：P=2x＋y是一个含有两个变量x和y的函数，称为目标函数。2、可行域：约束条件表示的平面区域称为可行域。3、整点：坐标为整数的点叫做整点。4、线性规划问题：求线性目标函数在线性约束条件下的最大值或最小值的问题，通常称为线性规划问题。只含有两个变量的简单线性规划问题可用图解法来解决。5、整数线性规划：要求量整数的线性规划称为整数线性规划。二、疑难知识导析线性规划是...

继续访问

算法最优化（2）线性规划问题中的常见概念辨析：可行解，最优解，基，基向量，非基向量，基变量，非基变量等等

继续访问

【线性规划】基本概念

线性规划的概念线性规划(Linear Programming 简记 LP)是了运筹学中数学规划的一个重要分支。自从 1947 年 G. B. Dantzig 提出求解线性规划的单纯形法以来，线性规划在理论上趋向成熟，在实用中由于计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划现代管理中经常采用的基本方法之一。在解决实际问题时，需要把问题归结成一个线性规划数学模型，关键及难点在于选适当的决策变量建立恰当的模型，这直接影响到问题的求解。线性规划问题的目标函数及约束条件均为线性函数；约

继续访问

【运筹学】什么是基变量？对于线性规划问题中“基”概念的理解（3月3日学习笔记）

在学习《线性规划与目标规划》的过程中，课程的主讲老师郭韧给出了对于基概念的定义如下图图片来源:运筹学（中国大学mooc网）由此我产生了几个疑惑:1.如何理解B是线性规划问题的一个基？2.为什么说最多有CnmC_n^mCnm个基呢？ 1.如何理解B是线性规划问题的一个基？1.如何理解B是线性规划问题的一个基？1.如何理解B是线性规划问题的一个基？在回答第一个...

继续访问

一、唯一最优解、二、无穷多最优解、三、无界解、四、无可行解、五、线性规划迭代范围、六、线性规划求解步骤

继续访问

线性规划与非线性规划的求解

单纯形法求解线性规划一、大M法求解线性规划的原理（1）、大M法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵I，那么已经得到了一个初始可行基。否则在约束方程组的左边加上若千个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成-一个单位矩阵。以单位矩阵为初始基，即可求得一-个初始的基本可行解。为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量...

继续访问

热门推荐线性规划算法详解

线性规划首先什么是线性规划，大致的定义我总结为在线性的目标和约束中，找出一个最优解。举个例子： M1和M2两种原料用于生产内外墙涂料，M1日最大可用量24吨，M2日最大可用量为6吨，外墙涂料每吨需要6吨M1，1吨M2，内墙涂料每吨需要4吨M12，吨M2，外墙涂料每吨利润5个单位，内墙涂料每吨利润4个单位。且市场需求调查数据得出，内墙日需求量不超过外墙的日需求量+1吨，内墙最大日需求量为...

继续访问

运筹学 —线性规划总结

线性规划问题 1. 概述线性规划问题是在一组线性约束下，求资源配置的最大最小值的问题。直观的变现是在一个约束条件围成的区域上寻找一个点，这个点使得资源配置最优化： 2. 线性规划的思想线性规划的思路是将不等式转换为等式，最终求得一个满足等式的解。下面的约束式必然可以转换为[P|N]*X=B的形式，这里P是线性无关的M*M的方正。

继续访问

最优化——退化和某个非基变量检验数为零

文章目录退化和某个非基变量检验数为零退化问题退化问题的本质某个非基变量检验数为零退化和某个非基变量检验数为零退化问题基本可行解的基变量数值等于0。退化问题的本质多个可行基阵对应于一个基本可行解。某个非基变量检验数为零对于求max的线性规划问题，如果所有检验数均满足则说明已经得到最优解，若此时某非基变量的检验数为零，则说明该优化问题有无穷多最优解。 ...

Q3: OpenCV-Python教程:19.轮廓属性

1图像矩

帮python编写凸函数你计算一些属性python编写凸函数，比如重心，面积等。

函数cv2.moments()会给你一个字典，包含所有矩值

你可以从这个里面得到有用的数据比如面积，重心等。重心可以用下面的式子得到：

2.轮廓面积

轮廓面积由函数cv2.contourArea()得到或者从矩里得到M['m00']

3.轮廓周长

可以用cv2.arcLength()函数得到。第二个参数指定形状是否是闭合的轮廓（如果传True）。或者只是一个曲线。

4.轮廓近似

这会把轮廓形状近似成别的边数少的形状，边数由我们指定的精确度决定。这是Douglas-Peucker算法的实现。

要理解这个，假设你试图找一个图像里的方块，但是由于图像里的一些问题，你得不到一个完美的方块，只能得到一个“坏方块”。现在你可以使用这个函数来近似，第二个参数叫epsilon，是从轮廓到近似轮廓的最大距离。是一个准确率参数，好的epsilon的选择可以得到正确的输出。

在下面第二个图像里，绿线显示了epsilon = 10% of arc length 的近似曲线。第三个图像显示了epsilon = 1% of the arc length。第三个参数指定曲线是否闭合。

5.凸形外壳

凸形外壳和轮廓近似类似，但是还不一样（某些情况下两个甚至提供了同样的结果）。这儿，cv2.convexHull()函数检查凸面曲线缺陷并修复它。一般来说，凸面曲线总是外凸的，至少是平的，如果它内凹了，这就叫凸面缺陷。比如下面这张图，红线显示了手的凸形外壳。双向箭头显示了凸面缺陷，是轮廓外壳的最大偏差。

参数详情：

·points 是我们传入的轮廓

·hull 是输出，一般我们不用传

·clockwise：方向标示，如果是True，输出凸形外壳是顺时针方向的。否则，是逆时针的。

·returnPoints：默认是True。然后会返回外壳的点的坐标。如果为False，它会返回轮廓对应外壳点的索引。

所以要获得凸形外壳，下面

但是如果你想找到凸面缺陷，你需要传入returnPoints = False。我们拿上面的矩形图形来说，首先我找到python编写凸函数他的轮廓cnt，现在用returnPoints = True来找他的凸形外壳，我得到下面的值：[[[234 202]], [[51 202]], [51 79]], [[234 79]]] 是四个角的点。如果你用returnPoints = False，我会得到下面的结果：[[129], [67], [0], [142]]. 这是轮廓里对应点的索引，比如cnt[129] = [234, 202]]，这和前面结果一样。

6.检查凸面

有一个函数用来检查是否曲线是凸面, cv2.isContourConvex().它返回True或False。

7.边界矩形

有两种边界矩形

7.a.正边界矩形

这个矩形不考虑对象的旋转，所以边界矩形的面积不是最小的，函数是cv2.boundingRect()。

假设矩形左上角的坐标是(x,y)，（w, h）是它的宽和高

7.b.渲染矩形

这个边界矩形是用最小面积画出来的，所以要考虑旋转。函数是cv2.minAreaRect()。它返回一个Box2D结构，包含了(左上角(x,y)，（width, height）,旋转角度）。但是要画这个矩形我们需要4个角。这四个角用函数cv2.boxPoints()得到

8.最小闭包圆

我们找一个目标的外接圆可以用函数cv2.minEnclosingCircle().这个圆用最小面积完全包围目标。

9.椭圆