一、以例题分析步骤理解LP线性规划算法
1、分析问题
某机床厂生产甲、乙两种机床,每台销售后的利润分别为4000 元与3000 元。生产甲机床需用 A、B机器加工,加工时间分别为每台 2 小时和 1 小时;生产乙机床需用 A、B、C三种机器加工,加工时间为每台各一小时。若每天可用于加工的机器时数分别为A 机器10 小时、B 机器8 小时和C 机器7 小时,问该厂应生产甲、乙机床各几台,才能使总利润最大?
分析:上述问题的数学模型:设该厂生产x1 台甲机床和x2 台乙机床时总利润最大,则x1、x2应满足
这里变量x1、x2称之为决策变量,(1)式被称为问题的目标函数,(2)中的几个不等式是问题的约束条件,记为s.t.(即subject to)。由于上面的目标函数及约束条件均为线性函数,故被称为线性规划问题。
经验:总之,线性规划问题是在一组线性约束条件的限制下,求一线性目标函数最大或最小的问题。在解决实际问题时,把问题归结成一个线性规划数学模型是很重要的一步,但往往也是困难的一步,模型建立得是否恰当,直接影响到求解。而选适当的决策变量,是我们建立有效模型的关键之一。
2、线性规划的 Matlab 标准形式
线性规划的目标函数可以是求最大值,也可以是求最小值,约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便,Matlab 中规定线性规划的标准形式为
其中 c 和x 为n 维列向量, A 、Aeq 为适当维数的矩阵, b 、beq 为适当维数的列向量。
3 线性规划问题的解的概念
一般线性规划问题的(数学)标准型为
可行解 满足约束条件(4)的解x=(x1,x2,x3……xn),称为线性规划问题的可行解,而使目标函数(3)达到最大值的可行解叫最优解。
可行域 所有可行解构成的集合称为问题的可行域,记为R 。
4 线性规划的图解法
图解法简单直观,有助于了解线性规划问题求解的基本原理。我们先应用图解法来求解例1。对于每一固定的值z ,使目标函数值等于z 的点构成的直线称为目标函数等位线,当z 变动时,我们得到一族平行直线。对于例1,显然等位线越趋于右上方,其上的点具有越大的目标函数值。不难看出,本例的最优解为x* = (2,6)T ,最优目标值z* = 26。
5 求解线性规划的Matlab 解法
单纯形法是求解线性规划问题的最常用、最有效的算法之一。这里我们就不介绍单纯形法,有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的Matlab解法。
基本函数形式为 linprog(c,A,b),它的返回值是向量x 的值。还有其它的一些函数调用形式(在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式),如:
这里fval 返回目标函数的值,LB 和UB 分别是变量x 的下界和上界, x0是x 的初始值,OPTIONS 是控制参数。