当一对对偶规划达到最优时，如果一个问题的某个约束条件取不等式 ，则其对应的另一问题的变量取值为多少（）。

(1)写出可行区域D中的所有顶点;

(2)证明若一个线性规划问题在两个顶点上达到最优值，则此线性规划问题必有无穷多个最优解。

如,可以用6次乘法逐步计算x²³如下:.可以证明,计算x²³最少需要6次乘法.计算x23的幂序列中各幂次1、2、3、5、10、20、23组成了一个关于整数23的加法链.一般情况下,计算xⁿ的幂序列中各幂次组成正整数n的一个加法链:

上述最优求幂问题相应于正整数n的最短加法链问题,即求n的一个加法链,使其长度r达到最小.正整数n的最短加法链长度记为l(n).

算法设计:对于给定的正整数n,计算相应于正整数n的最短加法链.

数据输入:由文件input.txt给出输入数据.第1行有1个正整数n.

结果输出:将计算的最短加法链长度l(n)和相应的最短加法链输出到文件output.txt.

要的函数,并将此的数用于解0-1背包问题.

0-1背包问题描述如下;给定n种物品和一个背包.物品i的重量是w_i,其价值为v_i背包的容量为C.应如何选择装入背包的物品,使装入背包中物品的总价值最大？

在选择装入肯包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包.不能将物品i装入背包多次,也不能只装入部分的物品i.

0-1背包问题形式化描述如下:给定,要求n元0-1向量,使得而且达到最大.

算法设计:对于给定的n种物品的重量和价值,以及背包的容量,计算可装入背包的最大价值.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是物品数,c是背包的容量.接下来的1行中有n个正整数,表示物品的价值.第3行中有n个正整数,表示物品的重量.

结果输出:将计算的装入背包物品的最大价值和最优装入方案输出到文件output.txt

所示。

股民从网上搜索到了这几家公司股票的投资风险，这六只股票收益方差和协方差的数据入下表所示。

试问：

(1)一开始，如果忽视所有投资的风险，在这种情况下，最优的投资组合决策是什么，也就是在六种不同股票上分别投资多少？该投资组合总的风险是多少？

(2)假设不能在一种股票上投入超过总额40%的资金，在不考虑风险并加入这一限制条件下，最优投资组合是什么，该投资组合的总风险又是什么？

(3)将投资风险考虑在内，建立一个二次规划模型，使总风险最小，同时保证预期收益不低于所选择的最低可接受水平;

①希望能够获得至少35%的预期收益，同时又要保持最小的投资风险，这种情况下，最优的投资组合该如何？

②要获得至少25%的预期收益，最小风险是多少？要获得至少40%的预期收益，情况又会如何？

问题描述:给定一个赋权无向图G=(V,E),每个顶点都有权值w(v).如果,且对任意(u,V)∈E有u∈U或v∈U,就称U为图G的一个顶点覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖.

算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2个正整数u和v,表示图G的一条边(u,v).

结果输出:将计算的最小权顶点覆盖的顶点权值和以及最优解输出到文件output.txt.文件的第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi(1≤i≤n),xi=0表示顶点i不在最小权顶点覆盖中,xi=1表示顶点i在最小权顶点覆盖中.

设有线性规划问题及这里λ，μ均为大于0的实数，说明这两个问题的最优解的关系。当λ＜0或μ＜0时，这两者关系如何？

问题描述:设p是奇素数,1≤x≤p-1,如果存在一个整数y(1≤y≤p-1),使得x=y²(modp),则称y是x的模p平方根.例如,63是55的模103平方根.试设计一个求整数x的模p平方根的拉斯维加斯算法.算法的计算时间应为logp的多项式.

算法设计:设计一个拉斯维加斯算法,对于给定的奇素数p和整数x,计算x的模p平方根.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数p和x.

结果输出:将计算的x的模p平方根输出到文件output.txt.当不存在x的模p平方根时,输出0.

Voronoi图。Voronoi图最早应用在气象学中，荷兰气候学家ThiessenA.H.利用它研究降雨量的问题。

所给出的对平面的剖分.称为以P.为生成元的Voronoi图，简称V图。图中的顶点和边分别称为Voronoi点和Voronoi边，V(p)称为点Pi的Voronoi区域(多边形)，其中d(p，p)为点p和点P:之间的欧几里得距离。Voronoi图将相邻两个生成元相连接，并且做出连接线段的垂直评分线，这些垂直平分线之间的交线就形成一些多边形，这样就把整个平面剖分成一些分区域，一个分区域只含有一个生成元，分区域内生成元的属性可以代替此分区域的属性，而且可以根据分区域的面积作为权重推测出该区城中生成元的平均水平。若两个生成元Pi，Pj的Voronoi区城有公共边，就连接这两个点，以此类推遍历这n个生成元，可以得到一个连接点集S的唯一确定的网络，称为Delaunay三角网格，图4.13是Matlab软件画出的10平面点的Voronoi图及对偶Delaunay三角网格图。

Voronoi图具有下列重要性质：

(1)Voronoi图与Delaunay三角网格图对偶;

(2)Voronoi图具有局域动态性，即增加和删除--个生成元只影响相邻生成元的Voronoi区域;

(3)如果点P.在区域V(p.)中，则p到各生成元的距离中，到生成元P的距离最小;

(4)两个相邻Voronoi区域的公共边上任意--点到这两个区域的生成元距离相等;

(5)Voronoi区域的顶点到邻近的生成元的距离相等，即与这个顶点有关的Voronoi区域的生成元共圆.称这个圆为最大空圆。

画出表4.18中数据对应的10个点的Voronoi图及其对偶Delauny三角网格图。

加油站停靠加油,使沿途加油次数最少.并证明算法能产生一个最优解.

算法设计:对于给定的n和k个加油站位置,计算最少加油次数.

数据输入:由文件input.tst给出输入数据.第1行有2个正整数n和k,表示汽车加满油后可行驶nkm,且旅途中有k个加油站.接下来的1行中有k+1个整数,表示第k个加油站与第k-1个加油站之间的距离.第0个加油站表示出发地,汽车已加满油.第k+1个加油站表示目的地.

结果输出:将计算的最少加油次数输出到文件output.txt.如果无法到达目的地,则输出“NoSolution",

号。然而，当轮到他们就诊时，却挤进一位带着孩子的家长抢先就诊，后打听得知该家长与专家是熟人。此案例中违背了患者的

A.自主权

B.隐私权

C.公平医疗权

D.损害求偿权

E.监督医疗权