运筹学知识竞赛题目答案
交通一班运筹学知识竞赛题目 1 基矩阵、非基矩阵、基变量、非基变量、基变量系数、非基变量系数
2对同一种事物(问题)从不同的角度(立场)观察,有两种相对的表述
3资源变量在什么范围内时目标函数值不变
max,, ,/|,0,,,min{,/|,0}baabbaaiirirriirir
4若给出了最终的单纯形表 如何确定矩阵B-1及B
B-1是指松弛变量所对应的系数矩阵;B是指对应基变量的系数矩阵。
5从最终计算表中我们可以看出y*的值,其经济解释是什么,说明意义
影子价格 其随具体情况而异,在完全市场经济条件下,当某种资源的市场价低于影子价格时,企业应买进资源用于扩大生产;反之,应卖掉资源。
6 对偶问题的性质是什么
CX,Yb(1).对称性 对偶问题的对偶是原问题 (2).弱对偶性 若。 (3)无界性 若原问题(对偶问题)为无界解,则对偶问题(原问
X题)无可行解。 (4)可行解是最优解的性质 设是原问题的可行解,Y是对偶问题的可行解,当CX=Yb时,X,Y是最优解。(5) 对偶定理 若原问题有最优解,那么对偶问题也有最优解:且目标函数值相等。 (6)互补松弛性 若X,Y分别是原问题和对偶问题的
可行解。那么Y,X=0和YX=0,当且仅当X,Y为最优解。(7)设sSS
,0原问题是 max z=CX:AX+X=b:X,X 它的对偶问题是 min ss
w=Yb:YA- Y=C:Y, Y0 ss,
7对偶问题的最适用条件是什么当变量多于约束条件,对这样的线性规划问题用对偶单纯性法计算可以减少计算量,因此对变量较少,而约束条件很多的线性规划问题,可先将它变为对偶问题,然后用对偶单纯形法求解
10. 生产量、需求量、运输费用
11( A
12( 解析:错误 应为 “加上和减去” 13 答:从每一空格出发,用水平或垂直直线向前划,当碰到数字格可以转90?,继续前进,直到回到起始空格,在沿闭回路线上第一点开始的运费依次乘以+1、-1、+1、-1„„并求和,即为空格的检验数,若检验数均正,则为最优解,否则不是.
14答案 错 应为“ 增加一个销地”
15( 0
16(正确
17 答案: m+n,1个变量组构成基变量的充要条件是它不包含任何闭回路。
18. 答案: 非负
19. 1.求初始运输
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
2.求检验数 3.调整运量 20. 答案:将不平衡问题化为平衡问题再按平衡问题求解。
21.线性相关
22( m+n-1 、 r<=m+n-1
23(要求解的整数规划问题A,与它相应的线性规划问题称为B,解线性规划的问题B,所以得到的以下几种情况中的哪个是正确的(
D)
A. B没有可行解,A也没有可行解时停止计算。 B. B有最优解,并符合问题,的整数条件,则此最优解极为,的最优。 C. B有最优解,但不符合A的整数条件。 D. B没有最优解,A也没有最优解。
24. 分支界定法的步骤: 第一步 先不考虑整数约束,变成一般的线性规划问题,用图解法或单纯形发球其最优解,记为x。第二步:若求得的最优解x,刚好就是整数解,则该整数解就是原整数规划的最优解,否则转下步。第三步:对原问题进行分支寻求整数最优解。第四步:对上面两个字问题按照线性规划方法球最优解。若子问题的解是整数解,则停止该子问题的分支,并把他的目标值与上一步求出的最优整数解相比较已决定取舍;否则,对该子问题继续进行分支。第五步:重复第三四步直至获得原问题的最优解为止。
25. 割平面法与分支界定法德基本思路是__不断增加新约束,通过求解线性规划问题,得到整数最优解。______________。
26(切割方程由单纯形表的最终表中的任一个含有_非整数基变量 __________的等式约束演变而来的。因此切割方程不唯一,可令为相应的线性规划的最优解中为分数________的一个基变量,得到单纯形表。
27(
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
型的指派问题要满足的两个条件目标为min z; 系数矩阵为方阵且所有元素均为非负
28(解矩阵是什么意思,满足条件的可行解写成表格或矩阵形式,称
为解矩阵
29(指派问题最优解的性质若从系数矩阵的一行各元素中分别减去该行的最小元素得到新矩阵,那么以新矩阵为系数矩阵求得的最优解和用原矩阵求得的最优解相同。
30. 枚举法是将所有变量取0.、1的组合逐个带入约束条件试算的方法找可行解.
31. 0—1规则的变量有n个,则存在个可行解。
对 错
32.运输问题的一半数学模型是哪个,
A.线性规划模型
B.混合0—1型模型
C全0—1型模型
D.混合整数规划模型
32. 解一般整数规划,0—-1整数规划,指派问题分别用什么方法,分枝定界法、割平面法,隐枚举法,匈牙利法
33..求最大值的指派问题与最小值的指派问题处理时有什么区别,最小值时是减去每行的最小值,然后再减去每列的最小值,而求最大值时,是用每行的最大值减去每行的元素,再找出每列的最大值减去每列的元素,其他两者一样
34(指派问题(匈牙利法)的基本步骤:1、分枝定界法、割平面法,隐枚举法,匈牙利法。2、最小值时是减去每行的最小值,然后再减
去每列的最小值,而求最大值时,是用每行的最大值减去每行的元素,再找出每列的最大值减去每列的元素,其他两者一样。3(第一;找出矩阵中每一行的最小元素,分别从每行中减去最小元素,再所得矩阵中找出每列的最小元素,再分别从每列中减去。第二;用最少直线覆盖所有的0第三;当直线等于原矩阵的阶时停止,否则从矩阵未被直线覆盖的数字中找出一个最小的书k,在直线相交处的元素加上k,未被直线覆盖的元素减去k,被直线覆盖没相交的元素不变。再用最少直线覆盖,直到与原矩阵阶相等。第四;找出每一列中0元素最少的那一列的0元素画o,它所对应的那一行的其他0叉掉,依次类推,画o所代表的元素即为所求的基
35.当原问题无可行解时,问其对偶问题的情况,
它们的换基顺序不同,对偶单纯法先确定出基变量再确定进基变量,而普通单纯形法先确定进基变量再确定出基变量。
37.互补松弛定理 设X?、Y?分别为(LP)与(DP)的可行解,XS和YS是它的松弛变量的可行解,则X?和Y?是最优解当且仅当YSX?=0和Y?XS=0
38.判断:若原问题存在可行解,其对偶问题一定存在可行解码,不一定
39. 判断线性目标规划模型中目标函数是否得到满意解,
(1)检验数P1,P2,…,,k行的所有值均为非负;
(2)P1,…,Pi行所有检验数,第Pi+1行存在负检验数,但在负检验数所在列的上面行中有正检验数。
40. 用单纯形法求解目标规划问题的大概步骤,
第,步:列出初始单纯形表
第,步:确定换入变量。
第,步:确定换出变量
第,步:用换入变量替换基变量中的换出变量,进行迭代运算,得到满意解。
41. 关于目标规划单纯性法中如何确定换入变量和换出变量, 在Pk行,从那些上面没有正检验数的负检验数中,选绝对值最大者,记这一列为s列,则Xs就是换入变量。
确定换出变量依据最小比值法,b列数字同Xi列中的
正数相比,其最小比值对应的变量Xj即为换出变量。 42. 简要阐述一下目标规划模型中目标的优先级与权系数。 目标的优先级与权系数。在一个目标规划的模型中,如果两个不同目标重要程度相差悬殊,为达到某一目标可牺牲其它一些目标,称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1,P2…表示,并规定Pk>>Pk+1即不同优先级之间的差别无法用数字大小衡量。对属于同一层次优先级的不同目标,按其重要程度可分别乘以不同的权系数。权系数是一个具体数字,乘上的权系数越大,表明该目标越重要。
43. 简单阐述一下正负偏差量的定义
负偏差量表示实现值未达到目标值的部分,
正偏差量表示实现值超过目标值的部分。
44. 简单阐述系统约束和目标约束
在引入了目标值和正负偏差量后,可以将目标函数加上负偏差量,减去正偏差量,并令其等于目标值,形成新的约束条件,成为目标约束。而系统约束,是指必须严格满足的等式和不等式约束,线性规划问题中的所有的约束条件是绝对约束。
45. 下列逻辑是否正确。
,,(1) maxZ=d+ d
,,(2) maxZ=d — d
,,(3) minZ=d + d
,,(4) minZ=d — d
46. 目标规划与线性规划相比的优点
在实际问题中不一定需要线性规划的绝对最优解,在实际情况中有轻重缓急和主次之分,目标规划的满意解更容易满足实际需要。 47. 满意解的定义
目标规划问题中的求解是分级进行的,在不破坏上一级目标的前提下,实现下一个目标的最优,这样求得的解就是满意解。 48. 目标的优先级与权系数
目标的优先级与权系数。在一个目标规划的模型中,如果两个不同目标重要程度相差悬殊,为达到某一目标可牺牲其它一些目标,称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因
子P1,P2…表示,并规定 Pk>>Pk+1即不同优先级之间的差别无法用数字大小衡量。对属于同一层次优先级的不同目标,按其重要程度可分别乘以不同的权系数。权系数是一个具体数字,乘上的权系数越大,表明该目标越重要。
49.原问题与对偶问题的对应关系,
1.50.价值系数变化在什么范围时,目标函数值不变,51.填空题:线性规划的解的四种形式是,,,、,,,、,,,、,,,。有唯一最优解、有多重解、有无界解、无可行解。
2.52.填空题:若线性规划问题的系数矩阵为A,A是m×n矩阵。当
mCnm,n时,该线性规划最多有,,个基矩阵。
QQ123.53.判断题:在一个线性规划的图解中,线段上的点为最优解时,
QQQQ1212点、为线段端点,则点、都是基本最优解。正确
54.判断题:线性规划的基本可行解集合K中的点X是极点的充要条件为X是基本可行解,极点与基本可行解是一一对应的。错误
。
55.简答题:线性规划通常用于解决哪类问题, (1)当任务或目标确定后,如何统筹兼顾,合理安排,用最少的资源 (如资金、设备、原标材料、人工、时间等)去完成确定的任务或目标;(2)在一定的资源条件限制下,如何组织安排生产获得最好的经济效益(如产品量
最多 、利润最大.
56.简答题:怎样辨别一个模型是线性规划模型,a解决问题的目标函数是多个决策变量的线性函数,通常是求最大值或最小值;
b解决问题的约束条件是一组多个决策变量的线性不等式或等式。
n57.简答题:线性规划数学模型的一般表达式,max(min)Z,cx,jj,1j4.
n,ax,( ,,,)bi,ijj, i,1,2,L,m,j,1
,x,0,j,1,2,L,nj,
58.简答题:如何将一个线性规划问题化为标准型,(说出具体步骤)5.
(1)若目标函数要求minZ=CX,则变化为标准型时令Z'=-Z,可得maxZ'=-CX;
(2)若约束条件右端项有bi<0,则在该不等式两端同时乘以-1; (3)约束方程为?不等式时,在?不等式左端加入非负松弛变量;若为?不等式,则在原不等式左端减去一个非负剩余变量,变为等式约束条件;
(4)若存在取值无约束的变量Xk,可令Xk=Xk'-Xk'',其中Xk',Xk''?0.
59.简答题:在用单纯形法解线性规划问题时,如何判断最终的解11.
的情况,
a唯一最优解的判断:最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解
b多重最优解的判断:最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解.
c无界解的判断: 某个λk>0且aik?,(i=1,2,…,m)则线性规划具有无界解
d无可行解的判断:当用大M单纯形法计算得到最优解并且存在至少一个人工变量大于零时,则表明原线性规划无可行解。
6.60. 判断题:单纯形法求解时一定要化为标准型正确