运筹学第2章习题

第三章线性规划对偶理论与灵敏度分析习题

一、思考题

1． 对偶问题和对偶变量的经济意义是什么

2．简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么

3．什么是资源的影子价格它和相应的市场价格之间有什么区别

4．如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检

验数之间的关系

5．利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解

6．在线性规划的最优单纯形表中，松弛变量（或剩余变量）0knx，其经济意

义是什么

7．在线性规划的最优单纯形表中，松弛变量knx的检验数0kn（标准形为

求最小值），其经济意义是什么

8．将ijjibca,,的变化直接反映到最优单纯形表中，表中原问题和对偶问题的解

将会出现什么变化有多少种不同情况如何去处理

二、判断下列说法是否正确

1．任何线性规划问题都存在且有唯一的对偶问题。

2．对偶问题的对偶问题一定是原问题。

3．若线性规划的原问题和其对偶问题都有最优解，则最优解一定相等。

4．对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定

有最优解。

5．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。

6．已知在线性规划的对偶问题的最优解中，对偶变量0iy，说明在最优生产计

划中，第i种资源已经完全用尽。

7．已知在线性规划的对偶问题的最优解中，对偶变量0iy，说明在最优生产计

划中，第i种资源一定还有剩余。

8．对于ijjibca,,来说，每一个都有有限的变化范围，当其改变超出了这个范围

之后，线性规划的最优解就会发生变化。

9．若某种资源的影子价格为u，则在其它资源数量不变的情况下，该资源增加k

个单位，相应的目标函数值增加 uk。

10．应用对偶单纯形法计算时，若单纯形表中某一基变量0ix，且ix所在行的

第 1 页 共 29 页 《运筹学》复习参考资料

资料加工、整理人——杨峰（函授总站高级讲师）

要求掌握的各部分知识点

第一部分 线性规划问题的求解（相当于教材的第一章）

——重要算法：单纯形迭代、大M法单纯形迭代、表上作业法、匈牙利法

第二部分 动态规划问题的求解（相当于教材的第三章）

——重要算法：图上标号法

第三部分 网络分析问题的求解（相当于教材的第四章）

——重要算法：破圈法、TP标号法、寻求网络最大流的标号法

第四部分 存储论简介（相当于教材的第七章）

※杨老师关于学习方法的提示：《运筹学》属于应用数学的范畴，本门课程在管理类本科生层次开设时，又称“管理运筹学”，是现代数学理论和计算机技术应用于管理科学的新兴学科。非应用数学系（专业）学生学习本门课程之前务必先具备“高数Ⅱ”（线性代数、概率论与数理统计）的知识基础。学员同志们通过学习，必须领会数学建模的思想、系统工程的思想。

非全日制学生学习时，只要求知道若干典型数学模型及其算法的操作，即只须明白“怎样做”，而不必去过问“为什么”要这样做。 第 2 页 共 29 页 第一部分 线性规划问题的求解

一、两个变量的线性规划问题的图解法：

㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。

定义：达到目标的可行解为最优解。

㈡图解法：

图解法采用直角坐标求解：x1——横轴；x2——竖轴。1、将约束条件（取等号）用直线绘出；

2、确定可行解域；

3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；

注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。

4、确定最优解及目标函数值。

㈢参考例题：（只要求下面这些有唯一最优解的类型）

例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：

《运筹学教程》第二章习题答案

1、（1）解：引入松弛变量x4≥0,x5≥0,化不等式为等式为：

minz=2X1 +3X2+4X3

s.t. X1+3X2+2X3+X4=7

4X1+2X2+X5=9

X1,X2,X4,X5≥0

化自由变量为非负，令X3=X3′-X3〞，X3′，X3〞≥0 ：

minz=2X1 +3X2+4X3′-4X3〞

s.t. X1+3X2+2 X3′-2 X3〞+X4=7

4X1+2X2+X5=9

X1,X2, X3′，X3〞，X4,X5 ≥0

(2)解：引入松弛变量x5≥0,剩余变量X6≥0，化不等式为等式为：

maxz=X1 -5X2+4X3- X4

s.t. X1+2X3+X5=7

X2-2X4-X6=9

X1,X2，X4,X5 ，X6≥0

化自由变量为非负，令X3=X3′-X3〞，X3′，X3〞≥0 ：

maxz=X1 -5X2+4X3′-4X3〞- X4

s.t. X1+2 X3′-2 X3〞+X5=7

X2-2X4-X6=9

X1,X2, X3′，X3〞，X4,X5 , X6≥0

化极大的目标函数为极小的目标函数： minz=-X1+5X2-4X3′+4X3〞+X4

s.t. X1+2 X3′-2 X3〞+X5=7

X2-2X4-X6=9

X1,X2, X3′，X3〞，X4,X5 , X6≥0

2、(1)是 不等式表示下图阴影区域，过阴影部分任意两点的直线仍在该区域内。

(2)不是 不等式表示下图阴影区域，过阴影部分且通过曲线上部的直线上的点不完全在该区域内。

(3)不是 不等式表示下图阴影区域，过阴影部分且通过圆内部的直线上的点不完全在该区域内。

3、在以下问题中，指出一组基础变量，求出所有基础可行解以及最优解。

（1）123123123123max2..2644,,0zxxxstxxxxxxxxx

1 第1章线性规划与单纯形法习题详解(习题)

用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。

（1）max 12zxx

51x+102x≤50

1x+2x≥1

2x≤4

1x，2x≥0

（2）min z=1x+2x

1x+32x≥3

1x+2x≥2

1x，2x≥0

（3）max z=21x+22x

1x-2x≥-1

1x+2x≤2

1x，2x≥0

（4）max z=1x+2x

1x-2x≥0

31x-2x≤-3

1x，2x≥0

将下列线性规划问题变换成标准型，并列出初始单纯形表。

（1）min z=-31x+42x-23x+54x

2 41x-2x+23x-4x=-2

1x+2x+33x-4x14

-21x+32x-3x+24x2

1x，2x，3x0，4x无约束

（2）max kkzsp

11nmkikikikzax

11(1,...,)mikkxin

ikx0 (i=1…n; k=1,…,m)

在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。

（1）max z=21x+32x+43x+74x

21x+32x-3x-44x=8

1x-22x+63x-74x=-3

1x,2x,3x,4x0

（2）max z=51x-22x+33x-64x

1x+22x+33x+44x=7

21x+2x+3x+24x=3

1x2x3x4x0

分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步相当于图形的哪一点。

（1）max z=21x+2x

3 31x+52x15

61x+22x24

1x，2x0

（2）max z=21x+52x

1x4

22x12

31x+22x18

1x，2x0

以题（1）为例，具体说明当目标函数中变量的系数怎样变动时，满足约束条件的可行域的每一个顶点，都可能使得目标函数值达到最优。