运筹学-2线性规划

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

128499-管理运筹学-第⼆章线性规划-习题11（2），12,14,18 习题2-1 判断下列说法是否正确：（1）任何线性规划问题存在并具有惟⼀的对偶问题； T （2）对偶问题的对偶问题⼀定是原问题；T（3）根据对偶问题的性质，当原问题为⽆界解时，其对偶问题⽆可⾏解，反之，当对偶问题⽆可⾏解时，其原问题具有⽆界解；F（4）若线性规划的原问题有⽆穷多最优解，则其对偶问题也⼀定具有⽆穷多最优解；（5）若线性规划问题中的b i ，c j 值同时发⽣变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为⾮可⾏解的情况；（6）应⽤对偶单纯形法计算时，若单纯形表中某⼀基变量x i <0，⼜x i 所在⾏的元素全部⼤于或等于零，则可以判断其对偶问题具有⽆界解。

（7）若某种资源的影⼦价格等于k ，在其他条件不变的情况下，当该种资源增加5个单位时，相应的⽬标函数值将增⼤5k ；（8）已知y i 为线性规划的对偶问题的最优解，若y i >0，说明在最优⽣产计划中第i 种资源已经完全耗尽；若y i =0，说明在最优⽣产计划中的第i 种资源⼀定有剩余。

2-2将下述线性规划问题化成标准形式。

≥≥-++-≤+-+-=-+-+-+-=⽆约束43214321432143214321,0,,232142224.5243max )1(x x x x x x x x x x x x x x x x st x x x x z2-3分别⽤图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基可⾏解对应图解法中可⾏()≥≤≤-+-=++-+-=⽆约束321321321321,0,0624.322min 2x x x x x x x x x st x x x z 域的哪⼀顶点。

()≥≤+≤++=0,825943.510max 121212121x x x x x x st x x z ()≥≤+≤++=0,24261553.2max 221212121x x x x x x st x x z 2-4已知线性规划问题，写出其对偶问题：543212520202410max x x x x x z ++++=≥≤++++≤++++057234219532..5432154321j x x x x x x x x x x x t s≥≥+≥+≥+++≥++0226332..31434321421j x x x x x x x x x x x x t s≥≤≤-+-=++-⽆约束321321321,0,064..x x x kx x x x x x t s （1）(2)2-5运⽤对偶理论求解以下各问题：（1）已知线性规划问题：其最优解为（a ）求k 的值；（b ）写出并求出其对偶问题的最优解。

用单纯形法同时求解原问题和对偶问题
原问题是：
maxZ=2x1 +x2 5x2 ≤15 6x1 + 2x2 ≤ 24 x1 + x2 ≤ 5 x1 , x2 ≥0
5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi ≥0
原问题的标准型是：maxZ=2x1 +x2+0x3+0x4 +0x5
b
15 24 5 0
x1 0 6 1 2
比 值
-
24/6=4
5/1=5
检验数j
对偶问题剩余变量 y4、y5
对偶问题变量 y1、y2 、y3
检验数行的－ (cj-zj)值是其对偶问题的一个基本解yi ；
原问题变量
0 2
原问题松驰变量
1 0 0 0 0 1/6 -1/6 -1/3 0 0 1 0
3
x3 x1
x2 1 检验数j= cj-zj
-1/4 -1/2
对偶问题剩余变量 y4、y5
对偶问题变量 y1、y2 、y3
此时得原问题最优解:X*=(7/2,3/2,15/2,0,0)T，Z*=17/2 则对偶问题最优解:Y*=(0,1/4,1/2,0,0)T，S*=17/2
又例：用单纯形法同时求解原问题和对偶问题
定理6（互补松弛定理）
在线性规划问题的最优解中，如果对应某一约束条件的 对偶变量值为非零，则该约束条件取严格等式；反之如果约 束条件取严格不等式，则其对应的对偶变量一定为零。
注：证明过程参见教材59页性质5证明
讨论:
互补松弛定理也称松紧定理，它描述了线性规划达到最

第二章线性规划教学目的和要求：目的：使学生具备线性规划的基本知识以及应用线性规划的基本能力。

要求：理解线性规划概念，标准型，解的概念，基本定理；掌握单纯形法，人工变量法，了解图解法。

重点：线性规划标准型，解的概念，单纯形法，人工变量法。

难点：线性规划基本定理，单纯形法。

教学方法：讲授法，习题法。

学时分配：12学时 作业安排：见教材P 38.线性规划是运筹学的一个重要分支。

1939年苏联科学家康托罗维奇提出了生产组织和计划中的线性规划模型。

1947年美国学者丹捷格(George B.Dantzig)提出了求解一般线性规划问题的方法。

此后，线性规划理论日趋成熟，应用也日益广泛和深入。

第一节线性规划问题一、问题的提出在企业的生产经营活动中经常会面临这样两类问题：一是如何合理地利用有限的人力、物力、财力等资源，取得最佳的经济效果；二是在取得一定的经济效果的前提下，如何合理安排使用人力、物力、财力等资源，使花费的成本最低。

例1.生产计划问题 某工厂利用甲、乙、丙、丁四种设备生产A 、B 、C 三种产品，具体数据如下表所示。

A 、B 、C 单位产品的利润分别是4.5、5、7(百元)。

问如何安排生产计划，才能使所获总利润最大？解：设产品A 、B 、C 产量分别为X 1,X 2,X 3件,Z 表示利润，要求总利润最大，即求Z=4.5X 1+5X 2+7X 3的最大值，故记作极大化Z=4.5X 1+5X 2+7X 3，另外对甲、乙、丙、丁设备需满足2X 1+2X 2+4X 3≦800，X 1+2X 2+3X 3≦650，4X 1+2X 2+3X 3≦850，2X 1+4X 2+2X 3≦700；同时产量应非负，故X j ≧0 (j=1,2,3)；以上问题可用数学模型表示为： 极大化Z=4.5X 1+5X 2+7X 3 满足 2X 1+2X 2+4X 3≦800 X 1+2X 2+3X 3≦6504X 1+2X 2+3X 3≦850 2X 1+4X 2+2X 3≦700X j ≧0 (j=1,2,3)例2.运输问题 设某种物资有m 个产地；A 1,A 2, …,A m ,它们的产量分别为a 1,a 2, …,a m ,有n 个销地B 1,B 2, …,B n 需要这种物资，它们的销量分别为b 1,b 2, …,b n 。