《数学规划模型》PPT课件.ppt

第6章 数学规划模型,在一系列客观或主观限制条件下，寻求使关注的某个或多个指标达到最大（或最小）的决策。例如：运输方案要在满足物资需求和装载条件下安排从各供应点到各需求点的运量和路线，使运输总费用最低；生产计划要按照产品工艺流程和顾客需求，制定原料、零件、部件等订购、投产的日程和数量，尽量降低成本使利润最高。上述这些决策问题通常称为优化问题。虽然最优化可以追溯到十分古老的极值问题，然而，它成为一门独立的学科是在上世纪40年代末，是在1947年Dantzing提出求解一般线性规划问题的单纯型法之后。,问题驱动：高等教育收费,学费问题涉及到每一个大学生及其家庭，是一个敏感而又复杂的问题：过高的学费会使很多学生无力支付，过低的学费又使学校财力不足而无法保证质量。高等教育属于非义务教育，其经费在世界各国都由政府财政拨款、学校自筹、社会捐赠和学费收入等几部分组成。对适合接受高等教育的经济困难的学生，一般可通过贷款和学费减、免、补等方式获得资助，品学兼优者还能享受政府、学校、企业等给予的奖学金。学费问题近来在各种媒体上引起了热烈的讨论。据中国国情，利用数学建模的方法，收集诸如国家生均拨款、培养费用、家庭收入等相关数据，就几类学校或专业的学费标准进行定量分析，得出明确、有说服力的结论。,问题背景分析,要确保有良好的高等教育质量，必须有相应的经费保障。高等教育的学费问题涉及到每一个大学生及其家庭。根据相关规定，高等教育属于非义务教育，其成本主要是根据高等教育收益分享情况进行分摊，即遵循“谁收益、谁负担”的原则。基于此理论，我国于1993年试行并轨招生，缴费上学制度开始在部分高校试行。到1997年，全国高校全部并轨收费。然而，自高等教育实行收费政策以来，收费标准出现了逐步攀升的情况，以至于学费水平在一定程度上成了人们关注的社会问题，也成为人们争议的社会焦点。,高等教育的经费主要由政府拨款、学校自筹、社会捐赠和学费收入等几部分组成，其中由受教育者及其家庭所承担的学费是本文主要的讨论对象。目前学费收入已成为高等学校办学经费的主要来源之一，也已成为维系学生与学校经济关系的主要纽带。,目标分析,高等教育收费要满足如下几个需求因素：目标1：培养质量指标（师资力量、教育设备、教学氛围）；目标2：学生就读指标；目标3：办学收益指标（办学获利）；目标4：学生收益指标。这是一个多因素的问题，多因素分析的方法有很多，解决高等教育收费问题的方法也有很多，但是结合实际，主要考虑制定最合理的学费价格和生均奖贷助学金。而“最”在数学上通常就是我们所说的优化问题。,6.1规划模型简介,模型分类在很多实际问题中，所能够提供的决策变量取值受到很多因素的制约，这样就产生了一般的优化模型，统称为数学规划模型。按照数学规划模型的具体特征可以将数学规划分为：线性规划，非线性规划，整数规划，多目标规划，目标规划等。,规划问题结构（三要素）,1、决策变量，通常是该问题要求解的那些未知量；2、目标函数，通常是该问题要优化（最小或最大）的那个目标的数学表达式；3、约束条件，由该问题对决策变量的限制条件给出，即允许取值的范围，称为可行域，常用一组关于的不等式（也可以有等式）来界定。,规划模型的一般形式,规划模型的分类,1、在模型中若目标函数和约束条件中的函数均为线性函数，则称为线性规划（简记为LP），否则就称为非线性规划（简记为NLP）。2、规划中的变量（部分或全部）限制为整数时，称为整数规划（简记为IP）。3、若整数规划模型中的决策变量只能取0或1，则称模型为0-1规划。如不加特殊说明，整数规划一般指整数线性规划,例1,s.t.,例2,s.t.,62数学规划模型实例及求解,1、线性规划问题数学模型 例2.1 加工奶制品的生产计划 一奶制品加工厂用牛奶生产A1、A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1、A2能全部售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤，设备乙的加工能力没有限制。试为该厂制定一个生产计划，使每天获利最大。,决策变量 设每天用x1桶牛奶生产A1，用x2桶牛奶生产A2 目标函数 设每天获利为Z元。x1桶牛奶可生产3x1公斤A1，获利24*3x1，x2桶牛奶可生产4 x2公斤A2，获利16*4 x2，故Z=24*3x1+16*4 x2 约束条件 原料供应 劳动时间 非负约束、均不能为负值,在LINGO模型窗口输入如下：Max=72*x1+64*x2;X1+x2=50;12*x1+8*x2=480;3*x1=100;,用鼠标单击菜单中的求解命令（SOLVE）就可以得到解答，结果窗口显示如下：Global optimal solution found at iteration:2 Objective value:3360.000 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000,假定A,B,C,D四种产品价格随产量的扩大而递减，其需求函数分别为,试确定四种产品的产量，以便使总收益最大。,例 设用甲、乙、丙三种有效资源生产A,B,C,D四种产品，产品的资源消耗定额及资源的有效供应量如表所示,解 设A,B,C,D四种产品的产量分别为x1,x2,x3和x4，则问题的目标函数（总收益函数）为：,注意到资源约束，上述问题可表为,下面用Lingo软件来求解上述的例子，打开Lingo执行文件，编程如下：Model:max=11*x1+12*x2+13*x3+14*x4-x5;x5=0.01*(x1*x1+2*x2*x2+3*x3*x3+4*x4*x4);x1+2*x2+3*x3+2*x4200;7*x1+9*x2+8*x3+x4300;3*x1+x3+7*x4400;end为了编制程序的方便，我们引入了中间变量 选择菜单“Solve”进行求解，得到输出 Objective value:1003.010 Variable Value Reduced Cost X1 0.000000 1.713858 X2 6.900608 0.4349500E-07 X3 23.00476 0.000000 X4 53.85646 0.000000 X5 132.8497 0.000000,。,某航空公司为满足客运量日益增长的需要，欲购置一批新的远程、中程及短程客机。每架远程客机价格6700万元，中程客机5000万元，短程客机3500万元。该公司现有资金7.5亿元可用于购买飞机。估计年净利润每架远程客机为420万元，中程客机300万元，短程客机230万元。该公司现有熟练驾驶员可用来配备30架新飞机。维修设备足以维修新增加40架新的短程客机，每架中程客机的维修量相当于4/3短程客机，而每架远程客机的维修量相当于5/3架短程客机。为获取最大利润，该公司应购买各类客机多少架？,设购买远程、中程、短程客机的数量分别为x1,x2,x3架,问题的数学模型为,，（目标函数）,，,，,，（约束条件）,，,。,将上述模型输入Lingo如下：max=420*x1+300*x2+230*x3;6700*x1+5000*x2+3500*x375000;x1+x2+x330;5*x1+4*x2+3*x3120;gin(x1);gin(x2);gin(x3);,得到最优解为,最优解为,元,6.4多目标规划,在许多实际问题中，衡量一个方案的好坏标准往往不止一个，例如设计一个导弹，既要射程最远，又要燃料最省，还要精度最高.这一类问题统称为多目标最优化问题或多目标规划问题.设在一段时间（比如两年）内，某市有b亿元资金可用于投资，有m个项目，A1，A2,Am 可供选择。若对第i个项目投资，需要资金bi亿元，可安排劳动力ai人就业，消耗能源ei(t)标准煤，可获利税收入ci亿元，若该市在这段时间内的能耗限额为e(t)标准煤，有a个人急需安置就业，欲确定一个最佳的投资方案，使该市所获得的利税总收入最多、安置的劳动力最多，而能耗最少？,z1为所获得的利税总收入，,z2为安置的劳动力的总数，,z3为总能耗,改写为如下形式：,，,，,多目标规划问题的求解多目标规划问题的解法大致可分为两类：直接解法和间接解法。到目前为止，关于直接解法的成果还不多，常用的多为间接解法。所谓间接解法是指：根据问题的实际背景和特征，设法将多目标的优化问题转化为单目标优化问题，从而获得满意解的方法。下面我们来介绍线性加权求和法。,对模型（）的p个目标函数,按其重要程度给以适当的权系数,作为新的目标函数，称为评价（目标）函数，再求解问题,