文档介绍：第一章线性规划
-
线性规划及其实例
在人们的生产实践中,经常会遇到如何利用现有资源来安排生产,以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划,而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。
例子
例1 某机床厂生产甲、乙两种机床,每台销售后的利润分别为4000元与3000元。生产甲机床需用机器加工,加工时间分别为每台2小时和1小时;生产乙机床需用三种机器加工,加工时间为每台各一小时。若每天可用于加工的机器时数分别为机器10小时、机器8小时和机器7小时,问该厂应生产甲、乙机床各几台,才能使总利润最大?
线性规划的Matlab标准形式
线性规划的目标函数可以是求最大值,也可以是求最小值,约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便,Matlab中规定线性规划的标准形式为
其中c和x为n维列向量,b为m维列向量,A为m×n矩阵。
线性规划问题的解的概念
一般线性规划问题的标准型为
可行解满足约束条件(4)的解x=(x1,x2,...,xn),称为线性规划问题的可行解,而使目标函数(3)达到最小值的可行解叫最优解。
可行域所有可行解构成的集合称为问题的可行域,记为。
(3)
(4)
从上面的图解过程可以看出并不难证明以下断言:
(1)可行域可能会出现多种情况。R可能是空集也可能是非空集合,当R非空时,它必定是若干个半平面的交集(除非遇到空间维数的退化)。R既可能是有界区域,也可能是无界区域。
(2)在R非空时,线性规划既可以存在有限最优解,也可以不存在有限最优解(其目标函数值无界)。
(3)R非空且LP有有限最优解时,最优解可以唯一或有无穷多个。
(4)若线性规划存在有限最优解,则必可找到具有最优目标函数值的可行域R的“顶点”。
求解线性规划的Matlab解法
单纯形法是求解线性规划问题的最常用、最有效的算法之一。单纯形法是首先由
e Dantzig于1947年提出的,近60年来,虽有许多变形体已被开发,但却保持着同样的基本观念。由于有如下结论:若线性规划问题有有限最优解,则一定有某个最优解是可行区域的一个极点。基于此,单纯形法的基本思路是:先找出可行域的一个极点,据一定规则判断其是否最优;若否,则转换到与之相邻的另一极点,并使目标函数值更优;如此下去,直到找到某一最优解为止。