数学建模案例之线性规划共59页

第一章 线性规划§1 线性规划在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。

此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。

自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。

特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。

1.1 线性规划的实例与定义例1某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。

生产甲机床需用B A 、机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用C B A 、、三种机器加工，加工时间为每台各一小时。

若每天可用于加工的机器时数分别为A 机器10小时、B 机器8小时和C 机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？上述问题的数学模型：设该厂生产1x 台甲机床和2x 乙机床时总利润最大，则21,x x 应满足（目标函数）2134m ax x x z += (1)s.t.（约束条件）⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤+0,781022122121x x x x x x x （2）这里变量21,x x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式是问题的约束条件，记为s.t.(即subject to)。

由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。

总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。

在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。

而选适当的决策变量，是我们建立有效模型的关键之一。

1.2 线性规划的Matlab 标准形式线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。

题的求解过程。
混合整数线性规划问题求解
要点一
混合整数线性规划问题的复杂性
混合整数线性规划问题是指包含整数变量的线性规划问题 。由于整数变量的存在，混合整数线性规划问题的求解变 得更加困难，需要采用特殊的算法和技术来处理。
要点二
混合整数线性规划模型的求解方 法
为了解决混合整数线性规划问题，可以采用一些特殊的算 法和技术，如分支定界法、割平面法等。这些方法能够将 问题分解为多个子问题，并逐步逼近最优解，从而提高求 解效率。
目标函数的类型
常见的目标函数类型包括最小化、最大化等。
确定约束条件
约束条件
01
约束条件是限制决策变量取值的条件，通常表示为数学不等式
或等式。
确定约束条件的原则
02
根据问题的实际情况，选择能够反映问题约束条件的条件作为
约束条件。
约束条件的类型
03
常见的约束条件类型包括等式约束、不等式约束等。
线性规划模型的建立
也可以表示为
maximize (c^T x) subject to (A x geq b) and (x leq 0)。
线性规划的应用场景
生产计划
物流优化
在制造业中，线性规划可以用于优化生产 计划，确定最佳的生产组合和数量，以满 足市场需求并降低成本。
在物流和运输行业中，线性规划可以用于 优化运输路线、车辆调度和仓储管理，降 低运输成本和提高效率。
初始基本可行解
在线性规划问题中，一个解被称为基 本可行解，如果它满足所有的约束条 件。
在寻找初始基本可行解时，可以采用 一些启发式算法或随机搜索方法，以 快速找到一个可行的解作为起点。
初始基本可行解是线性规划问题的一 个起始点，通过迭代和优化，可以逐 渐逼近最优解。

ai1 x1+ai2 x2+ … +ain xn+s = bi 11
1.线性规划的概念
当约束条件为
ai1 x1+ai2 x2+ … +ain xn ≥ bi
时，类似地令
s=(ai1 x1+ai2 x2+ … +ain xn)- bi 显然，s 也具有非负约束，即s≥0，
这时新的约束条件成为
ai1 x1+ai2 x2+ … +ain xn-s = bi
生产所占用的机时数不能超过65，于是我
们可以得到不等式：3 x1 + 2 x2 ≤ 65； 对设备B，两种产品生产所占用的机
时数不能超过40，于是我们可以得到不等
式：2 x1 + x2 ≤ 40； 3
1.线性规划的概念
对设备C，两种产品生产所占用的
机时数不能超过75，于是我们可以得到
不等式：3x2 ≤75 ；另外，产品数不可 能为负，即 x1 ,x2 ≥0。同时，我们有
4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0
20
2.线性规划的图解法
线性规划的图解法(解的几何 表示)对于只有两个变量的线性规 划问题，可以二维直角坐标平面 上作图表示线性规划问题的有关 概念，并求解。图解法求解线性 规划问题的步骤如下：
x2=25，最优值z
划 =
的 最 优 解 x1=5 、
70000。即最优方
案为生产甲产品5件、乙产品25件，
可获得最大利润为70000元。

已知该部门现有资金100万元，试为该部门确定投资 方案，使得第五年末它拥有的资金本利总额最大？
1）模型建立。
①决策变量。决策变量为每年年初向四个项目的投资 额，设第i(i=1,2,3,4,5)年年初向A,B,C,D(j=1,2,3,4) 四个项目的投资额为xij（万元）。 ②目标函数。设第五年年末拥有的资金本利总额为z， 为了方便，将所有可能的投资列于下表1.2
表1.3 三个货舱装载货物的最大容许量和体积
前舱 重量限制/t 10
中舱 16
后舱 8
体积限制/m3
6800
8700
5300
现有四类货物供该货机本次飞行装运，其有关信息 如表1.4，最后一列指装运后获得的利润。
表1.4 四类装运货物的信息
货物1 货物2 货物3 货物4
质量/t 18 15 23 12
空间/(m3/t) 480 650 580 390
利润(元/t) 3100 3800 3500 2850
应如何安排装运，使该货机本次飞行利润最大？
1）模型假设。问题中没有对货物装运提出其他要 求，我们可做如下假设：
①每种货物可以分割到任意小； ②每种货物可以在一个或多个货舱中任意分布； ③多种货物可以混装，并保证不留空隙。 2）模型建立。 ①决策变量：用xij表示第i种货物装入第j个货舱的重 量（吨），货舱j=1,2,3分别表示前舱、中舱、后舱。
年份
1 x11
2 x21 x23 x24
3 x31 x32 x34
4 x41
5
项目
投资限额/万 元
A B C D
年年末回收的本利之和，于是， 目标函数为 ③约束条件 z 1.15x41 1.25x32 1.40 x23 1.06 x54