下载文档原格式
第一章 线性规划【教学内容】线性规划模型，图解法，可行区域的几何结构，基本可行解及线性规划的基本定理，单 纯形方法，单纯形表，两阶段法，关于单纯形方法的几点说明，对偶线性规划，对偶理论， 对偶单纯形法，求解线性规划问题的几个常用软件。
【教学要求】要求学生理解线性规划的标准形式，能熟练的将一般的线性规划问题化为标准形式；掌 握图解法，能用单纯形法求解线性规划问题；掌握灵敏度分析方法，能够建立线性规划模型 及用常用软件求解线性规划问题。
【教学重点】线性规划模型，图解法，单纯形方法，单纯形表，两阶段法，对偶线性规划，对偶单纯 形法，灵敏度分析。
【教学难点】基本可行解及线性规划的基本定理，单纯形方法，对偶线性规划，对偶理论，对偶单纯 形法。
第一节 线性规划模型线性规划(Linear Programming ， 简记为 LP )问题研究的是在一组线性约束条件下一个线 性函数最优问题。
§1．1 线性规划问题举例例 1.1.1 某工厂用 3 种原料 3 2 1 , , P P P 生产 3 种产品 3 2 1 , , Q Q Q 。
已知单位产品所需原 料数量如表 1.1.1 所示，试制订出利润最大的生产计划。
453 单位产品的利润（千元）20005 2 800 4 2 0 P 2 1500 0 3 2 P 1 原料可用量Q 3Q 2 Q 1 单位产品所需产品原料数量(kg)原料3P 3表 1.1.1分析 设产品 j Q 的产量为 j x 个单位， 3 , 2 , 1 = j ，它们受到一些条件的限制。
首先， 它们不能取负值，即必须有 3 , 2 , 1 , 0 = ³ j x j ；其次，根据题设，三种原料的消耗量分别不 能超过它们的可用量，即它们又必须满足：1223 123 231500 24800 3252000 x x x x x x x +£ ì ï+£ í ï ++£ î我们希望在以上约束条件下，求出 3 2 1 , , x x x ，使总利润 3 2 1 4 5 3 x x x z + + = 达到最大， 故求解该问题的数学模型为：123 12 23 123 max 354 231500 24800 .. 3252000 0,1,2,3j z x x x x x x x s t x x x x j =++ +£ ì ï +£ ï í++£ ï ï ³= î 类似这样的问题非常多。
OPERATIONS RESEARCH运筹学Ⅰ——怎样把事情做到最好第一章绪论♦1.1题解Operations 汉语翻译工作、操作、行动、手术、运算Operations Research日本——运用学港台——作业研究中国大陆——运筹学Operational Research原来名称，意为军事行动研究——历史渊源绪论♦1.2 运筹学的历史早期运筹思想：田忌赛马丁渭修宫沈括运粮Erlang 1917 排队论Harris 1920 存储论Levinson 1930 零售贸易康脱洛维奇1939 LP绪论♦1.2运筹学的历史军事运筹学阶段德军空袭防空系统Blackett运输船编队空袭逃避深水炸弹轰炸机编队绪论♦1.2运筹学的历史管理运筹学阶段战后人员三分:军队、大学、企业大学：课程、专业、硕士、博士企业：美国钢铁联合公司英国国家煤炭局运筹学在中国：50年代中期引入华罗庚推广优选法、统筹法中国邮递员问题、运输问题1.3学科性质▪应用学科▪Morse&Kimball定义：运筹学是为决策机构在对其控制的业务活动进行决策时提供的数量化为基础的科学方法。
▪Churchman定义：运筹学是应用科学的方法、技术和工具，来处理一个系统运行中的问题，使系统控制得到最优的解决方法。
▪中国定义：运筹学是应用分析、试验、量化的方法，对经济管理系统中人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。
1.4定性与定量♦例：店主进货♦两者都是常用的决策方法♦定性是基础，定量是工具，定量为定性服务。
♦定性有主观性也有有效性，定量有科学性也有局限性。
管理科学的发展，定量越来越多。
但定量不可替代定性。
1.5运筹学的模型♦模型：真实事物的模仿，主要因素、相互关系、系统结构。
♦形象模型：如地球仪、沙盘、风洞♦模拟模型：建港口，模拟船只到达。
学生模拟企业管理系统运行。
♦数学模型：用符号或数学工具描述现实系统。
《运筹学基础》串讲讲义课程介绍一、课程性质《运筹学》是计算机、数学和经济管理等近20个专业本科生和专科生的必修课程之一。
《运筹学基础》是全国高等教育自学考试计算机信息管理专业的专业基础课，是一门理论与实际结合的课程。
通过本课程的学习，能够理论联系实际，把书本上的知识可以直接应用到日常生活中去，提高分析和解决问题的能力。
在考试中出现的考题并不难，跨章节的考题很少，但是题量很大，学员在学习的过程中要熟练掌握各章的例题和课后练习题，并提高计算速度。
二、教材的选用自学教材：《运筹学基础》，全国高等教育自学考试指导委员会组编，张学群主编，经济科学出版社 2002年版三、章节体系《计算机体系结构》共11章，可分为三部分：第1章为第一部分，介绍运筹学的基本概念、决策过程的步骤，提出问题、分析问题和解决问题。
第二部分主要内容为预测，即利用以前和现在的资料，应用不同的方法预测将来要发生的事情并做好准备，主要包含：第2章、第3章、第9章和第11章。
第三部分主要内容为优化，即如何利用现有资源，合理安排之后设计可行方案，达到所耗资源最少或获得利润最大的问题，主要包含：第4章、第5章、第6章、第7章、第8章和第10章。
考情分析一、题型与分值从题型与分值来看，本课程共有四种题型模式：单项选择，填空，名词解释和计算，计算又分计算题Ⅰ、计算题Ⅱ、计算题Ⅲ和计算题Ⅳ。
题型与分值情况如下：单选（共15小题，每题1分，共15分）；填空（共10小题，每题1分，共10分）；名词解释（共5小题，每题3分，共15分）；计算题Ⅰ（共3小题，每题5分，共15分）；计算题Ⅱ（共3小题，每题5分，共15分）；计算题Ⅲ（共2小题，每题7分，共14分）；计算题Ⅳ（共2小题，每题8分，共16分）。
二、知识点分布从知识点分布来看，本课程试题覆盖了教材11章的全部内容。
1、单选题：覆盖面最广，15个选择题中每章1—2题，每章都要涉及考察基本知识点，利用排除法很容易拿分，是一个主要的得分点，尽量不丢分。
运筹学讲义《管理运筹学》1、运筹学的工作步骤(1)提出和形成问题．(2)建立模型．(3)求解．(4)解的检验．(5)解的控制．(6)解的实施.2、运筹学模型三种基本形式：(1)形象模型(2)模拟模型(3)符号或数学模型构模的五种方法和思路： (1)直接分析法 (如线性规划)(2)类比法（手机的普及与电视机的普及）(3)数据分析法（如汽车销售量预测模型）(4)试验分析法（销售量与价格之间的关系模型）(5)想定(构想)法（销售与心理）3、如何将线性规划问题的一般形式化为标准形式：1.如果问题是求目标函数的最小值，求min f＝∑Cjxj则可先将目标函数乘（-1），化为求极大值问题，即求 max Z=－f=－∑Cjxj2.如果有某个bk≤0，则可将该等式两边均乘以(－1)，使右端常数项bk=－bk≥03.如果第k个约束条件是∑akjxj≤bk,引入松弛变量sk≥0 , 将它写成∑akjxj+sk＝bk如果第l个约束条件是∑aljxj≥bl则引入剩余变量(也可称为松弛变量)sl≥0，将它写成∑aljxj—sl=bl 且使松弛变量和剩余变量在目标函数中的系数为零。
4.如果对某个变量xj没有非负限制(这种变量称为自由变量或无约束变量)，则引进两个非负变量xj′，xj″，令xj＝xj′－xj″代人目标函数和约束条件中，可将它化为对全部变量都有非负限制的问题。
4、①目标函数为变量的线性函数，约束条件也为变量的线性等式或不等式的模型称之为线性规划。
②如果目标函数是变量的非线性函数，或约束条件中含有变量非线性的等式或不等式的数学模型则称之为非线性规划。
③满足所有约束条件的解称为该线性规划的可行解。
④把使得目标函数值最大(即利润最大)的可行解称为该线性规划的最优解,此目标函数值称为最优目标函数值，简称最优值5、图解法的启示1．最优解：如果某一个线性规划问题有最优解，则一定有一个可行域的顶点对应一个最优解。
（一般为封闭可行域凸集）2．无穷多个最优解：若将上例中的目标函数变为求maxZ=50x1+50x2则代表目标函数的直线平移到最优位置后将和直线x1+x2=300重合。
运筹学课程讲义第一部分 线性规划 第一章 线性规划的基本性质 1.1 线性规划的数学模型一、 线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。
桌子售价50元/个，椅子售价30元/个。
生产桌子和椅子需木工和油漆工两种工种。
生产一个桌子需要木工4小时，油漆工2小时。
生产一个椅子需要木工3小时，油漆工1小时。
该厂每月可用木工工时为120小时，油漆工工时为50小时。
问该厂如何组织生产才能使每月的销售收入最大？213050m ax x x z +=⎪⎩⎪⎨⎧≥≤+≤+0,50212034212121x x x x x x 例：某工厂生产某一种型号的机床。
每台机床上需要 2.9m 、2.1m 、1.5m 的轴，分别为1根、2根和1根。
这些轴需用同一种圆钢制作，圆钢的长度为74m 。
如果要生产100台机床，问应如何安排下料，才能用料最省？二、 数学模型的标准型 1. 繁写形式 2. 缩写形式 3. 向量形式 4. 矩阵形式三、 任一模型如何化为标准型？1. 若原模型要求目标函数实现最大化，如何将其化为最小化问题？2. 若原模型中约束条件为不等式，如何化为等式？3. 若原模型中变量x k 是自由变量，如何化为非负变量？4. 若原模型中变量x j 有上下界，如何化为非负变量？⎪⎪⎩⎪⎪⎨⎧≥≤-=--≤+--≥-+----=无约束321321321321321,0,052010651535765max x x x x x x x x x x x x x x x z 令'''3'3''3'331'1,0,,,Z Z x x x x x x x =-≥-=-=⎪⎪⎩⎪⎪⎨⎧≥-=+-++=+-+-=+-+-+--+-++-=0,,,,,,,5201010651533507765min 7654''3'32'17''3'32'15''3'32'164''3'32'1765''3'32'1'x x x x x x x x x x x x x x x x x x x x x x x x Mx Mx x x x x x z 1. 2图解法该法简单直观，平面作图适于求解二维问题。
4x 1<164x 2 _12a 21X 1 a 22X 2 ... a 2n X n 十，-）b a m1 X 1第一章线性规划的单纯形法§.1线性规划的基本概念建立数学模型：设X i ,X 2分别是生产的件数，则有:maxz = 2x 1 3x 2x 1, x 2 0这里X 1,X 2称为决策变量。
目标函数与约束条件关于决策变量是线 性的称为线性规划线性规划的一般形式:max(min)z yxr c 2x 2 …厲人耳必+%X 2 +...+九人兰（=,a ）ba m2X 2 ・・・ a mn X n - (一, —)bm x ,,x 2,..,x n 一（专0或无约束2. 线性规划的标准形maxz 二C1X1 …Cn X n"a^x, +ai2x2+••• + 印*人=Ra21^ +a22x2+... + a2n x n= b2a m1 为* a m2 X2 * …+ a mn 人=b m捲_ 0,X2_0,...,X n_0特点：目标函数求极大；等式约束；变量非负。
^令c =(G,c2,…,q), X = (X1,X2，…,x n) , A = (a ij )m n，b=(九^,…,b m ) 则线性规划标准形的矩阵表达式为:max z = exAx = bx _0约定：b — 0,m ^ n,秩A=m.如何化标准形：（I）目标函数实现极大化，即min z=cx，令w--z，则m w丸；（II ）约束条件为不等式约束条件为“「不等式，则在约束条件的左端加上一个非负的松弛变量；约束条件为“ 一”不等式，则在约束条件的左端减去一个非负的松弛变量。
（III ）若存在无约束的变量X k，可令X k = Xk - x k，其中x k 一0,x'k- 0.故有 x^ -B 4b 。
由此，得到Ax -b 的一个解例1.将线性规划min z = -捲 2x 2x-i x 2 x 3 _ 2* X i — X ? + X 3 乏 1论Z0,x 2兰0,x 3无约束化为标准形。
