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

第一章线性规划及单纯形法,1,7 线性规划应用举例,一般情况下，一个经济管理问题满足以下条件时才能建立线性规划（LP）模型.(1)目标函数能用线性函数的形式，用数值指标反映；(2)该问题有多中可行方案；(3)要求达到的目标是在一定的约束条件下实现的，这些约束条件能用线性等式或不等式表示。,第一章线性规划及单纯形法,2,7 线性规划应用举例,例1.13 生产计划问题（P.27）例1.14 合理下料问题（P.29）例1.15 多阶段投资问题（P.30）例1.16 场地租借问题（P.32）例1.17 分配问题（P.33）例1.18 选址问题（P.34）,第一章线性规划及单纯形法,3,合理下料问题,要制作100套钢筋架子，每套有长2.9m、2.1m和1.5m的钢筋各一根。已知原料长7.4m，应如何切割，使所用原料最节省。,考察如下方案的综合使用：,设xj（j=1，2，8）分别表示第j种方案下料的原材料根数。该问题的LP模型如下：,第一章线性规划及单纯形法,4,（）,（）,思考：如何求解（）、（）？,第一章线性规划及单纯形法,5,模型（）利用大 M 法求解，得到：,此时剩余料头16 m,第一章线性规划及单纯形法,6,兴安公司有一笔 30 万元的资金，考虑今后三年内用于下列项目的投资：1.三年内的每年年初均可投入，每年获利为投资额的 20%，其本利可一起用于下一年的投资；2.只允许第一年初投入，于第二年年末收回，本利合计为投资额的150%，但此类投资限额15万以内；3.允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元以内；4.允许于第三年初投入，年末收回，可获利40%，但限额为10万元以内；试为该公司确定一个使第三年末本利总和为最大的投资组合方案。,多阶段投资问题,第一章线性规划及单纯形法,7,解：用 xij 表示第 i 年初投放到 j 项目的资金数，则可投资的变量表如下,第一章线性规划及单纯形法,8,由于第三年末收回的本利只包含第三年初项目一的投资、第二年初项目三的投资和第三年初项目四的投资，因此目标函数为：,第一年初投资总额为30万，因此有：,第二年初的投资额与第一年末收回的本利总额相同：,第三年初投资额与第二年末收回的本利总额相同：,第一章线性规划及单纯形法,9,再考虑各项目的投资限额，得到该问题的线性规划模型如下：,第一章线性规划及单纯形法,10,某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表，问该厂每月生产这三种牌号糖果各多少千克，使该厂获利最大，试建立该问题的线性规划模型。,练习：混合配料问题,第一章线性规划及单纯形法,11,解：用 i=1,2,3 分别代表原料A、B、C，用 j=1,2,3 分别代表甲、乙、丙三种糖果。设 xij 为生产第 j 种糖果使用的第 i 种原料的数量，则问题的数学模型可归结为：,目标函数:,第一章线性规划及单纯形法,12,约束条件:,第一章线性规划及单纯形法,13,作业：P.36,第一章习题：2,第一章线性规划及单纯形法,14,补充：应用LINDO求解LP问题,LINDO可以从下面的网址下载：www.LLINDO由美国芝加哥大学开发，可求解线性规划和线性整数规划等。其可按自然格式输入模型，使用方便。,例如:,第一章线性规划及单纯形法,15,第一章线性规划及单纯形法,16,例：应用LINDO求解下面LP问题：,第一章线性规划及单纯形法,17,