当前位置：文档之家 › 数学建模 司守奎01第1章 线性规划

数学建模 司守奎01第1章 线性规划

  • 格式：ppt
  • 大小：1.52 MB
  • 文档页数：39

下载文档原格式

  / 39

合集下载

第1章线性规划

第1章线性规划

第1章 线性规划与单纯形法
从图解法中我们可以直观地看到： 1、当线性规划问题的可行域非空时，它是有界或无 界的凸多边形； 2、若线性规划存在最优解，它一定是在有界可行域 的某个顶点得到； 3、如果在两个顶点同时得到最优解，则它们连线上 的任意一个点都是最优解，即有无穷多个最优点。 图解法虽然直观、简便，但是当变量多于三个以上 时就无能为力了。因此后面要介绍一种代数法—单纯 形法。为了便于讨论，先规定线性规划问题的数学模 型的标准形式。
此外，各种合金的加入量以整吨为单位，即限制x1、x2、 x3、x4≥0，且为整数。 综上所述，我们得到该问题的数学模型为：
第1章 线性规划与单纯形法
min z 11.5 x1 9.7 x 2 8.2 x 3 7.6 x 4 3.21 x1 4.53 x 2 2.19 x 3 1.76 x 4 320 2.04 x1 1.12 x 2 3.57 x 3 4.33 x 4 210 s .t . 5.82 x1 3.06 x 2 4.27 x 3 2.73 x 4 430 x x x x 100 2 3 4 1 x1 , x 2 , x 3 , x 4 0 , 且为整数
设选用原材料T1，T2，T3，T4的量分别为x1、x2、x3、x4。 由于追求目标是成本最小，故有最小成本表达式： min z 11.5 x1 9.7 x2 8.2 x3 7.6 x4 炼制过程中质量没有损耗，熔炼不锈钢100吨，故有：
x1 x2 x3 x4 100
第1章 线性规划与单纯形法
或简写为：
第1章 线性规划与单纯形法
max z c j x j
j 1 n
n a ij x j b j , i 1 ,2 , , m j 1 x 0 , j 1 ,2 , , n j

《管理运筹学》教学课件-第1章线性规划

《管理运筹学》教学课件-第1章线性规划

要求至少应增加出油能力500桶/天，但又不得超过1100桶/天，试确定该公司总经济效益最大的
投资方案。
表 1.5
方 案 序 号
投资方案内容
技改方案内容
决
投资（万元）
策
年收益
变 量
第一年 第二年 （万元）
1 更新旧装置，提高炼油能力 500 桶/ X1
200
200
100
天
2 建造新装置， 提高炼油能力 1000 X2
2 、数学模型中系数的含义:
Max Z = 70x1＋30x2 s.t. 3x1 + 9x2 ≤ 540
5x1 + 5x2 ≤ 450 9x1 + 3x2 ≤ 720 x1 , x2 ≥0
…① …② …③ …④ …⑤
①.目标函数中决策变量的系数70,30 ------ 叫价值系数，表单位产品提供的利润(元/件)；
1946年，世界上第一台计算机问世，使单纯形法处理大规模L.P.数模成为可能。
三、 L.P.问题的求解过程
1、将实际问题转化为数学模型(数学公式)：建模。 2、求解数学模型：
• 图解法： 适合于 2 个变量的 L.P. 数学模型。 • 单纯形法：适合于任意个变量的 L.P. 数学模型。 3、利用数学模型的最优解获得原问题的最优决策方案。
解: ① 设甲、乙产品产量分别为x1、x2 公斤——— 决策变量，简称变量 ② 设总利润为Z，则
Max Z = 70x1＋30x2 ③ 设备可用工时数限制
——— 目标函数 ——— 约束条件
s.t. 3x1 + 9x2 ≤ 540 A 设备可用工时约束
5x1 + 5x2 ≤ 450 B 设备可用工时约束

数学建模线性规划

数学建模线性规划

线性规划1.简介：线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.规划问题。

一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。

在优化模型中，如果目标函数f(x)和约束条件中的gi(x)都是线性函数，则该模型称为线性规划。

2.线性规划的3个基本要素（1）决策变量（2）目标函数f(x)（3）约束条件（gi(x)≤0称为约束条件）3.建立线性规划的模型（1）找出待定的未知变量（决策变量），并用袋鼠符号表示他们。

（2）找出问题中所有的限制或者约束，写出未知变量的线性方程或线性不等式。

（3）找到模型的目标或判据，写成决策变量的线性函数，以便求出其最大值或最小值。

以下题为例，来了解一下如何将线性规划用与实际的解题与生活中。

生产计划问题某工厂生产甲乙两种产品，每单位产品消耗和获得的利润如表试拟订生产计划，使该厂获得利润最大解答：根据解题的三个基本步骤（1）找出未知变量，用符号表示：设甲乙两种产品的生产量分别为x1与x2吨，利润为z万元。

（2）确定约束条件：在这道题目当中约束条件都分别为：钢材，电力，工作日以及生产量不能为负的限制钢材：9x 1+5 x 2≤360，电力：4x 1+5 x 2≤200，工作日：3x 1+10 x 2≤300，x 1 ≥0 ，x 2 ≥0，（3）确定目标函数：Z=7x 1+12 x 2所以综合上面这三步可知，这个生产组合问题的线性规划的数学模型为：max Z=7x 1+12 x 2s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥≤+≤+≤+00300103200543605921212121x x x x x x x x4.使用MATLAB 解决线性规划问题依旧是以上题为例，将其用MATLAB 来表示出来1.将目标函数用矩阵的乘法来表示max Z=(7 12)⎪⎪⎭⎫ ⎝⎛21x x 2.将约束条件也用矩阵的乘法表示s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧⎪⎪⎭⎫ ⎝⎛≤⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎭⎫ ⎝⎛≤⎪⎪⎭⎫ ⎝⎛⎪⎪⎪⎭⎫ ⎝⎛2121003002003601035459x x x x 编写MATLAB 的程序如下：c=[-7 -12]; (由于是max 函数，因此将目标函数的系数全部变为负数)A=[9,5;4,5;3,10];b=[360;200;300];Aeq=[];beq=[];vlb=[0;0];vub=[];[x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub)其运行结果显示如下：x =20.000024.0000fval =-428.00005.MATLAB 求解线性规划的语句(1)c=[ ] 表示目标函数的各个决策变量的系数(2)A=[ ] 表示约束条件中≥或≤的式子中的各个决策变量的系数。

线性规划数学模型

线性规划数学模型

目标规划的数学模型
4.达成函数(即目标规划中的目标函数) 目标规划的目标函数(准则函数)是按各目标约束的正、负 偏差变量和赋予相应的优先因子及权系数而构造的。当每 一目标值确定后，决策者的要求是尽可能缩小偏离目标值。 因此目标规划的目标函数只能是minZ = f(d＋、d－)。 一般说来，有以下三种情况，但只能出现其中之一： (1)要求恰好达到规定的目标值，即正、负偏差变量要尽 可能小，则minZ = f(d＋＋ d－)。 (2)要求不超过目标值，即允许达不到目标值，也就是正 偏差变量尽可能小，则minZ = f(d＋)。 (3)要求超过目标值，即超过量不限，但不低于目标值， 也就是负偏差变量尽可能小，则minZ = f(d－)。 对由绝对约束转化而来的目标函数，也照上述处理即可。
• 为了弥补线性规划问题的局限性，解决有限资源和计 划指标之间的矛盾，在线性规划基础上，建立目标规 划方法，从而使一些线性规划无法解决的问题得到满 意的解答。
目标规划与线性规划的比较
• 线性规划只讨论一个线性目标函数在一组线性约束条 件下的极值问题；而目标规划是多个目标决策，可求 得更切合实际的解。
润比作为权系数即70:120，化简为7:12，P2(7d2＋+12d2 -)
第二目标：P3(d4＋+d4 -)
MinZ = P1d1- + P2 (7d2+ +12d3- ) + P3 (d4- + d4+ )
st
3974xx102xxx11+1x+++1+dd+1542-3-01xx--2x2220d+dx2+3+d223=40=-+00-22d000510d-004+-

第一章 线性规划

第一章 线性规划

第1章线性规划Chapter 1 Linear Programming本章内容提要线性规划是运筹学的重要内容。

本章介绍线性规划数学模型、线性规划的基本概念以及求解线性规划数学模型的基本算法——单纯形法。

学习本章要求掌握以下内容：⏹线性规划模型的结构⏹线性规划的标准形式，非标准形式转化为标准形式⏹线性规划的图解以及相应的概念。

包括：约束直线，可行半空间，可行解，可行域，凸集，极点，目标函数等值线，最优解⏹线性规划的基本概念。

包括：基，基础解，基础可行解，基变量，非基变量，进基变量，离基变量，基变换⏹单纯形法原理。

包括：基变量和目标函数用非基变量表出，检验数，选择进基变量的原则，确定离基变量的方法，主元，旋转运算⏹单纯形表。

包括初始单纯形表的构成，单纯形表运算方法⏹初始基础可行解，两阶段法⏹退化的基础可行解§1.1 运筹学和线性规划1.1.1 运筹学运筹学（Operations Research）是二十世纪三十年代二次大战期间由于战争的需要发展起来的一门学科。

当时，英国组织了一批自然科学和工程科学的学者，和军队指挥员一起，研究大规模战争提出的一些问题。

如轰炸战术的评价和改进、反潜艇作战研究等，研究结果在战争实践中取得了明显得效果。

这些研究当时在英国称为Operational Research，直译为作战研究。

战争结束以后，这些研究方法不断发展完善，并逐步形成学科理论体系，其中一些主要的理论和方法包括：线性规划，网络流，整数规划，动态规划，非线性规划，排队论，决策分析，对策论，计算机模拟等。

这些理论和方法在经济管理领域也得到了广泛应用，Operations Research也转义成为“作业研究”。

我国将Operations Research译成“运筹学”，非常贴切地将Operations Research这一英文术语所包含的作战研究和作业研究两方面的涵义都体现了出来。

现在，运筹学已经成为管理科学重要的基础理论和应用方法，是管理科学专业基本的必修课程之一。

线性规划数学模型

线性规划数学模型
该企业应如何拟定生产计划？
七、生产计划问题的数学模型
一、决策变量
设xj为第j种产品的计划产量
二、约束条件 ⑴ 指标约束 ⑵ 需求约束 ⑶ 资源约束
三、目标函数 ⑴ 总产值 ⑵ 总成本
xj ≥ ej ,
xj ≤ dj ,
n
∑a x j=1 ij j
≤
bi,
j = 1,2,… ,n j = 1,2,… ,n i = 1,2,…,m
它的适用领域非常广泛，从工业、农业、商业、交通 运输业、军事的计划和管理及决策到整个国民经济计 划的最优方案的提出，都有它的用武之地，是现代管 理科学的重要基础和手段之一。
3
第一节 线性规划问题的提出
线性规划研究的问题主要有以下两类。
(1) 给出一定量的人力、物力、财力等资源，如何统筹 规划这些有限资源完成最大任务。（如资金、设备、原标 材料、人工、时间等） (2) 给定一项任务，如何运筹规划，合理安排，以最少 资源来完成它。（如产品量最多 、利润最大.）
原料D不少于25% 原料P不超过50%
单价(元/kg)
50 35
原料
最大供量 (kg/天)
单价 (元/kg)
A 100
65
B 100
25
Z
不限
25
C 60
35
应如合配制，才能使利润达到最大？
二、配料问题的数学模型
一、决策变量
设以 xij 表示每天生产的 第i 种产品中所含第j 种原料 的数量(kg，右表)。
配料问题
原料 化学成分
成分含量(%)
甲
乙
产品成分 最低含量(%)
A
12
3
4
B
2
3

数学建模（司守奎）目录

目录第一章线性规划 (1)§1 线性规划 (1)1.1 线性规划的实例与定义 (1)1.2 线性规划的Matlab 标准形式 (1)1.3 线性规划问题的解的概念 (2)1.4 线性规划的图解法 (2)1.5 求解线性规划的Matlab 解法 (3)1.6 可以转化为线性规划的问题 (4)§2 运输问题 (4)§3 指派问题 (5)§4 对偶理论与灵敏度分析 (7)习题一 (9)第二章整数规划 (11)§1 概论 (11)§2 分枝定界法 (11)0-整数规划 (13)§3 10-变量的实际问题 (14)3.1 引入10-整数规划解法之一 (15)3.2 1§4 蒙特卡洛法（随即取样法） (16)§5 整数规划的计算机解法 (17)习题二 (18)第三章非线性规划 (19)§1 非线性规划 (19)1.1 非线性规划实例与定义 (19)1.2 线性规划与非线性规划的区别 (20)1.3 非线性规划的Matlab 解法 (20)1.4 求解非线性规划的基本迭代格式 (21)1.5 凸函数、凸规划 (22)§2 无约束问题 (22)2.1 一维搜索方法 (22)2.2 二次插值法 (25)2.3 无约束极值问题的解法 (25)2.4 Matlab求函数的极小值和函数的零点 (31)§3 约束极值问题 (31)3.1 最优性条件 (32)3.2 二次规划 (32)﹒i﹒3.3 罚函数法 (32)§4 飞行管理问题 (33)习题三 (34)第四章动态规划 (35)§1 引言 (35)§2 基本概念，基本方程和计算方法 (36)§3 逆序解法的计算框图 (38)§4 动态规划与静态规划的关系 (39)§5 若干典型问题的动态规划模型 (41)习题四 (42)第五章图与网络模型及方法 (44)§1 概论 (44)§2 图与网络的基本概念 (45)§3 应用—最短路问题 (51)§4 树 (53)§5 匹配问题 (56)§ 6 Euler图和Hamilton图 (57)§7 最大流问题 (61)§8 最小费用流及其求法 (66)习题五 (67)第六章排队论模型 (69)§1 基本概念 (69)§2 输入过程与服务时间的分布 (71)§3 标准的M/M/1模型 (74)§4 产生给定分布的随机数的方法 (75)§5 排队模型的计算机模拟 (76)习题六 (79)第七章对策论 (80)§1 引言 (80)§2 对策问题 (80)§3 零和对策的混合策略 (83)§4 零和对策的线性规划解法 (85)习题七 (88)第八章层次分析法 (89)§1 层次分析法的基本原理与步骤 (89)§2 层次分析法的应用 (93)习题八 (95)第九章插值与拟合 (97)§1 插值方法 (97)﹒ii﹒1.1 拉格朗日多项式插值 (97)1.2 牛顿插值 (99)1.3 分段线性插值 (101)1.4 埃尔米特(Hermite)插值 (102)1.5 样条插值 (103)1.6 二维插值 (106)§2 曲线拟合的线性最小二乘法 (107)2.1 线性最小二乘法 (107)2.2 最小二乘法的Matlab实现 (108)§3 曲线拟合与函数逼近.....................................................................109 习题九 (110)第十章数据的统计描述和分析 (112)§1 统计的基本概念…………………………………………………………………11 2§2 参数估计 (118)§3 假设检验 (119)习题十 (123)第十一章方差分析 (124)§1 单因素方差分析 (124)§2 双因素方差分析 (128)习题十一 (129)第十二章回归分析 (131)§1 多元线性回归 (131)§2 非线性回归和逐步回归..................................................................138 习题十二 (141)第十三章微分方程建模 (143)§1 发射卫星为什么用三级火箭 (143)§2 人口模型 (148)§3 战争模型 (150)习题十三 (155)第十四章稳定状态模型 (157)§1 微分方程稳定性理论简介………………………………………………………157 §2 再生资源的管理和开发…………………………………………………………159 §3 V olterra模型……………………………………………………………………16 4﹒iii﹒习题十四 (168)第十五章常微分方程的解法 (169)§1 常微分方程的离散化……………………………………………………………169 §2 欧拉(Euler)方法…………………………………………………………………170 §3 改进的(Euler)方法………………………………………………………………17 1§4 龙格—库塔(Runge—Kutta)方法 (172)§5 线性多步法 (174)§6 一阶微分方程组与高阶微分方程的数值解法…………………………………17 5§7 Matlab 解法……………………………………………………………………17 6 习题十五 (181)第十六章差分方程模型 (182)§1 差分方程 (182)§2 蛛网模型 (185)§3 商品销售量预测 (188)§4 遗传模型 (190)习题十六 (196)第十七章马氏链模型 (197)§1 随机过程的概念 (197)§2 马尔可夫链 (197)§3 马尔可夫链的应用 (205)习题十七 (206)第十八章动态优化模型 (208)§1 变分法简介 (208)§2 生产设备的最大经济效益 (216)习题十八 (219)第十九章神经网络模型 (220)§1 神经网络简介 (220)§2 蠓虫分类问题与多层前馈网络 (222)§3 处理蠓虫分类的另一种网络方法 (226)习题十九 (229)第二十章偏微分方程的数值解 (230)§1偏微分方程的定解问题 (230)§2 偏微分方程的差分解法 (232)§3 Matlab 解法 (237)﹒iv﹒习题二十 (241)第二十一章目标规划 (243)§1 目标规划的数学模型 (243)§ 2 多目标规划的Matlab解法 (245)习题二十一 (246)附录一Matlab入门 (247)附录二Matlab在线性代数中的应用 (253)附录三运筹学的Lingo软件 (257)参考文献 (260)﹒v﹒。

第一章 线性规划

第四节 线性规划的典型案例
线性规划
【开篇案例】
一、人力资源分配的问题
某旅行社为了迎接旅 游黄金周的到来，对一日 游导游人员的需求经过统 计分析如表所示。为了保 证导游充分休息，导游每 周工作 5天，休息两天， 并要求休息的两天是连续 的。问应该如何安排导游 人员的作息，既满足工作 需要，又使配备的导游人
下午5时14分
什么是规划？
• 以上问题无一例外都属于规划问题，涉及到求解最大值 和最小值
• 人们经常谈规划，比如国家有5年规划、10年规划、城市 有城市规划，个人有自己的人生规划.
• 规划是在现有的人力、物力水平下，使得目标达到最优 的全面、理性的计划
下午5时14分
线性规划
• 线性规划简介： • 运筹学中最成熟的一个分支 • 静态规划：单周期决策
第一节 下午5时14分 线性规划的一般模型
三、线性规划模型的特征
1. 模型隐含假定
作为严密的数学模型，线性规划蕴含着以下假定： （1）线性化假定
函数关系式f(x)= c1x1+c2x2+… +cnxn，称线性函数。 经济学中大多数函数都是非线性，通过偏导求最优。但在企业
运营决策中，经常考虑比较短时间内的计划安排，通过线性化 更便于应用。
乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？
甲
乙
丙
资源限制
铸造工时(小时/件)
5
10
7
8000
机加工工时(小时/件)
6
4
8
12000
装配工时(小时/件)
3
2
2
10000
自产铸件成本(元/件)
3
5
4
外协铸件成本(元/件)

第1章线性规划


(0,6)
3x1+2x2=18 x1=4
(2,6) (4,6)
2x2=12
(4,3)
3x1+5x2=50
(0,0)
(4,0) (6,0)
x2=0 x1
无可行解
若线性规划问题的决策变量超过2个时， 应用图解法求解时便会显得很困难。这里需 要解决线性规划问题的更一般的代数的方 法——单纯形法。
单纯形法可以解决成千上万个变量或约 束条件的线性规划问题。
x1 ，x2 ，x3 ，x4 ，x5 ≥ 0
需要指出的是：线性规划问题的标准形 式与其原始形式是等价的，即一个线性规划 问题的最优解与其标准形式的最优解的值是 一样的。一个问题的标准形式并不改变问题 的本质，它只是改变对问题约束条件的写法。
我们已经说过，单纯形法需要标准形式。但对 于单纯形法，我们不做深入探讨，这里只给出几个 必要的基本概念。
在使用单纯形法解决问题中，必须对线 性规划的一般形式进行变形，化为标准形式。
线性规划的标准形式： n
max z = c j x j
j 1
s.t.
n j 1
aij x j
bi
(i 1,2, m)
x j 0
( j 1,2, n)
①目标函数取极大化， ②约束条件全为等式，
③约束条件右端常数项均为非负值，④变量
令非基变量x1＝x2＝0，解得x3＝4， x4＝12， x5＝18，则x＝(0,0,4,12,18)T是一个基解。因该基解 中所有变量取值为非负，满足线性规划问题的所有 约束条件，故也是基可行解。
1.2 对偶问题
例1.3（委托加工）对于例1.1的产品组合问 题，公司从交易市场上得到另一信息：某中 间商得到一笔生产与公司相同产品的合同。 但该中间商并没有生产这些产品的设备，欲 委托该公司为其加工产品。现在的问题是公 司应该让中间商至少付出多少代价，才能放 弃这两种新产品的生产，为中间商委托生产？

运筹学第一章线性规划

Z＝ X1＋X2 X1
《运筹学》 第一章 线性规划
Slide 18
4、无可行解——可行域为空集
X2
maxz=2X1+4X2
L3: X1<=4
s.t.
L1: X1+X2>=6
X1＋X2>=6 X1＋2X2<=6
L2: X1＋2X2<=6
L4: X2<=3
X1 <=4, X2<=3
X1>=0, X2>=0
二、一般线性规划问题的建模过程（方法）
追求什么目标？ 决策变量？ 目标函数？ 约束条件？
《运筹学》 第一章 线性规划
Slide 4
课本P4例1.1: 生产安排问题 设X1,X2,X3是甲、乙、丙三种产品的产量，Z是工厂 的总利润。 maxz=3X1+2X2+5X3
s.t. X1+2X2+X3<=430 ——第一道工序 3X1＋2X3<=460 ——第二道工序 X1+4X2<=420 ——第三道工序 X1>=0, X2>=0 , X3>=0
b1
b2
Xm＝
bm
－
a1m1 a2m1 amm1
Xm＋1
a1n
a2n
－用…向－量的am形n 式Xn表示为：(1.j1m18a) j x j
b
n
ajxj
j m1
(1.19)
方程组的基是B，设XB是对应于这个基的基变量，XB=（
X1，X2，…，Xm）T
《运筹学》 第一章 线性规划
满足约束条件：
am
x1 1 am x2 2 x1, x2,, xn
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

12/39
数学 建模
（2）求解的 Matlab 程序如下 f=[-2; -3; 5]; a=[-2,5,-1;1,3,1]; b=[-10;12]; aeq=[1,1,1]; beq=7; [x,y]=linprog(f,a,b,aeq,beq,zeros(3,1)); x, y=-y
13/39
数学 建模
6/39
数学 建模
1.1.2 线性规划问题的解的概念
一般线性规划问题的（数学）标准型为
n
max
(1.3）
z=
å
cj xj ，
j= 1
n ì ï ï aij x j = bi i = 1, 2,L , m , å ï ï s.t. í j= 1 ï ï ï ï î x j ? 0 j 1, 2,L , n. 其中 bi ³ 0， i = 1, 2,L , m 。
数学建模算法与应用
第1章 线性规划
基础部数学教研室
数学 建模
1.1 线性规划问题
在人们的生产实践中，经常会遇到如何利用现有资源 来安排生产，以取得最大经济效益的问题。此类问题构成 了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记 LP)则是数学规划的一个重要分支。 自 从 1947 年 G. B. Dantzig 提出求解线性规划的单纯形方法 以来，线性规划在理论上趋向成熟，在实用中日益广泛与 深入。特别是在计算机能处理成千上万个约束条件和决策 变量的线性规划问题之后，线性规划的适用领域更为广泛 了，已成为现代管理中经常采用的基本方法之一。
i= 1
min
å
n
( ui + vi ) ，
i= 1
s. t.
19/39
ì 轾 u ï ï ? b, ï [ A, - A] 犏 犏 v í 臌 ï ï ï ï î u, v ³ 0.
数学 建模
例1.5（续例1.4类型的实例） 求解下列数学规划问题 min z = | x1 | + 2 | x2 | + 3 | x3 | + 4 | x4 | ， ì ï ï ï x1 - x2 - x3 + x4 ? 2, ï ï s.t. ï í x1 - x2 + x3 - 3 x4 ? 1, ï ï 1 ï ï x1 - x2 - 2 x3 + 3 x4 ? . ï ï 2 î
数学 建模
例 1.2 求解下列线性规划问题 max z = 2 x1 + 3 x2 - 5 x3 ， s.t. x1 + x2 + x3 = 7 ， 2 x1 - 5 x2 + x3 ? 10 ， x1 + 3 x2 + x3 ? 12 ， x1 , x2 , x3 ³ 0 .
求得的最优解为 x1 = 6.4286 , x2 = 0.5714， x3 = 0 ，对应 的最优值 z = 14.5714 。
14/39
（3）求解的Lingo程序如下 model: sets: row/1..2/:b; col/1..3/:c,x; links(row,col):a; endsets data: c=2 3 -5; a=-2 5 -1 1 3 1; b=-10 12; enddata max=@sum(col:c*x); @for(row(i):@sum(col(j):a(i,j)*x(j))<b(i)); @sum(col:x)=7; end
线性规划的目标函数可以是求最大值， 也可以是求最 小值，约束条件的不等号可以是小于号也可以是大于号。 为了避免这种形式多样性带来的不便，Matlab 中规定线 性规划的标准形式为 min f T x ，
ì A祝 x b, ï ï ï s.t. í Aeq ? x beq , ï ï ï ï î lb ＃x ub. 其中 f , x, b, beq, lb, ub 为列向量， f 称为价值向量， b 称为
数学 建模
解 （1）化成 Matlab 标准型 min w = - 2 x1 - 3 x2 + 5 x3 ， 轾 x1 轾 轾 - 2 5 - 1犏 - 10 犏 x2 £ 犏 ， s.t. 犏 犏 犏 犏 1 3 1 12 臌 臌 犏 x3 臌 [1, 1, 1]?[ x1 , x2 , x3 ]T 7 .
20/39
数学 建模
xi + | xi | | xi | - xi 解 做 变 量 变 换 ui = ， vi = ， 2 2 i = 1,2,3,4 ， 并 把 新 变 量 重 新 排 序 成 一 维 向 量 轾 u y = 犏 = [u1 ,L , u4 , v1 ,L , v4 ]T ，则可把模型变换为线性规划 犏 v 臌 模型 min cT y ， ì 轾 u ï ï ? b, ï [ A, - A] 犏 犏 s. t. í v 臌 ï ï ï ï î y ³ 0.
15/39
数学 建模
例1.3 求解线性规划问题 min z = 2 x1 + 3 x2 + x3 ， ì x1 + 4 x2 + 2 x3 ? 8, ï ï ï s.t. í 3 x1 + 2 x2 ? 6, ï ï ï ï î x1 , x2 , x3 ³ 0.
16/39
数学 建模
解 编写Matlab程序如下 c=[2;3;1]; a=[1,4,2;3,2,0]; b=[8;6]; [x,y]=linprog(c,-a,-b,[],[],zeros(3,1)) 束，对应的矩阵为空矩阵
18/39
数学 建模
记 u = [u1 ,L , un ]T ，v = [v1 ,L , vn ]T ，从而可以把上面的 问题变成
min
å
n
( ui + vi ) ，
ì A( u - v ) ? b, ï ï s. t. í ï ï î u, v ³ 0. 这里 u ³ 0 表示向量 u的每个分量大于等于 0。 进一步把模型改写成
24/39
数学 建模
例 1.6
min{max | e i |}，其中e i = xi - yi 。
xi yi
取 v = max | e i |，这样，上面的问题就变换成
yi
min v ， ì x1 - y1 ? v ,L , xn ï ï s.t. í ï ï î y1 - x1 ? v ,L , yn
求得最优解 x1 = - 2 ， x2 = x3 = x4 = 0 ，最优值 z = 2 。
23/39
数学 建模
Lingo程序如下 model: sets: col/1..4/:c,x; row/1..3/:b; links(row,col):a; endsets data: c=1 2 3 4; b=-2 -1 -0.5; a=1 -1 -1 1 1 -1 1 -3 1 -1 -2 3; enddata min=@sum(col:c*@abs(x)); @for(row(i):@sum(col(j):a(i,j)*x(j))<b(i)); @for(col:@free(x)); !x的分量可正可负; end
yn ? v , xn ? v .
25/39
数学 建模
1.2 投资的收益和风险 1.2.1 问题提出
市场上有 n种资产 si（ i = 1,2,L , n）可以选择，现用数 额为 M 的相当大的资金作一个时期的投资。这 n 种资产在 这一时期内购买 si 的平均收益率为 ri ，风险损失率为 qi ，投 资越分散，总的风险越少，总体风险可用投资的 si 中最大 的一个风险来度量。 购买 si 时要付交易费，费率为 pi ，当购买额不超过给 定值 ui 时，交易费按购买 ui 计算。另外，假定同期银行存 款利率是 r0 ，既无交易费又无风险（ r0 = 5%） 。 已知 n = 4 时相关数据如表 1.1。
%这里没有等式约
x3 = 0.0166， 求得的最优解为 x1 = 0.8066 , x2 = 1.7900 ， 对应的最优值 z = 7.0000 。
17/39
数学 建模
1.1.4 可以转化为线性规划的问题
例1.4 数学规划问题 min | x1 | + | x2 | + L + | xn |,
4/39
数学 建模
上述问题的数学模型：设该厂生产 x1 台甲机床和 x 2 乙 机床时总利润 z 最大，则 x1 , x2 应满足 max z = 4 x1 + 3 x2 ， （1.1） ì 2 x1 + x2 ? 10, ï ï ï ï x1 + x2 ? 8, ï s.t.í (1.2） ï x2 £ 7, ï ï ï ï î x1 , x2 ³ 0. 变量 x1 , x2 称之为决策变量， （1.1）式被称为问题的目
x
资源向量， A, Aeq 为矩阵。
9/39
数学 建模
Matlab 中求解线性规划的命令为 [x,fval] = linprog(f,A,b) [x,fval] = linprog(f,A,b,Aeq,beq) [x,fval] = linprog(f,A,b,Aeq,beq,lb,ub) 其中 x 返回的是决策向量的取值， fval 返回的是目标函 数的最优值，f 为价值向量，A，b 对应的是线性不等式 约束，Aeq，beq 对应的是线性等式约束，lb 和 ub 分 别对应的是决策向量的下界向量和上界向量。
10/39
数学 建模
例 1.2 求解下列线性规划问题 max z = 2 x1 + 3 x2 - 5 x3 ， s.t. x1 + x2 + x3 = 7 ， 2 x1 - 5 x2 + x3 ? 10 ， x1 + 3 x2 + x3 ? 12 ， x1 , x2 , x3 ³ 0 .