您好,欢迎访问三七文档
运筹学复习《运筹学F_02》第1章线性规划及单纯形法•一、判断题•(1)图解法与单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的。•正确。•(2)线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大。•正确。这里注意:增加约束,可行域不会变大;减少约束,可行域不会变小。•(3)线性规划问题的每一个基解对应可行域的一个顶点。•错误。线性规划的基本定理之一为:线性规划问题的基本可行解对应于可行域的顶点。•(4)如线性规划问题存在可行域,则可行域一定包含坐标的原点。•错误。•如果约束条件中有一个约束所对应的区域不包含坐标的原点,则即使有可行域,也不包含坐标的原点。•(5)取值无约束的变量𝑥𝑖,通常令𝑥𝑖=𝑥𝑖′−𝑥𝑖′′,其中𝑥𝑖′≥0,‘𝑥𝑖′′≥0,在用单纯形法求得的最优解中,有可能同时出现𝑥𝑖′0,’𝑥𝑖′′0。•错误。•(6)用单纯形法求解标准型式的线性规划问题时,与𝜎𝑗0对应的变量都可以被选作入基变量。•正确。•(7)单纯形法计算中,如不按最小比值原则选取换出变量,则在下一个解中至少有一个基变量的值为负。•正确。•(8)一旦一个人工变量在迭代中变为非基变量后,则该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果。•正确。•人工变量一般是为取得对应的初始基基向量而引入的,它一旦成为出基变量,其地位已被对应的入基变量取代,删除单纯形表中该变量及相应列的数字,不影响计算结果。•(9)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示。•错误。•如果𝜆𝑖=1𝑚𝑖=1,则命题正确,否则,不正确。•(10)对一个有n个变量,m个约束的标准型的线性规划问题,其可行域顶点恰好是𝑐𝑛𝑚个。•错误。•(11)线性规划问题的可行解如为最优解,则该可行解一定是基本可行解。•错误。•唯一最优解时,最优解是可行域顶点,对应基本可行解;无穷多最优解时,除了其中的可行域顶点对应基本可行解外,其余最优解不是可行域的顶点。•(12)若线性规划问题具有可行解,且其可行域有界,则该线性规划问题最多具有有限个数的最优解。•错误。•如果在不止一个可行解上达到最优,它们的凸组合仍然是最优解,这样就有了无穷多的最优解。•(13)若线性规划问题的可行域可以伸展到无限,则该问题一定具有无界解。•错误。•二、用单纯形法求解标准型式的线性规划问题时,如何判别该问题具有唯一最优解、无穷多最优解、无界解或者无可行解?•当所有𝜎𝑗≤0,且非基变量的检验数0,有唯一最优解;•当所有𝜎𝑗≤0,至少有一个非基变量检验数为0,有无穷多最优解;•对于某个𝜎𝑗0,有𝑃𝑗≤0,有无界解•对于所有𝜎𝑗≤0,而基变量中含非0人工变量,有无可行解。•三、下表中给出某一求极大化问题的单纯形表,问表中𝑎1,𝑎2,𝑐1,𝑐2,𝑑为何值时以及表中变量属哪一种类型时有:•(a)表中解为唯一最优解;(b)表中解为无穷多最优解之一;•(c)表中解为退化的可行解;(d)下一步迭代将以𝑥1替换𝑥5;•(e)该线性规划问题具有无界解;(f)该线性规划问题无可行解。𝑥1𝑥2𝑥3𝑥4𝑥5𝑥3d4𝑎1100𝑥42-1-5010𝑥53𝑎2-3001𝑐𝑗−𝑧𝑗𝑐1𝑐2000•答案:•(a)d≥0,𝑐10,𝑐20;•(b)d≥0,𝑐1≤0,𝑐2≤0,但𝑐1,𝑐2中至少一个为零;•(c)d=0;或者d0,𝑐10,且𝑑4=3𝑎2;•(d)𝑐10,𝑐1𝑐2,𝑑43𝑎2;•(e)𝑐20,𝑎1≤0;•(f)𝑥5为人工变量,且𝑐1≤0,𝑐2≤0。•四、已知某线性规划问题单纯形法迭代时得到中间某两步的单纯形表如下表所示,试将表中空白处的数字填上。𝑥1𝑥2𝑥3𝑥4𝑥5𝑥65𝑥283231013000𝑥5143−4305−23100𝑥62935304−2301𝑐𝑗−𝑧𝑗−1304−2301⋮⋮⋮⋮⋮⋮⋮⋮⋮𝑥25141841−1041𝑥3−641541441𝑥1−241−12411541𝑐𝑗−𝑧𝑗检验数:(0,0,0,-45/41,-24/41,-11/41)第2章线性规划的对偶理论•一、判断题•(1)任何线性规划问题存在并具有唯一的对偶问题。•正确。•(2)对偶问题的对偶一定是原问题。•正确。•(3)根据对偶问题的性质,当原问题为无界解时,其对偶问题无可行解;反之,当对偶问题无可行解时,其原问题具有无界解。•错误。•(4)设𝑥和𝑦分别是标准形式(P,max)和(D,min)的可行解,𝑥∗和𝑦∗分别为其最优解,则恒有𝑐𝑥≤𝑐𝑥∗=𝑦∗b≤𝑦b。•正确。•(5)若原问题有可行解,则其对偶问题有可行解。•错误。•(6)若原问题无可行解,则其对偶问题也一定无可行解。•错误。•(7)若原问题有最优解,则其对偶问题也一定有最优解。•正确。•(8)若原问题和对偶问题均存在可行解,则两者均存在最优解。•正确。•(9)如果原问题的约束方程Ax≤b,变成Ax≥b,则其对偶问题的唯一改变就是非负的y≥0变成非正的y≤0。•正确。•(10)已知𝑦𝑖∗为线性规划的对偶问题的最优解的第i个分量,若𝑦𝑖∗0,说明在最优生产计划中第i种资源已经耗尽。•正确。•(11)已知𝑦𝑖∗为线性规划的对偶问题的最优解第i个分量,若𝑦𝑖∗=0说明在最优生产计划中第i种资源已经耗尽且一定有剩余。•错误。•(12)用对偶单纯形法求解线性规划的每一步,在单纯形表检验数行与基变量列对应的对偶问题与原问题的解代入各自的目标函数得到的值始终相等。•正确。•(13)如果某种资源的影子价格为k,在其它条件不变的前提下,当该种资源增加5个单位时,相应的目标函数值将增加5k。•错误。•(14)应用对偶单纯形法计算时,若单纯形表中某一基变量𝑥𝑖0,又𝑥𝑖所在行的元素全部大于或等于零,则可以判断其对偶问题具有无界解。•错误。•(15)若线性规划问题中的𝑏𝑖、𝑐𝑗值同时发生变化,反应到最终单纯形表中,不会出现原问题和对偶问题均为非可行解的情况。•错误。•(r)在线性规划问题的最优解中,如果某一变量𝑥𝑗为非基变量,则在原来问题中,无论改变它在目标函数中的系数𝑐𝑗或在各约束中的相应系数𝑎𝑖𝑗,反应到最终单纯形表中,除该列数字有变化外,将不会引起其它列数字的变化。•正确。•二、已知线性规划问题:•(a)写出其对偶问题;•(b)已知原问题用两阶段法求解时得到的最终单纯形表如下,试写出其对偶问题的最优解。536-60𝐶𝐵𝑋𝐵𝐵−1b𝑥1𝑥2𝑥3′𝑥3′′𝑥40𝑥48010015𝑥11412000-6𝑥3′′401-110𝑐𝑗−𝑧𝑗0-1000•答案•(a)对偶问题•(b)y1=0,y2=1,y3=3•𝑥4的检验数=0→y1=0•𝑥1=14→2y2+y3=5•𝑥3=-4→3y2+y3=6•三、•四、某厂生产Ⅰ、Ⅱ、Ⅲ三种产品,分别经过A、B、C三种设备加工,已知生产单位各种产品所需要的设备台时,设备的现有加工能力以及每件产品的预期的利润如下表:•(a)求获利最大的产品计划?•Maxz=10𝑥1+6𝑥2+4𝑥3•𝑥1+𝑥2+𝑥3≤10010𝑥1+4𝑥2+5𝑥3≤6002𝑥1+2𝑥2+6𝑥3≤100𝑥𝑗≥0,𝑗=1,2,3ⅠⅡⅢ设备能力/台•hA111100B1045600C226300单位产品利润/元1064•最优单纯形表•因此,获利最大的产品生产计划为1003,2003,0,0,0,100′•𝑧∗=220031064000𝐶𝐵𝑋𝐵𝐵−1b𝑥1𝑥2𝑥3𝑥4𝑥5𝑥66𝑥22003015653−16010𝑥110031016−231600𝑥6100004−201𝑐𝑗−𝑧𝑗00−83−103−230•(b)产品Ⅲ每件的利润增加到多大时才值得安排生产?如果产品Ⅲ的每件利润增加到50/6元,求最优计划的变化?•2003(见下页PPT)•(c)产品Ⅰ的利润在多大范围变化时,原最优计划保持不变?•[6,15]•(d)设备A的能力如为100+10𝜃,确定保持最优基不变的的变化范围?•[-4,5]•(e)如有一种新产品,加工一件设备A、B、C的台时为1、4、3小时,预期每件的利润为8元,是否值得安排生产?•检验数为正,值得生产•(f)如合同规定该厂至少生产10件产品Ⅲ,试确定最优的变化?•去掉生产10件产品Ⅲ的资源,重新计算,结论为[95/3,175/3,10]106506000𝐶𝐵𝑋𝐵𝐵−1b𝑥1𝑥2𝑥3𝑥4𝑥5𝑥66𝑥22003015653−16010𝑥110031016−231600𝑥6100004−201𝑐𝑗−𝑧𝑗0053−103−2306𝑥2𝟐𝟕𝟓𝟔0102512−16−52410𝑥1𝟏𝟕𝟓𝟔100−7216−124506𝑥325001−12014𝑐𝑗−𝑧𝑗000−23−512第3章运输问题•一、判断题•(1)在运输问题中,只要任意地给出一组含m+n-1个非零的𝑥𝑖𝑗,且满足𝑥𝑖𝑗=𝑎𝑖𝑛𝑗=1,𝑥𝑖𝑗=𝑏𝑗𝑚𝑖=1,就可以作为一个初始基本可行解。•错误。•(2)表上作业法实质上就是求解运输问题的单纯形法。•正确。•(3)按最小元素法(或Vogel法)给出的初始基可行解,从每一空格出发可以找出而且仅能找出唯一的闭回路。•正确。•(4)如果运输问题单位运价表的某一行(或某一列)元素分别加上一个常数k,最优调运方案将不会发生变化。•正确。•(5)如果运输问题单位运价表的某一行(或某一列)元素分别乘上一个常数k,最优调运方案将不会发生变化。•错误。•(6)如果运输问题单位运价表的全部元素乘上一个常数k(k0),最优调运方案将不会发生变化。•正确。•(7)用位势法求运输问题某一调运方案的检验数时,其结果可能同闭回路法求得的结果有异。•错误。•(8)运输问题初始方案的基本要求:(m+n-1)个数字格,不存在全部以数字格为顶点的闭回路。•正确。•二、不是最优,因为不是基可行解。3.5某造船厂根据合同要在当年算起的连续三年年末各提供三条规格相同的大型货轮。已知该厂今后三年的生产能力及生产成本如表。已知加班生产情况下每条货轮成本比正常生产时高出70万元,又知造出的货轮如当年不交货,每条货轮每积压一年将增加维护保养等损失为40万元。在签订合同时该厂已有两条积压未交互的货轮,该厂希望在第三年末在交完合同任务后能储存一条备用。问该厂应如何安排计划,使在满足上述要求的条件下,使总的费用支出为最小。年度正常生产时可完成的货轮数加班生产时可完成的货轮数正常生产时每条货轮成本第一年23500万元第二年42600万元第三年13550万元设jx为期初库存用于第j年交货的数量ijy为第i年正常生产用于第j年交货的数量ijz为第i年加班生产用于第j年交货的数量约束条件:1231112131112132223222333332234213xxxyyyzzzyyzzyz生产能力限制111112121222223131323233333334xyzxyzyzxyzyzyz需求限制0,0,0jijijxyz目标函数:31minjjijijijijjZcxcycz其中费用系数见下表:需求供应第一年第二年第三年初期库存04080第一年正常生产500540580第一年加班生产570610650第二年正常生产M600640第二年加班生产M670710第三年正常生产MM550第三年加班生产MM620产地:每年正常生产、加班生产及其库存销地:每一年的需求销地产地第一年第二年第三年假想地产量期初库存04080M2第一年正常生产5005405
本文标题:运筹学复习题
链接地址:https://www.777doc.com/doc-5599964 .html