1.3 线性规划问题建模
建模是解决线性规划问题的重要环节。从实践的角度来讲，一个正确数模的建成，标志着问题的解决接近完成一半，答案在计算机上由线性规划软件运行就会很快获得。正确建模要求建模者熟悉规划问题的基本内容，明确目标要求和约束条件，要通过大量的调查和统计资料获取原始的可靠数据。这些要求对于建立一个较复杂的实际模型是要花费相当大的工作量的。对于初学者来说，怎样从问题的内容出发，分析和认识问题，善于有条理地表述出来，掌握建模过程是十分重要的技术。
线性规划适用解决的问题面很广，因此很难有一个统一的建模标准，这就使建模成为一种带技巧性的工作。即使如此，建模过程还是有一定规律的，归结为以下三个步骤。
第一步 分析问题的要求，确定决策变量。
第二步 找出问题目标要求，确定目标函数。
第三步 分析决策变量所受的限制，列出约束条件。
本节通过经济管理领域中几个典型问题来说明建模过程，同时介绍不同类型问题的建模过程，使得对线性规划的应用领域和它的现实意义有进一步的认识。
1.3.1 资源合理利用问题
资源合理利用是企业编制生产计划时经常考虑的实际问题。其任务是企业（也可以是一个地区，甚至整个国家）如何规划和调配它的有限资源以达到生产的目的，并使企业获取最大的利润；或使资源、材料耗费最少，从而使生产成本为最小。现举例说明。
【例1-2】某厂生产A、B两种产品，都需用煤、金属材料、电力等资源。制造A产品1吨需用煤6吨、金属材料80千克、电力50千瓦；制造B产品1吨需用煤8吨、金属材料50千克、电力10千瓦。现该厂仅有煤540吨、电力2000千瓦和金属材料4000千克可供利用，其他资源可以充分供应。又知：A、B产品能得到的利润分别为6×103元/吨和5×103元/吨。问：在现有这些资源条件下，应生产多少吨A和B产品，使企业获得利润最大？试建立该问题的数学模型。
解：这是一个典型的资源合理利用问题，将问题转化为表1-2，辅助建模。
表1-2 产品生产基础数据表
（1）确定决策变量。要求回答的是A、B产品的生产量，现用x1和x2分别表示A、B产品的生产量（吨）。
（2）确定目标函数。工厂是要求利润为最大，设Z表示企业利润，则有
Max Z=6x1+5x2（103元）
（3）确定约束条件。根据该问题三种资源（煤、金属材料、电力）可用量的限制，可建立这三种资源限制约束条件如下。
煤： 6x1+8x2≤540（吨）
金属材料： 80x1+50x2≤4000（千克）
电力： 50x1+10x2≤2000（千瓦）
非负限制： x1, x2≥0
可得该问题线性规划数模如下：
资源合理利用问题的一般数模如下：假设某个企业有m种资源，已知每种资源的数量为bi （i=1,2, …,m）；该企业能生产n种产品（xj为第j种产品的产量，j=1,2, …,n），已知生产每一种产品单位产量所消耗的各种资源数量，我们用aij表示第j种产品对第i种资源单耗；设各种产品的价格为已知，用cj表示第j种产品的单价；在现有资源条件下如何规划生产，使得产值最大。数模如下：
1.3.2 运输问题
在国民经济中如何组织好一个企业、一个地区乃至全国范围内的物资调运工作是十分重要的。譬如某类产品有若干个生产地，已知每个生产地的产量；这类产品有若干个消费地，各地需求量也知道。假如总产量和总消费量恰好相等，由各产地运到各消费地的运输单价已知，现如何来编制一个最优的运输计划，使总的运输费用为最小。
【例1-3】某地有三个有色金属矿A1、A2、A3，生产同一种金属矿石，A1矿的年产量为100万吨， A2矿为80万吨，A3矿为50万吨。矿石全部供应4个冶炼厂，B1厂的全部需求量为50万吨，B2厂为70万吨，B3厂为80万吨，B4厂为30万吨。总产量恰好等于总需求量，矿石由各矿山运到冶炼厂的单位运价已知，如表1-3所示。问：如何安排运输，使各矿山的矿石运到冶炼厂，满足各厂的需要，且总运输费用最小？试建立该问题的数学模型。
表1-3 运价表（单位：元/吨）
解：这是一个运输问题，要制订最优运输计划使总运输费用最小。
（1）确定决策变量。要确定各矿山运给冶炼厂多少矿石，使总运输费用最小，故设xij表示第i个矿山运到第j个冶炼厂的矿石量，可列表1-4。
表1-4 运输计划表
（2）确定目标函数。本题给出的表1-4中的单位运价就是价值系数cj（元/吨）。问题的目标是求总运输费用最小，设Z表示总运输费用，故目标函数为
Min Z=1.5x11+2x12+0.3x13+3x14+7x21+0.8x22+1.4x23+2x24+1.2x31+0.3x32+2x33+2.5x34（万元）
（3）确定约束条件。由表1-4可以写出
运输问题的一般数模可表达如下：设某产品有m个生产地，其产量分别为ai（i=1,2, …, m）；该产品有n个消费地，需要量分别为bj（j=1,2, …, n），并且产销平衡，即总产量等于总需求量。以cij表示第i产地运到第j消费地的单位产品运价。则数模为：
1.3.3 合理下料问题
合理下料是许多工业部门中经常遇到的问题。例如机械加工时，常常将一定的条形金属原材料或板料切割成若干段或块，加工成所需的毛坯。在一般情况下，材料不可能被完全利用，就有边角余料要处理，处理不好就会造成大材小用，优材劣用，甚至当成废物收集，搬运回炉。这样产品材料单耗高，成本也就高。因此如何最大限度地减少边角余料，提高原材料利用率，就是提高经济效益的规划问题。现举一例说明。
【例1-4】有一批长度为180厘米的钢管，需截成70厘米、52厘米和35厘米三种管料，如图1-2所示。它们的需求量应分别不少于100个、150个和100个。问：应如何下料才能使钢管的余料为最少？试建立该问题的数学模型。
图1-2 钢管长度及其管料尺寸示意图
解：这是一个合理下料问题，下料方案是在满足管料尺寸条件下可能的各种下料方式中进行选择，利用上图列出所有的下料方式（共有8种），如表1-5所示。
表1-5 下料方式列表
（1）确定变量。设xj为第j种下料方式所用的钢管根数，j=1,2, …,8。
（2）确定目标函数。要求总余料最少，设总余料为Z，则
Min Z = 5x1+6x2+23x3+5x4+24x5+6x6+23x7+5x8（厘米）
（3）确定约束条件。获得的管料个数不少于需求量，即：
70厘米管料个数需求约束：2x1+x2+x3+x4≥100（个）
52厘米管料个数需求约束：2x2+x3+3x5+2x6+x7≥150（个）
35厘米管料个数需求约束：x1+x3+3x4+2x6+3x7+5x8≥100（个）
非负约束：xj≥0，并且为整数，j=1,2, …,8
于是该下料问题的线性规划数模如下：
这是一个整数线性规划数学模型，即变量要求取整数。如果数学模型中所有的变量都要求取整数，则该数学模型称为纯整数线性规划数学模型；如果数学模型中一部分变量要求取整数，则该数学模型称为混合整数线性规划数学模型。
合理下料问题的一般数学模型如下：假设需要切割m种零件毛坯，其数量分别以bi表示（i=1,2, …, m）；设可能有n种下料方式，并分别以a1j, a2j, …, amj表示第j种下料方式每根原料（或每块板料）所切割出来的各种零件毛坯数量。设xj表示第j种下料方式所消耗的原材料根数，则有
1.3.4 分派问题
在生产管理中，常有为了发挥最大工作效率而优化分派人员的问题，现举一例说明。
【例1-5】设有A、B、C、D四件工作分派给甲、乙、丙、丁做，每项工作只能由一人来做，每个人只能做一项工作。希望适当安排人选，发挥各人特长又能使总的效率最大。表1-6表示各人对各项工作所具有的工作效率。
表1-6 人员工作效率表
解：这是一个分派问题，要制订最优分派计划使总效率最大。
（1）确定决策变量。设xij为分派第i个人从事第j项工作，xij= 1、0（分派与否），如果xij=1，说明把第j项工作分派给第i人来做；如果xij=0，表示第j项工作不分派给第i人来做。因此，xij只能取0和1两个值中之一，可列表1-7。
表1-7 人员分派计划表
（2）确定目标函数。总效率可以认为是各人从事每项工作效率之和，设总效率为Z，
则目标函数为：
Max Z=0.6x11+0.2x12+0.3x13+0.1x14+0.7x21+0.4x22+0.3x23+0.2x24+0.8x31+1.0x32+0.7x33+0.3x34+0.7x41+0.7x42+0.5x43+0.4x44
（3）确定约束条件。由题意知，每个人只能被分派一项工作（且必须做一项工作），每项工作只能由一个人来做（且必须由一个人来做），由此可列出以下约束条件方程：
上述人员分派问题在运筹学中被称为“指派问题”或“分派问题”，这是一个0-1线性规划数学模型，即变量要求取0和1两个整数。如果数学模型中所有变量都要求取0和1，则该数学模型称为纯0-1线性规划数学模型；如果数学模型中只有一部分变量要求取0和1，则该数学模型称为混合0-1线性规划数学模型。
分派问题的一般数模为：设有n项工作由n个人来做，每个人必须做一项工作且只能做一项工作；每项工作必须由一个人来做且只能由一个人来做。则该问题的数模如下：
1.3.5 投资方案选择问题
在经济管理中，常有选择最佳投资方案使经济效益最大的问题，现举一例说明。
【例1-6】某炼油公司为提高炼油能力和增加企业经济效益，经研究有5种技术改造的投资方案可供选择，它们所需的投资费用和年利润如表1-8所示。其中：方案1和方案2只能选择其中一种，不能兼而实现；并且如选择方案2，则方案3必须同时选择，或者都不选择。现该公司可供支配的资金总额为：第一年有650万元，第二年仅有460万元。技术履行的结果要求至少应增加出油能力500桶/天，但又不得超过1100桶/天，试确定该公司年总利润最大的投资方案。
表1-8 投资方案表
解：将该问题转换成如表1-9所示的投资方案表。
表1-9 建模辅助表
（1）确定决策变量。要求从五种投资方案中选择最优方案，设决策变量xj(j=1,2, …,5)表示第j方案的取舍，则当xj=1时，表示第j方案被采纳，反之，当xj=0时，表示第j方案被舍弃，所以决策变量xj的取值仅有1和0两种值。
（2）目标函数。要求公司年总利润最大，设总利润为Z，则
Max Z =100x1+200x2+50x3+30x4+20x5（万元）
（3）约束条件。本例的约束条件有投资总额约束（包括第一年和第二年两个约束条件）、生产能力增加约束（包括下限和上限两个约束）、方案制约条件（包括1、2方案不能兼而实现和2、3方案必须同时选择两个约束条件），以及变量的取值限制，即有：
1.3.6 选点决策问题
在现实中，常有选点决策问题，现举一例说明。
【例1-7】某公司拟在A、B、C、D、E 5个城市中建立若干产品经销联营点，各处设点都需资金、人力、设备等，需求量以及能提供的利润各处不同，有些点可能亏本，但却能获得贷款和人力等。假设数据已知，如表1-10所示，为使总利润最大，问：厂方应做何种最优选点决策？
表1-10 城市选点资源表
解：这是一个选点决策问题，要确定在哪几个城市建立产品经销联营点，才能使总利润最大。
（1）确定决策变量。要求从五个城市中选择最优产品经销联营点，设决策变量xj(j=1,2, …,5)表示第j个城市的取舍，所以决策变量xj的取值仅有1和0两种值。
（2）目标函数。要求公司总利润最大，设总利润为Z，则
Max Z =4.5x1+3.8x2+9.5x3-2x4-1.5x5（万元）
（3）约束条件。根据该问题三种资源（资金、人力、设备）可用量的限制，可建立这三种资源限制约束条件如下：
资金： 4x1+6x2+12x3-8x4+x5≤20（百万元）
人力： 5x1+4x2+12x3+3x4-8x5≤15（人）
设备： x1+x2+x3 ≤2（套）
可得该问题线性规划数模如下：
线性规划所能描述的问题当然远远超出以上所举的例子范畴，限于篇幅，不一一罗列。