运筹学习题集.doc

例:将下面的线性规划化为标准型无非负限制解 :班次时间所需人数16点到10点60210点到14点70314点到18点60418点到22点50522点到2点2062点到6点30设司机和乘务人员分别在各时间区段一开始时上班,并连续上班8小时,问该公交线路至少配备多少司机和乘务人员。列出线型规划模型。解:设(k=1,2,3,4,5,6)为个司机和乘务人员第k班次开始上班。建立模型:Minz=+++++.+60+70+60+50+20+30,,,,,、B、C加工成三种不同牌号的糖果甲乙丙,已知各种糖果中ABC含量,原料成本,各种原料的每月限制用量,三种牌号糖果的单位加工费用及售价如表所示:原料甲乙丙原料成本(元/千克)每月限制用量(千克)A60%15%%60%50%,使得获利最大?建立数学模型。解:解:设,,是甲糖果中的A,B,C成分,,,是乙糖果的A,B,C成分,,,是丙糖果的A,B,C成分。线性规划模型:Maxz=+++++-++.-++--+-++--+--+++2000++2500++1200,,,,,,,,、、III。每种产品经过AB两道加工程序,该厂有两种设备能完成A工序,他们以,表示;有三种设备完成B工序,分别为,,;产品I可以在AB任何一种设备上加工,产品可以在任何规格的A设备上加工,但完成B工序时,只能在设备上加工;产品III只能在,上加工。已知条件如下表,要求安排最优生产计划,使该厂利润最大化。:产品1,设,完成A工序的产品,件;B工序时,,,完成B工序的,,件,产品,设,完成A工序的产品,件;B工序时,完成B的产品为件;产品111,完成A工序的件,完成B工序的件;+=+++=建立数学模型:Maxz=(-)*(+)+(2-)*(+)+(-)-(5+10)300/6000-(7+9+12)321/10000-(6+8)250/4000-(4+11)783/7000-7*200/+1060007+9+12100006+840004+**********+=+++=,,,,,,,,0用单纯形法求解线性规划极大化MAX解引入松弛变量,得到原规划的标准型极大化单纯形表为所以,:最优解例:设线性规划求:;,使最优解不变;取,求最优解;,使最优基不变,取求最优解;;,原问题的最优解为例求下面运输问题的最小值解:12341311310721923437410593656解:由最小元素法得到初始解:v1=2v2=9v3=3v4=101934u1=01311310743u2=-121923431u3=-53741059633656则:,最小值为-6,非基变量为,闭回路,最大调整量为1,得新解:,重新计算位势及影响系数,得下表:v1=8v2=9v3=3v4=101234u1=01311310752u2=-721923431u3=-53741059633656,最小值为-5,非基变量为,闭回路,最大调整为2,得新解:重新计算位势及影响系数,得下表:v1=3v2=4v3=3v4=51234u1=01311310725u2=-221923413u3=03741059633656,此时,,故当前解为最优解。最优解值为:。-3和表3-4中分别给出两个运输问题的产销平衡表和单位运价表,试用伏格尔法直接给出近似最优解。表3-3销地产地123产量15181222411433674销量91011表3-4销地产地12345产量110231592525201524303155147**********M830销量2020301025解:(1)在表3-3中分别计算出各行和各列的次最小运费和最小运费的差额,填入该表的最右列和最下列。得到:销地123行差额产地151842241133673列差额136从行差额或者列差额中找出最大的,选择它所在的行或者列中的最小元素,上