规划问题求解与EXCEL应用.doc

培训与发展
Training & Development

2005年专刊2
（总第34期）

国家发展和改革委员会培训中心 2005年6月30日

规划问题求解与EXCEL应用

目　　录

第一节 EXCEL中的规划求解工具………………………………(2)
第二节 线性规划求解方法…………………………………………(7)
第三节 对偶问题与影子价格……………………………………(23)
第四节 线性规划的敏感度分析 ………………………………(28)
第五节 整数规划求解………………………………………………(32)
第六节 非线性规划求解……………………………………………(33)
第七节 目标规划问题求解………………………………………(37)

规划问题求解与EXCEL应用
国家发展改革委培训中心委机关培训部编写

1939年，前苏联科学家康托洛维奇总结了他对生产组织的研究，写出了《生产组织与计划中的数学方法》一书，是线性规划应用于工业生产问题的经典著作。1947年，丹齐格提出了单纯形方法后，线性规划便迅速形成了一个独立的理论分支。此后，整数规划、目标规划、非线性规划理论逐渐形成并成熟。
微软在EXCEL中开发的“规划求解”工具是以单纯形方法为基础的，使用起来比较方便。另外，芝加哥LINDO公司研制的Lindo软件在解决线性规划模型、整数规划模型、二次规划模型等方面功能比较强大。但目前尚无汉化版，需要学习者，可从LINDO公司的网址免费下载教学演示软件，如果要得到功能全面的软件，必须购买正版软件。
我们组织编写的《经济计量分析与EXCEL应用》一书，对“规划求解”略有介绍。由于规划理论是经济学中的一种重要方法，规划求解在实际经济管理和管理决策中应用广泛，我们特编一个参阅材料，仅供参考。

第一节 EXCEL中的规划求解工具

EXCEL中的规划求解工具设置了4个对话框。有的选项已有默认值，只是需要改变才需要选择。为便于大家选择，我们特将选项作些说明。
一、关于“规划求解参数”对话框

【设置目标单元格】在此指定要设置为特定数值或者最大值或最小值的目标单元格。该单元格必须包含公式。
【等于】在此指定是否希望目标单元格为最大值、最小值或某一特定数值。如果需要指定数值，请在右侧编辑框中键入该值。
【可变单元格】在此指定可变单元格。求解时其中的数值不断调整，直到满足约束条件并且“设置目标单元格”框中指定的单元格达到目标值。可变单元格必须直接或间接地与目标单元格相关联。在“设置目标单元格”框中，输入目标单元格的单元格引用或名称。目标单元格必须包含公式。在“可变单元格”框中，输入每个可变单元格的名称或引用，用逗号分隔不相邻的引用。可变单元格必须直接或间接与目标单元格相联系。最多可以指定 200 个可变单元格。
【推测】单击此按钮，自动推测“设置目标单元格”框中的公式所引用的所有非公式单元格，并在“可变单元格”框中定位这些单元格的引用。
【约束】在此列出了规划求解的所有约束条件。
【添加】显示“添加约束”对话框。
【更改】显示“更改约束”对话框。
【删除】删除选定的约束条件。
【求解】对定义好的问题进行求解。
【关闭】关闭对话框，不进行规划求解。但保留通过“选项”、“添加”、“更改”或“删除”按钮所做的更改。
【选项】显示“规划求解选项”对话框。在其中可加载或保存规划求解模型，并对求解过程的高级属性进行控制。
【全部重设】清除规划求解中的当前设置，将所有的设置恢复为初始值。
二、关于“规划求解选项”对话框

在本对话框中，可以设定规划求解过程的一些高级功能、加载或保存规划求解定义，以及为线性和非线性规划求解定义参数。每一选项都有默认设置，可以满足大多数情况下的要求。
【最长运算时间】在此设定求解过程的时间。可输入的最大值为 32767（秒），默认值 100（秒）可以满足大多数小型规划求解要求。
【迭代次数】在此设定求解过程中迭代运算的次数，限制求解过程的时间。可输入的最大值为 32767，默认值 100 次可满足大多数小型规划求解要求。
【精度】在此输入用于控制求解精度的数字，以确定约束条件单元格中的数值是否满足目标值或上下限。精度值必须表示为小数（0 到 1 之间），输入数字的小数位越多，精度越高。例如，0.0001 比 0.01 的精度高。
【允许误差】在此输入满足整数约束条件并可被接受的目标单元格求解结果与真实的最佳结果间的百分偏差。这个选项只应用于具有整数约束条件的问题。设置的允许误差值越大，求解过程就越快。
【收敛度】在此输入收敛度数值，当最近五次迭代后目标单元格中数值的变化小于“收敛度”框中设置的数值时，“规划求解”停止运行。收敛度只应用于非线性规划求解问题，并且必须表示为小数（0 到 1 之间）。设置的数值越小，收敛度就越高。例如，0.0001 表示比 0.01 更小的相对差别。收敛度越小，“规划求解”得到结果所需的时间就越长。
【采用线性模型】当模型中的所有关系都是线性的，并且希望解决线性优化问题时，选中此复选框可加速求解进程。
【显示迭代结果】如果选中此复选框，每进行一次迭代后都将中断“规划求解”，并显示当前的迭代结果。
【自动按比例缩放】如果选中此复选框，当输入和输出值量级差别很大时，可自动按比例缩放数值。例如，基于百万美元的投资将利润百分比最大化。
【假定非负】如果选中此复选框，则对于在“添加约束”对话框的“约束值”框中没有设置下限的所有可变单元格，假定其下限为 0（零）。
【估计】指定在每个一维搜索中用来得到基本变量初始估计值的逼近方案。
【正切函数】使用正切向量线性外推。
【二次方程】用二次方程外推法，提高非线性规划问题的计算精度。
【导数】指定用于估计目标函数和约束函数偏导数的差分方案。
【向前差分】 用于大多数约束条件数值变化相对缓慢的问题。
【中心差分】 用于约束条件变化迅速，特别是接近限定值的问题。虽然此选项要求更多的计算，但在“规划求解”不能返回有效解时也许会有帮助。

表1　　　　差分公式表
阶数
向前差分公式
向后差分公式
中心差分公式
一阶

二阶

【搜索】指定每次的迭代算法，以确定搜索方向。
【牛顿法】牛顿法的基本思想是利用目标函数f(x)在第三代点xk处的二次Taylor展开作为模型函数，并用这个二次模型函数小点序列去逼近目标函数的极小点。用准牛顿法迭代需要的内存比共轭法多，但所需的迭代次数少。
【共轭法】比牛顿法需要的内存少，但要达到指定精度需要较多次的迭代运算。当问题较大和内存有限，或步进迭代进程缓慢时，可用此选项。
【装入模型】显示“装入模型”对话框，输入对所要加载的模型的引用。
【保存模型】显示“保存模型”对话框，在其中可指定保存模型的位置。只有需要在工作表上保存多个模型时，才单击此命令。第一个模型会自动保存。
三、约束条件

（一）添加约束条件
1.在“规划求解参数”对话框的“约束”下，单击“添加”。
2.在“单元格引用位置”框中，输入需要对其中数值进行约束的单元格引用或单元格区域的名称。
3.单击希望在引用单元格和约束条件之间使用的关系（“<=”、“=”、“>=”、“Int”或“Bin”）。如果单击“Int”，则“约束值”框中会显示“整数”；如果单击“Bin”，则“约束值”框中会显示“二进制”。
4.在“约束值”框中，键入数字、单元格引用或名称，或键入公式。
5.执行下列操作之一：一是若要接受约束条件并要添加其他的约束条件，请单击“添加”；若要接受约束条件并返回“规划求解参数”对话框，请单击“确定”。
6.只能在对可变单元格的约束条件中应用“Int”和“Bin”关系。当“规划求解选项”对话框中的“采用线性模型”复选框被选中时，对约束条件的数量没有限制。对于非线性问题，每个可变单元格除了变量的范围和整数限制外，还可以有多达 100 个约束。
(二)更改或删除约束条件
1.在“规划求解参数”对话框的“约束”下，单击要更改或删除的约束条件。
2.单击“更改”，并进行所需的更改，或单击“删除”。
3.单击“求解”，再执行下列操作之一：若要在工作表中保存求解后的数值，请在“规划求解结果”对话框中，单击“保存规划求解结果”。
4.若要恢复原始数据，请单击“恢复为原值”。
四、关于“规划求解结果”对话框
显示完成消息和最接近的目标求解结果。
【保存规划求解结果】单击此选项，接受求解结果，并将其放置到可变单元格中。
【恢复为原值】单击此选项可在可变单元格中恢复初始值。
【报告】创建指定类型的报告，并将每份报告放置于工作簿中单独的一张工作表上。
【运算结果报告】列出目标单元格和可变单元格及其初始值和最终结果、约束条件以及有关约束条件的信息。
【敏感性报告】提供有关求解结果对“规划求解参数”对话框的“目标单元格”框中所指定的公式的微小变化或约束条件的微小变化的敏感程度的信息。含有整数约束条件的模型不能生成该报告。对于非线性模型，该报告提供递减梯度和拉格朗日乘数；对于线性模型，该报告中将包含递减成本、阴影价格、目标式系数（允许的增量和允许的减量）以及约束右侧的区域。
【极限值报告】列出目标单元格和可变单元格及其各自的数值、上下限和目标值。含有整数约束条件的模型不能生成该报告。下限是在保持其他可变单元格数值不变并满足约束条件的情况下，某个可变单元格可以取到的最小值。上限是在这种情况下可以取到的最大值。
【保存方案】打开“保存方案”对话框，在其中可保存用于 Microsoft Excel“方案管理器”的单元格数值。
五、规划求解常用函数
表2　　　　规划求解常用函数表
名称
功能
语法
MDETERM

返回一个数组的矩阵行列式的值
MDETERM(array)
Array ：行数和列数相等的数值数组
MIN VERSE
返回数组矩阵的逆距阵
MINVERSE(array)
Array ：是具有相等行数和列数的数值数组。
MMULT
返回两数组的矩阵乘积。结果矩阵的行数与 array1 的行数相同，矩阵的列数与 array2 的列数相同。
MMULT(array1,array2)
Array1, array2 ：是要进行矩阵乘法运算的两个数组。

SUMPRODUCT

在给定的几组数组中，将数组间对应的元素相乘，并返回乘积之和。
SUMPRODUCT(array1,array2,array3, ...)
Array1, array2, array3, …为 2 到 30 个数组，其相应元素需要进行相乘并求和。

第二节　线性规划求解方法

　 线性规划是在一定的限制条件下，利用数学方法进行运算，使对前景的规划达到最优的方法。
在经济管理中，线性规划研究的主要问题包括运输问题、生产的组织与计划问题、合理下料问题、配料问题、布局问题、分派问题等。有的著作把它分为资源分配问题、成本收益平衡问题、网络配送问题等。
线性规划的组成： 目标函数：Max f（x）或Min f(x)
约束条件：s.t. (subject to)满足于
决策变量：用符号来表示可控制的因素
线性规划问题的 
一般形式为：
目标函数： Max （Min） z = c1 x1 + c2 x2 + … + cn xn
约束条件： s.t. a11 x1 + a12 x2+…+ a1n xn≤(≥)b1

a21x1 + a22 x2 +…+ a2n xn≤(≥ )b2

………………………………
ak1 x1 + ak2 x2 +… + akn xn ≤ (≥)bk
x1 ，x2 ，… ，xn ≥ 0

用矩阵表示则化为求x，满足约束条件

使目标函数f(x)=cx达到极大（或极小）。
线性规划问题的 
标准形式可以通过对一般形式进行改造而得。
（1）如果第k 个式子为： ak1 x1 + ak2 x2 +… + akn xn ≤ (≥)bk，则加入xm+k≥0，改为：ak1 x1 + ak2 x2 +… + akn xn ＋xm+k＝bk。其他式子也如法炮制。xm+k为松弛变量。
（2）如果问题是求目标函数max z = c1 x1 + c2 x2 + … + cn xn ，则化为求目标函数min zَ= －c1 x1 － c2 x2 － … － cn xn
（3）如果对某变量xj没有非负限制，则引进两个非负变量xjَ≥0， xًَ≥0，令xj＝xjَ－xًَ，代入约束条件和目标函数中，化为对全部变量都有非负限制。由此，线性规划的标准形式为：

式中，A为矩阵，b,c,x均为向量：

我们把满足所有约束条件的一组值称为线性规划的可行解。所有可行解构成的集合称作可行解集，由于一般线性规划问题的可行解集构成n维空间的区域,因此可行解集也称作可行域。在所有的可行解中，使目标函数取得最大值或最小值的可行解称为线性规划问题的最优解。对应的目标函数的取值称为最优值。
线性规划的运算方法很多，如图解法、表上作业法、图上作业法、匈牙利等等。其中最常用的是单纯形法。EXCEL的规划求解功能就是按单纯形法设计的。单纯形算法的原理是：从一个原始可行解x=(0,0,0,…,0)开始，每迭代一次确定一个新的基本可行解（从可行解集合的一个顶点转移到别一个顶点），使得目标函数值严格增加，经过有限次迭代，算法最后终止于一个最优基本解。
一、运输问题
一般地，设某种物资有m个产地：A1，A2，…，Am，联合供应n个销地：B1，B2，…，Bn。产地产量、各销地销量、各产地到销地单位运价如表3：
　　　　　　表3　　运输问题规划求解表
销地
产地
B1，B2，…，Bm
产量（千克）
A1
A2
┆
Am
C11 C12 … C1n
C21 C22 … C2n
…┆ ┆ ┆
Cm1 Cm2 … Cmn
a1
a2
┆
am
销量（千克）
b1 b2 … bn

表中：ai表示产地Ai的产量（i＝1，2，…m）；
bj表示销地Bj的销量（j＝1，1，…n）；
Cij表示AiBj的单位运价（元／千克）（i＝1，2，…m；j＝1，2，…n）。
假定产销平衡（∑ai＝∑bj）。设xij表示由产地Ai运往销地Bj的物资数量，那么，上述运输问题的数学模型为：
（１）已知数据：cij、ai、bj均为常数；
（２）决策变量：xij；
（３）目标函数：min S＝c11x11+c12x12+…cmnxmn
（４）约束条件：
如果在运输问题中，没有产销平衡这一限制，当产大于销（∑ai＞∑bj）时，这一问题的数学模型为：
（１）已知数据：cij、ai、bj均为常数 ；
（２）决策变量：xij；
（３）目标函数：min
（４）约束条件：
【例1】假定有某种物资要从Ａ、Ｂ、Ｃ三个产地运到甲、乙、两、丁四个销地。三个产地的供应量分别为：1000t、800t、500t；四个销地的需要量分别为：500t、700t、800t、300t，各产地和销地之间每吨产品的运费如下表所示，要求计算如何组织运输才能运费最省？
　　　　　　表4　　运费表

销地甲
销地乙
销地丙
销地丁
产地Ａ
15
20
3
30
产地Ｂ
7
8
14
20
产地C
12
3
20
25
【解】利用EXCEL进行规划求解，具体步骤如下：
第一步，建立模型
（１）已知数据：cij、ai、bj均为常数。其中cij为运费矩阵；ai为供应量，bj为需求量；
（２）决策变量：xij；
（３）目标函数：min S＝c11x11+c12x12+…cmnxmn
约束条件为：

第二步，在Ｅxcel中建立工作表，并在可变单元格和目标单元格之间建立函数关系，如下：
B11=B8+B9+B10，并复制到C11:E11；
F8=B8+C8+D8+E8，并复制到F8:F10；
F11=∑cx=｛＝SUMPRODUCT(B2:E4,B8:E10)｝。SUMPRODUCT( )为数组间对应元素乘积之和。

图１ 物资调运运费最小计算表
第三步，应用规划求解工具求解。
在【设置目标单元格】填入$F$11；在【等于】点击“最小值”；在【可变单元格】输入B8:E10；并根据要求“添加”约束条件。约束条件：B8:E10≥０；B11=500、C11=700、D11=800、E11=300；F8=1000、F9=800、F10=500。
最后点击“求解”。　

图２ 物资调运运费最小规划求解表
点击“保存规划求解结果”，并“确定”。

图３ 规划解结果

图４ 物资调运运费最小计算结果表
最后，得到目标函数值为：16600元；运量安排见图1中的B8:E10。
第四步，进行信息分析（主要是敏感性分析，在后面进行重点介绍）。
【例２】有两个煤厂Ａ、B，每月分别进煤 60吨、100吨。它们担负供应三个居民区用煤任务。这三个居民区每月需用煤分别为45吨、75吨、40吨。A厂离这三个居民区分别为10公里、5公里、6公里，B厂离这三个居民区分别为4公里、8公里、15公里。问这两煤厂如何分配供煤，才使运输量最小。
【解】　
第一步，建立模型
（１）已知数据：cij为煤厂至居民区的距离即Ｂ２:Ｄ３；ai＝｛60,100｝为供应量；bi=｛45,75,40｝为需求量。
（２）决策变量：xij为运输数，即Ｂ２：Ｄ３。
（３）目标函数：min S＝c11x11+c12x12+…cmnxmn
（４）约束条件：
第二步，在Ｅxcel中建立工作表，并在可变单元格和目标单元格之间建立函数关系，如下：
E6 =B6+C6+D6，并复制到E7；
B8 =B6+B7，并复制到C8:D0；
E8=∑cx=｛＝SUMPRODUCT(B2:D3,B6:D7)｝。SUMPRODUCT( )为数组间对应元素乘积之和。
第三步，规划求解

图５ 规划求解结果表
二、布局问题
设有n个地区A1，A2，…，An，在某一个计划期内，Ai生产某种原料ai吨，同时需要用这种原料加工的某种产品bi吨(i=1，2，…，n），已知k吨原料可制造1吨该产品。设这n个地区所产原料的总数恰好能生产各地区所需该产品的总数，即。
另外已知在Ai设厂加工该产品的加工费为每吨di元。在Ai设厂生产该产品数最多为ei吨，最少为fi吨（i=1,2，…n）。从Ai运原料或产品到Aj（i，j=l，2，…，n）每吨运价为cij元。问应在何地设厂，生产多少该产品，才能既满足需要，又使生产费用（包括原料和产品运费、产品加工费）最少？
在此，设Xij表示由Ai运到Aj的原料数（单位：吨）（i，j=1，2，…，n），其中j=i时表示Ai留用数；yij表示由Aj运到Ai的成品数（单位：吨）（i，j=l，2，…，n），其中j=i时，表示 Ai留用数；Zi表示Ai设厂的年产成品数（单位；吨）(i=1，2，…，n)。

表5　布局问题规划求解表

A1
A2
…
An
A1
A2
…
An
生产原
料数
生产成品数
加工
费
A1
c11
c12
…
c1n

A2
c21
c22
…
c2n

…
…
…

…

An
cn1
cn2
…
cnn

A1
x11
x12
…
x1n
y11
y12
…
y1n
a1
f1≤z1≤e1
d1
A1
x21
x22
…
x2n
y21
y22
…
y2n
a2
f2≤z2≤e2
d2
…
…
…
…
…
…
…
…

…
…
…
An
xn1
xn2
…
xnn
yn1
yn2
…
ynn
an
fn≤zn≤en
dn
需成
品数

b1
b1
…
bn

需原
料数
kz1
kz2
…
kzn

因此，其数学模型如下：
（１）已知数据：cij、ai、bj、di均为常数；
（２）决策变量：xij、yij、zi；
（３）目标函数：min
约束条件
【例３】设有某种原料产地Al，A２，A３，把这种原料经过加工，制成成品，再运往销地。假设用4吨原料可制成1吨成品。产地A１年产原料30万吨，同时需要成品7万吨。产地A２年产26万吨，同时需要成品13万吨。产地A３年产24万吨，不需成品。A１与A２间距离150公里，A１与A３间距离100公里，A２与A３间距离200公里。又知原料运费为 0．3万元／万吨公里，成品运费为 0．25万元／万吨。且知在Ａ１开设加工厂加工费为0．55万元／万吨，在A２为 0．4万元／万吨，在A３为 0·3万元／万吨。因条件限制，在Ａ２设厂规模不能超过年产成品5万吨，A１和A２可以不限制。问应在何地设厂，生产多少成品，才能使生产费用（包括原料运费、成品运费、加工费等）为最小。
【解】
第一步，建立数学模型
（１）已知数据：cij(i=1,2,3;j=1,2,3)为原材料运费即Ｂ２：Ｄ３；cij(i=1,2,3;j=4,5,6)为成品运费即E2：G3；ai＝｛30，26，24｝为生产原材料数；bi=｛7，13，0｝为成品需求量；k=4,即4吨原材料可生产1吨成品；d=｛0.55，0.4，0.3｝为加工费。
（２）决策变量： xij、yij、zi；　
（３）目标函数：min
（4）约束条件
第二步，在Ｅxcel中建立工作表，并在可变单元格和目标单元格之间建立函数关系，如下：
1.工作表并输入有关数据
H5==B5+C5+D5,并复制到H6:H7上；
E8==E5+E7+E7, 并复制到F8:G8上;
I5=E5+F5+G5, 并复制到I6:I7上;
B9=B5+B6+B7, 并复制到C9:D9上;
2.名称
Ｂ２:Ｄ４定义为“原料运费；
Ｂ５:Ｄ７定义为“xij；
E２:G４定义为“成品运费；
Ｅ5:Ｇ７定义为“Yij”；
I9=｛SUMPRODUCT(原料运费,_xij)+SUMPRODUCT(成品运费,_yij)+I5*J5+I6*J6+I7*J7｝；

图6 建立规划求解工作表
第三步，规划求解
目标单元格：I９；等于“最小值”；
可变单元格：Ｂ２：Ｄ７，Ｅ２：Ｇ７，Ｉ５：Ｉ７。
约束条件：Ｂ５：Ｇ７≥０，Ｉ５：Ｉ７≥０；Ｉ６≥５；
Ｈ５＝３０；Ｈ６＝２６；Ｈ７＝２４；
Ｅ８＝７；Ｆ８＝１３；Ｇ８＝０；
Ｂ９＝4*I5;C9=4*I6;D9=4*I7.

图7 选择规划求解参数
三、分派问题
设有n件工作Bl，B２，…，Bn分派给n人Al，A2，…，An去做，每人只做一件工作且每件工作只分派一人去做。设Ai完成Bj的工时为cij（i，j=1，2，…，n）。问应如何分派才使完成全部工作的总工时最少。。
显然，设xij为Bj分派给Ai的情况:Bj分派给Ai时，xij=1;不分派给Ai时，xij=0（i，j=1，2，…，n）。那末这一问题的数学模型为：
（１）数据：cij、ai、bj均为已知常数；
（２）决策变量：xij；
（３）目标函数：
（４）约束条件：
【例4】将6项不同的工作分配给6个人去做，每个人都有能力完成其中的任何一项工作，但效率的高低不同。现将每人完成各项工作所需要的时间如图8所示，请提出6个人完成6项工作总的花费时间达到最少的方案。
【解】这个分派问题是整数线性规划问题。通过ＥＸＣＥＬ求解的基本步骤为：
第一步，建立模型
设Ai为完成工作的人员；Bi为工作任务；cij为Ai完成 Bi所需要的时间。xij为Bi分配给Ai的情况。但∑xij＝1，xij=1或0。∑cijxij的值最小。
（１）数据：cij、ai、bj均为已知常数；
（２）决策变量：xij；
（３）目标函数：
（４）约束条件：
第二步，建立工作表并在可变单元格与目标单元格之间建立函数关系
（1）建立工作表；
（2）H９=B９+C９+D９+E９+F９+G９，并复制到H1０：H1４；
（3）B15=B9+B10+B11+B12+B13+B14，并复制到C15：G15；
（4）H15＝｛=SUMPRODUCT(B2:G7,B9:G14)｝。
第三步，规划求解
点击“规划求解”。选择“目标单格”即H15；等于“最小值”；可变单格为：B9:G14；约束条件为：B9:G14≥0，B9:G14＝整数；H9:H14＝1；B15:G15＝1。求解得出结果。

图8 规划求解结果表
四、生产组织与计划问题
设用Al，A2，…，An种原料，可生产Bl，B2，…，Bn种产品。现有原料数(ai)、每单位产品所需原料数(cij)，及每单位产品可得利润数(bj)如表6。如何通过组织生产使利润最大。
　　　　　　表6　　生产计划问题规划求解表
产品
原料
B1，B2，…，Bm
现有原料
A1
A2
┆
Am
C11 C12 … C1n
C21 C22 … C2n
…┆ ┆ ┆
Cm1 Cm2 … Cmn
a1
a2
┆
am
单位产品利润
b1 b2 … bn

这一问题的数学模型为：
（１）数据：cij、ai、bj均为已知常数；
（２）决策变量：xij(i=1,2,…m;j=1,2,…,n);
（３）目标函数：
（４）约束条件：
【例５】某木器厂生产圆桌和衣柜两种产品。现有两种木料，第一种有 72立方米，第二种有 56立方米。假设生产每种产品都需要用两种木料。生产一只圆桌和一个衣柜所需木料如下表所示。每生产一只圆桌可获利润6元；生产一个衣柜可获利润10元。木器厂在现有木料条件下，圆桌和衣柜应各生产多少，才使获得利润最多。

　　　　　　　表7　　产品用材料数表
产品
木料（单位：立方米）
第一种
第二种
圆桌
衣柜
0.18
0.09
0.08
0.28
【解】
第一步，建立模型
cij为生产一只圆桌和一个衣柜所需木料， xj为生产圆桌、衣柜的数量；ai为可使用的木料量；bj为单位产品利润，目标函数maxz＝∑xjbj。
这一问题的数学模型为：
（１）数据：cij、ai、bj均为已知；
（２）决策变量：xij(i=1,2,…m;j=1,2,…,n);
（３）目标函数：
（４）约束条件：
第二步，建立工作表并在可变单元格与目标单元格之间建立函数关系
B6=$B$9*B2，并复制到B7；C6=$C$9*C2，并复制到C7；
E6=B6+C6,并复制到E7:E9；B10=B8*B9，并复制到C10；
E10=B10+C10.
第三步，规划求解
目标单元格：Ｅ１０；等于“最大值”；可变单元格：Ｂ８:Ｃ８。
约束条件：Ｂ８:Ｃ８≥0,E6≤72,E7≤56。

图9 规划求解结果表

五、合理下料问题
设用某原材料（条村或板材）下零件Al，A2，…，An的毛坯。根据过去经验在一件原材料上有B1，B2，…，Bn种不同的下料方式，每种下料方式可得各种毛坯个数及每种零件需要量如表8所示。问应怎样安排下料方式，使得既能满足需要，用的原材料又最少。
　　　　表8　　下料问题规划求解表
下料方式
零件
B1，B2，…，Bm
零件需要量
A1
A2
┆
Am
C11 C12 … C1n
C21 C22 … C2n
…┆ ┆ ┆
Cm1 Cm2 … Cmn
a1
a2
┆
am
这一问题的数学模型为：
（１）数据：cij为各种方式下的零件个数： cij、ai均为已知常数；
（２）决策变量：xj(j=1,2,…,n);
（３）目标函数：
（４）约束条件：
【例６】某工地要将7.3m长的圆钢截成2.9m长的毛坯200根、2.1m长的毛坯306根、1.5m长的毛坯92根。现有8种下料方法，每种方法截出各种毛坯的根数和残料的长度如图10，问怎样截法，才使所用的原材料最少。

图10 下料问题数据表
【解】
第一步，建立模型
（１）数据：cij为各种方式下的零件个数： cij、ai均为已知常数；
（２）决策变量：xj(j=1,2,…,n);
（３）目标函数：
（４）约束条件：
第二步，建立工作表并在可变单元格与目标单元格之间建立函数关系
B7=$B$10*B2,并复制到B8:B9；
C7=$C$10*C2,并复制到C8:C9；
D7=$D$10*D2,并复制到D8:D9；
E7=$E$10*E2,并复制到E8:E9；
F7=$F$10*F2,并复制到F8:F9；
J7=SUM(B7*H7),并复制到J8:J10；

图１1 规划求解结果表
第三步，规划求解
目标单元格：J１０；等于“最小值”；可变单元格：Ｂ１０：Ｈ１０。
约束条件：J7≥K7; J8≥K8; J9≥K9。
六、配料问题
设用n种原料B1,B2，…Bn制成具有m种成分A1，A2，…，Am的产品，其所含各成分需要量分别不低于a1，a2，…，am。各种原料的单价，以及各种原料所含成分的数量如表9所示。问应如何配料，才使产品成本最低。

　　　　表9　　配料问题规划求解表
原料
成分名称
B1，B2，…，Bm
产品所含成分需要量
A1
A2
┆
Am
C11 C12 … C1n
C21 C22 … C2n
…┆ ┆ ┆
Cm1 Cm2 … Cmn
a1
a2
┆
am
单价
b1 b2 … bn

这一问题的数学模型为：
（１）数据：cij为一单位原料所含成分的数量； cij、ai、bj均为已知常数；
（２）决策变量：xj(j=1,2,…,n);
（３）目标函数：
（４）约束条件：
【例７】某铝金厂生产某种铝合金，拟从Ｂ１、Ｂ２、Ｂ３、Ｂ４、Ｂ５种原料中选择搭配与铝熔合成。各种原料的主要化学成分和杂质的含量（Ａi）（％）、含量限制（％）与进料价格如表10，要求规划求解找到合理配方，使原料成本达到最低。
表10 某种铝合金用料化学成分与进料价格表

Ａ
Ｂ
Ｃ
Ｄ
Ｅ
Ｆ
Ｇ
1

各种
原料

产品所含
成分限量
2

B1
B2
B3
B4
B5
3
A1
0.06870
0.05142
0.04500
0.00220
0.97000
0.117～0.1157
4
A2
0.00500
0.01878
0.02700
0.00015
0
0.0193～0.0213
5
A3
0.02050
0.00408
0.01200
0.00300
0.01000
0.00900
6
A4
0.00250
0.00150
0.01300
0
0
0.01000
7
A5
0.00108
0.00189
0.00170
0
0
0.00300
8
A6
0.00250
0.00431
0.00300
0
0
0.00500
9
A7
0.00084
0.00050
0.00128
0
0
0.00300
10
A8
0.00100
0.00100
0.00200
0
0
0.00300
11
单价
1.9
1.8
2.1
2.7
1.9

【解】
第一步，建立数学模型
设cij为一单位原料所含成分的数量；ai为含量限制、bj为单价。
（１）数据：cij为一单位原料所含成分的数量； cij、ai、bj均为已知常数；
（２）决策变量：xj(j=1,2,…,n);
（３）目标函数：
（４）约束条件：
第二步，建立工作表并在可变单元格与目标单元格之间建立函数关系
(1) B14＝$B$22*B3,并复制到B15:B21;
(2) C14＝$C$22*C3,并复制到C15:C21;
(3) D14＝$D$22*D3,并复制到D15:D21;
(4) E14＝$E$22*E3,并复制到E15:E21;
(5) F14＝$F$22*F3,并复制到F15:F21;
建立总含量的函数：
Ｇ14＝ＳＵＭ（Ｂ１４：Ｆ１４）,并复制到Ｇ15:Ｇ21;
建立成本函数关系：
Ｂ２4＝Ｂ22*Ｂ２3,并复制到Ｃ15:Ｇ21;
第三步，规划求解
目标单元格G24（ ）；等于“最小值”。
约束条件：

图１2 规划求解结果表

第三节 对偶问题与影子价格
一、对偶线性规划问题
（一） 对偶概念
每一个线性规划问题都存在一个与其对偶的问题，在求出一个问题解的同
时，也给出了另一个问题的解。
我们把线性规划问题
（Ⅰ）Min s= c1 x1 + c2 x2 + … + cn xn
s.t. a11 x1 + a12 x2+…+ a1n xn ≥ b1

a21x1 + a22 x2 +…+ a2n xn ≥ b2

………………………………
ak1 x1 + ak2 x2 +… + akn xn ≥ bk
x1 ，x2 ，… ，xn ≥ 0

称为原始问题，则把　
(Ⅱ) Max g= b1 y1 + b2 y2 + … + bn yn