下载文档原格式
. 1实验报告实验课程名称运筹学实验工程名称大M法或两阶段法的上机实验年级专业学生学号00 学院实验时间：年月日实验容〔包括实验具体容、算法分析、源代码等等〕：1.书上P97页第6题：用大M 法和两阶段法求解以下线性规划问题。
ma* z=5；3213x x x ++ 约束条件：102x 4x x 321≥++，16.x 2x -x 321≤+A ：大M 法图1.1图1.2δ，得出目标函数的最优解*1=16，*2=0，由上面的结果可知，满足所求出的0≤j*3=0，s*4=16，R*5=0，s*=0，最优值是80。
当把M的值改为100000后，值还是一样的，这样就可以得出当M为100时，已经得出有效解。
B：两阶段法图1.3由图1.3可知，先进展线性规划的第一阶段，满足0≤j δ，且z 值为零，即说明存在一个可行解使得所有的人工变量都为零，此时*2=2.5，s*6=21，其余为0得出z=0。
接下来进展第二阶段，令z=5*1+*2+3*3-0s*4+0R*5+0s*6，和大M 的分析方法一样，最终将得到满足0≤j δ时到达最优解：当*1=16，*2=0，*3=0，s*4=6，R*5=0，s*6=0，最优值为80。
2.书上P97页第7题〔4〕大M 法和两阶段法求解以下线性规划问题 。
ma* z=；321x x 2x ++ 约束条件：，42x 2x 4x 321≥++，204x 2x 21≤+，162x 8x 4x 321≤++ A ：大M 法图2.1图2.2由上面的图 2.1可知，首先先输入数据即线性规划的系数如图 2.1所示令ma* z=321x x 2x ++-0s*4+0s*6+0s*7-MR*5；进展下一次迭代，以同样的方法一直下去，直到所求出的为止0≤j δ，就可以得出目标函数的最优解：*1=4，s*4=12，s*6=12，其余为0时，最优值为8。
当把M 的值改为100000后，值还是一样的，这样就可以得出当M 为100时，已经得出有效解。
《管理运筹学期末复习题》运筹学期末复习题⼀、判断题：1、任何线性规划⼀定有最优解。
（）2、若线性规划有最优解，则⼀定有基本最优解。
（）3、线性规划可⾏域⽆界，则具有⽆界解。
（）4、基本解对应的基是可⾏基。
（）5、在基本可⾏解中⾮基变量⼀定为零。
（）6、变量取0或1的规划是整数规划。
（）7、运输问题中应⽤位势法求得的检验数不唯⼀。
（）8、产地数为3，销地数为4的平衡运输中，变量组{X11，X13，X22，X33，X34}可作为⼀组基变量.（）9、不平衡运输问题不⼀定有最优解。
（）10、m+n-1个变量构成基变量组的充要条件是它们不包含闭回路。
（）11、含有孤⽴点的变量组不包含有闭回路。
（）12、不包含任何闭回路的变量组必有孤⽴点。
（）13、产地个数为m销地个数为n的平衡运输问题的系数距阵为A，则有r(A)≤m+n-1（）14、⽤⼀个常数k加到运价矩阵C的某列的所有元素上,则最优解不变。
（）15、匈⽛利法是求解最⼩值分配问题的⼀种⽅法。
（）16、连通图G的部分树是取图G的点和G的所有边组成的树。
（）17、求最⼩树可⽤破圈法.（）18、Dijkstra算法要求边的长度⾮负。
（）19、Floyd算法要求边的长度⾮负。
（）20、在最短路问题中，发点到收点的最短路长是唯⼀的。
（）21、连通图⼀定有⽀撑树。
（）22、⽹络计划中的总⼯期等于各⼯序时间之和。
（）23、⽹络计划中，总时差为0的⼯序称为关键⼯序。
（）24、在⽹络图中，关键路线⼀定存在。
（）25、紧前⼯序是前道⼯序。
（）26、后续⼯序是紧后⼯序。
（）27、虚⼯序是虚设的,不需要时间,费⽤和资源,并不表⽰任何关系的⼯序。
（）28、动态规划是求解多阶段决策问题的⼀种思路，同时是⼀种算法。
（）29、求最短路径的结果是唯⼀的。
（）30、在不确定型决策中，最⼩机会损失准则⽐等可能性则保守性更强。
（）31、决策树⽐决策矩阵更适于描述序列决策过程。
（）32、在股票市场中，有的股东赚钱，有的股东赔钱，则赚钱的总⾦额与赔钱的总⾦额相等，因此称这⼀现象为零和现象。
《数据模型与决策》复习题及参考答案第一章绪言一、填空题1．运筹学的主要研究对象是各种有组织系统的管理问题，经营活动。
2．运筹学的核心是运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。
3．模型是一件实际事物或现实情况的代表或抽象。
4、通常对问题中变量值的限制称为约束条件，它可以表示成一个等式或不等式的集合。
5．运筹学研究和解决问题的基础是最优化技术，并强调系统整体优化功能。
运筹学研究和解决问题的效果具有连续性。
6．运筹学用系统的观点研究功能之间的关系。
7．运筹学研究和解决问题的优势是应用各学科交叉的方法，具有典型综合应用特性。
8．运筹学的发展趋势是进一步依赖于_计算机的应用和发展。
9．运筹学解决问题时首先要观察待决策问题所处的环境。
10．用运筹学分析与解决问题，是一个科学决策的过程。
11.运筹学的主要目的在于求得一个合理运用人力、物力和财力的最佳方案。
12．运筹学中所使用的模型是数学模型。
用运筹学解决问题的核心是建立数学模型，并对模型求解。
13用运筹学解决问题时，要分析，定议待决策的问题。
14．运筹学的系统特征之一是用系统的观点研究功能关系。
15.数学模型中，“s·t”表示约束。
16．建立数学模型时，需要回答的问题有性能的客观量度，可控制因素，不可控因素。
17．运筹学的主要研究对象是各种有组织系统的管理问题及经营活动。
二、单选题1.建立数学模型时，考虑可以由决策者控制的因素是（ A ）A．销售数量 B．销售价格 C．顾客的需求 D．竞争价格2．我们可以通过（ C ）来验证模型最优解。
A．观察 B．应用 C．实验 D．调查3．建立运筹学模型的过程不包括（ A ）阶段。
A．观察环境 B．数据分析 C．模型设计 D．模型实施4.建立模型的一个基本理由是去揭晓那些重要的或有关的（ B ）A数量 B变量 C 约束条件 D 目标函数5.模型中要求变量取值（ D ）A可正 B可负 C非正 D非负6.运筹学研究和解决问题的效果具有（ A ）A 连续性B 整体性C 阶段性D 再生性7.运筹学运用数学方法分析与解决问题，以达到系统的最优目标。
大M 法大M 法的求解线性规划的过程和单纯形法一样，不同的是对线性规划的一般形式的处理方式，大M 法将线性规划min ,..0Ax b f Cx s t x =⎧=⎨≥⎩转化为如下问题min ,..,0T Ax y b f cx Me s t x y +=⎧=+⎨≥⎩步骤如下：（1） 首先将线性规划min ,..0Ax b f Cx s t x =⎧=⎨≥⎩转化成如下问题 min ,..,0T Ax y b f cx Me s t x y +=⎧=+⎨≥⎩； （2） 确定初始基变量矩阵B ；求解方程；（3） 令0N x =，计算B B f c x =；其中B c 和N x 分别代表基变量和非基变量的值，B c 表示基变量在目标函数中的系数；（4） 求解方程B B c ω=，对于所有非基变量计数判别数j j j j z c p c ω-=-，其中j p 为非基变量在约束系数矩阵中相对应的列，令max()k k j j z c z c -=-，如果0k k z c -≤，则停止计算，输出最优解，否则转步骤5；（5） 求解方程k k By p =，若k y 的每个分量均大于0，则问题不存在最优解，否则转步骤6；（6） 令min |0s i sk sk ik b b y y y ⎛⎫=> ⎪⎝⎭，其中B b x =，用k p 代替Bs p ，得到新的基变量矩阵B 再转步骤3计算。
例：12312312313123211423min 3,..21,,0x x x x x x f x x x s t x x x x x -+≤⎧⎪-++≥⎪=-++⎨-+=⎪⎪≥⎩解：先把上面的一般形式化为标准形式：123671234123561371234567min 3()21142321,,,,,,0f x x x M x x x x x x x x x x x x x x x x x x x x x =-++++-++≤⎧⎪-++-+≥⎪⎨-++=⎪⎪≥⎩ 得出：1211000114120110,320100011[31100]A b c M M -⎡⎤⎡⎤⎢⎥⎢⎥=--=⎢⎥⎢⎥⎢⎥⎢⎥-⎣⎦⎣⎦=-- 在MATLAB 命令窗口输入：A=[1 -2 1 1 0 0 0;-4 1 2 0 -1 1 0;-2 0 1 0 0 0 1];c=[-3 1 1 0 0 2 2];b=[11;3;1];[x,minf]=ModifSimpleMthd(A,c,b,[4 6 7])所得结果：x =4.0000 1.0000 9.0000 0 0 0 0 minf =-2.0000如果M=1会怎样？A=[1 -2 1 1 0 0 0;-4 1 2 0 -1 1 0;-2 0 1 0 0 0 1];c=[-3 1 1 0 0 1 1];b=[11;3;1];[x,minf]=ModifSimpleMthd(A,c,b,[4 6 7])得到的结果：x =4.0000 1.0000 9.0000 0 0 0 0 minf =-2.0000从结果可以看出，m=1 对结果没有影响。
运筹学复习题线性规划的基本概念一、填空题1．线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。
2．图解法适用于含有两个变量的线性规划问题。
3．线性规划问题的可行解是指满足所有约束条件的解。
4．在线性规划问题的基本解中，所有的非基变量等于零。
5．在线性规划问题中，基可行解的非零分量所对应的列向量线性无关6．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。
7．线性规划问题有可行解，则必有基可行解。
8．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即可得到最优解。
9．满足非负条件的基本解称为基本可行解。
10．在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。
11．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。
12．线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。
13．线性规划问题可分为目标函数求极大值和极小_值两类。
14．线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。
二、单选题1．如果一个线性规划问题有n个变量，m个约束方程(m<n)，系数矩阵的数为m，则基可行解的个数最多为_C_。
A．m个 B．n个 C．C n m D．C m n个2．下列图形中阴影部分构成的集合是凸集的是 A3．在下列线性规划问题的基本解中，属于基可行解的是 BA．(一1，0，O)T B．(1，0，3，0)T C．(一4，0，0，3)T D．(0，一1，0，5)T7．关于线性规划模型的可行域，下面_D_的叙述正确。
A．可行域内必有无穷多个点B．可行域必有界C．可行域内必然包括原点D．可行域必是凸的8．下列关于可行解，基本解，基可行解的说法错误的是_B__.A．可行解中包含基可行解 B．可行解与基本解之间无交集C．线性规划问题有可行解必有基可行解 D．满足非负约束条件的基本解为基可行解9.线性规划问题有可行解，则 AA 必有基可行解B 必有唯一最优解C 无基可行解 D无唯一最优解10.为化为标准形式而引入的松弛变量在目标函数中的系数应为 AA 0B 1C 2D 311.若线性规划问题没有可行解，可行解集是空集，则此问题 BA 没有无穷多最优解B 没有最优解C 有无界解D 无有界解三、多选题1．在线性规划问题的标准形式中，不可能存在的变量是D .A．可控变量B．松驰变量c．剩余变量D．人工变量2．下列选项中符合线性规划模型标准形式要求的有BCDA．目标函数求极小值B．右端常数非负C．变量非负D．约束条件为等式E．约束条件为“≤”的不等式3．某线性规划问题，n个变量，m个约束方程，系数矩阵的秩为m(m<n)则下列说法正确的是ABDE。
运筹学大M法运筹学大M法是一种经典的运筹学方法，在数学建模中被广泛应用。
它的全称是Mixed Integer Linear Programming，即混合整数线性规划，主要解决的是有约束条件下的最优化问题。
运筹学大M法使用了约束条件、决策变量和目标函数三个要素，可以用数学形式进行表示和求解。
假设我们有一组决策变量x1,x2,...,xn，它们需要满足一些约束条件，同时要最大化或最小化目标函数f(x1,x2,...,xn)。
在大M法中，我们将相应的约束条件用等式或不等式进行表示：等式约束条件：a1*x1 + a2*x2 + ... + an*xn = b目标函数：max[f(x1,x2,...,xn)] 或 min[f(x1,x2,...,xn)]在这里，a1,a2,...,an，c1,c2,...,cn和b,d都是确定的常数。
同时，决策变量xi也可以是整数或者二进制变量。
为了求解这个最优化问题，我们需要首先将不等式约束式转化为等式形式。
在这个过程中，我们需要加入一些松弛变量（也叫做slack变量）来确保约束条件可以满足。
假设第i个不等式为：然后我们将这个不等式转化成等式形式：其中，s1是松弛变量。
类似地，我们可以将每个不等式约束条件都转化成等式形式。
在这个过程中，我们需要加入一些约束条件来限制决策变量xi的取值。
如果xi可以为任意实数，那么我们不需要这些额外的约束条件。
但是，如果xi是整数或者二进制变量，我们需要加入一些约束条件来限制它们的取值范围。
为了限制整数变量xi的取值范围，我们通常会引入两个新的变量：yi和zi。
yi表示xi是否等于下限值，zi表示xi是否等于上限值。
我们可以通过以下约束条件来实现这一点：xi >= li*yi其中，li是xi的下限，ui是xi的上限。
因此，如果yi=1，那么xi的取值就是li；如果zi=1，那么xi的取值就是ui。
如果既不是yi=1，也不是zi=1，那么xi就可以取任意整数值。
第二章线性规划的基本概念一、填空题1．线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。
2．图解法适用于含有两个变量的线性规划问题。
3．线性规划问题的可行解是指满足所有约束条件的解。
4．在线性规划问题的基本解中，所有的非基变量等于零。
5．在线性规划问题中，基可行解的非零分量所对应的列向量线性无关6．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。
7．线性规划问题有可行解，则必有基可行解。
8．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即可得到最优解。
9．满足非负条件的基本解称为基本可行解。
10．在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。
11．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。
12．线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。
13．线性规划问题可分为目标函数求极大值和极小_值两类。
14．线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。
15．线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解16．在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上的一切点都是最优解。
17．求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。
18.如果某个约束条件是“≤”情形，若化为标准形式，需要引入一松弛变量。
19.如果某个变量X j为自由变量，则应引进两个非负变量X j′,X j〞,同时令X j＝X j′－X j。
20.表达线性规划的简式中目标函数为max(min)Z=∑c ij x ij。
21..(2.1 P5))线性规划一般表达式中，a ij表示该元素位置在i行j列。
二、单选题1．如果一个线性规划问题有n个变量，m个约束方程(m<n)，系数矩阵的数为m，则基可行解的个数最为_C_。
运筹学复习题线性规划的基本概念一、填空题1．线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。
2．图解法适用于含有两个变量的线性规划问题。
3．线性规划问题的可行解是指满足所有约束条件的解。
4．在线性规划问题的基本解中，所有的非基变量等于零。
5．在线性规划问题中，基可行解的非零分量所对应的列向量线性无关6．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。
7．线性规划问题有可行解，则必有基可行解。
8．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即可得到最优解。
9．满足非负条件的基本解称为基本可行解。
10．在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。
11．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。
12．线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。
13．线性规划问题可分为目标函数求极大值和极小_值两类。
14．线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。
二、单选题1．如果一个线性规划问题有n个变量，m个约束方程(m<n)，系数矩阵的数为m，则基可行解的个数最多为_C_。
A．m个 B．n个 C．C n m D．C m n个2．下列图形中阴影部分构成的集合是凸集的是 A3．在下列线性规划问题的基本解中，属于基可行解的是 BA．(一1，0，O)T B．(1，0，3，0)T C．(一4，0，0，3)T D．(0，一1，0，5)T7．关于线性规划模型的可行域，下面_D_的叙述正确。
A．可行域内必有无穷多个点B．可行域必有界C．可行域内必然包括原点D．可行域必是凸的8．下列关于可行解，基本解，基可行解的说法错误的是_B__.A．可行解中包含基可行解 B．可行解与基本解之间无交集C．线性规划问题有可行解必有基可行解 D．满足非负约束条件的基本解为基可行解9.线性规划问题有可行解，则 AA 必有基可行解B 必有唯一最优解C 无基可行解 D无唯一最优解10.为化为标准形式而引入的松弛变量在目标函数中的系数应为 AA 0B 1C 2D 311.若线性规划问题没有可行解，可行解集是空集，则此问题 BA 没有无穷多最优解B 没有最优解C 有无界解D 无有界解三、多选题1．在线性规划问题的标准形式中，不可能存在的变量是D .A．可控变量B．松驰变量c．剩余变量D．人工变量2．下列选项中符合线性规划模型标准形式要求的有BCDA．目标函数求极小值B．右端常数非负C．变量非负D．约束条件为等式E．约束条件为“≤”的不等式3．某线性规划问题，n个变量，m个约束方程，系数矩阵的秩为m(m<n)则下列说法正确的是ABDE。
%运用大M法计算线性规划的最大值，计算之前先化成标准型，其中z中存放线性规划的最大值
%x中用于存放解，c为价值列向量，b为资源列向量
function [z,x]=DM2(A,c,b)
M=10000;k=1;flag=1;%设M为1000000,flag用于表示解的类型
[m,n]=size(A);%计算系数矩阵的行数和列数
c1=-M*ones(1,m);
c=[c;c1'];%计算此时的Cj
E=eye(m);
A=[A,E];%初始单纯形表
B=n+1:n+m;%B中存基变量的下标
CB=c1;%CB存放基变量前的系数
sigma=c';
for i=1:m
sigma=sigma+M*A(i,:);%计算初始单纯形表中的检验数sigma
end
D=find(sigma>0);
le=length(D);%循环的判断条件当存在sigma<=0时循环终止
while le
Max=max(sigma);
for i=1:n+m %寻找换入变量
if Max==sigma(i)
k=i; %k中用于存放换入变量的下标
end
end
j=1;
for i=1:m %寻找换出变量
if A(i,k)>0
theta(j)=b(i)/A(i,k); %计算theta的值
j=j+1;
else theta(j)=inf; %当A(i,k)<=0时theta取无穷大
j=j+1;
end
end
Q=min(theta);
for i=1:m
if theta(i)==Q
l=i; %l中用于存放换出变量的下标
end
end
B(l)=k; %更新基变量
CB(l)=c(k); %更新基变量前的系数
%更新单纯形表
b(l)=b(l)/A(l,k);
A(l,:)=A(l,:)/A(l,k);
for i=1:m
if i~=l
b(i)=b(i)-b(l)*A(i,k);
A(i,:)=A(i,:)-A(l,:)*A(i,k);
end
end
%更新单纯形表完毕
sigma=c';
for i=1:m
if c(B(i))~=0
sigma=sigma-c(B(i))*A(i,:); %重新计算检验数sigma end
end
D=find(sigma>0); %判断sigma中是否有大于0的数
le=length(D);
if le %判断是否为无界解
for i=1:n+m
if sigma(i)>0 %对任一sigma>0有pj<=0则为无界解
if A(:,i)<=0
flag=0; %flag=0表示线性规划有无界解
end
end
end
end
if flag==0 %如果flag=0则跳出循环
break;
end
end %循环到此终止
sigma1=sigma;
for i=1:m %判断某非基变量检验数为0则有无穷多最优解sigma1(B(i))=1;
end
for i=1:n+m
if sigma1(i)==0
flag=-1;
end
end
for i=n+1:n+m %判断线性规划是否无可行解
for j=1:m
if B(j)==i %检验基变量中是否有非0的人工变量
flag=2;
end
end
end
if flag==2 %flag=2则表明线性规划无可行解disp('无可行解');
z={};x={};
end
if flag==0 %flag=0则表明线性规划有无界解input('无界解');
z={};x={};
end
if flag==-1 %flag=-1则表明线性规划有无穷多最优解disp('无穷多最优解');
disp('一个最优解是'); %输出一个最优解
z=CB*b;
x=zeros(1,n);
for i=1:m
x(B(i))=b(i);
end
end
if flag==1 %flag=1则表明线性规划有最优解disp('有唯一最优解');
z=CB*b;
x=zeros(1,n);
for i=1:m
x(B(i))=b(i);
end
end。
