数学实验第五次讲稿

Search phrase number of hits（英文） 短语 点击数（中文）
“optimize the supply chain”1,160,000 优化供应链414,000
“optimize (the) return” 2,490,000 优化回报 453,000
“optimal experience” 32,400,000 最优经历
2021/1/21
9
每一种饲料每磅所含的营养成分
每种饲料每磅的成本
2021/1/21
10
引例2:供应与选址
某公司有6个建筑工地要开工，每个工地的位置（用平面坐标a，b表示，距离单位：千米）及水 泥日用量d 吨由下表给出。目前有两个临时料场位于A(5,1), B(2,7)，日储量各有20吨。假设从料场到 工地均有直线道路相连，（1）试制定每天的供应计划，即从A、B 两料场分别向各工地运送多少吨 水泥，使总的吨千米数最小。
“optimal choice”
25,800,000 最优选择10,900,000
“optimal design”
77,300,000 优化设计 1,270,000
“optimal health”
31,900,000 优化健康
还有如:优化产业结构 2,830,000 优化人员结构 3,110,000
2021/1/21
5
2021/1/21
为说明最优化 的价值,建立了专 门的网站,列举了 哪些公司的什么问 题,运用最优化方 法节约和增加了多 少金额.
有可选的行业, 考察的方面,受益 的方式,希望同学 们各选择其中的一 个,提一份报告,以 说明最优化的价值.
6
一,优化问题的普遍性以及引例
Google上相关搜索的结果：
效果? 甚至自然中的动植物，也时刻面临这样的问题. 类似的问题，还广泛的存在于无机世界中.
2021/1/21
3
一,优化问题的普遍性以及引例
看看下面的例子分别属于哪一类？ a)证券的投资组合；b)国家经济发展战略； c)产品规格、性能设计；d)球形的水滴； e)狼群的集体捕食；f)好的购物方案； g)物质分子结构； h)生物的身体构造； i)乘务组排班表; j)光传播路径:直线,反射,折射 课堂作业：和你的同桌讨论还有什么方面需要优化的。
“optimal investment” 8,320,000 优化投资 8,250,000
“optimal system”
84,200,000 优化系统 13,800,000
“optimal decision” 28,800,000 最优决策 2,890,000
“optimize your PC” 3,300,000 优化你的PC
制的变量. 而参数是指不能由决策者决定的量.实际上，数学模型很少有能表达变量和有效性测度
之间的精确关系的. 实际上，运筹学分析者的任务就是找出对测度有最重要影响的变量 然后找出
这些变量和测度之间的数学关系.这个数学关系也就是目标函数.
2021/1/21
13
二，优化问题的表述
• 决策变量和参数
•
我们称对应决策者可控的量称为决策变量,决策变量的取值确定了系统的最终性能,也
224021/1/21
线性规划模型 线性规划解的若干概念
max z = 5x1+3x2 s.t. 2x1+x2≤40
x1+2x2≤50 x1，x2≥0
可行点 可行域 凸多面体
225021/1/21
X2
2 X1 + X2 = 40 d
Bc
内点 边界点 顶点
X1 + 2 X2 = 50 Ⅰ
a
v
b
X1
线性规划模型
x2 L1
0 x2
L1 L3
0 ① 无可行解
2021/1/21
求解LP的特殊情形
L3 L2
x1 x2
Max z = 3x1+x2 s.t. -x1+x2≤2 ----L1
x1-2x2≤2 ----L2 3x1+2x2≤14 ----L3 x1，x2≥0
x2
L1 L2
x1 0
L1
L3
L2
z=c
x1 0
同学们有没有发现,英文和中文短语间有很大的不同,原因可能是什么?
2021/1/21
7
一,优化问题的普遍性以及引例
3,相关的几句格言： Waste neither time nor money, but make the best use of both. -- Benjamin Franklin Obviously, the highest type of efficiency is that which can utilize existing material to the best advantage. --
max cTx s.t. Ax≤b
x≥0
223021/1/21
2 3 1 34
A
3
2
1
.5
,
b
3 6
3 2 5 40
线性规划 标准形式
min (max) cTx s.t. Ax≤b, (或Ax = b)
x≥0 (或a ≤ x ≤ b)
其中：x∈Rn，A ∈Rm×n， b∈Rm， c∈Rn
• 发现算法时非常年轻,以至到日本时,人们以为” 线性规划之父”是个老人,而对他无人问津.
George B. Dantzig
2021/1/21
18
• Kantorovich(1912-1986)苏联人,著名数学家和 经济学家,教授,年仅18岁获博士学位.因在经济 学上提出稀缺资源的最优配置获诺贝尔奖.线 性规划对偶理论的提出者,数学规划的三大创 始人之一.
2021/1/21
16
以下的三个人物和线性规划的出现有重要的关系.
• 约翰·冯·诺依曼(1903－1957),美藉匈牙利人.20世 纪最杰出的数学家之一,被誉为”计算机之父”,”博 弈论之父”.被认为是数学规划的三大创始人之一.
• John Von Neumann
2021/1/21
17
• George B. Dantzig(1914-2005),美国人,线性 规划单纯形法的创始人,被誉为”线性规划之父 ”.美国科学院三院院士,美国军方数学顾问,教 授.并以其名字设立Dantzig奖.数学规划的三大 创始人之一.
Jawaharlal Nehru It is more probable that the average man could, with no injury to his health, increase his efficiency fifty
percent.--Walter Scott 请同学翻译上面的句子，你喜欢那一句？你有什么好的 表述？
2021/1/21
4
一,优化问题的普遍性以及引例
2,一些成功的优化例子： “最优人员安排”为美国航空每年节约两千万美元. “改进的出货流程”每年为Yellow Freight 公司节约一千七百多万美元. “改进的卡车分派”为 Reynolds 公司每年节约七百万美元 . 最优全局供应链为数字设备行业节约超过三亿美元. 重建的 North America Operations, Proctor and Gamble减少 20%的工厂, 每年节约两亿美元. 大阪的Hanshin高速的最优安排每年节约一千七百万人小时 .
生产计划问题
规划模型 m a x Z 4 x1 3 x 2 2 x 3
利润
2 x1 3 x2 x3 34
材料
s .t .
3 3
x1 x1
2 2
x2 x2
1.5 x3 5 x3
3 40
6
工时 人力
x1 , x 2 , x 3 0
222021/1/21
线性规划模型
生产计划问题
线性规划解的图示
X2 2 X1 + X2 = 40
max z = 5x1+3x2 s.t. 2x1+x2≤40
x1+2x2≤50 x1，x2≥0
25 x1=10,x2=20
X1 + 2 X2 = 50
a
20 P=110
X1
P=50 P=0
问:什么样的问题可以使用图解法?你从图中得到什么启示?
226021/1/21
数学实验第五次讲稿
实验目的
1．理解优化模型的三个要素:决策变量，目标函数和约束条件； ２．掌握用MATLAB优化工具箱求解线性规划的方法； ３．体验由实际问题建立线性规划模型的全过程。
2
2021/1/21
一,优化问题的普遍性以及引例
1，无处不在的优化 每一个人，高致总统首相，总裁经理，平民百姓，无不在做决策：该做什么，该怎Fra Baidu bibliotek做，才能有最好的
LP的通常解法是单纯形法。
2021/1/21
28
MATLAB软件求解 Matlab中求解线性规划的命令为: linprog, 解决的线性规划的标准格式为：
min cTx x∈Rn s.t. A·x <= b
Aeq·x = beq VLB≤x≤VUB 其中，A, b, c, x, Aeq, beq, VLB, VUB等均表示矩阵,特别b, c, x, beq, VLB, VUB为列矩阵。
带约束条件,我们称之为无约束优化问题.而在实际问题中,决策变量带有约束是普遍的.
2021/1/21
15
三,优化问题的分类
优化问题的分类可以从几个方面进行: 1,从变量取值的连续和离散可以分成:连续优化,离散优化和混合优化 2,从问题的线性非线性可以分为:线性规划和非线性规划 3,从变量是确定性和随机性可以分为:随机规划和确定性问题.
2021/1/21
12
二，优化问题的表述
• 目标函数
•
对应决策者而言,对其有利的程度必须定量的测度, 在商业应用中，有效性的测度经
常是利润或者成本, 但对于政府，更经常的使用投入产出率来测度.
•
表示有效性测度的经常称为目标函数.目标函数要表出测度的有效性, 必须说明测度和
导致测度改变的变量之间的关系. 系统变量分为决策变量和参数.决策变量是指能由决策者直接控
2021/1/21
8
引例1,动物饲料配置问题
美国一家公司以专门饲养并出售一种实验用的动物而闻名。这种动物的生长对饲料中的三种营养 成分特别敏感，即蛋白质、矿物质和维生素。
需 要
蛋白质：70克
的
营
养
量
矿物质：3克
维生素：9.1毫克 现有五种饲料，公司希望找出满足动物营养需要使成本达到最低的混合饲料配置。
② 无最优解
③ 最优解不唯一
L2 x1
27
线性规划的基本性质
2维
可行域 线段组成的凸多边形 目标函数 等值线为直线 最优解 凸多边形的某个顶点
n维
超平面组成的凸多面体 等值线是超平面 凸多面体的某个顶点
LP的基本性质： 可行域存在时，必是凸多面体； 可行解对应于可行域中的点； 最优解存在时，必在可行域的顶点取得。
m ax Z 4 x1 3 x2 2 x3
利润
2 x1 3 x2 x3 34
材料
s
.t
.
3 3
x x
1 1
2 2
x2 x2
1.5 x3 5 x3
36 40
工时 人力
x1 , x 2 , x 3 0
矩阵形式：
cT [4, 3, 2], x T [ x1, x2 , x3 ]
2021/1/21
11
二,优化问题建模的基本步骤介绍
在我们的生活中,始终有这样的问题:为了一定的目的做一些事情,我们可能要考虑有哪些重要的因 素,这些因素和要完成的目标之间有什么样的关系.也就是说,我们在做一个决定时,会注意下面的三个 要点: 目的是什么? 有哪些重要的因素? 这些因素和你的目标之间有什么样的关系?
Leonid Vitalyevich Kantorovich
2021/1/21
19
• 非线性规划问题在实践中也是及其常见的.标志着这一学科的产生的奠基性工作由美国的数学家 Tucker和Kuhn在1952年的一篇文章.该文章给出了非线性规划问题的必要条件和充分条件,后来成为 Kuhn-Tucker条件.这为非线性规划问题的求解算法的提出提供了理论基础和算法的基本思路.
是决策者采用决策的依据.在系统中还有一些量,它不能由决策者所控制,而是由系统所处的环境所
决定,我们称之为参数.
2021/1/21
14
二，优化问题的表述
• 约束条件
•
约束条件就是决策变量和参数之间的关系. 约束集界定决策变量可以取某些值而不能取
其他的值.比如对应生产问题, 任何活动中,时间和物品不能为负数.当然,也有一些优化问题不
• 相关的规划问题,比如多目标规划,决策论等等.
2021/1/21
20
决策变量 目标函数 约束条件 221021/1/21
x1, x2, x3
规划模型
max
Z4x13x22x3 利润
2x13x2x334 材料
3x12x21.5x336工时
3x12x25x340 人力
x1,x2,x3 0
生产计划问题