第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根， 则该问题归纳为：求满足约束条件
+2x2=100 +2x3=10 x≥0(=1,2,3) 并使得总钢筋数∫(x)=x+x2+x最小的一组数(x1,x2,x)。 一般的,设用某原材料(条材或板材)下零件A,A2,…,An的毛坯,根据过去经验 在一件原材料上有B1,B2…Bn种不同的下料方式,每种下料方式可得各种毛坯个数及每 种零件需要量如下表1-4所示,问应怎样安排下料方式,使得既得满足需求,用的原料 又小 解:设采用B,种方式下料时,需要的原材料数为x,则这一问题的数学模型为 求一组变量的值x(j=1,2,…,n),使它满足 ∑Cx1≥a(i=1,2…,m) (所下的A零件总数不能低于a) ≥0 并且使目标函数∫(x)=∑x的值最小。 表1-4 各种方式下 下料方式 的零件个数 B B2 B,零件需要量 零件名称 CC A2 C A CC 例1.4(投资计划问题) 个公司制订投资计划问题的关键是在预算范围内,合理选择投资项目,使总的资 金回收额达到最大。 例如,某建筑企业拥有20万资金,拟在今后五年内对下列项目投资。已知: 项目A:从第一年到第四年每年年初需要投资,并于次年末回收本利115% 项目B:第三年年初需要投资,到第五年末能回收本利125%,但规定最大投资不 超过8万元 项目C:第二年初需要投资,到第五年末能回收本利140%,但规定最大投资额不 超过6万元 项目D:五年内每年年初可购买公债或定期储蓄,于当年末归还,并加利息9%
( , , j x x x x x j + = + = ≥ = 1 2 2 3 3 2 100 2 100 0 1 2 3) 并使得总钢筋数 f ( ) x x = + x + x 1 2 3最小的一组数( , , ) T x x x 1 2 3 。 一般的，设用某原材料（条材或板材）下零件 的毛坯，根据过去经验 在一件原材料上有 1 2 , , , A A " Am 1 2 , , , B B " Bn 种不同的下料方式，每种下料方式可得各种毛坯个数及每 种零件需要量如下表 1-4 所示，问应怎样安排下料方式，使得既得满足需求，用的原料 又小。 解：设采用 Bj 种方式下料时，需要的原材料数为 j x ，则这一问题的数学模型为： 求一组变量的值 j x （ j = 1 2, ,", n ），使它满足 ( , , , ) n ij j i j j C x a i m x = ≥ = ≥ ∑ " 1 1 2 0 （所下的 Ai 零件总数不能低于ai ） 并且使目标函数 ( ) n j j f x = = ∑ 1 x 的值最小。 表 1-4 各种方式下 下料方式 的零件个数 零件名称 B1 2 B " Bn 零件需要量 m A A A 1 2 # n n m m C C C C C C C C C 11 12 1 21 22 2 1 2 " " # # " # " mn m a a a 1 2 # 例 1.4 （投资计划问题） 一个公司制订投资计划问题的关键是在预算范围内，合理选择投资项目，使总的资 金回收额达到最大。 例如，某建筑企业拥有 20 万资金，拟在今后五年内对下列项目投资。已知： 项目 A：从第一年到第四年每年年初需要投资，并于次年末回收本利 115%； 项目 B：第三年年初需要投资，到第五年末能回收本利 125%，但规定最大投资不 超过 8 万元； 项目 C：第二年初需要投资，到第五年末能回收本利 140%，但规定最大投资额不 超过 6 万元； 项目 D：五年内每年年初可购买公债或定期储蓄，于当年末归还，并加利息 9%
现要求确定这些项目每年的投资额,使到第五年末拥有的资金本利总额为最大 分析: 1.假设变量,设以x1x,xc,x(=1,2,3,4,5)分别表示第年i年初给项目A,B,C, D的投资额 2.资金流转分析,原则是每年年初应把资金全部投出去,手中不留呆滞资金。因 此,第一年年初将20万元资金投给A,D项目,有 x+xD=20000,0年底回收项目D的本息为:x1D(1+9%)=1.09xD 这些资金应在第二年年初投资给A,C,D三个项目,故有x24+x2c+x2D=1.09xD 第二年年底回收项目A的第一年投资和项目D当年投资的本利总合为: 1.15xA+1.09x2D这些资金在第三年初投资给项目A,B,D,有 x5A+xB+x3D=1.15xA+1.09x2D第三年底回以A项的第二年投资和D项当年投资的 本利总合为:1.15x4+1.09x30 类似的,可得第四年投资为:x4+x4D=1.15x24+109x30 第五年投资为:xD=1.15x34+1.09x4D 第五年年底共回收资金: 项目A:1.15x4 项目B:125xa,且xB≤8000 项目C:1. 且 项目D:1 从而得到该投资问题的模型为:求x12x,xC,x(=1,2,3,4,5),使其满足 x1+xD=200000 xip +x2a+x2c tx 0 1.15x,,-1.09x+x2,+x+x=0 1.15x24-1.09x2D+x4+x4D=0 115x-1.09 5D x5≤80000 x2c≤60000 ≥0(=1,2…,5) 并使f(x)=1.15x1A+125x8+1.40xc+109xD最大 例1.5(混凝土搅拌站选址问题) 在一个联合协作多点开口建筑施工的场地中,一个大型搅拌站的安装位置,对施工 的进度将起很大的作用,特别是基础浇灌阶段更为重要,由此,我们来建立一个选址问 题的数学模型 设共有n个施工地点(广义的称需求点),有m个可供选择建站的地点(广义的称
现要求确定这些项目每年的投资额，使到第五年末拥有的资金本利总额为最大。 分析： 1．假设变量，设以 , , , ( , , , , iA iB iC iD x x x x i = 1 2 3 4 5)分别表示第年 i 年初给项目 A，B，C， D 的投资额。 2．资金流转分析，原则是每年年初应把资金全部投出去，手中不留呆滞资金。因 此，第一年年初将 20 万元资金投给 A，D 项目，有 A D x x 1 1 + = 200000，则年底回收项目 D 的本息为： ( %) . D D x + = x 1 1 1 9 1 09 这些资金应在第二年年初投资给 A，C，D 三个项目，故有 . A C D D x + x x + = x 2 2 2 1 1 09 第二年年底回收项目 A 的第一年投资和项目 D 当年投资的本利总合为： . . A D x + x 1 1 15 1 09 2 这些资金在第三年初投资给项目 A，B，D，有 . . A B D A D x + + x x = x + x 333 1 2 1 15 1 09 . . 第三年底回以 A 项的第二年投资和 D 项当年投资的 本利总合为： A D x + x 2 3 1 15 1 09 类似的，可得第四年投资为： . . A D A D x + x x = + x 4 4 2 3 1 15 1 09 第五年投资为： . . D A D x = + x x 5 3 1 15 1 09 4 第五年年底共回收资金： 项目 A： . A x4 1 15 项目 B： . B x3 1 25 ，且 B x3 ≤ 80000 项目 C： . C x2 1 40 ，且 C x2 ≤ 60000 项目 D： . D x5 1 09 从而得到该投资问题的模型为：求 , , , ( , , , , iA iB iC iD x x x x i = 1 2 3 4 5)，使其满足 . . . . . . . , , , ( , , , ) A D D A C D A D A B D A D A D A D D B C iA iB iC iD x x xxx x x x x x x x x x x x x x x x x x x x i + = − + + + = − − + + + − − + + = − − + = ≤ ≤ ≥ = 1 1 1 2 2 2 1 2 3 3 3 2 3 4 4 3 4 5 3 2 200000 1 09 0 1 15 1 09 0 1 15 1 09 0 1 15 1 09 0 80000 60000 0 1 2 " 5 = 并使 ( ) . . . . A B C D f x x = + 1 15 432 1 25x +1 40x +1 09x5 最大。 例 1.5 （混凝土搅拌站选址问题） 在一个联合协作多点开口建筑施工的场地中，一个大型搅拌站的安装位置，对施工 的进度将起很大的作用，特别是基础浇灌阶段更为重要，由此，我们来建立一个选址问 题的数学模型。 设共有 n 个施工地点（广义的称需求点），有 m 个可供选择建站的地点（广义的称
为供应点),每个点至多建立一个搅拌站,现设在地点i建站的生产能力为(单位:立 方米),在地点i搅拌站生产的单位时间的固定成本为F(F可用固定资产折旧来衡量) 施工点j的需求量为S,从搅拌站i到施工点j的单位运费为C 设x为从搅拌站i向施工点j供应的混凝量(单位:立方米) l1表示是否选择地点i建立搅拌站, 则 ∫,若选;点 0,若不选i点 归纳得到数模:求满足 xn≤rl,(i=1,2,…,m) x≥S(=12…m) x≥0;u1取0或1(=1,2…,m,j=12…,m) 并使∫(x)=∑∑Cx+∑F取最小值的x/(=1,2…,mj=12…,n i=l j=l 综合上述各例,不难看出我们所建立的数学表示都具有一个共同特点:要求出一组 非负数x≥0(=1,2,…,m),且使它们满足一组线性条件(一组线性方程或线性不等式), 并且使得某一关于n个变量x的线性函数取得最大值或最小值。我们把这一类问题统称 为线性规划问题。 1.2线性规划的标准形式 121线性规划问题的标准形式 把上节例子加以概括,我们可以把它们抽象成这样一类数学问题: 求满足条件: a1x+a2x2+…+a1nxn≥(≤或= a21x+a2x2+…+a2nxn≥(≤或=)b2 (1-1) anx+an2x2+…+ ax≥(≤或=)。 0(j=1, 并且使∫(x)=C耳+c2+…+Gx取最大(小)值得一组数x(j=1,2,…,n)。(-3) 其中,a(=1,2,…mj=1,2…,m),b及c都是已知常数,(1-1)式中的线性条件
为供应点），每个点至多建立一个搅拌站，现设在地点 i 建站的生产能力为 （单位：立 方米），在地点 i 搅拌站生产的单位时间的固定成本为 （ 可用固定资产折旧来衡量） 施工点 j 的需求量为 ，从搅拌站 i 到施工点 j 的单位运费为 。 ir Fi Fi j S Cij 设 ij x 为从搅拌站 i 向施工点 j 供应的混凝量（单位：立方米） i u 表示是否选择地点 i 建立搅拌站， 则 = ，若不选 点 ，若选 点 i i ui 0 1 归纳得到数模：求满足 n ij j=1 ij ij ( , , , ) ( , , ) 0 1( , , , ; , , , ) i i m j i x ru i m x S j n x i m j = ≤ = ≥ = ≥ = = ∑ ∑ 1 1 2 1 2 1 2 1 2 " " 0; ui 取 或 " " n 并使 ( ) m n m ij ij i i i j i f x C x = = = = ∑∑ +∑ 1 1 1 Fu 取最小值的 xij (i m = = 1 2, ," " , ; j 1 2, , , n) ) 综合上述各例，不难看出我们所建立的数学表示都具有一个共同特点：要求出一组 非负数 ( , , , ij x ≥ = 0 1 j 2 " n ，且使它们满足一组线性条件（一组线性方程或线性不等式）， 并且使得某一关于 n 个变量 j x 的线性函数取得最大值或最小值。我们把这一类问题统称 为线性规划问题。 1.2 线性规划的标准形式 1.2.1 线性规划问题的标准形式 把上节例子加以概括，我们可以把它们抽象成这样一类数学问题： 求满足条件： (1-1) ( , , , ) n n n n m m mn n j a x a x a x a x a x a x a x a x a x x j n + + ≥ ≤ + + ≥ ≤ + + ≥ ≤ ≥ = 11 1 12 2 1 21 1 22 2 2 1 1 2 2 0 1 2 " " """"""""""""""" " " 1 2 m + ( 或= )b + ( 或= )b + ( 或= )b (1-2) 并且使 ( ) n n f x c = + x c x + + c x 1 1 2 2 " 取最大（小）值得一组数 j x ( , j =1 2,", n) " ) 。(1-3) 其中，a i ij( , =1 2,",m; j = 1 2, , , n ，bi 及ci 都是已知常数，（1-1）式中的线性条件
可以是方程式也可以是不等式,亦可以二者兼有 凡能表为以上形式的问题统称为线性规划问题。 (1-1)式称为线性规划的约束条件 (1-2)式称为线性规划的未知变量(决策变量)。 (1-3)式称为线性规划的目标函数 为了讨论方便起见,我们把以上线性规划问题统归成如下标准形式: 求满足约束方程: a1x+a2x2+…+a1nx=b1 a2x+a2x2+…+a2nxn=b2 bn x≥0(=12,…,n) b≥0(=1,2…,m) 使∫(x)=Cx十C2x+…+Cnx最大的一组数x=(x1,x2,…,x)。 为了叙述方便起见,我们用(L,P)代表以上的标准形线性规划。 1.标准线性规划的矩阵形式: b 设A b AX=b C=(c,C2…,cn),则(L,P)的矩阵形式为求满足条件 K≥0 并且使∫(x)=CX取最大的一组数X。 Maxf(x)=CX 简记为: sX≥0 b≥0 2.标准线性规划的向量形式 b b 则得(L,P)的向量形式
可以是方程式也可以是不等式，亦可以二者兼有。 凡能表为以上形式的问题统称为线性规划问题。 （1-1） 式称为线性规划的约束条件。 （1-2） 式称为线性规划的未知变量（决策变量）。 （1-3） 式称为线性规划的目标函数。 为了讨论方便起见，我们把以上线性规划问题统归成如下标准形式： 求满足约束方程： ( , , , ) 0( , , , ) n n n n m m mn n j i a x a x a x a x a x a x a x a x a x x j n b i m + + + + + + ≥ = ≥ = 11 1 12 2 1 21 1 22 2 2 1 1 2 2 0 1 2 1 2 " " """"""""""" " " " 1 2 m + = b + = b + = b 使 ( ) n n f x c = + x c x + + c x 1 1 2 2 " 最大的一组数 ( , , , ) T n x = x x x 1 2 " 。 为了叙述方便起见，我们用（L，P）代表以上的标准形线性规划。 1．标准线性规划的矩阵形式： 设 X= b= n n m m mn n m a a a x b a a a x b A a a a x b = 11 12 1 1 1 21 22 2 2 2 1 2 " " """""" # # " ( , , , ) C c n = c c 1 2 " ，则（L，P）的矩阵形式为求满足条件 AX b X = ≥ 0 并且使 f ( ) x = CX 取最大的一组数 X 。 简记为： ≥ ≥ = = 0 . 0 ( ) b X AX b st Maxf x CX 2．标准线性规划的向量形式 设 则得（L，P）的向量形式： = mj j j j a a a P " 2 1 = mb b b b " 2 1
Maxf(x)=∑cx axf(x)=∑c,x ∑qx=b ∑Px=b ≥0 s1x,≥0 b≥0 122将一般线性规划问题划为标准形式的方法 将非标准形式线性规划为标准形式线性规划时有以下几种情况可能出现,处理的方 法有 1.目标函数为极小化。对目标函数为极小化的问题只要将目标函数乘以(-1)即 可化为等价的极大化问题 2.约束条件为不等式。部分或全部约束条件为不等式有两种情况: (1)约束条件为不等式或等于形式。对这样的约束,在不等式的左端加上一个非 负的新变量即可化为等式。新增的非负变量成为松弛变量 (2)约束条件为大于或等于形式。对这样的约束,在不等式的左端减去一个非负 的新变量即可化为等式。新增的非负变量称为剩余变量,亦可以称为松弛变量。 3.决策变量有非正约束。如果x≤0,则用非负变量x代替,使x=-x。 4.决策变量x符号不受限制。标准形式中要求变量为非负,碰到变量无非负约束 时,可以用两个非负的新变量之差来代替。如变量x无非负性要求,则将它写成 x=x-x,新变量x和x为非负变量,而x的符号将由x和x来确定 5.决策变量有上下界。对这种情况,可将上下界分别处理。引进新的变量使等于 原变量减去上下限值,如此则下限为零,满足标准形式的非负性要求。如已知决策变量 x,的限制为a≤x,≤b,;则以x=x,-a代替x,从而得0≤x≤b-a,现时的x满足了 非负要求。并用新变量x替换目标函数和约束条件中所有的原变量x,,再将上限约束列 为新的约束条件并化为等式。 下面举例说明如何将一般非标准形式的线性规划问题划为标准形式的线性规划问 例1.6将下列线性规划问题化为标准形式 maxf(x)=2x,-x2+x3 < 2x-x+x212 x1-4x2-4x3 2 x1,x2≥0,x3不限
≥ ≥ = = ∑ ∑ = = 0 . 0 ( ) 1 1 j j n j ij j j n j j j b x a x b st Maxf x c x 或 ≥ ≥ = = ∑ ∑ = = 0 . 0 ( ) 1 1 j j n j j j j n j j j b x P x b st Maxf x c x 1.2.2 将一般线性规划问题划为标准形式的方法 将非标准形式线性规划为标准形式线性规划时有以下几种情况可能出现，处理的方 法有： 1．目标函数为极小化。对目标函数为极小化的问题只要将目标函数乘以（-1）即 可化为等价的极大化问题。 2．约束条件为不等式。部分或全部约束条件为不等式有两种情况： （1）约束条件为不等式或等于形式。对这样的约束，在不等式的左端加上一个非 负的新变量即可化为等式。新增的非负变量成为松弛变量。 （2）约束条件为大于或等于形式。对这样的约束，在不等式的左端减去一个非负 的新变量即可化为等式。新增的非负变量称为剩余变量，亦可以称为松弛变量。 3．决策变量有非正约束。如果 j x ≤ 0 ，则用非负变量 ' j x 代替，使 ' j j x = −x 。 4．决策变量 j x 符号不受限制。标准形式中要求变量为非负，碰到变量无非负约束 时，可以用两个非负的新变量之差来代替。如变量 j x 无非负性要求，则将它写成 ' " j j j x = x − x ，新变量 ' j x 和 " j x 为非负变量，而 j x 的符号将由 ' j x 和 " j x 来确定。 5．决策变量有上下界。对这种情况，可将上下界分别处理。引进新的变量使等于 原变量减去上下限值，如此则下限为零，满足标准形式的非负性要求。如已知决策变量 j x 的限制为a x j j ≤ ≤ bj ；则以 ' j j x = x − a 代替 j x ，从而得 ' j 0 ≤ x ≤ −b a，现时的 ' j x 满足了 非负要求。并用新变量 ' j x 替换目标函数和约束条件中所有的原变量 j x ，再将上限约束列 为新的约束条件并化为等式。 下面举例说明如何将一般非标准形式的线性规划问题划为标准形式的线性规划问 题。 例 1.6 将下列线性规划问题化为标准形式： max ( ) . , , f x x x x x x x x x s t x x x x x x = − + + − ≤ − + ≥ − − ≥ ≥ 1 2 1 2 3 1 2 3 1 2 3 1 2 3 2 3 20 2 1 4 4 2 0 不限 x3 2