复习思考题
第一章
11判断下列说法是否正确:
(a)图解法与单纯形法虽然求解的形式不同,但从几何上理解, 两者是一致的。
正确。
(b)线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大。正确。
这里注意:增加约束,可行域不会变大;减少约束,可行域不会变小。 (c)线性规划问题的每一个基解对应可行域的一个顶点。错误。
线性规划的基本定理之一为:线性规划问题的基本可行解对应于可行域的顶点。
(d)如线性规划问题存在可行域,则可行域一定包含坐标的原点。错误。
如果约束条件中有一个约束所对应的区域不包含坐标的原点,则即使有可行域,也不包含坐标的原点。 (e)取值无约束的变量xi,通常令xi=xi'-xi'',其中xi'≥0,xi''≥0,在用单纯形法求得的最优解中,有可能同时出现xi'>0,xi''>0。错误。
由于Pi=-Pi,BPi=(Pi
'
"
-1t
''
)
t
=-BPi=-(Pi
-1t
"
"
)
t
,因此,xi'和xi''中至多只有一个是Bt下的基变量,从而
xi和xi中至多只有一个取大于零的值。
'''
(f)用单纯形法求解标准型式的线性规划问题时,与σj>0对应的变量都可以被选作入基变量。正确。 如表1-1,取xk为入基变量,旋转变换后的目标函数值相反数的新值为:
-z
t+10
=-z-
t0
bl⨯σk
a
tlk
tt
=-z0-θlσk
ttt
tttttt
即旋转变换后的目标函数值增量为θlσk,由于θl≥0,只要σk≥0,就能保证θlσk≥0,满足单纯形法基变换
后目标函数值不劣化的要求。
表1-1
(g 正确。
假定单纯形法计算中,θ比值至少有两个不同的值θlt和θst,θlt为最小比值。 则θ=min
aik>0
t
tl
bia
t
tik
=
bla
t
tlk
ts
bsa
t
tsk
表1-2
如果取xts为出基变量,则有
b
t+1
l
=b-
tl
bs⨯alk
ask
t
tt
=a(
tlk
bl
t
alk
t
-
bs
t
t
ask
)
(h)单纯形法计算中,选取最大正检验数σk对应的变量作为换入变量,将使目标函数值得到最快的增长。错误。
假设存在正检验数,其中最大者为σk,取xk为入基变量,参考(f),可知旋转变换后的目标函数值增量为θlσk,无法肯定目标函数值得到了最快的增长。
(i)一旦一个人工变量在迭代中变为非基变量后,则该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果。正确。
人工变量一般是为取得对应的初始基基向量而引入的,它一旦成为出基变量,其地位已被对应的入基变量取代,删除单纯形表中该变量及相应列的数字,不影响计算结果。
(j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示。错误。
对可行域非空有界,(j)中线性组合改为凸组合就是正确的;对可行域无界,很明显,(j)不正确。
1212
(k)若x和x分别是某一线性规划问题的最优解,则x=λ1x+λ2x也是该线性规划问题的最优解,其中t
t
λ1和λ2为任意的正实数。错误。
设(P)如下:
maxz=cx⎧Ax=bs.t.⎨
⎩x≥0
(1)(2) (3)
又设x1和x2是的最优解。令x=λ1x1+λ2x2,λ1≥0,λ2≥0, 则:x≥0;
1212
Ax=A(λ1x+λ2x)=λ1Ax+λ2Ax=λ1b+λ2b=(λ1+λ2)b;
1212***
z=cx=c(λ1x+λ2x)=λ1cx+λ2cx=λ1z+λ2z=(λ1+λ2)z。
如果λ1+λ2=1,(k)正确;否则,(k)不正确。
(l)线性规划用两阶段法求解时,第一阶段的目标函数通常写为min也可以写为min
z=
z=
∑x
i
Gi
(xGi为人工变量),但
∑kx
ii
Gi
,只要所有ki均为大于零的常数。正确。
由于所有ki>0,所有xGi≥0,因此∑xGi≥0等价于∑kixGi≥0,(l)正确。
i
i
m
(m)对一个有n个变量,m个约束的标准型的线性规划问题,其可行域顶点恰好是cn个。错误。 ①如果m不是约束组约束个数,(m)不对。
②如果m为约束组约束个数(系数矩阵的行数),则可行基的最大数目为cn,由于线性规划问题的基本可行解对应于可行域的顶点,(m)也不对。
(n)单纯形法的迭代计算过程是从一个可行解转到目标函数值更大的另一个可行解。错误。
①迭代计算前后的解是基本可行解,不是任意可行解,因此(n)不对;
tttt
②把(n)中可行解换为基本可行解,据(h),旋转变换后的目标函数值增量为θlσk,由于θl≥0, σk≥0,
m
tttt
故θlσk≥0,不排除θlσk=0的可能。
(o)线性规划问题的可行解如为最优解,则该可行解一定是基本可行解。错误。
唯一最优解时,最优解是可行域顶点,对应基本可行解;无穷多最优解时,除了其中的可行域顶点对应基本可行解外,其余最优解不是可行域的顶点,。
(p)若线性规划问题具有可行解,且其可行域有界,则该线性规划问题最多具有有限个数的最优解。错误。
如果在不止一个可行解上达到最优,它们的凸组合仍然是最优解,这样就有了无穷多的最优解。 (q) 线性规划可行域的某一顶点若其目标函数值优于相邻所有顶点的目标函数值,则该顶点处的目标函数值达到最优。错误。
(r)将线性规划约束条件的"≤"号及"≥"号变换成"="号,将使问题的最优目标函数值得到改善。错误。 (s) 线性规划目标函数中系数最大的变量在最优解中总是取正的值。错误。
(t) 一个企业利用3种资源生产5种产品,建立线性规划模型求解到的最优解中,最多只含有3种产品的组合。错误。
(u)若线性规划问题的可行域可以伸展到无限,则该问题一定具有无界解。错误。
(v)一个线性规划问题求解时的迭代工作量主要取决于变量数的多少,与约束条件的数量关系较少。错误。 第二章
10判断下列说法是否正确:
(a)任何线性规划问题存在并具有唯一的 对偶问题。正确。 (b)对偶问题的对偶一定是原问题。正确。
(c)根据对偶问题的性质,当原问题为无界解时,其对偶问题无可行解;反之,当对偶问题无可行解时,其原问题具有无界解。错误。
**
(d)设x和y分别是标准形式(P)和(D)的可行解,则恒有cx≤cx*=y*b≤yb。 x和y分别为其最优解,
正确。
(e)若线性规划问题有无穷多最优解,则其对偶问题也一定具有无穷多最优解。错误。 (f)若原问题有可行解,则其对偶问题有可行解。错误。 (g)若原问题无可行解,则其对偶问题也一定无可行解。错误。 (h)若原问题有最优解,则其对偶问题也一定有最优解。正确。
(i)若原问题和对偶问题均存在可行解,则两者均存在最优解。正确。
(j)原问题决策变量与约束条件数量之和等于其对偶问题的决策变量与约束条件数量之和。错误。 (k)用对偶单纯形法求解线性规划的每一步,在单纯形表检验数行与基变量列对应的原问题与对偶问题的解代入各自的目标函数得到的值始终相等。正确。
(l)如果原问题的约束方程Ax≤b变成Ax≥b,则其对偶问题的唯一改变就是非负的y≥0变成非正的
y≤0。正确。
**
(m
若yi>0说明在最优生产计划中第i种资源已
经耗尽。正确。
**
(n
若yi=0说明在最优生产计划中第i种资源已经
耗尽一定有剩余。错误。
(o)如果某种资源的影子价格为k,在其它条件不变的前提下,当该种资源增加5个单位时,相应的目标函数值将增加5k。正确。
(p)应用对偶单纯形法计算时,若单纯形表中某一基变量xi
(q)若线性规划问题中的bi、cj发生变化,反应到最终单纯形表中,不会出现原问题和对偶问题均为非可行解的情况。错误。
(r)在线性规划问题的最优解中,如果某一变量xj为非基变量,则在原来问题中,无论改变它在目标函数中的系数cj或在各约束中的相应系数aij,反应到最终单纯形表中,除该列数字有变化外,将不会引起其它列数字的变化。正确。 第三章
10判断下列说法是否正确:
(a)运输问题是一种特殊的线性规划模型,因而求解的结果也可能出现下列四种情况之一:有唯一最优解,有无穷多最优解,无界解,无可行解。错误。
(b)在运输问题中,只要任意地给出一组含m+n-1个非零的{xij},且满足∑xij=ai,∑xij=bj,就
j=1
i=1
nm
可以作为一个初始基本可行解。错误。
(c)表上作业法实质上就是求解运输问题的单纯形法。正确。
(d)按最小元素法(或伏格尔法)给出的初始基可行解,从每一空格出发可以找出而且仅能找出唯一的闭回路。正确。
(e)如果运输问题单位运价表的某一行(或某一列)元素分别加上一个常数k,最优调运方案将不会发生变化。正确。
(f)如果运输问题单位运价表的某一行(或某一列)元素分别乘上一个常数k,最优调运方案将不会发生变化。错误。
(g)如果在运输问题或转运问题中,cij是从产地i到销地j的最小运输费用,则运输问题和转运问题将得到相同的最优解。错误。
(h)当所有产地的产量和所有销地的销量均为整数时,运输问题的最优解也为整数值。错误。 (i)如果运输问题单位运价表的全部元素乘上一个常数k(k>0),最优调运方案将不会发生变化。 正确。
(j)产销平衡运输问题中含有(m+n)个约束条件,但其中总有一个是多余的。错误。
(k)用位势法求运输问题某一调运方案的检验数时,其结果可能同闭回路法求得的结果有异。错误。 第四章
5判断下列说法是否正确:
(a)线性规划问题是目标规划问题的一种特殊形式。正确。 (b)正偏差变量取正值,负偏差变量应取负值。错误。
(c)目标规划模型中,可以不包含系统约束(绝对约束),但必须包含目标约束。正确。 (d)同一个目标约束中的一对偏差变量di、di至少有一个取值为零。正确。 (e)目标规划的目标函数中,既包含决策变量,又包含偏差变量。正确。 (f)只含目标约束的目标规划模型一定存在满意解。正确。
(g)目标规划模型中的目标函数按问题性质要求分别表示为求min或求max。正确。
(h)目标规划模型中的优先级p1,p2, ,其中pi较之pi+1目标的重要性一般为数倍至数十倍之间。错误。
-
+
复习思考题
第一章
11判断下列说法是否正确:
(a)图解法与单纯形法虽然求解的形式不同,但从几何上理解, 两者是一致的。
正确。
(b)线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大。正确。
这里注意:增加约束,可行域不会变大;减少约束,可行域不会变小。 (c)线性规划问题的每一个基解对应可行域的一个顶点。错误。
线性规划的基本定理之一为:线性规划问题的基本可行解对应于可行域的顶点。
(d)如线性规划问题存在可行域,则可行域一定包含坐标的原点。错误。
如果约束条件中有一个约束所对应的区域不包含坐标的原点,则即使有可行域,也不包含坐标的原点。 (e)取值无约束的变量xi,通常令xi=xi'-xi'',其中xi'≥0,xi''≥0,在用单纯形法求得的最优解中,有可能同时出现xi'>0,xi''>0。错误。
由于Pi=-Pi,BPi=(Pi
'
"
-1t
''
)
t
=-BPi=-(Pi
-1t
"
"
)
t
,因此,xi'和xi''中至多只有一个是Bt下的基变量,从而
xi和xi中至多只有一个取大于零的值。
'''
(f)用单纯形法求解标准型式的线性规划问题时,与σj>0对应的变量都可以被选作入基变量。正确。 如表1-1,取xk为入基变量,旋转变换后的目标函数值相反数的新值为:
-z
t+10
=-z-
t0
bl⨯σk
a
tlk
tt
=-z0-θlσk
ttt
tttttt
即旋转变换后的目标函数值增量为θlσk,由于θl≥0,只要σk≥0,就能保证θlσk≥0,满足单纯形法基变换
后目标函数值不劣化的要求。
表1-1
(g 正确。
假定单纯形法计算中,θ比值至少有两个不同的值θlt和θst,θlt为最小比值。 则θ=min
aik>0
t
tl
bia
t
tik
=
bla
t
tlk
ts
bsa
t
tsk
表1-2
如果取xts为出基变量,则有
b
t+1
l
=b-
tl
bs⨯alk
ask
t
tt
=a(
tlk
bl
t
alk
t
-
bs
t
t
ask
)
(h)单纯形法计算中,选取最大正检验数σk对应的变量作为换入变量,将使目标函数值得到最快的增长。错误。
假设存在正检验数,其中最大者为σk,取xk为入基变量,参考(f),可知旋转变换后的目标函数值增量为θlσk,无法肯定目标函数值得到了最快的增长。
(i)一旦一个人工变量在迭代中变为非基变量后,则该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果。正确。
人工变量一般是为取得对应的初始基基向量而引入的,它一旦成为出基变量,其地位已被对应的入基变量取代,删除单纯形表中该变量及相应列的数字,不影响计算结果。
(j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示。错误。
对可行域非空有界,(j)中线性组合改为凸组合就是正确的;对可行域无界,很明显,(j)不正确。
1212
(k)若x和x分别是某一线性规划问题的最优解,则x=λ1x+λ2x也是该线性规划问题的最优解,其中t
t
λ1和λ2为任意的正实数。错误。
设(P)如下:
maxz=cx⎧Ax=bs.t.⎨
⎩x≥0
(1)(2) (3)
又设x1和x2是的最优解。令x=λ1x1+λ2x2,λ1≥0,λ2≥0, 则:x≥0;
1212
Ax=A(λ1x+λ2x)=λ1Ax+λ2Ax=λ1b+λ2b=(λ1+λ2)b;
1212***
z=cx=c(λ1x+λ2x)=λ1cx+λ2cx=λ1z+λ2z=(λ1+λ2)z。
如果λ1+λ2=1,(k)正确;否则,(k)不正确。
(l)线性规划用两阶段法求解时,第一阶段的目标函数通常写为min也可以写为min
z=
z=
∑x
i
Gi
(xGi为人工变量),但
∑kx
ii
Gi
,只要所有ki均为大于零的常数。正确。
由于所有ki>0,所有xGi≥0,因此∑xGi≥0等价于∑kixGi≥0,(l)正确。
i
i
m
(m)对一个有n个变量,m个约束的标准型的线性规划问题,其可行域顶点恰好是cn个。错误。 ①如果m不是约束组约束个数,(m)不对。
②如果m为约束组约束个数(系数矩阵的行数),则可行基的最大数目为cn,由于线性规划问题的基本可行解对应于可行域的顶点,(m)也不对。
(n)单纯形法的迭代计算过程是从一个可行解转到目标函数值更大的另一个可行解。错误。
①迭代计算前后的解是基本可行解,不是任意可行解,因此(n)不对;
tttt
②把(n)中可行解换为基本可行解,据(h),旋转变换后的目标函数值增量为θlσk,由于θl≥0, σk≥0,
m
tttt
故θlσk≥0,不排除θlσk=0的可能。
(o)线性规划问题的可行解如为最优解,则该可行解一定是基本可行解。错误。
唯一最优解时,最优解是可行域顶点,对应基本可行解;无穷多最优解时,除了其中的可行域顶点对应基本可行解外,其余最优解不是可行域的顶点,。
(p)若线性规划问题具有可行解,且其可行域有界,则该线性规划问题最多具有有限个数的最优解。错误。
如果在不止一个可行解上达到最优,它们的凸组合仍然是最优解,这样就有了无穷多的最优解。 (q) 线性规划可行域的某一顶点若其目标函数值优于相邻所有顶点的目标函数值,则该顶点处的目标函数值达到最优。错误。
(r)将线性规划约束条件的"≤"号及"≥"号变换成"="号,将使问题的最优目标函数值得到改善。错误。 (s) 线性规划目标函数中系数最大的变量在最优解中总是取正的值。错误。
(t) 一个企业利用3种资源生产5种产品,建立线性规划模型求解到的最优解中,最多只含有3种产品的组合。错误。
(u)若线性规划问题的可行域可以伸展到无限,则该问题一定具有无界解。错误。
(v)一个线性规划问题求解时的迭代工作量主要取决于变量数的多少,与约束条件的数量关系较少。错误。 第二章
10判断下列说法是否正确:
(a)任何线性规划问题存在并具有唯一的 对偶问题。正确。 (b)对偶问题的对偶一定是原问题。正确。
(c)根据对偶问题的性质,当原问题为无界解时,其对偶问题无可行解;反之,当对偶问题无可行解时,其原问题具有无界解。错误。
**
(d)设x和y分别是标准形式(P)和(D)的可行解,则恒有cx≤cx*=y*b≤yb。 x和y分别为其最优解,
正确。
(e)若线性规划问题有无穷多最优解,则其对偶问题也一定具有无穷多最优解。错误。 (f)若原问题有可行解,则其对偶问题有可行解。错误。 (g)若原问题无可行解,则其对偶问题也一定无可行解。错误。 (h)若原问题有最优解,则其对偶问题也一定有最优解。正确。
(i)若原问题和对偶问题均存在可行解,则两者均存在最优解。正确。
(j)原问题决策变量与约束条件数量之和等于其对偶问题的决策变量与约束条件数量之和。错误。 (k)用对偶单纯形法求解线性规划的每一步,在单纯形表检验数行与基变量列对应的原问题与对偶问题的解代入各自的目标函数得到的值始终相等。正确。
(l)如果原问题的约束方程Ax≤b变成Ax≥b,则其对偶问题的唯一改变就是非负的y≥0变成非正的
y≤0。正确。
**
(m
若yi>0说明在最优生产计划中第i种资源已
经耗尽。正确。
**
(n
若yi=0说明在最优生产计划中第i种资源已经
耗尽一定有剩余。错误。
(o)如果某种资源的影子价格为k,在其它条件不变的前提下,当该种资源增加5个单位时,相应的目标函数值将增加5k。正确。
(p)应用对偶单纯形法计算时,若单纯形表中某一基变量xi
(q)若线性规划问题中的bi、cj发生变化,反应到最终单纯形表中,不会出现原问题和对偶问题均为非可行解的情况。错误。
(r)在线性规划问题的最优解中,如果某一变量xj为非基变量,则在原来问题中,无论改变它在目标函数中的系数cj或在各约束中的相应系数aij,反应到最终单纯形表中,除该列数字有变化外,将不会引起其它列数字的变化。正确。 第三章
10判断下列说法是否正确:
(a)运输问题是一种特殊的线性规划模型,因而求解的结果也可能出现下列四种情况之一:有唯一最优解,有无穷多最优解,无界解,无可行解。错误。
(b)在运输问题中,只要任意地给出一组含m+n-1个非零的{xij},且满足∑xij=ai,∑xij=bj,就
j=1
i=1
nm
可以作为一个初始基本可行解。错误。
(c)表上作业法实质上就是求解运输问题的单纯形法。正确。
(d)按最小元素法(或伏格尔法)给出的初始基可行解,从每一空格出发可以找出而且仅能找出唯一的闭回路。正确。
(e)如果运输问题单位运价表的某一行(或某一列)元素分别加上一个常数k,最优调运方案将不会发生变化。正确。
(f)如果运输问题单位运价表的某一行(或某一列)元素分别乘上一个常数k,最优调运方案将不会发生变化。错误。
(g)如果在运输问题或转运问题中,cij是从产地i到销地j的最小运输费用,则运输问题和转运问题将得到相同的最优解。错误。
(h)当所有产地的产量和所有销地的销量均为整数时,运输问题的最优解也为整数值。错误。 (i)如果运输问题单位运价表的全部元素乘上一个常数k(k>0),最优调运方案将不会发生变化。 正确。
(j)产销平衡运输问题中含有(m+n)个约束条件,但其中总有一个是多余的。错误。
(k)用位势法求运输问题某一调运方案的检验数时,其结果可能同闭回路法求得的结果有异。错误。 第四章
5判断下列说法是否正确:
(a)线性规划问题是目标规划问题的一种特殊形式。正确。 (b)正偏差变量取正值,负偏差变量应取负值。错误。
(c)目标规划模型中,可以不包含系统约束(绝对约束),但必须包含目标约束。正确。 (d)同一个目标约束中的一对偏差变量di、di至少有一个取值为零。正确。 (e)目标规划的目标函数中,既包含决策变量,又包含偏差变量。正确。 (f)只含目标约束的目标规划模型一定存在满意解。正确。
(g)目标规划模型中的目标函数按问题性质要求分别表示为求min或求max。正确。
(h)目标规划模型中的优先级p1,p2, ,其中pi较之pi+1目标的重要性一般为数倍至数十倍之间。错误。
-
+