求解器简介

两种解决策问题的优化方法：

• 启发式算法

• 精确算法

精确算法特点：

1. 精确算法可以得到最优解，启发式算法不能保证求得最优解（以及可行解与最优解的偏离） ；

2. 精确算法可以判断问题的不可行性，启发式方法不能判断 ；

3. 精确算法易于维护，容易适应不断变化的业务条件，启发式方法通常是针对特定问题的，条件的改变很容易使启发式方法无效。

求解器主要是用于求解线性规划问题（算法是用精确算法，如：单纯形法、内点法）

• 线性规划（Linear Programming，简称LP）：目标函数和约束条件皆为线性的最优化问题；

• 混合整数规划（mixed integer programming，简称MIP）：要求部分的变量为整数的线性规划问题；

• 整数规划（integer programming, 简称IP）：要求所有的变量都为整数的线性规划问题；

• 0-1整数规划：要求所有的变量都要是0或1。

线性规划问题

模型建立：

1. 确定决策变量：根据影响所要达到目的的因素找到决策变量 ；

2. 确定目标函数：由决策变量和所在达到目的之间的函数关系确定目标函数 ；

3. 确定约束条件：由决策变量所受的限制条件确定决策变量所要满足的约束条件 ；

4. 模型求解：在可行域内求目标函数的最优解及最优值。

线性规划问题标准形式：

其中x是n维变量，c∈R^n是目标系数，c^T x是目标函数， b∈R^m是约束边界, A∈R^(m∗n)是约束矩阵

文件格式

建模文件： LP 格式、 MPS 格式，规划软件对 MPS 文件支持的更好

线性规划模型：

MPS格式：

MPS文件：

LP文件：

数据结构

内存问题：LP的规模通常是由约束矩阵A的规模决定的，矩阵的元素通常用8个字节的double型储存，假设矩阵有m行，n列，则直接储存A需要8mn字节。如果A有10000行，20000列（不是特别大规模的），那么需要1.6G内存储存A，一方面内存要求高，另一方面对矩阵A的操作困难。

稀疏性：大规模LP通常含有大量的零元，非零元占比非常小，这个性质称为稀疏性，即A为稀疏矩阵。

稀疏矩阵的储存：只存储矩阵中的非0 元素以及元素所在矩阵中的行标和列标。

1、三元组顺序表，存储的是三元组（即由 3部分数据组成的集合），组中数据分别表示（行标，列标，元素值）。

2、行逻辑链接的顺序表，是在三元组顺序表的基础上增加一个专门记录矩阵中每一行第一个非0元在一维数组中的位置（提高了提取数据时遍历数组的效率）。

三元组顺序表和行逻辑链接的顺序表都是使用数组存储稀疏矩阵，数组 “不利于插入和删除数据”，以上两种压缩存储方式都不适合解决类似 "向矩阵中添加或删除非 0 元素" 的问题。

3、十字链表，采用的是 “链表+数组” 结构，

矩阵中的各行各列都各用一个链表存储，与此同时，所有行链表的表头存储到一个数组（rhead），所有列链表的表头存储到另一个数组（chead）中。两个指针域分别用于链接所在行的下一个元素以及所在列的下一个元素。

注：

1、十字链表便于插入和删除元素，但是元素访问比行（列）逻辑链接顺序表慢；

2、一般先用十字链表建立稀疏矩阵，然后转换为顺序表，以便快速进行求解。

求解算法

单纯形法

基本思想：在可行域的一个顶点处找到一个初始可行解，判断该解是不是最优，若不是，则迭代到下一个顶点处进行重复判断。

内点法

基本思想：迭代点在可行域的内部移动，并对接近可行域边界的点施加惩罚（加入障碍），距边界越近障碍越大，相当于在可行域的边界筑起一道很高的“围墙”，阻止迭代点穿越边界，从而将最优解“挡”在可行域内。

建模建议

避免数字问题

• 矩阵：系数不要太大/太小 

• 变量界限, 右侧项, 目标系数:不要太大 

• 避免接近平行的约束 

• 参考书籍：H.P.Williams:ModelBuilding in Mathematical Programming