运筹学第二章

运筹学第二章习题答案运筹学是一门应用数学学科，旨在通过数学模型和定量方法来解决实际问题。

在运筹学的学习中，习题是必不可少的一部分，通过解答习题可以加深对知识的理解和应用。

本文将针对运筹学第二章的习题进行解答，希望能够帮助读者更好地掌握运筹学的知识。

第一题：线性规划问题的基本要素包括目标函数、约束条件和决策变量。

请问线性规划问题的目标函数通常是什么形式？为什么？答：线性规划问题的目标函数通常是线性函数的形式。

这是因为线性函数具有简单的数学性质，容易求解和分析。

此外，线性函数的图像为直线，可以通过直观的图形方法来理解问题的解。

第二题：什么是单纯形法？请简要描述单纯形法的基本思想和步骤。

答：单纯形法是一种求解线性规划问题的常用方法。

其基本思想是通过不断地移动到更优解的顶点，直到找到最优解。

单纯形法的步骤如下：1. 初始解的选择：选择一个可行解作为初始解。

初始解可以通过图形方法或其他启发式算法得到。

2. 进行迭代：通过计算目标函数的改进方向来确定下一步移动的方向。

如果目标函数不能再改进，则停止迭代，当前解即为最优解。

3. 顶点的移动：通过改变决策变量的值，将当前解移动到相邻的顶点。

移动的方向和距离由迭代步骤中计算得到。

4. 检验最优性：对移动后的顶点进行最优性检验，判断是否达到最优解。

如果达到最优解，则停止迭代，当前解即为最优解；否则，返回第2步。

第三题：什么是整数规划问题？请举一个实际应用的例子，并说明为什么需要使用整数规划方法来解决。

答：整数规划问题是线性规划问题的一种扩展形式，要求决策变量的取值为整数。

整数规划问题通常用于需要离散决策的场景，如生产调度、资源分配等。

举个例子，假设某公司有多个项目需要进行投资，每个项目的投资金额和预期收益已知。

公司希望选择一些项目进行投资，使得总投资金额不超过公司的可用资金，并最大化预期收益。

由于项目的投资金额和收益都是整数，这就是一个整数规划问题。

使用整数规划方法来解决这个问题的原因是，如果将决策变量的取值限制为整数，可以更好地符合实际情况。

China University of Mining and Technology
-43-
运 筹 学
线性规划的对偶理论
性质3 最优性定理：如果 X 0 是原问题的可行解， 0 是其对偶 Y 问题的可行解，并且:
CX 0 BY 0
即: z w
则 X 0是原问题的最优解，Y 0是其对偶问题的最优解。
T
分别是原问题和对偶问题的可行解。 且原问题的目标函数值为
min W 20 y1 20 y2 s.t. y1 2 y2 1 2 y1 y2 2 2y1 3 y2 3 3 y1 2 y2 4 y1 , y2 0
Z CX 10
min W 20 y1 20 y2 s.t. y1 2 y2 1 2 y1 y2 2 2y1 3 y2 3 3 y1 2 y2 4 y1 , y2 0
(DP)
-41China University of Mining and Technology
-44China University of Mining and Technology
运 筹 学
线性规划的对偶理论
性质4 强(主)对偶性：若原问题及其对偶问题均具有可行解， 则两者均具有最优解，且它们最优解的目标函数值相等。
还可推出另一结论：若一对对偶问题中的任意一个有最优解， 则另一个也有最优解，且目标函数最优值相等；若一个问题 无最优解，则另一问题也无最优解。 一对对偶问题的关系，有且仅有下列三种： 1. 都有最优解，且目标函数最优值相等； 2. 两个都无可行解； 3. 一个问题无界，则另一问题无可行解。
-1-
运 筹 学
学习要点： 1. 理解对偶理论，掌握描述一个线性规划问题 的对偶问题。 2. 能够运用对偶单纯形法来求解线性规划问题。 3. 会用互补松弛条件来考虑一对对偶问题的界。

总结：①在迭代过程中要保持常数列向量非负，这能确保基 可行解旳非负性。最小比值能做到这一点。 ②主元素不能为0。因为行旳初等变换不能把0变成1。 ③主元素不能为负数。因为用行旳初等变换把负数变成1会 把常数列中相应旳常数变成负数。
16
三、其他解旳情况 1、无穷多种解 例2 解LP问题：
min Z x1 2 x2 x3 0 x4 0 x5
xx51
1 2c 5 3c
其中c是满足非负性旳任意常数。
21
再由
x1,
x5
旳非负性，知：
x1 x2
1 2c c
0 0
x5 5 3c 0
解出 0 c 5 3
最优解为：
(2c 1, c,0,0,5 3c)T （其中0 c 5 ）
3
最优值为：max S 1.
22
2、无最优解旳两种情况：
相应地，将 X 0代入目的函数得 Z ( X 0 ) 0
从数学角度看，若让非基变量 x1, x2 取值从零增长，
6
min Z 2x1 x2 0x3 0x4 0x5
相应旳目旳函数值Z也将随之降低。所以有可能找到一种 新旳基本可行解，使其目旳函数值有所改善。即进行基变
换，换一种与它相邻旳基。再注意到 x1 前旳系数－2比 x2
x3
6 x1 x1
2x2 x2
x4 x5
xi 0
i 1,,5
15 24 5
目前可行基{ x3, x4 , x5 }所相应旳基本可行解
X 0 (0,0,15,24,5)T
(相应可行域旳 o(0,0) )
显然不是最优。 因为从经济意义上讲， x1 0, x2 0
意味着该厂不安排生产，所以没有利润。
2

1
=
j
j = 1
(
(
这就是运输问题的数学模型，它包含 m·n 变量, m + n 个约束条件。如果用单纯形法求解，先得在各约 束条件上加入一个人工变量(以便求出初始基可行解)。 因此，即使是 m = 3 ， n = 4 这样的简单问题, 变量数 就有19个之多，计算起来非常复杂。因此，我们有必 要针对运输问题的某些特点，来寻求更为简单方便的 求解方法。
销地产地
B1
B2
B3
B4
A1
x11
x12
A2
x21
x24
A3
x32
x34
x11 、 x12 、 x32 、 x34 、 x24 、 x21 构成一个闭回路. 这里有： i1 = 1 ， i2 = 3 ， i3 = 2；j1 = 1 ，j2 = 2 ，j3 = 4. 若把闭回路 的顶点在表中画出, 并且把相邻两个变量用一条直线相连 (今后就称这些直线为闭回路的边)。
第二节 表上作业法1. 表上作业法的基本概念与重要结论针对运输问题的数学模型结构的特殊性，它的约束方 程组的系数矩阵具有如下形式( 具体见下一张幻灯片 )，该 矩阵中， 每列只有两个元素为1，其余都是0。根据这个特 点，在单纯形法的基础上，创造出一种专门用来求解运输 问题的方法，这种方法我们称为表上作业法。运输问题也是一个线性规划问题，当用单纯形法进 行求解时，我们首先应当知道它的基变量的个数；其次， 要知道这样一组基变量应当是由哪些变量来组成。由运输 问题系数矩阵的形式并结合第一章单纯形算法的讨论可以 知道: 运输问题的每一组基变量应由 m+n-1个变量组成。 (即基变量的个数 = 产地个数 + 销售地个数 – 1) 进一步我 们想知道, 怎样的 m+n-1个变量会构成一组基变量？

第二章线性规划的对偶理论与灵敏度分析一、学习目的与要求 1、掌握对偶理论及其性质 2、掌握对偶单纯形法3、熟悉灵敏度分析的概念和内容4、掌握限制常数与价值系数、约束条件系数的变化对原最优解的影响5、掌握增加新变量和增加新的约束条件对原最优解的影响，并求出相应因素的灵敏度范围6、了解参数线性规划的解法 二、课时 6学时第一节 线性规划的对偶问题一、对偶问题的提出定义：一个线性规划问题常伴随着与之配对的、两者有密切联系的另一个线性规划问题，我们将其中一个称为原问题，另一个就称为对偶问题，在求出一个问题的解时，也同时给出了另一问题的解。

应用：在某些情况下，解对偶问题比解原问题更加容易；对偶变量有重要的经济解释(影子价格)；作为灵敏度分析的工具；对偶单纯形法(从一个非可行基出发，得到线性规划问题的最优解)；避免使用人工变量(人工变量带来很多麻烦，两阶段法则增加一倍的计算量)。

例：某家具厂木器车间生产木门与木窗；两种产品。

加工木门收入为56元/扇，加工木窗收入为30元/扇。

生产一扇木门需要木工4小时，油漆工2小时；生产一扇木窗需要木工3小时，油漆工1小时；该车间每日可用木工总共时为120小时，油漆工总工时为50小时。

问：(1)该车间应如何安排生产才能使每日收入最大？(2)假若有一个个体经营者，手中有一批木器家具生产订单。

他想利用该木器车间的木工与油漆工来加工完成他的订单。

他就要考虑付给该车间每个工时的价格。

他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图而愿意为他加工这批订单、又使自己所付的工时费用最少。

解(1)：设该车间每日安排生产木门x1扇，木窗x2扇，则数学模型为⎪⎩⎪⎨⎧≥≤+≤++=-0502120343056max 21212121x x x x x x x zX*=(15,20)’ Z*=1440元解(2)：设y 1为付给木工每个工时的价格，y 2为付给油工每个工时的价格⎪⎩⎪⎨⎧≥≥+≥++=-0303562450120min 21212121y y y y y y y wY*=(2,24)’ W*=1440元将上述问题1与问题2称为一对对偶问题，两者之间存在着紧密的联系与区别：它们都使用了木器生产车间相同的数据，只是数据在模型中所处的位置不同，反映所要表达的含义也不同。

例2.4：将以下线性规划问题转化为 标准形式
Max s.t. Z = 3 x1 - 5 x2 + 8 x3 2x1 + 2x2 - x3 = 15.7
4 x1
+ 3x3 = 8.9
x1 + x2 + x3 = 38 x2 , x3 ≥ 0
4.右端项有负值的问题：
在标准形式中，要求右端项 必须每一个分量非负。当某一个 右端项系数为负时，如 bi<0，则 把该等式约束两端同时乘以-1， 得到：
产品甲 设备A 3 产品乙 2 设备能力 （h） 65
设备B
设备C 利润（元/件）
2
0 1500
1
3 2500
40
75
问：如何安排生产计划，才能使制药厂利润最大？
解：设变量 xi为第i种（甲、乙）产品的生 产件数（i＝1，2）。根据前面分析，可 以建立如下的线性规划模型： Max
z = 1500 x1 + 2500 x2
MinZ=∑xi
i=1
X6 +
x1 x1 + x2 x2 + x3 x3 + x4 x4 + x5 x5 + x6
≥ 8 ≥ 12
≥ 10
≥ 8 ≥ 6 ≥ 4
二、线性规划模型的一般形式
目标函数 s.t.
产品对资源的 单位消耗量
利润系数
Max(Min)z=c1x1+c2x2+……+cnxn
a11x1+a12x2+……+a1nxn≥(=、≤)b1 a21x1+a22x2+……+a2nxn≥(=、≤)b2 …… am1x1+am2x2+……+amnxn≥(=、≤)bm

对偶问题同时解
– 原问题为基础可行解，对偶问题为非可行解，但满足
互补松弛条件；则当对偶问题为可行解时，取得最优 解
13
2.2.5 原问题检验数与对偶问题的解
• 在主对偶定理的证明中我们有：对偶(min型)变量的最 优解等于原问题松弛变量的机会成本，或者说原问题松 弛变量检验数的绝对值
• 容易证明，对偶问题最优解的剩余变量解值等于原问题 对应变量的检验数的绝对值
1
1/2 5/2
1
1
0
1/2 3/2
0
0
0
1/2 3/2
OBJ=
39
9/2
3
6
6
0
3/2
3/2
cj - zj
1/2
0
0
0
0
3/2 -M-3/2
0
x4
4
0
0
1
1
1
1
3
5
x1
6
1
0
2
2
0
1
1
3
x2
4
0
1
1
(1)
0
1
2
OBJ=
42
5
3
7
7
0
2
1
cj - zj
0
0
1
1
0
2 -M+1
0
x4
ቤተ መጻሕፍቲ ባይዱ
8
0
1
0
0
1
0
1
5
x1
数值，
g(Y0)=Y0b= CBB1 b
而原问题最优解的目标函数值为
f(X0)=CX0= CBB1 b 故由最优解判别定理可知Y0 为对偶问题的最优解。证毕。

反之，若经过迭代，不能把人工变量都变
为非基变量，则表明原LP问题无可行解。
19
第2章
单纯形法
2.3 人工变量法
2.3.1 大M法
在原问题的目标函数中添上全部人工变量，并令其系数 都为-M，
而M是一个充分大的正数。即
max z = c1x1 + c2x2 + c3x3 + … + cnxn – M( xn+1 + xn+2 +…+ xn+m )
思路：由一个基本可行解转化为另一个基本可行解。 等价改写为 目标方程 max z max z = 3x1+5x2 z -3x1 -5x2 = 0 z -3x1 -5x2 x1 +x3 x1 +x3 = 8 2x2 +x4 2x2 +x4 = 12 s.t. s.t. 3x1+4x2 +x5 3x1 + 4x2 +x5 = 36 x1 ， x2 ，x3，x4，x5 x1 ， x2 ，x3，x4，x5 ≥ 0
以主列中正值元素为分母，同行右端常数为分子，求比值；
6
第2章
单纯形法
2.1 单纯形法的基本思想
(Ⅰ)
用换基运算 将X0 转化为 另一个基本 可行解 X1。
z- 3x1 -5x2 = 0 0 换基运算—— x1 +x3 = 8 ① 方程组的初等变换 目的是把主列变为 22x2 +x4 = 12 ② 单位向量：主元变 3x1 + 4x2 +x5 = 36 ③ 为1，其余变为0。 X0 = ( 0, 0, 8, 12, 36 )T z0 = 0
⑴ 当前基：m阶排列阵

(5.5) (5.6)
4.3 对偶问题的基本性质
证： 设B是一可行基，于是A=(B,N)
max z=CBXB+ CNXN BXB+BXN +Xξ=b X,XB,Xξ ≥0
其中Yξ=(Yξ1, Yξ2)
min ω =Yb YB－Yξ1=CB YN－Yξ2=CN Y, Yξ1 Yξ2 ≥0
(5.5) (5.6)
x1﹐x2 ≥0
关系？
对原模型设： 1 2
A= 4 0 b=(8,16,12)T C=(2，3) 04
X=（x1，x2）T Y=（y1，y2 ，y3 ） 则可得:
4.1 对偶问题的提出
min ω=8 y1+16y2 +12y3
y1+4y2
≥2
2 y1 +4y3≥3
与
y1 ， y2 ，y3≥0 12
max z＝2x1+3x2 x1＋ 2x2 ≤8
4x1
≤16
4x2 ≤12
x1﹐x2 ≥0
有何关 系？
对愿模型设： A= 4 0 04
b=(8,16,12)T C=(2，3)
X=（x1，x2）T
Y=（y1，y2 ，y3 ） 则可得:
max z=CX AX≤b （5.1） 和
min ω =Yb YA ≥ C （5.2）
120
A=
1 -3
0 2
1 1
1 -1 1
b=(2,3,-5,1)T C=(5,4, 6)
确定约束条件
YA
C
x1 ≥0 ﹐x2≤0, x3 无约束
解：因原问题有3个变 于是 量，4个约束条件， 所以对偶问题4个 变量，3个约束条

运筹学第二章习题和答案运筹学是一门研究如何通过数学模型和方法来优化决策和资源分配的学科。

在运筹学的学习过程中，习题是非常重要的一部分。

通过做习题，我们可以巩固理论知识，提高解决问题的能力。

本文将针对运筹学第二章的习题进行讨论和答案解析。

第二章主要介绍了线性规划的基本概念和方法。

线性规划是一种常见的优化问题，其数学模型可以表示为最大化或最小化一个线性目标函数的同时满足一组线性约束条件。

在解决线性规划问题时，我们常常使用单纯形法或者内点法等方法。

习题2.1：一个公司生产两种产品A和B，每个单位A产品的利润为3万元，每个单位B产品的利润为4万元。

公司的生产能力为每天生产A产品100个单位，B产品80个单位。

产品A和B分别需要2个和3个单位的原材料X和Y。

而公司每天可用的原材料X和Y分别为180个单位和210个单位。

问该公司应如何安排生产，才能使利润最大化？解析：首先，我们需要定义决策变量。

假设公司每天生产A产品x个单位，B 产品y个单位。

则我们的目标是最大化利润，即最大化目标函数Z=3x+4y。

同时，我们需要满足生产能力和原材料约束条件。

生产能力约束条件为x≤100，y≤80。

原材料约束条件为2x+3y≤180，2x+3y≤210。

通过绘制约束条件的图形，我们可以得到可行解的区域。

在该区域内，我们需要找到目标函数Z=3x+4y的最大值点。

通过计算，我们可以得到最大利润为320万元，此时生产100个单位的A产品和60个单位的B产品。

习题2.2：某工厂生产两种产品，产品A和产品B。

产品A的生产需要1个单位的原材料X和2个单位的原材料Y，产品B的生产需要2个单位的原材料X 和1个单位的原材料Y。

每个单位的产品A的利润为3万元，每个单位的产品B的利润为4万元。

工厂每天可用的原材料X和Y分别为10个单位和12个单位。

问该工厂应如何安排生产，才能使利润最大化？解析：同样地，我们首先定义决策变量。

假设工厂每天生产A产品x个单位，B产品y个单位。

❖ 影子价格不是市场价格，而是在现有技术和管理条件下， 新增单位资源所能够创造的价值，是特定企业的一种边 际价格；不同企业或同一企业不同时期，同种资源的影 子价格可能不同；当市场价格高于影子价格，可以卖出； 相反，则应买进，以获取更大收益
Ma例x：Z （ 2第x一1 章3例x22）
2 x1 2 x2 12
当原问题和对偶问题都取得最优解时，这 一对线性规划对应的目标函数值是相等的：
Zmax=Wmin
二、原问题和对偶问题的关系
1、对称形式的对偶关系
（1）定义：若原问题是
MaxZ c1 x1 c2 x2 cn xn
a11x1 a12 x2 a1n xn b1
s.t.a21
x1
a22
二、 手工进行灵敏度分析的基本原则 1、在最优表格的基础上进行； 2、尽量减少附加计算工作量；
5y3 3
，y
2
3
0
（用于生产第i种产 品的资源转让收益不 小于生产该种产品时 获得的利润）
对偶变量的经济意义可以解释为对工时及原材 料的单位定价 ；
若工厂自己不生产产品A、B和C，将现 有的工时及原材料转而接受外来加工时， 那么上述的价格系统能保证不亏本又最富 有竞争力（包工及原材料的总价格最低）
内，使得产品的总利润最大 。
MaxZ 2x1 3x 2
2x1 2x2 12
s.t.54xx12
16 15
x1, x 2 0
它的对偶问题就是一个价格系统，使在平衡了 劳动力和原材料的直接成本后，所确定的价格系统 最具有竞争力：
MinW 12y1 16y2 15y3
2y1 4y2
2
s.t.2y1y，1y
y1, y2, , ym 0

==８ ==6
① ② ③
－２Ｘ４＋Ｘ５ ＝１２
得到新的基本可行解 X1 =(0,6,8,0,12)T
(1)、决定进基变量：1=--3, X1进基 (2)、决定离基变量：最小比值规则来确定主 元与离基变量.
则Xl为进基变量。 MIN(8/1,-,12/3)=12/3 此时可以确定X5为离基变量
Z
X(0) =(0, 0, 10, 15 )T
Z0 =0
Z-30X1-20X2 =0 选中X1从0↗，X2 =0 X3=10-(-X1 )0
X4=15-(-3X1 )0 求X1， X1→+ ,Z→+
2.2.3 单纯形法计算之例
2-3 人工变量法 (Artificial Variable)
+1/2X4
+X5 =42 =6
X3 +2/3X4 -1/3X5 =4
X2 +1/2X4
X1 -2/3X4+1/3X5=4 令X4 =X5 =0 X =(4, 6, 4, 0, 0)T Z =42
。此时4=1/2,
Z值不 再增大了,X值是最优基本解
5
=1,
* T * 即:X =(4,6) ,Z =42
检验数
当目标方程中基变量系数全为0时，非基 变量的系数可以作为检验当前的基本可 行解是否最优的标志，称之为检验数。
(2)、判定解是否最优 Z-3X1-5X2 =0 当X1从0↗或X2从0↗ Z从0↗ ∴ X0 不是最优解
(3)、由一个基可行解→另一个基可行解。 ∵ -5<-3 选X2从0↗，X1 =0 X3 =8 X4 =12-2X2 0 X2 12/2
N
沿边界找新 的基本可行解
结束

CB
-3 -5 -Z’
xB x1 X2
2.4 对偶解的经济解释
一、对偶线性规划 的解： P55
Cj xB x3 x1 x2 z b 7/2 7/2 3/2 x1 1 0 0 y4 Cj yB b y1 15/2 0 原问题变量 x2 0 0 1 0 y5 对偶问题变量 y2 y3 x3 1 0 0 0 y1 原问题变量 x4 5/4 1/4 -1/4 1/4 y2 x5 -15/2 -1/2 3/2 1/2 y3
T.G.Koopman（库普曼）和 L.V.Kamtorovich（康脱罗维奇）
二人因此而共同分享了1975年的第7届诺贝尔经 济学奖。
2.5 灵敏度分析
一、灵敏度分析的含义 是指系统或事物因周围条件变化显示出来的敏感性程度的分析。 对于线性规划问题的灵敏度分析是指参数A，b，C变化引起的 对原问题解的变化的分析。 其中：A为技术参数矩阵，b为资源向量，C为价值向量 可以用参数变化后的问题重新用单纯形法求解？ 没必要，意义不大，有些问题看不出来。 把相应的变化反映到最终单纯形表中，再根据情况用相应的方 法求解。
Z 50 x1 30 x2
2.1 线性规划的对偶问题与对偶理论
假设现有乙公司准备租借用(购买)该木器厂的木工和 油漆工两种劳力的劳务，需要考虑这两种劳务以什么 样的价格租入最合算？而同时甲公司要以什么条件才 会租让？甲公司肯定会以自己利用两种劳力的劳务组 织生产所获得的利润最大为条件，设每个木工的租用 价格为y1，每个油漆工的租用价格为y2，则乙公司愿 意租用的出资为：
0 变量 0 无限制
型 约束 型 型
0 变量 0 无限制
型 约束 型 型

写出对偶问题
2 y1 3 y2 y3 2 3 y1 y2 4 y3 3 5 y1 7 y2 6 y3 4 y , y , y 0 1 2 3
原—对偶问题的相互变换形式
原问题（或对偶问题） 目标函数 max 约 束 条 件 变 量 m个 ≤ ≥ = n个 ≥0 ≤0 无约束 约束条件右端项 目标函数变量的系数 对偶问题（或原问题） 目标函数 min m个 ≥0 ≤0 无约束 n个 ≥ ≤ = 目标函数变量的系数 约束条件右端项 变 量 约 束 条 件
设y1 , y2 , y3分别为三种资源的收费单价，所以 有下式： 5 y1 2 y2 y3 10 2 y1 3 y2 5 y3 18 y1 , y2 , y3 0 就目标而言，用下式可以表达： 170 y1 100 y2 150 y3 W
一般而言，W 越小越好，但因需双方满意，故
变为对称形式
m axZ 2 x1 3 x 2 4 x 3 2 x 3 x 2 5 x 3 2 3 x1 x 2 7 x 3 3 x1 4 x 2 6 x 3 5 x1 , x 2 , x 3 0
min W 2 y1 3 y2 5 y3
B
1 0
M-1
-2
最 终 表
cj cB 3 -1 -1 xB x1 x2 x3 检验数 b 4 1 9
3 x1 1 0 0 0
-1 x2
-1 x3 0 0 1 0
0 x4 1/3 0 2/3 -1/3
I
0 1 0 0
-1/3 1/3-M 2/3- M
所以， X*=（4 , 1 , 9），Z = 2
初 始 表

3 x1 2 x2
7x4 4
2 x1 3 x2 4 x3 x4 6
x1 0, x2 , x3 0, x4无 约 束
解：原问题的对偶问题为
mi nW 5 y1 4 y2 6 y3
4 y1 3 y2 2 y3 2

20
一组互为对偶的线性规划问题的解之间只有 下列三种情况:
(1)两个规划问题都有可行解(此时,两个规划问题都有最优 解,且最优值相等);
(2)两个规划问题都不可行; (3) 一个规划问题不可行,另一个规划问题有可行解,且具有
无界解。
21
（4）互补松弛性： 在线性规划问题的最优解中，
则 aij xj * = bi ；
bi , 则 y i* = 0 (4)’ 互补松弛性：
在线性规划问题的最优解中， 则 aij yi * = cj ；
>cj , 则 xj* = 0
n
若 y i * >0,
j=1 n
若 a ij xj * <
j=1
m
若 x j * >0,
i=1 m
若 a ij yi*
i=1 22
m
= 证b：i y∵i*
y1 3 y1

2 y2
3 y3 4 y3
3 5

2 y1 7 y2 y3 1
y1

0,
y2

0,
y
无
3
约
束
对偶问题的对 偶还是原问题
14
• 练习 写出下列线性规划问题的对偶问题.
max Z 4x1 3x2 2x3
4x1

m
m
n
m
n
i
c x a x y b y
j 1 j j i 1 j 1 ij j i i 1 i
m
m
i
2.最优性 是原问题的可行解, 是其对偶问题的可行解，
ˆ bT Y ) ˆ (CX
则 是原问题的最优解
是对偶问题的最优解
证明：CX * bT Y * ˆ ˆ CX CX * bT Y * bT Y ˆ ˆ CX CX * bT Y * bT Y
j 1
( a
j 1 i 1
n
m
ij
ˆ ˆ yi c j ) x j 0
m
ˆ ˆ j 1,..., n, ( aij yi c j ) x j 0
i 1
例 线性规划问题
已知其对偶问题的最优解是 Y * (6,0)T ，求 该问题的最优解。
* y1 0 * y2 0
1 3
3
2 0
设备能力 （h） 65
40 75
利润（元/件）
1500
2500
解：设变量xi为第i种（甲、乙）产品的生产件数
（i＝1,2）。则问题数学模型为：
max z =1500x1+2500x2
s.t. 3x1+2x2≤ 65 2x1+ x2≤ 40 3x2≤ 75 x1 ,x2 ≥0
若另一企业欲租用工厂的资源，工厂收取租金。试
例
解：首先在各约束条件上加上松弛变量， 将上述问题化为标准形式
CB 0 0
XB x3 x4
b 12 8
2 x1 2 1
3 x2 2 2
0 x3 1 0
0 x4 0 1