如果约束条件中含有不等式约束，则可以加入惰性变量，使之成为等式约束。
为了对线性规划问题求解，需要找出一组初始基向量。
由于人工变量对应的价值系数远比其他变量所对应的价值系数大，所以在求解过程中，人工变量最终取值都为零。
为了使用单纯形法求解线性规划问题，上述表达式可以列成表格形式，称之为单纯形表。
(2)单纯形法的求解步骤
对于线性规划问题求解，单纯形法是一种有效的方法。然而，针对不同情况，单纯形法的求解过程也不尽相同。这里介绍一种常用的方法。
单纯形法的求解过程就是对单纯形表的变换过程。
7.4.2 商用车辆路径优化(SP、TSP、VRP、PDP以及变形)
概述与案例应用
1.SP问题
最短路问题(shortest path，SP)是运输路径计划优化中一类最基本的问题，其中常见的是带权图的最短路径问题，即求两个顶点间长度最短的路径。其中，路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。路径长度的具体含义取决于边上权值所代表的意义。例如，交通网络中常常提出的如下问题就是带权图中求最短路径的问题：①两地之间是否有路相通？②在有多条通路的情况下，哪一条最短？其中，交通网络可以用带权图表示：图中顶点表示城镇，边表示两个城镇之间的道路，边上的权值可表示两城镇间的距离，交通费用或途中所需的时间等等。
由于交通网络存在有向性，所以一般以有向网络表示交通网络。例如，设A城到B城有一条公路，A城的海拔高于B城。若考虑到上坡和下坡的车速不同，则边＜A，B＞和边＜B，A＞上表示行驶时间的权值也不同，即＜A，B＞和＜B，A＞应该是两条不同的边。习惯上称路径的开始顶点为源点(source)，路径的最后一个顶点为终点(destina tion)。
最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。但是，无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径算法。经典的最短路径算法——Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础，只是不同系统对Dijkstra算法采用了不同的实现方法。据统计，目前提出的此类最短路径的算法大约有十几种，除了Dijkstra算法，其他应用较多的是：
TQQ(graph growth with two queues)、DKA(the Dijkstra摧salgorithm implemented withap proximate buckets)以及DKD(the Dijkstra摧salgorithm implemented withdouble buckets)。
2.TSP、VRP与PDP问题
旅行商问题(traveling salesman problem，TSP)是运筹学、图论和组合优化中的着名问题，TSP不仅可以解决最优巡回路线等类TSP问题，在交通车辆巡回、学校教师课程计划安排、工厂装配线进度管理以及民航机组人员轮班等问题上也有着广泛的应用前景。
TSP问题一般可以描述如下：一个旅行者从出发地出发，经过所有要到达的城市后，返回到出发地。要求合理安排其旅行路线，使得总旅行距离(或旅行费用、旅行时间等)最短。
在处理现实生活中的具体问题时，可以对TSP附加一些限制性条件，例如在模型中假设该旅行者的时间有限，进而添加相应的时间约束等，从而衍生出许多和TSP相关的问题。
车辆路线安排问题(vehicle routing problem，VRP)是对进行物流配送的车辆进行优化调度。该问题一般可以描述如下：对一系列装货点或(和)卸货点，组织适当合理的行车路线，使车辆有序地通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量、数目限制、车辆行驶里程、时间限制等)下，达到一定的目标(如最短路程、最小费用、最短时间、最少车辆等)。
VRP问题由Dantzig和Ramser于1959年首次提出，该问题一经提出，立即引起了运筹学、图论与网络分析、物流科学、计算机应用等学科专家与运输问题制定和管理者的极大关注，成为运筹学和优化科学研究的前沿和热点问题。众多科学家对VRP问题进行了大量的理论研究和实验设计，他们的不懈努力促进了该问题的巨大进展。目前，该问题已经不再局限于原来的汽车运输问题，在水路和航空运输、工业管理、电网建设、通信工程以及计算机应用等领域也有相当广泛的应用。例如，在航空乘务员轮班安排、交通路线安排、生产系统的计划和控制等问题中，就利用VRP问题的算法思想编制了相关的应用软件，在实际的应用中取得了良好的经济效益和社会效益。
PDP(pickupand delivery problem，装卸货问题，以下简称PDP问题)问题是VRP问题在现实中的演化，与VRP不同的是，PDP不仅仅是在所要求的目的地完成一次访问(对于VRP问题来讲，这种访问就是进行一次送货或者取货服务，送货和取货任务不同时发生在同一点上)，同时需要完成送货和取货两种作业任务。这样一来PDP问题较之VRP更加复杂，对于车辆容量限制条件的考虑也更加难以确定。
如果考虑抵达地服务时间—时窗(time window)的限制条件，那么上述的TSP、VRP、PDP问题又可以演化为TSP with time window constraint、VRP with time win dow constraint、PDP with time window constraint，即TSPTW、VRPTW、PDPTW系列问题。
3.精确式算法及其应用的局限性
TSP、VRP、PDP等系列问题属于组合优化领域着名的NP难题。其求解方法一般相当复杂，通常的做法是应用相关技术将问题分解或者转化为一个或者多个已经研究过的基本问题(如旅行商问题、指派问题、运输问题、最短路问题、最大流问题、最小费用最大流问题、中国邮递员问题等)，再使用相对比较成熟的基本理论和方法进行求解，以求得原运输车辆调度问题的最优解或满意解。
精确式算法一般运用线性规划(包括经过了专门处理的分枝定界法、割平面法和标号法)和非线性规划等数学规划技术，以便求得问题的最优解。在VRP问题研究的早期，主要是单源点(One Point)(即配送中心、车场等)派车，研究如何用最短路线(或在最短时间内)对一定数量的需求点(即用户)进行车辆调度，因此主要运用精确算法求出问题的最优解。精确式算法一般有以下几种方法：①分枝定界法(branch and boundap proach)；②割平面法(cutting planes approach)；③网络流算法(net work flow ap proach)；④动态规划方法(dynamic programming approach)等。精确算法随着运输系统的复杂和调度目标的增加，其计算量呈指数递增，使得获取整个系统的精确最优解越来越困难，而用计算机求解大型优化问题的时间和费用又太大，因此，此类优化方法和算法现在一般仅用于求解运输调度的局部优化问题。
