表格法解线性规划问题.docx
表格法解线性规划问题
【教学目标】
知识目标：理解用表格法解线性规划问题的方法和步骤.
能力目标：通过例子详细地介绍了表格法解线性规划问题的过程，
并引入了线性规划标准型的概念，归纳总结了表格法
解线性规划问题的步骤 .
【教学重点】理解用表格法解线性规划问题的方法和步骤 .
【教学难点】理解用表格法解线性规划问题的方法和步骤 .
【教学设计】
1、表格法也称单纯形法，是解线性规划问题的常用方法，使用该
方法时，首先要将一般的线性规划问题化为标准型 . 在教材中给出了化标准型的方法 . 讲解时一定要注意 b≥0 以及变量的非负性 .
2、表格法解线性规划问题的过程，教材中归纳为五个步骤，这实
际上是一个算法，可以利用前面介绍过的算法知识来学习.
3、初始表格中初始解组的确定是关键，一般可取松弛变量，但当
标准型中没有这样的变量满足初始解组的要求时，通常要通过添加人工变量来解决，本教材没有就这方面的问题进行深入讨论（一般的运筹学教材中都可找到该内容）.
4、表格在转换时（通常称为转轴），教材中提到用加减消元法来转
轴. 教师可就这部分内容作适当的讲解.
5、由于通常的表格转换要进行多次，而表头部分是不变的，因此
可以将多张表格合并起来，具体样式可参见节表5-16.
【教学过程】
5.3.1线性规划问题的标准形式
求线性规划问题的图解法虽然直观简便，但对多于两个变量的情
况就不能适用了，对于多于两个决策变量的线性规划问题，可以用什么方法呢？
下面介绍一种用表格的方法来求解线性规划问题的解.
表格法是根据单纯形法而专门设计的一种计算表格.
单纯形法（Simple Method）是求解线性规划问题的主要方法，该法由丹赛（Dantzig ）于1947 年提出，后经过多次改进而成，是求解线性规划问题的实用算法 . 由上节的叙述可知，如果线性规划问题的最优解存在，则必定可以在其可行解集合的顶点（极点）中找到．因
此，寻求一个最优解就是在其可行域的各个极点中搜索最优点 . 单纯形法实质上是一个迭代过程，该迭代即是从可行域的一个极点移到另一个近邻的极点，直到判定某一极点为最优解为止 .
为使用表格法，首先介绍线性规划问题的标准形式.
一般的线性规划问题中目标函数可能是求最大 ( 或最小 ) 值，而线性约束条件中可能是线性方程，也可能是线性不等式，约束条件中约束方程（或不等式）的个数也未必就比决策变量的个数少，这些问题对于线性规划的求解，带来极大的不便，为此，引入下述标准形式：
求目标函数最大值max Z c1 x1c2 x2c3 x3...c n x n
n
( 用和式表示为max Z c j x j)
j 1
a 11 x 1
a 12 x 2
...
a 1n x n
b 1
a 21 x 1 a 22 x
2
... a 2n x
n
b 2
满足
............
a m1
x 1
a m2
x
2
...
a mn x
n
b m
x 1 0, x 2
0,..., x n 0
n
用和式表示为满足
a ij x i
b i , (i 1,2,3, , m)
j
1
x j
0,( j 1,2,3, , n)
其中， 各 a ij , b i , c j (i 1,2,3, , m; j 1,2,
, n) 都是确定的常数，
x j ( j
1,2, , n) 是决策变量 ，Z 是目标函数 ， a ij 叫做技术系数， b i ≥0 （ i
1,2, m) 叫做资源系数 ， c j 叫做目标函数系数 .
特点：
1、目标函数为极大化；
2、除决策变量的非负约束外， 所有的约束条件都是等式， 且右端
常数均为非负；
3、所有决策变量均非负．
如果根据实际问题建立起来的线性规划模型不是标准型的，可以
用下述方法将它化为标准型 .
（1）若目标函数是
min Z
c 1 x 1
c 2 x 2
c 3 x 3 ...
c n x n
可令
z
z ' , 将目标函数转化为
max Z '
(c 1 x 1
c 2 x 2
c 3 x 3
... c n x n )
（2）若约束条件不等式中是“≤” , 可在不等式左边加上非负变量，
将不等式转化为方程 . 如 6x 1 2x 2 ≤180 可转化为 6x 1 2x 2
x 3
180, 其
中 x 3 ≥0.
这里的
x 3 叫做松弛变量
.
表示没有用完的资源
.
（3）若约束条件不等式是“≥” ，可在不等式左边减去非负变量，将
不等式转化为等式方程，如 2x1 2x2≥10可转化为 2x12x2 x4 10 ，
其中， x4≥0. 这里的 x4叫做多余变量，表示不存在的资源 .
一般地，松弛变量和多余变量的目标函数系数为0.
（4）若有一个变量x k没有非负约束（叫做自由变量），可令x k x l x s，其中 x l≥0， x s≥0.
知识巩固
例 1 将节问题 1 中的线性规划问题化为标准型
6x12x2180
约束条件
求目标函数最大值
4 x110x2400 3x15x2210
x10, x20 max Z31x122 x2
解分别对前三个约束条件引入松弛变量x3 , x4 , x5，得标准型：
约束条件
求目标函数最大值
6x12x2x3180 4x110x2x4400 3x15x2x5210 x j 0, j1,2,3, 5.
max Z31x1 22 x2
5.3.2表格法
下面我们通过实例来介绍表格法.
首先要列出初始表格．为了得到初始表格，我们分几步来说明：先把标准型中的约束条件方程转换成表格（表）的形式．
如: 问题 1 转化的结果为：
6x12x2x30x40x5180
4x110 x20x3x40x5400
列成表格为：
3x15x20x30x4x5210
x j0, j1,2,,5.
表
x1x2x3x4x5b i
62100180
410010400
35001210
( 表格中的列数为变量个数加1，行数为方程个数加1)
从约束方程中，很容易得到，当 x1 0 ，x20 时，x3 180 ，x4 400 ，x5 210 ，显然这是一组可行解（我们把它叫作初始解组），将其中三
个取非0 值的变量x3, x4, x5列成一列对应地加在上表的最左侧，然后
再在所得表的左侧添加一列对应于该初始解组变量的目标函数系数，
在表的上侧添加一行对应于各变量的目标函数系数，得如下表：
其中在初始解组中的变量必须满足在对应行的约束条件方程中系
数为 1，而同列其他系数为 0，（如果约束条件方程中不满足这要求，
可以通过对线性约束条件方程作加减消元法而得到
. ）
再在上表的基础上，增加 1 行( 叫做检验数行
j
) 和 1 列( 叫做比值
列 i ) 得下面形式：
按下面的计算公式在表中依次填上检验数行
j
和比值列
i ,
其中
m
检验数计算公式
j
c j
c i a ij
, 例如
j
31 ，即为
x 1 所在列的目标函
i 1
数系数行中的
c 1 值减去该列系数与第一列初始解组的目标函数系数
的对应乘积和，
1
31 ( 0 6
4 0
3)
31 .
选取检验数最大的正数所在列 ( 记作 k 列，表中用 [ ]
表示 ) 然后
计算比值
i
．
比值的计算公式 i
b i
, a ik
0, ，例如
180 .
a
ik 1
6
选取最小的 i 值，记所在行为 i 行( 表中用 [ ] 表示 ) ，如下表 ( i 1 ）
最后填上目标函数Z 值一格，其中目标函数Z 为第一列C B与b所在列对应乘积和．
得下表：
表
可行解比值
c j3122000
B
X
B x
1
x
2
x3x
4
x5b i i
C
0x3(6)2100180[30]
0x4410010400100
0x53500121070 j
[31]220000
检验数目标函数 Z 这样我们得到了初始表格（表）
显然，前面的初始解组并不能产生最优目标函数值，因此，必须
要对初始解组中的变量进行替换，以求更好的解. 通常，我们按下述方法进行变量的替换：
根据上面所选的第 k 列第 i 行( 如上表中 x3所在行和 x1所在列，我们将两者的交叉点用 ( ) 表示 ) ，对初始解组作调整，将变量 x k换入，替代第 i 行中的初始变量 ( 即表中换入 x1，换出 x3 ) ，根据表格法的要求，必须同时将换入变量 x k在( ) 中的系数通过加减消元法化为 1，
且同列其他系数为0，而初始解组中其他未换出变量所在列的系数不
变，通常可用加减消元法来求得．
下面我们具体来说明表格的转换．
框中 行除以 6 得行； 行减 ×4 得行；
表
c j3122000
C X
x1x2x3x4x5b i
B B i
0x4410010400
0x535001210
表
c j3122000
B
X
B x
1
x x3x
4
x5b i i
C2
36
0x40262
33
0x50(4)1
210280 01120
再依次填上检验数行j和比值列i ，得下表(表．
表
c j3322000
B
X
B x x
2
x3x
4
x5b i i
C1
31x1111003090
36
0x40262
10280
420 3313
0x50(4 ）101120[30]
2
j 0[
35
]3100930
36
如果检验数全为非正数，那么，所得解就是最优解．否则，继续
按前方法修改可行解，直至不能继续为止．显然，上表中 x2换入，变量 x5换出．转下表 ( 表．
表
c j3122000
B
X
B x x
2
x3x
4
x5b i
i
C1
31x11050120
2412
0x400511320
126
22 x201
j00
1
8
89
24
1
4
35
12
30
1280
因为所有的检验数j≦0，故当前可行解 x120，x230 ，x30 ，x40 ， x50 为最优解，删去松弛变量，即得原线性规划最优解为
x120， x230 ，
最优值为Z=1280．
通上面的例子，可以一般的表格法的算步如下：
第一步：建立初始表格．
第二步：：若所有的j ≤0，当前可行解即最解；否
入(3) ．
第三步：：若存在k>0,且a ik ≤0，(i=1,2,?,m)，无最解；
否入(4)．
第四步：取数行中最大的正数所在的列，( 作k 列，表中
用[ ]表示 ) 然后算比
i ，比的算公式θi b i
a ik
, a ik0 ．
取最小的
i ，所在行i
行(表中用[ ]表示 ) ，确定x k，将x k入，将松弛量 x h出，用加减消元法化 x k的系数 a ik1，且同列其他系数 0．以x k取代x h得新表，入 (2).
巩固知典型例
例 2 用表格法解中的例 1：某工厂用与橡胶生 3 种品A、B、C,有关料如表所示.已知每天可得100位的和120位的橡胶，每天按排生 A、B、C三种品各多少，能使利最大？
写出的性束条件和目函数.
表
品位品消耗量位品橡胶消耗量位品利
A2340
B3345
C1224
2x13x2x3 100
则可得约束条件 3x13x22x3120
x10, x20, x30
目标函数为 max Z 40x145x224 x3
解引入松弛变量x4, x5，得标准型：
max Z40 x1 45x2 24x3
2x13x2x3x4100
满足3x13x2 2 x3x5120
x j0, j1,2,3,5
列初始表格 ( 表．
表
c j40452400
C B X B x1x2x3x4x5b i i 0x42(3)110100[ 100 ]
3
0x53320112040
40[45]24000
j
因为σ2为最大正数，转下表 ( 表．
表
c j40452400
C B X B x1x2x3x4x5b i i
45x22111010050 3333
0x5(1)011120[20]
[10]09-1501500
j
将 x1换入，x5换出，得表．
表
c j40452400
C B X B x1x2x3x4x5b i
i
45x20111220
33
40x11011120
0015-101700
j
因为所有的检验数j≦0，故当前可行解x120 , x220 , x30 ，x4 0 ， x5 0 为最优解，删去松弛变量，即得原线性规划最优解为
x120 , x220 , x3 0 ，
目标函数最优值为Z1700 .
怎么利用EXCEL求解线性规划
利用线性回归方法求解生产计划 方法一： 1、建立数学模型: ①设变量：设生产拉盖式书桌x台，普通式书桌y台，可得最大利润 ②确定目标函数及约束条件 目标函数：y = max+ 115 P90 x 约束条件：200 x .....................⑴ +y 10≤ 20 x .....................⑵ 4≤ +y 16 128 x .....................⑶ +y 10 15≤ 220 y x ..........................⑷ ,≥ 2、在Excel中求解线性规划 ①首先，如图1所示，在Excel工作表格输入目标函数的系数、约束方程的系数和右端常数项： 图1 ②将目标方程和约束条件的对应公式输入各单元格中 F2=MMULT（B6:C6,F6:F7)； F3=MMULT（B3:C3,F6:F7)； F2=MMULT（B4:C4,F6:F7)； F2=MMULT（B5:C5,F6:F7)；
出现图2样式： 图2 线性规划问题的电子表格模型建好后，即可利用“线性规划”功能进行求解。 选择“工具”→“规划求解”出现“规划求解参数”窗口，如图3所示: 图3 在该对话框中，目标单元格选择F2，问题类型选择“最大值”，可变单元格选择F6：F7，点击“添加”按钮，弹出“添加约束条件”窗口，如图4所示: 图4
根据所建模型，共有4个约束条件，针对约束（1）：20 x， +y 20 10≤ 左端“单元格所引用位置”选择F3，右端“约束值”选择D3，符号类型选择“<=”，同理继续添加约束（2）（3）（4），完成后选择“确定”，回到“规划求解参数”对话框，如5图所示： 图5 ④点击“选项”按钮，弹出“规划求解选项”对话框，选择“采用线性模型”和“假定非负”两项，如图6所示： 图6 ⑤点击“确定”→“求解”，选择“运算结果报告”“敏感性报告”“极限值报告”三项，最后点击“确定”，输出结果： 运算结果报告：
使用Excel规划求解解 线性规划问题
使用Excel规划求解解线性规划问题 引言 最近，开始学习运筹学，期望通过学习后能够解决许多困扰自已的难题。 刚开始时，选了很多教材，最后以Hamdy A.Taha著的《Operations Research:An Introduction》开始学习。（该书已由人民邮电出版社出版，书名《运筹学导论-初级篇（第8版）》，不知为什么，下载链接中只有该书配套的部分习题解答，而书中所说的光盘文件找不到下载的地方，因为中译本没有配光盘，因此也就错过了许多示例文件。不知道哪位有配套光盘文件，可否共享？？？） 线性规划求解的基本知识 线性规划模型由3个基本部分组成： ?决策变量（variable） ?目标函数（objective） ?约束条件（constraint） 示例：营养配方问题 （问题）某农场每天至少使用800磅特殊饲料。这种特殊饲料由玉米和大豆粉配制而成，含有以下成份： 特殊饲料的营养要求是至少30%的蛋白质和至多5%的纤维。该农场希望确定每天最小成本的饲料配制。 （解答过程） 因为饲料由玉米和大豆粉配制而成，所以模型的决策变量定义为： x1=每天混合饲料中玉米的重量（磅） x2=每天混合饲料中大豆粉的重量（磅） 目标函数是使配制这种饲料的每天总成本最小，因此表示为： min z=0.3×x1+0.9×x2 模型的约束条件是饲料的日需求量和对营养成份的需求量，具体表示为： x1+x2≥800 0.09×1+0.6×2≥0.3(x1+x2) 0.02×1+0.06×2≤0.05(x1+x2) 将上述不等式化简后，完整的模型为：
min z=0.3×1+0.9×2 s.t.x1+x2≥800 0.21×1-0.3×2≤0 0.03×1-0.01×2≥0 x1,x2≥0 可以使用图解法确定最优解。下面，我们介绍使用Excel的规划求解加载项求解该模型。使用Excel规划求解解线性规划问题 步骤1安装Excel规划求解加载项 单击“Office按钮——Excel选项——加载项——（Excel加载项）转到”，出现“加载宏”对话框，如下图所示。选择“规划求解加载项”，单击“确定”。 此时，在“数据”选项卡中出现带有“规划求解”按钮的“分析”组，如下图所示。 步骤2设计电子表格 使用Excel求解线性规划问题时，电子表格是输入和输出的载体，因此设计良好的电子表格，更加易于阅读。本例的电子表格设计如下图所示：
最新单纯形法解线性规划问题
一、用单纯形第Ⅰ阶段和第Ⅱ阶段解下列问题 s.t. 解：1)、将该线性问题转为标准线性问题 一、第一阶段求解初始可行点 2)、引入人工变量修改约束集合 取人工变量为状态变量，问题变量和松弛变量为决策变量，得到如下单纯形表，并是所有决策变量的值为零，得到人工变量的非负值。 2 -2 -1 1 2 1 1 -1 -1 1 2 -1 -2 1 2 5 -2 -4 1 -1 1 5 0 0 0 0 0 3)、对上述单纯形表进行计算，是目标函数进一步减小，选为要改变的决策变量，计算改变的限值。 2 -2 -1 1 2 1 1 1 -1 -1 1 0 2 -1 -2 1 2 0 5 -2 -4 1 -1 1 5 1 0 0 0 0 0 0 1 0 0 0 4)、由于，为人工变量，当其到达零值时，将其从问题中拿掉保证其值不会再变。同时将以改变的决策变量转换为状态变量。增加的值使目标函数值更小。 1 -3 1 1 1 0 1 1 -1 1
1 -3 1 1 1 0 0 0 0 0 0 0 0 5）使所有人工变量为零的问题变量的值记为所求目标函数的初始可行点，本例为， 二、第二阶段用单纯形法求解最优解 -2 2 1 0 1 1 -1 0 -2 1 2 1 5 1 3 要使目标函数继续减小，需要减小或的值，由以上计算，已经有两个松弛变量为零，因此或不能再减小了，故该初始可行点即为最优解。
2、求解问题 s.t. 如果目标函数变成，确定使原解仍保持最优的c值范围，并把目标函数最 大值变达成c的函数。 解：先采用单纯形法求解最优解，再对保持最优解时C值的范围进行讨论。 1）将问题华为标准线性问题 s.t. 2）用单纯形表表示约束条件，同时在不引入人工变量的前提下，取松弛变量得初始值为零值，求解初始解和最优解 10 -1 -1 -1 10 -20 1 5 1 -20 -2 -1 -1 0 0 0 0 要使目标函数继续减小，可以增大，增大的限值是10。 10 -1 -1 -1 10 0 -20 1 5 1 -20 -10 -2 -1 -1 0 -20 0 0 0 10 0 0 3）转轴。将为零的松弛变量和决策变量交换进行转轴 10 -1 -1 -1 10 -10 4 0 -1 -10 0 -20 1 1 2 -20
图解法和单纯形法求解线性规划问题
图解法和单纯形法求解以下线性规划问题 1.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直 角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题 它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式
表格法解线性规划问题
表格法解线性规划问题 【教学目标】 知识目标：理解用表格法解线性规划问题的方法和步骤. 能力目标：通过例子详细地介绍了表格法解线性规划问题的过程，并引入了线性规划标准型的概念，归纳总结了表格法 解线性规划问题的步骤. 【教学重点】理解用表格法解线性规划问题的方法和步骤. 【教学难点】理解用表格法解线性规划问题的方法和步骤. 【教学设计】 1、表格法也称单纯形法，是解线性规划问题的常用方法，使用该 方法时，首先要将一般的线性规划问题化为标准型.在教材中给出了化标准型的方法.讲解时一定要注意b≥0以及变量的非负性. 2、表格法解线性规划问题的过程，教材中归纳为五个步骤，这实 际上是一个算法，可以利用前面介绍过的算法知识来学习. 3、初始表格中初始解组的确定是关键，一般可取松弛变量，但当 标准型中没有这样的变量满足初始解组的要求时，通常要通过添加人工变量来解决，本教材没有就这方面的问题进行深入讨论（一般的运筹学教材中都可找到该容）. 4、表格在转换时（通常称为转轴），教材中提到用加减消元法来转 轴.教师可就这部分容作适当的讲解. 5、由于通常的表格转换要进行多次，而表头部分是不变的，因此 可以将多表格合并起来，具体样式可参见5.5节表5-16.
【教学过程】 5.3.1线性规划问题的标准形式 求线性规划问题的图解法虽然直观简便，但对多于两个变量的情况就不能适用了，对于多于两个决策变量的线性规划问题，可以用什么方法呢？ 下面介绍一种用表格的方法来求解线性规划问题的解. 表格法是根据单纯形法而专门设计的一种计算表格. 单纯形法（Simple Method ）是求解线性规划问题的主要方法，该法由丹赛（Dantzig ）于1947年提出，后经过多次改进而成，是求解线性规划问题的实用算法.由上节的叙述可知，如果线性规划问题的最优解存在，则必定可以在其可行解集合的顶点（极点）中找到．因此，寻求一个最优解就是在其可行域的各个极点中搜索最优点.单纯形法实质上是一个迭代过程，该迭代即是从可行域的一个极点移到另一个近邻的极点，直到判定某一极点为最优解为止. 为使用表格法，首先介绍线性规划问题的标准形式. 一般的线性规划问题中目标函数可能是求最大(或最小)值，而线性约束条件中可能是线性方程，也可能是线性不等式，约束条件中约束方程（或不等式）的个数也未必就比决策变量的个数少，这些问题对于线性规划的求解，带来极大的不便，为此，引入下述标准形式： 求目标函数最大值 n n x c x c x c x c Z ++++=...m ax 332211 (用和式表示为j j n j x c Z ∑==1max )
Excel规划求解操作指南线性规划问题的建模与求解
Excel规划求解操作指南(一) ——线性规划问题的建模与求解 内容摘要：《Excel规划求解操作指南》旨在比较通俗地来说明规划求解的步骤和怎么利用它来解决问题，便于大家自学或查询。本文主要介绍Excel规划求解的预备知识、线性规划问题的建模初步方法和利用Excel求解线性规划的步骤。 关键词：Excel 线性规划建模求解 第二次世界大战以来，运筹学成功地解决了许多经济管理问题，作为一门现代科学得到了广泛应用，规划论是运筹学的最重要的分支。计算机的应用为运筹学的发展提供了强大的支持，利用Excel可以解决通常情况下的规划求解问题。但是，使用过Excel的朋友，很多可能都不了解什么是规划求解，而知道有此功能的朋友，也很少有利用此功能来完成实际问题，或者学习时懂了，学过就忘了。《Excel规划求解操作指南》试图比较通俗地来说明规划求解的步骤和怎么利用它来解决问题，便于大家自学或查询。本文是该操作指南的一部分，其他部分将陆续向大家介绍。 一、预备知识 1、规划求解程序安装 在OFFICE的重要组件EXCEL中，有一个规划求解的加载宏。加载该宏之后，就可以利用EXCEl的规划求解功能进行规划求解。在EXCEL2003版本中，通过点击菜单【工具】——【加载宏】，在加载宏对话框中选择【规划求解】项，便可以加载该宏。如果计算机提示无法安装，那么需要插入OFFICE光盘，再进行安装。 2、规划求解的常用函数 （1）SUM函数 利用SUM函数，可以自动求出所选中的单元格数据的和。 首先，选中输出结果的单元格，输入“=”，在下拉菜单中选择“SUM”，得到函数参数对话框 然后，将光标放在Number框中，选中需要求和的单元格，确定。 在菜单栏中会出现输入内容以供检查。例如，
线性规划单纯形法(例题)
《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》 ? ? ??≥=+ +=+++++=?? ? ??≥≤+≤++=0 ,,,24 261553).(002max ,,0,24 261553).(2max 14.1843214213 214 321432121212 1x x x x x x x x x x t s x x x x z x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【为初始基变量， 选择43,x x )1000(00)0010(01 )2050(12)6030(24321=?+?-==?+?-==?+?-==?+?-=σσσσ 为出基变量。为进基变量，所以选择41x x
3 /1)6/122/10(00 )0210(03 /1)3/1240(10)1200(24321-=?+-?-= =?+?-==?+?-==?+?-=σσσσ 为出基变量。 为进基变量，所以选择32x x 24 /724/528/11012/112/124/1100 021110 120124321-=?+-?-=-=-?+?-==?+?-==?+?-=）（）（）（）（σσσσ 4 33 4341522max , )4 3,415(),(2112= +?=+===x x z x x X T T 故有：所以，最优解为
??? ??? ?≥=+ +=+=+ ++++=?????? ?≥≤+≤≤+=0,,,,18232424).(0002max ,,,0 ,182312212 ).(52max 24.185432152142315 43215432121212 1x x x x x x x x x x x x t s x x x x x z x x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【 )000010(00001000000000100520200052300010254321=?+?+?-==?+?+?-==?+?+?-==?+?+?-==?+?+?-=σσσσσ）（）（）（）（ 为出基变量。为进基变量，所以选择42x x
使用单纯形法解线性规划问题
使用单纯形法解线性规划问题 要求：目标函数为：123min 3z x x x =-- 约束条件为： 123123 1312321142321,,0 x x x x x x x x x x x -+≤??-++≥?? -+=??≥? 用单纯形法列表求解，写出计算过程。 解： 1） 将线性规划问题标准化如下： 目标函数为：123max max()3f z x x x =-=-++ s.t.： 123412356 1371234567211 42321,,,,,,0 x x x x x x x x x x x x x x x x x x x -++=??-++-+=??-++=??≥? 2） 找出初始基变量，为x 4、x 6、x 7，做出单纯形表如下： 表一：最初的单纯形表 变量 基变量 x 1 x 2 x 3 x 4 x 5 x 6 x 7 b i x 4 1 -2 1 1 0 0 0 11 x 6 -4 1 2 0 -1 1 0 3 x 7 -2 0 1 0 0 0 1 1 -f -3 1 1 3） 换入变量有两种取法，第一种取为x 2，相应的换出变量为x 6，进行第一次迭代。迭代后新的单纯形表为： 表二：第一种换入换出变量取法迭代后的单纯形表 变量 基变量 x 1 x 2 x 3 x 4 x 5 x 6 x 7 b i x 4 -7 5 1 -2 2 3
x2-4120-1103 x7-20100011 -f10-101-10-3 由于x1和x5对应的系数不是0就是负数，所以此时用单纯形法得不到最优解。 表一中也可以把换入变量取为x3，相应的换出变量为x7，进行一次迭代后的单纯形表为： 表三：第二种换入换出变量取法迭代后的单纯形表 变量 基变量x1x2x3x4x5x6x7 b i x43-20100-110 x60100-11-21 x3-20100011 -f-110000-1-1 4）表三中，取换入变量为x2，换出变量为x6，进行第二次迭代。之后的单纯形 表为： 表四：第二次迭代后的单纯形表 变量 基变量x1x2x3x4x5x6x7 b i x43001-22-512 x20100-11-21 x3-20100011 -f-10001-11-2 5）表四中，取换入变量为x7，换出变量为x3，进行第三次迭代。之后的单纯形 表为： 表五：第三次迭代后的单纯形表 变量 基变量x1x2x3x4x5x6x7 b i x4-7051-22017 x2-4120-1103 x7-20100011 -f10-101-10-3可以看出，此时x1，x5对应的系数全部非零即负，故迭代结束，没有最优解。 结论： 综上所述，本线性规划问题，使用单纯形法得不到最优解。
《运筹学》使用Excel求解线性规划问题
第三节 使用Excel 求解线性规划问题 利用单纯形法手工计算线性规划问题是很麻烦的。office 软件是一目前常用的软件，我们可以利用office 软件中的Excel 工作表来求解本书中的所有线性规划问题。对于大型线性规划问题，需要应用专业软件，如Matlab ，Lindo ，lingo 等，这些软件的使用这里我们不作介绍，有需要的，自己阅读有关文献资料。 用Excel 工作表求解线性规划问题，我们需要先设计一个工作表，将线性规划问题中的有关数据填入该工作表中。所需的工作表可按下列步骤操作： 步骤1 确定目标函数系数存放单元格，并在这些单元格中输入目标函数系数。 步骤2 确定决策变量存放单元格，并任意输入一组数据。 步骤3 确定约束条件中左端项系数存放单元格，并输入约束条件左端项系数。 步骤4 在约束条件左端项系数存放单元格右边的单元格中输入约束条件左端项的计算公式，计算出约束条件左端项对应于目前决策变量的函数值。 步骤5 在步骤4的数据右边输入约束条件中右端项（即常数项）。 步骤6 确定目标函数值存放单元格，并在该单元格中输入目标函数值的计算公式。 例 建立如下线性规划问题的Excell 工作表： 12 121 21212max 1502102310034120..55150,0 z x x x x x x s t x x x x =++≤??+≤??+≤??≥? 解：下表是按照上述步骤建立的线性规划问题的Excell 工作表。 其中： D4=B2*B4+C2*C4, D5=B2*B5+C2*C5 , D6=B2*B6+C2*C6, C7= B2*B1+C2*C1 。 建立了Excel 工作表后，就可以利用其中的规划求解功能求相应的线性规划问题的解。求解步骤如下： 步骤1 单击[工具]菜单中的[规划求解]命令。 步骤2 弹出[规划求解参数]对话框，在其中输入参数。置目标单元格文本框中输入目标单元格；[等于]框架中选中[最大值＼最小值］单选按钮。 步骤3 设置可变单元格区域，按Ctrl 键，用鼠标进行选取，或在每选一个连续区域后，在其后输入逗号“，”。 步骤4 单击[约束］框架中的[添加]按钮。 步骤5 在弹出的[添加约束]对话框个输入约束条件． 步骤6 单击[添加]按钮、完成一个约束条件的添加。重复第5步，直到添加完所有条件 步骤7 单击[确定]按钮，返回到[规划求解参数]对话框，完成条件输入的[规划
利用Excel求解线性规划问题
利用Excel求解线性规划问题 线性规划问题的求解有很多方法，也有很多工具。比如常用的Matlab、Lingo，记得参加 数学建模的时候就是用的Lingo解决线性规划问题的。本文主要讲解如何使用Excel求解 线性规划问题，Excel本身是没有计算线性规划问题能力的，因此我们首先要加载相应的宏定义。一、加载宏定义（不同版本的加载方式有所不同）：Excel 2003：单击“工具”菜单，然后单击“加载宏”，选择“规划求解”点击确定。Excel 2007：方法一：用快捷键。先按Alt+T，再按I键，即可打开加载宏对话框。方法二：单击“Office按钮→Excel 选项→加载项”，确保“管理”右侧下拉列表中的选项是“Excel 加载项”，单击“转到”按钮即可。Excel 2010：直接在功能区中选择“开发工具”选项卡，在“加载项”组中单击“加载项”命令，选择“规划求解”点击确定。注意：如果功能区中没有“开发工具”选项卡，可以通过自定义功能区来 显示“开发工具”选项卡：单击“文件→选项→自定义功能区”，然后在右侧区域中勾选“开发 工具”并单击“确定”。二、初始化数据（以Excel 2010为例，其他版本大同小异）：比如 我们要计算的线性规划问题如下：那么，我们可以构造如下的表格数据。其中，B2:F2为待求的值Xi，B3:F3为目标函数的系数，B4:F4、B5:F5、B6:F6为约束条件的系数。在G3单元格中输入公式 =$B$2*B3+$C$2*C3+$D$2*D3+$E$2*E3+$F$2*F3，并将鼠标放到单元格的右下角会变成黑色十字架，向下拖拽复制单元格公式到G4、G5、G6单元格。 然后，单
用Excel求解线性规划及线性方程组的方法
第23卷总第44期 西北民族学院学报(自然科学版)Vol.23,No.2 2002年6月 Journal of N orthw est Minorities U niversity(Natural Science)J une,2002 用Excel求解线性规划及线性方程组的方法 王培麟 (番禺职业技术学院,广东番禺511483) [摘 要]对利用美国微软公司开发的Office组件中的电子表格软件Excel求解线性规划的方法给予了介绍,并将该功能给予扩充,给出了用该软件求解线性方程组的方法1 [关键词]Excel;线性规划;求解方法 [中图分类号]TP271+.7 [文献标识码]A [文章编号]1009-2102(2002)02-0037-03 Excel是美国微软公司开发的Office组件中的电子表格软件,它具有强大的电子表格处理功能,使用户能够轻松地制作表格,并具有对数据进行检索、分类、筛选、排序、计算、分析与统计等功能1对大多数用户而言,也许更注重于Excel的表格功能,而对于它的计算功能,特别是数学计算功能可能就不是十分熟悉1本文将介绍用Excel解线性规划及线性方程组的方法与技巧1 1 用Excel解线性规划 用Excel解线性规划,必须在Excel系统中加载“规划求解”项目1如果没有,可以启动Excel软件,进入Excel用户界面,然后使用“工具”菜单下“加载宏”菜单项之“规划求解”子项,则可完成“规划求解”项的加载1 下面通过例1的求解来说明使用Excel解线性规划问题的方法1 例1 线性规划模型为: min s=2x1+7x2+4x3+9x4+5x51 S.t 3x1+2x2+x3+6x4+18x5≥700 x1+0.5x2+0.2x3+2x4+0.5x5≥30 0.5x1+x2+0.2x3+2x4+0.5x5=200 x1≤50;x2≤60;x3≤50;x4≤70;x5≤40; x1,x2,x3,x4,x5≥0 1 求解的具体方法为:首先要建立电子表格模型,输入如图1所示的工作表1 工作表的格式不是固定不变的,可根据具体的需要进行调整1建立工作表的步骤为: 1)确定一些单元格来代表决策变量,本例中x1,x2,…,x5为决策变量,需要将它们放到一些单元格中,称为可变单元格1一般地,可变单元格使用Excel的某行一块连续的区域,如 [收稿日期]2002-04-01 [作者简介]王培麟(1963—),男,副教授,硕士,主要从事数学和计算机方面的教学与研究1 — 7 3 —
利用excel求解线性规划问题
利用excel 求解线性规划问题 “规划求解”示例 例1 美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A ，B 的台时、调试工序时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如下表所示。问该公司应制造两种家电各多少件，使获取的利润为最大。 1.建立数学模型 2. 打开excel ，输入下列数据。 3、如何在工作表中设置问题条件？先设置目标单元格，即最大利润，把它放在E1单元格上，可变单元格放置计划生产Ⅰ和Ⅱ产品的件数，这里把它放在C10：D10区域。F4：F6是约束单元格，要对它们的值进行约束。单击E1，在编辑框输入如图所示的公式。 注意，表示绝对引用的美元符号，可以单击F4功能键添加。 ???????>=<=+<=+<=+=0 ,5242615 5..2max 212121 221x x x x x x x t s x x z
4、单击E4单击格式，在编辑栏上输入公式：=$C$4*$C$10+$D$4*$D$10。绝对引用单元格有一个好处，显示的单元格位置变化时，引用的数据没改变。 5、单击E5单击格式，在编辑栏上输入公式：=$C$5*$C$10+$D$5*$D$10。 6、单击E6单击格式，在编辑栏上输入公式：=$C$6*$C$10+$D$6*$D$10。 7、如何使用规划求解功能？单击工具菜单，如果看不到规划求解选项不要慌，先选加载宏。然后勾选规划求解，确定 单击数据菜单——点击“模拟分析”——
8、单击“规划求解”：指定目标单元格。一种方法是先选中目标单元格E1，单击工具---规划求解。另一种先单击工具---规划求解，再输入目标单元格名称。 输入可变单元格区域。比较快的方法是，单击折叠框，用鼠标选中可变单元格区域：$C$11：$E$11。注意勾选最大值哦。 设置目标： $E$1；点选“最大值”；设置：可变单元: $C$10：$D$10 9.设置条件不等式。单击添加，单击折叠框，选择单元格和不等号，单击关闭窗口，接着添加另一个条件。 1）.单击添加：输入约束不等式X1+X2≤0 ，即在E4输入：$E$4≤$F$4 2）.单击添加：输入约束不等式X1+X2≤0 ，即在E5输入：$E$5≤$F$5 2）.单击添加：输入约束不等式X1+X2≤0 ，即在E6输入：$E$6≤$F$6
如何在Excel中建立并求解线性规划模型
如何在Excel中建立并求解线性规划模型 刘桂莲 摘要：数学中线性规划问题的求解一直是很繁琐的，功能强大的Excel软件为我们提供了一种很好的求解方法，但这种方法却很少被人了解。本文就如何在Excel中建立并求解线性规划模型作了较详尽的论述。 关键词：线性规划数学模型电子表格模型规划求解Excel 线性规划是运筹学的一个分支，它的应用已愈来愈深入到社会生产和经济活动的各个领域。描述线性规划问题的抽象的数学式子是线性规划问题的数学模型。建立数学模型后，求解满足约束条件的目标函数的最优解是解决线性规划问题的关键。数学中常用的方法是图解法和单纯形法，而图解法只适用于两个变量的目标函数，单纯形法则计算量相当大，步骤烦琐，容易出错。在Excel中建立 电子表格模型，并利用它提供的“规划求解”工具，能轻松快捷地求解模型的解。 例如，某玻璃制品公司有三个工厂，公司目前决定停止不赢利产品的生产并撤出生产能力来生产两种新开发的产品：玻璃门和双把窗。估计三个工厂每周可用来生产新产品的时间分别为4小时、12小时、18小时，而每扇门需工厂1生产时间1个小时和工厂3生产时间3个小时，每扇窗需工厂2和工厂3生产时间各为2个小时，预测门的单位利润是300元，窗的单位利润是500元，问每周两种新产品数量的哪种组合能使总利润最大？ 问题的决策变量有两个：每周门的生产数量和窗的生产数量，目标是总利润最大，需满足的条件是：⑴三个工厂每周用于生产新产品的时间w每周可得时间 ⑵每周门、窗的生产数量均》0。设每周门的生产数量为X，窗的生产数量为y，则该问题的数学模型即为：最大化利润P =300x+500y,约束条件：xw4, 2y< 12，3x+2yw 18，x>0和y》0。 将上表的有关数据输入到Excel中，建立如图1所示的电子表格模型。被输入已知数据的单元格是数据单元格，如单元格C5：D8，G5：G7。决策变量(即两种产品每周的生产量)放在单元格C9和D9，正好定位在这些产品所在列的 数据单元格下面，这种含有需要做出决策的单元格是可变单元格。单元格E5： E7是用来计算各个工厂每周的总生产时间，如单元格E5就是用C5：D5和C9: D9的对应数值各自相乘再总加得到。Excel中有一个叫SUMPRODUCT的函数 能对相等行数和相等列数的两个变化范围的单元格中的值乘积后进行加和。被加 和的每个值是对第一个变化范围的一些值和对应位置的第二个变化范围的一些值的积。女口 E5=SUMPRODUCT(C5 : D5，C9：D9)是把C5：D5变化范围的每个值与C9 : D9变化范围中对应的每个值相乘，然后各个积相加。同样 E6=SUMPRODUCT(C6 : D6, C9：D9)，E7=SUMPRODUCT(C7 : D7, C9：D9)， E5、E6、E7这些单元格的数值是依赖于可变单元格的，它们是输出单元格。单元格F5、 F6、F7中的“W”符号表示它们左边的总值不允许超过列G中的对应
使用单纯形法解线性规划问题
使用单纯形法解线性规划 问题 The Standardization Office was revised on the afternoon of December 13, 2020
使用单纯形法解线性规划问题 要求：目标函数为：123min 3z x x x =-- 约束条件为： 123123 1312321142321,,0 x x x x x x x x x x x -+≤??-++≥?? -+=??≥? 用单纯形法列表求解，写出计算过程。 解： 1）将线性规划问题标准化如下： 目标函数为：123max max()3f z x x x =-=-++ .： 1234123561371234567211 42321,,,,,,0x x x x x x x x x x x x x x x x x x x -++=??-++-+=??-++=??≥? 2）找出初始基变量，为x 4、x 6、x 7，做出单纯形表如下： 表一：最初的单纯形表 3） 换入变量有两种取法，第一种取为x 2，相应的换出变量为x 6，进行第一 次迭代。迭代后新的单纯形表为： 表二：第一种换入换出变量取法迭代后的单纯形表
由于x1和x5对应的系数不是0就是负数，所以此时用单纯形法得不到最优解。 表一中也可以把换入变量取为x3，相应的换出变量为x7，进行一次迭代后的单纯形表为： 表三：第二种换入换出变量取法迭代后的单纯形表 4）表三中，取换入变量为x2，换出变量为x6，进行第二次迭代。之后的单纯形表为： 表四：第二次迭代后的单纯形表 5）表四中，取换入变量为x7，换出变量为x3，进行第三次迭代。之后的单纯形表为： 表五：第三次迭代后的单纯形表
2-线性规划问题的图解法
第二节 线性规划问题的图解法 对一个线性规划问题，建立数学模型之后，面临着如何求解的问题。这里先介绍含有两个未知变量的线性规划问题的图解法，它简单直观。 图解法的步骤： 步骤1：确定可行域。 第1步： 绘制约束等式直线，确定由约束等式直线决定的两个区域中哪个区域对应着由约束条件所定义的正确的不等式。我们通过画出指向正确区域的箭头，来说明这个正确区域。 第2步：确定可行域。 步骤2：画出目标函数的等值线，标出目标值改进的方向。 步骤3：确定最优解。用图示的方式朝着不断改进的目标函数值的方向，移动目标函数的等值线，直到等值线正好接触到可行域的边界。等值线正好接触到可行城边界的接触点对应着线性优化模型的最优解。 例1－3，用图解法求解线性规划问题 12 12121212max 23221228..416412,0 z x x x x x x s t x x x x =++≤??+≤??≤??≤?≥?? 解： 图1－3 （1） 画出线性规划问题的可行域，它是为以O(0,0)、A(0,3)、B(2,3)、C(4,2)、 D(0,4)为顶点的凸5边形，如图1－3。 （2） 画出一条目标函数的等值线12236x x +=，图1－3中红颜色的虚 线。
（3） 目标函数的等值线往上移动时，目标函数值增大（图1－3中红颜 色的实线）。由于问题的解要满足全部约束条件，因此目标函数的 等值线要与可行域有交点。当目标函数的等值线移动到 122314x x +=时，它与可行域只有一个交点，再往上移动时，与 可行域不再有交点。这就是说最优解为：124,2x x ==，最优目标 函数值为14。 例1-3中求解得到问题的最优解是唯一的，但对一般线性规划问题，求解结果还可能出现以下几种情况： （1）唯一最优解（2）多重最优解。 （3）无界解。 （4）无可行解。 这里我们不再举例，请大家自己阅读教材。 当线性规划问题的求解结果出现（3）、（4）两种情况时，一般说明线性规划问题建模有错误。前者缺乏必要的约束条件，后者是有矛盾的约束条件，建模时应注意。
使用Excel求解线性规划问题
使用Excel 求解线性规划问题 利用单纯形法手工计算线性规划问题是很麻烦的。office 软件是一目前常用的软件，我们可以利用office 软件中的Excel 工作表来求解本书中的所有线性规划问题。对于大型线性规划问题，需要应用专业软件，如Matlab ，Lindo ，lingo 等，这些软件的使用这里我们不作介绍，有需要的，自己阅读有关文献资料。 用Excel 工作表求解线性规划问题，我们需要先设计一个工作表，将线性规划问题中的有关数据填入该工作表中。所需的工作表可按下列步骤操作： 步骤 1 确定目标函数系数存放单元格，并在这些单元格中输入目标函数系数。 步骤 2 确定决策变量存放单元格，并任意输入一组数据。 步骤 3 确定约束条件中左端项系数存放单元格，并输入约束条件左端项系数。 步骤 4 在约束条件左端项系数存放单元格右边的单元格中输入约束条件左端项的计算公式，计算出约束条件左端项对应于目前决策变量的函数值。 步骤 5 在步骤4的数据右边输入约束条件中右端项（即常数项）。 步骤 6 确定目标函数值存放单元格，并在该单元格中输入目标函数值的计算公式。 例 建立如下线性规划问题的Excell 工作表： 12 12121212m ax 150******** 34120 ..55150,0z x x x x x x s t x x x x =++≤??+≤?? +≤??≥? 解：下表是按照上述步骤建立的线性规划问题的Excell 工作表。 其中： D4=B2*B4+C2*C4, D5=B2*B5+C2*C5 , D6=B2*B6+C2*C6, C7= B2*B1+C2*C1 。 建立了Excel 工作表后，就可以利用其中的规划求解功能求相应的线性规划问题的解。求解步骤如下： 步骤1 单击[工具]菜单中的[规划求解]命令。 步骤2 弹出[规划求解参数]对话框，在其中输入参数。置目标单元格文本框中输入目标单元格；[等于]框架中选中[最大值＼最小值］单选按钮。 步骤3 设置可变单元格区域，按Ctrl 键，用鼠标进行选取，或在每选一个连续区域后，在其后输入逗号“，”。 步骤4 单击[约束］框架中的[添加]按钮。 步骤5 在弹出的[添加约束]对话框个输入约束条件． 步骤6 单击[添加]按钮、完成一个约束条件的添加。重复第5步，直到添加完所有条件
EXCEL用于生产决策的线性规划法
EXCEL用于生产决策的线性规划法 朱建国 会计系 上海理工大学商学院 上海市复兴中路1195号 64337978 e-mail: zhjg@https://www.wendangku.net/doc/f12890467.html, 摘要：本文将介绍运用微软公司的Excel软件，来解决成本会计中生产决策的线性规划问题。企业生产两种或两种以上产品时，如果这些产品在企业生产能力、经济资源利用上存在着相互影响的关系，如何确定生产产量一般可以使用先行规划方法予以解决。一般在解线性规划问题时，多采用单纯形法，计算过程比较繁琐。微软公司的Excel软件有专用的规划求解加载宏可以利用，本文就此问题予以探讨。 关键词：Excel 线性规划生产决策 壹、引言 线性规划是运筹学的一个重要组成部分，专门用来对具有线性联系的极值问题进行求解的一种现代数学方法。所谓“线性”，是指所有变动因素的相互影响是直线关系。即约束条件和目标函数都是呈线性关系的。 在成本管理会计中线性规划研究的问题主要有以下两类： 对于已拥有一定数量的人力、物力和财力资源，研究如何合理使用，才能发挥它们的最大经济效益。 对于已确定的一项任务，研究如何统筹安排，才能以最少的人力、物力和财力资源去完成该项任务。 线性规划及其解法—单纯形法的出现，对运筹学的发展起了重大的推动作用。许多实际问题都可以化成线性规划来解决，而单纯形法有是一个行之有效的算法，但是，单纯形法的手工计算对于会计人员来讲，仍然是一项比较繁杂的工作。计算机的出现，为会计人员带来了一项非常有用的工具，使一些大型复杂的实际问题的解决成为现实。 微软公司的电子表格软件Excel提供的规划求解加载宏，“加载宏”是为EXCEL提供附加命令和函数的VBA模块。可以非常方便的完成线性规划的求解任务（事实上该工具也可以处理其他规划问题）。 贰、提出问题 企业在资源合理配置，产品品种决策等方面经常要使用线性规划法来求解，在产品生产安排的决策中，如果企业生产的产品品种有两种以上，且产品之间在资源需求、加工能力、市场需要等方面有一定的相互影响关系，就可以使用线性规划法进行决策，获得最优的产品生产数量，取得最大的边际贡献。 企业在运用线性规划法进行决策时，一般采用单纯形法进行求解，求解的步骤如下： 1.确定目标函数 2.确定约束条件 3.添加松弛变量
线性规划的单纯形法表格方法
线性规划的单纯形法表格方法 Max. z=5x 1+2x 2+3x 3 -x 4 +x 5 s.t. x 1+2x 2+2x 3 +x 4 =8 3x 1+4x 2+x 3 +x 5 =7 x j ≥0 j=1,2,3,4,5 表1 由表的中间行可求出基本可行解，令x1=x2=x3=0,由约束条件得 x4=8,x5=7. 表中最后一行分别为： ()1787811-=+-=???? ??-=z ()3)31(53111511=+--=???? ??--=-z c ()0)42(24211222=+--=???? ??--=-z c ()4)12(31211333=+--=??? ? ??--=-z c 因为c j -z j 行中存在正值，所以当前基本可行解不是最优解。c j -z j 行中的4最大因而非基变量 X 3使z 有最大的单位增量，把X 3选作新的（换入）基变量。 为确定被换出的基变量，采用最小比值法。用X 3列的值除以约束条件的常数（8/2=4，7/1=7）。第一行有最小比值，把它叫做旋转行。第一行原来的基变量是X 4 ，此时X 4为换出基变量，新的基变量为X 3、X 5。为此需要把表中X 3对应在约束条件中系数变为单位值（1，0）。在表1中：1）用2除旋转行使X 3系数为1；2）用-1/2乘旋转行加到第二行消去X 3。 ()153123413=+=???? ??=z ()1455/2/2113511=-=???? ??-=-z c ()-4623113222=-=???? ??-=-z c ()-21-11/2-21/13-133=-=??? ? ??-=-z c 因为c j -z j 行中仍存在正值，所以当前基本可行解不是最优解。c j -z j 行中的1最大因而非基变 量X 1使z 有最大的单位增量，把X 1选作新的（换入）基变量。
Excel规划求解的使用
§9.6 Excel软件“规划求解”的使用 用Excel软件的“规划求解”功能可以方便地求解线性规划、整数规划和非线性规划问题。但如果安装Office 97时采用的是典型安装方法，则【工具】菜单中是无“规划求解”功能项的。可参照§2.8中介绍的方法将未安装的组件安装完整。 下面以第八章例8.1为例介绍用Excel求解线性规划的操作步骤和运行输出结果的分析。 一．求解线性规划的操作过程 1．输入数据、公式和说明文字 （1）在工作表中按图9.7所示格式输入必要的说明文字（图中粗体字部分）和LP模型的原始数据（图中虚线框所示单元格内，注意并不需要化为标准型）；图中F4是放置目标函数的单元格，B5:D5是放置决策变量X1、X2、X3（既“可变单元格”）的区域。 图9.7 （2）在F4单元格内输入目标函数X0的计算公式： =B4*B5+C4*C5+D4*D5 或=SUMPRODUCT（B4:D4,B5:D5） 其中SUMPRODUCT（）函数返回两个或多个区域（即数组）中对应单元格乘积之和的值。该函数可在Excel的“数学和三角函数”中找到。 （1）在E8单元格中输入第一个约束条件左端的计算公式： =B8*$B$5+ C8*$C$5+D8*$D$5
或= SUMPRODUCT（B8:D8,$B$5:$D$5） 然后拖曳E8的填充柄将公式复制到E9、E10单元格（注意公式中的B5、C5、D5或B5:D5要使用绝对引用）。 当模型中的变量数较多时，使用SUMPRODUCT（）函数可大大加快以上两个公式的输入速度。 说明：图中粗线框是表示要输入公式的单元格。用Excel求解线性规划的数据输入格式可由用户自行设计，但以上介绍的格式不仅与我们所熟悉的LP模型相似，便于理解和使用；而且便于在对话框中输入约束条件。按以上格式输入说明文字后，还可以使系统所输出的三个运行结果报告更具可读性。 2．选【工具】→“规划求解”，“打开规划求解参数”对话框，见图9.8。 图9.8 （1）在“设置目标单元格”文本框中输入目标单元格（建议用鼠标选定的方法输入，下同），并选系统默认的“最大值”单选纽； （2）在“可变单元格”文本框中输入B5:D5（既指定决策变量所在的单元格）； 3．单击“约束”框中的〈添加〉按纽，打开“添加约束”对话框，见图9.9。 图9.9 （1）在“单元格引用位置”文本框中输入E8:E10；打开约束类型下拉列表框，选“〈=”；在“约束值”文本框中输入F8:F10；