第5章线性规划模板

机械优化设计
×
第五章 线性规划
第五章
线性规划
第一节线性规划的标准形式与基本性质
第二节基本可行解的转换
第三节单纯形方法
第四节单纯形法应用举例 第五节修正单纯形法
2019年1月7日5时37分
机械优化设计
第五章
线性规划
目标函数和约束条件都是线性的，像这类约束 函数和目标函数都是为线性函数的优化问题，称作 线性规划问题。它的解法在理论和方法上都很成熟， 实际应用也很广泛。虽然大多数工程设计是非线性 的，但是也有采用线性逼近方法求解非线性问题的。 此外，线性规划方法还常被用作解决非线性问题的 子问题的工具，如在可行方向法中可行方向的寻求 就是采用线性规划方法。当然，对于真正的线性优 化问题，线性规划方法就更有用了。
o
x2
E
C B A
图5.1线性规划的几何意义
x1
通过顶点Ｃ的直线满足上述条件，故点Ｃ是该问题的最优解。
2019年1月7日5时37分
机械优化设计
用代数法求解联立方 程组。设变量个数为 n, 方程个数为 m, 令p n m, 为使方程组有唯一解， 让p个变量等于零。
在例5.1中，p 4 2 2,因此，若四个变量中使 任意两个等于零，则必 存在两个变量组的唯一 解。 表5 1列出了６个可能的解， 其中有４个解恰好等于 多边形４个顶点的 坐标，余下的２个解则 违反了所有变量为非负 的约束条件。
（电力约束）
2019年1月7日5时37分
机械优化设计
将其化成线性规划标准形式： 求
x [ x1x2 ]T
使
且满足
min f ( x) 60x1 120x2
9 x1 4 x2 x3来自百度文库 360
3x1 10 x2 x4 300
1 2 1 2 1 2 1 2
2019年1月7日5时37分
机械优化设计
例5-2：生产甲种产品每件需使用材料9kg、3个工时、4kw电，获 利润60元。生产乙种产品每件需用材料4kg、10个工时、5kw电， 可获利120元。若每天能供应材料360kg，有300个工时，能供 200kw电。试确定两种产品每天的产量，使每天可能获得的利润 最大？
日利润最大
生产能力限制
劳动力限制 变量非负
2019年1月7日5时37分
机械优化设计
建模例1： 某公司有钢材、铝材、铜材1200t，800t和650t，拟调往 物资紧张的地区甲、乙、丙。已知甲、乙、丙对上述物资的总需求 分别为：900t，800t和1000t。各种物资在各地销售每吨的获利如下 表所示。试问公司应如何安排调运计划，才能获利最大？建立该问 题的数学模型。
3 x1' -3 x1 " +2x2 8 x1' - x1 " - 4x2 14 x1 ' , x1 " , x2 0
3 x1' -3 x1 " +2x2 +x3 = 8 x1' - x1 " - 4x2 +x 4= 14 x1' , x1" ,x2 ,x3 ,x4 0
2019年1月7日5时37分
4x1 5x2 x5 200 xi 0(i 1, 2,3, 4,5)
2019年1月7日5时37分
机械优化设计
例5-3：某厂生产甲、乙两种产品，已知：①两种产品分别由两
条生产线生产。第一条生产甲，每天最多生产9件，第二条生产
乙，每天最多生产7件；②该厂仅有工人24名，生产甲每件用2工 日，生产乙每件用3工日；③产品甲、乙的单件利润分别为 40元
2019年1月7日5时37分
机械优化设计
二、线性规划的标准形式
线性规划数学模型的一般形式： 求 使 且满足
x [ x1x2 xn ]T
f ( x) c1 x1 c2 x2 cn xn min
a11 x1 a12 x2 a1n xn b1 a21 x1 a22 x2 a2 n xn b2 am1 x1 am 2 x2 amn xn bm
2019年1月7日5时37分
机械优化设计
例5 1的 数 学 模 型 可 化 为 如 标 下准 形 式 ： max z 2 x1 x2 s.t. 3 x1 5 x2 15 6 x1 2 x2 24 x1 0
min z 2 x1 x2 s.t. 3 x1 5 x2 x3 15 6 x1 2 x2 x4 24
机械优化设计
建模例3： 成批生产企业年度生产计划的按月分配 。 在成批生产的机械制造企业中，不同产品劳动量的结构上可能 有很大差别。如：某种产品要求较多的车床加工时间，另一种 产品的劳动量可能集中在铣床和其他机床上。因此，企业在按 月分配年度计划任务时，应考虑到各种设备的均衡且最大负荷。 在年度计划按月分配时一般要考虑:1）从数量和品种上保 证年度计划的完成；2）成批的产品尽可能在各个月内均衡生 产或集中在几个月内生产；3）由于生产技术准备等方面原因， 某些产品要在某个月后才能投产；4）根据合同要求，某些产 品要求在年初交货；5）批量小的产品尽可能集中在一个月或 几个月内生产出来，以便减少各个月的品种数量等等。如何在 满足上述条件的基础上，使设备均衡负荷且最大负荷。
2019年1月7日5时37分
机械优化设计
§第一节
线性规划的标准形式与基本性质
一、线性规划实例
解：设生产A、B两产品分别 例5-1： 某工厂要生产A、B两种产品，为x , x 台，则该问题的优化 1 2 每生产一台产品A 可获产值2万元； 数学模型为： 需占用一车间工作日3天，二车间工 max z 2 x x s.t. 3 x 5 x 15 作日6天；每生产一台产品B 可获产 6 x 2 x 24 值1万元；需占用一车间工作日5天， x 0 二车间工作日2天。现一车间可用于 x 0 生产A、B产品的时间15天，二车间 可用于生产A、B产品的时间24天。 试求出生产组织者安排A、B两种产 品的合理投资产数，以获得最大的总 产值。
获利 地区
物资
钢材
铝材
铜材
甲 乙 丙
260 210 180
300 250 400
400 550 350
2019年1月7日5时37分
机械优化设计
建模例2： 某工厂生产A、B、C三种产品，现根据订货合同以及生 产状况制定5月份的生产计划，已知合同甲为：A产品1000件，单件 价格为500元，违约金为100元/件；合同乙为：B产品500件，单件 价格为400元，违约金为120元/件；合同丙为：B产品600件，单件 价格为420元，违约金为130元/件；C产品600件，单件价格为400元， 违约金为90元/件；有关各产品生产过程所需工时以及原材料的情况 见下表。试以利润为目标，建立该工厂的生产计划线性规划模型 。
分析：每天生产的甲、乙两种产品分别为 x1 , x2 件
f ( x1 , x2 ) 60x1 120x2 max (利润最大)
g1 ( X ) 9 x1 4 x2 360
g2 ( X ) 3x1 10x2 300
（材料约束） （工时约束）
g3 ( X ) 4 x1 5x2 200
和80元。问工厂如何组织生产才能获得最大利润？
2019年1月7日5时37分
机械优化设计
解: 设甲、乙两种产品的日产件数分别为 x1 , x2 .
max F ( X ) 40x1 80x2 X D R2 s.t. x 9 1 x2 7 2 x1 3 x2 24 x1 , x2 0
如: 约束条件为“ ”时：
10 x1 12 x2 18
10 x1 12 x2 x3 18
x3为剩余变量
2019年1月7日5时37分
机械优化设计
(2) 变量 例如：
3x1+2x2 8 x1 -4x2 14 x2 0
1、x 0，令x’＝- x。 2、x取值无约束，令x= x'- x"
如果有不等式约束： ai1 x1 ai 2 x2 ain xn bi 则可加上新的变量 xn i 0(此时称xn i为松弛变量)，把它们全变为 等式约束，即 ai1 x1 ai 2 x2 ain xn xn i bi
约束条件为“ ”时：
如 : 6 x1 2 x2 24
6 x1 2 x2 x3 24
x3为松弛变量
2019年1月7日5时37分
机械优化设计
如果有不等式约束： ai1 x1 ai 2 x2 ain xn bi 则可减去新的变量 xn i 0(此时称xn i为剩余变量)，把它们全变为 等式约束，即 ai1 x1 ai 2 x2 ain xn xn i bi
Ｔ Ｔ Ｔ Ｔ
A p1 , p2 , p3 , p4
2019年1月7日5时37分
机械优化设计
三、线性规划的基本性质
以例5 1为例，用图解法解释线 性规划的几何意义，并 与代数法得到的解 加以对照说明。 min z 2 x1 x2 s.t. 3x1 5 x2 x3 15 6 x1 2 x2 x4 24 x j 0( j 1,2,3,4)
说明： 1）m=n,唯一解 2）m>n,无解 3）m<n,无穷解
xi 0(i 1, 2,, n) bj 0( j 1, 2,, m)
2019年1月7日5时37分
机械优化设计
将一般形式的线性规划化为标准形式的方法
约束条件包括两部分：一是等式约束条件，二是变量 (2)的非负要求，它是标准形式中出现的唯一不等式形式 在约束条件中，
机械优化设计
（3）x两边有约束的情况。 x1+x2 5 -6 x1 10 x20 (4) 右端常数 右端项b＜0时，只需将等式或不等式两 端同乘(一1)，则等式右端项必大于零。 -6+6 x1+6 10+6 令x1' = x1 +6 0 x1' 16 x1' +x2 11 x1' 16 x1' , x2 0
x2 0 x j 0( j 1,2,3,4) 用 矩 阵 和 向 量 表 示 ，有 则：
3 5 1 0 Ｔ A , b 15 , 24 ， c 2,1,0,0 ， 6 2 0 1 p1 3,6 ， p2 5,2 ， p3 1,0 ， p4 0,1
工序1 工序2 产品A /件 产品B /件 产品C /件 总工时或原材料 工时或原材料成本 （元） 2 1 2 4600 15 3 1 1 4000 10 工序3 2 3 2 6000 10 原材料1 原材料2 3 2 4 10000 20 4 3 2 8000 40 其他成本 10 10 10
2019年1月7日5时37分
D
x2
E
o
C B A
图5.1线性规划的几何意义
x1
2019年1月7日5时37分
机械优化设计
令松弛变量x3 0, x4 0, 画出上述约束 方程的图线，如图 5.1所示。
取Z为不同的常数，可画出 一系列平行 直线。在此直线族中 ，确定出一条直线 D 满足以下条件，即： 尽可能远离原点 O, 且与多边形 OACD至少有一交点。
序号 变 量 值 x1 x2 x3 x4 图5.1中对应 的顶点 1 0 0 15 24 O 2 0 3 0 18 D 3 0 12 -45 0 E 4 5 0 0 -6 B 5 4 0 3 0 A 6 15/4 3/4 0 0 C
2019年1月7日5时37分
机械优化设计
可行解：同时满足所有约束条件的任何一 x2 个解x=[x1,x2,„,xn]T。例：多边形OACD域 中任意一个解。 基本解：令线性规划标准形式中任意 (n-m)个变量等于零，若剩余的m个变量 构成的m个线性方程有唯一解，则称由此 得到的n个变量的解为基本解。例：表5-1 中列出的６个解(或图6.1对应的６个顶点 A、B、C、D、E、O)。