第1章-线性规划模型-宋.docxVIP

第一章线性规划模型 线性规划（Linear Programming ）是数学规划的一个重要组成部分，是最优化与运筹学理 论中的一个重要分支和常用的方法，是最优化理论的基础性内容。 第一节线性规划问题及其数学模型 一、问题的提出 在生产管理和经营活动中经常提出一类问题， 即如何利用有限的人力、物力、财力等资源， 以便得到最好的经济效果。 例1生产计划问题 某工厂在计划期内要安排生产I、□的两种产品，已知生产单位产品所需的设备台时， A、 B两种原材料的消耗以及每件产品可获得的利润如下表所示。问应如何安排生产计划使该工厂 获利最多？ I n 资源限量 设备 1 2 8（台时） 原材料A 4 0 16(kg) 原材料B 0 4 12(kg) 单位产品利润（元） 2 3 解：设Xi,X2分别表示在计划期内生产产品I、II的产量。由于资源的限制，所以有: 机器设备的限制条件：x1 2x2 8 4xi 16 （称为资源约束条件） 4xi 16 （称为资源约束条件） 4x2 12 Xi 0, x2 0 （称为变量的非负约束） 原材料B的限制条件: 同时，产品I、II的产量不能是负数，所以有 显然，在满足上述约束条件下的变量取值，均能构成可行方案，且有许许多多。而工厂的 目标是在不超过所有资源限量的条件下，如何确定产量 xi,x2以得到最大的利润，即使目标函 数z 2为3x2的值达到最大。 综上所述，该生产计划安排问题可用以下数学模型表示： max z 2为 3x2 x, 2x2 8 s.t4x 16 s.t 4x2 12 x1,x2 0 例2运输问题 某公司经销某种产品，三个产地和四个销地的产量、销量、单位运价如下表所示。问在保 证产销平衡的条件下，如何调运可使总运费最少？ 销地 价、、 B1 B2 B3 B4 A1 5 6 10 3 60 A2 4 1 9 7 40 A3 4 2 3 8 60 销量 30 50 40 40 解：(1)决策变量：设Xj(i 1,2,3; j 1,2,3, 4)为从产地i运到销地j的运量 目标函数：总运费最小约束条件：产量约束 目标函数：总运费最小 约束条件： 产量约束 销量约束 非负约束 模型为： min s.t 3 4 min z qXj i 1 j 1 X11 X12 :X13 X14 60 X21 X22 :X23 i X24 .40 X31 X32 :X33 i X34 60 X11 X21 X31 30 X12 X22 X32 50 X13 X23 X33 40 X14 X24 X34 40 Xj 0 3 4 z c X ^ij ij i 1 j 1 X11 X12 X13 X14 60 X21 X22 X23 X24 40 X31 X32 X33 X34 60 X11 X21 X31 30 X12 X22 X32 50 X13 X23 X33 40 X14 X24 X34 40 Xij 0(i 1,2, 3 j 1,2,3,4) 、线性规划问题的模型 上述几例所提出的问题，可归结为在变量满足线性约束条件下，求使线性目标函数值最大 或最小的问题。它们具有以下共同的特征。 每个问题都可用一组决策变量 (Xi,X2,L ,Xn)表示某一方案，其具体的值就代表一个具体 方案。通常可根据决策变量所代表的事物特点，对变量的取值加以约束，如非负约束。 存在一组线性等式或不等式的约束条件。 都有一个用决策变量的线性函数作为决策目标(即目标函数) ，按问题的不同，要求目标 函数实现最大化或最小化。 满足以上三个条件的数学模型称为线性规划( LP)问题的数学模型，其一般形式为： max(或 min) z c1x c2x2 L cnxn 咐2 a12X2 ai (， a21X2 s.t a22X2 a2nXn (， ，)b2 或矩阵形式 am〔X2 am2X2 Xi,X2, amnXn ,Xn 0 ( ,)bm max(或 min)z CX s.tAX ()b s.t AX ( )b 或向量形式 max (或 min ) z CX n PjXj ( , )b s.t j 1 Xj 0 (j 1,2,...,n) 其中C (c1,c2,L ,cn),称为价值系数向量; 称为技术系数矩阵(也称消耗系数矩阵)；b 称为技术系数矩阵(也称消耗系数矩阵)；b (b1,b2,L ,bm)T称为资源限制向量； a11 l a1n a21 a22 l a2n l l am1 am2 l amn X (Xi,X2,L , Xn )称为决策变量向量。 三、建立线性规划模型的一般步骤: 确定决策变量; 确定目标函数; 确定约束条件。 例3投资计划问题 某公司经调研分析知，在今后三年内有四种投资机会。第I种方案是在三年内每年年初投 资