系统工程在煤矿的应用.doc

下篇系统工程在煤矿的应用 第三章 线性规划及其应用 人们在从事生产活动过程中经常会遇到这类事情当一件事可以采取不止一种方法去完成时，总希望选择一种在某种意义上来说是最优的方案。线性规划就是寻找这种最优方案的方法之一。线性规划是运筹学中研究最早、应用较广、比较成熟的一个重要分支。它研究的问题主要有两个方面一是在一定的人力、物力、财力等资源的条件下，如何安排，以便用有限的资源去完成最大的任务；二是任 务已定，即工程已定，应如何统筹安排，以便以最小的资源去完成这一项任务。具体地说可以解决如下一些最优化问题生产的经营和计划问题、原材料合理下料问题、资源的合理利用问题、物资运输最优调配问题、作物布局问题以及国民经济综合平衡问题等。 本章仅由实例引出线性规划问题，介绍线性规划模型的建模方法，线性规划模型的单纯形计算法及线性规划在煤矿中的应用。 第一节 线性规划问题及数学模型 一、问题的提出 问题31 某企业在计划期内要生产A、B两种产品。每种产品生产1单位所需的原料、电力与劳动量，以及计划期内所能供应的原料、电力和劳动量均示于表1l。生产1单位A产品能获利7万元，生产1单位B产品能获利12万元。该企业应如何安排生产计划所得利润最多 该问题可用以下数学语言来描述。 假设产品A、B的产量分别为x1单位、x2单位，则这两种产品共需消耗资源原料9x14x2t；电力4x1 5x2kWh；劳动量3x1lOx2工日，但这些数量不能超过计划期内供应的数量，因此x1和x2要满足 表3l 活动 资源 单位产品消耗资源量 资源供应限度 A产品x1 B产品x2 原料，t 9 4 360 电力，kWh 4 5 200 劳动量，工日 3 10 300 9x14x2≤360 4x15x2≤200 3x1lOx2≤300 两种产品的产量不能是负数，因此x1和x2还要满足 x1≥O x2≥O 该企业目标是在不超资源供应能力的前提下，如何确定产量x1和x2，以便得到最大的利润。若用f′表示利润，则f′＝7 x112x2。 综合上述，这个计划问题可归纳为 满足约束条件 9x14x2≤360 4x15x2≤200 3x1lOx2≤300 x1，x2≥O 使得企业的经营目标利润 f′＝7x112x2为最大。 问题32 某矿井钢筋原材料每根5.Om长，现要求截成长2.6m、1.8m和1.2m三种不同的长度，以作钢筋砂浆锚杆之用。这三种钢筋的需要量分别为1000根、2000根相4000根。问如何剪截才能使所用的钢筋原材料最少 不难想到，上述三种不同长度的钢筋用5.Om原材料下料有表32所示的不同截法。 表32 截法 根数（2.6m） 根数（1.8m） 根数（1.2m） 剩料长度，m Ⅰx1 1 1 0 0.6 Ⅱx2 1 0 2 0 Ⅲx3 0 2 1 0.2 Ⅳx4 0 1 2 0.8 Ⅴx5 0 0 4 0.2 假设用截法Ⅰ截x1根，截法Ⅱ截x2根，截法Ⅲ截x3根，截法Ⅳ截x4根，截法Ⅴ截x5根，则这个问题可归纳为 x1x2＝1000 x12x3x4＝2000 2x2x32x44x5＝4000 x1,x2,x3,x4,x5≥O 使得总共消耗的原材料钢筋根根数f′＝x1x2x3x4x5为最小。 分析上面两个例子，可以看出它们具有下共同特征 1每一问题都是用一组未知数x1，x2xn表示某一方案，通常要求这些未知数的取值是非负的； 2存在定的限制条件称为约束条件，这些限制条件都可以用一组线性等式或线性不等式来表达； 3都有一个目标要求，并且这个目标可表示为一组未知数的线性函数称为目标函数。按问题不同，要求目标函数实现最大化或最小化。 象这类问题就是线性规划问题。 二、线性规划问题的数学模型 一一般形式 线性规划问题可田下列数学语言描述c 求 maxminfx＝c1x1c2x2 cnxn 31 满足 a11x1a12x2 c1nxn≤（＝≥）b1 a21x1a22x2 c2nxn≤（＝≥）b2 32 am1x1am2x2 cmnxn≤（＝≥）bm x1,x2, ,xn≥O 33 这就是线性规划的数学模型。由于它概述了线性规划问题的各种形式，也称为线性规划模型的一般形式。 在上述模型中，31式称为目标函数，32与33式称为约束条件，3-3式也称作非负条件。其中x1，x2xn代表n个未知量，m是约束方程的个数，aijil，2，，m；jl，2，，n称为约束方程的系数，cj称为目标函数的系数，bi称为常数项。 当变量和约束方程个数很多时，常把数学模型一般形式简写成 求 X＝x1，x2xnT* 满足 ijxj≤，≥ bi i＝1，2，，m xj≥0 j＝l，2，,n 使得 maxminfx＝jxj 式中aij，bi,cji1,2,,nn含义同前。 为了便于利用矩阵的理论和方法求解线性规划问题，其数学模型可用矩阵表示如下 求 X 满足 AX≤，≥ b X≥0 使 maxminfx＝CX 其中A〔aij〕为约束方程的系数矩阵（mn阶），一般情况下，m＜n； m，n为正整数。 a11 a12 a1m A a21 a22 a2m am2 am2 amm X为n个未知数x1，x2 ，xn 排成的n维列向量 x1 x1 X xn b为m个常数项b1，b2，，bm排成的m维列向量，又称限定向量 b1 b1 b bn C为目标函数系数c1，c2，，cn 排成的行向量，与其物理意义对应，又称价值向量. C（c1，c2，，cn） m和n有时分别称为线性规划的阶数和维数。 任一线性规划问题都可化成上述三种方式表达的数学模型般形式。例如 求 x1，x2 ，xn 满足 x1x22x3 4 x12x22.5x33x4 5 xj≥0（j1,2,3,4） 使得 minfx 2x13x20.5x3x4 可以写成如下简式 求 Xx1，x2 ，x4T 满足 ijxj≤，≥ bi i＝1，2 xj≥0 j＝l，2，3，4 使得 minfx＝jxj 它的矩阵形式则为 求 X 满足 AXb X≥0 使得 minfx CX 其中 C＝（Cj）14＝c1，c2，c3，c4 ＝2，3，0.5，1 X＝（x1，x2，x3，x4）T A＝（aij）24 ＝ a11 a12 a13 a14 ＝ 1 1 2 0 a21 a22 a23 a24 1 2 2.5 3 b＝（b1，b2）T＝（4，5）T 该规划的维数n＝4，阶数m＝2 从上述模型中可以看出，线性规划问题，就是在满足一组约束条件是一组线性方程下，求一组变量x1，x2 ，xnT的电称为线性规划模型的解，使目标函数（一个线性方程）取得最优值（极大值或极小值）问题。 满足下12和13式的解称为可行解，满足23式的可行解称为最优解。 二线性规划模型的标准型 从11、12和13式可以看出，线性规划模型有各种不同的形式。目标函数，有的求最大化，有的求最小化；约束条件可以是“≤”形式的不等式，也可以是“≥”形式的不等式，还可以是“＝”形式的等式。这种多样性给讨论问题带来了不便。为了便于以后讨论，规定线性规划模型的标准形式标准型为 minfx＝c1x1c2x2 cnxn 14 a11x1a12x2 c1nxn≤（＝≥）b1 a21x1a22x2 c2nxn≤（＝≥）b2 35 am1x1am2x2 cmnxn≤（＝≥）bm x1,x2, ,xn≥O 其简写形式为 minfx＝jxj ijxj≤，≥ bi i＝1，2，，m xj≥0 j＝l，2，,n 其矩阵形式为 minfx X AX X≥0 式中X，A，b，C的表达式同数学模型一般形式中的X，A，b，C表达式。 规定bi≥0i＝l，2，，m，如果不是这样，可以在方程两边同乘以－1。 从线性规划的标准型可以看出 1约束条件方程组是一组等式方程组。 2线性规划的目标函数是求极小值。 如果给出的线性规划模型是非标准形式，需设法将其化为标准形式，然后再求解。 这就是线性规划的数学模型。由于它概述了线性规划问题的各种形式， 三标准型的化法 1若约束条件方程组是小于等于型方程组 ijxj≤bi i＝1，2，，m xj≥0 j＝l，2，，n minfx＝jxj 可在约束条件方程组中的每个不等式的左端增添一个非负的松驰变量xni，从而可得标准形式 ijxjxni＝bi i＝1，2，，m 1-6 xj≥0，xni≥0 j＝l，2，,n；i＝1，2，，m minfx＝jxj 1-7 2若约束条件方程组是大于等于型方程组 ijxj≥bi i＝1，2，，m xj≥0 j＝l，2，,n minfx＝jxj 可在约束条件方程组中的每个不等式的左端减去一个非负的松驰变量xni，从而可得标准形式 ijxj-xni＝bi i＝1，2，，m xj≥0，xni≥0 j＝l，2，,n；i＝1，2，，m minfx＝jxj 3如果对变量xj没有非负限制（即自由变量），可引进两个非负变量xj′≥0，xj″≥0令xj xj′- xj″，就化为对全部变量都有非负限制。 4如果问题是求目标函数fx＝c1x1c2x2 cnxn的最大值，可令fx ′＝-fx，化目标函数fx ′＝-c1x1-c2x2-- cnxn，的最小值。 求出fx ′的最小值后，在用fx＝- fx ′化为原问题的最大值。 例1.试将线性规划问题化为标准形。 maxfx＝-x12x2-3x3 x1x2x3≤7 x1-x2x3≥2 -3x1x22x3＝5 x1，x2≥0，x3无非负限制 解通过以下步骤 1引进x3′≥0，x3″≥0令x3 x3′- x3″ 2在第一个约束条件“≤”号左端加上松驰变量x4，x4≥0 3在第二个约束条件“≥”号左端减去松驰变量x5，x5≥0 4令f′＝-f，把maxf改为minf′即可得 minf′x＝x1-2x23x3′- x3″ x1x2x3′- x3″ x4＝7 x1-x2x3′- x3″-x5＝2 -3x1x22x3′- x3″＝5 x1，x2，x3′，x3″，x4，x5≥0 整理为标准形 minf′x＝x1-2x23x3′-3x3″ x1x2x3′- x3″x4＝7 x1-x2x3′- x3″-x5＝2 -3x1x22x3′-2x3″＝5 x1，x2，x3′，x3″，x4，x5≥0 第二节 单纯形法 单纯形法是线性规划问题的一般解法，也是行之有效的方法。它可以求解一切标准型的线性规划问题。 一、线性规划模型标准型约束条件系数矩阵中含有m阶单位矩阵 比如方程组是由小于等于型变为标准型的，则约束条件1-6中的xn1, xn2, , xnm所对应的系数矩阵就是一个m阶单位矩阵。此时，可将线性规划问题写成如下形式 求一组变量 X＝x1，x2，，xn，xn1，xn2，，xnmT 满足 ijxjxni＝bi i＝1，2，，m 3-8 xj≥0 j＝l，2，n，n1，n2，，nm 使得 minfx＝jxjnixni 3-9 取得最小值。 把由3-8式得到的基变量xni＝bi -ijxj代人目标函数3-9 中，得到非基变量表示的目标函数 fx＝ni bi-（niaij-cj）xj 令 λj＝niaij-cj 3-10 f0＝ni bi 3-11 则 fx＝f0j xj 3-12 式中 λ非基变量检验数（一般情况，基变量检验数为零）。 根据3-8和3-12式的系数矩阵可设计一种如表1-3所示的计算表，即为单纯形表。表中最上边一行，填入全部变量，中间填入约束方程组左侧系数矩阵；最下边一行填入变量检验数；最左侧一列填入基变量；最右侧一列填入约束方程组右端常数项；最右角填入目标函数值。 表3-3 基变量 x1 x2 xn xn1 xn2 xnm 常数 xn1 a11 a12 a1n 1 0 0 b1 xn2 a21 a22 a2n 0 1 0 b2 xnm am1 am2 amn 0 0 1 b1 fx λ1 λ2 λn 0 0 0 f0 线性规划问题最优化解的判断准则当所有的检验数λj≤0（j1，2，， n-m n1，n2，，nm）时，X0，0，，0，b1，b2，，bmT为最优解（对表1-3而言） 线性规划问题无解的判断准则如存在一个检验数λk＞0，且所有aik≤0i1，2，，m则线性规划问题无解。 下面以问题31为例介绍用单纯形法计算线性规划问题的步骤和方法。 求 minfx＝-7x1-12x20 x30 x40 x5 满足 9x14x2x3＝360 4x15x2x4＝200 3x1lOx2x5＝300 x1，x2，x3，x4，x5≥O 从标准型中可以看出，约束条件方程组系数矩阵含有一个3阶单位矩阵。 第一步确定基变量，建立初始单纯形表。根据标准型，取约束条件系数矩阵中单位矩阵对应的变量为基变量，根据（3-10）和（3-11）式分别计算出检验数 λjj1,2,，n,n1, ，nm值和f0值，将上述有关变量、数据以及约束方程系数矩阵输入单纯形表，就得到初始单纯形表，从表中可以直接得到初始可行解、目标函数值，可直接进行最优解与无解判断。 取对应于x3，x4，x5的系数矩阵为单位矩阵，则x3，x4，x5为基变量；已知n2、m3，则 090403-（-7）7 同理 λ212 0360020003000 按单纯形法的填表方法，得到初始单纯形表1-4。 表3-4说明，基变量为x3，x4，x5，非基变量为x1和x2；若令非基变量为x1x20，则得到x3360，x4200，x5300（正是表中常数列数据），则得到一个初始基可行解，X0 （0，0，360，200，300）T,则得到目标函数fx0（正是表中右下角数字）。 第二步检查所有对应于非基变量的检验数λj（j1,2,，n）是否都小于等于零，若 λj≤（j1,2,，n），则已得到最优解，停止运算。否则转入下一步。 表3-4 基变量 x1 x2 x3 x4 x5 常数 x3 9 4 1 0 0 360 x4 4 5 0 1 0 200 x5 3 10* 0 0 1 300 fx 7 12 0 0 0 0 问题3-1中，λ17≥0，λ212≥0，说明没有得到最优解，转入下一步。 第三步检查各λj≤（j1,2,，n，且λj＞0）对应的系数aij（i1,2,，m）是否都小于等于零，若是，则线性规划无解，否则转入下一步。 问题3-2中，λ1和λ2对应的ai1≥0，ai2≥0（i1,2,3），转入下一步。 第四步选换入变量xk。从目标函数表达式可以看出，若将非基变量x1和x2换为基变量，目标函数还将继续减小，所以应设法将x1或x2换为基变量，为了使目标函数能较快的递减，在选取换入变量xk时，应挑选最大的正检验数所对应的非基变量。 即 （j1,2,，n） 问题1-1中， 即 k2，换入变量为x2。x2所在的列称为主元列。 第五步选取换出变量xL。有一非基变量换为基变量，必有一基变量换出为非基变量。 用主元列中大于零的aij去除相应的常数项bi，取其最小者。 aLk对应的行称为主元行，用L表示。aLk称为主元。主元行对应的基变量xL作为基变量被换出，由基变量变为非基变量。 问题1-1中 即L5、换出变量为x5，主元aLka5210，即得表3-4中打“*”者。 第六步进行初等变换。用高斯消去法进行初等变换，将主元aLk化为1，主元列中其他元素（包括行中fx的元素）化为零。并用xk代替xL作为基变量，填入xL所在的位置。因此，得到一张新的单纯形表。 问题1，用1/10乘主元行，使得新行分别乘以-4，-5，-12加到x3，x4和f（x）所在的行中，并用x2换出x5得到单纯形表3-5。 可以看出基变量为x3，x4，x2，若令非基变量等于零，则得一个新的基可行解X1（0,30,240,50,0）T，目标函数取值fx 360。 下面的步骤就是以新的单纯形表（此处为表3-5）为起点，从第二步开始，重复上述步骤，循环往复，直到求得最优解。 基变量 x1 x2 x3 x4 x5 常数 x3 7.8 0 1 0 -0.4 240 x4 2.5* 0 0 1 -0.5 50 x2 0.3 1 0 0 0.1 30 fx 3.4 0 0 0 -1.2 -360 问题3-1中，检查非基变量的检验数中λ13，4＞0，因此，重复上述步骤，的新表3-6。 表3-5 表3-6 基变量 x1 x2 x3 x4 x5 常数 x3 0 0 1 -3.12 1.16 84 x1 1 0 0 0.4 -0.2 20 x2 0 1 0 -0.12 0.16 24 fx 0 0 0 -1.36 -0.52 -428 可以看出，由于fx行所有检验数全为非正，故已得到最优解 X（20，24，84，0，0）T 目标函数fx -428 去掉松弛变量，得原问题的最优解 X（20，24）T 即 x120，x224 原问题目标函数 即生产A产品20单位，B产品24单位，使得利润最高，最高利润为428万元。 二、线性规划数学模型标准型约束条件的系数矩阵中不含有m阶单位矩阵 此时难以确定初始基可行解，需要引入人工变量，将原规划问题扩充，然后采用分阶段法求解。这种方法一般称为二阶段法。 例如，有一线性规划问题，其数学模型的标准型为 （3-13） （i1,2,，m） （j1,2,，n） （3-14） 该约束方程的系数矩阵中不含有m阶单位阵，故增加m个人工变量xn1（i1,2,，m），把它扩充后变为 （3-15） （i1,2,，m） （j1,2,，n） 我们称（3-13）、（3-14）式为原问题，称（3-15）、（3-16）式为原问题的第一阶段问题。称（3-16）式为第一阶段约束条件，（3-15）式为第一阶段目标函数。 因为原问题中不含有m阶单位阵，所以按上述单纯法解题步骤一般不能直接求得初始基可行解。但容易看出，第一阶段问题的任何可行解中，若所有人工变量都为零，便得到原问题的可行解。对于第一阶段的最优解，这结论无疑也是成立的。因此，如果第一阶段最优解中，所有人工变量恰好都为零，则第一阶段的这组最优解，去掉人工变量后即可构成原问题的一组初始基可行解。原问题有了初始基可行解，再用单纯形法进行迭代，就能求得最优解。这就是第二阶段法的主要直到思想。 二阶段法的步骤归纳为 （1）若minzx≠0，则原问题无最优解，若minzx0,则从第一阶段问题的最优解中去掉人工变量，就的原问题一组初始基可行解。 （2）对原问题的初始基可行解进行单纯形法迭代，求出最优解。 例1-4 解下述线性规化问题 minf5x121x3 x1-x26x3-x42 x1x22x3-x51 xj≥0 （j1，2，，5） 解由于约束方程中不含有单位阵，而需增加人工变量x6，x7，得到新的线性规化问题 minzx6x73-2x1-8x3x4x5 x1-x26x3-x4x62 x1x22x3-x5x71 xj≥0 （j1，2，，7） 把目标函数变为 zx6x7 2-x1x2-6x3x41-x1-x2-2x3x5 3-2x1-8x3x4x5 1.作初始单纯形表（表3-7） 表3-7 基变量 x1 x2 x3 x4 x5 x6 x7 常数 x6 1 -1 6* -1 0 1 0 2 x7 1 1 2 0 -1 0 1 1 zx 2 0 8 -1 -1 0 0 3 fx -5 0 -21 0 0 0 0 0 zx是第一阶段目标函数，该行所填的数为第一阶段目标函数系数的相反数。 fx是原问题目标函数行，该行所填的数为原问题目标函数系数的相反数。 2.进行第一阶段迭代，求出第一阶段的最优解 迭代过程仍按前面介绍的单纯形法步骤进行，检验数用zx行的数。 （1）求主元列。检查zx行中的λj是否都小于零，如果满足minzx0，则已求得了第一阶段的最优解，否则找出λk。 例如λkmaxλjmax｛2,8｝8 k3,换入变量为x3 （2）求主元行。 L6，换出变量是x6，表3-7中打“*”者为主元。 （3）进行初等变换，把主元化为1，主元例其余元素均化为0，结果的单纯表3-8. 表3-8 基变量 x1 x2 x3 x4 x5 x6 x7 常数 x3 1 0 0 x7 * 0 -1 1 zx 0 -1 0 fx 0 0 0 7 （4）重复上面一至三步直到取得第一阶段最优解。 λk，k2 ， x2为换入变量 ，L7，换出变量为x7，得表1-9 因zx行的λj≤0，minzx0即求得第一阶段问题的最优解 X 去掉人工变量得到原问题的一组基本可行解 X 3.进行第二阶段迭代 通过上述几次迭代已经求得原问题的基可行解，这是按照单纯形法迭代步骤继续迭代，即可求得原问题的最优解。 例中，第一阶段结束，x6，x7例及zx都可以去掉，fx行对用的数是检验数。 表3-9 基变量 x1 x2 x3 x4 x5 x6 x7 常数 x3 0 1 x2 * 1 0 zx 0 0 0 0 0 -1 -1 0 fx 0 0 λk0 k1 ， x1为换入变量 ，L2， x2为换出变量，得表3-10。 表3-10 基变量 x1 x2 x3 x4 x5 常数 x3 0 1 x1 1 2 0 fx 0 0 从表中可以看出，检验数λj≤0（j1,2,，5），说明已得到原问题的最优解，最优解为 即 x1，x20，x3，x40，x50 原问题的目标函数fx 。 三、单纯形法的计算机程序 按单纯形法的原理编制计算机程序，可很方便地结算线性规划问题，省去手工计算的麻烦，避免出现错误。 第三节 线性规划在煤矿中的应用实例 为了说明线性规划在煤矿中的应用，再举几个煤矿建设、生产和管理中的实例。 例3-5 某矿井有三个采区，根据生产技术条件，一采区工人的劳动生产率为5t/工，二、三区工人的劳动生产率分别是4t/工和3t/工。一采区人数不超过120人，二采区人数不超过200人，三个采区总人数不超过500人。按各个采区瓦斯涌出情况和通风要求，三个采区每人所需要的风量分别为8m3/min、6m3/min和10m3/min，供给三个采区的总风量为1200m3/min。矿井实行三班工作制，每个采区每班人数相等。问如何安排三个采区的日产量，使得矿井的日产量最大 解设三个采区的工人数分别为x1，x2，x3，矿井日产量为f，建立数学模型如下 maxf5x14x23x3 x1x2x3≤500 ≤1200 x1≤120 x2≤200 x1，x2，x3≥0 引入松弛变量，令-f，则化为标准型如下 minf′-5x1-4x2-3x3 x1x2x3x4 500 x5 1200 x1 x6 120 x2 x7 200， xj≥0 j1，2，，7 从标准函数可以看出，约束条件的系数矩阵中含4阶单位矩阵，则可直接由标准型，根据（1-10）、（1-11）式及填表规定建立初始单纯形表1-11。 表3-11 基变量 x1 x2 x3 x4 x5 x6 x7 常数 x4 1 1 1 1 0 0 0 500 x5 0 1 0 0 1200 x6 1* 0 0 0 0 1 0 120 x7 0 1 0 0 0 0 1 200 fx 5 4 3 0 0 0 0 0 由于λj≥0（j1,2,3），没有得到最优解，需迭代。 λkmax5,4,3 5 则k1，即x1为换入变量。 则L6，即x6为换出变量。 进行初等变换。主元是1，将主元行乘以（-1）、（-）、（-5），分别加到基变量x4，x5和f′x所在行上，并用x1代替x6,填入基变量列x6所在的位置，可得新的单纯形表1-12。 表3-12 基变量 x1 x2 x3 x4 x5 x6 x7 常数 x4 0 1 1 1 0 -1 0 380 x5 0 0 1 0 880 x1 1 0 0 0 0 1 0 120 x7 0 1* 0 0 0 0 1 200 fx 0 4 3 0 0 -5 0 600 同理，x2为换入变量，x7为换出变量，得表1-13。 表3-13 基变量 x1 x2 x3 x4 x5 x6 x7 常数 x4 0 0 1 1 0 -1 -1 180 x5 0 0 * 0 0 -2 480 x1 1 0 0 0 0 1 0 120 x2 0 1 0 0 0 0 1 200 0 0 3 0 0 -5 -4 -1400 同理，x3为换入变量，x5为换出变量，得表1-14。 表3-14 基变量 x1 x2 x3 x4 x5 x6 x7 常数 x4 0 0 0 1 0 36 x3 0 0 1 0 0 144 x1 1 0 0 0 0 1 0 120 x2 0 1 0 0 0 0 1 200 0 0 0 0 0 -1832 检查行，知λj全为非正，故已得到最优解 x1120，x2200，x3144， 原问题的目标函数（总产量）f-f′1832 于是当一、二、三采区日产量分别为1205600t/d，2004800 t/d，1443432 t/d，矿井日产量为最大，等于1832t/d。 例3-6 田集、杨庄两煤矿向甲、乙、丙三个用户供应煤炭，各煤矿的日产量与各用户的日需要量如表3-15。 表3-15 煤矿 产量，t/d 田集 2000 杨庄 5000 用户 需要量， t/d 甲 1500 乙 2500 丙 3000 各煤矿到三个用户之间的运输距离如表3-16。 表3-16 煤矿 用 户 甲 乙 丙 距 离，km 田集 75 210 380 杨庄 90 470 260 问如何进行调运分配才能使运输费用（单位tkm）为最小 解设x11、x12、x13代表田集煤矿供给甲、乙、丙三个用户煤的数量；x21、x22、x23代表田集煤矿供给甲、乙、丙三个用户煤的数量。 根据各用户的需煤量、两煤矿的生产能力及运输距离，建立数学模型如下 minf75x11210 x12380 x1390 x21470 x22260 x23 x11x211500 x12x222500 x13x233000 x11x12x132000 x21x22x235000 x11，x12，x13，x21，x22，x23≥0 为了解题方便，我们把双下标改为单下标x11用y1代替；x12用y2代替；x13用y3代替；x21用y4代替；x22用y5代替；x23用y6代替。 则线性规划数学模型变为 minf75y1210y2380y390y4470y5260y6 y1y41500 y2y52500 y3y63000 y1y2y32000 y4y5y65000 yi≥0 j1，2，，6 该线性规划数学模型为标准型。根据标准型，用单纯形表计算。 该线性规划约束方程系数矩阵不含单位阵，初始基可行解难以确定，需要用二阶段法，增加人工变量，得到新的规划模型 minz y7 y8y9y10y11 14000- 2y1-2y2-2y3-2y4-2y5-2y6 y1y4y71500 y2y5y82500 y3y6y93000 y1y2y3y102000 y4y5y6y115000 yi≥0 j1，2，，11 列初始单纯形表3-17。 基变量 y