2012年8月数学建模修改讲稿~

第一部分 线性规划及其对偶规划

§1线性规划问题

1. 线性规划问题的数学模型

例1 生产安排问题

某工厂有三种原料B1,B2,B3，其储量分别为170kg， 100kg和 150kg，现用来生产A1和A2两种产品，每 单位产品的原料消耗量及各产品的单位利润由下表给出，问工厂在现有资源的条件下，应如何安排生产，可使工厂获利最多？ 原料 B1 B2 B3 单价利润 产品

A1 5 2 1 10元

A2 2 3 5 18元 170kg 100kg 150kg 资源限额

模型建立：

引入决策变量：用x1,x2分别表示A1和A2两种产品的产量；

确定目标函数：使利润最大。工厂将生产的x1件A1产品和x2件A2产品全部销售出去，工

厂所获得利润为：maxZ?10x1?18x2

写出约束条件：资源限制----生产的x1件A1产品和x2件A2产品消耗资源B1的数量应≤资源限额

本题是求线性目标函数在线性约束下的极值问题，我们称它为线性规划。其数学模型为：

maxZ?10x1?18x2

s?t 5x1?2x2?170 2x1?3x2?100 x1?5x2?150

x1,x2?0

例2 选用饲料问题

某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质、30g矿物质、100mg维生素。现有五种饲料可供选用，各种饲料每kg营养成分含量及单价如下表，要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。

饲料 1 2 3 4 5 蛋白质(g) 3 2 1 6 18 矿物质(g) 1 0.5 0.2 2 0.5 维生素(mg) 0.5 1.0 0.2 2 0.8 价格(元kg) 0.2 0.7 0.4 0.3 0.8 1

模型建立：

引入决策变量：设每头动物每天需要选用xjkg第j种饲料；

确定目标函数：使费用最省。当第j种饲料选用xjkg（j?1,2,3,4,5）时，每头动物每

天所需的费用为：minZ?0.2x1?0.7x2?0.4x3?0.3x4?0.8x5

写出约束条件：当第j种饲料选用xjkg（j?1,2,3,4,5）时，其蛋白质含量应满足动物

生长时一天对蛋白质的营养需求，即有 3x1?2x2?x3?6x4?18x5?700

同理有 x1?0.5x2?0.2x3?2x4?0.5x5?30 ；0.5x1?x2?0.2x3?2x4?0.8x5?100

决策变量的非负约束：x1,?,x5?0

本题的数学模型为： minZ?0.2x1?0.7x2?0.4x3?0.3x4?0.8x5 s?t 3x1?2x2?x3?6x4?18x5?700

x1?0.5x2?0.2x3?2x4?0.5x5?30 0.5x1?x2?0.2x3?2x4?0.8x5?100 x1,?,x5?0

例3 糖果产品的生产安排问题

某糖果厂用三种原料A、B、C加工成三种糖果产品甲、乙、丙。已知各种糖果产品中A、B、C的含量，原料成本，各种原料的每月限制用量，三种糖果产品的单位加工费及单位售价如下表所示。问该厂每月应生产这三种糖果产品各多少千克，使该厂获利最大？

原 料 A B C 糖果产品 甲 ≥60% ≤20% 0.50 3.40 乙 ≥15% ≤60% 0.40 2.85 丙 ≤50% 0.30 2.25 原料成本 （元∕千克） 2.00 1.50 1.00 每月限制用量（千克） 2000 2500 1200 加工费（元∕千克） 售价（元∕千克） 模型建立 （假设三种原料在加工过程没有损耗） 引入决策变量：设该厂每月生产的甲种糖果中用掉原料A、B、C的数量依次为用x1,x2,x3千克；

每月生产的乙种糖果中用掉原料A、B、C的数量依次为x4,x5,x6千克； 每月生产的丙种糖果中用掉原料A、B、C的数量依次为x7,x8,x9千克。

确定目标函数：工厂每月所获得利润最大

maxZ?(3.4?0.5)(x1?x2?x3)?(2.85?0.4)(x4?x5?x6)

?(2.25?0.3)(x7?x8?x9)?2(x1?x4?x7)?1.5(x2?x5?x8)?1?(x3?x6?x9) 2

写出约束条件：每种糖果产品中所含原料的成份要求

甲种糖果产品中，原料A的成份不低于60%，因此有

x1 ?60%??0.4x1?0.6x2?0.6x3?0

x1?x2?x3 同理有：

x3?20%??0.2x1?0.2x2?0.8x3?0

x1?x2?x3x4?15%??0.85x4?0.15x5?0.15x6?0

x4?x5?x6x6?60%??0.6x4?0.6x5?0.4x6?0

x4?x5?x6x9?50%??0.5x7?0.5x8?0.5x6?0

x7?x8?x9 各种原料的每月限制用量：x1?x4?x7?2000 ；x2?x5?x8?2500 ；x3?x6?x9?1200 决策变量的非负限制： x1,?,x9?0

例4 杂粮的买进卖出问题

某贸易公司专门经营某种杂粮的批发业务。公司现有库容5000担的仓库。一月一日，公司拥有库存1000担杂粮，并有资金20000百元。估计第一季度杂粮价格如下表。如买进的杂粮当月到货，但需到下月才能卖出，且规定货到付款。公司希望本季度末库存为2000担，问应采取什么样的买进与卖出策略才能使三个月的总利润最大？

月份 一月 二月 三月 进货价（百元） 2.85 3.05 2.90 出货价（百元） 3.10 3.25 2.95 模型建立

（模型假定：假定每个月是先出货，再进货。）

引入决策变量：设xi为每月买进的杂粮担数，yi为每月卖出的杂粮担数 确定目标函数：三个月的总利润

maxZ?3.1y1?3.25y2?2.95y3?2.85x1?3.05x2?2.9x3 写出约束条件：

?y1?1000?1000?x1?y1?5000?存货限制 ?y2?1000?y1?x1 ； 库容限制 ?

1000?x?x?y?y?50001212??y?1000?x?x?y?y1212?3?2.85x1?20000?3.1y1? 资金限制 ?305x2?20000?3.1y1?3.25y2?2.85x1

?2.9x?20000?3.1y?3.25y?2.95y?2.85x?3.05x312312? 期末库存 1000?x1?x2?x3?y1?y2?y3?2000 决策变量的非负约束：x1,x2,x3,y1,y2,y3?0

例5 人员安排问题

某昼夜服务的公交线路每天各时间区段所需司机和乘务员的人数如下表，设司机和乘务员分别在各时间区段一开始时上班，并连续工作八个小时，问该公交线路至少需要配备多少名司机和乘务人员？

3

班 次 1 2 3 4 5 6 模型建立

时 间 6:00~10:00 10:00~14:00 14:00~18:00 18:00~22:00 22:00~2:00 2:00~6:00 所需人数 60 70 60 50 20 30 引入决策变量：用xk表示有xk名司机和乘务人员在第k班次开始时上班k?1,?,6； 确定目标函数：使配备的司机和乘务员总人数最少，即 minZ?x1?x2?x3?x4?x5?x6

写出约束条件：为保证第1班所需的司机和乘务员人数，应有x6?x1?60

x1?x2?70 ，x2?x3?60 ，x3?x4?50 ，x4?x5?20 ，x5?x6?30 ； 决策变量的非负约束：x1,?,x6?0

2. 线性规划问题的标准形式

对于具体的线性规划问题；目标函数有的是极大化，有的是极小化；约束条件有的是≤，有的是≥，有的是＝；决策变量可以≥0，也可以≤0，还可以不受限制。为了方便线性规划问题的统一求解，我们规定一个标准形式。

maxZ?C1x1?C2x2???Cnxn s?t a11x1?a12x2???a1nxn?b1 ? ? ? am1x1?am2x2???amnxn?bm

x1,x2,?,xn?0 ； 其中b1,b2,?,bm?0

标准形式的特点：① 目标函数要求是极大化；② 约束条件要求等式约束； ③ 决策变量满足非负约束；④ 右端常数项非负 。 引入矩阵和向量：记 C?(c1,c2,?,cn)---- 目标函数的系数行向量 A?aij??m?n---- 约束条件系数矩阵 ； X?(x1,x2,?,xn)T---- 决策变量列向量 ；

b?(b1,b2,?,bm)T---- 右端常数项列向量 ； Pj?(a1j,a2j,?,amj)T---- xj的系数列向量 则标准形式的矩阵描述为： maxZ?CX,AX?b,X?0. 向量描述为： maxZ?CX,?xPjj?1nj?b,X?0.

3. 标准形式的化法

① 极小化化成极大化；如：minZ?x1?2x2? maxZ???x1?2x2

② 化不等式约束为等式约束；

4

如：2x1?3x2?8?2x1?3x2?x3?8，其中x3?0，并称x3为松弛变量

如：5x1?3x2?4?5x1?3x2?x3?4 ，其中x3?0，并称x3为松弛（或剩余）变量

③ 化决策变量满足非负约束；

如：xi?0，则令 xi???xi，并用?xi?去代替xi

??xk??，其中xk?,xk???0，并用xk??xk??去代替xk 如：xk符号不限，则令xk?xk 如：xj??j，则令x?j?xj??j，此时有x?j?0

???r?xr，此时有xr??0，并用?r?xr?去代替xr 如：xr??r，则令xr 练习题 minZ?5x1?2x2?4x3?3x4

?x1?2x2?x3?4x4??2 s?t

?x1?3x2?x3?x4?142x1?x2?3x3?x4?2

x3,x4?0,x2?0,x1符号不限4. 线性规划问题中有关解的概念及线性规划问题的重要性质：

① 可行解：满足所有约束条件的解； ② 可行域：所有可行解构成的集合；

③ 最优解：使目标函数值达到最优时的可行解；

④ 基矩阵，基变量，非基变量，基本解，基本可行解。 为了了解上述概念，我们先看如下例题

maxZ?x1?2x2?11x3?7x4?6x5

s?tx1?2x3?x4?2x5?10x2?3x3?3x4?x5?6x1,x2,x3,x4,x5?0

对于线性规划问题：maxZ?CX,AX?b,X?0.

其中A为m?n矩阵，且R(A)?m?n，B为A的任意一个m阶满秩子方阵，则称B为线性规划问题的一个基矩阵；B中列向量所对应的决策变量称为基变量，其余的决策变量称为非基变量；令非基变量的取值为0，得基变量相应的取值，由此得到的解称为规划问题的一个基本解；如果基本解满足非负约束，则称它为基本可行解。

⑤ 重要性质：如果线性规划问题存在可行解，则一定存在基本可行解；

如果线性规划问题存在有界最优解，则它一定存在有界的最优基本可行解，即线性规划问题的最优解可以在基本可行解处得到。

5. 线性规划问题的求解方法—单纯形法

1）单纯形法的基本思想

从线性规划问题的一个基本可行解出发，判断它是否为最优解；如果不是，则将它进行迭代，迭代至下一个基本可行解，每次迭代，要使目标函数值有所改善；这样经过有限次迭代后，最终可以找到最优解或判断问题无界。

2）基本可行解的迭代过程

maxZ?x1?2x2?11x3?7x4?6x5 下面通过实例来介绍 例

s?tx1?2x3?x4?2x5?10x2?3x3?3x4?x5?6x1,x2,x3,x4,x5?0

5

2．对偶理论

定理1：设原问题与对偶问题之中其一存在最优解，则另一问题也存在最优解，且两问题的最优目标函数值相等， 从该定理的证明过程，可得如下结论：

定理2：如果原问题有最优解，最优基为B，则Y*?CBB?1便是对偶问题的一个最优解。

定理3：对于极大化原问题，如果它存在最优解，则在最优单纯形表中，松弛变量检验数的负值便是对偶问题的

一个最优解。 （ ??(C,CS)?CBB?1(A,I)?0?C?CBB?1A?0,0?CBB?1I??CBB?1?0 令Y*?CBB?1，则有 Y*A?C,Y*?0，满足对偶问题的约束条件。 ）

3．对偶解的经济解释-----影子价格

考虑原问题maxZ?CX,AX?b,X?0和对偶问题minW?Yb,YA?C,Y?0；

设B为原问题的最优基，CB为此时基变量的目标函数系数行向量，X*和Y*分别为各自问题的最优解，Z*和W*为相应的最优值。

由对偶理论可知：Z*?CX*?CBB?1b?Y*b?W* 即 Z?**y1b1?*y2b2???*ymbm?Z*?y* ， 由此可得 j ?bj?Z* 是最优目标函数值对资源bj的变化率，它表示当资源bj（或是第j个约束条件右端的常数项）增加

?bj一个单位时，最优目标函数值的增加量。因此y*j可解释（理解）为： 第j种资源的单位增加量引起的最优目标函数值的改变量（增加量） 我们把它称为第j种资源（第j个约束条件）的影子价格

例题 已知某工厂生产甲、乙两种产品，用线性规划方法来确定最优生产方案。根据产品的单位售价和生产这些产品的三种资源供应限量，建立了如下线性规划模型：

maxs?tZ?5x1?4x2x1?3x2?902x1?x2?80x1?x2?45x1,x2?0收益或产值（资源1）（资源2)（资源3) 其最优单纯形表如下：

CB XB x1 x2 x3 x4 x5 B?1b 0 5 4 x3 0 1 0 0 0 0 1 0 1 0 0 0 2 1 ?5 ?1 2 25 35 10 Z*?215 x1 x2 ?1 ?1 ?j ?3 11

从最优单纯形表得知，最佳生产方案为：甲产品生产35件，乙产品生产10件，工厂获利最多，最大利润为Z*?215

松弛变量x3,x4,x5的检验数分别为0,?1,?3，它们的负值便是对偶问题的最优解，即对偶问题的最优解

***为y1资源1的影子价格为0，它表示当资源1增加一个单位?0,y2?1,y3?3.于是三种资源的影子价格分别为：

时，目标函数最优值的增加量为0；资源2的影子价格为1，它表示当资源2增加一个单位时，目标函数最优值的增加量为1；资源3的影子价格为3，它表示当资源3增加一个单位时，目标函数最优值的增加量为3； 我们可以验证一下，譬如：当资源3的拥有量b3由45变为46时，由灵敏度分析可知，最优单纯形表中改变的只有右端的常数项列向量，由

?12?5??90??25??12?5??90??20???80???35?变为B?1b??01?1??80???34? B?1b??01?1???????????????0?12????45????10???0?12????46????12??最优目标函数值由Z*?CBB?1b?215变为Z*?CBB?1b?(0,5,4)(20,34,12)T?218，由此可见，最优目标函数值的增加量为218?215?3。

4. 影子价格在经济管理中的作用主要体现在以下几个方面：

① 影子价格可以告知管理者，增加何种资源对增加经济效益最有利。

上述三种资源的影子价格为(0,1,3)，所以首先应考虑增加第三种资源，因为它能带来最多的收益增加。 ② 影子价格可以告知管理者，花多大代价来增加资源才是合算的。

本例中，如果将第三种资源增加一个单位，所花的代价大于3，则说明增加第三种资源就不合算。 ③ 影子价格可以告知管理者，如何考虑新产品的价格。

如果一项新产品对三种资源的单位消耗量是(2,5,7)，则新产品的定价必须大于 0?2?1?5?3?7?28

它是新产品消耗各种资源的影子价格总和，它表示新产品的隐含成本。

5．线性规划问题的灵敏度分析

前面讨论的线性规划问题，我们把系数cj,aij,bi都看成常数，而这些数据，有的是统计值，有的是测量值，有的是专家评估得到的数据，它们并非绝对精确。

如果市场条件发生变化，cj就会随之而变；生产工艺的改进就会导致aij的变化；资源投入后的经济效果会影响bi的取值。由此引出如下两个方面的问题：

（1） 这些数据中的一个或几个发生变化时，已求得的线性规划问题的最优解会发生怎样的变化？ （2） 这些系数在什么范围内变化时，线性规划问题的最优解或最优基保持不变。

灵敏度分析就是讨论当系数发生变化时，最优解的变化情况。 1）目标函数中的价值系数cj发生变化： ① cj对应的决策变量为非基变量

当cj从cj变化到cj时，最终单纯形表中变化的只有xj的检验数，?j变为?j?cj?CBB?1Pj 如果仍有?j?0，则原最优解保持不变；如果?j?0，则需要使用单纯形法继续迭代。

② cj对应的决策变量为基变量 12

当cj从cj变化到cj时，由此引起CB的变化，变为CB，最终单纯形表中所有非基变量的检验数都发生变化（基变量的检验数还是0），变为?N?CN?CBB?1N.

如果检验数不满足最优性条件，则需从修改的单纯表出发，继续进行单纯形迭代。 2）约束条件右端常数项列向量b发生变化：

当常数项列向量由b变为b时，最终单纯形表中发生变化的只有常数项列向量，从B?1b变为B?1b，如果B?1b?0，则原最优基不变，最优值变为CBB?1b；如果B?1b中有分量小于0，则需将B?1b修改成B?1b后，使

用对偶单纯形法继续迭代。

例 已知某工厂生产甲、乙两种产品，用线性规划方法来确定最优生产方案。根据产品的单位售价和生产这些产品的三种资源供应限量，建立了如下线性规划模型：

maxs?tZ?5x1?4x2x1?3x2?902x1?x2?80x1?x2?45x1,x2?0收益或产值（资源1）（资源2)（资源3) 其最优单纯形表如下：

?J CB XB 5 4 0 0 0 B?1b x1 0 1 0 0 x2 0 0 1 0 x3 1 0 0 0 x4 2 1 x5 ?5 25 35 10 Z*?215 0 5 4 x3 x1 x2 ?j ?1 2 ?1 ?1 ?3 1）当c1在什么范围内变化时，原有最优解保持不变； 2）当b2在什么范围内变化时，原有最优基保持不变。

线性规划的最优化模型

一. 货机装运问题

某架货机有三个货舱：前舱、中舱、后舱。三个货舱所能装载的最大重量和体积都有限制。为了保持飞机

的平衡，三个货舱中实际装载货物的重量与其最大容许重量成比例。 重量限制（吨） 体积限制（米3） 前舱 中舱 后舱 10 16 8 6800 8700 5300 现有四类货物供该货机本次飞行装运，其有关信息如下表。 货物1 重量（吨） 空间（米3吨） 利润（元吨） 18 480 3100 货物2 15 650 3800 货物3 23 580 3500 货物4 12 390 2850 应如何安排装运，使该货机本次飞行获利最大？ 二. 模型假设：

1）每种货物可以分割成任意小；

2）每种货物可以在一个或多个货舱中任意分布； 3）多种货物可以混装，并保证不留空隙。

三. 符号说明：

xij：表示第i种货物装入第j个货舱的重量

Z：货机本次飞行所获利润

四. 模型分析：

本问题可建立成线性规划模型，其目标函数是货机本次飞行所获的总利润Z达到最大，其中

Z?3100(x11?x12?x13)?3800(x21?x22?x23)?3500(x31?x32?x33)?2850(x41?x42?x43) 约束条件有：1）供装载的四种货物的总重量约束

x11?x12?x13?18 ，x21?x22?x23?15 ，x31?x32?x33?23 ，x41?x42?x43?12

2）三个货舱的重量限制

x11?x21?x31?x41?10 ，x12?x22?x32?x42?16 ，x13?x23?x33?x43?8

3）三个货舱的空间限制

480x11?650x21?580x31?390x41?6800 ，480x12?650x22?580x32?390x42?8700

480x13?650x23?580x33?390x43?5300

4）三个货舱装入重量的平衡约束

x11?x21?x31?x41?x12?x22?x32?x42?x13?x23?x33?x4310168 五. 模型求解：

用LINDO求解如下：

max 3100x11+3100x12+3100x13+3800x21+3800x22+3800x23 +3500x31+3500x32+3500x33+2850x41+2850x42+2850x43 subject to

x11+x12+x13<=18 x21+x22+x23<=15 x31+x32+x33<=23 x41+x42+x43<=12 x11+x21+x31+x41<=10 x12+x22+x32+x42<=16 x13+x23+x33+x43<=8

480x11+650x21+580x31+390x41<=6800 480x12+650x22+580x32+390x42<=8700 480x13+650x23+580x33+390x43<=5300 8x11+8x21+8x31+8x41-5x12-5x22-5x32-5x42=0 x12+x22+x32+x42-2x13-2x23-2x33-2x43=0

end

14

将文件存储并命名后，选择菜单“Solve”，并对提示“DO RANGE (SENSITIVITY) ANALYSIS”（灵敏度分析）回答“是”或“否”。即可得到如下输出结果。

LP OPTIMUM FOUND AT STEP 7 OBJECTIVE FUNCTION VALUE 1) 121515.8

VARIABLE VALUE REDUCED COST X11 0.000000 400.000000 X12 0.000000 57.894737 X13 0.000000 400.000000 X21 10.000000 0.000000 X22 0.000000 239.473679 X23 5.000000 0.000000 X31 0.000000 0.000000 X32 12.947369 0.000000 X33 3.000000 0.000000 X41 0.000000 650.000000 X42 3.052632 0.000000 X43 0.000000 650.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 18.000000 0.000000 3) 0.000000 300.000000 4) 7.052631 0.000000 5) 8.947369 0.000000 6) 0.000000 0.000000 7) 0.000000 5453.289551 8) 0.000000 0.000000 9) 300.000000 0.000000 10) 0.000000 3.421053 11) 310.000000 0.000000 12) 0.000000 437.500000 13) 0.000000 -1750.000000 NO. ITERATIONS= 7

RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X11 3100.000000 400.000000 INFINITY X12 3100.000000 57.894844 INFINITY X13 3100.000000 400.000000 INFINITY X21 3800.000000 INFINITY 0.000000 X22 3800.000000 239.473801 INFINITY X23 3800.000000 0.000000 239.473801 X31 3500.000000 0.000000 INFINITY X32 3500.000000 2656.730713 122.222427 X33 3500.000000 239.473801 0.000000 X41 2850.000000 650.000000 INFINITY X42 2850.000000 650.000000 110.000221 X43 2850.000000 650.000000 INFINITY

15

RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 18.000000 INFINITY 18.000000 3 15.000000 3.000000 5.000000 4 23.000000 INFINITY 7.052631 5 12.000000 INFINITY 8.947369 6 10.000000 INFINITY 0.000000 7 16.000000 0.000000 1.000000 8 8.000000 INFINITY 0.000000 9 6800.000000 INFINITY 300.000000 10 8700.000000 11 5300.000000 12 0.000000 13 0.000000

580.000000 INFINITY 0.000000 6.000000 1700.000000 310.000000 24.000000 0.000000

16

第二部分 运输问题

1．运输问题的一般提法

设有m个产地A1,A2,?,Am，将生产的物资联合运往n个销地B1,B2,?,Bn；各产地Ai的产量为ai，各销地Bj的销量为bj；从Ai产地到Bj销地的单位运价为cij，问如何组织运输，可使总的运费最少？ 如果总的产量

?ai?1mi?总的销量

?bj?1nj，则称它为产销平衡运输问题

2．产销平衡运输问题的数学模型

引入决策变量：用xij表示从Ai产地运到Bj销地的物资数量

确定目标函数：使总运输费用最少，即 minZ???ci?1j?1mnijxij

写出约束条件：从Ai产地运出的物资数量应等于Ai产地的物资供应量

即

?xj?1nij?ai ， i?1,2,?,m

运到Bj销地的物资数量应等于Bj销地的需求量，

即

?xi?1mij?bj ，j?1,2,?,n ；xij取值非负。

说明：① 运输问题是一线性规划问题； ② xij?ai?bjd（其中d??a??bii?1j?1mnj）是运输问题的一个可行解，从而它有基本可行解；

又xij?minai,bj，故运输问题的任一可行解都是有限的，即可行域有界；因此运输问题必有有限

最优解且最优解同样可在基本可行解处得到。

③ 针对m个产地n个销地的产销平衡运输问题，其约束条件中共有m?n个方程，但这m?n个方程中，

任一方程都可以通过其余m?n?1方程得到。因此真正有效的方程个数是m?n?1个，我们可以将多余的一个方程划掉。这样以来，运输问题的基本可行解中只含m?n?1个基变量。

④ 当m和n取值较大时，引入的决策变量较多，采用表格单纯形法计算量较大，通常采用表上作业法求解运输问题。

??3．求初始调运方案（初始基本可行解）

1）左上角方法：从表格中左上角方格所对应的决策变量开始分配运输量，分配时让它取尽可能大的取值。 2）最小元素法：从表格中最小单位运价所对应的决策变量开始分配运输量，分配时让它取尽可能大的取值。 3）沃格尔（Vogel）法：

（ⅰ）首先计算每一行和每一列的次小单位运价与最小单位运价之间的差值，并分别称之为相应的行罚

数和列罚数；

（ⅱ）将各行的行罚数写在运输表格的右侧一列，将各列的列罚数写在运输表格下侧一行；

（ⅲ）确定最大罚数值所在的行或列，从该行或该列最小单位运价所对应的决策变量开始

分配运输量，分配时让它取尽可能大的取值。

17

销地 产地 B1 2 1 8 B2 9 3 4 B3 10 4 2 B4 7 2 5 供应量 9 5 7 21 21 A1 A2 A3 需求量 3 8 4 6 分配完之后，划掉表格中的一行或一列，得新的运输表格，再重复上述步骤。

用以上三种方法得到的初始基本可行解，它们对应的目标函数值，以沃格尔法为最小，最小

元素法次之，以左上角方法为最大。

4．最优方案的判别及调运方案的改进

（1） 闭回路概念

凡是能排成如下形式的变量集合 xi1j1,xi1j2,xi2j2,xi2j3,xi3j3,xi3j4,?,xisjs,xisj1

（其中i1,i2,?,is互不相同，j1,j2,?,js也互不相同）就称为一个闭回路。

闭回路中出现的变量称为闭回路的顶点，相邻两个顶点的连线称为闭回路的边。 现将闭回路的顶点在运输表格中画出来，同时将相邻顶点用直线段连接起来，就可以得到一条封

闭折线。

闭回路的特点：ⅰ）表中的各行各列至多只有闭回路的两个顶点； ⅱ）闭回路的边要么是水平的，要么是铅直的。

（2） 用闭回路方法计算非基变量的检验数 以非基变量xij所在的方格为起点，作一闭回路；（除起点xij之外，要求闭回路的其它顶点必须

是基变量）然后在闭回路上作运输量是一个单位的调整，并计算由此引起的总运费的改变量。

该改变量称为非基变量xij的检验数。

销地 产地 B1 2 ③ 1 ⑤ B2 9 B3 10 B4 7 ① 4 2 ⑤ 2 5 供应量 9 5 7 21 21 A1 A2 A3 需求量 ?3 3 ?4 8 ?1 4 ③ 8 ?2 ④ 4 ?11 3 ?3 6 （3） 最优调运方案的判别准则

如果所有非基变量的检验数全都?0，则此时的调运方案便是最优方案。

（4） 调运方案的改进

以最小负检验数所在的方格为起点，作一闭回路(除起点之外，要求闭回路的其它顶点必须是基

变量)；然后在闭回路上作运输量尽可能大的调整（调整量为负号格中的最小运输量）。

18

5．用位势法计算非基变量的检验数

对于m个产地n个销地的运输问题

（1） 引入m?n个待定变量R1,R2,?,Rm和K1,K2,?,Kn，并将Ri写在产地Ai的左边，将Kj写在销

地Bj的上方；

（2） 待定变量Ri和Kj的取值满足如下方程组

基变量所在方格(s,t)的单位运价Cst?该行的行位势Rs?该列的列位势Kt

由于基本可行解中只有m?n?1个基变量，故方程组中只有m?n?1个方程，但却有m?n未知量，

因此方程组有无穷多组解，一般我们取R1?0的这组解。

（3） 非基变量xrl的检验数?rl?Crl?Rr?Kl

6．产销不平衡运输问题

（1）总产量大于总销量

处理方法：ⅰ）虚设一个销地；ⅱ）虚设销地的需求量等于总产量减去总销量； ⅲ）各产地到虚设销地的单位运价设为零。（属于物资就地存储） （2）总产量小于总销量

处理方法：ⅰ）虚设一个产地；ⅱ）虚设产地的供应量等于总销量减去总产量；

ⅲ）虚设产地到各销地的单位运价设为零。（属于缺货情形）

7．需求分两种情形的运输问题

设有三个化肥厂供应四个地区的农用化肥。假定等量的化肥在这些地区的使用效果相

同，已知各化肥厂的年产量、各地区的需求量以及各化肥厂到各地区的运价如下表： 试决定使总运费最省的化肥调拨方案。

需求地区 化肥厂 A B C 最低需求量（万吨） 最高需求量（万吨） Ⅰ Ⅱ Ⅲ Ⅳ 16 13 22 17 14 13 19 15 19 20 23 — 30 70 0 10 50 70 30 不限 产量（万吨） 50 60 50

（1）第Ⅳ地区每年最多可以分到的化肥数量

三个化肥厂每年的总产量为160万吨，其它三个地区每年的最低需求必须得到满足，所以第Ⅳ地区

每年最多可以分到的化肥数量为160?(30?70?0)?60万吨； （2）按最高需求量建立产销平衡运输问题，此时最高需求量为50?70?30?60?210?总产量160万吨，所

以要虚设一个产地D，虚设产地的产量为210?160?50万吨；

（3）有两种需求的地区当做两个地区来对待。其中第一地区的需求量为最低需求部分，它必须得到满足，故

它不能由虚设产地D供应，因此产地D到它的单位运价设为M（M是一个很大的正数）。

第二地区的需求量为该地区的额外需求部分（最高需求量减去最低需求量），有条件时可以得到满

足，产地D到它的单位运价定为零。

19

销地 产地 A B C 虚设D 需求量

1? 16 14 19 30 M 20 1?? 16 50 14 20 19 0 0 2 13 13 20 M 30 3 22 19 10 23 0 4? 17 15 30 M M 20 4?? 17 15 M 0 产量 50 60 50 50 210 210 30 20 70 30 10 50 8．可化为运输问题的其它线性规划问题

由于表上作业法比单纯形算法简单，所以人们常常尽可能地将线性规划问题转化成运输问题。 例题 生产计划问题

某厂按合同规定须于每个季度末分别完成10，15，25，20台同一规格柴油机。已知该厂各季度生产能力及生产每台柴油机成本如下表。又如果生产出来的柴油机当季度不交货，每台每积压一个季度需储存、维护费用0.15万元。要求在完成合同的条件下，制定使该厂全年生产、储存和维护费用为最少的决策方案。

季 度 生产能力（台） 单台成本（万元） 线性规划模型： 用xij表示第i季度生产用于第j季度交货的柴油机台数 由于每季度生产能力的限制，有约束

?x11?x12?x13?x14?x22?x23?x24? ?x33?x34??x44??25?35?30?10Ⅰ 25 10.8 Ⅱ 35 11.1 Ⅲ 30 11.0 Ⅳ 10 11.3

由合同要求，必须满足

x11?10??x12?x22?15? ?

x?x?x?25132333???x14?x24?x34?x44?20 第i季度生产用于第j季度交货的每台柴油机，它的实际成本cij是由生产成本cij和储存维护费用两部分组成，具体数值如下表

i j Ⅰ Ⅱ Ⅲ Ⅳ Ⅰ 10.8 Ⅱ 10.95 11.1 Ⅲ 11.1 11.25 11.0 Ⅳ 11.25 11.4 11.15 11.3

目标函数为：minZ?10.8x11?10.95x12?11.1x13?11.25x14?11.1x22?11.25x23 ?11.4x24?11.0x33?11.15x34?11.3x44

从上述模型可以看到，在保证xij?0(i?j)的条件下，上述模型类似于总产量大于总销量的产销不平衡运输问题的线性规划模型。 销地 产地 Ⅰ Ⅱ Ⅲ Ⅳ

Ⅰ 10.8 M M M Ⅱ 10.95 11.1 M M Ⅲ 11.1 11.25 11.0 M Ⅳ 11.25 11.4 11.15 11.3 虚设Ⅴ 0 0 0 0 运输问题的最优化模型

一. 自来水输送问题

某市有甲、乙、丙、丁四个居民区，自来水由A、B、C三个水库供应。四个区每天必须得到保证的基本生活用水量分别为30，70，10，10千吨，但由于水源紧张，三个水库每天最多只能分别供应50，60，50千吨自来水。由于地理位置的差别，自来水公司从个水库向各区送水所需付出的引水管理费不同（见下表，其中C水库与丁区之间没有输水管道），其他管理费用都是450元/千吨。根据公司规定，各区用户按照统一标准900元/千吨收费。此外，四个区都向公司申请了额外用水量，分别每天50，70，20，40千吨。该公司应如何分配供水量，才能获利最多？

为了增加供水量，自来水公司正在考虑进行水库改造，使三个水库每天的最大供水量都提高一倍，问那时供水方案应如何改变？公司利润可增加多少？

引水管理费（元/千吨） A B C 甲 160 140 190 乙 130 130 200 丙 220 190 230 丁 170 150 / 二. 模型假设： 1）水在流经途中的损失可以忽略不计；

2）各居民区对水的需求量完全服从自来水公司的调配安排； 3）所有供水设施都能正常使用.

三. 符号说明：

xij：水库i向j居民区的日供水量 Z：自来水公司每日的引水管理费用 W：自来水公司每日所获的利润

四. 模型分析：

（1）分配供水量就是安排从三个水库向四个区送水的方案，目标是获利最多。 （2）从题目给出的数据可知，三个水库的供水量为160千吨；

四个区的基本生活用水量与额外用水量之和为300千吨，所以自来水公司的水能全部卖出并能获利。 （3）自来水公司的总收入为 900?(50?60?50)?14400元------与送水方案无关 0 公司每天的其它管理费用为 450?(50?60?50)?72000元-----与送水方案无关

（4）想使利润最大，只需使引水管理费最小。

（5）按最高需求量建立产销平衡运输问题，此时最高需求量为300?总供应量160万吨，所以要虚设一个

水库D，虚设水库的供水量为300?160?140万吨； 21

（6）有两种需求的居民区当做两个区来对待。其中第一区的需求量为基本生活用水量，它必须得到满足，

故它不能由虚设产地D供应，因此产地D到它的单位运价设为M（M是一个很大的正数）。

第二区的需求量为该区的额外需求用水量（最高需求量减去最低需求量），有条件时可以得到满足，

产地D到它的单位运价定为零。

五. 模型建立：

由以上分析可知，我们可以建立该问题运输问题模型如下 居民区 水库 A B C 虚设D 需求量 甲1 甲2 乙1 乙2 丙1 丙2 丁1 丁2 产量 50 60 50 140 300 300 160 140 190 M 160 140 190 0 130 130 200 M 130 130 200 0 220 190 230 M 10 220 190 230 0 170 150 M M 170 150 M M 30 50 70 70 20 10 40 六. 模型求解 采用运输问题的表上作业法，可得自来水公司的供水方案如下：

A水库向乙区供水50千吨 ；B水库向乙、丁区分别供水50，10千吨 ；

C水库向甲、丙分别供水40、10千吨 。 引水管理费用为 24400元

我们也可以建立该问题的线性规划模型如下：

确定目标函数：引水管理费用最小。

minZ?160x11?130x12?220x13?170x14?140x21?130x22?190x23?150x24?190x31?200x32?230x33

由于C水库与丁区之间没有输水管道，故x34?0

写出约束条件：约束条件有两类（一类是水库的供应量限制，另一类是各区的需求量限制）

由于供水量能全部卖出，故有如下供水量限制：

A水库供给四个区的总供水量x11?x12?x13?x14应等于A水库的日供应量50千吨

x11?x12?x13?x14?50 ；x21?x22?x23?x24?60 ；x31?x32?x33?50

需求量限制可表示为 30?x11?x21?x31?80

70?x12?x22?x32?140 ；10?x13?x23?x33?30 ；10?x14?x24?50 所有决策变量的非负限制 xij?0 用LINDO求解如下：

min 160x11+130x12+220x13+170x14+140x21+130x22+190x23+150x24+190x31+200x32+230x33 Subject to

x11+x12+x13+x14=50 x21+x22+x23+x24=60 x31+x32+x33=50 x11+x21+x31<=80

x11+x21+x31>=30 22

x12+x22+x32<=140 x12+x22+x32>=70 x13+x23+x33<=30 x13+x23+x33>=10 x14+x24<=50 x14+x24>=10 end

将文件存储并命名后，选择菜单“Solve”，并对提示“DO RANGE (SENSITIVITY) ANALYSIS”（灵敏度分析）回答“是”或“否”。即可得到如下输出结果。

LP OPTIMUM FOUND AT STEP 13 OBJECTIVE FUNCTION VALUE 1) 24400.00

VARIABLE VALUE REDUCED COST X11 0.000000 30.000000 X12 50.000000 0.000000 X13 0.000000 50.000000 X14 0.000000 20.000000 X21 0.000000 10.000000 X22 50.000000 0.000000 X23 0.000000 20.000000 X24 10.000000 0.000000 X31 40.000000 0.000000 X32 0.000000 10.000000 X33 10.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -130.000000 3) 0.000000 -130.000000 4) 0.000000 -190.000000 5) 40.000000 0.000000 6) 10.000000 0.000000 7) 40.000000 0.000000 8) 30.000000 0.000000 9) 20.000000 0.000000 10) 0.000000 -40.000000 11) 40.000000 0.000000 12) 0.000000 -20.000000 NO. ITERATIONS= 13

RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X11 160.000000 INFINITY 30.000000 X12 130.000000 20.000000 INFINITY X13 220.000000 INFINITY 50.000000 X14 170.000000 INFINITY 20.000000 X21 140.000000 INFINITY 10.000000 X22 130.000000 10.000000 20.000000 X23 190.000000 INFINITY 20.000000

X24 150.000000 20.000000 20.000000 23

X31 190.000000 10.000000 20.000000 X32 200.000000 INFINITY 10.000000 X33 230.000000 20.000000 40.000000 RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 40.000000 30.000000 3 60.000000 40.000000 30.000000 4 50.000000 40.000000 10.000000 5 80.000000 INFINITY 40.000000 6 30.000000 10.000000 INFINITY 7 140.000000 INFINITY 40.000000 8 70.000000 30.000000 INFINITY 9 30.000000 INFINITY 20.000000 10 10.000000 10.000000 10.000000 11 50.000000 INFINITY 40.000000 12 10.000000 30.000000 10.000000

七. 进一步讨论：

如果A、B、C三个水库每天的最大供水量都提高一倍，则公司总供水能力为每天320千吨，大于每天的总需求量300千吨，此时水库供水量不能全部卖出，因而不能将获利最多问题转化成引水管理费用为最少的问题。

为此我们首先计算A、B、C三个水库分别向甲、乙、丙、丁四个区供应每千吨水的净利润，即从收入900元中减去其它管理费用450元，再减去引水管理费，得下表 净利润（元/千吨） A B C 甲 乙 丙 丁 290 320 230 280 310 320 260 300 260 250 220 / 目标函数为：maxW?290x11?320x12?230x13?280x14?310x21?320x22?260x23? 300x24?260x31?250x32?220x33 由于供水量不能全部卖出，所以供水量限制改为：

x11?x12?x13?x14?100 ；x21?x22?x23?x24?120 ；x31?x32?x33?100

由于每个区的供水需求量都能完全满足，故需求量限制可改为

x11?x21?x31?80 ；x12?x22?x32?140 ；x13?x23?x33?30 ；x14?x24?50 用LINDO求解如下：

max 290x11+320x12+230x13+280x14+310x21+320x22+260x23+300x24+260x31+250x32+220x33 subject to

x11+x12+x13+x14<=100 x21+x22+x23+x24<=120 x31+x32+x33<=100 x11+x21+x31=80 x12+x22+x32=140 x13+x23+x33=30 x14+x24=50 end

将文件存储并命名后，选择菜单“Solve”，并对提示“DO RANGE (SENSITIVITY) ANALYSIS” 24

（灵敏度分析）回答“是”或“否”。即可得到如下输出结果。

LP OPTIMUM FOUND AT STEP 11 OBJECTIVE FUNCTION VALUE 1) 88700.00

VARIABLE VALUE REDUCED COST X11 0.000000 20.000000 X12 100.000000 0.000000 X13 0.000000 40.000000 X14 0.000000 20.000000 X21 30.000000 0.000000 X22 40.000000 0.000000 X23 0.000000 10.000000 X24 50.000000 0.000000 X31 50.000000 0.000000 X32 0.000000 20.000000 X33 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 50.000000 3) 0.000000 50.000000 4) 20.000000 0.000000 5) 0.000000 260.000000 6) 0.000000 270.000000 7) 0.000000 220.000000 8) 0.000000 250.000000 NO. ITERATIONS= 11

RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES

VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X11 290.000000 20.000000 INFINITY X12 320.000000 INFINITY 20.000000 X13 230.000000 40.000000 INFINITY X14 280.000000 20.000000 INFINITY X21 310.000000 20.000000 10.000000 X22 320.000000 20.000000 20.000000 X23 260.000000 10.000000 INFINITY X24 300.000000 INFINITY 20.000000 X31 260.000000 10.000000 20.000000 X32 250.000000 20.000000 INFINITY X33 220.000000 INFINITY 10.000000 RIGHTHAND SIDE RANGES

ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 100.000000 40.000000 20.000000 3 120.000000 50.000000 20.000000 4 100.000000 INFINITY 20.000000 5 80.000000 20.000000 50.000000 6 140.000000 20.000000 40.000000

7 30.000000 20.000000 30.000000 25

4 0.000000 9.600000 5 500.0000 0.000000 6 1500.000 0.000000 7 0.000000 -0.3200000E-02 8 0.000000 -0.7200000E-02 9 500.0000 0.000000 10 500.0000 0.000000 11 500.0000 0.000000

注意LINGO软件的输入形式

① 程序以”Model：”开始，每行最后加“；”，并以“end”结束； ② 非负约束可以省略，但乘号*不能省略； ③ 式中可以有括号，右端也可以有数学符号。

求解方法Ⅱ 引入0?1变量，用z1?1表示以10千元吨的价格采购原油A ，用z1?0表示不以价格10千元吨采购原油A；用z2?1表示以8千元吨的价格采购原油A ，用z2?0表示不以价格8千元吨采购原油A；用z3?1表示以6千元吨的价格采购原油A ，用z3?0表示不以价格6千元吨采购原油A；

于是非线性约束(y1?500)y2?0和(y2?500)y3?0可用线性约束表示则为：

500z2?y1?500z1 ；500z3?y2?500z2 ；y3?500z3 ； z1,z2,z3?0或1

(z1,z2,z3)的所有可能取值组合为

(0,0,0)，(1,0,0)，(0,1,0)，(0,0,1)，(1,1,0)，(1,0,1)，(0,1,1)，(1,1,1)；

其中(z1,z2,z3)?(0,0,0)，对应y1?y2?y3?0

(z1,z2,z3)?(1,0,0)，对应0?y1?500,y2?y3?0 (z1,z2,z3)?(1,1,0)，对应y1?500,0?y2?500,y3?0

(z1,z2,z3)?(1,1,1)，对应y1?500,y2?500,0?y3?500， 其它各组取值不成立。 用LINDO求解时，直接输入

max 4.8x1+5.6x2+4.8x3+5.6x4-10y1-8y2-6y3 st x1-x3>0 2x2-3x4>0

x1+x2-y1-y2-y3<500 x3+x4<1000 y1+y2+y3<1500 y1<500 y2<500 y3<500 y1-500z1<0 y1-500z2>0 y2-500z2<0 y2-500z3>0

y3-500z3<0 36

end

int z1 int z2

int z3

将文件存储并命名后，选择菜单“Solve”，运行该程序。 OBJECTIVE FUNCTION VALUE 1) 5000.000

VARIABLE VALUE REDUCED COST Z1 1.000000 0.000000 Z2 1.000000 2200.000000 Z3 1.000000 1200.000000 X1 0.000000 0.800000 X2 1500.000000 0.000000 X3 0.000000 0.800000 X4 1000.000000 0.000000 Y1 500.000000 0.000000 Y2 500.000000 0.000000 Y3 0.000000 0.400000

ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 0.000000 4) 0.000000 5.600000 5) 0.000000 5.600000 6) 500.000000 0.000000 7) 0.000000 0.000000 8) 0.000000 0.000000 9) 500.000000 0.000000 10) 0.000000 0.000000 11) 0.000000 -4.400000 12) 0.000000 0.000000 13) 0.000000 -2.400000 14) 500.000000 0.000000 NO. ITERATIONS= 33

BRANCHES= 2 DETERM.= 1.000E 0

例5 合理下料问题

某钢管零售商从钢管厂进货，然后将钢管按照顾客的要求切割后售出，从钢管厂进货时，每根钢管的长度都是19米。

① 现在有一客户需要50根4米、20根6米、15根8米的钢管，应如何下料最节省？

② 零售商如果采用的不同切割方式太多，将会导致生产过程的复杂化，从而增加生产和管理成本，所以该零售商规定采用的不同切割方式不能超过3种。此外，该客户除需要①中的三种钢管外，还需要10根5米的钢管，应如何下料最省？ 第一问求解：

首先确定每根原料钢管的下料方式 下料方式 4米长的根数 6米长的根数 8米长的根数 余料长度 1 4 0 0 3 2 3 1 0 1 3 2 0 1 3 4 1 2 0 3 5 1 1 1 1 6 0 3 0 1 7 0 0 2 3 数学模型：用xj表示第j种下料方式所下钢管的根数； 目标函数：使切割后总的余料长度最少。

minZ?3x1?x2?3x3?3x4?x5?x6?3x7st4x1?3x2?2x3?x4?x5?50 x2?2x4?x5?3x6?20

x3?x5?2x7?15x1,x2,?,x7?0且为整数用LINDO软件求解时，直接输入：

min 3x1+x2+3x3+3x4+x5+x6+3x7 st

4x1+3x2+2x3+x4+x5>=50 x2+2x4+x5+3x6>=20 x3+x5+2x7>=15 end gin 7

保存并命名后，按“solve”，得如下结果：

OBJECTIVE FUNCTION VALUE

1) 27.00000

VARIABLE VALUE REDUCED COST X1 0.000000 3.000000 X2 12.000000 1.000000 X3 0.000000 3.000000 X4 0.000000 3.000000 X5 15.000000 1.000000 X6 0.000000 1.000000 X7 0.000000 3.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 1.000000 0.000000 3) 7.000000 0.000000 4) 0.000000 0.000000

NO. ITERATIONS= 11

BRANCHES= 1 DETERM.= 1.000E 0

目标函数：使切割原料钢管的总根数最少。

minZ?x1?x2?x3?x4?x5?x6?x7st4x1?3x2?2x3?x4?x5?50 x2?2x4?x5?3x6?20

x3?x5?2x7?15x1,x2,?,x7?0且为整数 用LINDO软件求解时，直接输入： min x1+x2+x3+x4+x5+x6+x7

st

4x1+3x2+2x3+x4+x5>=50 x2+2x4+x5+3x6>=20 x3+x5+2x7>=15 end

gin 7 38

保存并命名后，按“solve”，得如下结果： OBJECTIVE FUNCTION VALUE

1) 25.00000

VARIABLE VALUE REDUCED COST X1 0.000000 1.000000 X2 15.000000 1.000000 X3 0.000000 1.000000 X4 0.000000 1.000000 X5 5.000000 1.000000 X6 0.000000 1.000000 X7 5.000000 1.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.000000 3) 0.000000 0.000000 4) 0.000000 0.000000

NO. ITERATIONS= 5

BRANCHES= 0 DETERM.= 1.000E 0 第二问求解：

将一根长为19米的原料钢管，切割成4米、5米、6米、8米长的小段，有许多种切割方式，按要求，我们只能从全部的切割方式中选取其中的三种。

用xi表示采用第i种切割方式切割原料钢管的根数。i?1,2,3.

用第i种切割方式切割一根长为19米的原料钢管时，得到4米长的小段钢管有yi1根，得到5米长的小段钢管有yi2根，得到6米长的小段钢管有yi3根、得到8米长的小段钢管有yi4根；i?1,2,3.

目标函数是：在满足顾客要求的条件下，使切割原料钢管的总根数最少。 minZ?x1?x2?x3

约束条件：① 用第1种方式切割原料钢管x1根，用第2种方式切割原料钢管x2根，用第3种方式切割原料钢管x3根，得到4米长的小段钢管总数为x1?y11?x2?y21?x3?y31，它应该≥50，才能满足顾客需求，因此有：x1?y11?x2?y21?x3?y31?50

x1?y12?x2?y22?x3?y32?10 同理有：x1?y13?x2?y23?x3?y33?20

x1?y14?x2?y24?x3?y34?15 ② 一根长为19米的原料钢管，按第一种方式切割，得到y11根4米长的、y12根5米长的、y13根6米长的、；同理有：y14根8米长的，故有 4y11?5y12?6y13?8y14?19（即它们的总长度不能超过19米）4y21?5y22?6y23?8y24?19 ，4y31?5y32?6y33?8y34?19 .

③ 无论采用何种切割方式切割原料钢管，每根原料钢管在切割后所剩下的余料长度最长为3米，也就是说每根原料钢管至少有16米被派上用场。因此我们有：

4y11?5y12?6y13?8y14?16，4y21?5y22?6y23?8y24?16，4y31?5y32?6y33?8y34?16 . 39

④ 4米长50根，5米长10根，6米长20根，8米长15根；相加起来可得顾客所需钢管的总长度为490米，由于每根原料钢管的长度为19米，所以至少49019?25.789根原料钢管，即至少需要25根原料钢管，因此有：x1?x2?x3?25

⑤ 4米长的需要50根：每根原料钢管可以切割出4根4米长的，所以切割13根原料钢管就能满足要求； 5米长的需要10根：每根原料钢管可以切割出3根5米长的，所以切割4根原料钢管就能满足要求； 6米长的需要20根：每根原料钢管可以切割出3根6米长的，所以切割7根原料钢管就能满足要求； 8米长的需要15根：每根原料钢管可以切割出2根8米长的，所以切割8根原料钢管就能满足要求； 由上面的分析可知，要满足顾客的要求，最多切割(13?4?7?8)?32根原料钢管，因此我们有：x1?x2?x3?32

⑥ 由于3种切割方式的排列顺序没有要求，因此约束条件x1?x2?x3对最优结果没有影响。我们可以加上该约束（因为约束条件越多，问题的可行域就越小，从而减少了可行解的搜索范围，这样就可以减少求解过程的运行时间）。

本题为整数非线性规划模型 用LINGO软件求解时，直接输入：

model:

min=x1+x2+x3;

x1*y11+x2*y21+x3*y31>=50; x1*y12+x2*y22+x3*y32>=10; x1*y13+x2*y23+x3*y33>=20; x1*y14+x2*y24+x3*y34>=15; 4*y11+5*y12+6*y13+8*y14<=19; 4*y21+5*y22+6*y23+8*y24<=19; 4*y31+5*y32+6*y33+8*y34<=19; 4*y11+5*y12+6*y13+8*y14>=16; 4*y21+5*y22+6*y23+8*y24>=16; 4*y31+5*y32+6*y33+8*y34>=16; x1+x2+x3<=32; x1+x2+x3>=26; x1>=x2; x2>=x3;

@gin(x1);@gin(x2);@gin(x3); @gin(y11);@gin(y21);@gin(y31); @gin(y12);@gin(y22);@gin(y32); @gin(y13);@gin(y23);@gin(y33); @gin(y14);@gin(y24);@gin(y34); end

保存并命名后，按“solve”，得如下结果：

Local optimal solution found at iteration: 28738 Objective value: 28.00000

Variable Value Reduced Cost X1 10.00000 0.000000 X2 10.00000 2.000000 X3 8.000000 1.000000 Y11 3.000000 0.000000

Y21 2.000000 0.000000 40

本文来源：https://www.bwwdw.com/article/whjv.html