管理运筹学02线性规划

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

x1 x2 ≤ 8
产量非负 x 1 , x 2 ≥ 0
决策变量
（decision variable）
总利润表三达要式素
目标函数 （objective function）
约束条件 生产能力,不 （subject to） 允许超过 当目标函数与约束条件均为决策变
量的线性函数，且变量取连续值时，
当xk的值由0增加到θ时，原来的基变 量xl取值首先变成零，选择其为出基变 量。称θ的表达式为最小比值原则。
如果所有aik ≤0, xk的值可以由0增加到 无穷，表示可行域是不封闭的，且目 标函数值随进基变量的增加可以无限 增加，此时不存在有限最优解。
下面对以上讨论进行总结.
2019/8/31
课件
15
称为线性规划LP；变量取整称为整
数线性规划ILP；变量取二进制为
0-1规划BLP。
2019/8/31
课件
5
2.1.2 线性规划的数学模型
【例2.1】（合理配料问题）由下表建立一个LP模型求解满足动物成长 需要又使成本最低的饲料配方。
饲料 营养甲(g/kg) 营养乙(g/kg) 营养丙(g/kg) 成本(g/kg)
x1+x2=8

x1
2019/8/31
课件
11
2.2.3 线性规划几何解的讨论
线性规划几何解存在四种情况：唯一最优解、无穷 多最优解、无界解、无可行解。 可行域为封闭有界区域时，可能存在唯一最优解， 无穷多最优解两种情况； 可行域为非封闭无界区域时，可能存在唯一最优解， 无穷多最优解，无界解三种情况； 可行域为空集时，没有可行解，原问题没有最优解。
1
0.5
0.1
0.08

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 ）写出并求出其对偶问题的最优解。

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
详细描述
分配问题在实际生活中广泛存在，如物资 分配、任务分配等。通过图解法，可以将 分配问题转化为线性规划模型，并利用图 形直观地展示最优解的资源分配方案。在 分配问题中，通常需要考虑不同需求方的 重要性和优先级，以及资源的有限性等因 素，以实现整体效益的最大化。