《运筹学》第一章 线性规划
- 格式:ppt
- 大小:1.49 MB
- 文档页数:82
第一章 线性规划1、由图可得:最优解为2、用图解法求解线性规划: Min z=2x 1+x 2⎪⎪⎩⎪⎪⎨⎧≥≤≤≥+≤+-01058244212121x x x x x x解:由图可得:最优解x=1.6,y=6.4Max z=5x 1+6x 2⎪⎩⎪⎨⎧≥≤+-≥-0,23222212121x x x x x x解:由图可得:最优解Max z=5x 1+6x 2, Max z= +∞Maxz = 2x 1 +x 2⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤0,5242261552121211x x x x x x x由图可得:最大值⎪⎩⎪⎨⎧==+35121x x x , 所以⎪⎩⎪⎨⎧==2321x xmax Z = 8.1212125.max 23284164120,1,2maxZ .jZ x x x x x x x j =+⎧+≤⎪≤⎪⎨≤⎪⎪≥=⎩如图所示,在(4,2)这一点达到最大值为26将线性规划模型化成标准形式:Min z=x 1-2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≥-=++-≥+-≤++无约束321321321321,0,052327x x x x x x x x x x x x解:令Z ’=-Z,引进松弛变量x 4≥0,引入剩余变量x 5≥0,并令x 3=x 3’-x 3’’,其中x 3’≥0,x 3’’≥0Max z ’=-x 1+2x 2-3x 3’+3x 3’’⎪⎪⎩⎪⎪⎨⎧≥≥≥≥≥≥-=++-=--+-=+-++0,0,0'',0',0,05232'''7'''5433213215332143321x x x x x x x x x x x x x x x x x x x7将线性规划模型化为标准形式Min Z =x 1+2x 2+3x 3⎪⎪⎩⎪⎪⎨⎧≥≤-=--≥++-≤++无约束,321321321321,00632442392-x x x x x x x x x x x x解:令Z ’ = -z ,引进松弛变量x 4≥0,引进剩余变量x 5≥0,得到一下等价的标准形式。
第1章线性规划Chapter 1 Linear Programming本章内容提要线性规划是运筹学的重要内容。
本章介绍线性规划数学模型、线性规划的基本概念以及求解线性规划数学模型的基本算法——单纯形法。
学习本章要求掌握以下内容:⏹线性规划模型的结构⏹线性规划的标准形式,非标准形式转化为标准形式⏹线性规划的图解以及相应的概念。
包括:约束直线,可行半空间,可行解,可行域,凸集,极点,目标函数等值线,最优解⏹线性规划的基本概念。
包括:基,基础解,基础可行解,基变量,非基变量,进基变量,离基变量,基变换⏹单纯形法原理。
包括:基变量和目标函数用非基变量表出,检验数,选择进基变量的原则,确定离基变量的方法,主元,旋转运算⏹单纯形表。
包括初始单纯形表的构成,单纯形表运算方法⏹初始基础可行解,两阶段法⏹退化的基础可行解§1.1 运筹学和线性规划1.1.1 运筹学运筹学(Operations Research)是二十世纪三十年代二次大战期间由于战争的需要发展起来的一门学科。
当时,英国组织了一批自然科学和工程科学的学者,和军队指挥员一起,研究大规模战争提出的一些问题。
如轰炸战术的评价和改进、反潜艇作战研究等,研究结果在战争实践中取得了明显得效果。
这些研究当时在英国称为Operational Research,直译为作战研究。
战争结束以后,这些研究方法不断发展完善,并逐步形成学科理论体系,其中一些主要的理论和方法包括:线性规划,网络流,整数规划,动态规划,非线性规划,排队论,决策分析,对策论,计算机模拟等。
这些理论和方法在经济管理领域也得到了广泛应用,Operations Research也转义成为“作业研究”。
我国将Operations Research译成“运筹学”,非常贴切地将Operations Research这一英文术语所包含的作战研究和作业研究两方面的涵义都体现了出来。
现在,运筹学已经成为管理科学重要的基础理论和应用方法,是管理科学专业基本的必修课程之一。
运筹学基本概念及判断题(含答案)第1章线性规划1.任何线性规划一定有最优解。
2.若线性规划有最优解,则一定有基本最优解。
3.线性规划可行域无界,则具有无界解。
4.在基本可行解中非基变量一定为零。
5.检验数λj表示非基变量xj增加一个单位时目标函数值的改变量。
7.可行解集非空时,则在极点上至少有一点达到最优值。
8.任何线性规划都可以化为下列标准形式:9.基本解对应的基是可行基。
10.任何线性规划总可用大M单纯形法求解。
11.任何线性规划总可用两阶段单纯形法求解。
12.若线性规划存在两个不同的最优解,则必有无穷个最优解。
13.两阶段法中第一阶段问题必有最优解。
14.两阶段法中第一阶段问题最优解中基变量全部非人工变量,则原问题有最优解。
15.人工变量一旦出基就不会再进基。
16.普通单纯形法比值规则失效说明问题无界。
17.最小比值规则是保证从一个可行基得到另一个可行基。
18.将检验数表示为的形式,则求极大值问题时基可行解是最优解的充要条件是。
19.若矩阵B为一可行基,则|B|=0。
20.当最优解中存在为零的基变量时,则线性规划具有多重最优解。
第2章线性规划的对偶理论21.原问题第i个约束是“≤”约束,则对偶变量yi≥0。
22.互为对偶问题,或者同时都有最优解,或者同时都无最优解。
23.原问题有多重解,对偶问题也有多重解。
24.对偶问题有可行解,原问题无可行解,则对偶问题具有无界解。
25.原问题无最优解,则对偶问题无可行解。
26.设X*、Y*分别是的可行解,则有(1)CX*≤Y*b;(2)CX*是w的上界(3)当X*、Y*为最优解时,CX*=Y*b;(4)当CX*=Y*b时,有 Y*Xs+Ys X*=0成立(5)X*为最优解且B是最优基时,则Y*=CBB-1是最优解;(6)松弛变量Ys的检验数是λs,则 X=-λS是基本解,若Ys是最优解,则X=-λS是最优解。
第5章运输与指派问题61.运输问题中用位势法求得的检验数不唯一。