运筹学 (1)
- 格式：doc
- 大小：124.50 KB
- 文档页数：3
下载文档原格式
合集下载
运筹学(一)
第三节
单纯形法原理
一、线性规划问题的解
可行解：满足约束条件的解称为可行解，可行解的集合称
a m 1 x1
a
m
2
x2
amnxn (,)bm
x1, x2 , , xn 0
n : 变 量 个 数 ; m:约 束 行 数 ;
n:变量个数 m：约束个数 cj:价值系数 bi:资源拥有量 aij :工艺系数
n m :线性规划问题的规模
c j : 价 值 系 数 ; b j : 右 端 项 ; aij : 技 术 系 数
2x1 x2 x3 x3 x4 9
st.34xx11
x2 2x3 2x3 x5 2x2 3x3 3x3 6
4
x1, x2, x3, x3, x4, x5 0
第二节
图解法
一、图解法的步骤
1.画出直角平面坐标系； 2.图示约束条件，找出可行域； 3.图示目标函数； 4.最优解的确定。
x2 2x2
2x3 3x3
4 6
x1 0, x2 0, x3取值无约束
解： z令 z,x1x1,x3x3 x3 ,其x中 3 ， x3 0， 同时引入x4松 和弛 剩变 余 x5,标 量 变准 量形式
m z x a 1 2 x 2 x 3 x 3 3 x 3 0 x 4 0 x 5
1940年，英国军事部门成立了第一个由一些数学家、物理学家 和工程专家等组成的OR小组，负责研究一些武器有效使用的问题。
1942年，美国也成立了由17人组成的OR小组，研究反潜艇策 略等问题。
（3）二战后：推广与发展
战时从事运筹学研究的许多专家转到了经济部门、民用企业、大 学或研究所，继续从事决策的数量方法的研究，运筹学作为一门学 科逐步形成并得以迅速发展。运筹学发展到今天，已成为分支学科 众多的一个繁荣昌盛的大家族。随着电子计算机的发展和使用，运 筹学处理复杂性问题的能力大大加强，成为解决实际问题的有力工 具，广泛地应用于企业管理、交通运输、公共服务等领域。
运筹学(1)
一、绪论§1 运筹学的简史运筹学作为科学名称出现于20世纪30年代末。
英、美对付德国空袭，采用雷达，技术上可行，实际运用不好用。
如何合理运用雷达？“运用研究”（Operational Research）,我国1956年用“运用学”名词，1957年正式定名为运筹学。
运筹学小组在英、美军队中成立，研究：护航舰队保护商船队的编队问题、当船队遭受德国潜艇攻击时如何使船队损失最小问题、反潜深水炸弹的合理爆炸深度（德国潜艇被摧毁数增到400%）、船只在受敌机攻击时的逃避方法（大船急转向、小船缓转向，中弹数由47%降到29%）。
运筹学组织在英、美军队（RAND）中成立，研究：战略性问题、未来武器系统的设计和合理运用方法、美国空军各种轰炸机系统的评价、未来武器系统和未来战争战略、苏联军事能力及未来预报、苏联政治局计划的行动原则和未来战争的战略、到底发展哪种洲际导弹（50年代）、战略力量的构成和数量（60年代）。
运筹学在工业、农业、经济、社会问题等领域有应用。
运筹数学：数学规划（线性规划（丹捷格（G.B.Dantzig）1947，单纯形法；康托洛维奇1939解乘数法，1960《最佳资源利用的经济计算》，诺贝尔奖；列昂节夫1932投入产出模型；冯.诺意曼）、非线性规划、整数规划、目标规则、动态规划、随机规划等）、图论与网络、排队论（随机服务系统理论）(丹麦工程师爱尔朗（Erlang）1917提出一些著名公式)、存贮论、对策论（冯.诺意曼和摩根斯坦，1944《对策论与经济行为》）、决策论、维修更新理论、搜索论、可靠性和质量管理等。
运筹学领域的诺贝尔奖得主：阿罗、萨谬尔逊、西蒙（经济学家）、多夫曼、胡尔威茨、勃拉凯特（Blackett,美，物理学家）。
运筹学会的建立：英国（1948年）、美国（1952年）、法国（1956年）、日本（1957年）、印度（1957年）、中国（1980年），38个国家和地区。
国际运筹学联合会（IFORS）的成立：1959年，英、美、法发起成立，中国1982年加入。
运筹学-第一章-单纯形法基本原理
初始基本可行解：
X ( 0) ( x1 , x2 ,, xm ,0,0,...,0)T (b1 , b2 ,......,bm ,0,0,...,0)T
0
0
0
单纯形法基本原理
2、基变换 定义：两个基可行解称为相邻的，如果它们之间变换 且仅变换一个基变量。 初始基可行解的前m个为基变量，
X
凸集
顶点
凸集
不是凸集
顶点：如果凸集C中不存在任何两个不同的点X1，X2，使X 成为这两个点连线上的一个点
单纯形法基本原理
定理1：若线性规划问题存在可行解，则该问题的可行域是 凸集。 定理2：线性规划问题的基可行解X对应可行域(凸集)的顶 点。 定理3：若问题存在最优解，一定存在一个基可行解是最优 解。（或在某个顶点取得）
的左边变成一个单位矩阵，
b (b1 a1 j ,.,bl 1 al 1 j , , bl 1 al 1 j ,.,bm am1 j , ) ( x1 , x2 ,..., xl 1 , x j , xl 1 ,..., xm )
X
(1)
T
与X
( 0)
是相邻的基可行解。
M M bm 0 L
M M
M M
L 1 am,m1 L L 00
M , M amn m
bi 其中： i a kj 0 a kj
j c j ci aij c j z j
单纯形法的计算步骤
例1.12 用单纯形法求下列线性规划的最优解
max Z 3 x1 4 x 2 2 x1 x 2 40 x1 3 x 2 30 x , x 0 1 2
xi0 aij 0, aij 0,取值无限，
X ( 0) ( x1 , x2 ,, xm ,0,0,...,0)T (b1 , b2 ,......,bm ,0,0,...,0)T
0
0
0
单纯形法基本原理
2、基变换 定义：两个基可行解称为相邻的，如果它们之间变换 且仅变换一个基变量。 初始基可行解的前m个为基变量，
X
凸集
顶点
凸集
不是凸集
顶点：如果凸集C中不存在任何两个不同的点X1，X2，使X 成为这两个点连线上的一个点
单纯形法基本原理
定理1：若线性规划问题存在可行解，则该问题的可行域是 凸集。 定理2：线性规划问题的基可行解X对应可行域(凸集)的顶 点。 定理3：若问题存在最优解，一定存在一个基可行解是最优 解。（或在某个顶点取得）
的左边变成一个单位矩阵，
b (b1 a1 j ,.,bl 1 al 1 j , , bl 1 al 1 j ,.,bm am1 j , ) ( x1 , x2 ,..., xl 1 , x j , xl 1 ,..., xm )
X
(1)
T
与X
( 0)
是相邻的基可行解。
M M bm 0 L
M M
M M
L 1 am,m1 L L 00
M , M amn m
bi 其中： i a kj 0 a kj
j c j ci aij c j z j
单纯形法的计算步骤
例1.12 用单纯形法求下列线性规划的最优解
max Z 3 x1 4 x 2 2 x1 x 2 40 x1 3 x 2 30 x , x 0 1 2
xi0 aij 0, aij 0,取值无限，
运筹学第1章-线性规划
凸集的数学定义:设K为n维欧氏空间的一个点集，若K中任意两个 点X1和X2连线上的所有点都属于K，即“X =αX1+(1-α) X2 ∈ K(0≤a ≤ 1)”，则称K为凸集。设X(x1，x2，…，xn)，X1(u1， u2，...，un)，X2(v1，v2，…，vn)，如图1一5所示，“X =αX1+(1α) X2 ∈ K(0≤a ≤ 1)”的证明思路如下:
下一页 返回
图解法步骤：
（1）建立坐标系； （2）将约束条件在图上表示； （3）确立满足约束条件的解的范围； （4）绘制出目标函数的图形 （5）确定最优解
用图解法求解下列线性规划问题
max z 2x1 3x2
4x1 0x2 16
s.t
10xx11
4x2 2x2
12 8
x1, x2 0
1. 1.1问题举例
(1)生产计划问题。 生产计划问题是典型的已知资源求利润最大化的问题，对于此类
问题通常有三个假设:①在某一计划期内对生产做出的安排;②生产 过程的损失忽略不计;③市场需求无限制，即假设生产的产品全部 卖出。
下一页 返回
1.一般线性规划问题的数学模型
例1 用一块连长为a的正方形铁皮做一个容 器，应如何裁剪，使做成的窗口的容积为最 大？
解：设 x1, x2分别表示从A,B两处采购的原油量（单
位：吨），则所有的采购方案的最优方案为：
min z 200x1 290x2
0.15x1 0.50x2 150000
s.t
0.20x1 0.50x1
0.30x2 0.15x2
120000 120000
x1 0, x2 0
1. 1线性规划问题与模型
也可以写成模型(1-6)和模型(1-7)的形式，其中模型(1-7)较为常用。
下一页 返回
图解法步骤：
（1）建立坐标系； （2）将约束条件在图上表示； （3）确立满足约束条件的解的范围； （4）绘制出目标函数的图形 （5）确定最优解
用图解法求解下列线性规划问题
max z 2x1 3x2
4x1 0x2 16
s.t
10xx11
4x2 2x2
12 8
x1, x2 0
1. 1.1问题举例
(1)生产计划问题。 生产计划问题是典型的已知资源求利润最大化的问题，对于此类
问题通常有三个假设:①在某一计划期内对生产做出的安排;②生产 过程的损失忽略不计;③市场需求无限制，即假设生产的产品全部 卖出。
下一页 返回
1.一般线性规划问题的数学模型
例1 用一块连长为a的正方形铁皮做一个容 器，应如何裁剪，使做成的窗口的容积为最 大？
解：设 x1, x2分别表示从A,B两处采购的原油量（单
位：吨），则所有的采购方案的最优方案为：
min z 200x1 290x2
0.15x1 0.50x2 150000
s.t
0.20x1 0.50x1
0.30x2 0.15x2
120000 120000
x1 0, x2 0
1. 1线性规划问题与模型
也可以写成模型(1-6)和模型(1-7)的形式，其中模型(1-7)较为常用。
运筹学-1、线性规划
则：
x1 x2 100
x1 ( x3 ) x4 x2 2
设x3为第二年新的投资； x4为第二年的保留资金；
则：
18
•设x5为第三年新的投资；x6为第三年的保留资金；
则：
x3 ( x5 ) x6 x4 2 x1 2
•设x7为第四年新的投资；第四年的保留资金为x8；
max Z 2 x7 x9 x1 x2 100 x 2x 2x 2x 0 2 3 4 1 4 x1 x3 2 x4 2 x5 2 x6 0 s.t 4 x3 x5 2 x6 2 x7 2 x8 0 4 x5 x7 2 x 8 2 x9 0 x 0, j 1, 2, , 9 j
13
例3：（运输问题）设有两个砖厂A1 、A2 ，产 量分别为23万块、27万块，现将其产品联合供应三 个施工现场B1 、 B2 、 B3 ，其需要量分别为17万 块、18万块、15万块。各产地到各施工现场的单位 运价如下表： 现场 砖厂 B1 B2 B3
A1 A2
5 6
14 18
7 9
问如何调运才能使总运费最省？
20
例5：（下料问题） 某一机床需要用甲、乙、 丙三种规格的钢轴各一根，这些轴的规格分别是 2.9,2.1, 1.5(m),这些钢轴需要用同一种圆钢来做，圆 钢长度为7.4m。现在要制造100台机床，最少要用多 少根圆钢来生产这些钢轴？
解：第一步：设一根圆钢切割成甲、乙、丙三 种钢轴的根数分别为y1,y2,y3，则切割方式可用不等 式2.9y1+2.1y2+1.5y3≤7.4 表示，求这个不等式的有实 际意义的非负整数解共有8组，也就是有8种不同的 下料方式，如下表所示：
运筹学第1章：线性规划问题及单纯型解法
原料甲 原料乙 最低含量 VA 0.5 0.5 2 VB1 1.0 0.3 3 VB2 0.2 0.6 1.2 VD 0.5 0.2 2 0.3 0.5 单价
分别代表每粒胶丸中甲, 设 x1, x2分别代表每粒胶丸中甲, 乙两种原料的用量
5
例3,合理下料问题 , 分别代表采用切割方案1~8的套数, 的套数, 设 xj 分别代表采用切割方案 的套数
19
( f(x
)= 3
6
1.2.2 单纯型法的基本思路
确定初试基础可行解
检查是否为 最优解? 最优解?
是
求最优解的目标函数值
否 确定改善方向
求新的基础可行解
20
1.2.3 单纯型表及其格式
IV CB III XB II x1 b c1 a11 a21 c1′′= cn+1 xn+1 b1 c2′′= cn+2 xn+2 b2 x2 … xn c2 … cn a12 … a1n a22 … a2n I xn+1 cn+1 1 0 0 zn+1 xn+2 cn+2 0 1 0 zn+2 … … … … … … xn+m cn+m 0 0 1 zn+m
OBJ : max f ( x) = 6x1 + 4x2 2x1 + x2 ≤ 10 铜资源约束 x1 + x2 ≤ 8 铅资源约束 s.t. x2 ≤ 7 产量约束 x1, x2 ≥ 0 产量不允许为负值 最优解: x1 = 2, x2 = 6, max f ( x) = 36.
4
例2,配料问题(min, ≥) ,配料问题(
2 max 1 O 1 2 3 4 D 5 6 7 H 8
运筹学习题答案(1)
第一章 线性规划及单纯形法（作业）1.4 分别用图解法和单纯型法求解下列线性规划问题，并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点。
（1）Max z=2x 1+x 2St.⎪⎩⎪⎨⎧≥≤+≤+0,24261553212121x x x x x x 解：①图解法：由作图知，目标函数等值线越往右上移动，目标函数越大，故c 点为对应的最优解，最优解为直线⎩⎨⎧=+=+242615532121x x x x 的交点，解之得X=(15/4,3/4)T 。
Max z =33/4. ② 单纯形法：将上述问题化成标准形式有： Max z=2x 1+x 2+0x 3+0x 4St. ⎪⎩⎪⎨⎧≥≤++≤++0,,,242615535421421321x x x x x x x x x x其约束条件系数矩阵增广矩阵为：P 1 P 2 P 3 P 4⎥⎦⎤⎢⎣⎡241026150153 P 3,P 4为单位矩阵，构成一个基，对应变量向，x 3,x 4为基变量，令非基变量x 1,x 2为零，找到T 优解，代入目标函数得Max z=33/4.1.7 分别用单纯形法中的大M 法和两阶段法求解下列线性规划问题，并指出属哪一类。
（3）Min z=4x 1+x 2⎪⎪⎩⎪⎪⎨⎧=≥=++=-+=+)4,3,2,1(0426343342132121j xj x x x x x x x x 解：这种情况化为标准形式： Max z ＇=-4x 1-x 2⎪⎪⎩⎪⎪⎨⎧=≥=++=-+=+)4,3,2,1(0426343342132121j xj x x x x x x x x 添加人工变量y1,y2Max z ＇=-4x 1-x 2+0x 3+0x 4-My 1-My 2⎪⎪⎩⎪⎪⎨⎧≥=≥=++=+-+=++0,).4,3,2,1(04263433214112321121y y j xj x x x y x x x y x x(2) 两阶段法： Min ω=y 1+y 2St.⎪⎪⎩⎪⎪⎨⎧≥=≥=++=+-+=++0,).4,3,2,1(04263433214112321121y y j xj x x x y x x x y x x第二阶段，将表中y 1,y 2去掉，目标函数回归到Max z ＇=-4x 1-x 2+0x 3+0x 4第二章 线性规划的对偶理论与灵敏度分析（作业）2.7给出线性规划问题：Max z=2x 1+4x 2+x 3+x 4⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥≤++≤++≤+≤++)4,3,2,1(096628332143221421j x x x x x x x x x x x x j要求：（1）写出其对偶问题；（2）已知原问题最优解为X *=(2,2,4,0),试根据对偶理论，直接求出对偶问题的最优解。
运筹学第1章
（第三版）《运筹学》教材编写组编清华大学出版社运筹学第1章线性规划与单纯形法第1节线性规划问题及其数学模型二.线性规划与目标规划第1章线性规划与单纯形法第2章对偶理论与灵敏度分析第3章运输问题第4章目标规划第1章线性规划与单纯形法第1节线性规划问题及其数学模型第2节线性规划问题的几何意义第3节单纯形法第4节单纯形法的计算步骤第5节单纯形法的进一步讨论第6节应用举例第1节线性规划问题及其数学模型•1.1 问题的提出•1.2 图解法•1.3 线性规划问题的标准形式•1.4 线性规划问题的解的概念第1节线性规划问题及其数学模型线性规划是运筹学的一个重要分支。
线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。
特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。
从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。
它已是现代科学管理的重要手段之一。
解线性规划问题的方法有多种，以下仅介绍单纯形法。
1.1 问题的提出从一个简化的生产计划安排问题开始例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。
资源产品ⅠⅡ拥有量设备 1 2 8台时原材料A40 16kg原材料B0 4 12kg续例1该工厂•每生产一件产品Ⅰ可获利2元，•每生产一件产品Ⅱ可获利3元，•问应如何安排计划使该工厂获利最多?如何用数学关系式描述这问题，必须考虑称它们为决策变量。
产品的数量，分别表示计划生产设II I,,21x x ∙12416482212121≤≤≤+∙x ;x ;x x ,x ,x 这是约束条件。
即有量的限制的数量多少，受资源拥生产021≥∙x ,x ,即生产的产品不能是负值这是目标。
最大如何安排生产，使利润,∙数学模型⎪⎪⎩⎪⎪⎨⎧≥≤≤≤++=0124164823221212121x ,x x x x x :x x z max 约束条件目标函数例2. 简化的环境保护问题靠近某河流有两个化工厂(见图1-1)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。
运筹学基础(1)
展
英国创刊 ☺ 1952年第一个运筹学学会在美国成立
☺ 1947年丹齐克在研究美国空军资源优化配置 时提出线性规划及其通用解法——单纯形法
战后这些研究成果被应用到生
产、经济领域，其发展可以分
运
为三个阶段：
筹 学
的
① 1945至50年代初期—创建时期
② 50年代初期至50年代末期——成长 时期
产
生
商船护航的规模等等。
战后这些研究成果被应用到生
产、经济领域，其发展可以分
运
为三个阶段：
筹 学
的
① 1945至50年代初期—创建时期
☺ 1948年英国成立“运筹学俱乐部”在煤力、 电力等部门推广应用运筹学
产
☺ 相继一些大学开设运筹学课程
生
1948年美国麻省理工学院
和
1950年英国伯明翰大学
发
☺ 1950年第一本运筹学杂志《运筹学季刊》在
的 定 义
与 特 点
为“运作研究”。
美国运筹学会认为：运筹学所研 究的问题，通常是在要求有限资 源的条件下科学地决定如何最好 地设计和运营人机系统。
中国大百科全书释义：它用数学 方法研究经济、民政和国防等部 门在内外环境的约束条件下合理 分配人力、物力、财力等资源， 使实际系统有效运行的技术科学，
bi ,i 1,2m 为资源系数；
aij ,i 1,2m, j 1,2n 为技术系数，或约束
系数 ；
mn
运筹学基础
第四讲
主讲教师：郑黎黎
学时：48
线 性 数规 学划 模问 型题 及 其
线性规划的标准形式有四个特点 ： 目标最大化、约束为等式、右端项 非负、决策变量均非负。 对于各种非标准形式的线性规划问 题，我们总可以通过以下变换，将 其转化为标准形式。
运筹学第一章
OR1
30
1.1.3解的概念
概念： 1、可行解：满足所有约束条件的解。 2、可行域：即可行解的集合。所有约束条件的交 集，也就是各半平面的公共部分。满足所有约 束条件的解的集合，称为可行域。 3、凸集：集合内任意两点的连线上的点均属于这 个集合。如：实心球、三角形。线性规划的可 行域是凸集。
OR1
OR1
27
线性规划图解法例题
（无界解）
max z x 2 y x y 1 2 x 4 y 3 x 0, y 0
OR1
28
线性规划图解法例题
（无解）
min z x 2 y x y 2 2 x 4 y 3 x 0, y 0
请问该 医院至 少需要 多少名 护士？
5
例题2建模
目标函数：min Z=x1+x2+x3+x4+x5+x6 约束条件： x1+x2 ≥70
x2+x3 ≥60 x3+x4 ≥ 50 x4+x5 ≥20 x5+x6 ≥30 非负性约束：xj ≥0,j=1,2,…6
OR1
6
例题3：运输问题
三个加工棉花的加工厂，并且有三个仓库供应棉花，各 供应点到各工厂的单位运费以及各点的供应量与需求量 分别如下表所示：问如何运输才能使总的运费最小？
OR1
14
总
结
从以上 5 个例子可以看出，它们都属于优化问题，它们 的共同特征： 1 、每个问题都用一组决策变量表示某一方案；这组决 策变量的值就代表一个具体方案，一般这些变量取值是 非负的。 2 、存在一定的约束条件，这些约束条件可以用一组线 性等式或线性不等式来表示。 3 、都有一个要求达到的目标，它可用决策变量的线性 函数（称为目标函数）来表示。按问题的不同，要求目 标函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划的数学模型。
30
1.1.3解的概念
概念： 1、可行解：满足所有约束条件的解。 2、可行域：即可行解的集合。所有约束条件的交 集，也就是各半平面的公共部分。满足所有约 束条件的解的集合，称为可行域。 3、凸集：集合内任意两点的连线上的点均属于这 个集合。如：实心球、三角形。线性规划的可 行域是凸集。
OR1
OR1
27
线性规划图解法例题
（无界解）
max z x 2 y x y 1 2 x 4 y 3 x 0, y 0
OR1
28
线性规划图解法例题
（无解）
min z x 2 y x y 2 2 x 4 y 3 x 0, y 0
请问该 医院至 少需要 多少名 护士？
5
例题2建模
目标函数：min Z=x1+x2+x3+x4+x5+x6 约束条件： x1+x2 ≥70
x2+x3 ≥60 x3+x4 ≥ 50 x4+x5 ≥20 x5+x6 ≥30 非负性约束：xj ≥0,j=1,2,…6
OR1
6
例题3：运输问题
三个加工棉花的加工厂，并且有三个仓库供应棉花，各 供应点到各工厂的单位运费以及各点的供应量与需求量 分别如下表所示：问如何运输才能使总的运费最小？
OR1
14
总
结
从以上 5 个例子可以看出，它们都属于优化问题，它们 的共同特征： 1 、每个问题都用一组决策变量表示某一方案；这组决 策变量的值就代表一个具体方案，一般这些变量取值是 非负的。 2 、存在一定的约束条件，这些约束条件可以用一组线 性等式或线性不等式来表示。 3 、都有一个要求达到的目标，它可用决策变量的线性 函数（称为目标函数）来表示。按问题的不同，要求目 标函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划的数学模型。
(名词解释)运筹学
(名词解释)运筹学
运筹学是一门研究如何在有限资源下做出最佳决策的学科。
它
涉及数学、统计学和计算机科学等多个领域，旨在找到最优解决方
案以最大程度地满足特定目标或约束条件。
运筹学的应用范围非常
广泛，包括生产调度、物流管理、供应链优化、交通规划、金融风
险管理等诸多领域。
在运筹学中，常用的方法包括线性规划、整数规划、动态规划、排队论、模拟等。
线性规划用于解决线性约束条件下的最优化问题，整数规划则是在变量为整数时的最优化问题，动态规划通过分阶段
决策来解决多阶段问题，排队论则研究排队系统的性能指标，模拟
则是通过构建模型来模拟实际系统的运行情况。
运筹学的发展历史可以追溯到二战期间，当时运筹学被用于军
事决策和战争规划，随后逐渐应用于工业生产和商业管理领域。
如今，随着信息技术的发展，运筹学在大数据分析、人工智能和机器
学习等方面也得到了广泛应用。
总的来说，运筹学致力于通过科学的方法和技术手段，帮助人
们做出最佳决策，提高资源利用效率，降低成本，优化系统运行，对于提升生产效率和管理水平具有重要意义。
运筹学讲义第1章
(2) 和式： max z= cjxj
j=1
n
s.t.
aijxj≤bi （i=1,2,……,m)
j=1
n
xj≥ 0
（j=1,2,……,n)
其中：cj---------表示目标函数系数 aij---------表示约束条件系数 bi ---------表示约束右端项
2007/08
-7-
---第 1 章 线性规划---
起迄时间 2----6 时 6---10 时 10--14 时 14--18 时 18--22 时 22---2 时
2007/08
服务员人数 4 8 10 7 12 4
-18-
---第 1 章 线性规划---
建立线性规划模型要求：
（1）要求决策的量是连续的、可控的量，或 者是可以简化为连续取值的变量；
1
n
xj≥0
（j=1,2,……,n)
（1）可行解：满足所有约束方程和变量符号限制条件的一组变量的 取值。 （2）可行域：全部可行解的集合称为可行域。 （3）最优解：使目标函数达到最优值的可行解。
2007/08 -20-
---第 1 章 线性规划---
（4）基：设A为线性规划模型约束条件系数矩阵（m n，m<n）， 而B为其mm子矩阵，若|B|≠0，则称B为该线性规划模型的一个基。
可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。 x3 x4 ——基变量 x x x x
1 2 3 4
设
A=
1 1
1 2
1
0
0
1
，令 B=
1
0
0
1
，则 | B |=1≠0,
运筹学作业解答(1-2)
运筹学作业（一）
题1.1：总结线性规划模型的特征； 判断下列数学模型是否为线性规划模型。 （模型a、b、c为常数；θ 为可取某常数值的参变量；x、y为变量）
(1) max Z = 3 x1 + 5 x 2 + 7 x3 x1 + 2 x 2 − 6 x3 ≥ 8 5 x + x + 8 x ≤ 20 1 2 3 3 x1 + 4 x 2 = 12 x1 , x3 ≥ 0
题1.9：填空题
１．在用图解法求线性规划问题时，目标函数Ｚ＝ ClX1+C2X2，则直线ClX1+C2X2＝10是Ｚ的一条平行线 平行线，而 平行线 当可行域非空有界时最优解必定能在可行域的顶点上 顶点上达 顶点上 到。 ２．线性规划数学模型三要素：决策变量 、目标函数 、 决策变量 目标函数 约束条件 ３．线性规划中，任何基对应的决策变量称为基变量 基变量。 基变量 ４．若某线性规划问题存在唯一最优解，从几何上讲，它 必定在可行解域的某个 顶点 处达到；从代数上讲，它 也一定是某个基变量组的 基可行解
s = 10 y 1 + 20 y y1 + 4 y y1 + y y1, y
2 2
2
st
= 10 ≥ 2
≥ 1
2
2 y1 + y
2
≥ 0
max s = 15 y 1 + 20 y 2 − 5 y 3 − y1 − 5 y 2 + y 3 ≥ − 5 5 y − 6 y − y ≤ − 6 1 2 3 st 3 y 1 + 10 y 2 − y 3 = − 7 y 1 ≥ 0 , y 2 ≤ 0 , y 3 无约束
题1.1：总结线性规划模型的特征； 判断下列数学模型是否为线性规划模型。 （模型a、b、c为常数；θ 为可取某常数值的参变量；x、y为变量）
(1) max Z = 3 x1 + 5 x 2 + 7 x3 x1 + 2 x 2 − 6 x3 ≥ 8 5 x + x + 8 x ≤ 20 1 2 3 3 x1 + 4 x 2 = 12 x1 , x3 ≥ 0
题1.9：填空题
１．在用图解法求线性规划问题时，目标函数Ｚ＝ ClX1+C2X2，则直线ClX1+C2X2＝10是Ｚ的一条平行线 平行线，而 平行线 当可行域非空有界时最优解必定能在可行域的顶点上 顶点上达 顶点上 到。 ２．线性规划数学模型三要素：决策变量 、目标函数 、 决策变量 目标函数 约束条件 ３．线性规划中，任何基对应的决策变量称为基变量 基变量。 基变量 ４．若某线性规划问题存在唯一最优解，从几何上讲，它 必定在可行解域的某个 顶点 处达到；从代数上讲，它 也一定是某个基变量组的 基可行解
s = 10 y 1 + 20 y y1 + 4 y y1 + y y1, y
2 2
2
st
= 10 ≥ 2
≥ 1
2
2 y1 + y
2
≥ 0
max s = 15 y 1 + 20 y 2 − 5 y 3 − y1 − 5 y 2 + y 3 ≥ − 5 5 y − 6 y − y ≤ − 6 1 2 3 st 3 y 1 + 10 y 2 − y 3 = − 7 y 1 ≥ 0 , y 2 ≤ 0 , y 3 无约束
运筹学_第1章_线性规划习题
第一章线性规划习题1.1（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？解：设x1、x2分别代表甲、乙两种产品的生产数量（件），z表示公司总利润。
依题意，问题可转换成求变量x1、x2的值，使总利润最大，即ma x z=50x1+100x2且称z=50x1+100x2为目标函数。
同时满足甲、乙两种产品所消耗的A、B、C三种资源的数量不能超过它们的限量，即可分别表示为x1 + x2≤3002x1 + x2≤400x2≤250且称上述三式为约束条件。
此外，一般实际问题都要满足非负条件，即x1≥0、x2≥0。
这样有ma x z=50x1+100x2x1 + x2≤3002x1 + x2≤400x2≤250x1、x2≥0习题1.2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m 3，在两个工厂之间有一条流量为200万m 3的支流。
两化工厂每天排放某种有害物质的工业污水分别为2万m 3和1.4万m 3。
从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。
环保要求河流中工业污水含量不能大于0.2%。
两化工厂处理工业污水的成本分别为1000元/万m 3和800元/万m 3。
现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。
解：设x 1、x 2分别代表工厂1和工厂2处理污水的数量(万m 3)。
则问题的目标可描述为min z =1000x 1+800x 2 约束条件有第一段河流（工厂1——工厂2之间）环保要求 (2－x 1)/500 ≤0.2% 第二段河流（工厂2以下河段）环保要求 [0.8(2－x 1) +(1.4－x 2)]/700≤0.2% 此外有x 1≤2； x 2≤1.4 化简得到min z =1000x 1+800x 2 x 1 ≥1 0.8x 1 + x 2 ≥1.6 x 1 ≤2 x 2≤1.4 x 1、x 2≥0习题1.3ma x z =50x 1+100x 2x 1 + x 2≤300 2x 1 + x 2≤400x 2≤250图1—1 x 2x1、x2≥0用图解法求解。
运筹学基础1
• 线性规划提出后很快受到经济学家的重视， 阿罗、萨谬尔逊、西蒙、多夫曼和胡尔威 茨等都因为将线性规划应用到经济分析中 而获得了诺贝尔奖金，并在运筹学某些领 域中发挥过重要作用 。最近的有数学家罗 伯特· 奥曼（Robert J. Aumann，2005）和 约翰.纳什(John F. Nash Jr., 1994)
四、运筹学的主要内容 :
• 规划论 (线性规划、非线性规划、整数规划、动 态规划、多目标规划、随机规划 )
min (max) st f (x, y, ) hi (x, y, ) 0 i 1 2 me g j (x, y, ) 0 j me 1 m x X R n为决策变量, y Y R m为参数,
原料I的费用 ： 65( x11 x21 x31 ) 原料II的费用： 25( x12 x22 x32 )
原料III的费用： 35( x13 x23 x33 )
则目标函数为总产值减去总成本,表示为
z 50( x11 x12 x13 ) 35( x21 x22 x23 ) 25( x31 x32 x33 ) 65( x11 x21 x31 ) 25( x12 x22 x32 ) 35( x13 x23 x33 ) 15x11 25x12 15x13 30 x21 10 x22 40 x31 10 x33
x1 x x
3
3
3
x1 x2 x4 6 x1 x x x5 5
2 x1 x2 x3 x3 2 x j 0, j 1, 2, 4, 5; x3 0, x3 0 3
另一种更好的方法是直接消去自由变量x3，由 最后的方程知： x3=2-2x1+x2 ， 代入到目标和 其它两个方程得：
四、运筹学的主要内容 :
• 规划论 (线性规划、非线性规划、整数规划、动 态规划、多目标规划、随机规划 )
min (max) st f (x, y, ) hi (x, y, ) 0 i 1 2 me g j (x, y, ) 0 j me 1 m x X R n为决策变量, y Y R m为参数,
原料I的费用 ： 65( x11 x21 x31 ) 原料II的费用： 25( x12 x22 x32 )
原料III的费用： 35( x13 x23 x33 )
则目标函数为总产值减去总成本,表示为
z 50( x11 x12 x13 ) 35( x21 x22 x23 ) 25( x31 x32 x33 ) 65( x11 x21 x31 ) 25( x12 x22 x32 ) 35( x13 x23 x33 ) 15x11 25x12 15x13 30 x21 10 x22 40 x31 10 x33
x1 x x
3
3
3
x1 x2 x4 6 x1 x x x5 5
2 x1 x2 x3 x3 2 x j 0, j 1, 2, 4, 5; x3 0, x3 0 3
另一种更好的方法是直接消去自由变量x3，由 最后的方程知： x3=2-2x1+x2 ， 代入到目标和 其它两个方程得：
运筹学第1章线性规划及单纯形法复习题
max (min)
Z = CX
AX ≤ ( = , ≥ ) b X ≥ 0
3、线性规划的标准形式 、
ma0
4、线性规划问题的解 、 （一）求解方法
一 般 有 两种方法 图 解 法 单纯形法 两个变量、 两个变量、直角坐标 三个变量、 三个变量、立体坐标
适用于任意多个变量、 适用于任意多个变量、但需将 一般形式变成标准形式
（二）线性规划问题的解
1、解的概念 可行解：满足约束条件② 的解为可行解。 ⑴ 可行解：满足约束条件②、③的解为可行解。 所有解的集合为可行解的集或可行域。 所有解的集合为可行解的集或可行域。 最优解： 达到最大值的可行解。 ⑵ 最优解：使目标函数①达到最大值的可行解。 ⑶ 基：B是矩阵A中m×m阶非奇异子矩阵 是矩阵A ≠0）， ），则 是一个基。 （∣B∣≠0），则B是一个基。
§2 图 解 法
例一、 例一、 max
Z = 2 x 2 x 2 x 4 x
2 2 1
+ 3 x
2
2 x1 + x + 1 4 x1 x1 ≥
≤ 12 ≤ 8 ≤ 16 ≤ 12
2
⑴ ⑵ ⑶ ⑷
2
0, x
≥ 0
max
Z = 2 x1 + 3 x 2 x 2 x
2 2
当xj=0时, 必有 j=zj=0, 因此 时 必有y
∑P x = ∑P y = ∑P z
j =1
r
r
r
r
j
j
j =1
j
j
j =1
j
j
=b
∑(y
j =1
j
− z j ) Pj = 0
运筹学第一课
产品 甲 资源 设备A 设备 设备B 设备 材料C 材料 材料D 材料 利润（ 件 利润（元/件） 3 2 4 2 40 1 2 5 3 30 2 4 1 5 50 200 200 360 300 乙 丙 现有资源
分别为甲、 【解】设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型 为：
m Z = 40x1 + 30x2 + 50x3 ax
10
4 配料问题
例5．某工厂要用三种原料1、 某工厂要用三种原料1 2、3混合调配出三种不同规格的 产品甲、 数据如右表。 产品甲、乙、丙，数据如右表。 该厂应如何安排生产， 问：该厂应如何安排生产，使利 润收入为最大？ 润收入为最大？
单价（ 产品名称 规格要求 单价（元/kg） ） 50 甲 原材料 1 不少于 50%，原材料 2 不超过 25% ， 35 乙 原材料 1 不少于 25%，原材料 2 不超过 50% ， 25 丙 不限 原材料名称 1 2 3 每天最多供应量 100 100 60 单价（ 单价（元/kg） ） 65 25 35
• 利润 = 总收入 - 总成本 = 甲乙丙三种产品的销售单价 产品数量 - 甲乙 甲乙丙三种产品的销售单价*产品数量 丙使用的原料单价*原料数量 原料数量， 丙使用的原料单价 原料数量，故有
目标函数
50（ +35（ +25（ Max 50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65 25（ 35（ （x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33） = -15x11+25x12+15x13-30x21+10x22-40x31-10x33
分别为甲、 【解】设x1、x2、x3 分别为甲、乙、丙三种产品的产量数学模型 为：
m Z = 40x1 + 30x2 + 50x3 ax
10
4 配料问题
例5．某工厂要用三种原料1、 某工厂要用三种原料1 2、3混合调配出三种不同规格的 产品甲、 数据如右表。 产品甲、乙、丙，数据如右表。 该厂应如何安排生产， 问：该厂应如何安排生产，使利 润收入为最大？ 润收入为最大？
单价（ 产品名称 规格要求 单价（元/kg） ） 50 甲 原材料 1 不少于 50%，原材料 2 不超过 25% ， 35 乙 原材料 1 不少于 25%，原材料 2 不超过 50% ， 25 丙 不限 原材料名称 1 2 3 每天最多供应量 100 100 60 单价（ 单价（元/kg） ） 65 25 35
• 利润 = 总收入 - 总成本 = 甲乙丙三种产品的销售单价 产品数量 - 甲乙 甲乙丙三种产品的销售单价*产品数量 丙使用的原料单价*原料数量 原料数量， 丙使用的原料单价 原料数量，故有
目标函数
50（ +35（ +25（ Max 50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65 25（ 35（ （x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33） = -15x11+25x12+15x13-30x21+10x22-40x31-10x33
运筹学第一章
第一章、 线性规划和单纯形法1.1 线性规划的概念一、线性规划问题的导出1．(引例) 配比问题——用浓度为45%和92%的硫酸配置100t 浓度为80%的硫酸。
取45%和92%的硫酸分别为x1和x2t,则有： 求解二元一次方程组得解。
目的相同，但有5种不同浓度的硫酸可选（30%，45%，73%，85%，92%）会出现什么情况？设取这5种硫酸分别为 x1、x2、x3、x4、x5 t, 则有： ⎩⎨⎧⨯=++++=++++1008.092.085.073.045.03.01005432154321x x x x x x x x x x 请问有多少种配比方案？为什么？哪一种方案最好？假设5种硫酸价格分别为：400，700，1400，1900，2500元/t ，则有：2.生产计划问题如何制定生产计划，使三种产品总利润最大？考虑问题：⎩⎨⎧⨯=+=+1008.092.045.01002121x x x x ⎪⎩⎪⎨⎧=≥⨯=++++=++++++++=5,,2,1,01008.092.085.073.045.03.0100..250019001400700400543215432154321 j x x x x x x x x x x x t s x x x x x MinZ j（1）何为生产计划？（2）总利润如何描述？（3）还要考虑什么因素？（4）有什么需要注意的地方（技巧）？（5）最终得到的数学模型是什么？二、线性规划的定义和数学描述（模型）1．定义：对于求取一组变量xj (j =1,2,......,n)，使之既满足线性约束条件，又使具有线性表达式的目标函数取得极大值或极小值的一类最优化问题称为线性规划问题，简称线性规划。
2.配比问题和生产计划问题的线性规划模型的特点：用一组未知变量表示要求的方案，这组未知变量称为决策变量；存在一定的限制条件，且为线性表达式；有一个目标要求（最大化，当然也可以是最小化），目标表示为未知变量的线性表达式，称之为目标函数； 对决策变量有非负要求。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
期末考试《运筹学》B 卷
一、单项选择题（在下列每题的四个选项中，只有一个选项是符合试题要求的。
请把答案填入答题框中相应的题号下。
每小题2分，共20分） 1．单纯形迭代中，出基变量在紧接着的下一次迭代中（ ）立即进基。
A ．会 B ．不会 C ．有可能 D ．不一定
2．线性规划的约束条件为 X 1 + X 2 + X 3 = 3 ，2X 1+ 2X 2+ X 4= 4，X i ≥0（i=1-4）,则基本可行解是（ ）
A ．（0，0，4， 3）
B ．（0，0，3，4）
C ．（2，1，0，-2）
D ．（3，0，0，-2）
3．普通单纯形法的最小比值定理的应用是为了保证（ ） A ．使原问题保持可行 B ．使对偶问题保持可行 C ．逐步消除原问题不可行性 D ．逐步消除对偶问题的不可行性 4. 原问题与对偶问题都有可行解，则有（ ） A ．原问题有最优解，对偶问题可能没有最优解
B ．原问题与对偶问题可能都没有最优解
C ．可能一个问题有最优解，另一个问题具有无界解
D ．原问题与对偶问题都具有最优解
5. 求解整数规划问题的分支定界法中，有（ ） A ．最大值问题的目标值是各分支的上界 B ．最大值问题的目标值是各分支的下界
C ．最小值问题的目标值是各分支的上界
D ．以上结论都不对
6．在运输方案中出现退化现象，是指数字格的数目 （ ） A ．等于 m+n B ．等于m+n-1 C ．小于m+n-1 D ．大于m+n-1
7．若运输问题的单位运价表的某一行元素分别加上一个常数k ，最优调运方案将（ ）。
A ．发生变化
B ．不发生变化
C ．A 、B 都有可能 D. 都不对 8．在产销平衡运输问题中，设产地为m 个，销地为n 个，那么解中非零
变量的个数（ ）。
A ．不能大于(m+n-1)
B ．不能小于(m+n-1)
C ．等于(m+n-1)
D ．不确定
9．在运输问题中，每次迭代时，如果有某非基变量的检验数等于零，则该运输问题（ ）。
A ．无最优解
B ．有无穷最优解
C ．有唯一最优解
D ．出现退化解 10．动态规划问题中最优策略具有性质：（ ）。
A ．每个阶段的决策都是最优的
B ．当前阶段以前的各阶段决策是最优的
C ．无论初始状态与初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略
D ．它与初始状态无关
二、判断题（每题1分,共10分）
1．图解法提供求解线性规划问题的通用方法。
( ) 2．用单纯形法求解一般线性规划时，当目标函数求最小值时，若所有的
检验数Cj-Zj ≥0，则问题达到最优。
( ) 3．在单纯形表中，基变量对应的系数矩阵往往为单位矩阵。
( ) 4．满足线性规划问题所有约束条件的解称为基本可行解。
( ) 5．在线性规划问题求解过程中，基变量和非基变量个数是固定的。
（ ) 6．对偶问题的目标函数总是与原问题目标函数相等。
( ) 7．原问题与对偶问题一一对应。
( ) 8． 运输问题可行解中基变量个数一定遵循m ＋n －1规则。
( ) 9．指派问题的解中基变量的个数为m ＋n 。
( ) 10．网络最短路径是指从网络起点至终点的一条权和最小的路线。
( )
三、填空题（每空1分,共10分）
Consider the following problem Maximize Z=6x 1+x 2+2x 3
Let x 4, x 5, and x 6 denote apply the simplex method, the slack variables for the respective constraints. After you a portion of the final simplex tableau is as follows:
Use the fundamental insight to identify the missing numbers in the final
simplex tableau.
四、建模题（每题15分,共15分）
福安商场是个中型的百货商场，它对售货人员的需求经过统计分析如下表所示，为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问该如何安排售货人员的休息，既满足了工作需要，又使配备的售货人员的人数最少，请列出此问题的数学模型。
时间 所需售货人员数
时间 所需售货人员数
星期一 28 星期五 19 星期二 15 星期六 3l 星期三 24 星期日 28 星期四
25
得 分 评卷人
得 分
评卷人
五、计算题（每题15分,共45分）
1．Three research teams are currently trying three different approaches for solving the problem that fly safely to Mars. The estimate has been made that the probability that the respective teams—call them 1, 2, and 3—will not succeed is 0.40, 0.60, and 0.80, respectively. Because two more top scientists have been assigned to the project. Table gives the estimated probability that the respective teams will fail when 0, 1, or 2 additional scientists are added to that team. The problem is to determine how to allocate the two additional scientists to minimize the probability that all
three teams will fail.。