下载文档原格式
1、在使用单纯形法求解线性规划问题时，初始基本可行解通常通过以下哪种方法获得？A. 两阶段法B. 高斯消元法C. 矩阵求逆D. 逐次逼近法（答案）A2、在单纯形表的迭代过程中，当所有检验数均非负时，说明当前解是？A. 无界解B. 无解C. 最优解D. 可行解但非最优（答案）C3、单纯形法中，选择进入基的变量时，通常选择检验数最小的变量，这是？A. 错误的做法B. 正确的做法，但仅当目标函数求最大值时C. 正确的做法，但仅当目标函数求最小值时D. 无论目标函数求最大还是最小，都是正确的做法（答案）B（假设题目中指的是选择绝对值最大的负检验数对应的变量进入基，若求最小值则选择正检验数）4、在单纯形迭代过程中，若出现某个基变量的值为零，而该变量在目标函数中的系数（即检验数）为正，则？A. 该问题无界B. 应立即停止迭代，因为当前解不可行C. 应将该变量从基中换出D. 这种情况不可能发生（答案）C5、单纯形法中，退出基的变量选择通常基于？A. 检验数的大小B. 基变量在约束条件中的系数比值（即比值检验）C. 目标函数中的系数D. 变量的下界或上界（答案）B6、在单纯形迭代过程中，若所有基变量的检验数均为零，则？A. 达到了最优解，且可能存在多个最优解B. 达到了最优解，且唯一C. 问题无解D. 需要进行人工变量调整（答案）A7、单纯形法中，若某个迭代步骤中发现无法找到符合条件的进入基变量（即所有检验数均非负），则？A. 当前解即为最优解B. 问题无解C. 需要引入人工变量继续迭代D. 应检查初始基本可行解的正确性（答案）A8、在构建初始单纯形表时，若目标函数为求最小化，则检验数应如何计算？A. 检验数= 目标函数系数- 约束条件右侧常数与基变量系数的乘积之和B. 检验数= 目标函数系数+ 约束条件右侧常数与基变量系数的乘积之和的相反数C. 检验数= 目标函数系数直接作为检验数D. 检验数= 约束条件左侧系数与目标函数系数的比值（答案）B（简化描述，实际计算中需考虑基变量的当前值和目标函数系数）9、单纯形法中，当某个基变量的值为负时，说明？A. 当前解不可行B. 当前解可能是最优解，但需进一步验证C. 应立即将该变量从基中换出D. 这种情况在正确执行单纯形法时不可能发生（答案）D（在正确执行时，基变量应始终非负）10、在单纯形迭代过程中，若发现某个非基变量的检验数为正，且该变量对应的约束条件为“≤”类型，则？A. 该变量应被选为进入基的变量B. 该变量不能进入基，因为其检验数为正C. 需要检查该变量的上界是否满足约束D. 该问题可能无解（答案）A（在求最大化问题时，正检验数对应的非基变量是潜在的进入基候选）。
单纯形法的计算题
单纯形法是一种求解线性规划问题的数学方法。
下面是一道使用单纯形法求解的线性规划问题的例子：
求最大化目标函数z = -2x1 + 3x2，
约束条件：
1. x1 + x2 <= 4
2. 3x1 + 4x2 <= 12
3. x1, x2 >= 0
用单纯形法求解此问题，需要进行以下步骤：
1. 建立初始单纯形表格：根据约束条件，我们可以确定初始单纯形表格的基变量和非基变量。
2. 计算目标函数的系数和：根据目标函数的系数，我们可以计算出目标函数的系数和。
3. 检查退出条件：如果目标函数的系数和大于零，则无法找到可行解；如果目标函数的系数和小于等于零，则已经找到最优解。
4. 迭代计算：如果未达到最优解，需要继续迭代计算，更新单纯形表格，直到找到最优解为止。
5. 输出结果：最终的单纯形表格中，最优解对应的基变量和非基变量的值即为所求的最优解。
具体到这个例子中，可以使用线性规划软件包或编程语言实现单纯形法来求解。
通过输入约束条件和目标函数，可以得到最优解。
四、把下列线性规划问题化成标准形式：2、minZ=2x1-x2+2x3五、按各题要求。
建立线性规划数学模型1、某工厂生产A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示：根据客户订货，三种产品的最低月需要量分别为200，250和100件，最大月销售量分别为250，280和120件。
月销售分别为250，280和120件。
问如何安排生产计划，使总利润最大。
2、某建筑工地有一批长度为10米的相同型号的钢筋，今要截成长度为3米的钢筋90根，长度为4米的钢筋60根，问怎样下料，才能使所使用的原材料最省?某运输公司在春运期间需要24小时昼夜加班工作，需要的人员数量如下表所示： 起运时间 服务员数 2—6 6—10 10一14 14—18 18—22 22—24 8 10 7 12 4每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少?五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相当于图解法可行域中的哪一个顶点。
六、用单纯形法求解下列线性规划问题：七、用大M法求解下列线性规划问题。
并指出问题的解属于哪一类。
八、下表为用单纯形法计算时某一步的表格。
已知该线性规划的目标函数为maxZ=5x1+3x2，约束形式为“≤”，X3，X4为松驰变量．表中解代入目标函数后得Z=10XlX2 X3 X4 —10 b-1 f g X3 2 C O 1 1／5 Xlade1(1)求表中a ～g 的值 (2)表中给出的解是否为最优解?（1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=－5 （2） 表中给出的解为最优解 第四章 线性规划的对偶理论 五、写出下列线性规划问题的对偶问题 1．minZ=2x1+2x2+4x3六、已知线性规划问题应用对偶理论证明该问题最优解的目标函数值不大于25七、已知线性规划问题maxZ=2x1+x2+5x3+6x4其对偶问题的最优解为Yl﹡=4，Y2﹡=1，试应用对偶问题的性质求原问题的最优解。
单纯形法原理及例题
单纯形法原理：
单纯形法是求解线性规划问题的一种数学方法，它是由美国数学家卢克·单纯形于1947年发明的。
用单纯形法求解线性规划的过程，往往利用线性规划的对偶形式，将原问题变换为无约束极大化问题，逐步把极大化问题转换为标准型问题，最后利用单纯形法的搜索方法求解满足所有约束条件的最优解。
例题：
问题：求解最小化目标函数z=2x1+x2的线性规划问题，约束条件如下：
x1+2x2≥3
3x1+x2≥6
x1,x2≥0
解：将上述线性规划问题转换为无约束极大化问题，可得：
极大化问题：
Max z=-2x1-x2
s.t. x1+2x2≤3
3x1+x2≤6
x1,x2≥0
将极大化问题转换为标准型问题，可得：
Max z=-2x1-x2
s.t. x1+2x2+s1=3
3x1+x2+s2=6
x1,x2,s1,s2≥0
运用单纯形法的搜索方法求解：
令x1=0,x2=0，则可得s1=3,s2=6，即(0,0,3,6)是单纯形的初始解；
令z=-2x1-x2=0，代入约束条件，可得x1=3,x2=3，则可得s1=0,s2=0，即(3,3,0,0)是新的单纯形解。
由于s1=s2=0，说明x1=3,x2=3是线性规划问题的最优解，且最小值为z=2*3+3=9。
单纯形法求解线性规划问题例题线性规划问题（LinearProgrammingProblem,LPP）是指由一系列约束条件和优化目标函数组成的数学最优化模型，它可以用于解决各种单位时间内最高效率的分配问题。
在求解LPP的过程中，单纯形法（Simplex Method）是最主要的优化算法之一。
单纯形法的原理是采用一组基本变量的拿破仑表示法，一步步构造出线性规划问题的最优解。
下面我们来看一个例子：有公司向农户出售两种农药，甲和乙，每瓶甲农药售价3元，每瓶乙农药售价2元，公司每天有200瓶甲农药和150瓶乙农药，问该公司售出多少瓶甲农药和乙农药，能每天获得最大收益？该问题可表示为下述线性规划模型：最大化 $3x_1+2x_2$约束条件：$x_1+x_2le 200$$2x_1+x_2le 150$$x_1,x_2ge 0$由上述模型可知，有两个未知量$x_1$和$x_2$，它们分别代表出售的甲农药和乙农药的瓶数。
单纯形法的基本思想是采用一组基本变量表示未知量，将未知量$x_1$和$x_2$表示为由两个基本变量$y_1$和$y_2$组成的拉格朗日变换系数矩阵形式，即：$x_1+x_2=y_1+y_2$$2x_1+x_2=m(y_1+y_2)$其中，m是一个系数，根据上面的约束条件，m取200/150=4/3，则：$x_1=y_1+frac{1}{3}y_2$$x_2=y_2-frac{1}{3}y_2$由此可以得到该问题的新的线性规划模型：最大化 $3y_1+2(frac{4}{3})y_2$约束条件：$y_1+y_2le 200$$y_2le 150$$y_1,y_2ge 0$可以看出，该问题所构建出来的新的线性规划模型比原来的模型更加容易求解。
我们将建立单纯形表，以便求出最优解。
首先列出单纯形表：$begin{array}{|c|c|c|c|c|c|c|}hline& y_1 & y_2 & S_1 & S_2 & f & b hline1 & 1 & 1 & 1 & 0 & 3 & 200 hline2 & 0 & 1 & 0 & 1 & 4/3 & 150 hlineend{array}$其中，$y_1$和$y_2$是基本变量，$S_1$和$S_2$是可行解系数，$f$是目标函数系数，$b$是右端项。
补全单纯形表例题
单纯形法是线性规划问题的一种求解方法。
在给定的线性规划问题中，我们首先找到一个初始解，然后通过迭代的方式找到最优解。
以下是一个简单的线性规划问题的单纯形法求解过程：
例题：
目标函数：最大化 z = 3x + 4y
约束条件：
1. x + 2y <= 12
2. 2x + y <= 10
3. x, y >= 0
初始单纯形表：
x y z c b
1 0 -
2 -1 30 + 40 4 0
2 0 -1 2 30 + 40
3 0
3 1 0 0 0 0 12
4 2 0 0 0 0 10
迭代步骤：
1. 从最后一行开始，检查是否满足所有约束条件。
发现第3个约束条件不满足，即x+2y>12，说明我们可以增加y的取值以减小x的取值。
2. 将第4列中的y增加1，得到新的单纯形表：
x y z c b
1 0 -
2 -1 30 + 40 4 -4
2 0 -1 2 30 + 40
3 -2
3 1 0 1 0 -2 6
4 2 0 1 0 -1 5
3. 检查新的单纯形表，所有约束条件都满足。
现在我们有了初始解，x=0, y=1。
将这个解代入目标函数得到z=30+41=4。
因此，初始最优解是(x=0, y=1, z=4)。
例 1.用单纯替换法求目标函数()22124(5)(6)1f x x x =-+-+的最小值,设初始点()[]089T x =，()[]11011T x =,()[]2811Tx =0.01ε=。
解：选()[]089T x =，()[]11011T x =,()[]2811Tx =为顶点作初始单纯形，计算各顶点函数值 00()45f f x ==,11()61f f x ==,22()125f f x == 可见最好点0L x x =,最差点2H x x =,次差点1G x x =,求02,x x 的重心3x []301011()()8102n T i H i x x x x x n ==-=+=∑ 求反射点4x 及其函数值4f [][][]4324422810101169()13T T T x x x f f x =-=-===由于40f f <，故需扩张，取2α=的扩张点5x[]534355+2()48()8T x x x x f f x =-===由于54f f <，故以5x 代替2x ，由510x x x 构成新单纯形，进行下一轮循环。
经19次循环，可将目标函数值降低到2110ε-=⨯，接近最小值()165*)(*===f x f f下面按要求分别有以下步骤：红色的部分是输入的部分1.首先输入目标函数f3=inline('4*(x(1)-5)^2+(x(2)-6)^2+1') 回车2.再输入Simplexe2(f3,[8;9],2,0.618,2,2,0.01) 回车[ps：Simplexe2(fhandle,X_0,n,lambda,mu,h,epsiro)% -fhandle 函数句柄（此处为f3）% -X_0 n维初始列向量（需要根据目标函数维数修改，本题为二维，则为二维坐标）% -n 维数(需要根据目标函数维数修改，本题为二维，则n=2)% -lambda 步长压缩系数!=0.5 (0 1)% -mu 步长加大系数>1% -h 单纯形边长(若题中给出步长则需要修改)% -epsiro 精度（若题中给出精度则需要修改）]3.最后输入fminsearch(f3,[0;0]) 回车（这次结果是得到最小值的坐标，第二步得到的结果是精度e下的最小值和其坐标）。
《管理运筹学》第四版第5章单纯形法课后习题解析《管理运筹学》第四版课后习题解析第5章单纯形法1．解：表中a 、c 、e 、f 是可⾏解，f 是基本解，f 是基本可⾏解。
2．解：（1）该线性规划的标准型如下。
max 5x 1＋9x 2＋0s 1+0s 2+0s 3 s.t. 0.5x 1＋x 2＋s 1＝8 x 1＋x 2－s 2＝100.25x 1＋0.5x 2－s 3＝6 x 1，x 2，s 1，s 2，s 3≥0（2）⾄少有两个变量的值取零，因为有三个基变量、两个⾮基变量，⾮基变量取零。
（3）（4，6，0，0，-2）T（4）（0，10，-2，0，-1）T（5）不是。
因为基本可⾏解要求基变量的值全部⾮负。
（6）略 3.解：令333x x x ''-'=，z f -=改为求f max ；将约束条件中的第⼀个⽅程左右两边同时乘以-1，并在第⼆和第三个⽅程中分别引⼊松弛变量5x 和剩余变量6x ，将原线性规划问题化为如下标准型：j x '、j x ''不可能在基变量中同时出现，因为单纯性表⾥⾯j x '、j x ''相应的列向量是相同的，只有符号想法⽽已，这时候选取基向量的时候，同时包含两列会使选取的基矩阵各列线性相关，不满⾜条件。
4．解：（1）表5-10,,,,,, 24423 1863 1334 7234max 654332163321543321433214321≥'''=-''+'--=++''+'-+-=+''+'---++-=x x x x x x x x x x x x x x x x x x x x x x x x x x x f 约束条件：（2）线性规划模型如下。
max 6x 1＋30x 2＋25x 3 s.t. 3x 1＋x 2＋s 1=40 2x 2＋x 3＋s 2=50 2x 1＋x 2-x 3＋s 3＝20 x 1，x 2，x 3，s 1，s 2，s 3 ≥0（3）初始解的基为（s 1，s 2，s 3）T ，初始解为（0，0，0，40，50，20）T，对应的⽬标函数值为0。
单纯形法例题
单纯形法是一种用于解决什么类型问题的算法？
A. 线性规划
B. 非线性规划
C. 整数规划
D. 动态规划
在单纯形法中，基可行解对应的基变量应满足什么条件？
A. 全部为非零
B. 全部为零
C. 部分为零，部分为非零
D. 无特定要求
单纯形表中的一个关键元素是检验数，它用于判断：
A. 当前解是否最优
B. 当前解是否可行
C. 是否需要继续迭代
D. 问题的约束条件是否满足
在单纯形法的迭代过程中，若所有检验数都小于或等于零，则：
A. 当前解为最优解
B. 当前解不是最优解，需要继续迭代
C. 问题无解
D. 问题有无穷多解
单纯形法中选择换入变量的规则是：
A. 选择检验数最大的非基变量
B. 选择检验数最小的非基变量
C. 选择检验数绝对值最大的非基变量
D. 选择任意非基变量
在单纯形法中，若某个基变量的值变为零，则意味着：
A. 该变量退出了基变量集
B. 该变量仍然是基变量
C. 问题出现了无解的情况
D. 需要重新构造初始基可行解
单纯形法迭代过程中，换出变量的选择依据是：
A. 比值规则
B. 最小元素规则
C. 最大元素规则
D. 任意选择规则
当单纯形法中出现两个或更多检验数同时达到最大值时，这意味着：
A. 问题有多个最优解
B. 问题有无穷多最优解
C. 需要进一步分析以确定最优解的情况
D. 问题无解。
习题二2.1 分别用图解法和单纯形法求解下述LP 问题，并指出单纯形法迭代中每一基本可行解跟图解法可行域中哪一极点相互对应。
（1）max z=10x 1+5x 2s.t. 1212123495280,0x x x x x x +≤⎧⎪+≤⎨⎪≥≥⎩(2) max z=2x 1+x 2s.t. 2121212515622450,0x x x x x x x ≤⎧⎪+≤⎪⎨+≤⎪⎪≥≥⎩ 2.2 用单纯形法求解1.7题。
2.3 用单纯形法求解下述LP 问题：（1）max z= x 1+2x 2+3x 3+4x 4s.t. 123412341,,,0x x x x x x x x +++=⎧⎨≥⎩ （2）第一章例4（3）max z= x 1+x 2+x 3+x 4s.t. 12341234123462,,,0x x x x x x x x x x x x +++=⎧⎪-+-=⎨⎪≥⎩（4）min w= x 2-3x 3+2x 5+2x 6s.t. 23413523562412327438100,1,2,...,6j x x x x x x x x x x x j -++=⎧⎪++=⎪⎨-+++=⎪⎪≥=⎩2.4用单纯形法求解下述LP 问题：(1) max z=2x 1+2x 2s.t. 12121210.520,0x x x x x x -≥-⎧⎪-+≤⎨⎪≥≥⎩(2) max z=10x 1+5x 2s.t.121212120,0 x xx xx x-+≥⎧⎪-≥⎨⎪≥≥⎩(3) max z= 5x1+3x2+2x3+4x4s.t.1234123412345810 243210,,,0x x x xx x x xx x x x+++=⎧⎪+++=⎨⎪≥⎩(4) min w= 2x1+3x2+x3s.t.12312123428 326,,0x x xx xx x x++≥⎧⎪+≥⎨⎪≥⎩(5) min w=2 x1+x2-x3-x4s.t.123412341234123422 2367 ,,,0x x x xx x x xx x x xx x x x-+-=⎧⎪+-+=⎪⎨+++=⎪⎪≥⎩(6) max z=10 x1+15x2+12x3s.t.123123123123539 56151525,,0x x xx x xx x xx x x++≤⎧⎪-++≤⎪⎨++≥⎪⎪≥⎩(7) min z= 3x1-4x2+x3-2x4s.t.123434124123412322102105 52320,,0x x x xx xx x xx x x xx x x+++=⎧⎪+≤⎪⎪-+≥-⎨⎪≤+++≤⎪⎪≥⎩2.5 以2.1题之（1）为例，具体说明当目标函数中变量的系数怎样改变时，能够：（1）分别使每个极点成为最优点；（2）使该LP问题有多重最优解。
