3.1 线性规划的数学模型_运筹学基础-QQ阅读男生都市网

上QQ阅读APP看本书，新人免费读10天

设备和账号都新为新人

3.1 线性规划的数学模型

3.1.1 线性规划问题示例

例3.1.1（弹药使用优化问题）王强所在部队拟组织一次炮兵实弹训练，涉及两型炮弹的使用问题。已知负责运输炮弹的可用车辆共8台，每辆运输车在可用时间内只能运输Ⅰ型炮弹1个基数弹药基数是弹药供应的一种计算单位，如1个基数120发等，基数简单好记、便于保密，可以给军事实践活动带来很大方便，不同级别、不同用途时规定的基数不尽相同。或Ⅱ型炮弹0.5个基数；而每型弹药的可用总量有限，Ⅰ型炮弹可用总量为4个基数，Ⅱ型炮弹可用总量为3个基数（见表3-1-1）。已知两型炮弹的战斗力指数战斗力指数是对作战力量战斗能力的一种指数化度量，一般通过和某一规定标准进行比较获得。它是对作战单位完成任务能力的简化认识，可根据用途、层级和对象的不同选用不同的战斗力指数。分别为2和3，演习首长要求发挥最大的军事效益，则应该如何安排使用两种型号炮弹的数量，才能使总的战斗力指数最大？

表3-1-1　弹药使用优化问题中的数据

对这类问题可进行如下分析：演习需要就不同型号炮弹的使用数量（称为方案）进行决策，这种决策受到了运输车辆、总量等方面的限制（称为资源限量），而希望获取的战斗力最强（称为目标）。由此，这类问题需要对方案、资源限量和目标这3个方面进行分析并建模，表达出相关要素的数量和相互关系。首先，用定量化表达使用炮弹的不同决策方案，设、分别表示演习使用两型炮弹的数量，则(，)表示不同的方案；其次，对资源限制进行建模，考虑运输车辆的限制，用不等式表达为

同理，考虑弹药总量的限制，得到不等式：

显然，所用炮弹基数必须为非负数，即有

最后，考虑目标是达成最大战斗力指数，用表示战斗力指数，得到

综合上述分析，弹药使用优化的问题可以用数学模型表达为

对经济活动来说，往往也是运用资源达到一定目的一类的问题，如工厂使用原材料、设备等资源制造不同类型的产品，通过出售产品获取利润。一般性的问题：如何安排生产不同的产品，使得在资源总量受限情况下获利最多？

例3.1.2（工厂生产优化问题）某工厂拟生产甲、乙两种产品，已知生产每吨产品所需的设备台时台时指设备、特别多套设备在某一时间段内的工作总时间，如5台设备，每台工作2小时，计为10台时，多用于工业生产中。及A、B两种原材料的消耗，如表3-1-2所示，则应该如何安排生产使工厂获利最多？

表3-1-2　工厂生产优化问题中的数据

类似上面的分析过程，首先，用定量表达出工厂的不同决策方案，可设、分别表示工厂安排生产时甲、乙两种产品的产量，则(，)表达不同的方案；其次，考虑目标（获利最多）和设备台时与原材料两类资源的限制，构建工厂优化生产的数学模型请注意这里模型的形式，其中的符号和书写顺序不仅直观易读，也是一种表达惯例。为

这个模型和例3.1.1中的模型的形式一致，这也意味着，问题虽然来自不同的领域，但本质是一样的。

上面的例子考虑的都是如何获取最大的收益，要求目标函数最大化。有些时候目标函数可能是最小化的形式，表示完成任务的成本或代价最小。

例3.1.3（装备编配造价优化问题）某部拟组建一个战斗机编队，按照使命任务要求，编队的总载弹量不能小于32个单位，挂载的空空导弹数不小于48个单位，现共有3种型号的战斗机可供选择，A型、B型与C型，它们具有的最大载弹量及最大可挂载空空导弹数如表3-1-3所示。已知3种飞机的造价分别为9000万元、6000万元与4500万元，试求出造价最小且能满足任务要求的战斗机编队组建方案。

表3-1-3　装备编配造价优化问题中的数据

同上，对方案、资源限制和目标进行量化表达，设组建能够完成任务的战斗机A型、B型、C型分别为、、架，考虑载弹量和空空导弹数两方面的限制以及目标要求，该问题可用以下数学模型严格来说，本模型中变量表示战斗机的架数，应约束其为整数，则该模型将为整数规划模型，该类模型将在本书第6章中讨论，这里暂不考虑这一约束（实际上，本模型得到的确实是整数解）。来描述：

3.1.2 线性规划模型的形式

对于上面的例子，无论是目标求最大化，还是求最小化，都属于同一类优化问题，它们具有共同的特征：首先，问题本身都需要进行决策，存在需要“优化”的变量；其次，有一定的资源约束，表现为“在哪些方面受到限制？”即有一个或多个方面受到制约；最后，决策本身有明确的目标，表现为“想达成什么目标？”并且目标能够明确地用数量表达出来。如果将一个问题的这几个方面的特征都弄清楚，就可以对问题进行量化，建立数学模型，进行求解、检验并实际应用，这一过程也就是运筹学研究的工作步骤。模型特征总结如下。

（1）有可选方案，方案集合可用一组变量表示。允许在不同方案间进行选择，可用一组决策变量的所有可能取值表示全体方案集合，而其中一个具体取值就代表一个方案。

（2）存在一定的约束条件，且均可用线性表达式表达。在实际问题中总是存在各类资源约束，如时间、经费、原材料等方面。这里给出的模型要求这样的约束可以用线性等式或线性不等式表达出来。

（3）有一个可以线性表达的优化目标。问题有一个明确的目标，要求最大值或最小值，并且可用决策变量的线性函数（称为目标函数）表达出来。

将具有如上3个方面特征的数学模型称为线性规划模型。其一般形式为

（3-1-1）

在上面的线性规划模型中，式（3-1-1）称为目标函数，式（3-1-2）和式（3-1-3）统称为约束条件，其中式（3-1-3）中如果变量为大于等于0的，也称为变量的非负约束条件，有时方便起见，也将式（3-1-2）直接称为约束条件。

线性规划模型中所有表达式必须是线性的！这样的要求对于实际问题来说是否太强了？的确如此，在实际中很多问题可能无法用线性来表达，或者说强行用线性表达，失真太多，以至于求出的解没有实用价值。由此就有“非线性规划”模型的问题，可惜的是，非线性规划模型中除了少数特别的形式（如凸规划）得到了很好的解决，一般模型的求解非常困难，那么在根据实际问题建模的时候，就存在“模型”复杂性和实用性之间的平衡问题，需要研究者在两者之间寻求最好的平衡点，保证模型可以求解，又具有实用价值。

一个有意思的问题：既然线性规划模型求解相对简单，而一般非线性规划模型难以求解，那么能否将后者转化为前者进行求解？当然肯定不是所有的非线性模型都能转化，但若干特殊形式的确是可以转化的，如分式形式、最大值表达、分段线性、可分离乘积等。