没有合适的资源?快使用搜索试试~ 我知道了~
首页MATLAB实例:优化机床生产计划以最大化利润
MATLAB实例:优化机床生产计划以最大化利润
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 86 浏览量
更新于2024-06-26
收藏 12.3MB PDF 举报
"《MATLAB实例与程序》是一本详尽的教材,共799页,专注于介绍线性规划在实际问题中的应用与编程技巧。本书以G.B. Dantzig的单纯形法为核心,讲解了线性规划的基本概念,如其在生产和管理决策中的重要性,如何通过数学模型解决实际问题,如机床厂的生产优化案例。 1.1节深入探讨了线性规划的实例,如如何通过建立目标函数(如最大化利润,用z=4x1+3x2表示)和约束条件(如每天可用机器工时限制)来确定最优生产方案。决策变量x1和x2在这里起到了关键作用,目标函数和约束条件必须都是线性的,以定义为线性规划问题。 1.2部分介绍了MATLAB中处理线性规划的标准形式,它以最小化为目标(min),将线性目标函数(cTx)与线性不等式约束(Ax≤b)结合,同时考虑变量的下界(lb)和上界(ub)。这些矩阵和向量的使用在MATLAB中非常直观,有助于简化问题的表达和求解过程。 《MATLAB实例与程序》不仅提供了理论背景,还提供了丰富的实例和代码,帮助读者掌握如何在MATLAB环境中实际操作线性规划算法,解决复杂的优化问题。书中强调模型建立的精确性和选择合适决策变量的重要性,这对于理解和应用线性规划技术来说至关重要。通过阅读这本书,读者能够提升对线性规划的理解,并熟练运用MATLAB工具进行高效计算和决策分析。"
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/87600508/bg10.jpg)
假设:
(1)每种货物可以无限细分;
(2)每种货物可以分布在一个或者多个货舱内;
(3)不同的货物可以放在同一个货舱内,并且可以保证不留空隙。
问应如何装运,使货机飞行利润最大?
-15-
![](https://csdnimg.cn/release/download_crawler_static/87600508/bg11.jpg)
第二章 整数规划
§1 概论
1.1 定义
规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,
变量限制为整数,则称为整数线性规划。目前所流行的求解整数规划的方法,往往只适
用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。
1.2 整数规划的分类
如不加特殊说明,一般指整数线性规划。对于整数线性规划模型大致可分为两类:
1
o
变量全限制为整数时,称纯(完全)整数规划。
2
o
变量部分限制为整数的,称混合整数规划。
1.2 整数规划特点
(i) 原线性规划有最优解,当自变量限制为整数后,其整数规划解出现下述情况:
①原线性规划最优解全是整数,则整数规划最优解与线性规划最优解一致。
②整数规划无可行解。
例 1 原线性规划为
min
z
x
1
x
2
2x
1
4x
2
5, x
1
≥
0, x
2
≥
0
其最优实数解为:
x
1
0,
x
2
5
4
, min z
5
4
。
③有可行解(当然就存在最优解),但最优解值变差。
例 2 原线性规划为
min
z
x
1
x
2
2x
1
4x
2
6, x
1
≥
0, x
2
≥
0
其最优实数解为:
x
1
0,
x
2
3
2
, min z
3
2
。
若限制整数得:
x
1
1,
x
2
1,
min
z
2
。
(ii) 整数规划最优解不能按照实数最优解简单取整而获得。
1.3 求解方法分类:
(i)分枝定界法—可求纯或混合整数线性规划。
(ii)割平面法— 可求纯或混合整数线性规划。
(iii)隐枚举法— 求解“0-1”整数规划:
①过滤隐枚举法;
②分枝隐枚举法。
(iv)匈牙利法— 解决指派问题(“0-1”规划特殊情形)。
(v)蒙特卡洛法— 求解各种类型规划。
下面将简要介绍常用的几种求解整数规划的方法。
§2 分枝定界法
对有约束条件的最优化问题(其可行解为有限数)的所有可行解空间恰当地进行系
统搜索,这就是分枝与定界内容。通常,把全部可行解空间反复地分割为越来越小的子
集,称为分枝;并且对每个子集内的解集计算一个目标下界(对于最小值问题),这称
为定界。在每次分枝后,凡是界限超出已知可行解集目标值的那些子集不再进一步分枝,
-16-
![](https://csdnimg.cn/release/download_crawler_static/87600508/bg12.jpg)
若其最优解不符合 A 的整数条件,那么 B 的最优目标函数必是 A 的最优目标函数 z 的
上界,记作 z ;而 A 的任意可行解的目标函数值将是 z 的一个下界 z 。分枝定界法就
是将 B 的可行域分成子区域的方法。逐步减小 z 和增大 z ,最终求到 z 。现用下例来
⎨7x1 20x2 ≤ 70
可见它不符合整数条件。这时 z 是问题 A 的最优目标函数值 z 的上界,记作 z 。而
即 0 ≤ z ≤ 356 。
⎩
⎨7x1 20x2 ≤ 70
⎩
⎨7x1 20x2 ≤ 70
再定界: 0 ≤ z ≤ 349 。
⎩
这样,许多子集可不予考虑,这称剪枝。这就是分枝定界法的主要思路。
分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由 Land
Doig 和 Dakin 等人提出的。由于这方法灵活且便于用计算机求解,所以现在它已是解
整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂
选址问题、背包问题及分配问题等。
设有最大化的整数规划问题
A
,与它相应的线性规划为问题
B
,从解问题
B
开始,
*
*
*
说明:
例 3 求解下述整数规划
Max
z
40x
1
90x
2
⎧
9x
1
7x
2
≤
56
⎪
⎪
x
1
,
x
2
≥
0
且为整数
解
(
i
)先不考虑整数限制,即解相应的线性规划
B
,得最优解为:
x
1
4.8092,
x
2
1.8168,
z
355.8779
*
x
1
0,
x
2
0
显然是问题
A
的一个整数可行解,这时
z
0
,是
z
*
的一个下界,记作
z
,
*
(
ii
)因为
x
1
,
x
2
当前均为非整数,故不满足整数要求,任选一个进行分枝。设选
x
1
进行分枝,把可行集分成 2 个子集:
x
1
≤
[4.8092]
4
,
x
1
≥
[4.8092]
1
5
因为 4 与 5 之间无整数,故这两个子集的整数解必与原可行集合整数解一致。这
一步称为分枝。这两个子集的规划及求解如下:
问题
B
1
:
Max
z
40x
1
90x
2
⎧
9x
1
7x
2
≤
56
⎪
⎪
0
≤
x
1
≤
4,
x
2
≥
0
最优解为:
x
1
4.0,
x
2
2.1,
z
1
349
。
问题
B
2
:
Max
z
40x
1
90x
2
⎧
9x
1
7x
2
≤
56
⎪
⎪
x
1
≥
5,
x
2
≥
0
最优解为:
x
1
5.0,
x
2
1.57,
z
1
341.4
。
*
(
iii
)对问题
B
1
再进行分枝得问题
B
11
和
B
12
,它们的最优解为
-17-
![](https://csdnimg.cn/release/download_crawler_static/87600508/bg13.jpg)
再定界: 341340 ≤≤ z ,并
将 12B 剪枝。
求得其目标函数值,并记作 z 。以 z 表示问题 A 的最优目标函数值;这时有
B
11
:
x
1
4,
x
2
2,
z
11
340
B
12
:
x
1
1.43,
x
2
3.00,
z
12
327.14
*
(
iv
)对问题
B
2
再进行分枝得问题
B
21
和
B
22
,它们的最优解为
B
21
:
x
1
5.44,
x
2
1.00,
z
22
308
B
22
无可行解。
将
B
21
,
B
22
剪枝。
于是可以断定原问题的最优解为:
x
1
4,
x
2
2,
z
*
340
从以上解题过程可得用分枝定界法求解整数规划(最大化)问题的步骤为:
开始,将要求解的整数规划问题称为问题
A
,将与它相应的线性规划问题称为问
题
B
。
(
i
)解问题
B
可能得到以下情况之一:
(
a
)
B
没有可行解,这时
A
也没有可行解,则停止.
(
b
)
B
有最优解,并符合问题
A
的整数条件,
B
的最优解即为
A
的最优解,则
停止。
(
c
)
B
有最优解,但不符合问题
A
的整数条件,记它的目标函数值为
z
。
(
ii
)用观察法找问题
A
的一个整数可行解,一般可取
x
j
0,
j
1,
,
n
,试探,
*
z ≤ z
*
≤ z
进行迭代。
第一步:分枝,在
B
的最优解中任选一个不符合整数条件的变量
x
j
,其值为
b
j
,
以
[b
j
]
表示小于
b
j
的最大整数。构造两个约束条件
x
j
≤
[b
j
]
和
x
j
≥
[b
j
]
1
将这两个约束条件,分别加入问题
B
,求两个后继规划问题
B
1
和
B
2
。不考虑整数条件
求解这两个后继问题。
定界,以每个后继问题为一分枝标明求解的结果,与其它问题的解的结果中,找出
最优目标函数值最大者作为新的上界
z
。从已符合整数条件的各分支中,找出目标函数
值为最大者作为新的下界
z
,若无作用
z
不变。
第二步:比较与剪枝,各分枝的最优目标函数中若有小于
z
者,则剪掉这枝,即
以后不再考虑了。若大于
z
,且不符合整数条件,则重复第一步骤。一直到最后得到
z
*
z
为止。得最优整数解
x
*
j
,
j
1,
,
n
。
§
3 0 − 1
型整数规划
0
−
1
型整数规划是整数规划中的特殊情形,它的变量
x
j
仅取值
0
或
1
。这时
x
j
称
为
0
−
1
变量,或称二进制变量。
x
j
仅取值
0
或
1
这个条件可由下述约束条件:
0
≤
x
j
≤
1
,整数
-18-
![](https://csdnimg.cn/release/download_crawler_static/87600508/bg14.jpg)
⎧1, 当Ai点被选中,
z ∑ ci xi
⎪∑ bi xi ≤ B
⎪⎪ i1
⎪x x ≥ 1
⎪ 4
⎨7x1 3x2 ≤ 45 (1 − y)M
⎩ y 0或1
⎩
所代替,是和一般整数规划的约束条件形式一致的。在实际问题中,如果引入
0 − 1
变
量,就可以把有各种情况需要分别讨论的线性规划问题统一在一个问题中讨论了。我们
先介绍引入
0 − 1
变量的实际问题,再研究解法。
3.1
引入
0 − 1
变量的实际问题
3.1.1 投资场所的选定— — 相互排斥的计划
例 4 某公司拟在市东、西、南三区建立门市部。拟议中有 7 个位置(点)
A
i
(i
1,2,
,7)
可供选择。规定
在东区。由
A
1
,
A
2
,
A
3
三个点中至多选两个;
在西区。由
A
4
,
A
5
两个点中至少选一个;
在南区,由
A
6
,
A
7
两个点中至少选一个。
如选用
A
i
点,设备投资估计为
b
i
元,每年可获利润估计为
c
i
元,但投资总额不能
超过
B
元。问应选择哪几个点可使年利润为最大?
解题时先引入
0
−
1
变量
x
i
(i
1,2,
,7)
令
x
i
⎨
⎩
0
,
当 A
i
点没被选中.
于是问题可列写成:
i
1,2,
,7
.
Max
7
i1
⎧
7
⎨
x
1
x
2
x
3
≤
2
5
⎪
⎩
x
6
x
7
≥
1,
x
i
0
或
1
3.1.2 相互排斥的约束条件
有两个相互排斥的约束条件
5x
1
4x
2
≤
24
或
7x
1
3x
2
≤
45
。
为了统一在一个问题中,引入
0 − 1
变量
y
,则上述约束条件可改写为:
⎧
5x
1
4x
2
≤
24
yM
⎪
⎪
y 0 或 1
其中
M
是充分大的数。
约束条件
x
1
0
或
500
≤
x
1
≤
800
可改写为
⎧
500
y
≤
x
1
≤
800
y
⎨
-19-
剩余807页未读,继续阅读
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/2ab41b4b301b4cc6861912179f3798cc_qq_41127811.jpg!1)
![](https://csdnimg.cn/release/wenkucmsfe/public/img/user-vip.1c89f3c5.png)
JGiser
- 粉丝: 7647
- 资源: 5101
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 利用迪杰斯特拉算法的全国交通咨询系统设计与实现
- 全国交通咨询系统C++实现源码解析
- DFT与FFT应用:信号频谱分析实验
- MATLAB图论算法实现:最小费用最大流
- MATLAB常用命令完全指南
- 共创智慧灯杆数据运营公司——抢占5G市场
- 中山农情统计分析系统项目实施与管理策略
- XX省中小学智慧校园建设实施方案
- 中山农情统计分析系统项目实施方案
- MATLAB函数详解:从Text到Size的实用指南
- 考虑速度与加速度限制的工业机器人轨迹规划与实时补偿算法
- Matlab进行统计回归分析:从单因素到双因素方差分析
- 智慧灯杆数据运营公司策划书:抢占5G市场,打造智慧城市新载体
- Photoshop基础与色彩知识:信息时代的PS认证考试全攻略
- Photoshop技能测试:核心概念与操作
- Photoshop试题与答案详解
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)