下载文档原格式
第四章 线性规划的求解法当线性规划的变量和约束条件比较多，而初始基本可行解又不知道时，是不容易用尝试的方法得到初始基本可行解的，何况有可能基本可行解根本就不存在。
在此时，大M 法可能是应付此类情况的一个行之有效的算法。
§4.1 大M 法的原理当初始基本可行解不知道时，则1.，2.两个特点不能兼得，即下列两条件不能兼得： 1. 中心部位具有单位子块； 2. 右列元素非负；这时可以先用容许的运算使由列为非负，然后在中心部位人为添加一个单位子块。
如下例所述： 例4.1123123123123min 32..323624,,0z x x x s tx x x x x x x x x =-+++-=-+-=-≥ （4.1.1）列成表格：上述第三张表中人工增加了两个变量45,x x ，称为人工变量，即把原来的约束条件改为：1234123512345..323624,,,,0s tx x x x x x x x x x x x x +-+=-++=≥ （4.1.2） 式（4.1）和（4.2）的约束方程组并不同解，但（4.1）的解和（4.2）中450x x ==的解是相对应的。
只要找到以（4.2）为约束条件，且人工变量45,x x 均为自由变量的基本可行解，也就找到了（4.1）的基本可行解，于是，要设法迫使450x x ==。
以上途径通过修改（4.1）的目标函数来实现。
具体修改为：12345min 32z x x x Mx Mx =-++++ （4.1.3）其中M 为足够大的正数，然后以（4.2）为约束条件，求（4.3）的最小值。
只要45,x x 不为零，就一定为正数，于是目标函数的值就会增加它们和的M 倍。
由于M 为足够大的正数，所以只要原问题有基本可行解，就不会在45,x x 取正值时达到最小值。
本例中把表改为：通过运算使它具备第三个特点：底行相应于单位子块位置的元素为0，然后再严格按照单纯形法的步骤求解：由于M 为足够大的正数，所以-3-4M 应视为负数，故选它。
线性规划是高考数学必考的内容，侧重于考查同学们的数学建模、数学运算、数学分析等能力.线性规划问题的类型有很多，在本文中笔者总结了几类常见的线性规划题型及其解法，以帮助同学们加深对线性规划题型及其解法的了解.类型一：求目标函数的最值求目标函数的最值是线性规划中的一类常见题型，主要有两种形式：（1）求线性目标函数的最值；（2）求非线性目标函数的最值.无论是哪一种，解题的基本思路都是：（1）画出约束条件所确定的平面区域；（2）将目标函数变形为斜截式直线方程、两点间的距离、直线的斜率等；（3）在可行域内寻找取得最优解的对应点的位置；（4）解方程组求出对应点的坐标(即最优解)，代入目标函数，即可求出最值.例1.已知x、y满足以下约束条件ìíîïï2x+y-2≥0,x-2y+4≥0,3x-y -3≤0,则z=x2+y2的最大值和最小值分别是_____.解：作出如图1所示的可行域，将z=x2+y2可以看作点()x,y到原点的距离的平方，由图可知，在可行域内点A到原点的距离的平方最大，即||AO2=13,直线2x+y-2=0到原点的距离的平方最小，为d2=æèççöø÷÷||0-222+122=45，所以z=x2+y2的最大值和最小值分别是13和45.在求目标函数的最值时，同学们要注意将目标函数进行适当的变形，深入挖掘其几何意义，将其看作直线的斜率、截距、两点间的距离等，然后在可行域内寻找取得最值的点.类型二：求可行域的面积求可行域的面积的关键在于根据约束条件画出正确的图形，然后将可行域拆分、补充为规则的几何图形，如三角形、平行四边形、矩形等，再利用三角形、平行四边形、矩形等的面积公式进行求解.例2.已知不等式组ìíîïï2x+y-6≥0,x+y-3≤0,y≤2,则该不等式表示的平面区域的面积为_____.解：根据所给的不等式组作出可行域，如图2所示，由图2可知△ABC的面积即为所求.显然S△ABC=S梯形OMBC-S梯形OMAC，S梯形OMBC=12×()2+3×2=5，S梯形OMAC=12×()1+3×2=4，所以S△ABC=S梯形OMBC-S梯形OMAC=5-4=1.本题中的可行域为三角形，而该三角形的面积很难直接求得，于是将其看作梯形OMAB的一部分，将梯形OMAB的面积减去梯形OMAC的面积，便可得到三角形ABC的面积.类型三：求参数的取值或者范围很多线性规划问题中含有参数，要求其参数的取值或范围，首先要确定可行域，然后结合题意寻找符号条件的最优解，建立相对应的关系式，便可求得参数的取值或者范围.例3.已知x、y满足以下约束条件ìíîïïx+y≥5,x-y+5≤0,x≤3,使z=x+ay()a>0取得最小值的最优解有无数个，则a的值为_____.解：根据约束条件作出可行域，如图3所示，作出直线l:x+ay=0，要使目标函数z=x+ay()a>0取得最小值的最优解有无数个，可将直线l向右上方平移，使之与直线x+y=5重合，故a=1.通常含有参数的目标函数图象是不确定的，因此正确绘制出可行域十分关键，只有对问题中的所给条件进行正确的分析，才能快速找到正确的解题思路.通过对上述三类题型的分析，同学们可以发现线性规划问题都比较简单，按照基本的解题步骤：画图—变形目标函数—寻找最优解对应的点—求值便能得到答案.同学们在解答线性规划问题时还需重点关注特殊点、直线，这些特殊的点、位置常常是取得最优解的点或者位置.（作者单位：江苏省江阴市第一中学）承小华图1图2图３方法集锦45。
线性规划知识点一、概述线性规划是一种数学优化方法，用于求解线性约束条件下的最优解问题。
它在运筹学、管理科学、经济学等领域有着广泛的应用。
线性规划的目标是通过线性目标函数的最小化或最大化，找到使得一系列线性约束条件得到满足的最优解。
二、基本概念1. 线性规划模型线性规划模型由目标函数和约束条件组成。
目标函数是需要最小化或最大化的线性函数，约束条件是一系列线性不等式或等式。
2. 可行解可行解是满足所有约束条件的解。
在线性规划中，可行解构成了一个可行域，即满足所有约束条件的解的集合。
3. 最优解最优解是使得目标函数取得最小或最大值的可行解。
在线性规划中，最优解可以是有限的，也可以是无穷的。
4. 线性规划的标准形式线性规划的标准形式包括以下特点：- 目标函数为最小化形式；- 所有约束条件为等式形式；- 变量的取值范围为非负数。
1. 图形法图形法是线性规划最直观的解法之一。
它通过绘制变量的可行域图形，找到目标函数的最优解。
2. 单纯形法单纯形法是一种迭代算法，通过不断地移动解的位置来逐步逼近最优解。
它是线性规划中应用最广泛的解法之一。
3. 对偶理论对偶理论是线性规划中的重要概念之一。
它通过将原始问题转化为对偶问题，从而得到原始问题的最优解。
四、线性规划的应用线性规划在实际生活中有着广泛的应用，以下是一些常见的应用领域：1. 生产计划线性规划可以用于确定最佳的生产计划，以最小化生产成本或最大化利润。
2. 运输问题线性规划可以用于解决运输问题，如货物的最佳配送方案、最短路径等。
3. 金融投资线性规划可以用于优化投资组合，以最大化投资收益或最小化风险。
4. 资源分配线性规划可以用于确定最佳的资源分配方案，如人力资源、物资等。
尽管线性规划在许多问题中有着广泛的应用，但它也存在一些局限性：1. 线性假设线性规划的基本假设是目标函数和约束条件都是线性的，这限制了它在处理非线性问题上的应用。
2. 离散性问题线性规划通常适用于连续变量的问题，对于离散变量的问题，它的应用受到限制。
Java基础算法详解查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。
因为其实现代码较短，应用较常见。
所以在面试中经常会问到排序算法及其相关的问题。
但万变不离其宗，只要熟悉了思想，灵活运用也不是难事。
一般在面试中最常考的是快速排序和归并排序，并且经常有面试官要求现场写出这两种排序的代码。
对这两种排序的代码一定要信手拈来才行。
还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。
面试官对于这些排序可能会要求比较各自的优劣、各种算法的思想及其使用场景。
还有要会分析算法的时间和空间复杂度。
通常查找和排序算法的考察是面试的开始，如果这些问题回答不好，估计面试官都没有继续面试下去的兴趣都没了。
所以想开个好头就要把常见的排序算法思想及其特点要熟练掌握，有必要时要熟练写出代码。
冒泡排序冒泡排序是最简单的排序之一了，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。
这个过程类似于水泡向上升一样，因此而得名。
举个栗子，对5,3,8,6,4这个无序序列进行冒泡排序。
首先从后向前冒泡，4和6比较，把4交换到前面，序列变成5,3,8,4,6。
同理4和8交换，变成5,3,4,8,6,3和4无需交换。
5和3交换，变成3,5,4,8,6,3.这样一次冒泡就完了，把最小的数3排到最前面了。
对剩下的序列依次冒泡就会得到一个有序序列。
冒泡排序的时间复杂度为O(n^2)。
实现代码：*@Description:冒泡排序算法实现public class BubbleSort {public static void bubbleSort(int[] arr) {if(arr == null || arr.length == 0)for(int i=0; i) {for(int j=arr.length-1; ji; j--) {if(arr[j]arr[j-1]) {swap(arr, j-1, j);public static void swap(int[] arr, int i, int j) { int temp = arr[i];arr[i] = arr[j];arr[j] = temp;抑或简单理解一点的正向排序public class BubbleSort {public static void bubbleSort(int[] arr) {if(arr == null || arr.length == 0)for(int i=1;iarr.length-1;i++) {for(int j=0; jarr.length-i; j++) {if(arr[j]arr[j+1]) {swap(arr, j+1, j);public static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;选择排序选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。
线性规划常见题型及解法一．基础知识：(一)二元一次不等式表示的区域二元一次不等式0>++C By Ax 表示直线0=++C By Ax 某一侧的所有点组成的区域，把直线画成虚线表示不包括边界， 0≥++C By Ax 所表示的区域应包括边界，故边界要画成实线.由于在直线0=++C By Ax 同一侧的所有点（x,y ）,把它的坐标（x,y ）代入C By Ax ++，所得的符号相同，所以只需在此直线的某一侧取一个特殊点（0,0y x ），从C By Ax ++00的正负即可判断0≥++C By Ax 表示直线哪一侧的平面区域。
通常代特殊点（0，0）。
（二）线性规划(1)不等式组是一组对变量x 、y 的约束条件，由于这组约束条件都是关于x 、y 的一次不等式，所以又可称其为线性约束条件.z =A x +B y 是欲达到最大值或最小值所涉及的变量x 、y 的解析式，我们把它称为目标函数.由于z =A x +B y 又是关于x 、y 的一次解析式，所以又可叫做线性目标函数.另外注意：线性约束条件除了用一次不等式表示外，也可用一次方程表示.(2)一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题.(3)那么，满足线性约束条件的解（x ,y ）叫做可行解，由所有可行解组成的集合叫做可行域.在上述问题中，可行域就是阴影部分表示的三角形区域.其中可行解（11,y x ）和（22,y x ）分别使目标函数取得最大值和最小值，它们都叫做这个问题的最优解.线性目标函数的最值常在可行域的顶点处取得;而求最优整数解必须首先要看它们是否在可行(4)用图解法解决简单的线性规划问题的基本步骤：1.首先，要根据线性约束条件画出可行域（即画出不等式组所表示的公共区域）.2.设z =0，画出直线l 0.3.观察、分析，平移直线l 0，从而找到最优解.4.最后求得目标函数的最大值及最小值. (5) 利用线性规划研究实际问题的解题思路：首先，应准确建立数学模型，即根据题意找出约束条件，确定线性目标函数.然后，用图解法求得数学模型的解，即画出可行域，在可行域内求得使目标函数取得最值的解. 最后，还要根据实际意义将数学模型的解转化为实际问题的解，即结合实际情况求得最优解.线性规划是新教材中新增的内容之一，由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下常见题型。
线性规划问题的解法与最优解分析线性规划是一种数学建模方法，用于解决最优化问题。
它在工程、经济学、管理学等领域有着广泛的应用。
本文将介绍线性规划问题的解法和最优解分析。
一、线性规划问题的定义线性规划问题是指在一定的约束条件下，求解一个线性目标函数的最大值或最小值的问题。
线性规划问题的数学模型可以表示为：max/min Z = c₁x₁ + c₂x₂ + ... + cₙxₙsubject toa₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + aₙ₂x₂ + ... + aₙₙxₙ ≤ bₙx₁, x₂, ..., xₙ ≥ 0其中，Z表示目标函数的值，c₁, c₂, ..., cₙ为目标函数中的系数，a₁₁,a₁₂, ..., aₙₙ为约束条件中的系数，b₁, b₂, ..., bₙ为约束条件中的常数，x₁,x₂, ..., xₙ为决策变量。
二、线性规划问题的解法线性规划问题的解法主要有两种：图形法和单纯形法。
1. 图形法图形法适用于二维或三维的线性规划问题。
它通过绘制约束条件的直线或平面以及目标函数的等高线或等高面，来确定最优解。
首先，将约束条件转化为不等式，并将其绘制在坐标系上。
然后，确定目标函数的等高线或等高面，并绘制在坐标系上。
最后，通过观察等高线或等高面与约束条件的交点，找到最优解。
图形法简单直观，但只适用于低维的线性规划问题。
2. 单纯形法单纯形法是一种迭代的求解方法，适用于高维的线性规划问题。
它通过在可行域内不断移动，直到找到最优解。
单纯形法的基本思想是从初始可行解开始，每次通过找到一个更优的可行解来逼近最优解。
它通过选择一个基本变量和非基本变量，来构造一个新的可行解。
然后，通过计算目标函数的值来判断是否找到了最优解。
如果没有找到最优解，则继续迭代，直到找到最优解为止。
单纯形法是一种高效的求解线性规划问题的方法，但对于大规模的问题，计算量会很大。
第六章 线性规划及其解的实现线性规划是目前应用最广泛的一种系统优化方法，它的理论和方法已十分成熟，可以应用于生产计划、物质调运、资源优化配置、地区经济规划等许多实际问题.线性规划最早由前苏联学者L V Kantorovich 于1939年提出，但他的工作当时并未为人所熟知.直到1947年，美国学者G B Danzing 提出求解线性规划最有效的算法-----单纯性算法后，才引起数学家、经济学家和计算机工作者的重视，并迅速发展成为一门完整的学科而得到广泛的应用.利用线性规划建立数学模型也是中国大学生数学建模竞赛中最常用的方法之一.优化模型的一般形式为T n Xx x x X X f z ),,,(),(min 21 == (1)m i X g t s i ,,2,1,0)(.. =≤ (2)其中)(x f 称为目标函数，)(X g i 称为约束条件.只满足式(2)的X 称为可行解；同时满足式(1)、式(2)两式的解*X X =称为最优解.由式(1)、式(2)组成的模型属于约束优化，若只有式(1)就是无约束优化.一般情况下，优化问题都是有约束的，但是如果最优解不是在可行域的边界上，而是在可行域的内部，那么就可以用无约束优化作比较简单的处理.若f ，i g 均为线性函数，优化模型式(1)、式(2)称为线性规划，否则称为非线性规划. 本章主要对线性规划问题及其解的实现作简要介绍.§6.1 线性规划模型形式及其性质线性规划是运筹学的一个重要分支，应用很广.线性规划问题可以描述为求一组非负变量，这些非负变量在一定线性约束的条件下，使一个线性目标函数取得极小(或极大)值的问题.1、线性规划的标准形式目标函数 n n x c x c x c z +++= 2211m in约束条件 ⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=+++=+++=+++0,,,2122112222212111212111n mn mn m m n n n n x x x bx a x a x a b x a x a x a b x a x a x a这里n x x x ,,,21 是变量，i ij i b a c ,,都是已知常数，且0≥i b ，约束条件常用..t s 表示.线性规划用矩阵表示就是T n x x x X cX z ),,,(,min 21 ==T n n m ij b b b b n m a A x b AX t s ),,,(),()(,0,..21 =≤=≥=⨯.2、线性规划的一般形式 目标函数 n n x c x c x c z +++= 2211m in约束条件 ⎪⎪⎩⎪⎪⎨⎧+++++++++mn mn m m n n n n b x a x a x a b x a x a x a b x a x a x a )()()(22112222212*********式中的( )可以是关系符号：≤≥=<>,,,,中的任意一个.3、线性规划化为标准形的方法 把线性规划化为标准形：(1)目标函数一律化为求极小(如果是求极大，则利用)m in(m ax z z -⇔化为求极小).(2)对约束条件中b Ax ≤的不等式，利用加入松弛变量的方法化为等式.如果原约束条件中有""b ≥形式的约束，可以在不等式两边同时加负号化为""b -≤的形式.(3)标准形中一般要求0≥i x .如果某个i x 无此约束，可以引入两个新变量''',i i x x ，令'''i i i x x x -=，0,'''≥i i x x ；如果原来的约束为i i l x ≥，可以令i i i l x x -='，0'≥i x .4、线性规划的基本性质 线性规划有以下基本性质：1）若存在可行域，可行域必为凸集； 2）基可行解对应于可行域的顶点；3）若有最优解，必在可行域的顶点取得.§6.2 线性规划问题的数学模型及其解的基本概念1、线性规划问题的数学模型例1 (生产计划问题)某工厂生产甲、乙两种产品，甲产品每生产一件需耗黄铜2kg 、3个工作日、两个外协件，每件可获利润60元；乙产品每生产一件需耗黄铜4kg 、1个工作日、不需外协件，每件可获利润30元，该厂每月可供生产用的黄铜320kg ，总工作日180个，外协件100个.问应怎样安排生产才能使工厂的利润最高？分析问题，建立数学模型.问题：怎样安排生产，即甲、乙两种产品各生产多少才能使工厂的利润最高？用1x ，2x 分别表示甲、乙两种产品生产的件数，该厂追求的目标是获取最高利润，用数学表达式表示为：213060m axx x f +=.由于生产甲、乙产品的件数要受到生产能力的约束，即 黄铜约束：3204221≤+x x ，工作日约束：180321≤+x x ， 外协件约束：10021≤x ， 非负约束：0,21≥x x .这样，该厂生产计划问题就归结为如下数学模型：⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤++=.0,,1002,1803,32042..,3060max 211212121x x x x x x x t s x x f例2 (运输问题)计划由三个粮站1A ，2A ，3A 运输某种粮食至三个加工厂1B ，2B ，3B ，三个粮站的供应量和三个加工厂的需求量以及各供应地至需求地的单位运输价(元/t)如表1所示，试作出运费最省的调运计划方案.表 1问题：如何调运，才能使运费最省？设ij x 表示第i 个粮站到第j 个加工厂的粮食数量(单位：3,2,1,,=j i t )，则总运费3332312322211312112050603040709080120x x x x x x x x x f ++++++++=.从各粮站运出的粮食数量不能超过供应量，20131211=++x x x ，30232221=++x x x ，50333231=++x x x ，同时还要保证各加工厂的需要，25312111=++x x x ，50322212=++x x x ，25332313=++x x x ，而运输量应满足0≥ij x .则上述运输问题的数学模型为⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧≥=++=++=++=++=++=++++++++++=.0255025503020..2050603040709080120min 332313322212312111333231232221131211333231232221131211ij x x x x x x x x x x x x x x x x x x x t s x x x x x x x x x f从上述两个例子可以看出，虽然两个问题的具体内容和性质不同，但它们都属于优化问题，它们的数学模型都有相同的数学形式，即在一定的线性等式或不等式的条件下，使某一线性函数达到最大(或最小).所谓线性规划问题的数学模型是将实际问题转化为一组线性不等式获等式约束下求线性目标函数的最小(大)值问题.2、解的基本概念对于线性规划问题的标准形式..min ≥==x b Ax t s cx z 其中系数矩阵A 是行满秩的，即)()(n m m A R ≤=，并引入列向量),,2,1(n j P j =表示系数矩阵的列向量.满秩约束条件的解称为线性规划问题的可行解，可行解的全体}0,|{≥==x b Ax x D 称为线性规划问题的可行域.满足目标函数的可行解称为线性规划问题的最优解.系数矩阵A 的任意一个m 阶的可逆方阵B 称为线性规划问题的一个基.显然，A 最多有mn C 个基.基B 中的任意一列向量j P 称为基向量.系数矩阵A 中除基B 外的其余m n -个列向量称为非基向量.显然，选择的基不同，与基对应的非基向量也不尽相同.与基向量j P 对应的变量j x 称为基变量.与非基向量j P 对应的变量j x 称为非基变量.为叙述方便，不妨假设基B 是阵A 的前m 列构成的，即),,,(21m P P P B =，如若不然，则可通过调整变量顺序达到此目的.按上述定义，),,2,1(m j x j =为基变量，),,2,1(n m m j x j ++=为非基变量，记T m B x x x X ),,,(21 =，T n m m N x x x X ),,,(21 ++=，),,,(21n m m P P P N ++=那么约束条件可用分块矩阵表示为b X X N B N B =⎪⎪⎭⎫ ⎝⎛),(令0=N X ，由b BX B =得b B X B 1-= (3) 称⎪⎪⎭⎫⎝⎛=⎪⎪⎭⎫ ⎝⎛=-01b B X X X N B为对应于基B 的基解.很显然，由于m B R =)(，即0||≠B ，所以式(3)的解是惟一的.即对应于某个基的基解是惟一的，从而一个线性规划问题最多有mn C 个基解.若基解满足0≥x ，则称基解为基可行解。
线性规划问题的解法比较与分析
【摘要】 总结了线性规划问题数学模型各种解法的优势和局限性，结合具体实例介绍一种适用性强，便于理解和记忆的新解法—新两阶段的解题思想和步骤，并通过初等行变换对单纯形法进行了进一步的改进。
关键词： 新两阶段法；换基迭代； 单纯形法； 初等行变换
1.问题的提出
线性规划问题的数学模型的一般表示形式为：
112211112211211222221122
12,max(min)(,)(,)(,),,0n n
n n n n m m mn n m
n z c x c x c x a x a x a x b a x a x a x b a x a x a x b
x x x =++++++≤=≥⎧⎪+++≤=≥⎪⎪⎨
⎪+++≤=≥⎪≥⎪
⎩
由于有的线性规划问题目标函数求“最大值”，有的求“最小值”；约束条件中数量约束部分有的为“等式”约束，有的为“不等式”约束，故在解线性规划问题数学模型时，除图解法外，通常先规定线性规划问题的标准形式，然后给出标准形式的解法。
在此我们规定，线性规划问题数学模型的标准形式为：
112211112211
21122222
1122
12,max ,,0n n
n n n n m m mn n m
n z c x c x c x a x a x a x b a x a x a x b a x a x a x b
x x x =++++++=⎧⎪+++=⎪⎪
⎨
⎪+++=⎪≥⎪
⎩
且：0(1,2,
)i
b i m ≥=
2.新两阶段法
以往，根据标准形式的不同形式的不同特点需要采用不同的解法。
常用方法有：单纯形方法,大M 法，两阶段法及对偶单纯形方法等等。
在吕为的《线性规划数学模型的一种新解法》【1】
一文中，给出了适用性强，便于理解和记忆
的新解法——新两阶段法，下面我们结合例题介绍其解题方法和步骤： 例1：求解线性规划问题：
123
123123
13max 428228212..230(1,2,3)
j z x x x x x x x x x s t x x x j =-+-++≥⎧⎪-+≤⎪⎨
-=-⎪⎪≥=⎩
1. 标准化
新两阶段法标准化时必须引入m 个松弛变量，若某约束条件在原始问题中为等式约束，引入松弛变量的系数为0.因而标准形中共有n+m 个决策变量。
例1标准化为：
123
12341235136max 428228
212..2030(1,2,,6)
j z x x x x x x x x x x x s t x x x x j =-+-++-=⎧⎪-++=⎪⎨
-++=⎪⎪≥=⎩ 显然标准形中无现成单位阵作初始可行基，可以采用大M 法或两阶段法先找出第一个单位阵作可行基，而用新两阶段法相对简单一些。
2. 列表
表1：
其中第一行为标准形式目标函数中各决策变量系数的相反数和常数，最后一行为虚拟检验数行，即是松弛变量系数不等于1的各约束条件决策变量系数不等于1的各约束条件决策变量系数的相反数之和。
表2
：
若表1得到的虚拟检验数行所有元素均为0，说明松弛变量系数恰为单位阵，可取其作初始可行基；若有非0元素，需进行换基迭代；若无负虚拟检验数，且不全为0，说明该线性规划问题无可行解。
取表1虚拟检验数行最小者-3<0，根据单纯形法选取主元，换基迭代的表2， 表3：
继续迭代得表3，因其虚拟检验数均为0，即出现单位阵作为可行基，去掉最后一行，继续换基迭代，得表4。
表4：
表4所有检验数均大于等于0，所以为最优单纯性表，即例1的最优解为：
1235,11,13x x x ===
最优值为：
max 11z =
3.对单纯形法的改进
通常我们用单纯形法解决线性规划问题时，往往计算过程复杂易出错，于是我们通过对系数增广矩阵的初等行变换来对单纯行法进行改进，以达到提高计算效率的目的。
我们通过一个例题来讲述这个改进方法： 例2：求解
123
1234123513min 3211423..210(1,2,,5)
i z x x x x x x x x x x x s t x x x i =-++-++=⎧⎪-++-=⎪⎨
-+=⎪⎪≥=⎩ 首先，对系数增广矩阵做保持可行性的初等行变换：
121101132010103001212412013010011010011201001201001201001⎡-⎤⎡-⎤⎡-⎤
⎢⎥⎢⎥⎢⎥--→-→-⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥---⎣⎦⎣⎦⎣⎦
然后，安排初始单纯形表如下：
于是，得到最优解*
(4,1,9,0,0)T x
=及最优值*2z =-
而该例用书上的大M 法进行了3次迭代才得到最优解；用两阶段法进行了2次迭代才完成了第一阶段，然后进入了第二阶段，又进行了1次迭代才求得最优解。
4.各解法的优势和局限性
通常，根据标准形式的不同形式的不同特点需要采用不同的解法。
教材中给出的方法有：图解法，单纯形方法,大M 法，两阶段法及对偶单纯形方法等等。
每种方法各有其优势和局限性。
现对各方法的优缺点进行比较： i.
图解法：
优点：简单直观，有助于了解线性规划问题求解的基本原理 缺点：当变量数多于三个以上时无法求解
ii.
单纯形法：
优点：解法简单，易于掌握
缺点：1.只适用于标准形约束方程组系数矩阵A 中含有现成的m 阶单位子阵为初始可行
基的情况， 2.计算步骤繁杂；
iii.
对偶单纯形法：
优点：解法简单，易于掌握
缺点：只适用于一小部分无现成单位阵的情况；
iv.
大M 法
优点：适用于所有的线性规划模型，
缺点：1.需引用人工变量，使计算量大幅度增加，
2.使用大M 法时事先无法确定M 究竟多大才能保证人工变量出基，手算时工作量大
3.上机计算时，选取过分大的M 会使计算产生困难或误差；
v.
两阶段法
优点：适用于所有的线性规划模型，
缺点：当第一阶段完成进入第二阶段时，需重新计算检验数才行，使计算量和计算难度
增加。
vi.
新两阶段法 优点：
1. 通用性强，适用于所以线性规划问题数学模型。
2. 克服了大M 法中M 无法确定，决策变量增加，检验数难于计算等弱点。
3. 两个阶段所用的换基迭代及判优的方法前后一致，连贯性强，便于理解，记忆和计
算。
4.方法简单统一，适用于计算机编程。
缺点：计算过程还是比较繁杂，计算效率不是很高。
vii.单纯形法的改进方法
优点：
1.在于寻求初始可行基时，思路清晰，不需要引用人工变量，方法简明。
2.借助于线性代数的初等行变换。
在进行主元选取时，通过改进入基变量的选取准
则明显提高了单纯行法的计算效率。
缺点：不易寻找对系数增广矩阵做保持可行性的初等行变换
5.参考文献
【1】吕为，赵佳因，线性规划数学模型的一种新解法，北京市经济管理干部学院学报，2000,15（1）
【2】申卯兴，许进，求解线性规划的单纯形法的直接方法，计算机工程与应用，2007,43（30）：【3】申卯兴，宁振民，郝彩丽，线性规划单纯形法的改进与教学，中国企业运筹学第三届学术年会论文集，2008.4.26
【4】李阳，熊令纯等，求解线性规划的一种单纯形矩阵法，数学的实践与认识，2003，43（17）
【5】《运筹学》教材编写组，运筹学（第四版）[M]，北京，清华大学出版社，2005。
