数学建模：线性规划问题(超全)

线性规划问题的提出线性规划的基本概念线性规划的数学模型线性规划问题的标准形式继续返回第一节线性规划问题

及其数学模型问题的提出例:生产计划问题产品I产品2如何安排生产使利润最大？决策变量（Decisionvariables）目标函数（Objectivefunction）约束条件（Constraintconditions）可行域（Feasibleregion)最优解（Optimalsolution)基本概念问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。它是决策变量的函数指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。满足约束条件的决策变量的取值范围可行域中使目标函数达到最优的决策变量的值是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。第1步-确定决策变量设——I的产量——II的产量——利润第2步--定义目标函数MaxZ=x1+x2决策变量

MaxZ=2x1+3x2系数第2步--定义目标函数对我们有何限制?第3步--表示约束条件

x1+2x2

84x1

164x2

12x1、x2

0该计划的数学模型

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0x1

x2线性规划问题的共同特征一组决策变量X表示一个方案,一般X大于等于零。约束条件是线性等式或不等式。目标函数是线性的。求目标函数最大化或最小化

线性规划模型的一般形式ïïïîïïïíì³³=£+++³=£+++³=£++++++=0,...,,),(......................................................),(...),(......)min(21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxczMax线性规划问题的标准形式标准形式为:目标函数最大约束条件等式决策变量非负

简写为

用矩阵表示C—价值向量b—资源向量X—决策变量向量

minZ=CX等价于maxZ’=-CX“”约束：加入非负松驰变量一般线性规划问题的标准化例：

目标函数MaxZ=2x1+3x2约束条件x1+2x2

84x1

164x2

12x1、x2

0

minZ=CX等价于maxZ’=-CX“”约束：加入非负松驰变量一般线性规划问题的标准形化例：

“”约束：减去非负剩余变量；

Max例：可正可负（即无约束）；

解：标准形为线性规划模型举例(一)运输问题(二)布局问题(三)分派问题(四)生产计划问题(五)合理下料问题线性规划模型的条件（1）要求解问题的目标函数能用数值指标来反映，且为线性函数；（2）存在着多种方案；（3）要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。(一)运输问题设某种物资有m个产地，A1，A2，…，Am；联合供应n个销地：B1，B2，…，Bn。各产地产量（单位：吨），各销地销量（单位：吨），各产地至各销地单位运价（单位：元／吨）如下表所示。应如何调运，才使总运费最少？表中：ai表示产地Ai的产量(i=1，2，…，m)；

bj表示产地Bj的产量(j=1，2，…，n)；

cij表示AiBj间的单位运价（元／吨）(i=1，2，…，m;j=1，2，…，n)；单价（元／吨）销地产地产量（吨）

B1B2…BnA1A2

┇

Am销量（吨）

C11C12…C1nC21C22…C2n

┇

┇

…┇Cm1Cm2…Cmnb1b2…bna1a2┇

am

设xij表示由产地Ai运往销地Bj的物资数(i=1,2,…,m;j=1,2,…,n)。那么，上述运输问题的数学模型为：求一组变量xij(i=1,2,…,m;j=1,2,…,n)

的值,使它满足即(一)运输问题(Ⅰ)产销平衡

(Ⅰ)产销平衡

(Ⅱ)产销不平衡

约束条件产地Ai发到各销地的发量总和应等于Ai的产量各产地发到销地Bj的发量总和应等于Bj的销量调运量不能为负数0(Ⅰ)产销平衡的模型约束条件产地Ai发到各销地的发量总和应等于Ai的产量各产地发到销地Bj的发量总和应等于Bj的销量调运量不能为负数0(Ⅰ)产销平衡的模型(Ⅰ)产销平衡的模型()()()njmixnjbxmiaxijijiijmijnj,,1;,,2,1

0,,2,1

,,2,1

11

LLLL==³====åå==约束条件()()()njmixnjbxmiaxijijiijmijnj,,1;,,2,1

0,,2,1

,,2,1

11

LLLL==³====åå==(Ⅰ)产销平衡的模型这一问题的数学模型应为：

求一组变量的值,使它满足(Ⅱ)产销不平衡—产大于销(一)运输问题调运量不能为负数(Ⅱ)产销不平衡—产大于销的模型产地Ai发到各销地的发量总和不超过Ai的产量各产地发到销地Bj的发量总和应等于Bi的销量约束条件（二）布局问题作物布局

在n块地上种植m种作物，已知各块土地亩数、各种作物计划播种面积及各种作物在各块的单产（每亩的产量）如表—（与运输问题相似），问：如何合理安排种植计划，才使总产量最多。

产量（吨）

B1B2…BnA1A2

┇

Am销量（吨）

C11C12…C1nC21C22…C2n

┇

┇

…┇Cm1Cm2…Cmnb1b2…bna1a2┇

am（二）布局问题n块土地每亩的产量m种农作物总产量最多方法与运输问题类似销地产地单价（元／吨）(三）分派问题

设有n件工作分派给n人去做，每人只做一件工作且每件工作只分派一人去做。设Ai完成Bj的工时为。问：应如何分派才使完成全部工作的总工时最少。(完成全部工作的总工时最少）(三）分派问题解：设为Bj分派给人Ai情况：

Bj分派给Ai时，；不分派给Ai时，。那末这一问题的数学模型为：ijx1=ijx()njixij,,2,1,0L==

求一组变量的值，使目标函数的值最小。åå===nimjijijxcs11

()njixij,,2,1,L=分派问题的模型约束条件目标函数åå===nimjijijxcs11

min()()()njixnixnjxijijijnjni,,2,1,

1

0,,2,1

1,,2,1

111LLL======åå==或每件工作只分派一人去做每人只做一件工作每人对每件工作只有做与不做两种情况(四）生产组织与计划问题(Ⅰ)总的加工成本最低(Ⅱ)生产存储问题

某工厂用机床加工种零件。在一个生产周期，各机床只能工作的机时、工厂必须完成各零件加工数、各机床加工每个零件的时间（单位：机时／个）和加工每个零件的成本（单位：元／个）如表1及表2所示。问：在这个生产周期，怎样安排各机床的生产任务，才能既完成加工任务，又使总的加工成本最低。(Ⅰ)总的加工成本最低(四）生产组织与计划问题加工每个零件的时间零件机床在一周期能工作机时

B1B2…BnA1A2

┇

Am必须加工零件数

C11C12…C1nC21C22…C2n

┇

┇

…┇Cm1Cm2…Cmnb1b2…bna1a2┇

am表1：加工每个零件的时间(Ⅰ)总的加工成本最低(四）生产组织与计划问题表

2：加工每个零件的成本(Ⅰ)总的加工成本最低(四）生产组织与计划问题

零件加工每个零件的成本机床

B1B2…BnA1A2

┇

Am

d11d12…d1nd21d22…d2n

┇

┇…┇dm1dm2…dmn

求一组变量的值,使它满足

解：设为机床在下一生产周期加工零件的个数。这一问题的数学模型为：(Ⅰ)总的加工成本最低(四）生产组织与计划问题(加工零件个数不能为负数、分数）(机床加工各零件总机时不能超过能工作机时）(各机床加工零件的总数不能少于需要数）约束条件()()()njmixnjbxmiaxcijiijiijijninj,,2,1,,,2,1

,

0,,2,1

,,2,1

11LLLL==³=³=£åå==整数(Ⅰ)总加工成本最低的模型(四）生产组织与计划问题(Ⅰ)总加工成本最低的模型(四）生产组织与计划问题约束条件目标函数()()()njmixnjbxmiaxcijiijiijijninj,,2,1,,,2,1

,

0,,2,1

,,2,1

11LLLL==³=³=£åå==整数åå===njmiijijxds11

min某厂签订了5种产品上半年的交货合同。已知各产品在第月

的合同交货量，该月售价成本价及生产1件时所需工时。该厂第月的正常生产工时为，但必要时可加班生产，第月允许的最多加班工时不超过，并且加班时间内生产出来的产品每件成本增加额外费用元。若生产出来的产品当月不交货，每件库存1个月交存贮费元。试为该厂设计一个保证完成合同交货，又使上半年预期盈利总额为最大的生产计划安排。(四）生产组织与计划问题(Ⅱ)生产存储问题()5,,1L=ij()6,,1L=jijDijsijcijajjtjjt'ijc'ip解：设为种产品月份在正常时间内生产的数量，为第种产品月份在加班时间内生产的数量。该厂盈利总额为生产的5种产品销售价减去成本和库存费用。问题的限制条件有两项：

一是各个月的正常和加班的允许工时；

二是满足交货要求。

(四）生产组织与计划问题(Ⅱ)生产存储问题jijx'ijxiij该生产存储问题的线性规划模型为目标函数盈利总额=生产的5种产品销售价

—成本和库存费用(四）生产组织与计划问题

一是各个月的正常和加班的允许工时；二是满足交货要求。

约束条件()()()()ïïïïîïïïïíì==³=³+=£=£åååå====

,6)1,j,5;1,(i

0

6,,1

'6,,1

''6,,1

115151LLLLLijikikikjijijjijijxjDxxjtxajtxajkjkii

设用某原材料(条材或板材)下零件