商业数据分析理念与方法 课件 第六章 商业运营与规划

第6章

商业运营与规划学习目标1．掌握线性规划问题、运输问题、整数规划的数学模型及模型特征。2．能利用线性规划、整数规划解决实际问题。3．能熟练运用软件求解线性规划、运输问题、整数规划。4．掌握用不同软件求解整数问题的技巧。目录CONTENTS01线性规划问题02整数规划问题03运输问题04本章习题线性规划问题01一、问题提出

线性规划是运筹学的一个重要分支，是帮助决策者做出决策的有效方法之一。在经济管理活动中，针对有限的资源通常需要寻求最佳的利用或分配方式。任何资源，如劳动力、原材料、设备或资金等都是有限的，所以必须进行合理的配置，寻求最佳的分配方式。所谓最佳的分配方式，必须有一个标准或目标，在单一目标问题中，就是使利润最高或成本最低，由此可以把有限资源的合理配置归纳为两类问题：一类是如何合理地使用有限资源，使得效益最大化；另一类是在经济管理的任务确定的条件下，如何合理地组织、安排活动，使所消耗的资源数最少，这是最常见的两类规划问题。与规划问题有关的数学模型主要由以下两部分内容组成：一部分是约束条件，反映有限资源对经济管理活动的种种约束，或者必须完成的任务；另一部分是目标函数，反映决策者在有限资源条件下希望实现的目标。一、问题提出

例6-1-1XY公司计划生产Ⅰ、Ⅱ两种产品。已知各生产一种产品时分别占用的设备台时、工时和资源总量，各售出一种产品时的收益情况，如下表所示。问该公司应如何组织生产，以使获取的总收益最大。这是一个合理使用有限资源产生最大收益的问题。资源信息表III资源总量/元设备台时/(小时/件)23300工时/(小时/件)21.5150收益/(元/件)100120

一、问题提出

例6-1-2某加工厂要制作100套钢架，每套要用长为2.9m、2.1m和1.5m的圆钢各一根。已知原料长为7.4m，问应如何下料可使所用材料最省。这是一个典型的在生产任务确定的条件下，合理组织生产（下料），以使所消耗资源数量最少的问题。日期所需营业员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六28表6.1.2工作需求表二、线性规划问题的数学模型

数学模型的约束条件中的第一个式子表示产品Ⅰ、产品Ⅱ的制造数量受设备的限制，第二个式子表示产品Ⅰ、产品Ⅱ的制造数量受人工能力的限制，第三个式子称为变量的非负约束，表示产品Ⅰ、产品Ⅱ的制造数量不可能取负值。二、线性规划问题的数学模型

例6-1-2可以这样理解：在长度一定的原材料上截三种不同长度的圆钢，有多种下料方案，基本原则是按各种下料方案下料以后剩下的余料要足够少，即剩下的余料已不能再截下任何一种规格的圆钢，即余料的长度必须小于1.5m。按照这样的原则，可以归纳出8种不同的下料方案，按余料长度逐步递增排序，如下表所示。下料方案表下料方案12345678圆钢/m2.9120101002.1002211301.531203104余料/m00.10.20.30.80.91.11.4至此，此问题则变为如何混合使用表中这8种不同的下料方案来制造100套钢架，并且使剩余余料的总长度最短。二、线性规划问题的数学模型

二、线性规划问题的数学模型

二、线性规划问题的数学模型

此数学模型可简写为

二、线性规划问题的数学模型

如果用向量表示，该数学模型则可写为式中，；该数学模型用矩阵和向量来表示可写为式中，A被称为约束方程组（约束条件）的系数矩阵。

三、线性规划问题数学模型的标准形式

；

因为目标函数和约束条件在内容和形式上存在差异，所以线性规划问题数学模型的表达方式可以有很多种。为了便于讨论和制定统一的求解方法，因此统一规定线性规划问题数学模型的标准形式如下：如果用矩阵和向量来表示可以写为在标准形式的数学模型中，必须符合以下四个条件:目标函数为极大化型。约束条件全为等式。约束条件右端常数项𝒃_𝒊全为非负值。决策变量𝒙_𝒋的取值全为非负值。四、标准型线性规划解的概念

；

max z=CX四、标准型线性规划解的概念

；；

五、线性规划问题的图解法

图解法是一种只能求解两个决策变量的线性规划问题的方法，不能解决多个决策变量的问题。但它有助于直观了解线性规划问题，并有助于后面章节介绍的单纯形法的理解。（一）图解法的基本步骤例6-1-7利用图解法求解下列线性规问题；

五、线性规划问题的图解法

图6-1-2可行域图6-1-1五、线性规划问题的图解法

；

图6-1-3目标函数

图6-1-4图解法求解

五、线性规划问题的图解法

（二）图解法的几种可能结果在使用图解法求解线性规划问题的过程中，除了存在上述唯一最优解的情况，还可能存在其他情况，如存在多个最优解，存在无界解或无可行解，下面分别进行讨论与总结。（1）可行域为封闭的有界区域。①存在唯一的最优解，如图6-1-5所示。②存在无穷多的最优解，如图6-1-6所示。

图6-1-5存在唯一的最优解（1）

图6-1-6存在无穷多的最优解（1）五、线性规划问题的图解法

（2）可行域为非封闭的无界区域。①存在唯一的最优解，如图6-1-7所示。②存在无穷多的最优解，如图6-1-8所示。③存在无界解，如图6-1-9所示。（3）可行域为空集。可行域为空集，即约束条件不存在公共部分，这种情况下是无可行解的，如图6-1-10所示。图6-1-7存在唯一的最优解（2）

图6-1-8存在无穷多的最优解（2）

图6-1-9存在无界解

图6-1-10无可行解

五、线性规划问题的图解法

（三）图解法基本结论对于只有两个决策变量的线性规划问题，可以利用图解法求解，从几何的角度得出以下几个结论。（1）线性规划问题的可行域为一个有界或无界的凸多边形，其顶点个数是有限个，且对应该问题的基可行解。（2）若线性规划问题有唯一的最优解，那么最优解一定可在可行域的某个顶点（基可行解）上找到。（3）求解线性规划问题时，解的可能情况有唯一最优解、无穷多最优解、无界解、无可行解等。；

六、线性规划的对偶问题与灵敏度分析

（一）对偶问题的提出对偶理论是线性规划问题中最重要和有意义的概念。它的基本思想是每个线性规划问题都有一个对偶问题，求出一个问题的解时，也同时给出了对偶问题的解。通过实际例子可以看出对偶问题的意义。在例6-1-1中，XY公司利用现有的资源生产两种产品时，其线性规划问题为；

六、线性规划的对偶问题与灵敏度分析

现在从另一角度提出问题。假如某个公司想购买XY公司的资源，它至少应付出多大代价，才能使XY公司愿意放弃其目前的生产活动，出售自己的资源？很显然，如果要使XY公司出让自己的资源，其基本条件应当是出让代价不低于自己用相同数量的资源组织生产活动时所能够获取的赢利。如果单位设备台时和工时的出让代价分别用y1和y2来代表，因为XY公司生产一件产品Ⅰ需要用到2单位的设备台时和2单位的工时，可以赢利100元；生产一件产品Ⅱ需要用3单位的设备台时和1.5单位的工时，可以赢利120元，所以y1、y2的取值应该要满足这家公司希望用最小代价把XY公司的全部资源收买过来，故有显然，yi

≥0（i=1，2），再综合上式有

对于上述的两个线性规划问题，通常称前者为原问题，称后者为前者的对偶问题。六、线性规划的对偶问题与灵敏度分析

（二）对称形式下对偶问题的一般形式定义6.1.1满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束；其约束条件为当目标函数求极大值时均取“≤”号，当目标函数求极小值时均取“≥”号[20]。对称形式下，线性规划原问题的一般形式为；

六、线性规划的对偶问题与灵敏度分析

；

六、线性规划的对偶问题与灵敏度分析将上述对称形式下线性规划问题的原问题与对偶问题进行比较，如下表所示。原问题与对偶问题的对比；

原问题对偶问题A约束系数矩阵其约束系数矩阵的转置b约束条件的右端常数项向量目标函数中的价格系数向量C目标函数中的价格系数向量约束条件的右端常数项向量目标函数约束条件六、线性规划的对偶问题与灵敏度分析

六、线性规划的对偶问题与灵敏度分析将上述对称形式下线性规划问题的原问题与对偶问题进行比较，如下表所示。

原问题与对偶问题的对比；

原问题对偶问题A约束系数矩阵其约束系数矩阵的转置b约束条件的右端常数项向量目标函数中的价格系数向c量C目标函数中的价格系数向量约束条件的右端常数项向量目标函数约束条件六、线性规划的对偶问题与灵敏度分析

；

六、线性规划的对偶问题与灵敏度分析

；

七、线性规划软件求解（一）用Excel求解线性规划模型例6-1-10用Excel求解线性规划模型：；

七、线性规划软件求解先将线性规划模型数据输入Excel表格中点击“数据”→“规划求解”按钮，弹出上图所示的“规划求解参数”对话框，依次添加规划求解参数。点击“求解”按钮，根据计算提示可知，得到了一个最优解，满足所有的约束条件及目标函数值的最大化要求，在“规划求解结果”对话框中选中“保存规划求解结果”单选按钮，然后点击“确定”按钮，可以得到求解的结果；

模型数据输入求解结果（Excel）求解步骤七、线性规划软件求解（二）用LINGO软件求解线性规划问题LINGO（LinearInteractiveandGeneralOptimizer）即“交互式的线性和通用优化求解器”，可用于求解线性规划和非线性规划的大规模优化问题，其建模和输入方便，执行速度快。例6-1-11有如下线性规划问题，请用Lingo软件求解。；

七、线性规划软件求解对于决策变量少、约束条件不多的线性规划模型，只需按照LINGO程序书写规则，将线性规划模型直接输入。；

点击“Run”按钮

输入线性规划模型

求解结果（LINGO）七、线性规划软件求解（三）用管理运筹学软件求解线性规划问题例6-1-12某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源限制，如下表所示。产品信息表

问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最大？；

III资源限制设备台时/小时11300原料A/kg21400原料B/kg01250单位产品获利/元50100

七、线性规划软件求解

软件求解过程如下1234七、线性规划软件求解；

整数规划问题02一、整数规划的一般形式

整数规划的一般形式如下：例6-2-1某公司拟用集装箱托运甲、乙两种货物，货物信息（每箱的体积、质量、利润及托运限制）如下表所示。两种货物各托运多少箱，可使所获利润最大?货物信息一、整数规划的一般形式

二、含0-1变量的整数规划0-1变量作为逻辑变量（LogicalVariable），常用于表示系统是否处于某一特定状态或者决策时是否采取某个方案，因此提供选择的功能，即整数规划建模上的灵活性在很大程度上是由于使用了0-1变量（又称为二进制变量）。例6-2-2背包问题：一个登山队员需要携带的物品有食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等，物品的质量和重要性系数如下表所示。设登山队员可携带的最大质量为25kg，试选择该队员应携带的物品。表6.2.2物品质量和重要性函数

三、混合整数规划

例6-2-4高压容器公司制造小、中、大三种尺寸的容器，所需资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如下表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器设备有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号容器是100万元，中号容器为150万元，大号容器为200万元。请制定一个生产计划，使获得的利润最大。

制造一个容器所需的各种资源的数量资源小号容器中号容器大号容器金属板/吨248劳动力/（人/月）234机器设备/（台/月）123三、混合整数规划

三、混合整数规划

四、整数规划模型求解方法

五、指派问题及其解法

（一）指派问题的数学模型例6-2-6有5个工人，要指派他们分别完成5项工作，各人完成各项工作所需时间如下表所示。指派哪个人去完成哪项工作，才能使得消耗的总时间最短？各人完成各项工作所需的时间工作工人ABCDE甲56841乙73579丙18656丁63785戊97268五、指派问题及其解法

为了解决这个问题，首先引入0-1变量xij，令用z表示5个工人分别完成5项工作所消耗的总时间，该问题的目标函数为约束条件为五、指派问题及其解法

五、指派问题及其解法

六、整数规划软件求解

（一）Excel求解用Excel对整数规划问题进行建模就是在对线性规划问题进行建模的基础上，如果要求所有决策变量取整数，则在约束条件中进行变量设置。对于例6-2-1，用Excel对其建模。对例6-2-1建模其中，约束条件格F2的命令为“=sumproduct(B2：B3，E2：E3)”；约束条件格F3的命令为“=sumproduct(C2：C3，E2：E3)”；目标函数格F5的命令为“=sumproduct(D2：D3，E2：E3)”。

规划求解选项设置点击“规划求解选项”对话框中的“确定”按钮，再点击“规划求解参数”对话框中的“求解按钮”，得到最优解。例6-2-1的求解结果（Excel）六、整数规划软件求解

（二）LINGO软件求解对例6-2-1进行求解。LINGO程序如下：MODEL：MAX=600*x1+400*x2；2*x1+4*x2<=13；200*x1+100*x2<=700；@gin(x1)；!变量x1为整数；@gin(x2)；!变量x2为整数；End例6-2-1的求解结果（LINGO）

运输问题03一、运输问题的数学模型

一、运输问题的数学模型

销售地B1B2…Bn生产地A1c11c12…c1nA2c21c22…c2n

Amcm1cm2…cmn单位运价表销售地B1B2…Bn生产地A1…A2…

Am…平衡表

一、运输问题的数学模型

一、运输问题的数学模型

二、运输问题的基本性质

三、运输问题软件求解

（一）运输问题Excel求解1．产销平衡运输问题Excel求解例6-3-1某公司有3个生产同类产品的加工厂（生产地），生产的产品由4个销售点（销售地）出售，各生产地的产量、各销售地的销量（假定单位均为吨）及将产品由各生产地运往各销售地的单位运价（元/吨）如表所示，应如何调运才能使总费用最小?

产量、销量单位运价表（1）

销售地产量/吨B1B2B3B4生产地A14124118A2210395A38511611销量/吨4767

三、运输问题软件求解

用Excel对运输问题建模类似于用Excel对线性规划问题建模。其中，约束条件格F12、F13、F14的命令分别为“=sum(B12：E12)”“=sum(B13：E13)”“=sum(B14：E14)”；约束条件格B15、C15、D15、E15的命令分别为“=sum(B12：B14)”“=sum(C12：C14)”“=sum(D12：D14)”“=sum(E12：E14)”；目标函数格C17的命令为“=sumproduct(B5：E7，B12：E14)”。给定可变单元格与约束条件后，点击“选项”按钮进行规划求解选项设置。对例6-3-1建模规划求解选项设置（1）三、运输问题软件求解

2．产销不平衡运输问题Excel求解利用Excel求解产销不平衡的运输问题时

，我们可以不用将其转变为产销平衡运输问题而直接进行求解。例6-3-1的求解结果（Excel）三、运输问题软件求解

（二）运输问题管理运筹学软件求解例6-3-3某公司从三个生产地A1、A2、A3将产品运往四个销售地B1、B2、B3、B4，各生产地的产量、各销售地的销量和将产品由各生产地运往各销售地的单位运价（万元/吨）所示，问：应如何调运使总运输费用最小?产量、销量、单位运价表设xij为从生产地Ai运往销售地Bj的运输量，得到运输量表所示。运输量表

销售地产量/吨B1B2B3B4生产地A1675314A2842727A35910619销量/吨22131213

销售地产量/吨B1B2B3B4生产地A114A227A319三、运输问题软件求解

整理可得三、运输问题软件求解

将上述问题用单位运价表表示产量、销量、单位运价表（4）运行管理运筹学软件，选择“运输问题”模块，点击“新建”按钮，设置目标函数，输入产地个数、销地个数，点击“确定”按钮后，工作区中会出现单位运价表。按照各个生产地到销售地的运价情况完善单位运价表。点击“解决”按钮，输出求解结果。求解结果显示：此运输问题的成本为232万元，最佳运输方案为：从生产地