线性规划问题数学模型

1、关于线性规划问题的数学模型第一张，PPT共五十三页，创作于2022年6月线性规划问题第一节 线性规划问题的数学模型（一）引言 线性规划是运筹学的重要分支之一，也是研究较早、发展较快、应用较广而且比较成熟的一个分支。自1947年线性规划被成功的运用于工业、交通、农业和军事等各个领域后，现在它已成为管理科学的重要基础和手段之一。随着计算机的普及，它的适应领域越来越广泛。 线性规划研究的问题主要有两类：一是一项任务确定后，如何统筹安排，尽量作到用最少的人力物力资源去完成这一任务。二是已有一定数量的人力物力资源，如何安排使用他们，使得完成任务最多。其实这两类问题是一个问题的两个方面，就是所谓寻求整个问

2、题的某个整体指标最优的问题。 1.运输问题 2.生产的组织与计划问题 3.合理下料问题 4.配料问题 5.布局问题 6.分配问题第二张，PPT共五十三页，创作于2022年6月（二）线性规划问题的数学模型1.运输问题 设有两个砖厂A1、A2。其产量分别为23万块与27万块。它们生产的供应B1、B2、 B 3三个工地。其需要量分别为17万块、18万块和15万块。自各产地到各工地的运价格如下表：问应如何调运，才使总运费最省。 运价 工地 砖厂B1B2B 3A1506070A260110160第三张，PPT共五十三页，创作于2022年6月解：设 xi j表示由砖厂Ai 运往工地 Bj 砖的数量（i=1

3、,2；j=1,2,3)运量 工地砖厂B1B2B 3发量A1x11x12x1323A2x21x22x2327收量17181550第四张，PPT共五十三页，创作于2022年6月目标函数 约束条件第五张，PPT共五十三页，创作于2022年6月2.生产的组织与计划问题 某工厂生产A 、B两种产品，现有资源数、生产每单位产品所需原材料数以及每单位产品可得利润如下表所示。问如何制定生产计划使两种产品总利润最大？单位产品 产品耗用资源 资源A（公斤）B（公斤）现有资源铜（吨）94360电力（千瓦）45200劳动日（个）310300单位利润（万元/公斤）712第六张，PPT共五十三页，创作于2022年6月解：

4、假设生产A产品x1公斤， B产品x2公斤， x1 ， x2称为决 策变量，简称变量。得到利润7 x1 +12 x2万元，这一问 题的数学模型为：约束条件 目标函数第七张，PPT共五十三页，创作于2022年6月 上述例子虽然有不同的实际内容，但是都可归结为一类优化问题。从数学上说它们具有以下共同特征： 每一个问题都是求一组变量（称为决策变量）的值。这组变量的一组定值就代表一个具体方案。通常要求这组变量的取值是非负的。 存在一定的限制条件，称为约束条件。这些约束条件都可以用一组线性等式或不等式来表示。 都有一个期望达到的目标，并且这个目标可以表示为决策变量的线性函数（称为目标函数）。按所研究问题的

5、不同，要求目标函数值最大化或最小化。 我们将具有上述三个特点的最优化问题归结为线性规划问题，其数学模型称为线性规划问题的数学模型，简称线性规划数学模型。第八张，PPT共五十三页，创作于2022年6月线性规划问题的数学模型的一般形式（1）式称为目标函数（2）式中等式或不等式称为约束条件（3）式是非负约束条件 x1 , x2, ,xn称为决策变量，简称变量。第九张，PPT共五十三页，创作于2022年6月满足约束条件的一组变量的值称为线性规划问题的一个可行解，使目标函数取得最大（或最小）的可行解称为最优解。此时，目标函数的值称为最优值。 建立线性规划数学模型的步骤 首先，确定决策变量。线性规划的数学

6、模型建得是否容易，求解是否方便，取决于决策变量的选取是否得当。 其次，确定约束条件，并根据实际问题添加非负条件。明确问题中所有的限制条件，并用决策变量的线性等式或不等式表示。一般可用表格形式列出所有的限制数据，然后根据所列出的数据写出相应的约束条件，以避免遗漏或重复所规定的限制要求。 最后，确定目标函数，并确定是求极大还是求极小。用决策变量的线性函数来表示实际问题所要达到的目标，得到目标函数。第十张，PPT共五十三页，创作于2022年6月第二节 两个变量的线性规划问题的图解法例1 求x1、x2的值，使它们满足并且使目标函数f =2 x1+5x2的值最大。图解法是利用直观的几何图形求解线性规划的

7、一种几何解法 第十一张，PPT共五十三页，创作于2022年6月x12x1+5x2=192x1+5x2=152x1+5x2=82x1+5x2=4x2=3x1=4x1+2x2=80 x2最优解为 x1=2，x2=3 相应的目标函数的最大值为 S=2*2+5*3=19第十二张，PPT共五十三页，创作于2022年6月x1x1+2x2=8x1+2x2=6x1+2x2=2x1+2x2=0 x2=3x1=4x1+2x2=80 x2例2 若把例1的目标函数改为 s= x1+2x2 ，最优解有 无穷多个， 它们对应的目标函数值都是 8。（见下图）第十三张，PPT共五十三页，创作于2022年6月例3 求x1、x2

8、的值，使它们满足并且使目标函数s=2 x1+2x2的值最小。第十四张，PPT共五十三页，创作于2022年6月x1x20X1-x2=1X1+2x2=02X1+2x2=22X1+2x2=62X1+2x2=102X1+2x2=16最优解 X1=1，x2=0, 目标函数最小值 s=2解：例4 若把例3改为使的目标函数的值最大，从图可看出目标函数无上界，因此无最优解第十五张，PPT共五十三页，创作于2022年6月例5 求x1、x2的值，使它们满足并且使目标函数s=2 x1+2x2的值最小。第十六张，PPT共五十三页，创作于2022年6月x1x2-x1 + x2 =1x1 + x2 = -2没有可行解，当

9、然没有最优解。解：第十七张，PPT共五十三页，创作于2022年6月（一）线性规划问题的标准形式 线性规划问题的数学模型有各种不同的形式。为了便于讨论，需要将线性规划数学模型写成统一格式。 线性规划问题的标准型是：第三节 单纯形法约束条件（2）式又称等式约束（3）式称非负约束。 标准型的特点为（1）目标函数为最大值形式（2）约束条件用等式表示且等 式右端的常数 为非负值（3）决策变量非负。第十八张，PPT共五十三页，创作于2022年6月 把一般的线性规划问题化成标准型的过程称为线性规划问题的标准化。线性规划问题的标准化的方法如下：1. 求目标函数的最小值 令F=-f，则可将求f的最小值问题转化成

10、求F的最大值问题，即2. 约束条件为不等式 引入一个非负变量 xn+i，转化为线性等式，称 xn+i 为松弛变量。 3. 若有bi0 可在该约束条件两边同乘 -1，化为 4.如果有某个变量xj 无非负约束 可引进非负变量xj/, xj/，令xj =xj /- xj/ 代入约束条件和目标函数中。第十九张，PPT共五十三页，创作于2022年6月例1 将下面的线性规划问题化成标准型。解 引进松弛变量 x40 , x5 0 ，将式中不等式约束条件变换成等式约束条件：将3x1-x2 -2x3 =-5两边同乘 -1，变为-3x1+x2 +2x3 =5变量x3无非负约束，引进非负变量x6, x7，令x3 =

11、 x7 - x6 ，代入约束条件 和目标函数。得最后，令F=-f，则可将求f的最小值问题转化成求F的最大值问题。标准型为：第二十张，PPT共五十三页，创作于2022年6月（二）、基本概念 定义 在线性规划的标准型中，如果有变量只在某一个约束方程 中系数为1，在其余约束方程中系数全为0，则称为该约束 的一个基变量；如果每个等式约束都有一个基变量，则称 等式约束条件是这些基变量的典型方程组。 如果线性规划的约束条件是典型方程组，不失一般性，设n个变量的线性规划问题的典型方程组为：第二十一张，PPT共五十三页，创作于2022年6月其中基变量为x1 , x2 , , xm ，从而xm+1 , xm+2

12、 , , xn称为非基变量。令非基变量xm+1 =0, xm+2 =0, xn =0 ，则可求得约束方程的一个解： x1 = b1, x2 = b2, , xm = bm , xm+1 =0 , xm+2 =0, , xn =0 称为基本解。如果bi0( i=1,2,m )则称此基本解为基本可行解。 (三)、单纯形法1单纯形法的基本思想单纯形法的基本思路是：根据标准型，从可行域的一个基本可行解开始，转移到另一个基本可行解，并且使目标函数值逐步变优，当目标函数值达到最大值时，就得到问题的最优解。第二十二张，PPT共五十三页，创作于2022年6月下面举例说明单纯形法的基本思想例2 求解线性规划问题

13、解 先将问题化成标准型第二十三张，PPT共五十三页，创作于2022年6月 显然 x4 , x5为基变量， x1 , x2 , x3为非基变量，约束条件是典型方程组。由（1）可得：将（2）代入目标函数可得 f = 2x1 +3 x2 + x3 +0 , 令非基变量 x1 = x2 = x3 =0则有 f = 2x1 +3 x2 +1x3 + 0 = 0 , 同时得到一个基本可行解 x1 = x2 = x3 =0 ,x4=1, x5=3 由f = 2x1 +3 x2 + x3 +0可知，非基变量的系数都是正数，若将其中任意一个非基变量变成基变量（取值从0变成正数）,都可以使目标函数值增加,所以只要

14、在目标函数的表达式中还存在有正系数的非基变量，就表示目标函数值还有增加的可能，从而不是最优解，就需要将非基变量与基变量进行对换。我们把非基变量转换为基变量称为进基。一般选择正系数最大的那个非基变量（本例为x2 ）为进基变量，以求得目标函数值较快的增加。将x2换入到基变量中。同时，还要确定基变量中有一个要换出来成为非基变量。变量由基变量转化成非基变量称为出基。第二十四张，PPT共五十三页，创作于2022年6月 怎样确定出基变量，由（2）式， x2 为进基变量， x1, x3仍为非基变量，故x1, x3的值为零。代入（2）式可得随着x2的值增加， x4, x5的值会逐渐变小，由于 才能保证x40,

15、 x50 （即解的可行性）。当x2 =9/4时， x5=0。即用 x2替换x5 （ x5出基），于是得到新的基变量x4, x2 ,非基变量x1, x3 , x5 。这种确定出基变量的方法称为最小比值原则。第二十五张，PPT共五十三页，创作于2022年6月由（2）式写出用非基变量表示基变量的表达式：整理得 代入目标函数得 f=27/4+5/4 x1 -17/4 x3 9/4 x5令非基变量x1 = x3 = x5 =0 得一新的基本可行解 x1 =0, x2 =9/4, x3 =0, x4 =1/4, x5 =0代入代入目标函数 得相应的目标函数值 f= 27/4 非基变量x1的系数是正数，说明

16、目标函数值还可能增加，于是再用上述方法，确定进基、出基变量，又得到另一个基本可行解 x1 =1, x2 =2, x3 =x4 =x5 =0 f= 21+32=8用非基变量表示目标函数 f= 8 - 3x3 5x4 - 1x5第二十六张，PPT共五十三页，创作于2022年6月式中所有非基变量的系数均是负数，意味着目标函数值不可能再增加，故此时的基本可行解就是最优解，最优值为8 2最优性检验由标准形等式约束条件得代入目标函数进行简单的运算后，用非基变量表示目标函数为称为非基变量的检验数。将用检验数来判定线性规划问题是否有最优解，有最优解定理。第二十七张，PPT共五十三页，创作于2022年6月定理

17、(1)如果关于非基变量的所有检验数 则基本可行解就是最优解(2)如果关于非基变量的所有检验数且其中有一个非基变量xm+k的检验数为零 则该线性规划问题有无穷多个最优解(3)如果存在非基变量xm+k 的检验数0 且xm+k对应的系数列均小于等于零 则该线性规划问题无最优解 第二十八张，PPT共五十三页，创作于2022年6月3. 单纯形表 用表格的形式来表示上面求解线性规划问题的单纯形法的计算过程可以 使计算和检验更加简便。具体方法如下： 将目标函数式改写为-f+ c1 x1 + c2 x2 + cnxn =0 且作为等式约束方程组的第m+1个方程，得对方程组(3-1)的增广矩阵施行初等行变换，化

18、为如下的阶梯形矩阵第二十九张，PPT共五十三页，创作于2022年6月将矩阵表示成单纯形表xBb100010001-f000-f0 x1x2xmxm+1xnx1x2xmb1b2bma1m+1a2m+1amm+1a1na2namn下面通过具体的例子说明用单纯形法求解线性规划问题。 第三十张，PPT共五十三页，创作于2022年6月例1 用单纯形法解线性规划问题解 将该线性规划问题化为标准型第三十一张，PPT共五十三页，创作于2022年6月显然x3 , x4 , x5为基变量， x1 , x2为非基变量。可得单纯形表(下表所示）。这种直接从线性规划问题得到的单纯形表称为初始单纯形表 xB b 2 2

19、1 0 0 12 1 2 0 1 0 8 4 0 0 0 16 -f 2 3 0 0 0 01x3x4x5x1x2x3x4x5初始基本可行解为 x1 = x2 =0 , x3 =12 ,x4 =8 ,x5 =16。由于检验系数有正数，所以这个基本可行解不是最优解 。从x1 ， x2中选一个检验数最大的变量x2进基。根据最小比值原则(mim12/2,8/2=4)确定,x4出基。进基变量x2所在列与出基变量x4所在行的交叉处元素称为主元，加上方括号，再施行行初等变换，将主元所在列的主元化为1，其余元素化为0，得下表 注 用最小比值原则确定出基变量的一般方法是：在单纯形表中， b列元素与进基变量 列

20、对应的正元素之比，取其比值最小的所对应的基变量出基。第三十二张，PPT共五十三页，创作于2022年6月 xB b 1 0 1 -1 0 4 1/2 1 0 1/2 0 4 4 0 0 0 16 -f 1/2 0 0 -3/2 0 -12x3x2x5x2x3x5x4x11 xB b 0 0 1 -1 -1/4 0 0 1 0 1/2 -1/8 2 1 0 0 0 4 -f 0 0 0 -3/2 -1/8 -14x1x2x3x4x5x3注：比值相等时可任选其一 x2x1 1/4最优解为x1 =4 x2 =2 x3 =x4=x5=0目标函数值为f=14 非基变量的检验数小于0第三十三张，PPT共五十

21、三页，创作于2022年6月例2 用单纯形法求解线性规划问题解 x3 , x4为基变量， x1 , x2为非基变量。可得初始单纯形表 XBb1-1102-31014-f32000X1X3X4X2X3X4第三十四张，PPT共五十三页，创作于2022年6月XBb1-11020-23110-f05-30-6X1X2X3X4X1X4有检验数0系数列均0 无最优解例3 用单纯形法求解线性规划问题第三十五张，PPT共五十三页，创作于2022年6月解 将该线性规划问题化为标准型：F=-f 进行换基迭代，计算过程如表第三十六张，PPT共五十三页，创作于2022年6月XBb111006120108010013-F

22、33000011100601-1102010013-F00-300-18XBb111006120108010013-F33000011100601-1102010013-F00-300-18XBb111006120108010013-F33000011100601-1102010013-F00-300-18 xB b 1 1 1 0 0 6 1 2 0 1 0 8 0 1 0 0 3 -F 3 3 0 0 0 0 1 1 1 0 0 6 0 1 -1 1 0 2 0 1 0 0 3 -F 0 0 -3 0 0 -18 x1 x4 x3 x5 x2 x3 x4 x5 x1 x4 x5 1 1非基

23、变量有检验数0 ， 有检验数=0 无穷多个最优解其中一个最优解是 x1 = 6 , x2= 0 最优值为 f = - F = -18 第三十七张，PPT共五十三页，创作于2022年6月第四节 两阶段法 求解线性规划问题的单纯形法必须满足每个等式约束都有一个基变量即线性规划的约束条件是典型方程组，但经常出现的情况是线性规划的标准型的约束条件不是典型方程组，从而不具有初始单纯形表，这时，需要在线性规划问题中加入人工变量，把问题变为约束条件是典型方程组的情形，再按上述方法换基迭代求出最优解。 人工变量是后加入原约束方程组中的虚拟变量，我们必须把它们从基变量中逐渐替换掉。若经过基的变换，基变量中不再含

24、有人工变量，这表示原问题有解；若经过基的变换，最后在基中还有一个或几个人工变量，这意味着原问题无可行解。 两阶段法是处理人工变量的方法之一，它是将加入人工变量后的线性规划问题分成两阶段求解。第三十八张，PPT共五十三页，创作于2022年6月第一阶段：判断原线性规划问题是否有基本可行解。其方法是：对于线性规划问题标准型的目标函数、等式约束、非负约束引入人工变量y1 , y2 , ym ，构造一个辅助线性规划问题。 对辅助线性规划问题应用单纯形法，求出辅助问题的最优解。若最优值Z=0，说明所有人工变量都变换为非基变量，表明原问题已得到一个基本可行解，则进入第二阶段；否则原问题无可行解，计算结束。第

25、三十九张，PPT共五十三页，创作于2022年6月第二阶段：在第一阶段所得的初始单纯形表基础上，进行换基迭代。将第一阶段最终计算表中的目标函数的系数换成原问题目标函数的系数，划去人工变量所在的列，完成单纯形表，就得到求解原问题的初始单纯形表。然后用单纯形法进行计算求出最优解。例1 用两阶段法求解下面的线性规划问题解 第一阶段 ： 第一、第二约束中暂缺基变量，分别引入人工变量 y1 、 y2 , 引入辅助线性规划问题第四十张，PPT共五十三页，创作于2022年6月Z用非基变量表示： 用单纯形表进行换基迭代如下 XBb5118101024320110-Z7541000201001-Z00011102

26、-Z0000-1-10 XB x1 x2 x3 x4 y1 y2b y151181010 y224320110 -Z754100020第四十一张，PPT共五十三页，创作于2022年6月 XB x1 x2 x3 x4 y1 y2b x45/81/81/811/805/4 y23/415/411/40-1/4115/2 -Z3/415/411/40-5/4015/2 x4 3/501/3012/15-1/301 x21/5111/150-1/154/152 -Z0000-1-10由于得到辅助问题的最优值Z=0，且人工变量均已出基，于是进入第二阶段。第四十二张，PPT共五十三页，创作于2022年6月

27、第二阶段 在第一阶段的最终表中划去人工变量所在的列，并将-Z行换成 -f 行即得原问题的初始单纯形表。这里需注意的是，填 f 行前，需将 f 用非基变量表示，由上表最后一次换基迭代知：用单纯形法进行计算，如下表所示 第四十三张，PPT共五十三页，创作于2022年6月XB x1x2x3x4 bx43/501/3011x21/5111/1502-f20-1/30-10 x1101/185/35/3x20113/18-1/35/3-f00-4/9-10/3-40/3原线性规划问题最优解为 x1 =5/3, x2 =5/3, x3= x4 =0 最优值为 f=40/3 第四十四张，PPT共五十三页，创

28、作于2022年6月例2 用两阶段法求解下面的线性规划问题解 化成标准型第四十五张，PPT共五十三页，创作于2022年6月解 第一阶段 ： 引入人工变量 y1 、 y2 、y3, 引入辅助线性规划问题Z用非基变量表示： 用单纯形表进行换基迭代如下： 第四十六张，PPT共五十三页，创作于2022年6月xBx1x2x3y1y2y3 by195010014y213-20102y33-230014-Z136100020y1011-910-32y2011/3-301-1/32/3x11-2/31001/34/3-Z044/3-1200-13/38/3x201-9/111/110-3/112/11y2000-1/312/30 x1105/112/3305/3316/11-Z000-4/30-1/30第四十七张，PPT共五十三页，创作于2022年6月于是得辅助问题的最优值Z=0。人工变量y2尚未出基，且y2所在行的非人工人工变量列元素均为零，无法让y2出基。但是由最后一个单纯形表中y2所在行，得这表明原问题的约束方