入基变量可以是负数吗?

2023-02-17 11:25:01Python030

入基变量可以是负数吗?,第1张

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

标准模型

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

在这里插入图片描述

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

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的线性规划问题，如果所有检验数均满足则说明已经得到最优解，若此时某非基变量的检验数为零，则说明该优化问题有无穷多最优解。 ...

因为基本可行解的个数有限，故经有限次转换必能得出问题的最优解。从线性方程组找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小了，决定下一步选择的单纯形。通过优化迭代，直到目标函数实现最大或最小值。如果线性问题存在最优解，一定有一个基可行解是有最优解。因此单纯形法迭代的基本思路是：先找出一个基可行解，判断其是否为最优解。如为否，则转换到相邻的基可行解，并使目标函数值不断增大，一直找到最优解为止。扩展资料：由于目标函数和约束条件内容和形式上的差别，线性规划问题可以有多种表达式。因此，为了便于讨论和制定统一的算法，在制定单纯形法时，规定使用单纯形法求解的线性规划问题需要有一个标准形式，它有下面三个特征：(1) 标准形式目标函数统一为求极大值或极小值，但单纯形法主要用来求解极大值；(2) 所有约束条件（除非负条件外）都是等式，约束条件右端常数项bi全为非负值；(3) 所有变量的取值全为非负值。

搜索

免费python全套教程

python必背100源代码

编程入门教程300例

初学编程100个简单教程

初中数学全套解题技巧

编程必背50个程序

如何实现大数据利润最大利润化

制定合适的价格很重要，再怎么夸大都不过分。价格提高1%意味着经营利润平均可以增长8.7%（当然，假设销量没有损失）。不过我们估计，在许多公司每年制定的成千上万个定价决策中，多达30%未能给出最合适的价格——这意味着收入大量流失。而且考虑到如今海量数据为公司提供了难得的机会，可以做出合理得多的定价决策，这种现状尤其令人不安。对那些能够井然有序地应对复杂的大数据的公司而言，这蕴含着巨大价值。

将数据转化为利润的四个步骤

想制定更合适的价格，关键是完全明白现在可供公司使用的数据。这就需要放大目标，而不是缩小目标。正如综合性能源和化工企业沙索（Sasol）集团副总裁兼营销和销售总经理汤姆·奥布赖恩（Tom O’Brien）提及这种做法时说：“销售团队知道价格，还可能知道销量，但这种做法需要了解更多信息：极其精细的数据，实际上来自每一张发票，按产品、客户和包装分门别类。”

事实上，将大数据成功应用于B2B环境方面最激动人心的一些例子实际上不仅仅着眼于定价，还涉及一家公司的商业引擎的其他方面。比如说，“动态交易评分”（dynamic deal scoring）提供了单笔交易层面的价格指导，还提供了决策逐级上报点、激励机制、绩效评分及更多方面，立足于一系列相似的盈/亏交易。使用较小的、相关的交易样本很有必要，因为与任何一笔交易息息相关的因素会有变化，这导致一系列总体交易成为毫无用处的衡量基准。我们已见过这种方法应用于技术行业，取得了巨大成功。将销售利润率提高了4到8个百分点（相对于同一家公司的对照组）。

想获得足够精细的数据，公司就要做好这四项工作

倾听数据。制定最合理的价格不是牵涉数据的挑战（公司通常已经坐拥庞大的数据宝库），而是牵涉分析的挑战。最出色的B2C公司知道如何解释自己拥有的海量数据，并见机行事，但B2B公司往往一味管理数据，而不是利用数据推动决策。优秀的分析工具可以帮助公司确定经常被忽视的因素（比如更宏观的经济形势、产品偏好以及销售代表的洽谈），揭示什么因素左右针对每个客户群和产品的价格。

提高自动化。人工分析数千种产品太耗费时间和财力。自动化系统可以识别狭小的客户群，确定什么因素左右每个客户群的价值，并且拿来与历史交易数据进行比较。这样一来，公司就可以根据数据，为产品群和客户群制定有针对性的价格。自动化还大大简化了复制和调整分析的工作，因此没必要每次都从头开始分析。

培养技能、树立信心。实施新价格既在运营方面带来了挑战，又在沟通方面带来了挑战。成功的公司非常注重深思熟虑的变革计划，帮助销售队伍了解并接受新的定价方法。公司需要与销售代表们齐心协力，解释为什么实行建议价，这套价格体系是如何运作的，那样销售代表就会非常信任价格，从而竭力说服顾客。同样重要的是制定一套明确清晰的沟通方法，为价格给出一个理由，从而着重突出价值，然后针对具体顾客给出相应的理由。全面的洽谈培训也至关重要，以便让销售代表获得信心和工具，那样与客户面对面交流时，能拿出颇有说服力的理由。最优秀的领导陪同销售代表会见最难拿下的客户，专注于迅速见效，那样销售代表就能树立起信心，积极奉行新的定价方法。林德集团旗下瑞士PanGas AG公司的总经理罗伯特·克里格（Robert Krieger）说：“表明领导层支持这种新的定价方法这个立场，至关重要。为此，我们采取的做法就是领导层与销售代表一起拜见难缠的客户。我们不仅能够帮助销售代表，还能够阐明为什么制定新价格。”

积极管理绩效。想改善绩效管理，公司就需要借助实用的绩效指标支持销售队伍。最大的影响来自确保销售一线对于客户带来的利润了然于胸；销售和营销部门拥有合适的分析技能，得以发现机会，并牢牢抓住机会。还需要将权力下放给销售队伍，让他们自行调整价格，而不是依赖集中式团队。这不仅需要创业理念，还需要在针对特定的客户制定价格策略时有一定的创造力。在改变定价策略和绩效衡量标准的同时，可能还要改变激励机制。

我们已经看到了这一幕：软件、化工、建材和电信等众多行业的公司利用大数据，帮助制定更合理的定价决策，因而收到显著成效。这些公司都有数量众多的库存单位（SKU）和交易，还有一大批高度分散的客户；重新制定价格后，都发现利润率提高了3%到8%，这些价格是在极其精细的产品数据层面制定的。仅举一例，一家欧洲建材公司为几种有所选择的产品制定合适的价格后，利润增幅高达20%。如果公司想制定合适的价格，就应该充分利用大数据，并投入足够的资源来支持销售代表，否则它们会发现自己在为此付出高昂的代价：利润流失。

转载请注明：数据分析 » 如何实现大数据利润最大利润化

量化分析师的Python_python 金融量化分析_python金融大数据分析

一、SciPy概述

前篇已经大致介绍了NumPy，接下来让我们看看SciPy能做些什么。NumPy替我们搞定了向量和矩阵的相关操作，基本上算是一个高级的科学计算器。SciPy基于NumPy提供了更为丰富和高级的功能扩展，在统计、优化、插值、数值积分、时频转换等方面提供了大量的可用函数，基本覆盖了基础科学计算相关的问题。

在量化分析中，运用最广泛的是统计和优化的相关技术，本篇重点介绍SciPy中的统计和优化模块，其他模块在随后系列文章中用到时再做详述。

本篇会涉及到一些矩阵代数，如若感觉不适，可考虑跳过第三部分或者在理解时简单采用一维的标量代替高维的向量。

首先还是导入相关的模块，我们使用的是SciPy里面的统计和优化部分：

In[1]:

import numpy as npimport scipy.stats as statsimport scipy.optimize as opt

二、统计部分2.1 生成随机数

我们从生成随机数开始，这样方便后面的介绍。生成n个随机数可用rv_continuous.rvs(size=n)或rv_discrete.rvs(size=n)，其中rv_continuous表示连续型的随机分布，如均匀分布（uniform）、正态分布（norm）、贝塔分布（beta）等；rv_discrete表示离散型的随机分布，如伯努利分布（bernoulli）、几何分布（geom）、泊松分布（poisson）等。我们生成10个[0, 1]区间上的随机数和10个服从参数$a = 4$，$b = 2$的贝塔分布随机数：

In[2]:

rv_unif = stats.uniform.rvs(size=10)print rv_unifrv_beta = stats.beta.rvs(size=10, a=4, b=2)print rv_beta

[ 0.20630272 0.25929204 0.16859206 0.92573462 0.16383319 0.3475617 0.83792048 0.79574153 0.37945051 0.23439682][ 0.71216492 0.85688464 0.70310131 0.3783662 0.69507561 0.78626586 0.54529967 0.4261079 0.26646767 0.8519046 ]

在每个随机分布的生成函数里，都内置了默认的参数，如均匀分布的上下界默认是0和1。可是一旦需要修改这些参数，每次生成随机都要敲这么老长一串有点麻烦，能不能简单点？SciPy里头有一个Freezing的功能，可以提供简便版本的命令。SciPy.stats支持定义出某个具体的分布的对象，我们可以做如下的定义，让beta直接指代具体参数$a = 4$和$b = 2$的贝塔分布。为让结果具有可比性，这里指定了随机数的生成种子，由NumPy提供。

In[3]:

np.random.seed(seed=2015)rv_beta = stats.beta.rvs(size=10, a=4, b=2)print "method 1:"print rv_betanp.random.seed(seed=2015)beta = stats.beta(a=4, b=2)print "method 2:"print beta.rvs(size=10)

method 1:[ 0.43857338 0.9411551 0.75116671 0.92002864 0.62030521 0.56585548 0.41843548 0.5953096 0.88983036 0.94675351]method 2:[ 0.43857338 0.9411551 0.75116671 0.92002864 0.62030521 0.56585548 0.41843548 0.5953096 0.88983036 0.94675351]

2.2 假设检验

好了，现在我们生成一组数据，并查看相关的统计量（相关分布的参数可以在这里查到：http://docs.scipy.org/doc/scipy/reference/stats.html）：

In[4]:

norm_dist = stats.norm(loc=0.5, scale=2)n = 200dat = norm_dist.rvs(size=n)print "mean of data is: " + str(np.mean(dat))print "median of data is: " + str(np.median(dat))print "standard deviation of data is: " + str(np.std(dat))

mean of data is: 0.705195138069median of data is: 0.658167882933standard deviation of data is: 2.08967006905

假设这个数据是我们获取到的实际的某些数据，如股票日涨跌幅，我们对数据进行简单的分析。最简单的是检验这一组数据是否服从假设的分布，如正态分布。这个问题是典型的单样本假设检验问题，最为常见的解决方案是采用K-S检验（ Kolmogorov-Smirnov test）。单样本K-S检验的原假设是给定的数据来自和原假设分布相同的分布，在SciPy中提供了kstest函数，参数分别是数据、拟检验的分布名称和对应的参数：

In[5]:

mu = np.mean(dat)sigma = np.std(dat)stat_val, p_val = stats.kstest(dat, 'norm', (mu, sigma))print 'KS-statistic D = %6.3f p-value = %6.4f' % (stat_val, p_val)

KS-statistic D = 0.045 p-value = 0.8195

假设检验的$p$-value值很大（在原假设下，$p$-value是服从[0, 1]区间上的均匀分布的随机变量，可参考http://en.wikipedia.org/wiki/P-value ），因此我们接受原假设，即该数据通过了正态性的检验。在正态性的前提下，我们可进一步检验这组数据的均值是不是0。典型的方法是$t$检验（$t$-test），其中单样本的$t$检验函数为ttest_1samp：

In[6]:

stat_val, p_val = stats.ttest_1samp(dat, 0)print 'One-sample t-statistic D = %6.3f, p-value = %6.4f' % (stat_val, p_val)

One-sample t-statistic D = 4.761, p-value = 0.0000

我们看到$p$-value$ <0.05$，即给定显著性水平0.05的前提下，我们应拒绝原假设：数据的均值为0。我们再生成一组数据，尝试一下双样本的$t$检验（ttest_ind）：

In[7]:

norm_dist2 = stats.norm(loc=-0.2, scale=1.2)dat2 = norm_dist2.rvs(size=n/2)stat_val, p_val = stats.ttest_ind(dat, dat2, equal_var=False)print 'Two-sample t-statistic D = %6.3f, p-value = %6.4f' % (stat_val, p_val)

Two-sample t-statistic D = 5.565, p-value = 0.0000

注意，这里我们生成的第二组数据样本大小、方差和第一组均不相等，在运用$t$检验时需要使用Welch’s $t$-test，即指定ttest_ind中的equal_var=False。我们同样得到了比较小的$p$-value$，在显著性水平0.05的前提下拒绝原假设，即认为两组数据均值不等。

stats还提供其他大量的假设检验函数，如bartlett和levene用于检验方差是否相等；anderson_ksamp用于进行Anderson-Darling的K-样本检验等。

2.3 其他函数

有时需要知道某数值在一个分布中的分位，或者给定了一个分布，求某分位上的数值。这可以通过cdf和ppf函数完成：

In[8]:

g_dist = stats.gamma(a=2)print "quantiles of 2, 4 and 5:"print g_dist.cdf([2, 4, 5])print "Values of 25%, 50% and 90%:"print g_dist.pdf([0.25, 0.5, 0.95])

quantiles of 2, 4 and 5:[ 0.59399415 0.90842181 0.95957232]Values of 25%, 50% and 90%:[ 0.1947002 0.30326533 0.36740397]

对于一个给定的分布，可以用moment很方便的查看分布的矩信息，例如我们查看$N(0, 1)$的六阶原点矩：

In[9]:

stats.norm.moment(6, loc=0, scale=1)

Out[9]:

15.000000000895332

describe函数提供对数据集的统计描述分析，包括数据样本大小，极值，均值，方差，偏度和峰度：

In[10]:

norm_dist = stats.norm(loc=0, scale=1.8)dat = norm_dist.rvs(size=100)info = stats.describe(dat)print "Data size is: " + str(info[0])print "Minimum value is: " + str(info[1][0])print "Maximum value is: " + str(info[1][1])print "Arithmetic mean is: " + str(info[2])print "Unbiased variance is: " + str(info[3])print "Biased skewness is: " + str(info[4])print "Biased kurtosis is: " + str(info[5])

Data size is: 100Minimum value is: -4.12414564687Maximum value is: 4.82577602489Arithmetic mean is: 0.0962913592209Unbiased variance is: 2.88719292463Biased skewness is: -0.00256548794681Biased kurtosis is: -0.317463421177

当我们知道一组数据服从某些分布的时候，可以调用fit函数来得到对应分布参数的极大似然估计（MLE, maximum-likelihood estimation）。以下代码示例了假设数据服从正态分布，用极大似然估计分布参数：

In[11]:

norm_dist = stats.norm(loc=0, scale=1.8)dat = norm_dist.rvs(size=100)mu, sigma = stats.norm.fit(dat)print "MLE of data mean:" + str(mu)print "MLE of data standard deviation:" + str(sigma)

MLE of data mean:-0.249880829912MLE of data standard deviation:1.89195303507

pearsonr和spearmanr可以计算Pearson和Spearman相关系数，这两个相关系数度量了两组数据的相互线性关联程度：

In[12]:

norm_dist = stats.norm()dat1 = norm_dist.rvs(size=100)exp_dist = stats.expon()dat2 = exp_dist.rvs(size=100)cor, pval = stats.pearsonr(dat1, dat2)print "Pearson correlation coefficient: " + str(cor)cor, pval = stats.pearsonr(dat1, dat2)print "Spearman's rank correlation coefficient: " + str(cor)

Pearson correlation coefficient: -0.0262911931014Spearman's rank correlation coefficient: -0.0262911931014

其中的$p$-value表示原假设（两组数据不相关）下，相关系数的显著性。

最后，在分析金融数据中使用频繁的线性回归在SciPy中也有提供，我们来看一个例子：

In[13]:

x = stats.chi2.rvs(3, size=50)y = 2.5 + 1.2 * x + stats.norm.rvs(size=50, loc=0, scale=1.5)slope, intercept, r_value, p_value, std_err = stats.linregress(x, y)print "Slope of fitted model is:" , slopeprint "Intercept of fitted model is:", interceptprint "R-squared:", r_value**2

Slope of fitted model is: 1.44515601191Intercept of fitted model is: 1.91080684516R-squared: 0.798786910173

在前面的链接中，可以查到大部分stat中的函数，本节权作简单介绍，挖掘更多功能的最好方法还是直接读原始的文档。另外，StatsModels（http://statsmodels.sourceforge.net ）模块提供了更为专业，更多的统计相关函数。若在SciPy没有满足需求，可以采用StatsModels。

三、优化部分

优化问题在投资中可谓是根本问题，如果手上有众多可选的策略，应如何从中选择一个“最好”的策略进行投资呢？这时就需要用到一些优化技术针对给定的指标进行寻优。随着越来越多金融数据的出现，机器学习逐渐应用在投资领域，在机器学习中，优化也是十分重要的一个部分。以下介绍一些常见的优化方法，虽然例子是人工生成的，不直接应用于实际金融数据，我们希望读者在后面遇到优化问题时，能够从这些简单例子迅速上手解决。

3.1 无约束优化问题

所谓的无约束优化问题指的是一个优化问题的寻优可行集合是目标函数自变量的定义域，即没有外部的限制条件。例如，求解优化问题 [

minimizef(x)=x24.8x+1.2

] 就是一个无约束优化问题，而求解 [

minimizef(x)=x24.8x+1.2subject tox≥0

]则是一个带约束的优化问题。更进一步，我们假设考虑的问题全部是凸优化问题，即目标函数是凸函数，其自变量的可行集是凸集。（详细定义可参考斯坦福大学Stephen Boyd教授的教材convex optimization，下载链接：http://stanford.edu/~boyd/cvxbook ）

我们以Rosenbrock函数 [ f(mathbf{x}) = sum{i=1}^{N-1} 100 (x_i – x{i-1}^2)^2 + (1 – x_{i-1})^2 ] 作为寻优的目标函数来简要介绍在SciPy中使用优化模块scipy.optimize。

首先需要定义一下这个Rosenbrock函数：

In[14]:

def rosen(x): """The Rosenbrock function""" return sum(100.0*(x[1:]-x[:-1]**2.0)**2.0 + (1-x[:-1])**2.0)

3.1.1 Nelder-Mead单纯形法

单纯形法是运筹学中介绍的求解线性规划问题的通用方法，这里的Nelder-Mead单纯形法与其并不相同，只是用到单纯形的概念。设定起始点$mathbf{x}_0 = (1.3, 0.7, 0.8, 1.9, 1.2)$，并进行最小化的寻优。这里‘xtol’表示迭代收敛的容忍误差上界：

In[15]:

x_0 = np.array([0.5, 1.6, 1.1, 0.8, 1.2])res = opt.minimize(rosen, x_0, method='nelder-mead', options={'xtol': 1e-8, 'disp': True})print "Result of minimizing Rosenbrock function via Nelder-Mead Simplex algorithm:"print res

Optimization terminated successfully. Current function value: 0.000000 Iterations: 436 Function evaluations: 706Result of minimizing Rosenbrock function via Nelder-Mead Simplex algorithm: status: 0 nfev: 706 success: True fun: 1.6614969876635003e-17 x: array([ 1., 1., 1., 1., 1.]) message: 'Optimization terminated successfully.' nit: 436

Rosenbrock函数的性质比较好，简单的优化方法就可以处理了，还可以在minimize中使用method=’powell’来指定使用Powell’s method。这两种简单的方法并不使用函数的梯度，在略微复杂的情形下收敛速度比较慢，下面让我们来看一下用到函数梯度进行寻优的方法。

3.1.2 Broyden-Fletcher-Goldfarb-Shanno法

Broyden-Fletcher-Goldfarb-Shanno（BFGS）法用到了梯度信息，首先求一下Rosenbrock函数的梯度：

[ begin{split} frac{partial f}{partial xj} &= sum{i=1}^N 200(xi – x{i-1}^2)(delta{i,j} – 2x{i-1}delta{i-1,j}) -2(1 – x{i-1})delta_{i-1,j} &= 200(xj – x{j-1}^2) – 400xj(x{j+1} – x_j^2) – 2(1 – x_j) end{split}] 其中当$i=j$时，$delta_{i,j} = 1$，否则$delta_{i,j} = 0$。

边界的梯度是特例，有如下形式： [ begin{split} frac{partial f}{partial x_0} &= -400x_0(x_1 – x_0^2) – 2(1 – x_0), frac{partial f}{partial x{N-1}} &= 200(x{N-1} – x_{N-2}^2) end{split}]

我们可以如下定义梯度向量的计算函数了：

In[16]:

def rosen_der(x): xm = x[1:-1] xm_m1 = x[:-2] xm_p1 = x[2:] der = np.zeros_like(x) der[1:-1] = 200*(xm-xm_m1**2) - 400*(xm_p1 - xm**2)*xm - 2*(1-xm) der[0] = -400*x[0]*(x[1]-x[0]**2) - 2*(1-x[0]) der[-1] = 200*(x[-1]-x[-2]**2) return der

梯度信息的引入在minimize函数中通过参数jac指定：

In[17]:

res = opt.minimize(rosen, x_0, method='BFGS', jac=rosen_der, options={'disp': True})print "Result of minimizing Rosenbrock function via Broyden-Fletcher-Goldfarb-Shanno algorithm:"print res

Optimization terminated successfully. Current function value: 0.000000 Iterations: 52 Function evaluations: 63 Gradient evaluations: 63Result of minimizing Rosenbrock function via Broyden-Fletcher-Goldfarb-Shanno algorithm: status: 0 success: True njev: 63 nfev: 63 hess_inv: array([[ 0.00726515, 0.01195827, 0.0225785 , 0.04460906, 0.08923649], [ 0.01195827, 0.02417936, 0.04591135, 0.09086889, 0.18165604], [ 0.0225785 , 0.04591135, 0.09208689, 0.18237695, 0.36445491], [ 0.04460906, 0.09086889, 0.18237695, 0.36609277, 0.73152922], [ 0.08923649, 0.18165604, 0.36445491, 0.73152922, 1.46680958]]) fun: 3.179561068096293e-14 x: array([ 1. , 0.99999998, 0.99999996, 0.99999992, 0.99999983]) message: 'Optimization terminated successfully.' jac: array([ 4.47207141e-06, 1.30357917e-06, -1.86454207e-07, -2.00564982e-06, 4.98799446e-07])

3.1.3 牛顿共轭梯度法（Newton-Conjugate-Gradient algorithm）

用到梯度的方法还有牛顿法，牛顿法是收敛速度最快的方法，其缺点在于要求Hessian矩阵（二阶导数矩阵）。牛顿法大致的思路是采用泰勒展开的二阶近似： [ f(mathbf{x}) approx f(mathbf{x}_0) + nabla f(mathbf{x}_0)(mathbf{x} – mathbf{x}_0) + frac{1}{2}(mathbf{x} – mathbf{x}_0)^Tmathbf{H}(mathbf{x}_0)(mathbf{x} – mathbf{x}_0) ] 其中$mathbf{H}(mathbf{x}_0)$表示二阶导数矩阵。若Hessian矩阵是正定的，函数的局部最小值可以通过使上面的二次型的一阶导数等于0来获取，我们有： [ mathbf{x}_{mathrm{opt}} = mathbf{x}_0 – mathbf{H}^{-1}nabla f ]

这里可使用共轭梯度近似Hessian矩阵的逆矩阵。下面给出Rosenbrock函数的Hessian矩阵元素通式：

[ begin{split} H{i,j} = frac{partial^2 f}{partial x_i partial x_j} &= 200(delta{i,j} – 2x{i-1}delta{i-1,j}) – 400xi(delta{i+1,j} – 2xidelta{i,j}) – 400delta{i,j}(x{i+1} – xi^2) + 2delta{i,j}, &= (202 + 1200xi^2 – 400x{i+1}) delta{i,j} – 400x_idelta{i+1,j} – 400x{i-1}delta{i-1,j} end{split}] 其中$i,j in [1, N-2]$。其他边界上的元素通式为： [ begin{split} frac{partial^2 f}{partial x_0^2} &= 1200x_0^2 – 400x_1 + 2, frac{partial^2 f}{partial x_0 partial x_1} = frac{partial^2 f}{partial x_1 partial x_0} &= -400x_0, frac{partial^2 f}{partial x{N-1} partial x{N-2}} = frac{partial^2 f}{partial x{N-2} partial x{N-1}} &= -400x_{N-2}, frac{partial^2 f}{partial x_{N-1}^2} &= 200. end{split}]

例如，当$N=5$时的Hessian矩阵为：

[ mathbf{H} =

[1200x20400x1+2400x0000400x0202+1200x21400x2400x1000400x1202+1200x22400x3400x2000400x2202+1200x23400x4400x3000400x3200]

]为使用牛顿共轭梯度法，我们需要提供一个计算Hessian矩阵的函数：

In[18]:

def rosen_hess(x): x = np.asarray(x) H = np.diag(-400*x[:-1],1) - np.diag(400*x[:-1],-1) diagonal = np.zeros_like(x) diagonal[0] = 1200*x[0]**2-400*x[1]+2 diagonal[-1] = 200 diagonal[1:-1] = 202 + 1200*x[1:-1]**2 - 400*x[2:] H = H + np.diag(diagonal) return H

In[19]:

res = opt.minimize(rosen, x_0, method='Newton-CG', jac=rosen_der, hess=rosen_hess, options={'xtol': 1e-8, 'disp': True})print "Result of minimizing Rosenbrock function via Newton-Conjugate-Gradient algorithm (Hessian):"print res

Optimization terminated successfully. Current function value: 0.000000 Iterations: 20 Function evaluations: 22 Gradient evaluations: 41 Hessian evaluations: 20Result of minimizing Rosenbrock function via Newton-Conjugate-Gradient algorithm (Hessian): status: 0 success: True njev: 41 nfev: 22 fun: 1.47606641102778e-19 x: array([ 1., 1., 1., 1., 1.]) message: 'Optimization terminated successfully.' nhev: 20 jac: array([ -3.62847530e-11, 2.68148992e-09, 1.16637362e-08, 4.81693414e-08, -2.76999090e-08])

对于一些大型的优化问题，Hessian矩阵将异常大，牛顿共轭梯度法用到的仅是Hessian矩阵和一个任意向量的乘积，为此，用户可以提供两个向量，一个是Hessian矩阵和一个任意向量$mathbf{p}$的乘积，另一个是向量$mathbf{p}$，这就减少了存储的开销。记向量$mathbf{p} = (p_1, ldots, p_{N-1})$，可有

[ mathbf{H(x)p} = begin{bmatrix} (1200x0^2 – 400x_1 + 2)p_0 -400x_0p_1 vdots -400x{i-1}p{i-1} + (202 + 1200x_i^2 – 400x{i+1})pi – 400x_ip{i+1} vdots -400x{N-2}p{N-2} + 200p_{N-1} end{bmatrix} ]

我们定义如下函数并使用牛顿共轭梯度方法寻优：

In[20]:

def rosen_hess_p(x, p): x = np.asarray(x) Hp = np.zeros_like(x) Hp[0] = (1200*x[0]**2 - 400*x[1] + 2)*p[0] - 400*x[0]*p[1] Hp[1:-1] = -400*x[:-2]*p[:-2]+(202+1200*x[1:-1]**2-400*x[2:])*p[1:-1] -400*x[1:-1]*p[2:] Hp[-1] = -400*x[-2]*p[-2] + 200*p[-1] return Hpres = opt.minimize(rosen, x_0, method='Newton-CG', jac=rosen_der, hessp=rosen_hess_p, options={'xtol': 1e-8, 'disp': True})print "Result of minimizing Rosenbrock function via Newton-Conjugate-Gradient algorithm (Hessian times arbitrary vector):"print res

Optimization terminated successfully. Current function value: 0.000000 Iterations: 20 Function evaluations: 22 Gradient evaluations: 41 Hessian evaluations: 58Result of minimizing Rosenbrock function via Newton-Conjugate-Gradient algorithm (Hessian times arbitrary vector): status: 0

转载请注明：数据分析 » 量化分析师的Python_python 金融量化分析_python金融大数据分析

线性规划变量函数顶点问题

# 上一篇：一个简单的C语言程序，求解

# 下一篇：r语言求平均值