数学建模规划问题的经典案例(32页).ppt

建立优化模型的一般步骤,1.确定决策变量,2.确定目标函数的表达式,3.寻找约束条件,例1：设某厂生产电脑和两种产品，这两种产品的生产需要逐次经过两条装配线进行装配电脑在第一条装配线每台需要2小时，在第二条装配线每台需要3小时；在第一条装配线每台需要4小时，在第二条装配线每台需要1小时第一条装配线每天有80个可用工时，第一条装配线每天有60个可用工时，电脑和每台的利润分别为100元和80元问怎样制定生产计划？,分析：,目标是利润L；而利润是由电脑的产量x和的产量y决定,§2.4 案例,假设：,1、两种产品的销量不受限制,2、原材料供应不受限制,约束条件：,装配线1的工时限制,装配线2的工时限制,变量约束,建立模型,,模型求解：,,,,,,,1,2,4,3,6,5,7,例2：最短路线问题的数学建模实例,14,15,12,10,13,20,9,12,8,8,,,,,,,,,,,,10,1,,,,2,4,3,,,,6,5,7,,,,,9,8,10,,,,,,,例3：最短路线问题算例,100,150,200,175,125,400,250,300,200,275,175,275,200,350,150,100,9-10100,8-10150,6-9-10300,5-8-10400,7-8-10275,2-6-10600,4-6-10500,3-5-10600,1-4-10650,最短路线为:1-4-6-9-10，长度：650,1,2,4,3,6,5,7,14,15,12,10,13,20,9,12,8,8,,,,,,,,,,,,10,例4：最小费用流问题,例5：最大流量问题,1,2,4,3,6,5,7,14,15,12,10,13,20,9,12,8,8,,,,,,,,,,,,10,工厂定期订购原料，存入仓库供生产之用；车间一次加工出一批零件，供装配线每天生产之用；商店成批购进各种商品，放在货柜里以备零售；水库在雨季蓄水，用于旱季的灌溉和发电。

存贮模型,存贮量多少合适？存贮量过大，存贮费用太高；存贮量太小，会导致一次性订购费用增加，或不能及时满足需求问题1 不允许缺货的存贮模型,配件厂为装配线生产若干种部件，轮换生产不同的部件时因更换设备要付生产准备费（与生产数量无关），同一部件的产量大于需求时因积压资金、占用仓库要付存贮费今已知某一部件的日需求量100件，生产准备费5000元，存贮费每日每件1元如果生产能力远大于需求，并且不允许出现缺货，试安排该产品的生产计划，即多少天生产一次（称为生产周期），每次产量多少，可使总费用最小问题分析,若每天生产一次，每次100件，无存贮费，生产准备费5000元，每天费用5000元；若10天生产一次，每次1000件，存贮费900+800+…+100=4500元，生产准备费5000元，总计9500元，平均每天费用950元；若50天生产一次，每次5000件，存贮费4900+4800+…+100=122500元，生产准备费5000元，总计127500元，平均每天费用2550元；,寻找生产周期、产量、需求量、生产准备费和存贮费之间的关系，使每天的费用最少模型假设,1 连续化，即设生产周期 T 和产量 Q 均为连续量；2 产品每日的需求量为常数 r ；3 每次生产准备费 C1，每日每件产品存贮费 C2；4 生产能力为无限大（相对于需求量），当存贮量 降到零时，Q件产品立即生产出来供给需求，即 不允许缺货。

模型建立,总费用与变量的关系,总费用=生产准备费+存贮费,存贮费=存贮单价*存贮量,存贮量=？,设 t 时刻的存贮量为 q(t) ，t = 0时生产 Q 件，存贮量 q(0) = Q , q(t) 以需求速率 r 线性递减，直至q(T) = 0，如图q(t) = Q- r t， Q = r T 存贮量的计算,卡盟排行榜 卡盟,Microsoft Office PowerPoint，是微软公司的演示文稿软件用户可以在投影仪或者计算机上进行演示，也可以将演示文稿打印出来，制作成胶片，以便应用到更广泛的领域中利用Microsoft Office PowerPoint不仅可以创建演示文稿，还可以在互联网上召开面对面会议、远程会议或在网上给观众展示演示文稿 Microsoft Office PowerPoint做出来的东西叫演示文稿，其格式后缀名为：ppt、pptx；或者也可以保存为：pdf、图片格式等,一个周期内存贮量,一个周期内存贮费,(A的面积),一个周期的总费用,每天平均费用,模型求解,用微分法,每天平均最小费用,思考,建模中未考虑生产费用（这应是最大一笔费 用），在什么情况下才可以不考虑它？建模时作了“生产能力无限大”的简化假设，如 果生产能力有限，是大于需求量的一个常数，如何建模？,结果解释,当准备费 c1 增加时，生产周期和产量都变大；当存贮费 c2 增加时，生产周期和产量都变小；当日需求费 r 增加时，生产周期变小而产量变大。

这些定性结果符合常识，而定量关系（平方根，系数2 等）凭常识是无法得出的，只能由数学建模得到这里得到的费用C与前面计算得950元有微小差别，你能解释吗？,在本例中,敏感性分析,讨论参数,有微小变化时对生产周期T 影响由相对变化量衡量对参数的敏感程度T 对c1 的敏感程度记为,意义是当准备费增加1%时，生产周期增加0.5% ；而存贮费增加1%时，生产周期减少0.5% ；日需求量增加1%时，生产周期减少0.5% 当,有微小变化对生产周期影响不太大模型假设,1 连续化，即设生产周期 T 和产量 Q 均为连续量；2 产品每日的需求量为常数 r ；3 每次生产准备费 C1，每日每件产品存贮费 C2；4 生产能力为无限大（相对于需求量），允许缺 货，每天每件产品缺货损失费C3 ，但缺货数量需 在下次生产（订货）时补足问题2 允许缺货的存贮模型,模型建立,总费用=生产准备费+存贮费+缺货损失费,存贮费=存贮单价*存贮量,缺货损失费=缺货单价*缺货量,存贮量=？，缺货量=？,因存贮量不足造成缺货，因此 q(t) 可取负值， q(t) 以需求速率 r 线性递减，直至q(T1) = 0，如图q(t) = Q-r t， Q = r T1 。

一个周期内缺货损失费,一个周期内存贮费,一个周期的总费用,每天平均费用,模型求解,用微分法 令,每天平均最小费用,每个周期的供货量,与不允许缺货模型相比较，有,结果解释,即允许缺货时，,周期和供货量增加，周期初的存贮量减少2）缺货损失费愈大， 愈小， 愈接近 ， 愈接近 1）,3）,不允许缺货模型可视为允许缺货模型的特例企业生产计划,奶制品的生产与销售,空间层次,工厂级：根据外部需求和内部设备、人力、原料等条件，以最大利润为目标制订产品生产计划；,车间级：根据生产计划、工艺流程、资源约束及费用参数等，以最小成本为目标制订生产批量计划时间层次,若短时间内外部需求和内部资源等不随时间变化，可制订单阶段生产计划，否则应制订多阶段生产计划一奶制品加工厂用牛奶生产A1、A2两种奶制品，一桶牛奶可以在甲类设备上用12小时加工成3公斤A1，或者在乙类设备上用8个小时加工成4公斤A2根据市场需求，生产的A1，A2全部都能售出，且每公斤A1获利24元，每公斤A2获利16元现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且甲类设备每天之多能加工100公斤A1，乙类设备没有加工能力限制。

试为该厂制订一个生产计划，使每天获利最大，并进一步讨论一以下3个附加问题：,例1 加工奶制品的生产计划,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,例1 加工奶制品的生产计划,50桶牛奶,时间480小时,至多加工100公斤A1,制订生产计划，使每天获利最大,35元可买到1桶牛奶，买吗？若买，每天最多买多少?,可聘用临时工人，付出的工资最多是每小时几元?,A1的获利增加到 30元/公斤，应否改变生产计划？,每天：,x1桶牛奶生产A1,x2桶牛奶生产A2,获利 24×3x1,获利 16×4 x2,原料供应,劳动时间,加工能力,决策变量,目标函数,每天获利,约束条件,非负约束,线性规划模型(LP),时间480小时,至多加工100公斤A1,模型分析与假设,比例性,可加性,连续性,xi对目标函数的“贡献”与xi取值成正比,xi对约束条件的“贡献”与xi取值成正比,xi对目标函数的“贡献”与xj取值无关,xi对约束条件的“贡献”与xj取值无关,xi取值连续,A1,A2每公斤的获利是与各自产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与各自产量无关的常数,A1,A2每公斤的获利是与相互产量无关的常数,每桶牛奶加工出A1,A2的数量和时间是与相互产量无关的常数,加工A1,A2的牛奶桶数是实数,,线性规划模型,模型求解,图解法,约束条件,,,,,目标函数,z=c (常数) ~等值线,在B(20,30)点得到最优解,目标函数和约束条件是线性函数,可行域为直线段围成的凸多边形,目标函数的等值线为直线,最优解一定在凸多边形的某个顶点取得。

OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2,模型求解,软件实现,LINDO 6.1,max 72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end,DO RANGE (SENSITIVITY) ANALYSIS?,No,20桶牛奶生产A1, 30桶生产A2，利润3360元。

OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2：,。