运筹学第一章线性规划及单纯形法

第一章 线性规划及单纯形法目 录线性规划介绍线性规划数学模型线性规划的图解法线性规划的单纯形法问题的提出v 在现有各项资源条件的限制下，如何确定方案，使预期目标达到最优；或为了达到取其目标，确定使资源消耗最少的方案。问题的提出v 例 1 美佳公司计划制造 I， II两种家电产品。已知各制造一件时分别占用的设备 A、 B的台时、调试时间及 A、 B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表 1-1所示。问该公司应制造 A、 B两种家电各多少件，使获取的利润为最大。例 2、生产计划问题A B 备用资源煤 1 2 30劳动日 3 2 60仓库 0 2 24利润 40 50x1 + 2x2 30 3x1 + 2x2 602x2 24x1， x2 0max Z= 40x1 +50x2解 :设产品 A, B产量分别为变量 x1 ， x2问题的提出例 3：捷运公司拟在下一年度的 1-4月的 4个月内需租用仓库堆放物资，已知各月所需仓库面积如表 1-2。仓库租借费用随合同期限而定，合同期越长，折扣越大，具体见表 1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积数和期限。该厂可在任何一月办理租借合同，每次办理一份或若干份均可。为使租借费用最小，公司应如何选择签订合同的最优决策？月份 1 2 3 4所需 仓库 面 积15 10 20 12合同租借期限1个月 2个月 3个月 4个月合同期内的租 费2800 4500 6000 7300例 4求：最低成本的原料混合方案原料 A B 每单位成本1 4 1 0 22 6 1 2 5 3 1 7 1 64 2 5 3 8每单位添加剂中维生 12 14 8 素最低含量解：设每单位添加剂中原料 i的用量为 xi(i =1,2,3,4)minZ= 2x1 + 5x2 +6x3+8x44x1 + 6x2 + x3+2x4 12x1 + x2 +7x3+5x4 142x2 + x3+3x4 8xi 0 (i =1, 4)补充作业、运输问题从仓库到工厂运送单位原材料的成本，工厂对原材料的需求量，仓库目前库存分别如表所示，求成本最低的运输方案。工厂 仓库 1 2 3 库存1 2 1 3 502 2 2 4 303 3 4 2 10需求 40 15 35设 xij为 i 仓库运到 j工厂的原棉数量 (i 1， 2， 3， j 1， 2， 3)minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33x11 +x12+x13 50x21+x22+x23 30x31+x32+x33 10x11 +x21+x31 = 40x12 +x22+x32 = 15x13 +x23+x33 = 35xij 0一、线性规划模型特点决策变量：向量 (x1 xn)T 决策人要考虑和控制的因素非负约束条件：线性等式或不等式目标函数： Z=(x1 xn) 线性式，求 Z极大或极小线性规划介绍二、线性规划解决的管理问题 ：1. 合理利用线材问题；2. 配料问题；3. 投资问题；4. 产品生产计划；5. 劳动力安排；6. 运输问题。线性规划介绍1. 要求达到某些数量上的最大化或最小化；2. 在一定的约束条件下追求其目标。三、线性规划问题的共同点 ：线性规划介绍线性规划的数学模型一、线性规划数学模型的一般形式二、线性规划数学模型的标准形式用数学语言描述目标函数约束条件解：用变量 x1和 x2分别表示美佳公司制造家电 I和 II的数量。线性规划的一般式max(min)Z=C1x1+ C2x2+ Cnxna11x1+ a12x2+ a 1nxn (=, )b1a21x1+ a22x2+ a 2nxn (=, )b2 am1x1+ am2x2+ amnxn (=, )bmxj 0(j=1,n )19简写为：用矩阵和向量形式表示：线性规划标准形式线性规划的标准形式目标函数： max约束条件 ： =变量符号 ： 0（一） 一般式（二） 矩阵式（三） 向量式返回线性规划标准型的几种表示法(一 ) 一般型MaxZ=C1X1+ C2X2+ CnXna11X1+ a12X2+ a 1nXn =b1a21X1+ a22X2+ a 2nXn =b2 am1X1+ am2X2+ amnXn =bmXj 0(j=1,2,n )其中 bi 0 (i=1,2,m ) 返回(二 ) 矩阵型maxZ=CXAX=bX 0 P1 P2 Pna11 a12 a 1n其中 A= a21 a22 a2nam1 am2 amnX1 X= X2XnC=(C1 C2 Cn )b1 b= b2bm返回(三 ) 向量型X1AX=(P1 P2 Pn ) X2 = bXn P1 X1+ P2 X2 + + Pn Xn=b 返回(四 ) 化标准型1. 约束条件3. 变量2. 目标函数返回 4. 右端项系数1. 约束条件x3为松弛变量x4为剩余变量松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。当 约束条件为 “”时，当 约束条件为 “”时，例 1 maxZ=2X1+ X2 +0X3 +0X4+0X55x2 15 6x1 + 2x2 24x1 + x2 5xi 0+X3 =15+X4 =24+X5 = 5 松弛变量例 2minZ=2X1+ 5X2+6X