算法设计与应用——线性规划
线性规划介绍
线性规划描述了一大类优化任务，这些任务的共同特点是约束条件和优化准则都可以表示为线性函数。
线性规划所研究的对象属于最优化的范畴，本质上是一个极值问题。三个基本要素：
- 决策变量：决策者所控制的量，它们的取值由决策者决定
- 约束条件：决策变量在这些限制范围内才有意义
- 目标函数：代表决策者希望对其优化的指标。目标函数是决策变量的函数。
示例：利润最大化
巧克力作坊生成两种产品：Pyramide和Nuit
-假设每天生产x1盒pyramide和x2盒Nuit，前者利润为$1，后者每盒$6
-市场需求，每日最多200盒Pyramide,300盒Nuit
-巧克力作坊每日最多生成400盒巧克力
问：如何做到利润最大化
线性规划：
-决策变量：x1,x2
-目标函数：max 1x1+6x2
-约束条件：x1<=200
x2<=300
x1+x2<=400
x1>=0&&x2>=0
图解法求解
建立线性规划数学模型的步骤
- 首先，决定决策变量
- 决定约束条件
- 决定目标函数
单纯形法
示例：更多产品
巧克力作坊推出一种新产品 Luxe，每盒利润$13。（原来两种产品：Pyramide($1)和Nuit($6)）
市场需求，每日最多200盒Pyramide,300盒Nuit
三种巧克力每天最多生产400 盒。
Nuit和Luxe 需要使用相同的包装设备，而且每个Luxe 的包装需要使用三次该设备，设备每天最多使用600次。
最优的生产计划应该又是怎样的呢？
线性规划
决策变量：x1、x2、x3 分别表示每天生产的数量，
目标函数：max x1+6x2+13x3
S.t. ： x*1≤200
x2≤300
x1+x2+x3≤400
x2+3x3≤600
x1, x2, x3≥0
单纯形法求解线性规划（爬山法）
介绍
- 算法从一个顶点开始，不断重复地寻找 目标函数值较高的邻居顶点(该顶点与原顶点由可行区域的一条边相连)，并向其移动，一旦再也找不到更高的邻居，结束计算
- 对于线性规划问题是一定能找出最优解的，无论是几维
实现方法（不作教学要求）：
- 在每次迭代中，单纯形法需要完成如下两项任务：
- 1.检测当前顶点是否最优，如果是，则退出
- 2.决定下一个移动方向
应用
- 单纯形法解决 示例：利润最大化
- 单纯形法解决 示例：更多产品
单纯形法的工作状态
线性规划问题的标准形式
什么是标志型
线性规划问题的数学模型有各种不同的形式。为了便于讨论，需要将线性规划数学模型写成统一格式
线性规划问题的标准型是
- 标准型的特点为
- 目标函数为最大值形式
- 约束条件用等式表示且等 式右端的常数为非负值
- 决策变量非负。
标准化
把一般的线性规划问题化成标准型的过程称为线性规划问题的标准化
- 方法：
例子
matlab或python解决问题
同一个模型
配套作业
wechat
alipay