1-5-7单纯形法的矩阵描述及应用举例课案

返回接着第五、七节单纯形法的进一步探讨和应用举例----单纯形法的矩阵描述及应用举例矩阵单纯形法计算的描述P41线性规划问题解：化为标准型，引入松弛变量初始单纯形表：最终单纯形表：

单纯形法的矩阵描述不妨设基矩阵为基变量非基变量则当前基解当前目标函数值目标函数令得当前的目标函数值为：

单纯形法的矩阵描述当前检验数

单纯形法的矩阵描述检验数其中当前对应的系数列当基变量为时，新的单纯形表矩阵单纯形法计算的描述当前检验数当前基解例10用向量矩阵描述下面LP问题的计算系数矩阵例10用向量矩阵描述下面LP问题的计算初始单纯形表

203000

0122021000

16410010015005001

203000BI例10单纯形表

203000

231001/20-1/50

4010-214/5

33001001/5

000-10-1/5最优解为(3,3,0,4,0)，最大值为Z=15IB-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前分拣完并发送出去.问该分拣部各雇佣多少全日制非全日制工人,并如何支配班次,使总的工资支出为最少.迅达快递公司下设一个快件分拣部,处理每天收寄的快件.据统计资料,每天各时段快件到达数量如表..时段到达快件数500014:00-15:00300010:00-11:00400015:00-16:00400011:00-12:00250016:00-17:00450012:00-13:00450017:00-18:00350013:00-14:00250018:00-19:00300010:00前时段到达快件数