第1章线性规划 线性规划是运筹学的一个十分重要的分支,自1949年丹捷格提出了求解线性规划 问题的单纯形法后,线性规划的应用日趋增多,现国内外盛行。 线性规划所解决的问题主要分为两类:一类是在资源(人力、物力、财力…) 定的情况下,我们如何利用这些有限的资源来完成最多的任务。另一类是在任务确定的 情况下,我们如何利用最小的资源完成这个确定的任务。 要用线性规划解决一个实际问题,一般来说,都需要首先根据待要解决的问题,建 立线性规划的数学模型,其次对已得模型利用计算机求解,得出优解,再施于实践。故 此,这里我们首先考虑线性规划的数学模型 1.1线性规划的数学模型 建模是解决线性规划问题的极为重要的一个环节,一个正确数模(数学模型)的建 立,要求建模者熟悉问题的生产情况和管理内容,明确目的要求和错综复杂的已知与未 知条件,以及它们之间二者相互关系,而一些已知数据还要通过大量的调查和统计资料 获取可靠的原始数据加以证实。对初学者来说,要求我们怎样从问题的内容出发,分析 和认识问题,善于从数学的角度有条理的表述出来,掌握建模的分析问题的步骤及方法 一般来说,一个待建模的线性规划问题需满足以下条件,方可入手 1)所求问题的目标一定能表示为最大化或最小化问题,例如,求最小成本或人 力投资等,材料储备的最大利用,企业的最大利润等问题。 (2)问题一定要具备有达到目标的不同方法,即必须要有选择的可能性 (3)要达到的目标是有限制条件的 (4)问题的目标和约束都能表示为线性式 以下我们将通过几个实例来说明建模的思路及线性规划在实际问题中的应用,并随 之引出线性规划的标准模型 1.1.1线性规划问题举例 例1.1(资源利用问题)设某建筑公司的预制厂利用沙,石,灰三种原料A1,A2, A3,来生产两种产品B1和B2,已知该厂各种原料的现有数量,每单位产品对各种原料 的消耗量及所获利润如下表1-1所示。 现在的问题是,在这些现有的资源条件下,如何分配产品B1,B2的生产,才使公 司取得利润最大
第 1 章 线性规划 线性规划是运筹学的一个十分重要的分支，自 1949 年丹捷格提出了求解线性规划 问题的单纯形法后，线性规划的应用日趋增多，现国内外盛行。 线性规划所解决的问题主要分为两类：一类是在资源（人力、物力、财力……）一 定的情况下，我们如何利用这些有限的资源来完成最多的任务。另一类是在任务确定的 情况下，我们如何利用最小的资源完成这个确定的任务。 要用线性规划解决一个实际问题，一般来说，都需要首先根据待要解决的问题，建 立线性规划的数学模型，其次对已得模型利用计算机求解，得出优解，再施于实践。故 此，这里我们首先考虑线性规划的数学模型。 1.1 线性规划的数学模型 建模是解决线性规划问题的极为重要的一个环节，一个正确数模（数学模型）的建 立，要求建模者熟悉问题的生产情况和管理内容，明确目的要求和错综复杂的已知与未 知条件，以及它们之间二者相互关系，而一些已知数据还要通过大量的调查和统计资料 获取可靠的原始数据加以证实。对初学者来说，要求我们怎样从问题的内容出发，分析 和认识问题，善于从数学的角度有条理的表述出来，掌握建模的分析问题的步骤及方法。 一般来说，一个待建模的线性规划问题需满足以下条件，方可入手。 （1）所求问题的目标一定能表示为最大化或最小化问题，例如，求最小成本或人 力投资等，材料储备的最大利用，企业的最大利润等问题。 （2）问题一定要具备有达到目标的不同方法，即必须要有选择的可能性。 （3）要达到的目标是有限制条件的。 （4）问题的目标和约束都能表示为线性式。 以下我们将通过几个实例来说明建模的思路及线性规划在实际问题中的应用，并随 之引出线性规划的标准模型。 1.1.1 线性规划问题举例 例 1.1 （资源利用问题）设某建筑公司的预制厂利用沙，石，灰三种原料 A1，A2， A3，来生产两种产品 B1 和 B2，已知该厂各种原料的现有数量，每单位产品对各种原料 的消耗量及所获利润如下表 1-1 所示。 现在的问题是，在这些现有的资源条件下，如何分配产品 B1，B2 的生产，才使公 司取得利润最大
表1-1 位 品 B1B2原料现有数(M2) 消 原料 2 单位利润(百元) 54 分析:1.确定未知变量,设x表示B的生产数量,x2为产品B的生产数量。 2.因为所求问题的目标是要求公司取得最大利润,所以,设利润函数为fx, 则∫(x)=5x+4x2(百元)。 3.问题的约束资源限制为各种原料的现有数,所以,有关系式: 2x1+x,≤8 x2≥0 归纳1,2,3式得出该问题为 求满足 +3x,≤90 x2≤ x1+x,≤45 ≥0 并使∫(x)=5x+4x2最大的一组数(x2,x2)。 般的,设用A,A2,…,An种原料,可以生产B1,B2,…,Bn种产品,已知A种原料为a1 单位,B,种单位产品所需A种原料a单位,B,种单位产品的利润为C,元,问应如何组 织生产才能获得最大利润? 解:设x为生产产品B(j=1,2,…m)的计划数,那么这一类问题的数学模型为:求 组变量x(j=1,2,…,n)的值,使它满足 ∑anx≤a1(i=1,2…,m)
表 1-1 B1 B2 原料现有数（ M 2 ） A1 1 3 90 A2 2 1 80 A3 1 1 45 单位利润（百元） 5 4 单 产 位 产 品 品 的 消 原 料 耗 分析：1.确定未知变量，设 x1 表示 B1的生产数量，x2 为产品 B2的生产数量。 2.因为所求问题的目标是要求公司取得最大利润，所以，设利润函数为 f(x)， 则 ( ) 1 2 f x x = + 5 4x 0 0 （百元）。 3.问题的约束资源限制为各种原料的现有数，所以，有关系式： 1 2 1 2 1 2 1 2 3 9 2 8 45 , 0 x x x x x x x x + ≤ + ≤ + ≤ ≥ 归纳 1，2，3 式得出该问题为： 求满足 1 2 1 2 1 2 1 2 3 9 2 8 45 , 0 x x x x x x x x 0 0 + ≤ + ≤ + ≤ ≥ 并使 ( ) 1 5 4 2 f x x = + x 最大的一组数( 1 2 , ) T x x 。 一般的，设用 A A 1 2 , ,", Am 种原料，可以生产 1 2 , , , B B " Bn 种产品，已知 种原料为 单位， Ai i a Bj 种单位产品所需 Ai 种原料aij 单位，Bj 种单位产品的利润为C 元，问应如何组 织生产才能获得最大利润？ j 解：设 j x 为生产产品 ( 1, 2, , Bj j = " ) ) n 的计划数，那么这一类问题的数学模型为：求 一组变量 ( 1, 2, , j x j = " n 的值，使它满足 ( ) 1 1, 2, , n ij j i j a x a i m = ∑ ≤ = " 0 1 ( ) , 2, , j x ≥ =j n
并使利润函数f(x)=∑Cx,的值最大 例1.2(物资调运问题) 设有两个砖厂A,A2变量分别为23万和27万块砖,它的产品供应B1,B2,B3三个工 地,需要量分别为17万块、18万块和15万块,已知从A,A,分别向B1,B2,B3运送1万 块砖需要的运费如表1-2所示。 运价表(单位:万块) 1-2 运价工地 B B 砖厂 60 110 160 问如何调运才使的总运费最小? 解:设x表示有砖厂4运往工地B,的砖的数量(单位:万块)(=1,2,j=1,2,3) 因为,由砖厂A运往三个工地的砖数总和应等于A的产量,从而有约束式 x1+x2+x13=23 x20(=12j=123) 又因为由A,A2,两个砖厂运到各地的砖数总和应等于各工地的需求量,所以又得约 束式: x1;+x xn≥0(=1,2j=12,3) 于是,该运输问题归结为: 求一组满足条件 23 x1+x21= 18 x20(=12,j=123) 并使∫(x)=50x1+60x2+70x3+60x2+110x2+160x23最小的x(i=1,2j=1,2,3) 般的,设某种物资有m个产地:A1,A2,…,A联合供应n个销地:B1,B2,…,Bn
并使利润函数 ( ) 1 n j j j f x C= = ∑ x , 的值最大。 例 1.2 （物资调运问题） 设有两个砖厂 A A 1, 2 变量分别为 23 万和 27 万块砖，它的产品供应 1 2 3 B , , B B 1 2 3 , , 三个工 地，需要量分别为 17 万块、18 万块和 15 万块，已知从 A A 1, 2 , 分别向 B B B 运送 1 万 块砖需要的运费如表 1-2 所示。 运价表（单位：万块） 表 1-2 运价 工地 砖厂 B1 B2 B3 A1 50 60 70 A2 60 110 160 问如何调运才使的总运费最小? 解：设 ij x 表示有砖厂 Ai 运往工地 B j 的砖的数量（单位：万块）（i j =1,2; =1,2,3） 因为，由砖厂 Ai 运往三个工地的砖数总和应等于 Ai 的产量，从而有约束式： ( ) 11 12 13 21 22 23 23 27 0 1, 2; 1, 2,3 ij x x x x x x x i j + + = + + = ≥ = = 又因为由 两个砖厂运到各地的砖数总和应等于各工地的需求量，所以又得约 束式： 1 2 A A, , ( ) 11 21 12 22 13 23 17 18 15 0 1,2; 1,2,3 ij x x x x x x x i j + = + = + = ≥ = = 于是，该运输问题归结为： 求一组满足条件: ( ) 11 12 13 21 22 23 11 21 12 22 13 23 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 + + = + + = + = + = + = ≥ = = 并使 ( ) 11 12 13 21 22 23 f x x = + 50 60x + + 70x 60x +110x +160x 最小的 ij x （i j =1,2; =1,2,3）。 一般的，设某种物资有 m 个产地： A A 1 2 , ,", Am 联合供应 n 个销地： 1 2 , , , B B B " n
各产地产量(单位:吨),各销地销量(单位:吨),各产地至各销地单位运价(单位: 元/吨)如表1-3所示。 表1-3 单价(元/吨) 销地 BB2…Bn产量(吨) C A2 销量(吨) bb b 表中:a表示产地的产量A的产量(=1,2,…,m) b表示销地B的销量(=12…n) C表示A到B间的单位运价(元吨)(=12…,mj=12…,m)。问应如何调运 才能使总运费最小? 解:当产销平衡(即∑a=∑h)时,设x表示由产地4运往销地B的物资数 (=1,2,…,m,j=12…,n) 那么,上述运输问题的数学模型为: 求一组变量x(1=12.…m,j=1,2,…nm)的值,使它满足约束条件 x1+x12+……+x1n=41 x21+x2+…+x2n=a xml+?+ x1+x21+…+xm!= b x=b xn+x2n+…+xm=bn x20(=12, 并使目标函数f(x)=C1x1+C1x2+…+Cmxm的值最小 利用连加号(∑),这一数学模型可以写为 求一组变量的值x(i=12,…,mj=12…,n),使它满足
各产地产量（单位：吨），各销地销量（单位：吨），各产地至各销地单位运价（单位： 元/吨）如表 1-3 所示。 表 1-3 单价（元/吨） 销地 产地 B1 2 B " Bn 产量（吨） m A A A 1 2 # n n m m m C C C C C C C C C 11 12 1 21 22 2 1 2 " " # # " # " n m a a a 1 2 # 销量（吨） n b b 1 2 " b 表中：ai 表示产地的产量 Ai 的产量(i m =1, 2,", ) j b 表示销地 Bj 的销量( ) j n =1, 2,", Cij 表示 Ai 到 Bj 间的单位运价（元/吨）(i m =1, 2,", ; j =1, 2,", n) i b 。问应如何调运， 才能使总运费最小？ 解：当产销平衡（即 ∑ ）时，设 1 1 m n i i i a = = = ∑ ij x 表示由产地 Ai 运往销地 Bj 的物资数 ( ) i m =1, 2," " , ; j =1, 2, , n 。 那么，上述运输问题的数学模型为： 求一组变量 ij x (i m =1, 2,", ; j =1, 2,", n) 的值，使它满足约束条件： ( ) 11 12 1 1 21 22 2 2 1 2 11 21 1 1 12 22 2 2 1 2 0 1, 2, , ; 1, 2, , n n m m mn m m m n n mn n ij x x x a x x x a x x x a x x x b x x x b x x x b x i m j + + + = + + + = + + + = + + + = + + + = + + + = ≥ = = " " """""""""" " " " """""""""" " " " n 并使目标函数 ( ) 11 11 12 12 mn mn f x C= + x C x +"+C x 的值最小。 利用连加号（∑），这一数学模型可以写为： 求一组变量的值 ij x ( ) i m =1, 2,", ; j =1, 2,",n ，使它满足
x=a1(=12 b, c ≥0(i=1,2,…,m,j=1,2,…,m) 并且使目标函数f(x)=∑∑Cx的值最小。 如果运输问题中,没有产销平衡这一限制,当产大于销时(即∑a>∑b,这一问 题的数学模型应为 求一组变量x(1=12…,m,j=12,…nm)的值,使它满足 xn≤a1(=1, (产地A发到各销地得发量总合不超过A的产量) x=b,(=1,2,…,n) (各产地发到销地B,的发量总合应等于B的产量) x≥0(=12,…mj=12,…m)(调运量不能取负值) 并且使目标函数f(x)=∑∑Cx的值最小 例1.3(节约下料问题) 设有一批规格为10米长的圆钢筋,将它截成分别为3米,4米长的预制构件的短钢 筋各100根,问怎样截取最省料。 解:因为,10米长的钢筋截为3米或4米长,共有三种截法 截法I:3331米 截法Ⅱ:3340米 截法Ⅲ:4402米 所以,设按截法Ⅰ,Ⅲ,Ⅲ各截取10米长的钢筋分别为x1,x2x3根, 则该问题归纳为:求满足约束条件
1 1 ( 1, 2, , ) ( 1, 2, , ) 0( 1, 2, , ; 1, 2, , ) n ij i j m ij j i ij x a i m x b j n x i m j = = = = = = ≥ = = ∑ ∑ " " " " n 并且使目标函数 ( ) 1 1 n m ij ij j i f x C = = = ∑∑ x j b 的值最小。 如果运输问题中，没有产销平衡这一限制，当产大于销时（即 1 1 m n i i j a = = ∑ > ∑ ），这一问 题的数学模型应为： 求一组变量 ij x ( ) i m =1, 2,", ; j =1, 2,",n ) 的值，使它满足 1 ( 1, 2, , n ij i j x a i m = ∑ ≤ = " （产地 Ai 发到各销地得发量总合不超过 Ai 的产量） 1 ( 1,2, , m ij j i x b j n) = ∑ = = " （各产地发到销地 Bj 的发量总合应等于 Bj 的产量） ij x ≥ 0 (i m =1, 2,", ; j =1, 2,", n) （调运量不能取负值） 并且使目标函数 ( ) 1 1 n m ij ij j i f x C = = = ∑∑ x 的值最小。 例 1.3 （节约下料问题） 设有一批规格为 10 米长的圆钢筋，将它截成分别为 3 米，4 米长的预制构件的短钢 筋各 100 根，问怎样截取最省料。 解：因为，10 米长的钢筋截为 3 米或 4 米长，共有三种截法： 截法Ⅰ：3 3 3 1 米 截法Ⅱ：3 3 4 0 米 截法Ⅲ：4 4 0 2 米 所以，设按截法Ⅰ，Ⅱ，Ⅲ各截取 10 米长的钢筋分别为 x , , x x 1 2 3根， 则该问题归纳为：求满足约束条件