当前位置：文档之家 › 《运筹学》第二章线性规划

《运筹学》第二章线性规划

  • 格式：pdf
  • 大小：2.15 MB
  • 文档页数：46

下载文档原格式

  / 46

合集下载

管理运筹学第二章 线性规划的图解法

管理运筹学第二章 线性规划的图解法

B、约束条件不是等式的问题：
若约束条件为 ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量si ，使它等于约束右 边与左边之差 si=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，si 也具有非负约束，即si≥0， 这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn+si = bi
第二章 线性规划 的图解法
一、线性规划的概念 二、线性规划问题的提出 三、线性规划的数学模型 四、线性规划的图解法 五、线性规划解的情况 六、LP图解法的灵敏度分析
一、线性规划的概念
线性规划Linear Programming 简称LP，是一 种解决在线性约束条件下追求最大或最小的 线性目标函数的方法。 线性规划的目标和约束条件都可以表示成线 性的式子。
max z 3 x1 2 x2
2 x1 x2 ≤ 10 设备B台时占用 s.t. x1 x2 ≤ 8 x , x ≥ 0 产量非负 1 2
决策变量 （decision variable） 目标函数 （objective function） 约束条件 （subject to）

-ai1
x1-ai2 x2- … -ain xn = -bi 。
例1.3：将以下线性规划问题转化为标准形式 Min f = 3.6 x1 - 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 - 6.1 x3 ≤15.7 4.1 x1 + 3.3 x3 ≥8.9 x1 + x2 + x3 = 38 x 1 , x 2 , x3 ≥ 0

第二章线性规划

第二章线性规划



线性规划要研究的两类问题中都包含有约束条件和目 标函数。用数学的方式描述，规划的目的就是在给定 的限制条件（或称约束条件）下，求目标函数的极值 问题（包括极小值和极大值）。
2
线性规划的数学模型
3
解： 设产品 的产量为：1 , 产品 的产量为：x2 x
4
5
6
7

配料问题：由若干种不同价格、不同成分含量的原料，用 不同的配比混合调配出一些不同规格的产品，在原料的供 应量限制和保证产品成分含量的前提下，如何进行配料来 获取最大利润或使总成本最低。
15
2.2.3 线性规划求解的可能结局
1、有唯一的最优解
2、有无穷多个最优解 （将目标函数改为 z=4x1+3x2 ）
x2
max z 4 x1 3 x2 x1 2 x2 5 2 x x 4 1 2 s.t. 4 x1 3 x2 9 x1 , x2 0
3x1 2 x2 4 x3 3
3x1 2 x2 4 x3 xs 3
剩余变量
变量xs实际上是原式左端减去右端的差，即 ：
xs 3x1 2 x2 4 x3 3
当约束条件是“ ”型的不等式时，只要将该约 束条件左端减去一个非负的剩余变量即可化为等式。 无论是松弛变量还是剩余变量在决策中都不产生实际价 值，因此它们在目标函数中的系数都应该为零。有时也将松 29 弛变量和剩余变量统称为松弛变量。
2x1+x2=4 D C
x1+2x2=5 B 4x1+3x2=9 O A x1
16
3、无界解
指线性规划问题有可行解，但是 在可行域，目标函数值是无界的， 因而达不到有限最优值。因此线 性规划问题不存在最优解。

管理运筹学第二章线性规划的图解法

管理运筹学第二章线性规划的图解法

02
图解法的基本原理
图解法的概念
图解法是一种通过图形来直观展示线性规划问题解的方法。它通过在坐标系中绘 制可行域和目标函数，帮助我们理解问题的结构和最优解的位置。
图解法适用于线性规划问题中变量和约束条件较少的情况，能够直观地展示出最 优解的几何意义。
图解法的步骤
确定决策变量和目标函数
明确问题的决策变量和目标函数，以便在图 形中表示。
目标函数是要求最小化或最大化的函数，通常表示为 $f(x) = c_1x_1 + c_2x_2 + ldots + c_nx_n$。
04
约束条件是限制决策变量取值的条件，通常表示为 $a_1x_1 + a_2x_2 + ldots + a_nx_n leq b$或 $a_1x_1 + a_2x_2 + ldots + a_nx_n = b$。
LINDO是一款开源的线性规划求解器，用 户可以免费使用。
软件工具的使用方法
Excel
用户需要先在Excel中设置好线性规划模型，然后使 用“数据”菜单中的“规划求解”功能进行求解。
Gurobi/CPLEX/LINDO
这些软件通常需要用户先在软件界面中输入线性规划 模型，然后通过点击“求解”按钮进行求解。
实例三：分配问题
总结词
分配问题是指如何根据一定的分配原则 或目标，将有限的资源分配给不同的需 求方，以最大化整体效益。
VS
详细描述
分配问题在实际生活中广泛存在，如物资 分配、任务分配等。通过图解法，可以将 分配问题转化为线性规划模型，并利用图 形直观地展示最优解的资源分配方案。在 分配问题中，通常需要考虑不同需求方的 重要性和优先级，以及资源的有限性等因 素，以实现整体效益的最大化。

管理运筹学_第二章_线性规划的图解法

管理运筹学_第二章_线性规划的图解法

线性规划中超过约束最低限的部分，称为剩余量。 记s1,s2为剩余变量，s3为松弛变量，则s1=0, s2=125,
s3=0，加入松弛变量与剩余变量后例2的数学模型变为 标准型： 目标函数： min f =2x1+3x2+0s1+0s2+0s3 约束条件： x1+x2-s1=350， x1-s2=125, 2x1+x2+s3=600, x1, x2, s1,s2,s3≥0.
阴影部分的每 一点都是这个线 性规划的可行解， 而此公共部分是 可行解的集合， 称为可行域。
B
X2=250
100
100
300
x1
B点为最优解， X1+X2=300 坐标为（50, 250）， Z=0=50x1+100x2 此时Z=27500。 Z=10000=50x1+100x2 问题的解： 最优生产方案是生产I产品50单位，生产Ⅱ产品250单位，可得 最大利润27500元。
Z=10000=50x1+50x2
线段BC上的所有点都代表了最优解，对应的最优值相 同： 50x1+50x2=15000。
10
3. 无界解，即无最优解的情况。对下述线性规划问题：
目标函数：max z =x1+x2 约束条件：x1 - x2≤1 -3x1+2x2≤6 x1≥0, x2≥0．
x2 -3x1+2x2=6 3
其中ci为第i个决策变量xi在目标函数中的系数， aij为第i个约束条件中第j个决策变量xj的系数， bj(≥0)为第j个约束条件中的常数项。
16
灵敏度分析
灵敏度分析：求得最优解之后，研究线性规划的

运筹学第二章第6节矩阵法求解线性规划问题

运筹学第二章第6节矩阵法求解线性规划问题

（3）初始单纯性表与当前单纯性表关系
单纯性法的每一步就是：令非基变量XN（XN1和 XS2）=0，则当前基本可行解X=（XB，0） =（B-1b，0）。当前的目标函数值为 Z=CBB-1b，通过刚才用矩阵法的展示，我们发现： 1）B：初始单纯性表中基。 2）BN：初始单纯性表非基变量在A中对应的矩阵。 3）B-1：初始单纯性表中单位矩阵所对应的列在当 前矩阵中所构成的矩阵。 4）CB：当前基变量的价值向量。 5）CN：当前非基变量的价值向量。
2 x1 [1] 4 0 2
3 x2 0 0 1 0
0 x3 1 0 0 0
0 x4 0 1 0 0
0 x5 0 1/4 -3/4 θ 4 -
-1/2 2
在迭代到单纯性表2时，当前的基变量为x3，x4，x2，其中 x3和x4是松弛变量。这时，松弛变量中，x5为基变量，x3和 x4为非基变量，因此：基变量XB由两部分组成，一部分是 XB1=x2，一部分是XS1=x3和x4；非基变量XN由两部分组成， 一部分是XN1=x1，另外一部分是XS2=x5。
BX X
B
B
b BN X
1
N1
S2 X
N1
S2
;
1
B b B B N1 X
1
1
1
B S 2 X s2 ;
1
目标函数： z C B B b (C N1 C B B B N1 ) X (C S 2 C B B I ) X
1 S N1
令非基变量=0，由上式得到：
x1 2 x 2 x 3 4 x1 4 x2 x
j

8
x4 0
16 x 5 12
j 1, 2 , , 5

运筹学第二章

运筹学第二章

例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

运筹学--第二章 线性规划的对偶问题

运筹学--第二章 线性规划的对偶问题

习题二2.1 写出下列线性规划问题的对偶问题(1) max z ＝10x1＋x2＋2x3(2) max z ＝2x1＋x2＋3x3＋x4st. x1＋x2＋2 x3≤10 st. x1＋x2＋x3 ＋x4≤54x1＋x2＋x3≤20 2x1－x2＋3x3＝－4x j≥0 （j＝1,2,3）x1－x3＋x4≥1x1，x3≥0，x2，x4无约束(3) min z ＝3x1＋2 x2－3x3＋4x4(4) min z ＝－5 x1－6x2－7x3st. x1－2x2＋3x3＋4x4≤3 st. －x1＋5x2－3x3≥15x2＋3x3＋4x4≥－5 －5x1－6x2＋10x3≤202x1－3x2－7x3 －4x4＝2＝x1－x2－x3＝－5 x1≥0，x4≤0，x2，，x3无约束x1≤0，x2≥0，x3无约束2.2 已知线性规划问题max z＝CX，AX=b，X≥0。

分别说明发生下列情况时，其对偶问题的解的变化：（1）问题的第k个约束条件乘上常数λ（λ≠0）；（2）将第k个约束条件乘上常数λ（λ≠0）后加到第r个约束条件上；（3）目标函数改变为max z＝λCX（λ≠0）；'x代换。

（4）模型中全部x1用312.3 已知线性规划问题min z＝8x1＋6x2＋3x3＋6x4st. x1＋2x2＋x4≥33x1＋x2＋x3＋x4≥6x3 ＋x4＝2x1 ＋x3 ≥2x j≥0（j＝1,2,3,4）(1) 写出其对偶问题；(2) 已知原问题最优解为x*＝（1，1，2，0），试根据对偶理论，直接求出对偶问题的最优解。

2.4 已知线性规划问题min z＝2x1＋x2＋5x3＋6x4 对偶变量st. 2x1 ＋x3＋x4≤8 y12x1＋2x2＋x3＋2x4≤12 y2x j≥0（j＝1,2,3,4）对偶问题的最优解y1*=4；y2*=1，试对偶问题的性质，求出原问题的最优解。

2.5 考虑线性规划问题max z＝2x1＋4x2＋3x3st. 3x1＋4 x2＋2x3≤602x1＋x2＋2x3≤40x1＋3x2＋2x3≤80x j≥0 （j＝1,2,3）４７４８（1）写出其对偶问题（2）用单纯形法求解原问题，列出每步迭代计算得到的原问题的解与互补的对偶问题的解；（3）用对偶单纯形法求解其对偶问题，并列出每步迭代计算得到的对偶问题解及与其互补的对偶问题的解；（4）比较（2）和（3）计算结果。

管理运筹学课件第2章线性规划

管理运筹学课件第2章线性规划

2019/7/14
课件
4
2.1.1 线性规划问题的提出
承导入案例
产品甲 产品乙 生产能力
设备A
2
1
10
设备B
1
1
8
单位利润 3
2
决策变量 （decision variable）
设两种产品产量为x1,x2,则有: 总利润表三达要式素
最大化 max z 3x1 2x2
目标函数 （objective function） 约束条件
最优值：z=18
10 2x1+x2=10
8
6
(2,6) z=3×2+2×6=18
【例2.3】用图解法求LP最优解
max z 3x1 2x2
s.t.
2xx11

x2 x2
≤10 ≤8
x1, x2 ≥ 0
可行域
o
45
令3x1+2x2=12
x1+x2=8
8
x1
2019/7/14
课件
课件
6
2.1.2 线性规划的数学模型
线性规划的一般形式：
max(min)z c1x1 c2x2 cn xn
a11x1 a12 x2 s.t.a21x1 a22 x2
am1x1 am2 x2
a1n xn ≤ (或≥， ）b1 a2n xn ≤ (或≥， ）b2
11
2.2.3 线性规划几何解的讨论
线性规划几何解存在四种情况：唯一最优解、无穷 多最优解、无界解、无可行解。 可行域为封闭有界区域时，可能存在唯一最优解， 无穷多最优解两种情况； 可行域为非封闭无界区域时，可能存在唯一最优解， 无穷多最优解，无界解三种情况； 可行域为空集时，没有可行解，原问题没有最优解。

运筹学第二章线性规划的对偶理论

运筹学第二章线性规划的对偶理论

(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章-线性规划的对偶理论

运筹学第2章-线性规划的对偶理论
❖ 影子价格不是市场价格，而是在现有技术和管理条件下， 新增单位资源所能够创造的价值，是特定企业的一种边 际价格；不同企业或同一企业不同时期，同种资源的影 子价格可能不同；当市场价格高于影子价格，可以卖出； 相反，则应买进，以获取更大收益
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

运筹学—线性规划第2章

运筹学—线性规划第2章

1 1
1 0
0 1
0 0
6 2 0 0 1
1 0 0
则
B 0
1
0
的列是线性无关的，即
1
0
0 0 1
p3 0, p4 1 0 0
•
0
p5 0 是线性无关，因此 1
x3
x4
x5
是, 0
p2
1 2
不在这个基中，所以x1,
x2为非基变量。
定义10：使目标函数达到最优值的基本可行解，称为基
本最优值。
• 例4：（SLP)如例3，试找一个基本可行解。
1 1 0
解：B1
1
0
0
是其一个基矩阵.p1,p3, p5是一个基。
6 0 1
则 x1 , x3, x5为基变量。X2, x4为非基变量。令 x2=x4=0. 得x1=2, x3=3, x5=9. 故 x1=(2,0,3,0,9)是原问题的一个基本 可行解，B1为基可行基。
•当 由0连续变动到1时，点z由y沿此直线连续的变动到x，且 因z-y平行x-y，则有：z y (x y) 于是有：
z x (1 ) y
•这说明当 0 1 时，x (1 ) y表示以x.y为端点的直线段
上的所有点，因而它代表以 x.y为端点的直线段。 一般地，如果x.y是n维欧氏空间Rn中的两点，则有如下定义：
• 定义14：设R是Rn中的一个点集，（即R Rn），对于任意 两点x R, y R 以及满足0 1 的实数 ,恒有
x (1 )y R
则称R为凸集。
• 根据以上定义12及13可以看到，凸集的几何意义是：连接凸 集中任意两点的直线段仍在此集合内。
其可行域如上图，可行解（3，1，0，0）T。用x1, x2 表示则为图上点（3，1）。由图可见这不是可行域的 顶点。而我们将证明基本可行解是可行域的顶点。而 在例4中p1,p3线性无关，所以B=(p1,p3)是一个基矩阵， 对应的基本解为（4，0，0，0）T。用坐标x1, x2表示则 为平面上的点（4，0），是上图可行域的顶点。

《管理运筹学》第2章_线性规划

《管理运筹学》第2章_线性规划

我们通过画图可以知道该线性规划问题的可行解所在 的范围是无界的,目标函数值可以增大到无穷大,称这种 情况为无界解或无最优解,如下图所示: x2
Z
0
x优解呢?那也不一定,如在(1.3)中,将目 标函数由 Max Z = x1 + x2 改为 Min Z = x1 + x2 , 则可行解所在的范围虽然无界,但有最优解 x1 = x2 = 0 ,即 (0,0)点. 当求解结果出现(2)、(3)两种 情况时,一般均说明线性规划问题的数学模型存在错误 ,前者缺乏必要的约束条件,后者是存在矛盾的约束条 件,在建立数学模型时，应当注意。
可行域D非空有界：（1）有唯一解、（2）有无 穷多最优解 可行域D非空无界：求max（1）无界解。求min （1）有唯一解、 （2）有无穷多组最优解 可行域D空：无可行解
幻灯片 18
从图解法中可直观地看到:
※ 当线性规划问题的可行域非空时, 它是有界或无界凸多面体(形).
※若线性规划问题存在有界最优解,则
无可行解(Infeasibility Solution)
无可行解是指不存在满足全部约束条件 的解。在图形中，无可行解是指可行域不 存在。也就是说，没有任何一个点能够同 时满足所有约束条件。
举例说明这一情况。在2.1中如果我们增加约束条 件，生产Ⅰ、Ⅱ两种产品至少分别需要3千克。
现有的资源无法生产满足需要（3，3）的产品， 此外，我们可以准确地告诉管理者要生产(3,3) 换需要多少资源
1 A B C 价 格 3 1 0.5 2
2 2 0.5 1 7
3 1 0.2 0.2 4
4 6 2 2 9
5 18 0.5 0.8 5
需 求 700 30 200
解：设 x j

运筹学 第2章 线性规划的图解法

运筹学 第2章 线性规划的图解法

图2-1
管 理 运 筹 学
2-12
•
可行域
可行域的几何形状由于问题不同可以千变 万化，但可行域的几何结构是凸集 要求集合中的任何两点的连线段落在这个 集合中
•
•
管
理
运
筹
学
2-13
§2
图解法
（4）目标函数z=50x1+100x2，当z取某一固定值时得到一 条直线，直线上的每一点都具有相同的目标函数值，称之 为“等值线”。平行移动等值线，当移动到B点时，z在可 行域内实现了最大化。A，B，C，D，E是可行域的顶点，对 有限个约束条件则其可行域的顶点也是有限的。
1.极小化目标函数的问题： 设目标函数为 Min f = c1x1 + c2x2 + … + cnxn (可以)令 z ＝ -f ， 则该极小化问题与下面的极大化问题有相同的最优解， 即 Max z = - c1x1 - c2x2 - … - cnxn
在线性规划中，一个“ ”约束条件中没使用 的资源或能力称之为松弛量。 • 为了把一个线性规划标准化，需要有代表没有 使用的资源或能力的变量，称之为松弛变量，记为 si •
管 理 运 筹 学
2-19
§2 图 解 法
• 线性规划的标准化内容之一：——引入松驰变量（含 义是资源的剩余量） 例1 中引入 s1， s2， s3 模型化为 目标函数：Max z = 50 x1 + 100 x2 + 0 s1 + 0 s2 + 0 s3 约束条件：s.t. x1 + x2 + s1 = 300 2 x1 + x2 + s2 = 400 x2 + s3 = 250 x1 , x2 , s1 , s 2 , s3 ≥ 0 对于最优解 x1 =50 x2 = 250 ， s1 = 0 s2 =50 s3 = 0 把所有的约束条件都写成等式，称为线性规划模型的 标准化。

运筹学第四版第二章线性规划及单纯形法

运筹学第四版第二章线性规划及单纯形法

方案的制定受到那些现实条件制约：
确定约束条件
人力资源（劳动力）的限制： 9x1 4x2 360
设备工时的限制：
4x1 5x2 200
原材料资源的限制：
3x1 10x2 300
此外，决策变量的取值不应为负值即 x1 0, x2 0
6
综上所述，我们得到了这个问题的数学模型
目标函数 约束条件
大？
项目
Ⅰ
设备A (h)
0
设备B (h)
6
调试工序(h) 1
利润（元） 2
Ⅱ 每天可用能力
5
15
2
24
表1-2
1
5
1
12
其数学模型为：
max Z 2x1 x2
5x2 15
6xx11
2x2 x2
24 5
x1, x2 0
13
例3：捷运公司在下一年度的1～4月份的4个月内拟租用仓库
堆放物资。已知各月份所需仓库面积列于下表1-3。仓库租
借费用随合同期而定，期限越长，折扣越大，具体数字见表
1-4。租借仓库的合同每月初都可办理，每份合同具体规定
租用面积和期限。因此该厂可根据需要，在任何一个月初办
理租借合同。每次办理时可签一份合同，也可签若干份租用
面积和租用期限不同的合同。试确定该公司签订租借合同的
最优决策，目的是使所租借费用最少。
14
max Z 70 x1 120 x2
9x1 s.t. 43xx11
x1,
4x2 5x2 10x2 x2 0
360 200 300
资源约束
非负约束
其中 约束条件可记 s.t (subject to), 意思为“以… 为条件“、”假定“、”满足“之意。

运筹学第2章线性规划的对偶问题

运筹学第2章线性规划的对偶问题
第2章 线性规划的对偶理论 与灵敏度分析
§2.1 线性规划的对偶问题
随着线性规划应用的逐步加深，人们发现每一个线性规 划问题都存在一个与之对应的、具有密切关联的线性规 划问题，其中一个称为原问题，另一个称为对偶问题 （Dual linear programming，DLP）。对偶问题不仅具有 优良的数理性质，而且还有着重要的实际意义，尤其在 生产运营管理中有明显的经济含义。对偶理论充分显示 出线性规划理论逻辑上的严谨性和结构上的对称性，使 线性规划理论更加丰富，应用领域更为广泛。
yi 0 (i 1,2,3)
则得如下的线性规划模型：
min w 48 y1 20 y2 8 y3 8 y1 4 y2 2 y3 600 6 y 2 y2 1.5 y3 300 s.t. 1 y1 1.5 y2 0.5 y3 200 y , y , y 0 1 2 3
max z 2 y1 5 y2 9 y3 y1 3 y2 2 y3 3 2 y y 2 y 1 1 2 3 5 y1 y2 3 y3 1 y1无约束,y2 0, y3 0,
max z 600 x1 300 x2 200 x3 8 x1 6 x2 x3 48 4 x1 2 x2 1.5 x3 20 s.t 2 x1 1.5 x2 0.5 x3 8 x , x , x 0 1 2 3
x1 2, x2 0, x3 8
（2.1.6）
设 yi (i 1,2,, m) 表示第i种资源的定价，则其对偶问 题的形式为：
min w b1 y1 b2 y2 ... bm ym a11 y1 a21 y2 ... am1 ym c1 a y a y ... a y c 12 1 22 2 m2 m 2 s.t. a y a y ... a y c mn m n 1n 1 2 n 2 y1 , y2 , , ym 0
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
讨论一：模型求解时，可得到如下几种解的状况： （1）唯一最优解：只有一点为最优解点，简称唯一解； （2）无穷多最优解：有许多点为最优解点，简称无穷多解； （3）无界最优解：最优解取值无界，简称无界解； （4）无可行解：无可行域，模型约束条件矛盾。
讨论二：LP模型求解思路： （1）若LP模型可行域存在，则为一凸形集合； （2）若LP模型最优解存在，则其应在其可行域顶点上找到； （3）顶点与基本解、基本可行解的关系：
如 x1+x23 x1+x2+ x3=3
zmin
当 “”时，引进剩余（surplus）
z
变量 - xs； 如 x1+2x2 4 x1+2x2－x4=4
x
z = -
（4）约束右端项：当 bi < 0，则不等式 两端同乘（- 1）
z max z
例2-2 将以下线性规划问
题转化为标准形式
min z 2x1 3x2 x3
LP的标准化：
（1）变量：若 xj0，令 xj=-xj，xj0 若 xj无约束，则令 xj= xj－xj，xj0，xj0
（2）目标函数：若求 min z，则 即有 min z= - max （- z）
（3）约束方程：当 “”时，引进松 弛（slack）变量+xs； z
am1x1 am2x2 amjx j anmxn ()bm 称为约束条件，
x1，x2，…，xj，…，xn³0
称为变量的非负约束。
线性规划问题矩阵和向量的表达式
， ，
或 写 成
二 图解法
图解法的优点是直观性强，计算方便，但缺点是只适 用于问题中有两个变量的情况。
图解法的步骤是：建立坐标系，将约束条件在图上表 示；确立满足约束条件的解的范围；绘制出目标函数的图 形；确定最优解。
c2x2 a12x2 a22x2
cjx j a1jx j a2jx j
cn x n a1nxn a2nxn
(,)b1 (,)b2
am1x1 am2x2 amj x j amn xn (, )bm
x1
x2
xj
xn
0
线性规划模型的三要素：
（1）决策变量：指模型中要求解的未知量，简称变量。 （2）目标函数：指模型中要达到的目标的数学表达式。
目标函数 max z 2x1 3x2
2x1 2x2 12
约束条件
:
x1 2x2 8 4x1 16
4x2 12
x1 , x2 0
-4-
例2-1 美佳公司下设两个分工厂，两个仓库及一个配送中心。其中F1和 F2是两个工厂，W1和W2是两个仓库。DC是一个分销中心。由工 厂生产的产品经由图2-1所示的运输网络运往仓库。每一条路线 运输的单位成本在线段上给出，其中，F1→F2与DC→W2路线由
以如下线性规划问题为例说明如下：
max z 2x1 3x2
2 x1 2 x2 12
s.t.
x1 2 x2 8
4 x1
16
4 x2 12
x1, x2 0
a
b c d e f
图1-2
x2 2x1+2x2=12
Q4
Q3
Q2 (4,2)
max z 2x1 3x2
2x1 2x2 12
300元/单位 X7
X6
需求60 W2 单位
图2-1 美佳公司的配送网络
第二节 线性规划模型与图解法
一 线性规划问题的数学模型
数学模型就是用数学表达式和符号对研究对象数量关系所进 行的定量描述。
线性规划问题的一般形式通常表现为以下几种形式
max(min) z c1x1
s.t.
a11x1
a 21x1
---第 1 章 线性规划---
第三节 单纯形法
一、线性规划模型的标准形式
（1）变量：所有变量均xj 0 （2）目标函数：为取“max”形式 （3）约束条件：全部约束方程均为“=”连接 （4）约束右端项：bi 0
非标准形式情况有
变量： xj 0 ,或xj无约束 目标函数：min 约束条件：“”或“” 约束右端项： bi<0
第 二 章 线性规划
Linear Programming
-1-
第二章 线性规划
第一节：线性规划问题及其建模 第二节：线性规划模型与图解法 第三节：单纯形法 第四节：对偶问题 第五节：灵敏度分析 第六节：运输问题 第七节：数据包络分析 第八节：线性规划的应用
第一节 线性规划问题及其建模
某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位
产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。 每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问 应如何安排计划使该工厂获利最多?
资源 产品
Ⅰ
Ⅱ
拥有量
设备 A
2
2
12
设备 B
1
2
8
原材料 A
4
/
16
原材料 B
/
4
12
-3-
建立模型：
设 产品的产量 甲x1件 ，乙 x2件，则
x1 x2 2x3 3
s.t .
2x1 3x2 x1 x2
x3 5 x3 4
x1,
x3 0
解：设 z= - z, x2= x2 - x2 , x2 0 , x2 0, x40, x50, 则有
（3）约束条件：指模型中的变量取值所需要满足的一 切限制条件。
其中 max(min) z c1x1 c2x2 c jx j cn xn 称为目标函数
a11x1 a 21x1
a12x2 a22x2
a1jx j a2jx j
a1n x n a2nxn
()b1 ()b2
x1 2x2 8
4 x1
16
4x1=16
4x2 12
4x2 =12 x1, x2 0
x1+2x2=8
O
Q1
x1
唯一解 A
无界解
无穷多解 A
B
无可行解
步骤：（1）作平面直角坐标系，标上刻度； （2）做出约束方程所在直线，确定可行域； （3）做出一条目标函数等值线，判定优化方向； （4）沿优化方向移动，确定与可行域相切的点，确定最优 解，并计算最优值。
于受到路线中的桥梁承重上限的要求，因此有最大运输量限制。 其他路线有足够的运输能力来运输两个工厂生产的货物。
生产50 单位 F1
900元/单位 400元/单位
x3
W1 需求30
单位
200 x1
x2
元/
DC
单位 最多10单位
生产40 单位 F2
300元/单位 x4
200元/单位
100元/单位 最多80单位 x5