第一章线性规划（linearprogramming）.pdfVIP

第一章 线性规划 （Linear Programming） 线性规划是运筹学中最基本和有代表性的内容，其理论方法体系相对成熟完整，在实际 中有广泛的应用。本章将介绍线性规划的问题与模型建立、模型的解的概念和求解原理、求 解方法、线性规划的对偶理论和灵敏度分析、运输问题以及0-1 规划。 1.1 模型与图解法 1.1.1 线性规划问题及其数学模型 1．线性规划的问题 在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效 益。 例1.1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。有关数据如表1.1 所示： 表 1.1 例1.1 的数据表 产品 资源单耗 甲 乙 资源限量 资源 煤（t ） 9 4 360 电（kW ·h ） 4 5 200 油（t ） 3 10 300 单位产品价格（万元） 7 12 试拟订使总收入最大的生产方案。 2．线性规划的模型 通过线性规划求解该问题，需明确线性规划模型的三要素： （1）决策变量：需决策的量，即待求的未知数； 本例中即甲、乙产品的计划产量，记为x 、x 1 2 （2）目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示； 本例中即总收入，记为z ，则z =7x +12x ，为体现对其追求极大化，在z 的前面冠以极 1 2 大号Max ； （3 ）约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示； 本例中即分别来自资源煤、电、油限量的约束，和产量非负的约束，表示为 9x1 4x2  360 4x 5x  200 s.t. 1 2 (1-1) 3x 10x  300  1 2 x , x  0  1 2 所以，该问题的最终模型为 Maxz  7x 12x 1 2 9x1 4x2  360 s.t.4x1 5x2  200 (1-2) 3x 10x  300  1 2 x , x  0  1