由图解法可知，若线性规划问题有两个可行域顶点X(1)和X(2)（基可行解）同时达到最优，则这两个顶点连线上的所有点?X(1)?(1??)X(2)(0???1)都是线性规划问题的最优解，此时，线性规划问题有无穷多个最优解。
对于一个有最优解的线性规划问题，从其最优单纯形表中判断是唯一解还是无穷多个解的准则：
对于线性规划问题的基B，若满足：
B-1b?0，CBB-1A-C?0
则基B是最优基；
此时，若所有非基变量的检验数严格大于零，即，σN=CBB-1N?CN?0，则基B是唯一的最优基，相应的基本解是线性规划问题的唯一最优解。
若存在一个非基变量xj的检验数等于零，则最优基和最优解不是唯一的。可将xj作为换入变量，由最小比值法求出换出变量，进行迭代运算，得到另一个基可行解，目标函数值保持不变，因此，该解也是最优解。将这两个最优解表示为
?X(1)?(1??)X(2)(0???1)，即求得该问题的所有最优解（无穷多个最优解）。
五、线性规划问题的EXCEL求解 1、建立线性规划问题的电子表格模型
我们以资源分配线性规划问题的数学模型为例，说明电子表格模型的建立。 设资源分配问题的数学模型为：
maxz?4x1?5x2x1?4??x2?3 (3-1) ?s..t??x1?2x2?8??x1,x2?0资源分配问题的数据表如3-3
表3-3 资源分配问题数据表 原料A 原料B 设备 单位产品利润(元) 甲产品 1 0 1 4 乙产品 0 1 2 5 资源限量 4(kg) 3(kg) 8(台时) 我们在原问题相关表格的基础上作些布局上的调整，就可以得到电子表格中
9
的模型描述。图3-1给出了资源分配问题的电子表格模型，该模型比较典型地反映了线性规划划问题在电子表格中的布局情况。
图3-1
下面逐步描述建立电子表格模型(图3-1)的过程。
在EXCEL电子表格中，我们将显示数据的单块小区域格称为数据单元格。 (1)单元格命名。为单元格命名可以使表格更容易理解。在资源分配问题的电子表格中，数据单元格所作的命名为：原料A、原料B、设备，单位利润(如图3-1)。为单元格命名，首先选中单元格，然后从插入菜单中选择命名，再输入名字（也可以直接在单元格中命名，或点击数据表上公式栏左侧的名字框命名）。 (2)电子表格布局。用电子表格建立数学模型，首先要解决关键的三个问题。这三个问题可表述为：一、要作什么决策？二、决策的约束条件有哪些？三、决策的绩效测度是什么？在资源分配线性规划问题中，三个关键问题可以确定：一、作出两种产品生产量的决策；二、决策的约束条件是两种产品生产所需资源不能超过可得资源量；三、决策的绩效测度是这两种产品生产的总利润。上述问题的确定过程，实际上就是线性规划模型如何在电子表格中布局的问题。
一般地，在原问题相关表格的基础上稍加调整，就可以建立电子表格模型。为方便理解和计算，我们在电子表格中增加了C9，D9单元格存放决策变量的值，并命名为“最优解”。增加 E5，E 6，E 7单元格，用以存放两种产品生产已经使用的资源数量，并命名为“合计”，增加F5，F6，F7单元格，存放符号“?”，这些单元格中的符号不参与计算，只起提示作用。另外，我们将E8单元格设置为目标利润值，用以存放相应决策方案对应的利润值，并称为目标单元格。目标单元格也可以根据需要、偏好和使用方便，设置在任意单元格内。
在E5，E6，E7单元格中的数字，实际上是代数模型中约束函数不等式左端的值，当给定决策变量的值时，约束函数左端表示资源实际被使用的数量。例如，对于第1个约束（原料A）的实际使用量是：
原料A的实际使用量= x1?1?x2?0
在电子表格中这个公式在E5单元格中表示为：
E5= C5?C9?D5?D9
上式中两对数相乘后相加，在EXCEL中有一个可以实现这一功能的函数
10
“sumproduct”，它可以将2至30个大小形状相同的单元格区域（每个单元格区域用逗号隔开）中的对应数值型元素（非数值型元素及空单元格作0处理）相乘后再相加，这个函数是求解线性规划问题中最常用的数学函数之一。上式用该函数表达就是：
E5= sumproduct（C5:C9,D5:D9）
注意在E5单元格输入公式时要在英文状态下输入等号右侧（包括等号）的内容，并且在数字和符号之间不能有空格（公式输入时不区分大小写）。
利用EXCEL函数的复制功能，这个公式可以通过不同的单元格引用方法复制到E6，E7，E8单元格中，避免重复输入公式。因为是纵向复制，可以把放有资源系数的单元格区域相对引用，把放有决策变量的单元格区域绝对引用或混合引用，这样，E5单元格中的公式就可以通过拖动复制E6，E7，E8单元格中。 用图3-1这样的布局把线性规划模型放到EXCEL工作表中后，可以尝试将某一决策值输入到C9,D9单元格中，电子表格会立即在E6，E7，E8显示出资源的使用数量，根据它们的值是否小于G列中对应行的数值，可以判断该决策是否可行。如果可行，还可以从E8单元格的数据获得该决策带来的利润大小。
将线性规划问题中A、b、C三类数据都输入电子表格后，我们就可以运用EXCEL表格中的“规划求解”工具来求解线性规划问题。
2、用EXCEL规划求解工具求解线性规划模型
EXCEL中的“规划求解”工具，可以方便地求解线性规划问题。“规划求解”加载宏是EXCEL的一个可选加载模块，在安装EXCEL时，只有在选择“定制安装”或“完全安装”时才可以选择装入这个模块。如果在EXCEL窗口菜单栏的“工具”菜单中没有“规划求解”选项，可以通过“工具”菜单的“加载宏”选项打开“加载宏”对话框来添加“规划求解”。
在应用规划求解工具前，要确认在EXCEL电子表格中包括决策变量、目标函数、约束函数三种信息的单元格或单元格区域。在图3-1的电子表格中已经包含了这些内容：决策变量在C9和D9单元格，目标函数的系数在C8和D8单元格，约束函数在C5，D5； C6，D6；C7，D7单元格。因为决策变量的值未知，所以，在决策变量所在的单元格中先填上初始值“0”，当然也可以什么都不填，系统会默认它为零。在求解后，EXCEL会自动将它们替换成决策变量的最优值。
下面用EXCEL规划求解功能求解资源分配问题。
首先，选取“工具”菜单栏，在弹出的子菜单中选择“规划求解”命令，就会弹出“规划求解参数”对话框。“规划求解参数”对话框的作用就是让计算机知道模型的各个组成部分放在电子表格中的什么地方，我们可以通过键入单元格（或单元区域）的地址或用鼠标在电子表格相应的单元格（或单元区域）单击或拖动的办法将有关信息加入到对话框相应的位置。具体步骤如下：
11
（1）设置目标单元格
在“规划求解参数”对话框中应该指定目标函数所在单元格的引用位置，此目标单元格经求解后获得某一特定数值、最大值、最小值。因此，该单元格必须包含公式。在资源分配问题中，由于目标函数在E8单元格，所以输入“E8”。输入后EXCEL会自动将其变成该单元格的绝对地址加以固定。
（2）等于
在此指定是否需要对目标单元格求取最大值、最小值或某一指定数值。如果需要让目标函数为某一指定数值，则要在右侧编辑框中键入。在资源分配问题中是求目标函数最大化，所以选最大值。
（3）可变单元格
可变单元格指定决策变量所在的各单元格，不含公式，可以有多个区域或单元格。求解时，其中的数据不断地调整，直到满足约束条件，并且“设置目标单元格”编辑框中指定的单元格达到目标值。可变目标单元格必须直接或间接与目标单元格相联系。在资源分配问题中，决策变量在C9和D9单元格内，所以在此键入“C9：D9”单元格引用区域。
（4）约束
在“规划求解参数”对话框点击“添加”按钮就会显示“添加约束”对话框。在此有三个选项需填写。
1）单元格引用位置。指定需要约束其中数据的单元格或单元格区域，一般在此处添加约束函数不等式左侧的函数表达式的单元格或单元格区域。在资源分配问题中，输入”E5:E7”。
2）约束值。在此指定对“单元格引用位置”编辑框中输入的内容的限制条件，即对于单元格引用及其约束条件，选定相应的需要添加或修改的关系运算符(>=,<=,=,int,bin ),然后在右侧的编辑框中输入数字、单元格或区域引用及公式等约束条件。在资源分配问题中，输入“G5:G7”。
3）添加。单击此按钮可以在不返回“规划求解参数”对话框的情况下继续添加其他约束条件。在资源分配问题中，由于已经把所有约束条件都一次添加上了，所以只需单击“确定”按钮，回到“规划求解参数”对话框，我们发现“约束”一栏中已经显示了刚刚添加的约束。
注意，在资源分配问题中，由于所有的不等式约束都是“<=”，所以可以利用单元格引用区域一次添加。否则，要分几次添加约束。
（5）规划求解选项
在“规划求解参数”对话框上单击“选项”按钮就会弹出“规划求解选项”对话框，它可以对求解运算的一些高级属性选项进行设定，这些高级属性选项如下：
1）最长运算时间。在此设定求解过程的时间，可输入的最大值为32767秒，
12
相关推荐：
loading