文档介绍:线性规划问题线性规划问题第一节第一节线性规划问题的数学模型线性规划问题的数学模型(一)引言(一)引言线性规划是运筹学的重要分支之一,也是研究较早、发展较快、应用较广线性规划是运筹学的重要分支之一,也是研究较早、发展较快、应用较广而且比较成熟的一个分支。自而且比较成熟的一个分支。自 1947 1947 年线性规划被成功的运用于工业、交通、年线性规划被成功的运用于工业、交通、农业和军事等各个领域后,现在它已成为管理科学的重要基础和手段之一。农业和军事等各个领域后,现在它已成为管理科学的重要基础和手段之一。随着计算机的普及,它的适应领域越来越广泛。随着计算机的普及,它的适应领域越来越广泛。线性规划研究的问题主要有两类:一是一项任务确定后,如何统筹安排, 线性规划研究的问题主要有两类:一是一项任务确定后,如何统筹安排, 尽量作到用最少的人力物力资源去完成这一任务。二是已有一定数量的人力尽量作到用最少的人力物力资源去完成这一任务。二是已有一定数量的人力物力资源,如何安排使用他们,使得完成任务最多。其实这两类问题是一个物力资源,如何安排使用他们,使得完成任务最多。其实这两类问题是一个问题的两个方面,就是所谓寻求整个问题的某个整体指标最优的问题问题的两个方面,就是所谓寻求整个问题的某个整体指标最优的问题。。 1. 2. 3. 4. 5. 6. (二)线性规划问题的数学模型(二)线性规划问题的数学模型 1 1. . 运输问题运输问题设有两个砖厂设有两个砖厂 A A 1 1、、A A 2 2。。其产量分别为其产量分别为 23 23万块与万块与 27 27万块。它万块。它们生产的供应们生产的供应 B B 1 1、、B B 2 2、、B B 3 3三个工地。其需要量分别为三个工地。其需要量分别为 17 17万块、万块、 18 18 万块和万块和 15 15万块。自各产地到各工地的运价格如下表:问应如何万块。自各产地到各工地的运价格如下表:问应如何调运,才使总运费最省。调运,才使总运费最省。 160 160 110 110 60 60 A A 2 2 70 70 60 60 50 50 A A 1 1B B 3 3B B 2 2B B 1 1运价运价工地工地砖厂砖厂解解:设 x i j表示由砖厂A i 运往工地 B j砖的数量( i=1,2 ; j=1,2,3) 50 50 15 15 18 18 17 17 收收量量 27 27 x x 23 23x x 22 22x x 21 21 A A 2 2 23 23 x x 13 13x x 12 12x x 11 11 A A 1 1发量发量 B B 3 3B B 2 2B B 1 1 运量运量工工地地砖厂砖厂目标函数目标函数约束条件约束条件 11 12 13 21 22 23 min 50 60 70 60 110 160 S x x x x x x ? ????? 11 12 13 21 22 23 11 21 12 22 13 31 23 27 17 18 15 0 ( 1, 2; 1, 2, 3) ij x x x x x x x x x x x x x i j ? ????? ????? ???? ???? ??? ???? 2. A A 、、B B两种产品,现有资源数、生产每单位产品所需原两种产品,现有资源数、生产每单位产品所需原材料数以及每单位产品可得利润如下表所示。问如何制定生产计划使两材料数以及每单位产品可得利润如下表所示。问如何制定生产计划使两种产品总利润最大种产品总利润最大? ? 单位产品产品耗用资源资源 A(公斤) B(公斤) 现有资源铜(吨) 94360 电力(千瓦) 45200 劳动日(个) 310300 单位利润(万元/公斤) 712 解解: :假设生产 A产品 x 1公斤, B产品 x 2公斤, x 1,x 2称为决策变量,简称变量。得到利润 7 x 1 +12 x 2万元, 这一问题的数学模型为: 约束条件约束条件 1 2 max 7 12 S x x ? ? 1 2 1 2 1 2 9 4 3 6 0 4 5 2 0 0 3 1 0 3 0 0 0