下载文档原格式
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 = 3x1 + 5x2。
约束条件：2x1 + x2 ≤ 10。
x1 + 3x2 ≤ 18。
x1, x2 ≥ 0。
首先，我们将上述问题转化为标准形式。
引入松弛变量，将不等式约束转化为等式约束：2x1 + x2 + x3 = 10。
x1 + 3x2 + x4 = 18。
x1, x2, x3, x4 ≥ 0。
接下来，我们构建初始单纯形表。
表格的第一行为目标函数系数，第一列为基变量。
x1 x2 x3 x4 b.----------------------------------。
Z | -3 -5 0 0 0。
----------------------------------。
x3 | 2 1 1 0 10。
x4 | 1 3 0 1 18。
然后，选择进入变量和离开变量。
进入变量选择目标函数系数最小的负值，即x2。
离开变量选择约束条件中比率最小的变量，即x4。
通过计算比率b/离开变量系数，得到x4的比率为18/3=6。
接下来，进行主元素列变换，使得离开变量的列成为单位向量。
具体步骤如下：1. 将主元素列除以主元素系数，使主元素系数变为1。
2. 将其他列减去相应比率乘以主元素列，使主元素列下的其他元素都变为0。
x1 x2 x3 x4 b.----------------------------------。
Z | 0 -1 0 5 90。
----------------------------------。
x3 | 0 -1 1 0 4。
x2 | 1 3 0 1 18。
然后，更新目标函数行。
将目标函数行减去目标函数系数乘以主元素列，使得目标函数系数下的其他元素都变为0。
x1 x2 x3 x4 b.----------------------------------。
一．单纯性法一．单纯性法1.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 122121212max 25156224..5,0z x x x x x s t x x x x =+£ìï+£ïí+£ïï³î 2.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 12121212max 2322..2210,0z x x x x s t x x x x =+-³-ìï+£íï³î 3.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 1234123412341234max 24564282..2341,,,z x x x x x x x x s t x x x x x x x x =-+-+-+£ìï-+++£íï³î4.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 123123123123123max 2360210..20,,0z x x x x x x x x x s t x x x x x x =-+++£ìï-+£ïí+-£ïï³î 5.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 12312312123max 224..26,,0z x x x x x x s t x x x x x =-++++£ìï+£íï³î6.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 15 分）分） 12121212max 105349..528,0z x x x x s t x x x x =++£ìï+£íï³î7.用单纯形法求解下列线性规划问题（共用单纯形法求解下列线性规划问题（共 16 分）分） 12121212max 254212..3218,0z x x x x s t x x x x =+£ìï£ïí+£ïï³î二．对偶单纯性法二．对偶单纯性法1.灵活运用单纯形法和对偶单纯形法解下列问题（共灵活运用单纯形法和对偶单纯形法解下列问题（共 15 分）分）12121212max 62..33,0z x x x x s t x x x x =++³ìï+£íï³î 2.灵活利用单纯形法和对偶单纯形法求解下列线性规划问题（共灵活利用单纯形法和对偶单纯形法求解下列线性规划问题（共 15 分）分） 121212212max 3510501..4,0z x x x x x x s t x x x =++£ìï+³ïí£ïï³î 3.用对偶单纯形法求解下列线性规划问题（共用对偶单纯形法求解下列线性规划问题（共 15 分）分） 1212121212min 232330210..050z x x x x x x s t x x x x =++£ìï+³ïï-³íï³ïï³î4.灵活运用单纯形法和对偶单纯形法求解下列线性规划问题（共灵活运用单纯形法和对偶单纯形法求解下列线性规划问题（共 15 分）分） 124123412341234min 262335,,,0z x x x x x x x s t x x x x x x x x =+-+++£ìï-+-³íï³î5.运用对偶单纯形法解下列问题（共运用对偶单纯形法解下列问题（共 16 分）分） 12121212max 24..77,0z x x x x s t x x x x =++³ìï+³íï³î6.灵活运用单纯形法和对偶单纯形法解下列问题（共灵活运用单纯形法和对偶单纯形法解下列问题（共 15 分）分） 12121212max 62..33,0z x x x x s t x x x x =++³ìï+£íï³î三．0-1整数规划整数规划1.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共10 分） 12345123451234512345123345max 567893223220..32,,,,,01z x x x x x x x x x x x x x x x s t x x x x x x x x x x x or =++++-++-³ìï+--+³ïí--+++³ï=î 2.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共 10 分） 12312312323123min 4322534433..1,,01z x x x x x x x x x s t x x x x x or =++-+£ì++³ïí+³ïï=î 3.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共 10 分） 1234512345123451234512345max 20402015305437825794625..81021025,,,,01z x x x x x x x x x x x x x x x s t x x x x x x x x x x =++++++++£ìï++++£ïí++++£ïï=î或 4.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共10 分） 12345123451234512345max 2534327546..2420,,,,01z x x x x x x x x x x s t x x x x x x x x x x =-+-+-+-+£ìï-+-+£íï=î或 5.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共10 分） 12341234123412341234min 25344024244..1,,,01z x x x x x x x x x x x x s t x x x x x x x x =+++-+++³ì-+++³ïí+-+³ïï=î或6.7.用隐枚举法解下列0-1型整数规划问题（共型整数规划问题（共10 分） 123451234513451245max 325232473438..116333z x x x x x x x x x x x x x x s t x x x x =+--+++++£ìï+-+£ïí-+-³ï 1231231231223max 3252244..346z x x x x x x x x x s t x x x x =-++-£ìï++£ïï+£íï+£ïï=四.K-T 条件条件1.利用库恩-塔克（K-T ）条件求解以下问题（共）条件求解以下问题（共 15 分）分）22121122121212max ()104446..418,0f X x x x x x x x x s t x x x x =+-+-+£ìï+£íï³î2.利用库恩-塔克（K-T ）条件求解以下非线性规划问题。
单纯形法原理及例题
单纯形法原理：
单纯形法是求解线性规划问题的一种数学方法，它是由美国数学家卢克·单纯形于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。
补全单纯形表例题
单纯形法是线性规划问题的一种求解方法。
在给定的线性规划问题中，我们首先找到一个初始解，然后通过迭代的方式找到最优解。
以下是一个简单的线性规划问题的单纯形法求解过程：
例题：
目标函数：最大化 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)。
单纯形法求解线性规划问题例题
线性规划问题（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 hline
1 & 1 & 1 & 1 & 0 & 3 & 200 hline
2 & 0 & 1 & 0 & 1 & 4/
3 & 150 hline
end{array}$
其中，$y_1$和$y_2$是基本变量，$S_1$和$S_2$是可行解系数，$f$是目标函数系数，$b$是右端项。
从表中可以发现，$y_1$和$y_2$的可行解条件的系数都为：
$S_1=1,S_2=0$，即$y_1+y_2=200$，从而可以推出本题的最优解为$y_1=200,y_2=0$，对应的$x_1=frac{200}{3},x_2=200$，即售出$frac{200}{3}$瓶甲农药和200瓶乙农药，公司每天可获得最大收益$3timesfrac{200}{3}+2times200=800$。
以上即为通过单纯形法求解线性规划问题的一个小例子，通过该例子的分析可以看出，单纯形法是一种非常有效的解决线性规划问题的方法，它通过将未知量用基本变量的形式表示，可以极大减少求解时间，十分适用于计算机求解线性规划问题。
因此，可见单纯形法在求解线性规划问题时非常有效，它不但可以加快求解速度，而且还可以避免求解过程中出现的不符合实际情况的解。
通过线性规划，也可以求解复杂的优化问题，因此扩展应用单纯形法的范围也很广泛，有利于更好地运用当今的计算机技术解决实际问题。
总之，单纯形法用于求解线性规划问题十分有效，它在求解速度、实用性以及扩展性上都得到了非常大的改进，可谓是一项十分重要的数学优化算法。
