运筹说 第161期 | 运筹学教程第一章习题讲解01:约束多变,如何找到最优解?

1.1 题目

1.1 答案

（1）图解法：

图1-1-1

当等值线与经过点（6/5，1/5）时，z最小，且有无穷多个最优解。

单纯形法：

在上述问题的约束条件中令，分别加入剩余变量x₃，x₄引入人工变量x₅，x₆，化为标准型：

由标准型列出初始单纯形表并逐步迭代，计算结果如表1-1-1所示。

表1-1-1

单纯形表的计算结果表明，，同时发现存在非基变量检验数为 0，说明该线性规划问题有无穷多最优解。

（2）图解法：

图1-1-2

在x₁，x₂≥0情况下约束条件无可行域，因此无可行解。

单纯形法：在添加松弛变量和人工变量后，模型可写成：

由标准型列出初始单纯形表并逐步迭代，计算结果如表1-1-2所示。

表1-1-2

此时所有检验数均≤0 ，但基变量中仍含有非零的人工变量（x₅=4），表明问题无可行解。

（3）图解法：

图1-1-3

当等值线经过点（6，5）时，z最大，且有唯一最优解。

单纯形法：

加入剩余变量 x₃，x₄，引入人工变量x₅，x₆，加入松弛变量x₇，x₈，化为标准型如下：

由标准型列出初始单纯形表并逐步迭代，计算结果如表1-1-3所示。

表1-1-3

单纯形表计算结果表明，。

（4）图解法：

该问题的可行域为无界域，如图1-1-4所示。目标函数有无界解。

图1-1-4

单纯形法：

加入剩余变量x₃，松弛变量x₄，引入人工变量x₅，化为标准型为：

由标准型列出初始单纯形表并逐步迭代，计算结果如表1-1-4所示。

表1-1-4

发现存在检验数x₃＞0，且其对应列向量均负数，根据解的判别规则，说明线性规划有无界解。

• 图解法的基本原理：通过绘制约束直线确定可行域，利用目标函数等值线的平移判断最优解的位置。线性规划若存在有限最优解，必存在一个可行域顶点达到最优值。

• 线性规划的四种求解结果：包括唯一最优解、无穷多最优解、无可行解和无界解。本题通过四个小问分别展示了这四种典型情况。

• 单纯形法的最优性判别：对最大化问题，采用检验数。当所有检验数均不大于零时，当前基可行解为最优解；若非基变量检验数为零，则需进一步判断是否存在其他最优解。

• 无可行解与无界解的判别：当人工变量无法消除且最终仍取正值时，原问题无可行解；当某非基变量检验数为正，而其对应列元素均不大于零时，原问题目标函数无界。

• 图解法与单纯形法的对应关系：单纯形法通过基变量的换入、换出实现基可行解之间的转移，在几何意义上通常对应于可行域相邻顶点之间的移动。

1.2 题目

1.2 答案

（1）化成标准形式：

（2）化成标准形式：

• 线性规划标准型的基本要求：目标函数采用最大化形式，约束条件全部转化为等式，所有决策变量均满足非负约束。

• 目标函数的转换：最小化问题可通过目标函数取相反数转化为最大化问题，即 min z等价于max(-z)。

• 不等式约束的转换：对“≤”约束增加非负松弛变量，对“≥”约束减去非负剩余变量，将不等式转化为等式；必要时先对约束两边同时乘以−1。

• 变量符号的处理：非正变量通过取相反数转化为非负变量；无约束变量通过两个非负变量之差表示。

• 标准型转换的注意事项：转换时必须保证原问题与标准型在可行性和目标函数取值上等价，特别注意负号、约束方向及变量符号的变化。

1.3 题目

1.3 答案

（1）由于约束方程组为3×5阶系数矩阵，其秩为3，从约束系数矩阵中选取三个线性无关的列向量作为基，取非基变量的值为 0，此时求出的基变量的值为方程的一个基解，有一个基就可以求出一个基解。设 X_i（i=1，2，...，8）是对应约束方程组的基变量，可知：

X₁=（x₃，x₄，x₅），令x₁=0，x₂=0，可求出x₃=4，x₄=12，x₅=18

X₂=（x₁，x₄，x₅），令x₃=0，x₂=0，可求出x₁=4 ，x₄=12，x₅=6

X₃=（x₁，x₃，x₄），令x₂=0，x₅=0，可求出x₁=6 ，x₃=-2，x₄=12

X₄=（x₁，x₂，x₄），令 x₃=0，x₅=0，可求出x₁=4 ，x₂=3，x₄=6

X₅=（x₂，x₃，x₅），令x₁=0，x₄=0，可求出x₂=6 ，x₃=4，x₅=6

X₆=（x₁，x₂，x₃），令x₄=0，x₅=0，可求出x₁=2 ，x₂=6，x₃=2

X₇=（x₁，x₂，x₅），令x₃=0，x₄=0，可求出x₁=4 ，x₂=6，x₅=-6

X₈=（x₂，x₃，x₄），令x₁=0，x₅=0，可求出x₂=9 ，x₃=4，x₄=-6

将每一个基解代入目标函数中，求出每一个对应的 值，满足约束条件  的解为基可行解，所有基可行解中满足  值最大的解为最优解。最终计算如表1-2-1所示，其中“□”标示的为基可行解，“*”标示的为最优解。

表1-2-1

故可得该问题的最优解为x₁=2，x₂=6，x₃=2，x₄=0，x₅=0，z^*=36。

（2）该线性规划问题的标准形式为：

其全部基解见表1-2-2中的①~⑥，其中“□”标示的为基可行解，“*”标示的为最优解，z^*=5。

表1-2-2

• 基的选取原则：对于约束矩阵 A，若其秩为m，则从中选取m个线性无关的列向量构成一个基，基变量与非基变量由此确定。

• 基解的求解方法：令全部非基变量为零，通过求解基变量对应的方程组得到基解。基解不一定满足非负约束。

• 基可行解的判别：在基解基础上，进一步检查所有变量是否非负。只有满足全部约束条件的基解才是基可行解。

• 最优解的确定：将各个基可行解代入目标函数进行比较，最大化问题取目标函数值最大者，最小化问题取目标函数值最小者。

• 基可行解的几何意义：基可行解对应线性规划可行域的顶点，不同基可能对应同一个顶点；多个基可行解也可能取得相同的最优目标函数值。

1.4 题目

1.4 答案

当d≠0时，由目标函数max z=cx₁+dx₂可得，其中为等值线的斜率。

（1）当k≤0时：

若 c≥0，d＞0，可行域的顶点（6，5）使目标函数达到最优；

若c≤0，d＜0，-1≤k≤0，可行域的顶点（3，0）使目标函数达到最优；

若c≤0，d＜0，-3/2≤k≤-1，可行域的顶点（2，1）使目标函数达到最优；

若c≤0，d＜0，k≤-3/2，可行域的顶点（0，4）使目标函数达到最优。

（2）当k≥0时：

若 c≥0，d＜0，可行域的顶点（6，0）使目标函数达到最优；

若c≤0，d＞0，可行域的顶点（0，5）使目标函数达到最优。

（3）当k不存在，即d=0时：

若c＞0，可行域的边界x₁=6使目标函数达到最优；

若c＜0，可行域的边界x₁=0使目标函数达到最优；

若c=0，目标函数恒为0，可行域内所有点均为最优解。

• 目标函数系数的作用：在约束条件不变的情况下，改变目标函数系数不会改变可行域，但会改变目标函数等值线的斜率，从而可能改变最优解的位置。

• 目标函数斜率的计算：对于max z=cx₁+dx₂，当d≠0时，等值线斜率为k=-c/d。可通过分析斜率变化判断不同顶点的最优性。

• 最优顶点的变化规律：随着目标函数系数变化，等值线的方向发生改变，最优解可能从可行域的一个顶点转移至另一个顶点。

• 多重最优解的产生条件：当目标函数等值线与可行域某条边平行，且该边达到最优目标函数值时，边上的所有点均为最优解。

• 特殊情况的处理：当d=0时，目标函数仅与x₁有关，应根据c的正负判断最优位置，而不能直接使用斜率公式。

1.5 题目

1.5 答案

上界对应的模型如下（c，b取大，a取小）

最优值（上界）为21。

下界对应的模型如下（c，b 取小，a取大）

最优值（下界）为6.4。

• 参数区间的基本含义：当目标函数系数、约束系数及资源限额在给定范围内变化时，可以通过构造边界模型确定最优目标函数值的可能范围。

• 最优值上界的确定：对本题最大化模型，在决策变量非负的条件下，取目标函数系数的上限、资源限额的上限及约束系数的下限，构造较为宽松的优化模型。

• 最优值下界的确定：取目标函数系数的下限、资源限额的下限及约束系数的上限，构造较为严格的优化模型。

• 边界模型的求解：分别求解上下界对应的线性规划模型，本题得到最优目标函数值的下界为6.4，上界为21。

• 参数变化分析的核心思想：利用参数的单调性和约束条件的松紧变化，分析最优目标函数值的变化范围，为后续灵敏度分析提供基础。

本期是《运筹学习题精讲篇》的第01期，我们围绕《运筹学教程》第一章的课后习题1.1—1.5进行了讲解。

1.1分别运用图解法和单纯形法求解线性规划问题，重点辨析了唯一最优解、无穷多最优解、无可行解和无界解四种情况，并梳理了检验数、人工变量及进基列元素的判别规则。1.2讲解线性规划的标准型转换，重点掌握目标函数取反、松弛变量与剩余变量的引入，以及非正变量和无约束变量的处理方法。1.3通过枚举基解、筛选基可行解并比较目标函数值，理清了基、基解、基可行解和最优解之间的关系。1.4分析目标函数系数变化对最优解的影响，利用等值线斜率判断不同顶点成为最优解的条件，理解最优解随目标函数方向变化的规律。1.5研究参数在给定区间内变化时最优目标函数值的上下界，通过调整目标函数系数、约束系数和资源限额，分别构造边界模型，确定最优值的变化范围。

总的来说，这五道题从线性规划的图解法、单纯形法和标准型转换出发，逐步深入到基可行解的求解、目标函数系数变化以及参数区间分析，构成了第一章线性规划基础知识的重要内容，也为后续学习单纯形法的进一步应用、对偶理论和灵敏度分析奠定了基础。

下一期，我们将继续讲解《运筹学教程》第一章的后续习题，重点学习大M法、两阶段法以及单纯形表的分析与计算，进一步掌握含人工变量的线性规划求解方法。如果你在学习过程中遇到哪道课后题卡住了，欢迎在留言区留下题号，我们下期见。