线性规划ppt课件.ppt

文档介绍：线性规划的理论与方法
y
线性规划的理论与方法
线性规划是指目标函数是由线性函数给出,约束条件由线性等式或者不等式给出的优化问题。
最早提出线性规划问题并进行专门研究的学者—康托洛维奇。
康托洛维奇在20世纪30年代就提出了求解线性规划问题的“解乘数法”。
自从1947年美国学者丹青格提出求解线性规划问题的一般方法—单纯形方法后,才使线性规划的理论和方法日臻成熟。
(1)由决策变量构成,反映决策的目标是线性函数。
(2)一组由决策变量的线性等式或不等式构成约束
条件。
(3)对决策变量取值范围加以限制的非负约束。
线性规划模型的特征
例1:某工厂生产甲、乙两种产品,每件产品的利润、
所消耗的材料、工时及每天的材料限额和工时限额,
。试问如何安排生产,使每天所得的利润为最大?

甲
乙
限额
材料
2
3
24
工时
3
2
26
利润(元/件)
4
3
设每天生产甲、乙两种产品分别为 x1 , x2 则该问题可描述为由如下数学模型:
线性规划问题的标准型
如下形式的线性规划模型被称作标准型:
也可用矩阵形式描述:
A:资源消耗系数矩阵
b: 资源限量向量
C:价格向量
X:决策变量向量
同时我们对标准型作如下假定:
一般的线性规划问题通过变换可化成标准型, 变
换方式可以归结为:
线性规划问题解的概念
对于线性规划问题
可行解
基解
基可行解