线性规划单纯形法(例
题)
《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》
???
??≥=++=+++++=??
?
??≥≤+≤++=0,,,24
261553).(002max ,,0,24
261553).(2max 14.1843214213
214
321432121212
1x x x x x x x x x x t s x x x x z x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】
（页【为初始基变量，选择43,x x
)1000(00)0010(01
)2050(12)6030(24321=?+?-==?+?-==?+?-==?+?-=σσσσ
为出基变量。为进基变量，所以选择41x x
3
/1)6/122/10(00
)0210(03
/1)3/1240(10
)1200(24321-=?+-?-==?+?-==?+?-==?+?-=σσσσ
为出基变量。为进基变量，所以选择32x x
24
/724/528/11012/112/124/1100
021110120124321-=?+-?-=-=-?+?-==?+?-==?+?-=）（）（）（）（σσσσ
433
4341522max ,)4
3,415(
),(2112=
+?=+===x x z x x X T
T 故有：所以，最优解为
单纯形法演算 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 无穷 0 4x 24 6 2 0 1 0 4 0 5x 5 1 1 0 0 1 5 j j z c -（检验数） 2 1 首先列出表格，先确定正检验数最大值所在列为主列，然后用b 除以主列上对应的同行数字。除出来所得值最小的那一行为主行，根据主行和主列可以确定主元（交点）。接着把主元化为1并把X4换成X1. ??? ??? ?≥=++=++=+++++=0,,524261550002max 5152 14213 25 4321x x x x x x x x x x x x x x x z ??????? ≥≤+≤+≤+=0 ,5 24261552max 21212122 1x x x x x x x x x z
j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5 1 1 0 0 1 j j z c - 2 1 这时进行初等行列变换，把主列换单位向量，主元为1。也就是X5所在行减去X1所在行。并且重新计算检验数。 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5-4 1-1=0 1-2/6 =4/6 0-1/6=-1/6 1 j j z c - 2-2*1-0*0-0*1=0 1-0*5-2*2/6-0*4/6=1/3 0-0*0-2*1/6-0*-1/6=-1/3 再次确定主元。为4/6。然后把X5换成X2。并且把主元化成1。
科学出版社《运筹学》教材 第一章引言 第二章线性规划，姜林 第三章对偶规划，姜林 第四章运输问题，姜林 第五章整数规划，姜林 第六章非线性规划，姜林 第七章动态规划，姜林 第八章多目标规划，姜林 第九章图与网络分析，熊贵武 第十章排队论，熊贵武 第十一章库存论，王勇 第十二章完全信息博弈，王勇 第十三章不完全信息博弈，王勇 第十四章决策论与影响图 第十五章运筹学模型的计算机求解 成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问 如何选择食品才能在满足营养的前提下使购买食品的费用最小？ 食品名称热量(kcal) 蛋白质(g) 钙（mg）价格（元）猪肉1000 50 400 14 鸡蛋800 60 200 6
大米900 20 300 3 白菜200 10 500 2 营养需求量 2000 55 800 解：设需猪肉、鸡蛋、大米和白菜各需 x1,x2,x3,x4斤。则热量的需求量为： 2000 20090080010004 3 2 1 x x x x 蛋白质 某工厂要做100套钢架，每套有长 3.5米、2.8米和2根2.4米的圆钢组成（如右图）已知原 料长12.3米，问应如何下料使需用的原材料最省。 解：假设从每根 12.3米的原材料上截取 3.5米、2.8米和2根2.4 米，则每根原材料需浪费 1.2米，做100套需浪费材料 120米，现 采用套裁的方法。 方案一二三四五六3.5 2.8 2.4 0 0 5 0 4 0 1 2 1 1 3 0 2 0 2 2 1 1 合计剩余 12 0.3 11.2 1.1 11.5 0.8 11.9 0.4 11.8 0.5 12.2 0.1 现在假设每种方案各下料x i （i=1、2、3、4、5、6），则可列出方程： minZ=0.3x 1+1.1x 2+0.8x 3+0.4x 4+0.5x 5+0.1x 6 约束条件： x 3+x 4+2x 5+2x 6=100 4x 2+2x 3+3x 4+x 6=100 5x 1+x 3+2x 5+x 6=200 ,,,800 50030020040055 102060503000 2009008001000. .23614min 4 3214 3 2 1 4 32 14 32 14321x x x x x x x x x x x x x x x x t s x x x x z
三、单纯形法的解题步骤 第一步：作单纯形表. ）（1）把原线性规划问题化为标准形式； ）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； ）（3）目标函数非基化； ）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即，则此时线性规划问题已取 得最优解. (2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划 问题无最优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. ，并确定所在列的非基变量为进基变量. （1）找到最大正检验数，设为 （2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号. 主元是最大正检验数 所在列，用常数项与进基变量所对应的列向 量中正分量的比值最小者； 替换出基变量，从而得到新的基变量.也就是主元所在 （3）换基：用进基变量 （4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表； （5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止. 例3 求.
解（1）化标准型：令 ，引进松弛变量 ，其标准型为 求 （2）作单纯形表：在约束方程组系数矩阵中 的系数构成单位矩阵，故取 为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8
（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出 ，, 代入目标函数 , 经整理后，目标函数非基化了. 作单纯形表，并进行换基迭代（见表6.9）. 最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变出基，非基变量进基. 换，基变量
单纯形法求最优解问题 题目（老师布置的那道作业题）：2153m ax x x f +=，其中 ??? ??? ?=≥=++=+=+5,4,3,2,1,0182312245214 231j x x x x x x x x j ，求2153m ax x x f +=的最大值。 这张表是根据题目画的，Cj （行向量）为5432100053m ax x x x x x f ++++=中各个变量的系数，Ci （列向量）为与X B （列向量）相对应的各项的系数，X B 称为基变量（3列，由题目中的方程个数决定），起初的基变量由构造的变量x3、x4、x5组成，b 为对应三个方程等式右边的常数，z j 为Ci 各列与xj 各列乘积的和，如z1=0*1+0*0+0*3=0。i θ为判别将哪个基变量换出的依据，根据c j -z j 为正，要先将x2换入XB 中，关键是判断x3、x4、x5哪个跟x2换，这就要根据各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，如上表可知x2跟x4换，换完之后注意原来x4所对应的列向量为[0 1 0]T ,故要将x2所对应的列向量变换为为[0 1 0]T ，注意b 也要跟着变化，于是得下表.
由上表知c 1-z 1=3>0，故仍需将x1换入XB 中，用各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，结合i θ可知，x1跟x5换，于是得下表。 由上表可知c j -z j 均非正，故5432100053m ax x x x x x f ++++=取最大值时，????? ?? ?????????=00662x ， 对应的最大值36max =f . 系统工程导论知识点整理： 系统是由相互作用和相互依赖的若干组成部分(要素)结合的具有特定功能的有机整体。 系统的特征：整体性、相关性、目的性、环境适应性。 系统的功能是指系统与外部环境相互作用所反映的能力。 结构是功能的内在根据，功能是结构的外在表现。 系统功能的特性：易变性、相关性。 系统工程就是用科学的方法规划和组织人力、物力、财力，通过最优途径的选择，使人们的工作在一定期限内收到最合理、最经济、最有效的效果。 科学的方法：从整体观念出发，通盘筹划，合理安排整体中的每一个局部，以求得整体的最优规划、最优管理和最优控制，使每个局部都服从一个整体目标，力求避免资源的损失和浪费。
线性规划及单纯形法 一．选择 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．什么是线性规划模型，在模型中各系数的经济意义是什么？ 2．线性规划问题的一般形式有何特征？ 3．建立一个实际问题的数学模型一般要几步？ 4．两个变量的线性规划问题的图解法的一般步骤是什么？ 5．求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6．什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7．试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8．试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9．在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10．大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 11．什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 二、判断下列说法是否正确。 1．线性规划问题的最优解一定在可行域的顶点达到。 2．线性规划的可行解集是凸集。 3．如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4．线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。 5．线性规划问题的每一个基本解对应可行域的一个顶点。 6．如果一个线性规划问题有可行解，那么它必有最优解。 7．用单纯形法求解标准形式（求最小值）的线性规划问题时，与 > j σ 对应的变量都 可以被选作换入变量。 8．单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一个基变量的值是负的。 9．单纯形法计算中，选取最大正检验数k σ对应的变量k x作为换入变量，可使目标函数值得到最快的减少。 10．一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1．某公司计划在三年的计划期内，有四个建设项目可以投资：项目Ⅰ从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120% ，每年又可以重新将所获本利纳入投资计划；项目Ⅱ需要在第一年初投资，经过两年可收回本利150% ，又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目Ⅲ需要在第二年年初投资，经过两年可收回本利160% ，但用于该项目的最大投资额不得超过15万元；项目Ⅳ需要在第三年年初投资，年末可收回本利140% ，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2．某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：
单纯形法例题 1、例1、目标函数max z=2 * +3 禹+ 2x2 W 8' 4xi W 16 4x2 W 12 k Ki,财鼻0』 解：首先要将约束条件化为标准形：由此可以看出我们需要加上三个松弛变量, ；汁Hi吃：弋"審得到的标准形式为： max z=2~ +3-+ 0 勺+g +O 5 'xt + 2xj + x] = 8 1 4?i X4 =16 4x；+ 巧=12 11 巾弓^3j 乂4, ^5 $ ? 2 3 0 0 0 C R b *4 0 8 1 2 1 0 0 4 0 16 4 0 0 1 0 - 0 ◎12 0[E(|00 1 3 k - z) 2 3 0 0 0 引」一弋木日lk(i才I) 熙=') (也就是如果与主元素同行，则用现在的值除以主元素即可得到即将要填入的值, 否则，就用现在的值减去与主元素构成矩形的边角上的值的乘积再除以主元素之后 的值。例如：上面的第一行所对应的b值为8-(12*2)/4=2 ,故填入值应该为2。而「 则是由我们根据非基变量的检验数的大小，挑选出最大的那个，作为换入变量，然 后用b的值除以该换入变量所在的列的所有值，得到 约束条件:
由于在检验数中仍然存在大于等于的数，而且, 的坐标中有正分量存在，所以需要继续进行迭代运算。通过观察可以看出主元素为1,换入变量为|勒，换出 由于检验数中存在正数，且P5和P3中有正分量存在，所以需要继续迭代（换入变 此时可以发现检验数中没有大于的数，表明已经得到了最优解，所以最优解是: (4,2,0,0,4 )，故目标函数值z=2*4+2*3=14 2、合理利用线材问题，现在要做100套钢架，每套用长为，，和的钢各一根,
第一章 线性规划及单纯形法习题 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.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直 角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题 它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式
例1 max z=2x1+3x2 （标准形式即所有的变量均为负、所有约束条件为等式、所有的右端项系数非负） a=(2,3) b1=(80,160,120) A2=NULL b2=NULL A3=NULL b3=NULL n.iter=n+2*m maxi=TRUE ● simplex(a=a,A1=A1,b1=b1,maxi=TRUE)： m1=3,m2=0,m3=0 m=3,n=2 a.o=a=(2,3) if(maxi) a=-a(-2,-3) if(m2+m3==0) a=(-2,-3,0,0,0) b=(80,160,120) init=(0,0,0,80,160,120) basic=(3,4,5) eps=1e -10 out1<-simplex1(a=a,A=A,b=b,init=init,basic=basic,eps=eps) ? simplex1(a=a,A=A,b=b,init=init,basic=basic,eps=eps): N=5,M=3 nonbasic=(1,2) if(stage==2) obfun=(-2,-3) it=1 ◆ while(!all(obfun > -eps) && (it <= n.iter))循环 pcol=3 if(stage==2) neg=(1,3) x1+2x2<=80 4x1<=160 4x2<=120 x1，x2>=0 A1= 1 2 4 0 0 4 A= 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 tableau= 80 -1 -2 160 -4 0 120 0 -4 tableau= 80 -1 -2 160 -4 0 120 0 -4 0 -2 -3 转化为标准形式 x1+2x2+x3=80 4x1+x4=160 4x2+x5=120 x1,x2,x3,x4,x5>=0
单纯形法例题 1、例1、目标函数 max z=2+3 约束条件： 解：首先要将约束条件化为标准形：由此可以看出我们需要加上三个松弛变量， .得到的标准形式为： max z=2+3+ 0+0+0 然后要将其初始的单纯形表画出来： 23000 b 08121004 01640010- 01200013 23000 由初始单纯形表可以看出，为换入变量，而为换出变量；然后根据：= (也就是如果与主元素同行，则用现在的值除以主元素即可得到即将要填入的值，否则，就用现在的值减去与主元素构成矩形的边角上的值的乘积再除以主元素之后的值。例如：上面的第一行所对应的b值为8-(12*2)/4=2,故填入值应该为2。而则是由我们根据非基变量的检验数的大小，挑选出最大的那个，作为换入变量，然后用b的值除以该换入变量所在的列的所有值，得到列的值。 23000 b 02010-1/22 016400104 3301001/4- 2000-3/4由于在检验数中仍然存在大于等于0的数，而且P1，P5的坐标中有正分量存在，所以需要继续进行迭代运算。通过观察可以看出主元素为1，换入变量为，换出变量为，故得到的单纯形表如下：
23000 b 221010-1/2- 0800-414 3301001/412 00-201/4由于检验数中存在正数，且P5和P3中有正分量存在，所以需要继续迭代(换入变 23000 b 241001/40 0400-21/21 32011/2-1/80 00-3/2-1/80 （4,2,0,0,4），故目标函数值z=2*4+2*3=14 2、合理利用线材问题，现在要做100套钢架，每套用长为，，和的钢各一根， 已知原料长，问应如何下料，使用的原材料最省； 解：首先我们必须要清楚该问题的需要设立的变量是什么。我们分析一下问题，做100套钢架，需要长的钢100根，的钢100根，的钢100根。而一份原料长度是， 长度/m 下料根数 截取方案 12345 112 212 3132所用长度 剩余长度0 方案，使得剩余的总长度最少。由此，我们可以将目标函数和约束条件表述出来： 目标函数：min z=+++ 约束条件 首先可以写出线性方程组的矩阵形式：发现不存在单位矩阵，所以要采用人造基的方式，也就是要添加人工变量：，那么线性方程组可以
单纯形法例题讲解
基可行解 单纯形法是针对标准形式的线性规划问题进行演算的，任何线性规划问题都可以化为标准形式。 min cx f = （1） s.t b Ax = （2） 0≥x （3） 其中 T m mn m m n n T n n b b b b a a a a a a a a a A x x x x c c c c )...,(,............ ... ..., ),...,,(),,...,(212 1 22221112 112121=??? ???????????=== 假设1≥≥m n ，并设系数矩阵A 的秩为m ，即 设约束方程（2）中没有多余的方程，用j p 表示A 的第j 列，于是（2可写成 b p x m k j j =∑=1 （4） 矩阵A 的任意一个m 阶非奇异子方阵为LP 的一个基（或基阵），若 ),...,(21jm j j p p p B = （5）
是一个基，则对应变量jm j j x x x ,...,,21，称关于B 的基变量，其余变量成为关于B 的非基变量，若令非基变量都取零值，则（4）变为 b p x m k jk jk =∑=1 （6） 由于此方程组的系数矩阵B 是满秩方阵，故知（6）有唯一解，记为T jn j j x x x ) ,...,,()0() 0(2) 0(1于是按分量 {}{}),...,,\,...2,1(0) ,....3,2,1(21) 0(m j jk jk j j j n j x m k x x ∈=== 所构成的向量) 0(x 是约束方程组b Ax =的一个 解，称此)0(x 为LP 的对应于基B 的基解 （或基本解），也可称为方程组b Ax =的一个基解，如果) 0(x 为一基解，且满足 0)0(≥x 即它的所有分量都非负，则称此) 0(x 是LP 的一个基可行解，基可行解对应的基 称为可行基。
单纯形法的解题步骤
三、单纯形法的解题步骤 第一步：作单纯形表. （1）（1）把原线性规划问题化为标准形式； （2）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； （3）（3）目标函数非基化； （4）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即 ，则此时线性规划问题已取得最优解. (2) 若存在某个检验数是正数，即，而 所对应的列向量无正分量，则线性规划问题无最 优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. （1）找到最大正检验数，设为，并确定
（2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故取为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）. 表 6.8 x1 x2x3x4x5常数 x 3 x 4 x 51 0 1 0 0 1 2 0 1 0 0 （1）0 0 1 5 10 4 S′ 1 3 0 0 0 0 x 3 x 4 x2 1 0 1 0 0 （1）0 0 1 -2 0 1 0 0 1 5 2 4 S′ 1 0 0 0 -3 -12 x 3 x 1 x 20 0 1 -1 2 1 0 0 1 -2 0 1 0 0 1 3 2 4 S′0 0 0 -1 -1 -14
（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出