图解法和单纯形法求解以下线性规划问题
1.1 图解法解线性规划问题
只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下：
(1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直
角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。
(2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。
(3)画出目标函数等值线，并确定函数增大（或减小）的方向。
(4)可行域中使目标函数达到最优的点即为最优解。
然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。
1.2 单纯形法解线性规划问题
它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。
单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。
单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。
1.3 线性规划问题的标准化
使用单纯形法求解线性规划时，首先要化问题为标准形式
所谓标准形式是指下列形式：
∑==
n
j j j
x c
z 1
max
?????=≥==??∑=),,2,1(0),,1(1n j x m i b x a t s j
n
j i j ij ΛΛ
当实际模型非标准形式时，可以通过以下变换化为标准形式： ①当目标函数为∑==
n
j j j
x c
z 1
min 时，可令Z ′=-Z ，而将其写成为
∑=-='n
j j j x c z 1
min
求得最终解时，再求逆变换Z=-Z ′即可。
②当s ·t ·中存在i n in i i b x a x a x a ≤+++Λ2211形式的约束条件时，可引进变量
??
?≥+++-=++0)
(1
22111n n in i i i n x x a x a x a b x Λ 便写原条件成为
??
?≥=++++++01
12211n i
n n in i i x b x x a x a x a Λ 其中的x n +1称为松驰变量，其作用是化不等式约束为等式约束。
同理，若该约束不是用“≤”号连接，而是用“≥”连接，则可引进松驰变量
??
?≥-+++=++0)(1
22111n i
n in i i n x b x a x a x a x Λ 使原条件写成
??
?≥=-++++0
1111n i
n n in i x b x x a x a Λ
2 单纯形法
2.1 单纯形法的基本原理
单纯形法迭代原理： （1） 确定初始可行解
① 当线性规划问题的所有约束条件均为≤号时，松弛变量对应的系数矩阵即
为单位矩阵，以松弛变量为基变量可确定基可行解。
② 对约束条件含≥号或=号时，可构造人工基，人为产生一个m ×m 单位矩阵
用大M 法或两阶段法获得初始基可行解。
（2） 最优性检验与解的判别（目标函数极大型）
① 当所有变量对应的检验数均非正时，现有的基可行解即为最优解。若存在
某个非基变量的检验数为零时，线性规划问题有无穷多最优解；当所有非基变量的检验数均严格小于零时，线性规划问题具有唯一最优解。 ② 若存在某个非基变量的检验数大于零，而该非基变量对应的系数均非正，
则该线性规划问题具有无界解（无最优解）。
③ 当存在某些非基变量的检验数大于零，需要找一个新的基可行解，基要进
行基变换。
2.1 确定初始可行解
确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定，为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m 个系数列向量恰好构成一个可行基，即Ａ=（ＢＮ），其中Ｂ=（Ｐ1，Ｐ2，…Ｐm ）为基变量x1，x2，…xm 的系数列向量构成的可行基，Ｎ=(Ｐm+1，Pm+2， …Pn)为非基变量xm+1，xm+2， …xn 的系数列向量构成的矩阵。
所以约束方程AX=b 就可以表示为B B N N X AX=(BN)=BX +NX =b X ??
???
用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得：-1-1
B N X =B b-B NX
若令所有非基变量N X =0，则基变量-1
B X =B b
由此可得初始的基本可行解1B b X=0-??
???
2.2 最优性检验
假如已求得一个基本可行解1B b X=0-??
???，将这一基本可行解代入目标函数，可求得相
应的目标函数值1-1
B N B B b Z=CX=(
C C )=C B b 0-?? ???
其中B 12m N m+1m+2n C =(c ,c ,c ), C =(c ,c ,c )L L 分别表示基变量和非基变量所对应的价值系数子向量。
要判定-1B Z=C B b 是否已经达到最大值，只需将-1-1
B N X =B b-B NX 代入目标函数，使
目标函数用非基变量表示，即：
B B N N -1-1B B N N B N N N
X Z=CX=(C C )X =C X +C X =C (B b-B NX )+C X ??
?
??
m+1m+2-1-1B N N B m+1,m+1,n n x x
C B b+σX C B b+(σσσ)x ?? ? ?= ? ???
@L M
其中-1
N N B m+1m+1n =C -C B N=(,,)σσσσL 称为非基变量ＸN 的检验向量，它的各个分
量称为检验数。若σN 的每一个检验数均小于等于0，即σN ≤0，那么现在的基本可行解就是最优解。
2.3 解的判别
定理1：最优解判别定理
对于线性规划问题{}
n maxZ=CX,D=X R /AX=b,X 0∈≥，若某个基本可行解所对
应的检验向量-1
N N B =C -C B N 0σ≤，则这个基本可行解就是最优解。
定理2：无穷多最优解判别定理
若1B b X=0-?? ???
是一个基本可行解，所对应的检验向量-1
N N B =C -C B N 0σ≤，其中存在
一个检验数σm+k=0，则线性规划问题有无穷多最优解。
定理3：无最优解判别定理
若1B b X=0-?? ???
是一个基本可行解，有一个检验数m+k 0σ>，但是-1
m+k B P 0≤，则该线
性规划问题无最优解。
2.4 基本可行解的改进
如果现行的基本可行解Ｘ不是最优解，即在检验向量-1
N N B =C -C B N σ中存在正的检验
数，则需在原基本可行解Ｘ的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：
（1）先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值）。
（2）再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。
由此可得一个新的基本可行解，由m+1m+2-1B m+1,m+1,n n x x Z C B b+(σσσ)x ??
?
?= ? ???
L M 可知，这样的变换一定能使目标函数值有所增加。
2.4.1 换入变量的确定-最大增加原则
把基检验数大于0的非基变量定为入基变量。若有两个以上的σj ＞0，则选其中的σj 最大者的非基变量为入基变量。
从最优解判别定理知道，当某个σj ＞0时，非基变量x j 变为基变量不取零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的σj ＞0，则为了使目标函数增加得更大些，一般选其中的σj 最大者的非基变量为入基变量。
2.4.2 换出变量的确定-最小比值原则
把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。
即若
lk l
ik ik i k a b
a a
b x =??????>=0|min
则应令xl 出基。其中bi 是目前解的基变量取值，aik 是进基变量xk 所在列的各个系数分量，要求仅对正分量做比，（这由前述作法可知，若aik ≤0，则对应的xi 不会因xk 的增加减值而成为出基变量）。
2.5 表格单纯形法
在单纯形法的求解过程中，有下列重要指标：
（1）每一个基本可行解的检验向量-1
N N B σ=C -C B N ，根据检验向量可以确定所求得
的基本可行解是否为最优解。如果不是最优又可以通过检验向量确定合适的换入变量。
（2）每一个基本可行解所对应的目标函数值 1
B Z=
C B b -，通过目标函数值可以观察
单纯形法的每次迭代是否能使目标函数值有效地增加，直至求得最优目标函数为止。
在单纯形法求解过程中，每一个基本可行解Ｘ都以某个经过初等行变换的约束方程组中的单位矩阵Ι为可行基。
当Ｂ=Ｉ时，Ｂ-1=Ｉ，易知：N N B σ=C -C N ，B Z=C b
可将这些重要结论的计算设计成如下一个简单的表格，即单纯形表来完成：
2.6 大M法
大M法首先将线性规划问题化为标准型。如果约束方程组中包含有一个单位矩阵I，那么已经得到了一个初始可行基。否则在约束方程组的左边加上若干个非负的人工变量，使人工变量对应的系数列向量与其它变量的系数列向量共同构成一个单位矩阵。以单位矩阵为初始基，即可求得一个初始的基本可行解。
为了求得原问题的初始基本可行解，必须尽快通过迭代过程把人工变量从基变量中替换出来成为非基变量。为此可以在目标函数中赋予人工变量一个绝对值很大的负系数-Ｍ。这样只要基变量中还存在人工变量，目标函数就不可能实现极大化。
以后的计算与单纯形表解法相同，Ｍ只需认定是一个很大的正数即可。假如在单纯形最优表的基变量中还包含人工变量，则说明原问题无可行解。否则最优解中剔除人工变量的剩余部分即为原问题的初始基本可行解。
2.7 单纯形法程序设计
完整的单纯形法的计算程序设计框图如下所示：
图1 单纯形法程序框图
3 应用实例 3.1 有最优解问题
例1 求如下方程的最优解
123451234
123
512345
maxZ=5x 2x 3x x x x 2x 2x x 83x 4x x x 7 x ,x ,x ,x ,x 0++-++++=??
+++=??≥?
在命令行输入：
>> A=[1 2 2 1 0;3 4 1 0 1];b=[8;7];c=[5 2 3 -1 1]; >> simplemethod(A,b,c); 即可得出结果： X =
1.2000 0 3.4000 0 0 0 0 最大值为： z = 16.2000 迭代次数： i = 4
程序结果与例题结果一致。 例2 求解下述线性规划问题
1212121234
maxZ=3x +2x x +x 40
2x +x 60x ,x ,x ,x 0≤??
≤??≥? 在命令窗口输入：
>> A=[1 1;2 1];b=[40;60];c=[3 2]; >> simplemethod(A,b,c); 即可得到结果：
已得到最优解： X =
20 20 0 0 最大值为： z = 100 迭代次数： i = 4
程序结果与例题结果一致。
例3 利用大M 法求解下述线性规划问题
121212212maxZ=-x +2x x x 2 -x x 1 x 3 x ,x 0
+≥??+≥??
≤??>=? 在命令窗口输入：
>> A=[1 1;-1 1;0 1];b=[2;1;3];c=[-1 2];sign=[1 1 -1]; >> simplemethod(A,b,c,sign); 结果如下： 已得到最优解： X =
0 3 1 2 0 0 0 最大值为： z = 6 迭代次数： i = 6
与例题结果一致。
3.2 无可行解问题
通过大Ｍ法或两阶段法求初始的基本可行解。但是如果在大Ｍ法的最优单纯形表的基变量中仍含有人工变量，人工变量的值不能取零，说明了原线性规划的数学模型的约束条件出现了相互矛盾的约束方程，此时线性规划问题也无最优解。
例4 利用大M 法求解下述线性规划问题
1231231323123minZ=3x +2x +x x x x 6
x -x 4 x -x 3x ,x ,x 0
++≤??≥??
≥??≥?
在命令窗口输入：
>> A=[1 1 1;1 0 -1;0 1 -1];b=[6;4;3];c=[-3 -2 -1];sign=[-1 1 1]; >> simplemethod(A,b,c,sign); 结果输出“此问题无可行解”。
3.3 无最优解问题
无最优解则是指线性规划问题存在可行解，但是可行解的目标函数达不到最优值，即目标函数在可行域内可以趋于无穷大（或者无穷小）。无最优解也称为有限最优解，或无界解。
判别方法：无最优解判别定理
在求解极大化的线性规划问题过程中，若某单纯形表的检验行存在某个大于零的检验数，但是该检验数所对应的非基变量的系数列向量的全部系数都为负数或零，则该线性规划问题无最优解。
例5求解下述线性规划问题
12121212
max 1
326,0Z x x x x x x x x =+-≤??
-+≤??≥? 在命令窗口输入：
>> A=[1 -1;-3 2];b=[1;6];c=[1 1]; >> simplemethod(A,b,c);
结果输出“此问题无最优解或有无界解”。
4 总结
本文程序虽能解决简单线性规划问题，但对于存在退化解问题却不能做出解答。还有些实际问题会做出错误解答，因此还需进一步改进。
通过本次学习单纯形法，我对单纯形法中的基本概念如基变量、非基变量、基向量、非基向量、可行基以及基本可行解等概念有了初步了解。在理解了单纯形法的解题步骤的基础上，编写了一个求解简单线性规划问题的单纯形法程序，更加深化了单纯形法的理解。
上机实验报告 一、实验目的和要求 1、目的： ●掌握单纯形算法的计算步骤，并能熟练使用该方法求解线性规划问题。 ●了解算法→程序实现的过程和方法。 2、要求： ●使用熟悉的编程语言编制单纯形算法的程序。 ●独立编程，完成实验，撰写实验报告并总结。 二、实验内容和结果 1、单纯形算法的步骤及程序流程图。 （1）、算法步骤
（2）、程序图 各段代码功能描述： （1）、定义程序中使用的变量 #include
float b[m]; /*用于存储常约束条件中的常数*/ float CB[m]; /*用于存储基变量的系数*/ float seta[m]; /*存放出基与入基的变化情况*/ float delta[n]; /*存储检验数矩阵*/ float x[n]; /*存储决策变量*/ int num[m]; /*用于存放出基与进基变量的情况*/ float ZB=0; /*记录目标函数值*/ （2）、定义程序中使用的函数 void input(); void print(); int danchunxing1(); int danchunxing2(int a); void danchunxing3(int a,int b); (3)、确定入基变量，对于所有校验数均小于等于0，则当前解为最优解。 int danchunxing1() { int i,k=0; int flag=0; float max=0; for(i=0;i 图解法和单纯形法求解以下线性规划问题 1.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直 角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题 它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式 一、用单纯形第Ⅰ阶段和第Ⅱ阶段解下列问题 s.t. 解：1)、将该线性问题转为标准线性问题 一、第一阶段求解初始可行点 2)、引入人工变量修改约束集合 取人工变量为状态变量，问题变量和松弛变量为决策变量，得到如下单纯形表，并是所有决策变量的值为零，得到人工变量的非负值。 2 -2 -1 1 2 1 1 -1 -1 1 2 -1 -2 1 2 5 -2 -4 1 -1 1 5 0 0 0 0 0 3)、对上述单纯形表进行计算，是目标函数进一步减小，选为要改变的决策变量，计算改变的限值。 2 -2 -1 1 2 1 1 1 -1 -1 1 0 2 -1 -2 1 2 0 5 -2 -4 1 -1 1 5 1 0 0 0 0 0 0 1 0 0 0 4)、由于，为人工变量，当其到达零值时，将其从问题中拿掉保证其值不会再变。同时将以改变的决策变量转换为状态变量。增加的值使目标函数值更小。 1 -3 1 1 1 0 1 1 -1 1 1 -3 1 1 1 0 0 0 0 0 0 0 0 5）使所有人工变量为零的问题变量的值记为所求目标函数的初始可行点，本例为， 二、第二阶段用单纯形法求解最优解 -2 2 1 0 1 1 -1 0 -2 1 2 1 5 1 3 要使目标函数继续减小，需要减小或的值，由以上计算，已经有两个松弛变量为零，因此或不能再减小了，故该初始可行点即为最优解。 2、求解问题 s.t. 如果目标函数变成，确定使原解仍保持最优的c值范围，并把目标函数最 大值变达成c的函数。 解：先采用单纯形法求解最优解，再对保持最优解时C值的范围进行讨论。 1）将问题华为标准线性问题 s.t. 2）用单纯形表表示约束条件，同时在不引入人工变量的前提下，取松弛变量得初始值为零值，求解初始解和最优解 10 -1 -1 -1 10 -20 1 5 1 -20 -2 -1 -1 0 0 0 0 要使目标函数继续减小，可以增大，增大的限值是10。 10 -1 -1 -1 10 0 -20 1 5 1 -20 -10 -2 -1 -1 0 -20 0 0 0 10 0 0 3）转轴。将为零的松弛变量和决策变量交换进行转轴 10 -1 -1 -1 10 -10 4 0 -1 -10 0 -20 1 1 2 -20 运筹学教程（胡运权主编，清华第4版）部分习题答案（第一章）1.1 （1）无穷多解：α (6/5, 1/5) + (1- α) (3/2, 0)，α∈ [0,1]。 （2）无可行解； （3）x* = (10,6)，z* = 16； （4）最优解无界。 1.2 （1）max z’ = 3x1 - 4x2 + 2x3 - 5x’4 + 5x’’4 s.t. –4x1 + x2 – 2x3 + x’4– x’’4 = 2 x1 + x2 – x3 + 2x’4– 2x’’4 + x5 = 14 –2x1 + 3x2 + x3 – x’4+ x’’4– x6 = 2 x1, x2, x3, x’4, x’’4, x5, x6 ≥ 0 （2）max z’ = 2x’1 + 2x2 – 3x’3 + 3x’’3 s.t. x’1 + x2 + x’3 – x’’3 = 4 2x’1 + x2 – x’3 + x’’3 + x4 = 6 x’1, x2, x’3, x’’3, x4, ≥ 0 1.3 （1）基解：(0, 16/3, -7/6, 0, 0, 0)； (0, 10, 0, -7, 0, 0)； (0, 3, 0, 0, 7/2, 0)，是基可行解，z = 3，是最优解； (7/4, -4, 0, 0, 0, 21/4)； (0, 16/3, -7/6, 0, 0, 0)； (0, 0, -5/2, 8, 0, 0)； (1, 0, -1/2, 0, 0, 3)； (0, 0, 0, 3, 5, 0)，是基可行解，z = 0； (5/4, 0, 0, -2, 0, 15/4)； (3/4, 0, 0, 0, 2, 9/4)，是基可行解，z = 9/4； (0, 0, 3/2, 0, 8, 0)，是基可行解，z = 3，是最优解。 （2）基解：(-4, 11/2, 0, 0)； (2/5, 0, 11/5, 0)，是基可行解，z = 43/5； (-1/3, 0, 0, 11/6)； (0, 1/2, 2, 0)，是基可行解，z = 5，是最优解； 使用单纯形法解线性规划问题 要求：目标函数为：123min 3z x x x =-- 约束条件为： 123123 1312321142321,,0 x x x x x x x x x x x -+≤??-++≥?? -+=??≥? 用单纯形法列表求解，写出计算过程。 解： 1） 将线性规划问题标准化如下： 目标函数为：123max max()3f z x x x =-=-++ s.t.： 123412356 1371234567211 42321,,,,,,0 x x x x x x x x x x x x x x x x x x x -++=??-++-+=??-++=??≥? 2） 找出初始基变量，为x 4、x 6、x 7，做出单纯形表如下： 表一：最初的单纯形表 变量 基变量 x 1 x 2 x 3 x 4 x 5 x 6 x 7 b i x 4 1 -2 1 1 0 0 0 11 x 6 -4 1 2 0 -1 1 0 3 x 7 -2 0 1 0 0 0 1 1 -f -3 1 1 3） 换入变量有两种取法，第一种取为x 2，相应的换出变量为x 6，进行第一次迭代。迭代后新的单纯形表为： 表二：第一种换入换出变量取法迭代后的单纯形表 变量 基变量 x 1 x 2 x 3 x 4 x 5 x 6 x 7 b i x 4 -7 5 1 -2 2 3 x2-4120-1103 x7-20100011 -f10-101-10-3 由于x1和x5对应的系数不是0就是负数，所以此时用单纯形法得不到最优解。 表一中也可以把换入变量取为x3，相应的换出变量为x7，进行一次迭代后的单纯形表为： 表三：第二种换入换出变量取法迭代后的单纯形表 变量 基变量x1x2x3x4x5x6x7 b i x43-20100-110 x60100-11-21 x3-20100011 -f-110000-1-1 4）表三中，取换入变量为x2，换出变量为x6，进行第二次迭代。之后的单纯形 表为： 表四：第二次迭代后的单纯形表 变量 基变量x1x2x3x4x5x6x7 b i x43001-22-512 x20100-11-21 x3-20100011 -f-10001-11-2 5）表四中，取换入变量为x7，换出变量为x3，进行第三次迭代。之后的单纯形 表为： 表五：第三次迭代后的单纯形表 变量 基变量x1x2x3x4x5x6x7 b i x4-7051-22017 x2-4120-1103 x7-20100011 -f10-101-10-3可以看出，此时x1，x5对应的系数全部非零即负，故迭代结束，没有最优解。 结论： 综上所述，本线性规划问题，使用单纯形法得不到最优解。 线性规划及单纯形法 一．选择 1. 运筹学应用分析、试验、（C ）的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。 A 统筹 B 量化 C 优化 D 决策 2. 运筹学研究的基本手段是（A ）。 A 建立数学模型 B 进行数学分析 C 进行决策分析 D 建立管理规范 3. 运筹学研究的基本特点是（ C ）。 A 进行系统局部独立分析 B 考虑系统局部优化 C 考虑系统的整体优化 D 进行系统的整体决策 4. 线性规划问题的数学模型包含三个组成要素：决策变量、目标函数、（B ） A 表达式 B 约束条件 C 方程变量 D 价值系数 5. 线性规划问题的基可行解X 对应线性规划问题可行域（凸集）的（ C ） A 边 B 平面 C 顶点 D 内部 6. 目标函数取极小化（Z min ）的线性规划问题可以转化为目标函数取极大化即（C ）的线性规划问题求解 A Z min B )min(Z - C )max(Z - D Z max - 7. 标准形式的线性规划问题，最优解（C ）是可行解 A 一定 B 一定不 C 不一定 D 无法确定 8. 在线性规划问题中，称满足所有约束条件方程和非负限制的解为（ C ）。 A 最优解 B 基可行解 C 可行解 D 基解 9. 生产和经营管理中经常提出任何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是所谓的（D ） A 管理问题 B 规划问题 C 决策问题 D 优化问题 10. 在线性规划问题中，图解法适合用于处理变量（ B ）个的线性规划问题 A 1 B 2 C 3 D 4 11. 求解线性规划问题时，解的情况有:唯一最优解、无穷多最优解、（ C ）、无可行解 A 无解B 无基解 C 无界解 D 无基可行解 12. 在用图解法求解的时，找不到满足约束条件的公共范围，这时问题有（D ），其原因是模型本身有错误，约束条件之间相互矛盾，应检查修正。 A 唯一最优解 B 无穷多最优解 C 无界解D 无可行解 13. 线性规划问题的基可行解()T n X X X ,,1 =为基可行解的充要条件是X 的正分量所对 应的系数列向量是（B ） A 线性相关 B 线性独立 C 非线性独立 D 无法判断 14. 线性规划问题进行最优性检验和解的判别时，如果当0≤j σ时，人工变量仍留在基本量中且不为零，（D ） A 唯一最优解 B 无穷多最优解 C 无界解 D 无可行解 15.如果集合C 中任意两个点21,X X 其连线上的所有点也都是集合C 中的点，称C 为（B ） 第一章 线性规划及单纯形法习题 1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。 （1）??? ??≥≥+≥++=0,42266432min 2121212 1x x x x x x x x z (2) ??? ??≥≥+≥++=0,12432 223max 2 121212 1x x x x x x x x (3) ?? ? ??≤≤≤≤≤++=8 3105120 106max 21212 1x x x x x x z (4) ??? ??≥≤+-≥-+=0,2322 265max 1 2212121x x x x x x x x z 2.将下列线性规划问题化成标准形式。 (1)????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43214321432143214321,0,,2321422 245243min x x x x x x x x x x x x x x x x x x x x z (2) ????? ? ?≥≤≥-++-≤-+-=++-+-=无约束 32143213213213 21,0,023*******min x x x x x x x x x x x x x x x x z 3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优解。 (1) ??? ?? ? ?=≥=-=+-+=+++++=)6,,1(0231024893631223min 61432143213 21Λj x x x x x x x x x x x x x x z j (2) ??? ??=≥=+++=+++++-=)4,,1(0102227 4322325min 432143214321Λj x x x x x x x x x x x x x z j 4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。 单纯形法求解线性规划的步骤 1>初始化 将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都就是非负的(否则无解),接下来的m 列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示 2>最优化测试 如果目标行的所有单元格都就是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0 3>确定输入变量 从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列 4>确定分离变量 对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题就是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量与主元行 5>建立下一张表格 将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格与新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0)、把主元列的变量名进行代换,得到新的单纯形表,返回第一步 为求简单 在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式: 1:指定行与列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0); 2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化与处理(本程序所用的实例用的就是这种方法) 程序中主要的函数以及说明 ~SimpleMatrix(); 销毁动态分配的数组、用于很难预先估计矩阵的行与列,所以在程序中才了动态的内存分配、需要重载析构函数bool Is_objectLine_All_Positive(); //判断目标行就是否全部为非负数,最后一列不作考虑 这个函数用来判断就是否已经存在最优解 bool Is_MainCol_All_Negative(int col);//判断主元列就是否全部为负数或零 这个函数用来判断线性规划就是否就是无解的 bool Is_column_all_Positive(int col); //判断col列中就是否全部为正(不包括目标行) 单纯形法求解线性规划的步骤 单纯形法求解线性规划的步骤 1>初始化 将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示 2>最优化测试 如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0 3>确定输入变量 从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列 4>确定分离变量 对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量和主元行 5>建立下一张表格 将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第一步 为求简单 在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式: 1:指定行和列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0); 2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化和处理(本程序所用的实例用的是这种方法) 程序中主要的函数以及说明 ~SimpleMatrix(); 销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需要重载析构函数 bool Is_objectLine_All_Positive(); //判断目标行是否全部为非负数,最后一列不作考虑 这个函数用来判断是否已经存在最优解 bool Is_MainCol_All_Negative(int col);//判断主元列是否全部为负数或零 这个函数用来判断线性规划是否是无解的 bool Is_column_all_Positive(int col); //判断col列中是否全部为正(不包括目标行) %单纯形法matlab程序-ssimplex % 求解标准型线性规划:max c*x; . A*x=b; x>=0 % 本函数中的A是单纯初始表，包括:最后一行是初始的检验数，最后一列是资源向量b % N是初始的基变量的下标 % 输出变量sol是最优解, 其中松弛变量（或剩余变量）可能不为0 % 输出变量val是最优目标值，kk是迭代次数 % 例：max 2*x1+3*x2 % . x1+2*x2<=8 % 4*x1<=16 % 4*x2<=12 % x1,x2>=0 % 加入松驰变量，化为标准型，得到 % A=[1 2 1 0 0 8; % 4 0 0 1 0 16; % 0 4 0 0 1 12; % 2 3 0 0 0 0]; % N=[3 4 5]; % [sol,val,kk]=ssimplex(A,N) % 然后执行 [sol,val,kk]=ssimplex(A,N)就可以了。 function [sol,val,kk]=ssimplex(A,N) [mA,nA]=size(A); kk=0; % 迭代次数 flag=1; while flag kk=kk+1; if A(mA,:)<=0 % 已找到最优解 flag=0; sol=zeros(1,nA-1); for i=1:mA-1 sol(N(i))=A(i,nA); end val=-A(mA,nA); else for i=1:nA-1 if A(mA,i)>0&A(1:mA-1,i)<=0 % 问题有无界解 disp('have infinite solution!'); flag=0; break; end end if flag % 还不是最优表，进行转轴运算 temp=0; for i=1:nA-1 if A(mA,i)>temp temp=A(mA,i); inb=i; % 进基变量的下标 end 使用单纯形法解线性规划 问题 The Standardization Office was revised on the afternoon of December 13, 2020 使用单纯形法解线性规划问题 要求：目标函数为：123min 3z x x x =-- 约束条件为： 123123 1312321142321,,0 x x x x x x x x x x x -+≤??-++≥?? -+=??≥? 用单纯形法列表求解，写出计算过程。 解： 1）将线性规划问题标准化如下： 目标函数为：123max max()3f z x x x =-=-++ .： 1234123561371234567211 42321,,,,,,0x x x x x x x x x x x x x x x x x x x -++=??-++-+=??-++=??≥? 2）找出初始基变量，为x 4、x 6、x 7，做出单纯形表如下： 表一：最初的单纯形表 3） 换入变量有两种取法，第一种取为x 2，相应的换出变量为x 6，进行第一 次迭代。迭代后新的单纯形表为： 表二：第一种换入换出变量取法迭代后的单纯形表 由于x1和x5对应的系数不是0就是负数，所以此时用单纯形法得不到最优解。 表一中也可以把换入变量取为x3，相应的换出变量为x7，进行一次迭代后的单纯形表为： 表三：第二种换入换出变量取法迭代后的单纯形表 4）表三中，取换入变量为x2，换出变量为x6，进行第二次迭代。之后的单纯形表为： 表四：第二次迭代后的单纯形表 5）表四中，取换入变量为x7，换出变量为x3，进行第三次迭代。之后的单纯形表为： 表五：第三次迭代后的单纯形表 单纯形法在线性规划中的应用 摘要 求解线性规划问题，就是在各项资源条件的限制下，如何确定方案，使预期的目标达到最优。本文重点介绍了求解线性规划问题目前最常见的两种方法，图解法和单纯形法。图解法适合于只含两个变量的线性规划问题，文中只做了简单的描述。而单纯形法是求解线性规划问题的通用方法，适合于求解大规模的线性规划问题，本文作了重点描述，对单纯形法中的基本概念如基变量、非基变量、基向量、非基向量、可行基以及基本可行解等概念作了详细的陈述，在此基础上，介绍了线性规划问题的标准化、单纯形法的基本原理、确定初始可行解、最优性检验、解的判别、基本可行解的改进、换入变量的确定-最大增加原则、换出变量的确定-最小比值原则、表格单纯形法、大M法、两阶段法等。 关键词：线性规划图解法单纯形法基变量基向量可行基基本可行解 正文 引言 在生产管理和经济活动中，经常遇到这些问题，如生产计划问题，即如何合理利用有限的人、财、物等资源，以便得到最好的经济效果；材料利用问题，即如何下料使用材最少；配料问题，即在原料供应量的限制下如何获取最大利润；劳动力安排问题，即如何用最少的劳动力来满足工作的需要；运输问题，即如何制定调运方案，使总运费最小；投资问题，即从投资项目中选取方案，使投资回报最大等等。对于这些问题，都能建立相应的线性规划模型。事实上，线性规划就是利用数学为工具，来研究在一定条件下，如何实现目标最优化。 解线性规划问题目前最常见的方法有两种，图解法和单纯形法。单纯形法是求解线性规划问题的通用方法。 1 线性规划问题的求解方法 1.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x 1为横坐标轴，x 2 为纵坐标轴，适当选取单位坐标长度建立平面 坐标直角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，图解法虽然直观、简便，但当变量数多于三个以上时，其实用意义不大。 第二节 线性规划问题的图解法 对一个线性规划问题，建立数学模型之后，面临着如何求解的问题。这里先介绍含有两个未知变量的线性规划问题的图解法，它简单直观。 图解法的步骤： 步骤1：确定可行域。 第1步： 绘制约束等式直线，确定由约束等式直线决定的两个区域中哪个区域对应着由约束条件所定义的正确的不等式。我们通过画出指向正确区域的箭头，来说明这个正确区域。 第2步：确定可行域。 步骤2：画出目标函数的等值线，标出目标值改进的方向。 步骤3：确定最优解。用图示的方式朝着不断改进的目标函数值的方向，移动目标函数的等值线，直到等值线正好接触到可行域的边界。等值线正好接触到可行城边界的接触点对应着线性优化模型的最优解。 例1－3，用图解法求解线性规划问题 12 12121212max 23221228..416412,0 z x x x x x x s t x x x x =++≤??+≤??≤??≤?≥?? 解： 图1－3 （1） 画出线性规划问题的可行域，它是为以O(0,0)、A(0,3)、B(2,3)、C(4,2)、 D(0,4)为顶点的凸5边形，如图1－3。 （2） 画出一条目标函数的等值线12236x x +=，图1－3中红颜色的虚 线。 （3） 目标函数的等值线往上移动时，目标函数值增大（图1－3中红颜 色的实线）。由于问题的解要满足全部约束条件，因此目标函数的 等值线要与可行域有交点。当目标函数的等值线移动到 122314x x +=时，它与可行域只有一个交点，再往上移动时，与 可行域不再有交点。这就是说最优解为：124,2x x ==，最优目标 函数值为14。 例1-3中求解得到问题的最优解是唯一的，但对一般线性规划问题，求解结果还可能出现以下几种情况： （1）唯一最优解（2）多重最优解。 （3）无界解。 （4）无可行解。 这里我们不再举例，请大家自己阅读教材。 当线性规划问题的求解结果出现（3）、（4）两种情况时，一般说明线性规划问题建模有错误。前者缺乏必要的约束条件，后者是有矛盾的约束条件，建模时应注意。 使用单纯形法解线性规划问题 要求：目标函数为：123min 3z x x x =-- 约束条件为： 123123 1312321142321,,0 x x x x x x x x x x x -+≤??-++≥?? -+=??≥? 用单纯形法列表求解，写出计算过程。 解： 1） 将线性规划问题标准化如下： 目标函数为：123max max()3f z x x x =-=-++ s.t.： 123412356 1371234567211 42321,,,,,,0 x x x x x x x x x x x x x x x x x x x -++=??-++-+=??-++=??≥? 2） 找出初始基变量，为x 4、x 6、x 7，做出单纯形表如下： 表一：最初的单纯形表 3） 换入变量有两种取法，第一种取为x 2，相应的换出变量为x 6，进行第一次迭代。迭代后新的单纯形表为： 表二：第一种换入换出变量取法迭代后的单纯形表 由于x1和x5对应的系数不是0就是负数，所以此时用单纯形法得不到最优解。 表一中也可以把换入变量取为x3，相应的换出变量为x7，进行一次迭代后的单纯形表为： 表三：第二种换入换出变量取法迭代后的单纯形表 4）表三中，取换入变量为x2，换出变量为x6，进行第二次迭代。之后的单纯形表为： 表四：第二次迭代后的单纯形表 5）表四中，取换入变量为x7，换出变量为x3，进行第三次迭代。之后的单纯形表为： 表五：第三次迭代后的单纯形表 可以看出，此时x1，x5对应的系数全部非零即负，故迭代结束，没有最优解。 结论： 综上所述，本线性规划问题，使用单纯形法得不到最优解。 第一章 线性规划及单纯形法习题 1.用图解法求解下列线性规划问题,并指出问题具有唯一最优解、无穷最优解还是无可行解。 （1）??? ??≥≥+≥++=0,42266432min 2121212 1x x x x x x x x z (2) ??? ??≥≥+≥++=0,12432 223max 2 121212 1x x x x x x x x (3) ?? ? ??≤≤≤≤≤++=8 3105120 106max 21212 1x x x x x x z (4) ??? ??≥≤+-≥-+=0,2322 265max 1 2212121x x x x x x x x z 2.将下列线性规划问题化成标准形式。 (1)????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43214321432143214321,0,,2321422 245243min x x x x x x x x x x x x x x x x x x x x z (2) ????? ? ?≥≤≥-++-≤-+-=++-+-=无约束 32143213213213 21,0,023*******min x x x x x x x x x x x x x x x x z 3.对下列线性规划问题找出所有基本解，指出哪些是基可行解，并确定最优解。 (1) ??? ?? ? ?=≥=-=+-+=+++++=)6,,1(0231024893631223min 61432143213 21 j x x x x x x x x x x x x x x z j (2) ??? ??=≥=+++=+++++-=)4,,1(0102227 4322325min 432143214321 j x x x x x x x x x x x x x z j 4.分别用图解发法和单纯形法求解下述问题，并对照单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。 目录 一．摘要 (2) 二．实验目的 (2) 三．实验内容 (2) 四．建立数学模型 (3) 五．实验原理 (5) 六．MALTAB程序代码及注释 (7) 七．结果运行测试 (13) 八．心得与感悟 (15) 一．摘要： 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.研究线性约束条件下线性目标函数的极值问题的数学理论和方法,英文缩写LP。 自1946年G.B.Dantizig提出单纯形法以来，它一直是求解线性规划问题的最有效的数学方法之一。单纯形法的理论根据是：线性规划问题的可行域是 n 维向量空间Rn中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。通过引入普通单纯形法，依次迭代并判断，逐步逼近，最后得到最优解。若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 关键字：线性规划，单纯形法，最优值，最优解 二．实验目的： 1.加强学生分析问题能力，锻炼数学建模能力。 2.了解并掌握MATLAB软件中的线性规划问题的编程、求解和分析。 3.利用所学的MALTAB语言，完成对单纯形法问题的编程设计。 三．实验内容： 某商场决定，营业员每周连续工作5天后连续休息2天，轮流休息，据统计，商场每天需要营业员如下：星期一：300，二：300；三：350，四：400，五：480，六：600；日：500； （1）商场人力资源部应如何安排每天上班的人数才能使商场总的营业员最少 （2）若商场可以雇佣临时工，上班时间同正式工，若正式工每天工资80，临时工每天100，问商场是否应雇佣临时工及雇佣多少名？ 线性规划单纯形法matlab解法 %单纯形法matlab程序-ssimplex % 求解标准型线性规划:max c*x; s.t. A*x=b; x>=0 % 本函数中的A是单纯初始表，包括:最后一行是初始的检验数，最后一列是资源向量b % N是初始的基变量的下标 % 输出变量sol是最优解, 其中松弛变量（或剩余变量）可能不为0 % 输出变量val是最优目标值，kk是迭代次数 % 例：max 2*x1+3*x2 % s.t. x1+2*x2<=8 % 4*x1<=16 % 4*x2<=12 % x1,x2>=0 % 加入松驰变量，化为标准型，得到 % A=[1 2 1 0 0 8; % 4 0 0 1 0 16; % 0 4 0 0 1 12; % 2 3 0 0 0 0]; % N=[3 4 5]; % [sol,val,kk]=ssimplex(A,N) % 然后执行 [sol,val,kk]=ssimplex(A,N)就可以了。 function [sol,val,kk]=ssimplex(A,N) [mA,nA]=size(A); kk=0; % 迭代次数 flag=1; while flag kk=kk+1; if A(mA,:)<=0 % 已找到最优解 flag=0; sol=zeros(1,nA-1); for i=1:mA-1 sol(N(i))=A(i,nA); end val=-A(mA,nA); else for i=1:nA-1 if A(mA,i)>0&A(1:mA-1,i)<=0 % 问题有无界解 disp('have infinite solution!'); flag=0; break; end end if flag % 还不是最优表，进行转轴运算 temp=0; for i=1:nA-1 if A(mA,i)>temp temp=A(mA,i); inb=i; % 进基变量的下标图解法和单纯形法求解线性规划问题
最新单纯形法解线性规划问题
16991-运筹学-习题答案选01_线性规划和单纯形法
使用单纯形法解线性规划问题
第1章线性规划及单纯形法
线性规划及单纯形法习题
单纯形法求解线性规划的步骤
单纯形法求解线性规划的步骤
线性规划单纯形法matlab解法
使用单纯形法解线性规划问题
单纯形法在线性规划中的应用
2-线性规划问题的图解法
使用单纯形法解线性规划问题
第一章线性规划及单纯形法习题
用单纯形法求解线性规划问题
线性规划单纯形法matlab解法
相关主题
文本预览