1-线性规划.ppt

线性规划方法
§1 线性规划及其单纯形求解方法
§2 线性规划的对偶理论
1
康托洛维奇生产组织与计划中的数学方法,一本小册子,1939;
康托洛维奇“最佳资源利用的经济计算”——1942完成、1959发表的著作;
自1947年丹泽()提出求解线性规划问题的一般方法--单纯形法之后,线性规划在理论上趋于成熟,应用日益广泛与深入;随着电子计算机的发展和计算速度的不断提高,其适用的领域更加广泛,它已成为必不可少的重要手段之一。
1975年库伯曼斯(Koopmans)因对资源最优分配理论的贡献而获年诺贝尔经济学奖;
冯•诺伊曼和摩根斯坦1944年发表的《对策论与经济行为》涉及与线性规划等价的对策问题及线性规划对偶理论。
2
线性规划方法是数学规划中发展较快、应用较广和比较成熟的一个分支。
最优化/运筹学的最基本的方法之一,网络规划,整数规划,目标规划和多目标规划都是以线性规划为基础的。
解决稀缺资源最优分配的有效方法,使付出的费用最小或获得的收益最大。
线性规划的基础是线性变换.
3
线性规划的数学模型
线性规划的标准形式
线性规划的解及其性质
线性规划问题的求解方法——单纯形法
线性规划应用实例: 农业生产结构优化模型
§1 线性规划及其单纯形求解方法
4
(1) 线性规划的实例
线性规划研究的两类问题:
▲如何统筹安排一项任务,以尽量用最少的资源(人力、物力和财力)来完成它;
▲如何利用一定量的人力、物力和资金来完成最多的任务。
它们都属于最优规划的范畴。以下为一些实例。
一、线性规划的数学模型
5
运输问题
假设某种物资(譬如水泥、钢铁、粮食等)有m个产地,n个销地。第i产地的产量为ai(i=1,2,…,m),第j 销地的需求量为bj(j=1, 2,…,n),它们满足产销平衡条件。
如果产地i到销地j的单位物资的运费为cij,要使总运费达到最小可这样安排物资的调运计划。
设xij表示由产地i供给销地j的物资数量,则上述问题可以表述为求一组实值变量xij(i=1,2,…,m;j=1,2,…,n),使其满足:
而且使:
6
资源利用问题
假设某地区拥有m种资源,其中,第i种资源在规划期内的限额为bi(i=1,2,…,m)。这m种资源可用来生产n种产品,其中,生产单位数量的第j种产品需要消耗的第i种资源的数量为aij(i=1,2,…,m;j=1,2, …,n),第j种产品的单价为cj(j=1,2, …,n)。要使规划期内资源利用的总产值达到最大,安排这几种产品的生产计划如下:
设第j种产品的生产数量为xj(j=1,2,…,n),则上述资源问题就是:
求一组实数变量xj(j=1,2,…,n),使其满足
7
合理下料问题
用某种原材料切割零件A1,A2, …,Am的毛坯,现已设计出在一块原材料上有B1,B2,…,Bn种不同的下料方式,如用Bj下料方式可得Ai种零件aij个,设Ai种零件的需要量为bi个。试问应该怎样组织下料活动,才能使得既满足需要,又使用去的原材料最少?
设采用Bj方式下料的原材料数为xj,则问题可表示为:
求一组整数变量xj(j=1,2,…,n),使得
8
(2) 线性规划的数学模型
以上例子表明,线性规划问题具有以下特征:
① 每一个问题都用一组未知变量(x1,x2,…,xn)表示某一规划方案,其一组定值代表一个具体的方案,而且通常要求这些未知变量的取值是非负的。
② 每一个问题的组成部分:
一是目标函数,按照研究问题的不同,常常要求目标函数取最大或最小值;
二是约束条件,它定义了一种求解范围,使问题的解必须在这一范围之内。
③ 每一个问题的目标函数和约束条件都是线性的。
9
由此可以抽象出线性规划问题的数学模型,一般形式为:
在线性约束条件
以及非负约束条件
xj≥0(j=1,2,…,n)
下,求一组未知变量xj (j=1,2,…,n)的值,使
10