运筹学试题库一、多项选择题1、下面命题正确的是()。
A、线性规划的标准型右端项非零;B、线性规划的标准型目标求最大;C、线性规划的标准型有等式或不等式约束;D、线性规划的标准型变量均非负。
2、下面命题不正确的是()。
A、线性规划的最优解是基本解;B、基本可行解一定是基本解;C、线性规划有可行解则有最优解;D、线性规划的最优值至多有一个。
3、设线性规划问题(P),它的对偶问题(D),那么()。
A、若(P)求最大则(D)求最小;B、(P)、(D)均有可行解则都有最优解;C、若(P)的约束均为等式,则(D)的所有变量均无非负限制;D、(P)和(D)互为对偶。
4、课程中讨论的运输问题有基本特点()。
A、产销平衡;B、一定是物品运输的问题;C、是整数规划问题;D、总是求目标极小。
5、线性规划的标准型有特点()。
A、右端项非零;B、目标求最大;C、有等式或不等式约束;D、变量均非负。
6、下面命题不正确的是()。
A、线性规划的最优解是基本可行解;B、基本可行解一定是基本解;C、线性规划一定有可行解;D、线性规划的最优值至多有一个。
7、线性规划模型有特点()。
A、所有函数都是线性函数;B、目标求最大;C、有等式或不等式约束;D、变量非负。
8、下面命题正确的是()。
A、线性规划的最优解是基本可行解;B、基本可行解一定是最优;C、线性规划一定有可行解;D、线性规划的最优值至多有一个。
9、一个线性规划问题(P)与它的对偶问题(D)有关系()。
A、(P)有可行解则(D)有最优解;B、(P)、(D)均有可行解则都有最优解;C、(P)可行(D)无解,则(P)无有限最优解;D、(P)(D)互为对偶。
10、运输问题的基本可行解有特点()。
A、有m+n-1个基变量;B、有m+n个位势;C、产销平衡;D、不含闭回路。
二、简答题(1)微分学求极值的方法为什么不适用于线性规划的求解?(2)线性规划的标准形有哪些限制?如何把一般的线性规划化为标准形式? (3)图解法主要步骤是什么?从中可以看出线性规划最优解有那些特点?(4)什么是线性规划的可行解,基本解,基可行解?引入基本解和基可行解有什么作用?(5)对于任意基可行解,为什么必须把目标函数用非基变量表示出来?什么是检验数?它有什么作用?如何计算检验数?(6)确定换出变量的法则是什么?违背这一法则,会发生什么问题? (7)如何进行换基迭代运算?(8)大M 法与两阶段法的要点是什么?两者有什么共同点?有什么区别? (9)松弛变量与人工变量有什么区别?试从定义和处理方式两方面分析。
(10)如何判定线性规划有唯一最优解,无穷多最优解和无最优解?为什么?(11)如何在以B 为基的单纯形表中,找出B -1?该表是怎样由初始表得到的? (12)对偶问题的构成要素之间,有哪些对应规律? (13)如何从原问题最优表中,直接找到对偶最优解? (14)叙述互补松弛定理及其经济意义。
(15)什么是资源的影子价格?它在经济管理中有什么作用? (16)对偶单纯形法有哪些操作要点?它与单纯形法有哪些相同,哪些地方有区别? (17)灵敏度分析主要讨论什么问题?分析的基本思路是什么?四种基本情况的分析要点是什么?三、模型建立题(1)某厂生产A ,B ,C 三种产品,每件产品消耗的原料和设备台时如表3-1所示:另外,要求三种产品总产量不低于65件,A 的产量不高于B 的产量。
试制定使总利润最大的模型。
(2)某钻井队要从以下10个可供选择的井位中确定5个钻井探油,使总的钻井费用最小。
若10个井位的代号为12310,,s s s s ,相应的钻井费用为1210,,,c c c ,并且井位选择上要满足下列限制条件:①或选择1s 和7s ,或选择钻探8s ;②选择了3s 或4s 就不能选5s ,或反过来也一样;③在5678,,,s s s s 中最多只能选两个;试建立这个问题的整数规划模型。
(3)某市为方便学生上学,拟在新建的居民小区增设若干所小学。
已知备选校址代号及其能覆盖的居民小区编号如表3–2所示,问为覆盖所有小区至少应建多少所小学,要求建模并求解。
(4)一货船,有效载重量为24吨,可运输货物重量及运费收入如表3-3所示,现货物2、4中优先运2,货物1、5不能混装,试建立运费收入最多的运输方案。
表3-3城市出发,到其他几个城市推销商品,规定每个城市均需到达且只到达一次,然后回到原出发城市。
已知城市i 和城市j 之间的距离为d ij 问商贩应选择一条什么样的路线顺序旅行,使总的旅程最短。
试对此问题建立整数规划模型。
四、计算及分析应用题(1)某公司打算利用具有下列成分(见表4-1)的合金配制一种新型合金100公斤,新合金含铅,锌,锡的比例为3:2:5。
(2)某医院每天各时间段至少需要配备护理人员数量见表4-2 表4-2假定每人上班后连续工作8小时,试建立使总人数最少的计划安排模型。
能否利用初等数学的视察法,求出它的最优解?(3)某工地需要30套三角架,其结构尺寸如图4-1所示。
仓库现有长6.5米的钢材。
如何下料,使消耗的钢材最少?图4-1(4)用图解法求下列线性规划的最优解:⎪⎪⎩⎪⎪⎨⎧≥≤+-≥+≥++=0,425.134 12 64 min )1(2121212121x x x x x x x x x x z⎪⎪⎩⎪⎪⎨⎧≥≤+≥+-≤++=0,82 5 1032 44 max )2(2121212121x x x x x x x x x x z⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤≤-≤+-≤++=0,6054 4 22232 96 max )3(21221212121x x x x x xx x x x x z⎪⎩⎪⎨⎧≥≤+-≥++=0,11234 3 max )4(21212121x x x x x x x x z(5) 把下列线性规划化为标准形式:⎪⎪⎩⎪⎪⎨⎧≥≤=-++-≥-+≤-+-+-=无约束432143213214313210,,01 32 212 min )1(x x x x x x x x x x x x x x x x x z⎪⎪⎩⎪⎪⎨⎧≤≤≥+-≤++=无约束211212121,02182 32 max )2(x x x x x x x x x z(6) 求出下列线性规划的所有基本解,并指出其中的基可行解和最优解。
⎪⎪⎩⎪⎪⎨⎧=≥=++=+=++=5,,1 ,0182 312 2 4853 max 521423121 j x x x x x x x x x x z j(7) 求下列线性规划的解: (1)(2)⎪⎪⎩⎪⎪⎨⎧≥≤+≤≤+=0,182 36 82 53 max 21212121x x x x x x x x z⎪⎩⎪⎨⎧≥≤+-≤++=0,1 42 42 max 21212121x x x x x x x x z(3)(4)⎪⎩⎪⎨⎧≥≤+--≥+-+=0,122 2 max 21212121x x x x x x x x z⎪⎪⎩⎪⎪⎨⎧≥≤≥≤--≤++≤+-++=0,0,020102603 2 max 321321321321321x x x x x x x x x x x x x x x z(8) 利用大M 法或两阶段法求解下列线性规划: (1) (2)⎪⎪⎩⎪⎪⎨⎧≥≥+≥-≤++=0,2172 23 max 2121212121x x x x x x x x x x z⎪⎪⎩⎪⎪⎨⎧≥=-+≤+≥++--=0,,54 21823 2 max 32132121321321x x x x x x x x x x x x x x z (3)(4)⎪⎪⎩⎪⎪⎨⎧≥≥≤-≥++-=0,2 6 31234 max 212212121x x x x x x x x x z⎪⎩⎪⎨⎧≥≥+++≥++++++=0,,,1223615263 343 min 4321432143214321x x x x x x x x x x x x x x x x z (9) 对于问题⎩⎨⎧≥==0b max X AX CX z (1)设最优解为X *,当C 改为C 时,最优解为X ,则0))((*≥--X X C C 。
(2)如果X 1,X 2均为最优解,则对于α∈[0,1],αX 1+(1-α)X 2均为最优解。
(10). 表4-2是一个求极大值线性规划的单纯形表,其中x 4,x 5,x 6是松弛变量。
(2)要使上表成为最优表,a应满足什么条件?(3)何时有无穷多最优解?(4)何时无最优解?(5)何时应以x3替换x1?(11)已知某线性规划的初始单纯形表和最终单纯形表如表4-3,请把表中空白处的数字填上,并指出最优基B及B-1。
(12).某个线性规划的最终表是表4-4表4-4初始基变量是1,4,5。
(1)求最优基B=(P1,P2,P3);(2)求初始表。
(13).写出下列线性规划的对偶问题:⎪⎪⎩⎪⎪⎨⎧≤≥=+-≥-+-≤+++-=无约束321321321321321,0,01314242 3 max )1(x x x x x x x x x x x x x x x z ⎪⎪⎩⎪⎪⎨⎧≤≥≥++=++-≤--+++-=无约束432143132143214321,,0,01222 242 32 min (2)x x x x x x x x x x x x x x x x x x z ⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎨⎧+=≤+==≥+=≥+===≤=∑∑∑∑====nn j x n n j x n j x mm i b x a m m i b x a m i b x a x c z jj j i nj j ij i nj j ij i nj j ij nj jj ,,1,0,,1,,,1,0,,1,,,1,,,2,1, max (3)221121211111无约束 ⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥=====∑∑∑∑====nj m i x nj b x m i a x x c z ij j m i ij i nj ij m i nj ijij ,,1 ,,10,,1 ,,1min (4)1111(14) 已知线性规划⎪⎩⎪⎨⎧≥≥++≥++++=0,, min 32123232221211313212111332211x x x b x a x a x a b x a x a x a x c x c x c z (1)写出它的对偶问题;(2)引入松弛变量,化为标准形式,再写出对偶问题; (3)引入人工变量,把问题化为等价模型:⎪⎩⎪⎨⎧≥=+-++=+-+++-++=0,,)( max 7127532322212116431321211176332211x x b x x x a x a x a b x x x a x a x a x x M x c x c x c z 再写出它的对偶问题。