下载文档原格式
运筹管理M B A运筹学讲义集团标准化工作小组 #Q8QGGQT-GX8G08Q8-GNQGJ8-MHHGN#MBA运筹学讲义运筹学是一门应用科学，它广泛应用现代科学技术知识、用定量分析的方法，解决实际中提出的问题，为决策者选择最优决策提供定量依据。
运筹学的核心思想是建立在优化的基础上。
例如，在线性规划中体现为两方面：（1）对于给定的一项任务，如何统筹安排，使以最少的资源消耗去完成（2）在给定的一定数量的资源条件下，如何合理安排，使完成的任务最多运筹学解决问题的主要方法是用数学模型描述现实中提出的决策问题，用数学方法对模型进行求解，并对解的结果进行分析，为决策提供科学依据。
随着计算机及计算技术的迅猛发展，目前对运筹学的数学模型的求解已有相应的软件。
因此，在实际求解计算时常可借助于软件在计算机上进行，这样可以节省大量的人力和时间。
第一部分线性规划内容框架LP问题基本概念数学模型可行解、最优解LP问题解的概念基本解、基可行解提出基本最优解基本方法图解法原始单纯形法单纯形法大M法人工变量法对偶单纯形法两阶段法对偶理论进一步讨论灵敏度分析──参数规划*在经济管理领域内应用运输问题（转运问题）特殊的LP问题整数规划多目标LP问题*第一部分线性规划（Linear Programming）及其应用第一章 LP问题的数学模型与求解§1 LP问题及其数学模型（一）引例1（生产计划的问题）某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获的利润如下表所示。
问应如何安排计划使该工厂获利最多该问题可用一句话来描述，即在有限资源的条件下，求使利润最大的生产计划方案。
解：设x1,x2分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。
由于资源的限制，所以有：机器设备的限制条件：x1+2x2≤8原材料A的限制条件： 4x1≤16 （称为资源约束条件）原材料B的限制条件： 4x2≤12同时，产品Ⅰ、Ⅱ的产量不能是负数，所以有x 1≥0，x2≥0 （称为变量的非负约束）显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。
运筹学课程讲义第一部分线性规划第一章线性规划的基本性质1.1 线性规划的数学模型一、线性规划问题的特点胜利家具厂生产桌子和椅子两种家具。
桌子售价50 元/个，椅子售价30 元/个。
生产桌子和椅子需木工和油漆工两种工种。
生产一个桌子需要木工4 小时，油漆工2小时。
生产一个椅子需要木工3 小时，油漆工1 小时。
该厂每月可用木工工时为120 小时，油漆工工时为50 小时。
问该厂如何组织生产才能使每月的销售收入最大？max z 50x1 30x24x1 3x2 1202x1 x2 50x1,x2 0 例：某工厂生产某一种型号的机床。
每台机床上需要 2.9m、2.1m、1.5m的轴，分别为1根、2根和1根。
这些轴需用同一种圆钢制作，圆钢的长度为74m。
如果要生产100台机床，问应如何安排下料，才能用料最省？二、数学模型的标准型1. 繁写形式2. 缩写形式3. 向量形式4. 矩阵形式若原模型中变量 x j 有上下界，如何化为非负变量？三、 任一模型如何化为标准型？1. 若原模型要求目标函数实现最大化，如何将其化为最小化问题？2. 若原模型中约束条件为不等式，如何化为等式？3. 若原模型中变量 x k 是自由变量，如何化为非负变量？1. 2 图解法该法简单直观，平面作图适于求解二维问题。
使用该法求解线性规划问题时，不必把原模型化为标准型。
一、 图解法步骤1. 由全部约束条件作图求出可行域2. 作出一条目标函数的等值线3. 平移目标函数等值线，作图求解最优点，再算出最优值 max z 5x 1 6x 2 7x 3x 1 5x 23x 3 15 5x 1 6x 210x 3 20 x 1 x 2 x 3 5x 1 0,x 2 0,x 3无约束令 x 1' x 1,x 3 x 3' x 3'',x 3' ,x 3'' 0, Z 1Z ' 1 1 min z ' 5x 1' 6x 2 7x 3' 7x 3'' 0x 5 Mx 6 1 x 1' 5x 2 1 11 3x 3' 3x 3'' x 4 x 6 15 1 5x 1' 6x 2 10x 3' 10x 3'' x 5 20 1 x ' x 1 ' II '' 54.Mx 7 x 1, x 2 , x 3, x 3, x 4 , x 5 ,x 6, x 7 0从图解法看线性规划问题解的几种情况1. 有唯一最优解2. 有无穷多组最优解3. 无可行解4. 无有限最优解（无界解）min z 6x1 4x?2x〔X2 13 最优解（1,0），最优值33x14x2 22x1, x20直观结论：1）线性规划问题的可行域为凸集，特殊情况下为无界域（但有有限个顶点）或空集；2）线性规划问题若有最优解，一定可以在其可行域的顶点上得到。
运筹学基本概念➢线性规划问题的基与解LP： max(min)z=CX （1-1）s.t AX=b （1-2）X>=0 （1-3）设A施m*n矩阵，且A的秩为m，则有●可行解：满足上述约束条件（1-2）、（1-3）的向量X称为可行解。
●最优解：满足式（1-1）的可行解称为最优解●基：A中任何一组m个线性无关的列向量构成的子矩阵B，称为该问题的一个基，即B为A的m*m非奇异子矩阵。
●基向量：基B中的一列即为B的一个基向量。
基B中公寓m个基向量●非基向量：矩阵A中基B之外的一列即为B的一个非基向量。
A中共有n-m个非基向量。
●基变量：与基B的基向量相应的变量恒伟B的基变量，基变量共有m个。
●非基变量：与基B非基向量相应的变量称为B的非基变量，非基变量共有n-m个。
●基本解：对于基B，令所有非基变量为零，求得满足式（1-2）的解，称为B对应的基本解。
●基本可行解：满足式（1-3）的基本解称为基本可行解，其对应的基称为可行基。
●基本最优解：满足式（1-1）的基本可行解称为基本最优解，其对应的基称为最优基。
●退化的基本解：若基本解中有基变量为零这，则称之为退化的基本解。
类似地，有退化的基本可行解和退化的基本最优解。
➢几何意义上的几个基本概念●凸集：设S是n维空间的一个点集，若任意两点X（1）、X(2) ∈S的所连线段上的一切点αX（1）+（1-α）X(2)，（0<=α<=1），则称S为凸集。
●凸组合：设X（1）、X(2)……X（K）,为n维空间中的k个点。
则X=μ1X（1）+μ2X(2)+ μkX（K）（0<=μi<=1，i=1,2……k,且μ1+……μk=1）称为X（1）、X(2)……X（K）的凸组合。
●极点：S是凸集，X∈S，若X不能用S中相异的两点X（1）、X(2)线性表示为：X=αX（1）+（1-α）X(2)，α∈（0,1），则称X为S的极点或定点。
即极点不能成为任何线段的内点。
