谈谈线性规划模型的建立
谈谈线性规划模型的建立
一、建立线性规划模型的步骤:
(1) 根据实际问题,设置变量。变量,就是待确定的未知数,也称决策变量,记为x1,x2,„,xn或xj(j=1,2,„,n)。在线性规划中,通常要求变量非负。
(2) 确定目标函数。某个函数要达到最大值或最小值,也即问题要实现的目标,就是目标函数。目标是求最大值的,用max;求最小值的,用min。
(3) 分析各种资源限制,列出约束条件。约束条件,就是变量所要满足的各项限制,包括变量的非负限制。它是一组包含若干未知数的线性不等式或线性等式。资源包括人力、资金、设备、原材料、电力等,考虑资源时不要遗漏。要根据各种资源的限制,确定取等式或不等式。
(4) 写出整个线性规划模型。将目标函数与约束条件写在一起,就是线性规划模型。我们通常将目标函数写在前面,约束条件写在目标函数的后面。
二、产品决策问题
一般地,产品决策问题的变量就是产品的产量,目标函数就是利润函数,约束条件则要根据该产品所涉及的资源来考虑,此时要根据问题提出的要求考虑是取等式还是取小于等于不等式或大于等于不等式。
建立线性规划模型时,我们一般要先制作“资源配置分析表”:产品、资源限额置于列的位置,资源、利润置于行的位置,最后一列为“资源限额”对应的数据,最后一行为单位产品利润,中间的数据代表单位产品消耗资源定额。我们也可以将变量、等号或不等号同时放进该表中。
利用“资源配置分析表”,我们可以比较容易地写出线性规划模型:先由最后一行写出目标函数,再由各资源行分别写出一个约束条件,最后再附上变量非负限制。
例1 某企业在一个生产周期内生产甲、乙两种产品,这两种产品分别需要A,B,C,D四种不同的机床来加工,这四种机床的可用工时分别为1500,1200,1800,1400。每件甲产品分别需要A,B,C机床加工4工时、2工时、5工时;每件乙产品分别需要A,B,D机床加工3工时、3工时、2工时。又知甲产品每件利润6元,乙产品每件利润8元。试写出能获得最大利润的线性规划模型。
分析 将题中各数据及变量填入表1所示的“资源配置分析表”中,其中第2,3列为产品甲和乙,最后一列为各机床的工时限额,第2~5行分别代表各机床,并按题意取小于等于号,最后一行代表利润。利润行中变量与单位利润乘积的总和就是目标函数,每个资源行(机床A~D)就是一个约束条件,由此表可直接写出线性规划模型。
表1 资源配置分析表
解 设生产甲、乙两产品的产量分别为x1,x2件,显然,x1,x2≥0。 又设利润为S,则线性规划模型为:
maxS6x18x2
4x13x215002x3x120012 5x180012x21400x1,x20
三、配料问题
一般地,配料问题的变量就是配料的数量,目标函数就是成本函数,约束条件则
要根据该产品所涉及的配料成分或其它要求来考虑,并确定是取等式还是取小于等于不等式或大于等于不等式。
同样,我们一般要先制作“资源配置分析表”:配料、混合要求(或成分要求等)的数额置于列的位置,各项要求(或成分等)、成本置于行的位置。我们也可以将变量、等号或不等号同时放进该表中。
例2 某企业有两种化学原料A1,A2都含有三种化学成分B1,B2,B3。每千克原料A1含B1成分0.7千克、B2成分0.2千克、B3成分0.1千克;每千克原料A2含B1成分0.1千克、B2成分0.3千克、B3成分0.6千克。A1原料成本每千克500元,A2原料每千克300元。今需要B1成分至少100千克,B2成分至少50千克,B3成分至少80千克。试写出线性规划模型。
分析 将题中各数据及变量填入表2所示的“资源配置分析表”中,其中第2,3列为原料A1和A2,第4列为各化学成分最低要求的数额,第2~4行分别为各化学成分,并按题意取大于等于号,第5行代表成本。最后一行中变量与单位成本乘积的总和就是目标函数,第2~4行分别代表一个约束条件,由此表可直接写出线性规划模型。
表2 资源配置分析表
解 设需要A1,A2两种原料分别为x1千克、x2千克,显然,x1,x2≥0。 又设成本为S,则线性规划模型为:
minS500x1300x2
0.7x10.1x21000.2x0.3x50 12
0.1x10.6x280x1,x20
四、运输问题
一般地,运输问题的变量就是每个产地运往各销地的运输量,目标函数就是运输
总费用函数(每产地运往各销地的单位运价与相应运输量乘积的总和),约束条件则是各产地供应量的运出和各销地需求量的运进要求,供求平衡运输问题取等式,供求不平衡运输问题则要根据问题提出的要求考虑是取等式还是取小于等于不等式或大于等于不等式。
若问题没有给出“运输平衡表与运价表”,可先制作此表,并将变量填入运输平衡表中,单位运价与相应运输量乘积的总和就是目标函数,运输平衡表中各产地行、各销地列分别代表一个约束条件,再附上变量非负限制就可得到线性规划模型。
例3 某运输问题的运输平衡表(单位:吨)和运价表(单位:元/吨)如表3所示:
表3 运输平衡表与运价表
试写出使运输总费用最小的线性规划模型。
分析 本问题需要安排运输量,故各产地到各销地的运输量就是我们要考虑的变量(变量较多,我们可用单下标或双下标表示,本问题我们用单下标),并填入表中,如表4所示:
表4 运输平衡表与运价表
本问题要求运输总费用最小。设运输总费用为S,则目标函数(运输量与对应的单位运价乘积之和)为:
min S=8x1+6x2+7x3+4x4+3x5+5x6+7x7+4x8+8x9
对各产地的约束条件(运输平衡表中各行运输量之和等于对应的供应量)为:
x1x2x330
x4x5x645 xxx25
897
对各销地的约束条件(运输平衡表中各列运输量之和等于对应的需求量)为:
x1x4x760
x2x5x830 xx
x10
693
综合上述分析并附上变量非负限制,便可得到线性规划模型。
解 设产地A1运送到销地B1,B2,B3的运输量分别为x1,x2,x3(吨);产地A2运送到销地B1,B2,B3的运输量分别为x4,x5,x6(吨);产地A3运送到销地B1,B2,B3的运输量分别为x7,x8,x9(吨)。
又设运输总费用为S,则线性规划模型为:
minS8x16x27x34x43x55x67x74x88x9
x1x2x330xxx45
564
x7x8x925
x1x4x760xxx30
58
2
x3x6x910x0(j1,2,,9)j