03 第三章 几种特殊的线性规划问题及其解法

1、第三章几个特殊线性规划问题及其解法，第三章几个特殊线性规划问题及其解法，第三章几个特殊线性规划问题及其解法，运输问题的主表运算方法和指派问题的匈牙利解法。熟悉运输问题数学模型的特殊结构，以及0-1计划和分配问题的特点。理解整数规划的概念、模型和解法以及0-1变量的应用。通过本章的学习，你应该能够：第三章几个特殊的线性规划问题及其解决方案，一个医药集团在中国有三个中药材种植加工基地，即A1、A2和A3；药材月生产加工能力分别为9吨、5吨和7吨。集团每月从这些基地向中国四个不同的制药厂B1、B2、B3和B4运输加工过的药材。四个制药厂每月的药材需求量分别为3、8、4和6吨。鉴于从各基地到各药厂的每

2、吨药材运费率如表3-1所示，集团应如何安排运输，在满足各药厂需求的前提下，将总运费率降至最低？第三章中的一些特殊线性规划问题及其解，第三章中的一些特殊线性规划问题及其解，属于线性规划问题，可用单纯形法求解。然而，用简单的表格来计算是非常繁重的，所以对于具有特殊结构的线性规划模型，人们讨论了一种更简单的求解方法，从而大大简化了计算。本章将介绍一些特殊的线性规划问题，如运输问题、0-1规划和指派问题及其相应的特殊解法。第三章，几个特殊线性规划问题及其解法，第一节运输问题和表格运算方法，第二节0-1规划问题，第三节分配问题，第四节案例分析，本章总结，第三节特殊线性规划问题及其解法，第一节运输问题和表

3、格运算方法，第一节运输问题的模型和特点。第二，用表格运算法解决运输问题；第三，处理其他运输问题；第三，几个特殊的线性规划问题及其求解，管理规划组织，生产1，生产2，生产3，销售1，销售4，销售2，销售3，原材料1，原材料2，原材料3，原材料4，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，物流，在第三章，一些特殊的线性规划问题及其求解，第一，运输问题的模型和特点，药材运输问题的运输表， X11，X12，X13，X14，X21，X31，X22，X23，X24，X32，X33，X34，第三，一些特殊的线性规

4、划问题及其解法，第一，运输问题的模型和特征，第三众所周知，有m个产地，用n个销售点表示，m个产地的产量分别为(可写成ai)，n个销售点的销售量分别为(可写成bj)。从第一个产地到第二个销售地点的单位材料运费率为cij。如何运输才能使总运输成本最小化？1.运输问题的模型和特征，第3章，一些特殊的线性规划问题及其解，表3-2，运输表，第3章，一些特殊的线性规划问题及其解，方程的数目是mn，生产和销售是平衡的，独立方程的数目是m n -1。m行n(约束方程)；然而，因为前m行的总和等于最后n行的总和(平衡条件)，所以有m个n-1行是线性独立的。首先，运输问题的模型和特征。第三章，几个特殊的线性规划问

5、题及其求解，m个生产区和n个销售区产销平衡运输问题的特点：必须有可行解和最优解；当产量和销售量都是整数时，必须有一个整数最优解；有m n-1个基本变量，如何判断m n-1个变量能否构成基本变量？1.运输问题的模型和特征，第三章，一些特殊的线性规划问题及其解，闭环的定义：闭环是运输表中的一个变量序列，其中任意两个相邻变量在同一行或同一列，而任意三个相邻变量不在同一行或同一列；序列中的最后一个变量与运输表中的第一个变量位于同一行或同一列。将一个序列中的两个相邻变量依次连接，并将最后一个变量与第一个变量连接，可以形成一个闭环，称为闭环。序列中的变量称为闭环的顶点，两个相邻变量之间的连线称为闭环的边。

6、1。运输问题的模型和特征，第3章，一些特殊的线性规划问题及其解，如果m=4和n=5，那么序列形成一个闭环，x21，x23，x41，x43，图3-1，闭环图(a)，第3章，一些特殊的线性规划问题及其解，x13，x34，如果n=5，变量序列形成一个闭环。图3-1，闭环示意图(b)，第3章，几个特殊的线性规划问题及其解，定理3-1，运输问题的m n-1个变量形成基本变量的充要条件是它不包含任何闭环。也就是说，不存在以所有顶点为基本变量的闭环。如果某个非基变量作为起点(第一个顶点)，而其他顶点都是基变量，则只能找到闭环。也就是说，不是任何m n-1个变量都可以构成基本变量！(1)运输问题的模型和特征；

7、(3)几个特殊的线性规划问题及其解法。表格运算法的基本步骤与单纯形法相似：(1)编制初始运输方案(即确定初始基本可行解)常用的方法有西北角法、最小单元法和沃格尔法。最优性测试的常用方法(寻找相应的测试数和测试)是闭环法和位势法。3方案的改进根据测试次数决定方案是否最佳，如果是，则终止，否则用闭环方法调整；回到步骤2，直到达到最佳状态。第三章，几个特殊的线性规划问题及其解法，1 .编制初始调度方案的最小单元法，3，0，2，4，0，3，2，0，4，3，3，3，0，5，4，0，5，4，5，0，0，0，基础该初始方案的总运费为59 47 31 22 34 42=100(100元)，基本变量数应为4 3

8、-1=6(件)。注意：在获得初始方案后，应检查最终的数字单元数是否正好为m n-1，如果数字单元数不等于m n-1，则不能进行以下计算。在第三章中，一些特殊的线性规划问题及其解被降级：3、0、0、0、4、0、5、2，运输问题用表运算法求解，在第三章中，一些特殊的线性规划问题及其解，2，最优性检验位势法，产销平衡运输问题的对偶问题有：对偶问题，原问题，变量ui，供给约束方程，变量vj，需求约束方程，m，n，行势，列势，xij，2。用表运算法求解运输问题，第三章，一些特殊线性规划问题及其解法，检验数计算公式：(3-1)然后用(3-1)计算其他非基本变量(空间)的检验数：(2)用表运算法求解运输问题

9、，第三章，一些特殊线性规划问题及其解法，U1=0，3，4，2，3，4，5，U1V2=9，V2=9，U1V4=7，V4=7，(-4)，10-(07)=3， (3)、3-(-59)=-1、(-1)、(7)、(3)、(2)，初始基本可行解不是最优解，因此有必要对基本可行解进行改进。 其次，利用表运算方法解决运输问题，从绝对值最大的负测试数对应的空白空间(基本变量)开始，构造一个所有其他顶点都是数字格的闭环。在保持生产和销售平衡的前提下，使基本变量的值尽可能大，同时调整闭环上其他顶点(基本变量)的值，以改进解。第二，用表格运算法解决运输问题。第三章，几个特殊的线性规划问题及其解法，闭环法：从基本变量出

10、发找出唯一的闭环，并从起点开始沿着闭环的每个顶点交替标记 和-；所有标有“-”的网格中的基变量xij的最小值作为基变量，其值作为调整量：2。用表格运算法解决运输问题；第三章，几个特殊的线性规划问题及其解法，闭环方法：对于闭环的每个顶点，将所有带“-”的网格加到初始值上，并用“-”减去网格的初始值；当基本变量从0改变时，获得新的调度方案。(不是闭环顶点的基础变量的值不变。)。重新计算测试次数，重复上述步骤，直到达到最佳状态。第三章，一些特殊的线性规划问题及其解法，3，4，2，3，4，5，(-4)，-，-，-，基本变量x11=3，X14=4-=1，X24=2=5。3，1，5，u1=0，v2=9，v

11、4=7，u3=-5，U2=-5，v3=7，v1=2，(3)，(-1)，(11)，(3)，(2)，(4)，U3=-4，U2=-5，v3=6，v1=2，(4)、(10)、(2)、(3)、(4)、(1)，调整后得到最优解。最低总运费：32 67 53 34 42=83(百元)。第二，用表格运算法解决运输问题；第三，一些特殊的线性规划问题及其解法；第三，处理其他运输问题。例3-1一家制药公司在中国有四家制药厂，其中某些药物的日产量为A1 600盒、A2 400盒、A3 300盒和A4 500盒。这些药厂每天将这些药物运送到四个地区的配送部门。每个配送部门的日需求量为：B1为200-600箱，B2为50

12、0-700箱，B3和B4分别为350箱和450箱。各药厂至各配送部门每箱药品的单位运费率见表3-13。制药公司应该如何运输它，以便在满足销售的同时使总运费最小化？第三章，几个特殊的线性规划问题及其解法，第三章，其他运输问题的处理，第三章，几个特殊的线性规划问题及其解法，它们被称为不平衡运输问题；是的，以“供大于求”为例，3 .处理其他运输问题，如“供大于销”和“供小于销”。几个特殊的线性规划问题及其解法。处理其他运输问题，模型是：3。几个特殊的线性规划问题及其解法，处理：在模型的输出约束(第一个m不等式，显然，在第三章，处理其他运输问题时，一些特殊的线性规划问题及其解法，松弛变量x i n 1

13、可以看作是从原产地A i到销售地B n 1的运输量，因为它不是实际运输的，它们的运费是，对于“供应小于销售”的问题，可以采用类似的处理，即增加虚拟原产地。3.在处理其他运输问题时，这个运输问题被转化为生产和销售平衡的问题。第三章，几个特殊的线性规划问题及其解法，例3-1的分析：每家制药厂这种药物的总产量是1800箱；四个配送部门的最低总需求量为1500箱，属于“供大于求”，需要增加虚拟销售区域以保持平衡；总的最大需求是2100箱，属于“供小于销”，因此有必要增加虚拟生产面积以保持平衡；每个分销部门的最低需求不能由虚拟原产地提供。3.其他运输问题的处理，第3章：几个特殊线性规划问题及其解决方案，

14、第2章：01规划问题，1: 01规划概念，2: 01变量应用，第3章：几个特殊线性规划问题及其解决方案，1: 01规划概念，当人们讨论一些线性规划问题时，有时他们必须将所有或部分决策变量限制为非负整数。这个线性规划问题通常被称为整数规划。作为线性规划的特例，整数规划也有最小化和最大化的区别。在第三章中，一些特殊的线性规划问题及其求解，整数规划也可以分为纯整数规划和混合整数规划。两者的区别在于前者的决策变量必须都是整数。而后者的决策变量只是部分整数。整数规划解有分枝定界法和截平面法。在纯整数规划和混合整数规划中，经常有一些变量的值只能是0或1(称为0-1变量)。如果模型中的所有变量都是0-1变量

15、，它们被称为0-1编程。一、01规划概念，第3章，一些特殊的线性规划问题及其解决方案，例3-2某集团公司正在考虑企业扩张计划，选项包括：收购医药行业上市公司进入医药领域；进入服装及配饰的生产和销售行业；扩展到信息技术行业；进入旅游业；进入食品和饮料行业。由于不同行业的不同特点和各种因素的限制，进入不同行业的投资周期是不同的，一般需要3-5年。不同行业投资所需的年投资额和10年后各行业净收入的现值如下表所示：1。01规划的概念，以及第三章，几个特殊的线性规划问题及其解决方法。如果只从收入的角度考虑投资计划，集团应该选择投资哪些行业？1.01规划的概念，第3章一些特殊的线性规划问题及其解法，z是1

16、0年后总净收入的现值。这个问题的数学模型如下：1 .01规划的概念，第3章一些特殊的线性规划问题及其解法，0-1规划的标准类型，求解0-1规划的隐式枚举法，1。01规划的概念，第三章一些特殊的线性规划第二，01变量的应用，进一步考虑了以下问题：集团决定不同时投资服装行业和食品行业，如果it决定投资旅游业，就必须先进入IT行业。0-1变量可以很容易地转换两个选择的决定，如选择和放弃，打开和关闭，是或不是，是或否，等等。数量关系。你如何在模型中表示你最多可以选择方案2和方案5中的一个进行投资，如果你不选择方案3，你就不能选择方案4？第三章，几个特殊的线性规划问题及其解法，1 .从方案2和方案5中最多选择一项投资，即方案2和方案5是互斥的，方案2和方案5不能同时选择，即x2和x5不能同时取1，