---

 一、线性规划

1.1简介

       在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济 效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记 LP) 则是数学规划的一个重要分支。自从 1947 年 G. B. Dantzig 提出 求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深 入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性 规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.2标准型         线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以 是小于号也可以是大于号。为了避免这种形式多样性带来的不便， Matlab 中规定线性 规划的标准形式为 其中 c 和 x 为 n 维列向量， A 、 Aeq 为适当维数的矩阵， b 、 beq 为适当维数的列向 量。在实际问题中，min中x为所求结果，s.t.( 即 subject to)中x为约束条件。

 

1.3 解题方法

1.3.1图解法

     图解法简单直观，有助于我们了解线性规划问题求解的基本原理。现在让我们用图解法解决以下问题 例 1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为 4000 元与 3000 元。 生产甲机床需用 A 、 B 机器加工，加工时间分别为每台 2 小时和 1 小时；生产乙机床需用 A 、 B 、 C 三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为 A 机器 10 小时、 B 机器 8 小时和 C 机器 7 小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 我们先应用图解法来 求解例 1 。对于每一固定的值 z ，使目标函数值等于 z 的点构成的直线称为目标函数等位线，当 z 变动时，我们得到一族平行直线。对于例 1 ，显然等位线越趋于右上方，其 上的点具有越大的目标函数值。不难看出，本例的最优解为 x * = (2,6) T ，最优目标值 z * = 26 。

 1.3.2 Matlab解题方法

         以标准型为例，基本函数形式为 linprog(c,A,b)，它的返回值是向量 x 的值。还有其它的一些函数调用形式（在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如： [x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS) 这里 fval 返回目标函数的值，LB 和 UB 分别是变量 x 的下界和上界，x0 是 x 的初始值，OPTIONS 是控制参数。

编写M文件

 根据matlab中标准型的格式要求，将大于等于换成小于等于，所以添加一负号，运行结果如下：

 1.4可以转化成线性规划的问题

      很多问题看似复杂但是可以通过转化成线性规划来求解，例如：

可以引入两个参数的形式将x和x的绝对值表示出来， 

 

 这样就可以通过约束u、v的范围和条件来对x进行求解，

 

 二、问题分类

2.1 运输问题

2.2 指派问题

 

对于上述指派问题，我们定义通过定义x的值实现指派，其解以矩阵的形式呈现，其中每一行只有一个1，其余元素皆为0，由此转换成0-1规划问题，降低计算复杂度。由于指派问题的特殊性，又存在着由匈牙利数学家 Konig 提出的更为简便的解法—匈牙利算法。算法主要依据以下事实：如果系数矩阵C = (cij) 一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵 B = (bij) ，则以C 或 B 为系数矩阵的指派问题具有相同的最优指派。

2.3 投资的收益和风险预估

市场上有 n 种资产 s i （ i = 1,2,.... , n ）可以选择，现用数额为 M 的相当大的资金作一个时期的投资。这 n 种资产在这一时期内购买 s i 的平均收益率为 r i ，风险损失率为 q i ，投资越分散，总的风险越少，总体风险可用投资的 s i 中最大的一个风险来度量。

 对题中符号做出如下规范：

根据体中相关要求可做出假设：

 根据做出的假设可以建立相关的数学模型：

 根据题目的要求：收益尽可能大，风险尽可能小，所以本题应是一个多目标类模型，

现在对模型进行简化

 

模型一   固定风险水平，优化收益

 

 建模分析：

约束分析：

 

 由于a是任意给定的的风险量度，没有一个准确的准则，不同的投资者有不同的风险考虑。本题我们从a=0开始，以0.001为步长进行循环搜索，编程如下：

a=0;
hold on
while a<0.05
    c=[0.05,0.27,0.19,0.185,0.185];
    A=[zeros(4,1),diag([0.025,0.015,0.055,0.026])];
    b=a*ones(4,1);
    Aeq=[1,1.01,1.02,1.045,1.065];
    beq=1;
    LB=zeros(5,1);
    [x,Q]=linprog(-c,A,b,Aeq,beq,LB);
    Q=-Q;
    plot(a,Q,'*r');
    a=a+0.001;  
end
xlabel('a'),ylabel('Q')

以图表形式呈现：

 结果分析：

1. 风险大，收益也大。 2 ．当投资越分散时，投资者承担的风险越小，这与题意一致。即： 冒险的投资者会出现集中投资的情况，保守的投资者则尽量分散投资。 3 ．在 a = 0.006 附近有一个转折点，在这一点左边，风险增加很少时，利润增长 很快。在这一点右边，风险增加很大时，利润增长很缓慢，所以对于风险和收益没有特 殊偏好的投资者来说，应该选择曲线的拐点作为最优投资组合，大约是 a = 0.6% ， Q = 20% ，所对应投资方案为： 风险度 a = 0.006 ，收益 Q = 0.2019 ， x 0 = 0 ， x 1 = 0.24 ， x 2 = 0.4 ， x 3 = 0.1091 ， x 4 = 0.2212 。