(完整版)运筹学习题集

..例：将下面的线性规划化为标准型min12343425zxxxx1234123412344223142322xxxxxxxxxxxx123400,,0,xxxx无非负限制解max7193834255zzxxxxx7193875193871938642231423222xxxxxxxxxxxxxxxxx9571368,,,,,,0.xxxxxxx1.9某昼夜服务的公交线路每天个时间段内所需司机和乘务员人数如下：班次时间所需人数16点到10点60210点到14点70314点到18点60418点到22点50522点到2点2062点到6点30设司机和乘务人员分别在各时间区段一开始时上班，并连续上班8小时，问该公交线路至少配备多少司机和乘务人员。列出线型规划模型。解：设kx（k=1，2，3，4，5，6）为kx个司机和乘务人员第k班次开始上班。建立模型：Minz=1x+2x+3x+4x+5x+6xs.t.1x+6x601x+2x702x+3x603x+4x50..4x+5x205x+6x301x,2x,3x,4x,5x,6x01.10某糖果公司厂用原料A、B、C加工成三种不同牌号的糖果甲乙丙，已知各种糖果中ABC含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费用及售价如表所示：原料甲乙丙原料成本（元/千克）每月限制用量（千克）A60%15%22000B1.52500C20%60%50%11200加工费0.50.40.3售价3.42.852.25问该厂每月应当生产这三种牌号糖果各多少千克，使得获利最大？建立数学模型。解:解：设1x，2x，3x是甲糖果中的A，B，C成分，4x，5x，6x是乙糖果的A，B，C成分，7x，8x，9x是丙糖果的A，B，C成分。线性规划模型：Maxz=0.91x+1.42x+1.93x+0.454x+0.955x+1.456x-0.05+0.45+0.95s.t.-0.41x+0.62x+0.63x0-0.21x-0.22x+0.83x0-0.854x+0.155x+0.156x0-0.64x-0.65x+0.46x0-0.7-0.5+0.501x+4x+20002x+5x+25003x+6x+12001x,2x,3x,4x,5x,6x,,,07x8x9x7x8x9x7x8x9x7x8x9x..1.11某厂生产三种产品I、、III。每种产品经过AB两道加工程序，该厂有两种设备能完成A工序，他们以1A,2A表示；有三种设备完成B工序，分别为1B，2B，3B；产品I可以在AB任何一种设备上加工，产品可以在任何规格的A设备上加工，但完成B工序时，只能在1B设备上加工；产品III只能在2A，2B上加工。已知条件如下表，要求安排最优生产计划，使该厂利润最大化。设备产品设备有效台时满负荷时的设备费用IIIIII1A51060003002A7912100003211B6840002502B41170007833B74000200原料费0.250.350.5单价1.252.002.8解：产品1，设1A,2A完成A工序的产品1x，2x件；B工序时，1B,2B，3B完成B工序的3x，4x，5x件，产品，设1A,2A完成A工序的产品6x，7x件；B工序时，完成B的产品为件；产品111，完成A工序的件，完成B工序的件；1x+2x=3x+4x+5x6x+=建立数学模型：Maxz=(1.25-0.25)*(1x+2x)+(2-0.35)*(6x+)+(2.8-0.5)-(51x+106x)300/6000-(72x+9+12)321/10000-(63x+8)250/4000-(44x+111B8x2A9x2B9x7x8x7x9x7x9x8x..)783/7000-75x*200/4000s.t51x+106x600072x+9+121000063x+8400044x+11700075x40001x+2x=3x+4x+5x6x+=1x,2x,3x,4x,5x,6x,,,0用单纯形法求解线性规划极大化MAX123235zxxx123123725310xxxxxx0,1,2,3ixi解引入松弛变量54,xx，得到原规划的标准型极大化5123423500zxxxxx12345123725310xxxxxxxx0,1,2,3,4,5ixi单纯形表为9x7x9x8x9x7x8x7x8x9x..12345452523500111107253011023500011110770851451083021xxxxxxcxxxx所以，最优解为,(0,7,0)t最优解值为21.解：最优解(4,2),14Xz例：设线性规划max1231064zxxx123123123100,1045600,226300,0,1,2,3.ixxxxxxxxxxi求：1.最优解;2.确定123,,ccc的范围,使最优解不变;取3506c,求最优解;3.确定123,,bbb的范围,使最优基不变,取1100,b求最优解;4.引入777,1,4,3,8TxPc求最优解;解1.由单纯形方法得..1234564564162161064000111100100104501060022600130010640003110104052102111006052106105011805502101060055120001063631211001006363004201100810222000003333xxxxxxxcxxxxxxxxx即,原问题的最优解为1002002200,,0,.333TXz例求下面运输问题的最小值解：12341311310721923437410593656解：由最小元素法得到初始解：..v1=2v2=9v3=3v4=101934u1=01311310743u2=-121923431u3=-53741059633656则：1112222431331,2,1,6,10,12，最小值为-6，非基变量为24x，闭回路242423131424:xxxxxx，最大调整量为1，得新解：1314212432345,2,3,1,6,3xxxxxx，重新计算位势及影响系数，得下表：v1=8v2=9v3=3v4=101234u1=01311310752u2=-721923431u3=-537410596336561112222331335,2,7,6,4,12，最小值为-5，非基变量为11x，闭回路111114242111:xxxxxx，最大调整为2，得新解：1113212432342,5,1,3,6,3xxxxxx重新计算位势及影响系数，得下表：..v1=3v2=4v3=3v4=51234u1=01311310725u2=-221923413u3=037410596336561214222331337,5,7,1,4,7，此时，0ij，故当前解为最优解。最优解值为：32351133465370Y。3.2表3-3和表3-4中分别给出两个运输问题的产销平衡表和单位运价表，试用伏格尔法直接给出近似最优解。表3-3销地产地123产量15181222411433674销量91011表3-4销地产地12345产量11023159252520152430315514715204201513M830销量2020301025解：（1）在表3-3中分别计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。得到：销地123行差额..产地151842241133673列差额136从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，上表中，第三列是最大差额列，此列中最小元素为1，由此可以确定产地2的产品应先供应给销售地3，得到下表：销地产地123产量1111221434销量91011同时将运价表第三列数字划去，得销地产地12产量15112224143364销量910对上表中的元素，计算各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列，重复上面的步骤，直到求出初始解，最终结果是：销地产地123产量121012231114344销量91011（2）3-4分别计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素。（方法同3-3相同）最终得出原问题的初始解：销地产地12345产量..12522030320430销量20203010253.3用表上作业法求给出运输问题的最优解（M是任意大正数）（1）销地产地甲乙丙丁产量137645224322343853销量3322解：（1）○1计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。○2从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，丙列中的最小元素为3，由此可以确定产地2的产品应先供应丙的需要，而产地2的产量等于丙地的销量，故在（2，丙）处填入0，同时将运价表中的丙列和第二行的数字划去，得到：销地产地甲乙丙丁产量137452234353销量332○3对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤○1○2，直到求出初始解为止。得到下表：销地产地甲乙丙丁产量132522023033..销量3322使用位势法进行检验：○1上表中，数字格处填入单位运价并增加一行一列，在列中填入iu（i=1，2，3），在行中填入jv（j=1，2，3，4），先令+=ijc（i，jB，B为基，下同）来确定和，得到下表：销地产地甲乙丙丁1340232-234313254○2由ij=-（+）（i，j为非基，下同）计算所有空格的检验数，并在每个格的右上角填入单位运价，得到下表销地产地甲乙丙丁1307561400221443020-234030825013254由上表可以看出，所有的非基变量检验数≥0，此问题达到最优解。又因为34=0，此问题有无穷多最优解。总运费minz=3*3+3*3+2*3+2*4=32（2）销地产地甲乙丙丁产量110671242161059935410104销量5246iuiviuiviuivijciuiviuiv..解：（2）○1计算出各行和各列的次最小运费和最小运费的差额，填入该表的最右列和最下列。○2从行差额或者列差额中找出最大的，选择它所在的行或者列中的最小元素，甲列是最大差额列，甲列的最小元素是5，所以产地3的产品先供应甲的需求，同时将运价表中产地3所在行的数字划去。○3对上表中的元素分别计算各行和各列的次最小运费和最小运费的差额，填入该标的最右列和最下行，重复步骤○1○2，直到求出初始解为止。得到下表：销地产地甲乙丙丁产量112142369344销量5246使用位势法进行检验：○1上表中，数字格处填入单位运价，并增加一行一列，在列中填入iu（i=1，2，3），在行中填入jv（j=1，2，3，4），先令1u=0，由+=ijc（i，jB，B为基，下同）来确定和.○2由ij=-（+）（i，jN）计算所有空格的检验数，并在每个格的右上角填入单位运价，得到下表销地产地甲乙丙丁110067121021681065090-235043108104-5106711由上表可以看出，所有的非基变量检验数≥0，此问题达到最优解。此问题有唯一最优解。总运费minz=118（3）iuiviuivijciuiviuiv..销地产地甲乙丙丁戊产