今天我们认识几个最优化问题的典型实例。它们分属于最优化问题的不同类别,它们的共同点是在给定的约束条件下,如何在某种范围内选取一些设计变量的取值,使得一个或者多个既定目标达到最优状态。不同之处就是设计变量、目标函数、约束条件这三要素的不同,而这三要素的不同也就决定了不同问题在解法上的差异。
某工厂生产A、B两种产品,制造ItA产品需要耗煤8t,耗电3kW,耗时2个工作日∶制造1tB产品需要耗煤4t,用电4kW,耗时9个工作日。已知制造1t产品A和B分别可以获利6000元和8000元。现在该厂原料有煤300t、电100kW,如果需要在200个工作日内生产这两种产品并达到利润最大,应当如何安排A和B的生产数量(参考数据表1)?
设x1和x2分别代表A、B两种产品的计划生产数(单位∶t),f表示利润(单位∶千元),则我们所需要解决的问题就是如何确定 A、B的生产数量(即确定x1和x2的数值),既可以充分利用资源,又可以使利润最大化。依据题意,生产产品A可获利6x1(千元),生产产品B可获利8x2(千元),则可以得到目标函数为f=6x1+8x2,优化设计的目标就是使得函数最大化。
要实现目标的优化必然要考虑到资源供应量的限制,在该问题中就是用煤、用电和用时。例如用煤,生产产品A需要消耗煤8x1(t),生产产品B需要消耗煤4x2(t),而该厂有煤360t。即煤的消耗总量应该小于360t,写成约束条件即
同理,对电力资源的消耗不得高于其供应量200kW,对劳动力时间的消耗不得高于300 工作日,这些限制可以写成如下约束条件∶
同时,每种产品可以生产一定数量或者不生产,故还需要满足非负限制,即
综合以上几点,该问题可以表述为如下的形式∶
s.t.是subject to的缩写,表示约束条件,该问题的表述即为∶在满足资源约束的条件下,求出产品A、B的产量x1和x2,使得利润总额f达到最大。可以看到,目标函数和约束条件均是线性的,故这是一个典型的线性规划问题。
假设某个项目由4项连续的任务构成,即完成了任务1之后才能开始任务2,完成了任务2之后才能开始任务3,以此类推;并且规定由项目组中的甲、乙、丙、丁4名成员每人完成且仅完成其中的一项任务,4个项目组成员分别完成4项任务的时间如表2所示。应该如何分配这些任务,即让哪个成员去完成哪个任务,可以使得花费的总时间最短?
各项目组成员完成各任务所需时间表2
首先,假设设计变量表达成如下形式∶
其中,xij为0-1变量,i代表项目组成员的序号,j代表任务的序号,则该变量代表的意义为∶
x11、x12、x13、x14分别代表指派甲完成任务1、任务2、任务3、任务4;
x21、x22、x23、x24分别代表指派乙完成任务1、任务2、任务3、任务4;
x31、x32、x33、x34分别代表指派丙完成任务1、任务2、任务3、任务4;
x41、x42、x43、x44分别代表指派丁完成任务1、任务2、任务3、任务4。
则效率矩阵可以表达为∶
该问题的目标就是选择一种合适的一对一的组合,使得最后所花费的时间总和最小。根据上述假设,可以得到目标函数,即所花费的总时间为∶
下面探讨约束条件,因为按照题意,每个人只能完成一项任务,故有∶
同时,由于每项工作有且仅有一人去完成,故有
综合以上分析,得出该问题可以表述成如下形式∶
上述问题即是,在设计变量的值要么取0、要么取1和满足限制条件(每个人完成且仅完成一项任务、每项任务有且仅有一人完成的这种一一对应的关系)的前提下,使得目标函数f达到最小。这是一个典型的分派问题,属于整数规划问题中的一类。
某企业有n个项目可供选择投资,并且至少要对其中一个项目投资。已知该企业拥有总资金A元,投资于第i(i=1,2,…,n)个项目需花资金ai元,并预计可收益bi元。试选择最佳投资方案。
要求解上述问题,首先要决定设计变量。可以设定该问题的目标是要在选择相应投资项目之后使得投资收益率最大,在这个过程中要确定的是对于某项目是投资还是不投资。于是令设计变量为x(i=1,2,…,n),当决定投资第i个项目时,xi=1;当决定不投资第i个项目时,xi=0。
由条件可知,投资的总额可以表示为
而投资第i个项目的预计收益为b元,投资预计的总收益为
我们设定的目标是使得投资收益率最大,故目标函数应为总收益和总投资额的比值,即
那么优化的目标就是使得f取得最大值。
下面继续探讨该问题的限制条件,由于该公司至少要对一个项目投资,并且总的投资金额不能超过总资金A,故有限制条件∶
另外,由于xi,(i=1…,n)只取值0或1,这个条件还可以写成如下形式∶
最佳投资方案应是在投资额尽可能小的前提下使得总收益额尽可能大的方案,所以这个最佳投资决策问题归结为在总资金及设计变量(取0或1)的限制条件下,极大化总收益和总投资之比。根据上面的各项分析,可以得出其数学模型为∶
上面例题是在一组等式或不等式的约束下,求一个函数的最大值(或最小值)问题,其中目标函数或约束条件中至少有一个非线性函数,这类问题称为非线性规划问题。关于以上规划类问题的具体解法我们会在后续讲到。
2022国赛备战交流群群
更多数模相关内容请于公众号内输入关键词搜索往期文章
如有任何疑问与意见请于评论区留言