1.1 基于MATLAB的线性优化
1.1.1 背景介绍
线性规划最早建立于优化理论，求解线性规划的单纯形法是20世纪十大数学算法之一，但随着非线性理论的发展，很多线性问题都可用非线性方法求解(本质上讲，线形是非线性的特例)。线性理论的学习有助于读者加深对数学算法的理解，有助于读者自己编写算法。
1. 线性规划应用
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，是辅助人们进行科学管理的一种数学方法。在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，如改善生产工艺，使用新设备和新型原材料：二是生产组织与计划的改进，即合理安排人力物力资源。线性规划研究的是在一定条件下，合理安排人力、物力等资源，使经济效果达到最好。一般的，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。
2. 线性规划的求解方法
求解线性规划问题的基本方法是单纯形法，随着线性优化算法的发展，为了提高解题速度，相继出现了改进单纯形法、对偶单纯形法、原始对偶方法、分解算法和各种多项式时间算法。
目前MATLAB求解线性规划的算法主要有内点法(interior-Point Methods)与单纯形法(Simplex Method)。
内点法是一种求解线性规划或非线性凸优化问题的算法，由John von Neumann发明，后被Narendra Karmarkar于1984年推广应用到线性规划，即Karmarkar算法。内点法的特点是将构造的新无约束目标函数一一惩罚函数定义在可行域内，并在可行域内求惩罚函数的极值点，即求解无约束问题时的探索点总是在可行域内，这样在求解内点惩罚函数的序列无约束优化问题的过程中求得的系列无约束优化问题的解总是可行解，在可行域内部逐步逼近原约束优化问题的最优解。内点法是求解不等式约束最优化问题的一种有效方法，不能处理等式约束，因为构造的内点惩罚函数是定义在可行域内的函数，而等式约束优化问题不存在可行域空间。
单纯形法是求解线性规划问题的通用方法，由美国数学家G.B.丹齐格于1947年首先提出，它的理论根据是线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在，必在该凸集的某顶点处达到，顶点所对应的可行解称为基本可行解。单纯形法的基本思想是先找出一个基本可行解，对它进行鉴别，看是否是最优解，若不是，则按照一定法则转换到另一改进的基本可行解再鉴别：若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解，如果问题无最优解也可用此法判别。单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的基本可行解。④按步骤3进行法代，直到对应检验数满足最优性条件(这时目标函数值不能再改善)，即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，终止迭代。具体算法本章不再详述，若有兴趣可阅读相关文献。
1.1.2 线性优化MATLAB求解
1. Iinprog函数
MATLAB求解线性优化的函数为linprog，在优化工具箱Optimization-Toolbox中。linprog针对线性函数的数学模型为:
其中A为不等式约束的系数矩阵，b为不等式约束值向量，Aeq为等式约束的系数矩阵，beq为等式约束值向量，Ib为x取值下限，ub为x 取值上限。
Linprog的计算方法主要有两个：内点法与单纯形法。
Linprog函数语法为:
2. 线性规模目标函数
3. 内点法求解
调用linprog使用默认算法(linprog的默认算法为内点法)计算线性规划问题，M文件为linprogtest1.m。
4. 单纯形法求解
设置linprog使用单纯形法，且显示每次选代计算结果，操作如下:
调用linprog进行计算：
计算结果Command Window输出：
1.1.3 含参数线性规划
在研究工作中，常常有不同的背最假设或参数假设，不同的参数假设会有不同的模型，例如:
对应不同参数α=[α1，α2，α3]，上述优化问题有不同的解。当参数变化时，为便于优化问题的求解，可以将上述问题写成参数优化问题，在进行每次新的计算前，只需修改参数 α= [α1，α2，α3]即可。
通过M文件linprogwithpara.m编程求解，其语法为:
