运筹学_第1章线性规划与单纯形法
- 格式：ppt
- 大小：277.05 KB
- 文档页数：42
下载文档原格式
合集下载
1 3 第一章线性规划与单纯形法运筹学习题集第一章线性规划与单纯形
1 3 第一章线性规划与单纯形法运筹学习题集第一章线性规划与单纯形13第一章线性规划与单纯形法运筹学习题集第一章线性规划与单纯形法复习思考题1. 试述线性规划数学模型的结构及各要素的特征。
2. 求解线性规划问题时可能出现哪几种结果?哪些结果反映建模时有错误?3. 什么是线性规划问题的标准形式?如何将一个非标准型的线性规划问题转化为标准形式?4. 试述线性规划问题的可行解、基解、基可行解、最优解的概念以及上述解之间的相互关系。
5. 试述单纯形法的计算步骤，如何在单纯形表上判别问题是具有唯一最优解、无穷多最优解、无界解或无可行解?6. 如果线性规划的标准型变换为求目标函数的极小化min z，则用单纯形法计算时如何判别问题已得到最优解?7. 在确定初始可行基时，什么情况下要在约束条件中增添人工变量?在目标函数中人工变量前的系数为(-M)的经济意义是什么?8. 什么是单纯形法计算的两阶段法?为什么要将计算分成两个阶段进行,如何根据第一阶段的计算结果来判定第二阶段的计算是否需要继续进行?9. 简述退化的含义及处理退化的勃兰特规则。
10. 举例说明生产和生活中应用线性规划的可能案例，并对如何应用进行必要描述。
11. 判断下列说法是否正确:(a) 图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的;(b) 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大;(c) 线性规划问题的每一个基解对应可行域的一个顶点;(d) 如线性规划问题存在可行域，则可行域一定包含坐标的原点;(e) 对取值无约束的变量xj，通常令xj=x′j-x″j，其中x′j?0，x″j?0，在用单纯形法求得的最优解中有可能同时出现x′j,0，x″j,0;(f) 用单纯形法求解标准型的线性规划问题时，与σj,0对应的变量都可以被选作换入变量; (g) 单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负;(h) 单纯形法计算中，选取最大正检验数σk对应的变量xk作为换入变量，将使目标函数值得到最快的增长;(i) 一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果;(j) 线性规划问题的任一可行解都可以用全部基可行解的线性组合表示; (k)若X1，X2分别是某一线性规划问题的最优解，则X=λ1X1+λ2X2也是该线性规划问题的最优解，其中λ1、λ2可以为任意正的实数;(l) 线性规划用两阶段法求解时，第一阶段的目标函数通常写为minz=?ixai(xai为人工变量)，但也可写为min z=?ikixai,只要所有ki均为大于零的常数;(m)对一个有n个变量、m个约束的标准型的线性规划问题，其可行域的顶点恰好为Cmn个; (n) 单纯形法的迭代计算过程是从一个可行解转换到目标函数值更大的另一个可行解; (o) 线性规划问题的可行解如为最优解，则该可行解一定是基可行解; (p) 若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解;(q) 线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值，则该顶点处的目标函数值达到最优;(r) 将线性规划约束条件的“?”号及“?”号变换成“=”号，将使问题的最优目标函数值得到改善;(s) 线性规划目标函数中系数最大的变量在最优解中总是取正的值;(t) 一个企业利用3种资源生产4种产品，建立线性规划模型求解得到的最优解中，最多只含有3种产品的组合;(u) 若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解; (v) 一个线性规划问题求解时的迭代工作量主要取决于变量数的多少，与约束条件的数量关系相对较小。
第1章-线性规划及单纯形法-课件(1)
✓ x1、 x2 0
IБайду номын сангаас
设备
1
原材料 A 4
原材料 B 0
利润
2
II 资源限量
2 8 台时
0
16kg
4
12kg
3
第一章 线性规划及单纯形法 运筹学
该计划的数学模型
✓ 目标函数 ✓ 约束条件
Max Z = 2x1 + 3x2
x1 + 2x2 8 4x1 16 4x2 12 x1、 x2 0
x1
✓ 美国航空公司关于哪架飞机用于哪一航班和哪些 机组人员被安排于哪架飞机的决策。
✓ 美国国防部关于如何从现有的一些基地向海湾运 送海湾战争所需要的人员和物资的决策。
✓ ……
第一章 线性规划及单纯形法 运筹学
二、线性规划问题的数学模型
✓ 1、一般形式 ✓ 2、简写形式 ✓ 3、表格形式 ✓ 4、向量形式 ✓ 5、矩阵形式
1、唯一最优解
max Z 2 x 1 3 x 2
2 x 1 2 x 2 12 ⑴
x1 4 x1
2 x2
8 16
⑵ ⑶
4 x 2 12 ⑷
x 1 0 , x 2 0
1 234 56
x2
⑶ ⑷
(4，2)
0 1 234 5678
x1
⑵
⑴
✓最优解：x1 = 4,x2 = 2，有唯一最优解Z=14。
第一章 线性规划及单纯形法 运筹学
三、线性规划模型的标准形式
✓ 1、标准形式 ✓ 2、转换方式
第一章 线性规划及单纯形法 运筹学
1、标准形式
maZx cjxj
xj
aijxj 0
bi
运筹学第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章线性规划与单纯形法第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章线性规划及单纯形法
线性规划及单纯形法 一．选择1. 运筹学应用分析、试验、（C ）的方法，对经济管理系统中人、财、物等有限资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。
A 统筹 B 量化 C 优化 D 决策2. 运筹学研究的基本手段是（A ）。
A 建立数学模型B 进行数学分析C 进行决策分析D 建立管理规范 3. 运筹学研究的基本特点是（ C ）。
A 进行系统局部独立分析B 考虑系统局部优化C 考虑系统的整体优化D 进行系统的整体决策4. 线性规划问题的数学模型包含三个组成要素：决策变量、目标函数、（B ） A 表达式 B 约束条件 C 方程变量 D 价值系数5. 线性规划问题的基可行解X 对应线性规划问题可行域（凸集）的（ C ） A 边 B 平面 C 顶点 D 内部6. 目标函数取极小化（Z min ）的线性规划问题可以转化为目标函数取极大化即（C ）的线性规划问题求解A Z minB )min(Z -C )max(Z -D Z max -7. 标准形式的线性规划问题，最优解（C ）是可行解A 一定B 一定不C 不一定D 无法确定8. 在线性规划问题中，称满足所有约束条件方程和非负限制的解为（ C ）。
A 最优解 B 基可行解 C 可行解 D 基解9. 生产和经营管理中经常提出任何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是所谓的（D ）A 管理问题B 规划问题C 决策问题D 优化问题10. 在线性规划问题中，图解法适合用于处理变量（ B ）个的线性规划问题 A 1 B 2 C 3 D 411. 求解线性规划问题时，解的情况有:唯一最优解、无穷多最优解、（ C ）、无可行解 A 无解B 无基解 C 无界解 D 无基可行解12. 在用图解法求解的时，找不到满足约束条件的公共范围，这时问题有（D ），其原因是模型本身有错误，约束条件之间相互矛盾，应检查修正。
A 唯一最优解 B 无穷多最优解 C 无界解D 无可行解13. 线性规划问题的基可行解()Tn X X X ,,1 =为基可行解的充要条件是X 的正分量所对应的系数列向量是（B ）A 线性相关B 线性独立C 非线性独立D 无法判断14. 线性规划问题进行最优性检验和解的判别时，如果当0≤j σ时，人工变量仍留在基本量中且不为零，（D ）A 唯一最优解B 无穷多最优解C 无界解D 无可行解15.如果集合C 中任意两个点21,X X 其连线上的所有点也都是集合C 中的点，称C 为（B ）A 集合B 凸集C 顶点D 子集16.线性规划问题求解的时候，目标函数与某一个约束条件平行，则解的情况为（ D ） A 无穷多最优解B 无可行解C 唯一最优解D 无法确定17.线性规划问题求解的时候,该线性规划问题有可行域，目标函数与某一个约束条件平行，则解的情况为（A ）A 无穷多最优解B 无可行解C 唯一最优解D 无法确定 18．运筹学涉及的主要领域是（C ）A 技术问题B 经济问题C 管理问题D 以上都不是 19.齐王赛马的故事运用运筹学的（C ）理论。
运筹学第一章
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．用X j （j=1.2…5）分别代表5中饲料的采购数，线性规划模型：12345123412341234min 0.20.70.40.30.8.3267000.50.2300.20.8100(1,2,3,4,5,6)0j z x x x x x st x x x x x x x x x x x x x x x x j =+++++++≥+++≥+++≥=≥555 +18 +2 0.5+2 2.解：设123456x x x x x x x 表示在第i 个时期初开始工作的护士人数，z 表示所需的总人数，则123456161223344556min .607060502030(1,2.3.4.5.6)0i z x x x x x x st x x x x x x x x x x x x x i =++++++≥+≥+≥+≥+≥+≥=≥ 3．解：设用i=1，2，3分别表示商品A ，B ，C ，j=1，2，3分别代表前，中，后舱，Xij 表示装于j 舱的i 种商品的数量，Z 表示总运费收入则：111213212223313233111213212223313233112131122232132333112131max 1000()700()600().6001000800105740010575400105715008652000z x x x x x x x x x st x x x x x x x x x x x x x x x x x x x x x =++++++++++≤++≤++≤++≤++≤++≤++≤ 122232132333112131122232132333122232112131132333865300086515008650.158658650.158658650.18650(1,2.3.1,2,3)ij x x x x x x x x x x x x x x x x x x x x x x x x x i j ++≤++≤++≤++++≤++++≤++≥== 5. （1）Z = 4（2）12121212max .6101207051038z x x st x x x x x x =++≤+≥≤≥≤≥ 解：如图：由图可得： **(10,6)16T x Z == ； 即该问题具有唯一最优解*(10,6)Tx =（3）无可行解(4)12121212max 56.22232,0z x x st x x x x x x =+-≥-+≤≥ 如图：由图知，该问题具有无界解。
第一章线性规划及单纯形法
第一章线性规划及单纯形法6.6单纯形法小结Drawingontheexampl,thetwoaxisinterceptsareplotted.2、求初始基可行解并进行最优性检验Cj比值CBXBb 检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000令非基变量x1=0，x2=0，找到一个初始基可行解：x1=0，x2=0，x3=8，x4=12，x5=36，σj＞0，此解不是最优（因为z=3x1+5x2+0x3+0x4+0x5)即X0=(0,0,8,12,36)T，此时利润Z=03、寻找另一基可行解Cj比值CBXBb检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9主元首先确定入基变量再确定出基变量检验数?j81010060101/2012300-21x3x2x5050-30300-5/20Cj比值CBXBb检验数?jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9令x1=0，x4=0，得x2=6，x3=8，x5=12，即得基可行解X1=(0,6,8,0,12)T此时Z＝30σ1=3＞0，此解不是最优迭代4、寻找下一基可行解Cj比值CBXBb检验数?jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数?j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1令x4=0，x5=0，得x1=4，x2=6，x3=4，即X0=(4,6,4,0,0)T?j＜0最优解:X=(4,6,4,0,0)T最优值:Z=42小结：单纯形表格法的计算步骤①将线性规划问题化成标准型。
②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。
运筹学第一章
max z = - x1’ +2x2 +3（ x3’ - x3” ） - x1’ +x2 – ( x3’ - x3” )-x4 = 9 st. 3x1’ +2x2 -4 ( x3’ - x3” )-x5= 7 x1’ +2x2 - 3 ( x3’ - x3” ) = 6 x1’ ≥ 0, x2 ≥ 0, x3’ ≥0 x3” ≥0
3.线性规划问题的标准形式 线性规划问题的标准形式 max z =- x1-2x2 -3x3 2 x1’+x2 +(x3’ - x3” )+ x4 = 9 3 x1’ +x2 +2 (x3’ - x3” ) –x5 = 4 st. -4 x1’ +2x2 +3 (x3’ - x3” ) =6 x1’ ≥ 0, x2 ≥0, x3’ ≥0 x3” ≥0
例1-1-2 ---1 min z = x1+2x2 +3x3 ﹣2 x1+x2 +x3 ≤9 st. ﹣3 x1+x2 +2x3 ≥ 4
4 x1－2x2 － 3x3 =﹣6
x1 ≤0, x2 ≥0, x3 无约束。 （1）min z = x1+2x2 +3x3 令Z=-Z’ min Z=min（-z ’）=max z ’
第一章 讲解内容
第一节： 第一节：线性规划问题及其数学模型 第二节： 第二节：线性规划问题的几何意义 第三节：单纯形法 第三节： 第四节： 第四节：单纯形法的计算过程 第五节： 第五节：单纯形法的进一步讨论 第六节： 第六节：应用案例
第一章 线性规划问题及其数学模型 1. 问题的提出 2.图解法（重点） 3. 线性规划问题的标准形式 4.线性规划问题的解的概念（重点、难点）
3.线性规划问题的标准形式 线性规划问题的标准形式 max z =- x1-2x2 -3x3 2 x1’+x2 +(x3’ - x3” )+ x4 = 9 3 x1’ +x2 +2 (x3’ - x3” ) –x5 = 4 st. -4 x1’ +2x2 +3 (x3’ - x3” ) =6 x1’ ≥ 0, x2 ≥0, x3’ ≥0 x3” ≥0
例1-1-2 ---1 min z = x1+2x2 +3x3 ﹣2 x1+x2 +x3 ≤9 st. ﹣3 x1+x2 +2x3 ≥ 4
4 x1－2x2 － 3x3 =﹣6
x1 ≤0, x2 ≥0, x3 无约束。 （1）min z = x1+2x2 +3x3 令Z=-Z’ min Z=min（-z ’）=max z ’
第一章 讲解内容
第一节： 第一节：线性规划问题及其数学模型 第二节： 第二节：线性规划问题的几何意义 第三节：单纯形法 第三节： 第四节： 第四节：单纯形法的计算过程 第五节： 第五节：单纯形法的进一步讨论 第六节： 第六节：应用案例
第一章 线性规划问题及其数学模型 1. 问题的提出 2.图解法（重点） 3. 线性规划问题的标准形式 4.线性规划问题的解的概念（重点、难点）
运筹学[第一章线性规划与单纯形法]山东大学期末考试知识点复习
![运筹学[第一章线性规划与单纯形法]山东大学期末考试知识点复习](https://img.taocdn.com/s1/m/83512a81ba0d4a7303763a31.png)
第一章线性规划与单纯形法1．线性规划问题的数学模型(1)一般形式(2)标准型式]2．数学模型化为标准型(1)若目标函数实现最小化，则min z=-max z'(令z'=-z)(2)若约束方程为不等式，则若约束方程为“≤”不等式左端+松驰变量(≥0)=右端若约束方程为“≥”不等式左端-剩余变量(≥0)=右端(3)若存在取值无约束的变量x k(1≤k≤咒)，则在标准型中x k=x'k-x"k(其中x k=x'，x"k≥0)3．线性规划的解线性规划问题：(1)可行解：满足约束条件②和③的解X=(x1，x2，…，x n)T。
(2)最优解：使目标函数①达到最大值的可行解。
(3)基：设A为约束方程组②的m×n阶系数矩阵，设n＞m，其秩为m，B 为矩阵A中的一个m×m阶的满秩子矩阵，则称B为线性规划问题的一个基。
不失一般性，设B中每一个列向量P j(j=1，2，…，m)称为基向量，与基向量PJ对应的变量x j称为基变量。
除基变量以外的变量为非基变量。
(4)基本解：在约束方程组②中，令所有非基变量x m+1=x m+2=…=x n=0，此时方程组②有唯一解X B=(x1，x2，…，x m)T，将此解加上非基变量取0的值有X=(x1，x2，…，x m，0，0…，0)T，称X为线性规划问题的基本解。
(5)基本可行解：满足非负条件③的基本解。
(6)可行基：对应于基本可行解的基。
4．初始基可行解的确定(1)直接从A中观察到存在一个初始可行基。
(2)对所有约束条件是“≤”形式的不等式，可利用化为标准型的方法，在每个约束条件左端加上一个松弛变量，这m个松弛变量就构成一个基变量，则对应的m个向量组成的单位矩阵B就是线性规划问题的一个可行基。
(3)对所有约束条件是“≥”形式的不等式以及等式约束情况，采用人造基的方法。
即对不等式约束的左端减去一个非负的剩余变量后，再加上一个非负的人工变量；对于等式约束的左端再加上一个非负的人工变量。
运筹学基础及应用第五版胡运权第一章
问题的提出 某企业计划生产Ⅰ、Ⅱ两种产品。这两种产品都要分别在A、B、C、D四种不同设备上加工。生产每件产品Ⅰ需占用各设备分别为2、1、4、0h，生产每件产品Ⅱ，需占用各设备分别为2、2、0、4h。已知各设备计划期内用于生产这两种产品的能力分别为12、8、16、12h，又知每生产一件产品Ⅰ企业能获得2元利润，每生产一件产品Ⅱ企业能获得3元利润，问企业应安排生产两种产品各多少件，使总的利润收入为最大。
xi 0
aij
aLj
xL 0
i
∴ P1 , P2,······,PL-1, PL+1,······ Pm, Pj 线性无关。
∴ X1 也为基本可行解。
四、最优性检验和解的判别
令
，其中 随基的改变而改变
X1 = (x1 0- a1j ,x2 0- a2j ,···,xm 0- amj ,0,···,,···,0)T
必要性：X非基本可行解 X非凸集顶点 不失一般性，设X=(x1,x2,······,xm,0,0,······,0)T，为非基本可行解， ∵ X为可行解，
证：等价于 X非基本可行解X非凸集顶点
又 X是非基本可行解， ∴ P1,P2,······,Pm线性相关，即有 1P1+2P2+······+mPm=0， 其中1，2，······，m不全为0，两端同乘≠0，得 1P1+2P2+······+mPm=0，······（2）
∵ >0, 1->0 ，当xj=0， 必有yj=zj=0
∴
pjyj =
j=1
n
pjyj=b ······(1)
j=1
r
pjzj =
j=1
n
pjzj=b ······(2)
xi 0
aij
aLj
xL 0
i
∴ P1 , P2,······,PL-1, PL+1,······ Pm, Pj 线性无关。
∴ X1 也为基本可行解。
四、最优性检验和解的判别
令
，其中 随基的改变而改变
X1 = (x1 0- a1j ,x2 0- a2j ,···,xm 0- amj ,0,···,,···,0)T
必要性：X非基本可行解 X非凸集顶点 不失一般性，设X=(x1,x2,······,xm,0,0,······,0)T，为非基本可行解， ∵ X为可行解，
证：等价于 X非基本可行解X非凸集顶点
又 X是非基本可行解， ∴ P1,P2,······,Pm线性相关，即有 1P1+2P2+······+mPm=0， 其中1，2，······，m不全为0，两端同乘≠0，得 1P1+2P2+······+mPm=0，······（2）
∵ >0, 1->0 ，当xj=0， 必有yj=zj=0
∴
pjyj =
j=1
n
pjyj=b ······(1)
j=1
r
pjzj =
j=1
n
pjzj=b ······(2)
运筹学第1章
18
运筹学解决问题的过程
1）提出问题：认清问题。 2）寻求可行方案：建模、求解。 3）确定评估目标及方案的标准或方 法、途径。 4）评估各个方案：解的检验、灵敏 性分析等。
19
运筹学解决问题的过程
5）选择最优方案：决策。 6）方案实施：回到实践中。 7）后评估：考察问题是否得到完 满解决。
1）2）3）形成问题；4）5）分析 问题：定性分析与定量分析相结合，构 成决策。
10
运筹学的产生和发展
战后这些研究成果被应用到生产、 经济领域，并得到迅速发展——有关理 论和方法的研究、实践不断深入。
1947年美国数学家丹捷格(G.B.Dantzig）
提出了求解线性规划的有效方法——单 纯形法。
11
运筹学的产生和发展
数学对运筹学的作用——是有 关理论和方法的研究基础，是建立 运筹学模型的工具。
20
如何学习运筹学课程
学习运筹学要把重点放在分 析、理解有关的概念、思路上。 在自学过程中，应该多向自己提 问，例如一个方法的实质是什么， 为什么这样进行，怎么进行等。
自学时要掌握三个重要环节：
21
如何学习运筹学课程
1.认真阅读教材和参考资料， 以指定教材为主，同时参考其他有 关书籍。一般每一本运筹学教材都 有自己的特点，但是基本原理、概 念都是一致的。注意主从，参考资 料会帮助你开阔思路，使学习深入。 但是，把时间过多放在参考资料上， 会导致思路分散，不利于学好。
2
运筹学
1.绪论 2.线性规划建模及单纯形法 3.线性规划问题的对偶与灵敏度分析 4.运输问题 5.动态规划 6.排队论 7.决策分析
8.图与网络分析
第一章 绪 论
4
运筹学概况简述
运筹学解决问题的过程
1）提出问题：认清问题。 2）寻求可行方案：建模、求解。 3）确定评估目标及方案的标准或方 法、途径。 4）评估各个方案：解的检验、灵敏 性分析等。
19
运筹学解决问题的过程
5）选择最优方案：决策。 6）方案实施：回到实践中。 7）后评估：考察问题是否得到完 满解决。
1）2）3）形成问题；4）5）分析 问题：定性分析与定量分析相结合，构 成决策。
10
运筹学的产生和发展
战后这些研究成果被应用到生产、 经济领域，并得到迅速发展——有关理 论和方法的研究、实践不断深入。
1947年美国数学家丹捷格(G.B.Dantzig）
提出了求解线性规划的有效方法——单 纯形法。
11
运筹学的产生和发展
数学对运筹学的作用——是有 关理论和方法的研究基础，是建立 运筹学模型的工具。
20
如何学习运筹学课程
学习运筹学要把重点放在分 析、理解有关的概念、思路上。 在自学过程中，应该多向自己提 问，例如一个方法的实质是什么， 为什么这样进行，怎么进行等。
自学时要掌握三个重要环节：
21
如何学习运筹学课程
1.认真阅读教材和参考资料， 以指定教材为主，同时参考其他有 关书籍。一般每一本运筹学教材都 有自己的特点，但是基本原理、概 念都是一致的。注意主从，参考资 料会帮助你开阔思路，使学习深入。 但是，把时间过多放在参考资料上， 会导致思路分散，不利于学好。
2
运筹学
1.绪论 2.线性规划建模及单纯形法 3.线性规划问题的对偶与灵敏度分析 4.运输问题 5.动态规划 6.排队论 7.决策分析
8.图与网络分析
第一章 绪 论
4
运筹学概况简述
运筹学第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
运筹学第一章
第一章、 线性规划和单纯形法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章线性规划与单纯形法
26
线性规划问题的数学模型
7. 线性规划问题的解
线性规划问题
n
max Z cj xj (1) j 1
s.t
n j 1
aij
xj
bi
(i 1, 2,
, m) (2)
x
j
0,
j
1, 2,
, n (3)
求解线性规划问题，就是从满足约束条件(2)、(3)的方程组 中找出一个解，使目标函数(1)达到最大值。
解： Max z = 3x1–5x2’+5x2”–8x3 +7x4 s.t. 2x1–3x2’+3x2”+5x3+6x4+x5= 28 4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0
x1 , x2 0, x3无约束
解:（１）因为x3无符号要求 ，即x3取正值也可取负值，标准 型中要求变量非负，所以
用 x3 x3 替换 x3 ，且 x3 , x3 0
20
线性规划问题的数学模型
(2) 第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4， x4≥0,化为等式；
(3) 第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5， x5≥0；
11
线性规划问题的数学模型
3. 建模条件 (1) 优化条件：问题所要达到的目标能用线型函数描述，且 能够用极值 （max 或 min）来表示；
(2) 限定条件：达到目标受到一定的限制，且这些限制能够 用决策变量的线性等式或线性不等式表示；
(3) 选择条件：有多种可选择的方案供决策者选择，以便找 出最优方案。
线性规划问题的数学模型
7. 线性规划问题的解
线性规划问题
n
max Z cj xj (1) j 1
s.t
n j 1
aij
xj
bi
(i 1, 2,
, m) (2)
x
j
0,
j
1, 2,
, n (3)
求解线性规划问题，就是从满足约束条件(2)、(3)的方程组 中找出一个解，使目标函数(1)达到最大值。
解： Max z = 3x1–5x2’+5x2”–8x3 +7x4 s.t. 2x1–3x2’+3x2”+5x3+6x4+x5= 28 4x1+2x2’-2x2”+3x3-9x4-x6= 39 -6x2’+6x2”-2x3-3x4-x7 = 58 x1 ,x2’,x2”,x3 ,x4 ,x5 ,x6 ,x7 ≥ 0
x1 , x2 0, x3无约束
解:（１）因为x3无符号要求 ，即x3取正值也可取负值，标准 型中要求变量非负，所以
用 x3 x3 替换 x3 ，且 x3 , x3 0
20
线性规划问题的数学模型
(2) 第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4， x4≥0,化为等式；
(3) 第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5， x5≥0；
11
线性规划问题的数学模型
3. 建模条件 (1) 优化条件：问题所要达到的目标能用线型函数描述，且 能够用极值 （max 或 min）来表示；
(2) 限定条件：达到目标受到一定的限制，且这些限制能够 用决策变量的线性等式或线性不等式表示；
(3) 选择条件：有多种可选择的方案供决策者选择，以便找 出最优方案。
运筹学(第二版)课后答案
得到一个基本解，但非可行解 x 同理可以求出
( 2)
x1 6 x 4 12 x 2 3
T ， Z 2 18 。 （6,0,2,12,0）
1 0 0 ( 3) T 。 （P3，P4，P5） （0,0,4,12,18） 0 1 0 ，得基本可行解 x 0 0 1
附录四习题参考答案
附录四：习题参考答案 第一章 线性规划及单纯形法
1.1 （1）解： 第一，求可行解集合。令两个约束条件为等式，得到两条直线，在第一 象限划出满足两个不等式的区域，其交集就是可行集或称为可行域，如图 1-1 所示，交集为（1/2, 0） 。 第二，绘制目标函数图形。将目标函数的系数组成一个坐标点（6，4） ， 过原点 O 作一条矢量指向点（6，4） ，矢量的长度不限，矢量的斜率保持 4 比 6，再作一条与矢量垂直的直线，这条直线就是目标函数图形，目标函 数图形的位置任意，如果通过原点则目标函数值 Z=0，如图 1-2 所示。 第三，求最优解。图 1-2 的矢量方向是目标函数增加的方向或称梯度方 向， 在求最小值时将目标函数图形沿梯度方向的反方向平行移动， （在求最 大值时将目标函数图形沿梯度方向平行移动）直到可行域的边界，停止移 动，其交点对应的坐标就是最优解，如图 1-3 所示。最优解 x=（1/2, 0）, 目标函数的最小值 Z=3。 X2 X2
CB 0 0 σj 0 10 σj 5 11
10 X1 3 5 10 0 1 0 1 0 0
5 X2 4 2 5 14/5 2/5 1 1 0 0
（表一）
T *
0 X3 1 0 0 1 0 0 5/14 -1/7 -5/14
0 X4 0 1 0 -3/5 1/5 -2 -3/14 2/7 -25/14
( 2)
x1 6 x 4 12 x 2 3
T ， Z 2 18 。 （6,0,2,12,0）
1 0 0 ( 3) T 。 （P3，P4，P5） （0,0,4,12,18） 0 1 0 ，得基本可行解 x 0 0 1
附录四习题参考答案
附录四：习题参考答案 第一章 线性规划及单纯形法
1.1 （1）解： 第一，求可行解集合。令两个约束条件为等式，得到两条直线，在第一 象限划出满足两个不等式的区域，其交集就是可行集或称为可行域，如图 1-1 所示，交集为（1/2, 0） 。 第二，绘制目标函数图形。将目标函数的系数组成一个坐标点（6，4） ， 过原点 O 作一条矢量指向点（6，4） ，矢量的长度不限，矢量的斜率保持 4 比 6，再作一条与矢量垂直的直线，这条直线就是目标函数图形，目标函 数图形的位置任意，如果通过原点则目标函数值 Z=0，如图 1-2 所示。 第三，求最优解。图 1-2 的矢量方向是目标函数增加的方向或称梯度方 向， 在求最小值时将目标函数图形沿梯度方向的反方向平行移动， （在求最 大值时将目标函数图形沿梯度方向平行移动）直到可行域的边界，停止移 动，其交点对应的坐标就是最优解，如图 1-3 所示。最优解 x=（1/2, 0）, 目标函数的最小值 Z=3。 X2 X2
CB 0 0 σj 0 10 σj 5 11
10 X1 3 5 10 0 1 0 1 0 0
5 X2 4 2 5 14/5 2/5 1 1 0 0
（表一）
T *
0 X3 1 0 0 1 0 0 5/14 -1/7 -5/14
0 X4 0 1 0 -3/5 1/5 -2 -3/14 2/7 -25/14
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
经第2工厂后的水质要求：
[ 0.8( 2 x1 ) ቤተ መጻሕፍቲ ባይዱ (1.4 x2 )] 2
700
1000
数学模型
目标函数 min z 1000x1 800x2
约束条件
x1 1
0.8x1 x2 1.6
x1 2
x2 1.4
x1 , x2 0
共同的特征
(1)每一个线性规划问题都用一组决策变量
图1-2
max z 2x1 3x2
x1 2x2 2
4 x1
16 4x2 12
x1 , x2 0
图1-3 目标值在（4，2）点，达到最大值14 目标函数 max z 2x1 3x2
x2
2 3
x1
z 3
表示一簇平行线
可能出现的几种情况
（1）无穷多最优解(多重最优解)，见图1-4 （2）无界解，见图1-5-1 （3）无可行解，见图1-5-2
可得到该问题的标准型
例4的标准型
max z ' x1 2x2 3(x4 x5 ) 0x6 0x7
x1 x2 (x4 x5 ) x6
7
x1 x2 (x4 x5 )
x7 2
3x1 x2 2(x4 x)
5
x1, x2 , x4 , x5 , x6 , x7 0
,
i 1,2,,m
x
j
0,
j 1,2,,n
用向量表示为：
M
'' 1
:目标函数： max
z
CX
n
约束条件： j1
Pj
x
j
b
x
j
0,
j 1,2,,n
C c1 ,c2 ,,cn ;
x1
a1 j
b1
X
a22
x2
a2n xn
b2
am1x1 am2 x2 amn xn bn x1,x2 ,,xn 0
线性规划问题的几种表示形式
M
' 1
:
n
目标函数：max z c j x j
j 1
n
约束条件： j1
aij x j
bi
图1-1
续例2
• 第一 化工厂每天排放含有某种有害物质的工业污 水2万立方米，第二化工厂每天排放这种工业污水 1.4万立方米。从第一化工厂排出的工业污水流到 第二化工厂以前，有20%可自然净化。根据环保要 求，河流中工业污水的含量应不大于0.2%。这两个 工厂都需各自处理一部分工业污水。第一化工厂处 理工业污水的成本是1000元/万立方米。
• 以上提到的几种解的概念，它们之间的关系可用图1-6 表明。
• 另外还要说明一点，基解中的非零分量的个数小于m 个时，该基解是退化解。在以下讨论时，假设不出现 退化的情况。以上给出了线性规划问题的解的概念和 定义，它们将有助于用来分析线性规划问题的求解过 程。
图1-6 它们之间的关系
小结
• 1. 线性规划问题的模型特征 • 2. 通过图解法了解如何求解线性规划问题 • 3. 为求解高维线性规划问题，必须建立的
(4) 要有一个达到目标的要求，它可用决策 变量的线性函数(称为目标函数)来表示。 按问题的不同，要求目标函数实现最大化 或最小化。
它们的对应关系可用表格表示：
决策变量
资源
x1 x2 xn
1
活
a11
a12 a1n
b1
2 a21 a22 a2n b2
动
m am1 am2 amn bm
(2) 约束方程为不等式。这里有两种情况：一种是 约束方程为“≤”不等式，则可在“≤”不等式的 左端加入非负松弛变量，把原“≤”不等式变为 等式；另一种是约束方程为“≥”不等式，则可 在“≥”不等式的左端减去一个非负剩余变量(也 可称松弛变量)，把不等式约束条件变为等式约 束条件。下面举例说明。
例3 将例1的数学模型化为标准型。
运筹学
（第二版）
刁在筠等 编
第1章 线性规划与 单纯形法
第1节 线性规划问题 及其数学模型
高等教育出版社
二. 线性规划与目标规划
第1章 第2章 第3章 第4章
线性规划与单纯形法 对偶理论与灵敏度分析 运输问题 目标规划
第1章 线性规划与单纯形法
第1节 线性规划问题及其数学模型 第2节 线性规划问题的几何意义 第3节 单纯形法 第4节 单纯形法的计算步骤 第5节 单纯形法的进一步讨论 第6节 应用举例
x1,x2 0
x1,x2 ,x3 ,x4 ,x 0
(3) 若存在取值无约束的变量xk,可令,
xk xk' xk" 其中。 xk' , xk" 0
例4 将下述线性规划问题化为标准型
min z x1 2x2 3x3
x1 x2 x3 7
第1节 线性规划问题及其数学模型
• 1.1 问题的提出 • 1.2 图解法 • 1.3 线性规划问题的标准形式 • 1.4 线性规划问题的解的概念
第1节 线性规划问题及其数学模型
线性规划是运筹学的一个重要分支。线性规划在理论 上比较成熟，在实用中的应用日益广泛与深入。特别是 在电子计算机能处理成千上万个约束条件和决策变量的 线性规划问题之后，线性规划的适用领域更为广泛了。 从解决技术问题的最优化设计到工业、农业、商业、交 通运输业、军事、经济计划和管理决策等领域都可以发 挥作用。它已是现代科学管理的重要手段之一。解线性
续例1
该工厂 • 每生产一件产品Ⅰ可获利2元， • 每生产一件产品Ⅱ可获利3元， • 问应如何安排计划使该工厂获利
最多?
如何用数学关系式描述这问题， 必须考虑
设 x1, x2分别表示计划生产 I,II产品的数量， 称它们为决策变量。
生产x1,x2的数量多少，受资源拥有量的限制, 这是约束条件。即x1 2x2 8;4x1 16;4x2 12
1.4 线性规划问题的解的概念
• 1.可行解 • 2.基 • 3.基可行解 • 4.可行基
1. 可行解
n
max z c j x j
j 1
n
aij x j
bi ,i 1,2,m
j1
x
j
0,
j 1,2,,n
(1 4) (1 5) (1 6)
满足约束条件(1-5)，(1-6)式的解X=(x1,x2，…，xn)T， 称为线性规划问题的可行解，其中使目标函数达到
价值系数 c1 c2 cn
线性规划的一般模型形式
目标函数
max(min) z c1x1 c2x2 cn xn 约束条件
a11x1 a12x2 a1n xn ( , )b1 a21x1 a22x2 a2n xn ( , )b2
x1 x2 x3 3
3x1 x2 x3 5
x1,x2 0; x3为无约束
处理的步骤：
(1) 用x4-x5替换x3，其中x4，x5≥0； (2) 在第一个约束不等式≤号的左端加入松
弛变量x6； (3) 在第二个约束不等式≥号的左端减去剩
余变量x7； (4) 令z′= -z，把求min z 改为求max z′，即
• 第二 化工厂处理工业污水的成本是800元/万立方 米。现在要问在满足环保要求的条件下，每厂各应 处理多少工业污水，使这两个工厂总的处理工业污 水费用最小。
建模型之前的分析和计算
设：
第一化工厂每天处理工业污水量为x1万立方米， 第二化工厂每天处理工业污水量为x2万立方米
经第2工厂前的水质要求：( 2 x1 ) 2 500 1000
x j( j 1,2,m )为基变量。
3. 基可行解 满足非负条件（1-6）的基解，
称为基可行解. 基可行解的非零分量的数目
也不大于m，并且都是非负的。
•
0,Q1 ,Q2 ,Q3 ,Q4
是基可行解
4. 可行基 对应于基可行解的基，称为可行基。
• 约束方程组(1-5)具有基解的数目最多是 Cnm个。一般基 可行解的数目要小于基解的数目。
概念
最大值的可行解称为最优解。
2. 基，基向量，基变量
B是系数矩阵A中的m m阶非奇异子矩阵B 0
称B为线性规划问题的基。
a11 a12 a1m
B
a21
a22
a2m
P1
,P2
,
Pm
am1 am2 amm
Pj( j 1,2,m )为基向量，
( 1.1 ) (1.2 )
am1x1 am2 x2 am xn ( , )bm
x1,x2 ,, xn 0
( 1.3 )
1.2 图解法
例1是二维空间（平面）线性规划问题， 可用作图法直观地来表述它的求解。
因存在 x1,x2 0 必须在直角坐标的第1象限内作图， 求解。
x2
; Pj
a2
j
;b
b2
;
j
1,2,n
xn
amj
bm
用矩阵表示为：
M
'' 1
:目标函数：max
z
[ 0.8( 2 x1 ) ቤተ መጻሕፍቲ ባይዱ (1.4 x2 )] 2
700
1000
数学模型
目标函数 min z 1000x1 800x2
约束条件
x1 1
0.8x1 x2 1.6
x1 2
x2 1.4
x1 , x2 0
共同的特征
(1)每一个线性规划问题都用一组决策变量
图1-2
max z 2x1 3x2
x1 2x2 2
4 x1
16 4x2 12
x1 , x2 0
图1-3 目标值在（4，2）点，达到最大值14 目标函数 max z 2x1 3x2
x2
2 3
x1
z 3
表示一簇平行线
可能出现的几种情况
（1）无穷多最优解(多重最优解)，见图1-4 （2）无界解，见图1-5-1 （3）无可行解，见图1-5-2
可得到该问题的标准型
例4的标准型
max z ' x1 2x2 3(x4 x5 ) 0x6 0x7
x1 x2 (x4 x5 ) x6
7
x1 x2 (x4 x5 )
x7 2
3x1 x2 2(x4 x)
5
x1, x2 , x4 , x5 , x6 , x7 0
,
i 1,2,,m
x
j
0,
j 1,2,,n
用向量表示为：
M
'' 1
:目标函数： max
z
CX
n
约束条件： j1
Pj
x
j
b
x
j
0,
j 1,2,,n
C c1 ,c2 ,,cn ;
x1
a1 j
b1
X
a22
x2
a2n xn
b2
am1x1 am2 x2 amn xn bn x1,x2 ,,xn 0
线性规划问题的几种表示形式
M
' 1
:
n
目标函数：max z c j x j
j 1
n
约束条件： j1
aij x j
bi
图1-1
续例2
• 第一 化工厂每天排放含有某种有害物质的工业污 水2万立方米，第二化工厂每天排放这种工业污水 1.4万立方米。从第一化工厂排出的工业污水流到 第二化工厂以前，有20%可自然净化。根据环保要 求，河流中工业污水的含量应不大于0.2%。这两个 工厂都需各自处理一部分工业污水。第一化工厂处 理工业污水的成本是1000元/万立方米。
• 以上提到的几种解的概念，它们之间的关系可用图1-6 表明。
• 另外还要说明一点，基解中的非零分量的个数小于m 个时，该基解是退化解。在以下讨论时，假设不出现 退化的情况。以上给出了线性规划问题的解的概念和 定义，它们将有助于用来分析线性规划问题的求解过 程。
图1-6 它们之间的关系
小结
• 1. 线性规划问题的模型特征 • 2. 通过图解法了解如何求解线性规划问题 • 3. 为求解高维线性规划问题，必须建立的
(4) 要有一个达到目标的要求，它可用决策 变量的线性函数(称为目标函数)来表示。 按问题的不同，要求目标函数实现最大化 或最小化。
它们的对应关系可用表格表示：
决策变量
资源
x1 x2 xn
1
活
a11
a12 a1n
b1
2 a21 a22 a2n b2
动
m am1 am2 amn bm
(2) 约束方程为不等式。这里有两种情况：一种是 约束方程为“≤”不等式，则可在“≤”不等式的 左端加入非负松弛变量，把原“≤”不等式变为 等式；另一种是约束方程为“≥”不等式，则可 在“≥”不等式的左端减去一个非负剩余变量(也 可称松弛变量)，把不等式约束条件变为等式约 束条件。下面举例说明。
例3 将例1的数学模型化为标准型。
运筹学
（第二版）
刁在筠等 编
第1章 线性规划与 单纯形法
第1节 线性规划问题 及其数学模型
高等教育出版社
二. 线性规划与目标规划
第1章 第2章 第3章 第4章
线性规划与单纯形法 对偶理论与灵敏度分析 运输问题 目标规划
第1章 线性规划与单纯形法
第1节 线性规划问题及其数学模型 第2节 线性规划问题的几何意义 第3节 单纯形法 第4节 单纯形法的计算步骤 第5节 单纯形法的进一步讨论 第6节 应用举例
x1,x2 0
x1,x2 ,x3 ,x4 ,x 0
(3) 若存在取值无约束的变量xk,可令,
xk xk' xk" 其中。 xk' , xk" 0
例4 将下述线性规划问题化为标准型
min z x1 2x2 3x3
x1 x2 x3 7
第1节 线性规划问题及其数学模型
• 1.1 问题的提出 • 1.2 图解法 • 1.3 线性规划问题的标准形式 • 1.4 线性规划问题的解的概念
第1节 线性规划问题及其数学模型
线性规划是运筹学的一个重要分支。线性规划在理论 上比较成熟，在实用中的应用日益广泛与深入。特别是 在电子计算机能处理成千上万个约束条件和决策变量的 线性规划问题之后，线性规划的适用领域更为广泛了。 从解决技术问题的最优化设计到工业、农业、商业、交 通运输业、军事、经济计划和管理决策等领域都可以发 挥作用。它已是现代科学管理的重要手段之一。解线性
续例1
该工厂 • 每生产一件产品Ⅰ可获利2元， • 每生产一件产品Ⅱ可获利3元， • 问应如何安排计划使该工厂获利
最多?
如何用数学关系式描述这问题， 必须考虑
设 x1, x2分别表示计划生产 I,II产品的数量， 称它们为决策变量。
生产x1,x2的数量多少，受资源拥有量的限制, 这是约束条件。即x1 2x2 8;4x1 16;4x2 12
1.4 线性规划问题的解的概念
• 1.可行解 • 2.基 • 3.基可行解 • 4.可行基
1. 可行解
n
max z c j x j
j 1
n
aij x j
bi ,i 1,2,m
j1
x
j
0,
j 1,2,,n
(1 4) (1 5) (1 6)
满足约束条件(1-5)，(1-6)式的解X=(x1,x2，…，xn)T， 称为线性规划问题的可行解，其中使目标函数达到
价值系数 c1 c2 cn
线性规划的一般模型形式
目标函数
max(min) z c1x1 c2x2 cn xn 约束条件
a11x1 a12x2 a1n xn ( , )b1 a21x1 a22x2 a2n xn ( , )b2
x1 x2 x3 3
3x1 x2 x3 5
x1,x2 0; x3为无约束
处理的步骤：
(1) 用x4-x5替换x3，其中x4，x5≥0； (2) 在第一个约束不等式≤号的左端加入松
弛变量x6； (3) 在第二个约束不等式≥号的左端减去剩
余变量x7； (4) 令z′= -z，把求min z 改为求max z′，即
• 第二 化工厂处理工业污水的成本是800元/万立方 米。现在要问在满足环保要求的条件下，每厂各应 处理多少工业污水，使这两个工厂总的处理工业污 水费用最小。
建模型之前的分析和计算
设：
第一化工厂每天处理工业污水量为x1万立方米， 第二化工厂每天处理工业污水量为x2万立方米
经第2工厂前的水质要求：( 2 x1 ) 2 500 1000
x j( j 1,2,m )为基变量。
3. 基可行解 满足非负条件（1-6）的基解，
称为基可行解. 基可行解的非零分量的数目
也不大于m，并且都是非负的。
•
0,Q1 ,Q2 ,Q3 ,Q4
是基可行解
4. 可行基 对应于基可行解的基，称为可行基。
• 约束方程组(1-5)具有基解的数目最多是 Cnm个。一般基 可行解的数目要小于基解的数目。
概念
最大值的可行解称为最优解。
2. 基，基向量，基变量
B是系数矩阵A中的m m阶非奇异子矩阵B 0
称B为线性规划问题的基。
a11 a12 a1m
B
a21
a22
a2m
P1
,P2
,
Pm
am1 am2 amm
Pj( j 1,2,m )为基向量，
( 1.1 ) (1.2 )
am1x1 am2 x2 am xn ( , )bm
x1,x2 ,, xn 0
( 1.3 )
1.2 图解法
例1是二维空间（平面）线性规划问题， 可用作图法直观地来表述它的求解。
因存在 x1,x2 0 必须在直角坐标的第1象限内作图， 求解。
x2
; Pj
a2
j
;b
b2
;
j
1,2,n
xn
amj
bm
用矩阵表示为：
M
'' 1
:目标函数：max
z