当前位置：文档之家 › 运筹学及其应用6.3线性目标规划的序贯式算法(20200711014236)

运筹学及其应用6.3线性目标规划的序贯式算法(20200711014236)

  • 格式：pdf
  • 大小：693.29 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

运筹学及其应用6.2 线性目标规划的图解法

运筹学及其应用6.2 线性目标规划的图解法

6.2线性目标规划的图解法目标规划问题的图解法::求一个区域，提供了相目标规划问题的图解法互矛盾的目标集的折衷方案。

+例Min S = d1X1+2X2+ d1--d1+ = 10X1+2X2 ≤6X1+X2 ≤4X1,X2,d1-, d1+ ≥0这个例子帮我们理解硬约束和软约束在图中的不同表达方式。

12x1x24681021342X 1+2X 2 ≤6Min S = d 1+X 1+2X 2+ d 1--d 1+ = 10X 1+2X 2 ≤6X 1+X 2 ≤4X 1,X 2,d 1-, d 1+ ≥053x1x24681021342X 1+X 2 ≤4Min S = d 1+X 1+2X 2+ d 1--d 1+ = 10X 1+2X 2 ≤6X 1+X 2 ≤4X 1,X 2,d 1-, d 1+ ≥054x1x24681021342Min S = d 1+X 1+2X 2+ d 1--d 1+ = 10X 1+2X 2 ≤6X 1+X 2 ≤4X 1,X 2,d 1-, d 1+ ≥055x1x24681021342x 1+2x 2=105d 1+d 1-A B(2,2)Min S = d 1+X 1+2X 2+ d 1--d 1+ = 10X 1+2X 2 ≤6X 1+X 2 ≤4X 1,X 2,d 1-, d 1+ ≥06x1x24681021342x 1+2x 2=105d 1+d 1-A B(2,2)当Min S = d 1+ 达到时d 1+ = 07x1x24681021342x 1+2x 2=105d 1-A B(2,2)当Min S = d 1+ 达到时d 1+ = 08x1x24681021342x 1+2x 2+d 1-= 10 d 1-= 25d 1-A B (2,2)当Min S = d 1+ 达到时d 1+ = 09x1x24681021342x 1+2x 2+d 1-= 10 d 1-= 45d 1-A B(2,2)有无穷多解：点（0，3）和点（2，2）连线上的点都是最优解。

运筹学课件--第五章 目标规划

运筹学课件--第五章 目标规划
例如
P1 级目标实现利润至少30元； P2级目标是甲乙产品的产量 假设：乙产品产量不少于4件比甲产品产量不少于6 件更重要，取其权重为2 minG= P1 d1- + P2(2d2- + d3- ) 3x1+5x2 +d1-- d1+ = 30 x2 +d2- - d2+ = 4 x1 + d3- - d3+ = 6 x1 , x2 ,dk- , dk+ ≥0(k=1,2,3)
16
OR:SM OR:SM
例3 在上题中（例2），如果工序Ⅱ在加班时间内生产出来的产品，每台A 型机减少利润20元，每台B型机减少利润25元，并且工序Ⅱ的加班时间每 周最多不超过30小时，这是p4级目标，试建立这个问题的目标规划模型。 解：设x1,x2分别为在正常时间和加班时间生产A型机台数，x3,x4 分别为在正 常时间和加班时间生产B型机台数，目标规划数学模型为：
10
OR:SM OR:SM
建模的步骤
1、根据要研究的问题所提出的各目标与条件，确定目标值，列 出目标约束与绝对约束；
2、可根据决策者的需要，将某些或全部绝对约束转化为目标约
束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即 可。
3、给各目标赋予相应的优先因子 Pk（k=1.2…K）。
OR:SM OR:SM
试试看——目标规划模型的实例
例1 某厂生产A、B、C三种产品，装配工作在同一生产线上 完成，三种产品时的工时消耗分别为6、8、10小时，生产线 每月正常工作时间为200小时；三种产品销售后，每台可获
利分别为500、650和800元；每月销售量预计为12、10和6台。
该厂经营目标如下： 1、利润指标为每月16000元，争取超额完成； 2、充分利用现有生产能力； 3、可以适当加班，但加班时间不得超过24小时； 4、产量以预计销售量为准。 试建立目标规划模型。

线性规划PPT课件

线性规划PPT课件

基解：令所为 有 0， 非求 基出 变的 (1量 .2)的 满解 足 称为基解。
基可行解与可行 足基 (1.3)： 的满 基解称为基可 对应基可行解的 为基 可， 行称 基。基 显可 然 解的数目 基解的数 C目 nm
基本最优解与最优基 满： 足(1.1) 的基可行解称为基本 优最 解，
对应m,如果 B是矩A中 阵的一 mm个 阶非奇异 (|B子 |0)矩 ,则阵 称 B是线性规 题的一个基。
基向量与非基向B量 中： 的基 列向量称为，基向 矩阵A中除B之外各列即为非，基 A中 向共 量 有nm个非基向量。
基变量与非基 基变 向P量 j量 对： 应与 的xj变 称量 为基变量；否 基则 变称 量为 。非
将文件存储并命名后，选择菜单 “Solve” 并对提示 “ DO RANGE(SENSITIVITY)ANALYSIS? ”回答“是”，即 可得到如下输出：
“资源” 剩余 为零的约束为 紧约束（有效 约束）
OBJECTIVE FUNCTION VALUE
1)
3360.000
VARIABLE VALUE REDUCED COST
可行解 基 解
基可行解
1.4 线性规划问题的图解法
下面结合例1的求解来说明图解法步骤。
例1
max Z 4 x1 3 x2
2 x1 3 x2 24
s. t 3 x1 2 x2 26
x2
x1, x2 0
Q3(6,4)
第一步：在直角坐标系中分
别作出各种约束条件，求出
3x1+2x2=26
Q2(6,4)
B
条 件
3x1 100
x1,x2 0
l3:3x1 100 l4
l4:x10,l5:x200

运筹学第二章线性目标规划

运筹学第二章线性目标规划

2 x x 11 2 1 x1 x2 d1 d1 0 st x1 2 x2 d 2 d 2 10 8 x1 10 x2 d 3 d 3 56 _ x , x , d 1 2 i 0, i 1,2,3
现有下列目标： P1、要求总利润必须超过 2500 元； P2、考虑产品受市场影响，为避免积压，A、B的生产量不超 过 60 件和 100 件 ； P3、由于甲资源供应比较紧张，不要超过现有量140 。 试建立目标规划模型。
天津大学管理与经济学部

第二章 线性规划
天津大学管理与经济学部
1 1
2 3 1 2 3 4
4
2

天津大学管理与经济学部

第二章 线性规划
定义3. 设 X R, 若不存在 X R, 使 F ( X ) F ( X ), 则称 X 为问题的弱有效解。
f
f1 ( x)
f 2 ( x)
* Rwp
0 两个目标一维变量弱有效解的例子
天津大学管理与经济学部
第二章 线性规划
例23 【喜糖问题】
设市场上有甲级糖及乙级糖，单价 分别为4元/斤及2元/斤。今要筹办 一桩喜事。“筹备小组”计划总花 费不超过40元，糖的总斤数不少于 10斤，甲级糖不少于5斤。问如何确 定最佳的采购方案。
天津大学管理与经济学部

第二章 线性规划
（ 4） F F
1
2
意味着 F
1
的每个分量都要小于或等于 F
1
2
对应的分量，并且至少存在 F 的某个分量要严格地小于向量
F 2 对应的分量，即对于 i 1,, p ，均有 f i1 f i 2 ，且至少 1 2 i ( 1 i p ), 有 f f 存在某个 0 0 i0 i0

线性规划方法及其应用

线性规划方法及其应用

05
线性规划方法优缺点分析
优点分析
有效处理多变量问题
线性规划能够同时处理多个决策变量，通过 优化算法寻找最优解。
直观易懂的数学模型
线性规划在各个领域都有广泛的应用，如生 产计划、资源分配、运输问题等。
广泛应用
线性规划的数学模型相对简单，易于理解和 应用。
可求解大规模问题
随着计算机技术的发展，线性规划可以求解 大规模的问题，满足实际应用的需求。
复杂约束处理
研究如何处理包含复杂约束条件的线性规划问题，提高求解效率和 准确性。
不确定性问题建模
针对包含不确定性因素的线性规划问题，发展有效的建模和求解方 法。
应用领域拓展
探索线性规划方法在更多领域（如机器学习、大数据分析等）的应用 潜力，推动相关领域的理论和技术创新。
感谢您的观看
THANKS
3
考虑不确定性
将不确定性因素引入资源分配问题中，通过线性 规划求解鲁棒性强的资源分配策略，以应对潜在 的风险和变化。
04
线性规划软件介绍
MATLAB软件介绍
1
MATLAB是一款由MathWorks公司开发的数学 计算软件，广泛应用于算法开发、数据可视化、 数据分析以及数值计算等领域。
2
MATLAB提供了丰富的工具箱，其中包括优化工 具箱（Optimization Toolbox），可用于解决线 性规划问题。
线性规划方法及其应用
目录
• 线性规划基本概念 • 线性规划方法 • 线性规划应用举例 • 线性规划软件介绍 • 线性规划方法优缺点分析 • 线性规划方法发展趋势与展望
01
线性规划基本概念
定义与特点
定义：线性规划是一种数学方法，用于 优化一组线性不等式约束下的线性目标 函数。

运筹学基础-目标规划

运筹学基础-目标规划

§5.1
目标规划问题的提出与目标规划模型
一、问题的提出
【引例1】某生物药厂需在市场上采购某种原料，现市场上有甲、乙
两个等级，单价分别为2千元/kg和1千元/kg，要求采购的总费用不得 超过20万元，购得原料的总重量不少于100kg，而甲级原料又不得少 于50kg，问如何确定最好的采购方案（即用最少的钱、采购最多数量 的原料）。 分析：这是一个含有两个目标的数学规划问题． 设x1、x2分别为采 购甲级、乙级原材料的数量（单位：kg）， y1为花掉的资金， y2为 所购原料总量．则： 2 x1 x2 200 x x 100 Miny1 2 x1 x2 1 2 目标函数为： Maxy x x 约束条件为： 2 1 2 x2 50 x1 , x2 0 注：此规划模型是一个多目标规划模型


（2）要求实际值小于目标值时，就是正偏差变量要尽可能地小，即 不希望d＋＞0，这时达成函数是：
min d

16
（3）要求实际值大于目标值时，就是负偏差变量要尽可能地小，即 不希望d－＞0，这时达成函数是：
min d
目标规划
【例】
x1 x2 d d 0
设备负荷（台小时） 单位产品利润 (元)
分析:设x1、x2分别是计划期内甲、乙产品的产量．则该问 9.2 x1 4 x2 3600 题的数学模型为
max y1 70x1 120x2 max y2 x1 min y x 3 2
s.t. 4 x 5 x 2000 1 2 3 x1 10 x2 3000 x1 , x2 0
min d

17
目标规划
【又例】

运筹学概述及线性规划应用——第四章

解：1.建立线性规划数学模型 加工（单位：人） 甲 乙 4 1 12 设安排生产甲产品X1件，乙产品X2件 X X 根据表中条件分别列出约束条件和目标函数为 4X1+X2≤12 X2≤5 X1+X2≤6 x1、x2≥0 装配（单位：人） 0 1 5 包装（单位：人） 1 1 6 利润（单位：千元） 2 3
用单纯形法求解此线性规划问题的最优解1引入松弛变量x将原问题写成标准形式2将方程中有关数字填入单纯形表的相应列中得初始单纯形表3将单纯形表相应数值输入线性规划单纯形法的计算机程序中进行运算得出最后结果如下
第四章 线性规划的解法
图解法
• 步骤、解的几种情况 • 步骤、方法 • 步骤、方法 • 基本变量确定、单纯形法步骤 • 步骤、方法 • 步骤、方法
例2 学院建筑工程造价专业学生到某建筑公司顶岗实习时，公司经理要求其为公司做一 投资方案。公司投资兴建多层时，每建设一个项目需资金200万元，需地皮200m2，可获 利润300万元；投资兴建高层时，每建设一个项目需要资金300万元，需要地皮100m2，可 获利润200万元，该公司现有可使用资金1200万元，地皮800m2，问应作怎样的组合投资， 可使所获利润最多？最大利润是多少? 解：1.建立线性规划数学模型
列出约束条件：
在平面直角坐标系上画出约束条件所限定的区域。 2. 在平面直角坐标系上画出约束条件所限定的区域。 2X1+3X2≤1750 X1+6X2≤2405 4X1+2X2≤2500 X1 ，X2∈N
X2
4X1+2X2=2500
E(0,1200)
B（365,340） 365,340） Ｆ(0,1750/3) A（0,2405/6） 0,2405/6） Ｇ（875,0） Ｇ（875,0） 875,0 2X1+3X2=1750 D （625,0） 625,0） Ｈ(2405,0) C（500,250） 500,250）

运筹学课件第四章 目标规划


一、目标规划的数学模型
例4、电视机厂装配25寸和21寸两种彩电，每台
第四章
电视机需装备时间1小时，每周装配线计划开动40小
时，预计每周25寸彩电销售24台，每台可获利80元， 每周21寸彩电销售30台，每台可获利40元。 该厂目标：
1、充分利用装配线，避免开工不足。
2、允许装配线加班，但尽量不超过10小时。 3、尽量满足市场需求。
(70,50),11000;
E(50,100),13000。
50
d+.d- =0
B O 50 100
X1 100X1+80X2 = 10000
二、目标规划的图解法
例2：用图解法求解。
第四章
min z
P d P d d P d 1 1 2 2 2 3 3


4 x1 16 4 x2 12 x x d d 1 2 1 1 0 s.t. x 2 x d d 1 2 2 2 8 2 x1 3 x2 d 3 d3 12 x , x , d , d i 1,2,3 1 2 i i 0
一、目标规划的数学模型
例3 Ⅰ Ⅱ 资源拥有量
第四章
原材料(公斤)
设备(小时) 利润(千元/件)
2
1 8
1
2 10
11
10
(1)、原材料价格上涨，超计划要高价购买，所以 要严格控制。
(2)、市场情况，产品Ⅰ销售量下降，产品Ⅰ的产 量不大于产品Ⅱ的产量。 (3)、充分利用设备，不希望加班。 (4)、尽可能达到并超过利润计划指标56千元。
一、目标规划的数学模型
目标规划数学模型涉及的基本概念 1、偏差变量

线性规划的方法及应用

线性规划的方法及应用1 引言运筹学最初是由于第二次世界大战的军事需要而发展起来的，它是一种科学方法，是一种以定量的研究优化问题并寻求其确定解答的方法体系．线性规划（Linear Progromming ，简称LP ）是运筹学的一个重要分支，其研究始于20世纪30年代末，许多人把线性规划的发展列为20世纪中期最重要的科学进步之一．1947年美国的数学家丹泽格提出了一般的线性规划数学模型和求解线性规划问题的通用方法――单纯形法，从而使线性规划在理论上趋于成熟．此后随着电子计算机的出现，计算技术发展到一个高阶段，单纯形法步骤可以编成计算机程序，从而使线性规划在实际中的应用日益广泛和深入．目前，从解决工程问题的最优化问题到工业、农业、交通运输、军事国防等部门的计划管理与决策分析，乃至整个国民经济的综合平衡，线性规划都有用武之地，它已成为现代管理科学的重要基础之一．2 线性规划的提出经营管理中如何有效地利用现有人力物力完成更多的任务，或在预定的任务目标下，如何耗用最少的人力物力去实现．这类问题可以用数学语言表达，即先根据问题要达到的目标选取适当的变量，问题的目标通常用变量的函数形式（称为目标函数），对问题的限制条件用有关变量的等式或不等式表达（称为约束条件）．当变量连续取值，且目标函数和约束条件为线性时，称这类模型为线性规划的模型．有关对线性规划问题建模、求解和应用的研究构成了运筹学中的线性规划分支．线性规划实际上是:求一组变量的值，在满足一组约束条件下，求得目标函数的最优解.从而线性规划模型的基本结构为： ①变量：变量又叫未知数，它是实际系统的位置因素，也是决策系统中的可控因素，一般称为决策变量，常引用英文字母加下标来表示，如n x x x ,,,21 等．②目标函数：将实际系统的目标用数学形式表示出来，就称为目标函数，线性规划的目标函数是求系统目标的数值，即极大值（如产值极大值，利润极大值）或极小值（如成本极小值，费用极小值等等）． ③约束条件：约束条件是指实现系统目标的限制因素．它涉及到企业内部条件和外部环境的各个方面，如原材料供应设备能力、计划指标．产品质量要求和市场销售状态等等，这些因素都对模型的变量起约束作用，故称其为约束条件．约束条件的数学表示有三种，即≤=≥,,,线性规划的变量应为非负值，因为变量在实际问题中所代表的均为实物，所以不能为负．线性规划问题有多种形式，函数有的要求实现最大化，有的要求最小化；约束条件可以是“≤”，也可以是“≥”，还可以是“=”，这种多样性给讨论带来不便. 为了便于讨论其一般解法，我们通常将线性规划问题的约束条件归结为线性方程和一组非负性限制条件，并且对目标函数统一成求最大值,也就是说,将线性规划问题的数学模型化成如下形式,并称它为线性规划问题的标准形式:),,2,1(..max11m i b x at s x c f ij nj ijjnj j ===∑∑==),,2,1(0n j x j =≥任何非标准形式的线性规划问题都能化成上述标准形式,这是由于不等式约束k j nj ijb x a≤∑=1等价于约束条件0,1≥=+++=∑k n k k n nj j ijx b x x a；不等式约束l j nj ijb x a≥∑=1等价于约束条件；0,1≥=-++=∑l n l l n nj j ijx b x x a这里增添的变量k n x +和l n x +称为松弛变量.还有,求函数f 的最小值解可转化为求函数f -的最 大值解.以下讨论线性规划问题时以标准型为主.3 线性规划的解法3.1 图解法满足约束条件的决策变量的一组值叫做这个线性规划的一个可行解;把所有可行解构成的集合叫做这个线性规划的可行域.因此,求解一个线性规划的问题,使目标函数取得最大值或最小值的可行解称为线性规划的最优解.一般求解线性规划问题是讨论它的最优解．下面介绍只有两个决策变量的线性规划问题的图解法.例１ 用图解法求解21m axx x f +-=22..21-≥-x x t s2221≤-x x 521≤+x x12,0x x ≥解 第一步 先画出可行域 以21,x x 为坐标轴作直角坐标系,因为0,021≥≥x x ，所以问题的可行解必在第一象限（含坐标轴）；约束条件222-≥-x x 要求问题的可行解必在直线222-=-x x 的右下方的半平面上；约束条件2221≤-x x ，要求问题的可行解必在直线2221=-x x 的左上方的半平面上；约束条件521≤+x x ，要求问题的可行解必在直线521=+x x 的左下方的半平面上.因为所有的约束条件都必须同时满足,所以问题的可行解域必为闭区域4321Q Q Q OQ ,如图3.1.1中的阴影部分. 第二步 从可行域中找出最优解现在分析目标函数21x x f +-=,在坐标平面上,它可以看作是以f 为参数的一族平行线:f x x +=12位于同一条直线上的点,都有相同的目标函数值,因而称它为等值线.当f 由小变大时,直线f x x +=12沿其法线方向向左上方移动.当移动到2Q 点时,f 的取值最大,这就得出了本题的最优解,如图3.1.2 ,此时f 最大,得 3411max =+⨯-=f .显然用图解法求解线性规划问题时,简单直观；但是当决策变量多于两个的时候,用图解法就失效了.3.2 单纯形法这一方法是丹泽格在1947年提出的，它以成熟的算法理论和完善的算法及软件统治线性规划近30年．单纯形法是求解线性规划问题的最重要、最基本的方法，它的解题思路[7](p27)是：将线性规划问题化为标准型后，先找出一个单位可行基，对这个可行基给出可行解，然后用判定定理——称为检验数，判定其是否为最优解．若是，求解过程结束；若不是，在单位可行基的基础上，进行换基迭代，该过程叫做迭代，直到得出最优解或证明无最优解为止.它有很强的程序性,它的具体操作是从一张叫做初始表的表格开始的.初始表由四部分构成[7](p27-28):第一部分A A B =-1(B 是单位可行基) 即约束方程组的系数矩阵.第二部分b b B =-1(B 是单位可行基) 即约束方程组的常数项构成的列向量.第三部分是检验数C A CB --1 (B C 为单位可行基变量所对应的目标函数中的系数列向量;C 是目标函数的系数行向量).第四部分b C B 该数为目标函数值.它的表格形式为:例２ 用单纯形法求解 2136m axx x f +=40x 23..21≤+x t s 21421≤+x x12,0x x ≥ ．解 第一步 将原问题化为标准型 43210036m ax x x x x f +++=40x 23..321=++x x t s214421=++x x x )4,3,2,1(0=≥j x j ．第二步 观察原问题是否存在现成的单位可行基 因为约束方程组的系数矩阵为),,,(101401234321p p p p A =⎪⎪⎭⎫⎝⎛= ，所以原问题存在现成的单位可行基()1341001B p p ⎛⎫== ⎪⎝⎭，第三步 列出初始表，计算⎪⎪⎭⎫⎝⎛==-10140123)111A A B ，⎪⎪⎭⎫⎝⎛==-2140)211b b B ， 3)1B C 是目标函数中基变量43,x x 的系数构成的列向量⎪⎪⎭⎫⎝⎛00，)0,0,3,6()4111--=-=--C C A B C B ，15)0B C b = ，1346)B x X x ⎛⎫= ⎪⎝⎭ .由上面计算结果，列出初始表（如下表）表3.2.1第四步 判定由初始表知，检验数中含有负数，故可行解Tx )21,40,0,0(=不是最优解，还需 要进行迭代运算（若检验数均为非负数，则可行解即为最优解） 第五步 迭代运算迭代一：①确定主元在检验数中，找出最小负数。

运筹学(第四版)清华大学出版社《运筹学》教材编写组-第5章 线性目标规划

11
清华大学出版社
第1节 目标规划的数学模型

目标规划的一般数学模型为
目标函数： min z Pl (lk d k lk dk ) l 1 k 1 L K
(4 1) (4 2) (4 3) (4 4) (4 5)
n c x d d g k , k 1, , K kj j k k j 1 n a x (, )b , i 1, , m 满足约束条件： ij j i j 1 x j 0, j 1, , n d k , d k 0, k 1, , K
16
清华大学出版社
第2节 解目标规划的图解法

解：设x1，x2分别表示黑白和彩色电视机的产量，本问题的 目标规划模型为：
目标函数： min z P d P d P ( 2 d d 1 1 3 3 4) 2 2
x1 x2 d1 d1 40 d2 50 x1 x2 d 2 满足约束条件： x1 d3 d3 24 x d d 2 4 4 30 x , x , d , d 0, i 1,2,3,4 1 2 i i
14
清华大学出版社
第2节 解目标规划的图解法

注意：求解目标规划问题时，把绝对约束作为最高优先 级考虑。在本例中，能依先后次序都满足d1+=0， d2++d2−=0，d3−=0，因而z*=0。但在大多数问题中并非如 此，会出现某些约束得不到满足，故将目标规划问题的 最优解称为满意解。
15
清华大学出版社
c j z j akj Pk j 1,2,, n; k 1,2,, K
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。