第一章-线性规划与单纯形法ppt课件.ppt

第一章-线性规划与单纯形法ppt课件.ppt

ID:58580170

大小:2.59 MB

页数:253页

时间:2020-10-20

第一章-线性规划与单纯形法ppt课件.ppt_第1页
第一章-线性规划与单纯形法ppt课件.ppt_第2页
第一章-线性规划与单纯形法ppt课件.ppt_第3页
第一章-线性规划与单纯形法ppt课件.ppt_第4页
第一章-线性规划与单纯形法ppt课件.ppt_第5页
资源描述:

《第一章-线性规划与单纯形法ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第一章线性规划与单纯形法第一节线性规划问题及其数学模型第二节线性规划问题的几何意义第三节单纯形法第四节单纯形法的计算步骤第五节单纯形法的进一步讨论第六节应用举例1第一节线性规划问题及其数学模型一、问题的提出二、图解法三、线性规划问题的标准形式四、线性规划问题的解的概念2线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟,在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后,线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管

2、理的重要手段之一。解线性规划问题的方法有多种,以下仅介绍单纯形法。3一、问题的提出例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗,如下表所示。资源产品ⅠⅡ拥有量设备128台时原材料A4016kg原材料B0412kg每生产一件产品Ⅰ可获利2元,每生产一件产品Ⅱ可获利3元,问应如何安排计划使该工厂获利最多?4利润z=2x1+3x25本问题的数学模型为:这就是一个最简单的线性规划模型。6例2建立LP数学模型某家电厂家利用现有资源生产两种产品,有关数据如下表:设备A设备B调试工序利润(元)0612521115时24时5时产品Ⅰ产

3、品ⅡD如何安排生产,使获利最多?7如何安排生产,使获利最多?厂家设Ⅰ产量–––––Ⅱ产量–––––8每一个线性规划问题都用一组决策变量表示某一方案,这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的;都有关于各种资源和资源使用情况的技术数据,创造新价值的数据;存在可以量化的约束条件,这些约束条件可以用一组线性等式或线性不等式来表示;都有一个达到某一目标的要求,可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同,要求目标函数实现最大化或最小化。上述两个问题具有的共同特征:9线性规划模型的一般形式目标函数满足约束条件价值系数技术(工艺)系数限额系数(

4、资源)非负约束条件10二、图解法例1是一个二维线性规划问题,因而可用作图法直观地进行求解。114x1=164x2=12x1+2x2=8x1x248430124x1=164x2=12x1+2x2=8x1x248430Q1可行域13目标值在(4,2)点,达到最大值144x1=164x2=12x1+2x2=8x1x248430Q2(4,2)Q1可行域x1+2x2=84x1=1614图解法求解步骤由全部约束条件作图求出可行域;作目标函数等值线,确定使目标函数最优的移动方向;平移目标函数的等值线,找出最优点,算出最优值。15练习:用图解法求解目标函数MaxZ=2x1+x2约束条件5x

5、2156x1+2x224x1+x25x1、x20169—8—7—6—5—4—3—2—1—0

6、

7、

8、

9、

10、

11、

12、

13、

14、123456789x1x2x1+x2=5目标函数MaxZ=2x1+x2约束条件5x2156x1+2x224x1+x25x1、x206x1+2x2=245x2=15图解法12—11—10—179—8—7—6—5—4—3—2—1—0

15、

16、

17、

18、

19、

20、

21、

22、

23、123456789x1x2x1+x2=5目标函数MaxZ=2x1+x2约束条件5x2156x1+2x224x1+x25x1、x206x1+2x2=245x2=15图解法12—11—10—可行域189—8

24、—7—6—5—4—3—2—1—0

25、

26、

27、

28、

29、

30、

31、

32、

33、123456789x1x2x1+x2=5目标函数MaxZ=2x1+x2约束条件5x2156x1+2x224x1+x25x1、x206x1+2x2=245x2=1512—11—10—x2=-2x16x1+2x2=24x1+x2=5最优解(3.5,1.5)目标值在(3.5,1.5)点,达到最大值8.519(1)无穷多最优解(多重最优解)(2)无界解(3)无可行解上例中求解得到问题的最优解是惟一的通过图解法,可观察到一般线性规划的解还可能出现一下几种情况:20无穷多最优解(多重最优解)4x1=164x2=12x1+2x2=

34、8x1x248430可行域Q2Q3MaxZ=2x1+4x2214x1=16x1x240无界解(a)可行域22无界解(b)23当存在相互矛盾的约束条件时,线性规划问题的可行域为空集,即无可行解,也不存在最优解。无可行解4x1=164x2=12x1+2x2=8x1x230原可行域8增加一个新的约束条件24可行域和解有以下几种情况(a)可行域有界有唯一最优解(b)可行域有界有无穷多最优解25(c)可行域无界有唯一最优解(d)可行域无界有无穷多最优解(e)可行域无界无最优解(无界解)26(f)可行域为空集无可行解27LP问

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。