最优化方法ppt课件.ppt

《最优化方法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一讲线性规划的基本概念线性规划问题及其数学模型线性规划的图解法线性规划问题的标准型标准型线性规划的解线性规划的基本原理1.问题的提出：在生产管理的经营活动中，通常需要对“有限的资源”寻求“最佳”的利用或分配方式。有限资源：劳动力、原材料、设备或资金等最佳:有一个标准或目标，使利润达到最大或成本达到最小。有限资源的合理配置有两类问题合理的使用有限的资源，使生产经营的效益达到最大在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所消耗的资源数最少1.1线性规划问题及其数学模型例１:某制药厂生产甲、乙两种

2、药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：每吨产品的消耗每周资源总量甲乙维生素（公斤）3020160设备（台）5115已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据市场需求调查的结果，甲药品每周的产量不应超过4吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？定义:为生产甲、乙两种药品的计划产量数目标：要使总利润最大化约束：每周资源总量的限制，甲种药品每周产量不应超过4吨的限制计划生产数不可能是负数，每吨产品

3、的消耗每周资源总量甲乙维生素（公斤）3020160设备（台）5115单位利润(万元)5２数学模型为这是一个如何合理的使用有限的资源，使生产经营的效益达到最大的数学规划问题。在满足一组约束条件的限制下，寻求决策变量x1，x2的决策值，使目标函数达到最大值。每吨产品的消耗每周资源总量甲乙维生素（公斤）3020160设备（台）5115单位利润(万元)5２例２：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品。已知甲、乙两种原料都含有A、B、C三种化学成分，两种原料分别所含三种化学成分的百分比含

4、量，以及按合同规定的产品中三种化学成分的最低含量如下表所示：已知甲、乙两种原料的成本分别是每公斤3元和2元，厂方希望总成本达到最小，问如何配置该产品？原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155化学成分定义分别为每公斤产品中甲，乙两种原料的数量，目标：使总成本最小化约束：配料平衡条件，产品中A、B、C三种化学成分的最低含量非负性条件原料化学成分含量（%）产品中化学成分的最低含量（%）甲乙A1234B232C3155单位成本（元）３２化学成分数学模型：这是一个原料配制问题，是在

5、生产任务确定的条件下，合理的组织生产，使所消耗的资源最少的数学规划问题。满足一组约束条件的同时，寻求变量和的值使目标函数取得最小值。例３:某铁器加工厂要制作100套钢架，每套要用长为2.9米，2.1米和1.5米的圆钢各一根。已知原料长为7.4米，问应如何下料，可使材料最省？分析：在长度确定的原料上截取三种不同规格的圆钢，可以归纳出8种不同的下料方案：圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104料头（米）00.10.20.30.80.91.１1.4问题归纳为如何混合使用

6、这8种不同的下料方案，来制造100套钢架，且要使剩余的余料总长为最短。设表示用第j种下料方案下料的原料根数，j=1,2,…,8,目标：使余料总长度最小化minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8约束：三种规格圆钢根数x1+2x2+x4+x6=1002x3+2x4+x5+x6+3x7=1003x1+x2+2x3+3x5+x6+4x8=100非负取整条件xj≥0(j=1,2…8)且取整数圆钢（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．5

7、31203104余料（米）00.10.20.30.80.91.１1.4数学模型s.t.这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。满足一组约束条件的同时，寻求变量至的值,使目标函数取得最小值。且为整数与规划问题有关的数学模型总有两部分组成：约束条件：反映了有限资源对生产经营活动的种种约束，或者生产经营必须完成的任务；目标函数：反映生产经营者在有限资源条件下希望达到的生产或经营的目标。2.线性规划的一般数学模型线性规划模型的特征：（1）用一组决策变量x1，x2，…,

8、xn表示某一方案，且在一般情况下，变量的取值是非负的。（2）有一个目标函数，这个目标函数可表示为这组变量的线性函数。（3）存在若干个约束条件，约束条件用决策变量的线性等式或线性不等式来表达。（4）要求目标函数实现最大化（max）或最小化（min）。满足上述4个特征的规划问题称为线性规划问题。通常称为决策变量，为价值系数，为消耗系数,　　　　为资源限制系数。线