单纯形法的矩阵描述及应用举例课案.ppt
,返回,继续,第五、七节 单纯形法的进一步讨论和应用举例,-单纯形法的矩阵描述 及应用举例,矩阵单纯形法计算的描述 P41,线性规划问题,解：化为标准型，引入松弛变量,初始单纯形表：,最终单纯形表：,单纯形法的矩阵描述,不妨设基矩阵为,基变量,非基变量,则,当前基解,当前目标函数值,目标函数,令 得当前的目标函数值为：,单纯形法的矩阵描述,当前检验数,单纯形法的矩阵描述,检验数,其中,当前 对应的系数列,当基变量为 时，新的单纯形表,矩阵单纯形法计算的描述,当前检验数,当前基解,例10 用向量矩阵描述下面LP问题的计算,系数矩阵,例10 用向量矩阵描述下面LP问题的计算,初始单纯形表,2 0 3 0 0 0 0 12 2 0 2 1 0 0 0 16 4 1 0 0 1 0 0 15 0 0 5 0 0 1 2 0 3 0 0 0,B,I,例10单纯形表,2 0 3 0 0 0 2 3 1 0 0 1/2 0-1/5 0 4 0 1 0-2 1 4/5 3 3 0 0 1 0 0 1/5 0 0 0-1 0-1/5,最优解为(3,3,0,4,0)，最大值为Z=15,I,B-1,应用举例,一个经济、管理问题要满足下列条件，才能归结为线性规划模型：(一)要求解的问题的目标能用某种效益指标度量大小程度,并能用线性函数描述目标的要求(二)为达到这个目标存在多种方案(三)要达到的目标是在一定约束条件下实现的,这些条件可用线性等式或不等式描述,例1 混合配料问题,某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙.已知各种牌号糖果中A、B、C含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如下表所示.问该厂每月生产这三种牌号糖果各多少千克，使该厂获利最大.试建立这个问题的线性规划的数学模型.,解：用i=1,2,3分别代表原材料A、B、C，用j=1,2,3分别代表甲、乙、丙三种糖果.设xij为第j种糖果中第i种原料的重量,则问题的数学模型为：,原料供应限制,含量要求条件,例2 投资项目的组合问题,兴安公司有一笔30万元的资金，考虑今后三年内用于下列项目的投资：(1)三年内的每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年的投资；(2)只允许第一年初投入，于第二年末收回，本利合计为投资额的150%，但此类投资限额不超过15万元；(3)允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元；(4)允许于第三年初投入，年末收回，可获利40%，但限额为10万元.试为该公司确定一个使第三年末本利和为最大的投资组合方案.,解：用 xij 表示第 i 年初投入到第 j 个项目的资金数,则可建立问题的数学模型为：,例3 生产、库存与设备维修综合计划的安排,红光厂有2台车床、1台钻床、1台磨床,承担4种产品的生产任务.已知生产各种产品所需的设备工时及生产单位产品的售价如表1-20所示。对各产品今后三个月的市场最大需求(小于最大需求量时可全部销出)及个产品在今后三个月的生产成本分别如表1-21和表1-22所示。,表1-20 单位产品所需工时aij值 单位：h,表1-22 单位产品成本Vkj 单位：元/件,表1-21 最大需求量Rkj 单位：件,上述设备在1-3月内各需进行一次维修,具体安排为:2台车床于2月份、3月份各维修一台,钻床安排在2月份维修,磨床安排在3月份维修.各设备每月工作22天,每天2班,每班8h,每次维修占用半个月时间.又生产出来的产品当月销售不出去(超过最大需求量)时,可在以后各月销售,但需付每件每月储存费5元.并规定每个月底各种产品储存量均不得超过100件.1月初各产品无库存,要求3月底各产品均库存50件.试安排该厂各月的生产计划,使总利润为最大。,解：用 xkj 表示第 j 种产品在第 k 个月的生产量，Skj 表示第 j 种产品在第k个月的销售量，Ikj 表示第 j 种产品在第k个月的库存量，Rkj 表示第 j 种产品在第k个月的最大需求量，Cki 表示第 i种设备在第 k 个月的生产能力，Pj 表示单位 j 种产品的售价，Vkj 为单位 j 种产品第k 个月的生产成本，aij 为单位 j 种产品所需 i 设备工时，则可建立问题的数学模型为：,例4(P53 例16),表1-23,该分拣部每天从早8:00-19:00对外营业,快件的分拣由工人操作机器进行,每台机器由一名工人操作,分拣率为500件/h,共有11台机器,分拣部内一部分为全日制工人,上班时间分别为10:00-18:00和12:00-20:00,每人每天工资150元;另一部分为非全日制工人,分三批上班：11:00-16:00,13:00-18:00,15:00-20:00,每人每天工资80元.考虑到快件的时间性强,快递公司承诺,每天12:00前到达的快件于14:00前分拣完寄出;12:00-15:00之前到达的快件于17:00前分拣完寄出;这之后到达的,均在当天20:00前分拣完并发送出去.问该分拣部各雇佣多少全日制非全日制工人,并如何安排班次,使总的工资支出为最少.,迅达快递公司下设一个快件分拣部,处理每天收寄的快件.据统计资料,每天各时段快件到达数量如表.,解：设 x1 和 x2 分别表示于10:00-18:00及12:00-20:00上班的全日制工人数,y1,y2,y3 为分别于11:00-16:00,13:00-18:00及15:00-20:00上班的非全日制工人数.则可建立问题的数学模型为：,单纯形法的矩阵描述 及应用举例,返回,结束,
