工商管理专业基础课运 筹 学

《工商管理专业基础课运 筹 学》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、工商管理专业基础课运筹学主讲人：刘舒燕武汉理工大学管理学院工商管理系第一部分线性规划（LinearProgramming，简称LP）线性规划的发展1939年，前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题1947年，Dantzig提出求解线性规划的单纯形法1950-1956年，主要研究线性规划的对偶理论1958年，发表整数规划的割平面法1960年，Dantzig和Wolfe研究成功分解算法，奠定了大规模线性规划问题理论和算法的基础。1979年，Khachiyan，1984年，Karmarkaa研究成功线性规划的多项式算法。线性规划研究的主

2、要问题一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。——实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（max或min）。另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。第一章线性规划基础例1.1某厂生产两种产品，下表给出了单位产品所需资源及单位产品利润问：应如何安排生产计划，才能使总利润最大？§1.1线性规划的基本概念一、问题的提出解：1.决策变量：设产品I、II的产量分别为x1、x22.目标函数：设总运费为z，则有：maxz=2x1+3x2

3、3.约束条件：x1+2x2≤84x1≤164x2≤12x1，x2≥0例1.2某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。解：1.决策变量：设四种原料的使用量分别为：x1、x2、x3、x42.目标函数：设总成本为z，则有：minz=5x1+6x2+7x3+8x43.约束条件：x1+2x2+x3+x4≥1602x1+4x3+2x4＝1603x1＋x2+x3+2x4≤180x1、x2、x3、x4≥0药物原料ABC单

4、位成本（元／吨）甲1235乙2016丙1417丁1228二、数学模型1.决策变量：X=(x1,x2,…..,xn)T2.目标函数：max(minz)=c1x1+c2x2+…….+cnxn3.约束条件：a11x1+a12x2+……..+a1nxn≤(=≥)b1a21x1+a22x2+……..+a2nxn≤(=≥)b2…………………………………………am1x1+am2x2+……..+amnxn≤(=≥)bmx1,x2,……xn≥0三、模型特点1都用一组决策变量X=(x1,x2,…,xn)T表示某一方案，且决策变量取值非负；———满足以上三个条件的数学模型称

5、为线性规划2都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数；3都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等式来表示。其它形式其中：①求和形式②矩阵形式决策变量常数项系数矩阵价值系数其中：§1.2线性规划数学模型的建立一、建模条件1优化条件：问题所要达到的目标能用线型函数描述，且能够用极值（max或min）来表示；2限定条件：达到目标受到一定的限制，且这些限制能够用决策变量的线性等式或线性不等式表示；3选择条件：有多种可选择的方案供决策者选择，以便找出最优方案。二、建模步骤1确定决策变量：即需要我们作出决策或选择的量。

6、一般情况下，题目问什么就设什么为决策变量。2找出所有限定条件：即决策变量受到的所有的约束；3写出目标函数：即问题所要达到的目标，并明确是max还是min。三、建模案例例1.3某工厂生产A、B两种产品，有关资料如下表所示：设总成本为z，A、B产品销量为x1、x2，产品C的销售量为x3，报废量为x4，则：maxz=4x1+10x2+3x3－2x42x1+3x2≤123x1+4x2≤24－2x2+x3+x4=0x3≤5x1、x2、x3、x4≥0船只种类船只数拖轮30A型驳船34B型驳船52航线号合同货运量12002400航线号船队类型编队形式货运成本（千元／

7、队）货运量（千吨）拖轮A型驳船B型驳船1112—362521—4362023224724041—42720问：应如何编队，才能既完成合同任务，又使总货运成本为最小？例1.4某航运局现有船只种类、数量以及计划期内各条航线的货运量、货运成本如下表所示：解：设：xj为第j号类型船队的队数（j=1，2，3，4），z为总货运成本则：minz=36x1+36x2+72x3+27x4x1+x2+2x3+x4≤302x1+2x3≤344x2+4x3+4x4≤5225x1+20x2＝20040x3+20x4＝400xj≥0j=1,2,3,4用单纯形法可求得：x1=8

8、，x2=0，x3=7，x4=6最优值：z=954即：四种船队类型的队数分别是8、0、7、6，此