运筹学秘籍 - 图文

运筹学秘籍 1 2 3 4 5 判断 选择 应用 证明 计算 5题 5题 4题 1题 5题 2分 2分 6分 8分 10分 10分 34分 6分 40分

将一般问题化为标准型 Max S = -x1+2x2-3x3 Min S = x1-2x2+3x3’-3x3” s.t. x1+x2+x3 <= 7 s.t. x1+x2+x3’-x3 ”+x4 =7 x1-x2+x3 >=2 x1-x2+ x3’-x3 ” -x5=2 -3x1+x2+2x3 = 5 -3x1+x2+2x3’-2x3” =5 x1,x2 >=0 x3 是自由变量 x1, x2,x3’,x3 ”, x4,x5>= 0

一、单纯形法

定义：如何从一个可行基找另一个可行基？称基变换。两个基本可行解称为相邻的，如果它们之间仅变换一个基变量。对应的基称为相邻可行基。

从数学角度看，若让非基变量 x1,x 2取值从零增加，相应的目标函数值Z也将随之减少。因此有可能找到一个新的基本可行解，使其目标函数值有所改善。即进行基变换，换一个与它相邻的基。再注意到x1前的系数－2比前的系数－1小，即x1每增加一个单位对Z的贡献比x2大。故应让x1从非基变量转为基变量，称为进基。又因为基变量只能有三个，因此必须从原有的基变量x3,x4,x5中选一个离开基转为非基变量，称为出基。谁出基？又因为 x2仍留作非基变量，故仍有x2=0.

用增广矩阵的初等变换表示为：

①在迭代过程中要保持常数列向量非负，这能保证基可行解的非负性。最小比值能做到这一点。②主元素不能为0。因为行的初等变换不能把0变成1。③主元素不能为负数。因为用行的初等变换把负数变成1会把常数列中对应的常数变成负数。

LP当前解已是最优的四大特征：⑴存在一组(初始)可行基（其系数矩阵为单位阵）。⑵检验行的基变量系数=0。⑶ 检验行的非基变量系数≥0。（全部〉0?唯一解。存在=0?无穷多个解。）⑷ 常数列向量≥0。

1分别用图解法和单纯形法求线性规划问题 2 用单纯形法表格求解线性规划问题

maxz?2x1?x2x2?33x1?x2?12x1?x2?5x1?2?0

minz?3x1?2x2?x3x1?2x2?x3?82x1?x2?5x1?3?0

二、人工变量法（也称大M法）所给LP的标准型中约束矩阵中没有现成的可行基时用

M为任意大的实数，称为罚因子

x6,x7是强行引进，称为人工变量。它们与x4,x5不一样。x4,x5称为松弛变量和剩余变量,是为了将不等式改写为等式而引进的，而改写前后两个约束是等价的。人工变量的引入一般来说是前后不等价的。只有当最优解中，人工变量都取值零时（此时人工变量实质上就不存在了）才可认为它们是等价的。得到 minZ?3x1?0x2?x3?0x4?0x5?Mx6?Mx7

解的判别定理：⑴ 最优解判别定理：所有检验数≥0；人工变量为0⑵ 无穷多最优解判别定理：所有检验数≥ 0；人工变量为0；存在某个非基变量的检验数为0。⑶ 无可行解判别：所有检验数≥ 0；人工变量≠0 (4)无界解判别定理：有一个非基变量的检验数＜0,但该数对应的列中没有正元素；人工变量为0

两阶段法：

（1）两阶段法的第一阶段求解一个目标中只包含人工变量的LP问题，即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数（一般取1），在保持原问题约束不变的情况下求这个目标函数极小化的解。显然在第一阶段中，当人工变量取值为0时，目标函数值也为0。这时候的最优解就是原问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，表明原LP问题无可行解。 （2）第二阶段：求解原线性规划问题的最优解。以第一阶段的最终单纯形表为基础，去掉人工变量，目标函数换为原问题的目标函数，得到第二阶段的初始表，继续迭代求解。

⑴ 若求得的单纯形矩阵中，所有人工变量都处在非基变量 的位置。即 x n ? i ? 0( i ? 1, 2, ? m ) 及 * ? 0 。则从第1阶段去掉人工变量后，即为原问题?的初始单纯形矩阵。并进入第2阶段。⑵ 若第一阶段所求得的单纯形中仍含有（解）非零的人工变量，则说明原问题无可行解。不再进入第2阶段。因此两阶段法的第1阶段求解有两个目的：一为判断原问题有无可行解。二，若有，则得原问题的一个初始可行基，再对原问题进行第2阶段的计算。

3用大M法和两阶段法求解线性规划问题

minz?2x1?3x2?x3x1?4x2?2x3?83x1?2x2?6x1?3?0

二、对偶原理

Max z=c x a x<=b x>=0 max z 决策变量为n个; 约束条件为m个 “≤” Min w=y b y a>=b y>=0 min w 决策变量为m个; 约束条件为n个 “≥”

max问题第i个约束取“≥”，则min问题第i个变量 ≤ 0 ； min问题第i个约束取“≤”，则max问题第i个变量 ≤ 0 ； 原问题第i个约束取等式，对偶问题第i个变量 自由变量； max问题第j个变量 ≤ 0 ,则min问题第j个约束取“≤” min问题第j个变量 ≤ 0 ，则max问题第j个约束取“≥” 原问题第j个变量自由变量，对偶问题第j个约束取等式。 原问题第i个约束取等式，对偶问题第i个变量自由变量。

(1)max问题任一可行解的目标值为min问题目标值的一个下界； (2)min问题任一可行解的目标值为max问题目标值的一个上界。 若原问题(对偶问题)为无界解，则对偶问题(原问题)为无可行解。若原(对偶)问题为无可行解，对偶(原问题)问题或为无界解，或为无可行解。若原问题有最优解，那么对偶问题也有最优解，且目标值相等。所以对偶问题中，解的情况有：1.都有有限最优解2.都无可行解3.一个有无界解，另一个无可行解。

对偶单纯形法

单纯形法：由 XB = B-1b ≥ 0，使σj ≥ 0，j = 1,···,m 对偶单纯形法：由σj ≥ 0(j= 1,···,n)，使XB = B-1b ≥ 0 相同点：都用于求解原问题

对偶单纯形法：从一个原始不可行而对偶可行的基出发，进行基变换，每次基变换时都保持基的对偶可行性，一旦获得一个原始可行基，则该基必定是最优基。 步骤：(1)保持σj ≥ 0，j= 1,···,n，确定XB，建立计算表格

(2)判别XB = B-1b ≥ 0是否成立？①若成立，XB为最优基变量；②若不成立，转(3)；

(4)取主变换，得到新的XB。重复（2）-（4）步，求出结果。

用对偶单纯形法求解线性规划问题

minz?x1?x22x1?x2?4x1?7x2?7x1?2?0

三、整数规划（整数规划是一类要求变量取整数值的数学规划）

原问题的松驰问题：任何整数规划（IP），凡放弃某些约束条件（如整数要求）后，所得到的问题（P）都称为（IP）的松驰问题

分支定界法：1.原问题的松驰问题。2.求解对应的松驰问题：若所得的最优解的各分量恰好是整数，则这个解也是原整数规划的最优解，计算结束。若松驰问题无可行解，则原整数规划问题也无可行解，计算结束。若松驰问题有最优解，但其各分量不全是整数，则这个解不是原整数规划的最优解，转下一步。

分别用穷举法和分枝定界法求整数规划

maxz?x1?x2951x2?1414 1?2x1?x2?3x1?2?0均为整数x1?

割平面法：先不考虑整数约束，按一般线性规划问题求其最优解，线性规划问题的最优基本可行解是解集的一个顶点，这个顶点的坐标未必都是整数，若不是整数解，可增加一条约束，相当于增加一个平面将这个顶点割掉，称这种方法为割平面法。 重点：新约束的求法

2.分别用穷举法和割平面法求解整数规划问题

maxz?x1?x22x1?x2?65x1?9x2?45x1?2?0均为整数

匈牙利法：

某商业公司设计开办五家新闻商店B1，B2，B3，B4，B5。为了尽早建成营业，商业公司通知了A1,A2，A3，A4，A5五个建筑公司，以便让每家新商店由一个建筑公司承建。建筑公司A对新商店B的建造费用的投标为C均见下表。商业公司应当对五家建筑公司怎样分配建造任务，才能使总建造费用最少？

步骤一：变换系数矩阵，使各行和各列皆出现零元素。如各行及各列分别减去本行及本列最小元素，这样可保证每行及每列中都有零元素，同时，也避免了出现负元素。

步骤二：试指派，以寻求最优解。此时，若独立零元素等于，则已可得出最优解。否则2种情况：①存在未标记0，且其所在行和列中至少有2个未标记0。将任一0记△ ，其余同行同列的未标记0记×。②独立零元素小于n。转步骤三。 步骤三：做能覆盖所有零元素的最少数目的直线集合。

步骤四：变换系数矩阵，使未被直线覆盖的元素中出现零元素。回到步骤二。

在未被直线覆盖的元素中总有一个最小元素。对未被直线覆盖的元素所在的行（或列）中各元素都减去这一最小元素，

为了消除负元素，只要对它们所在的列（或行）中各元素都加上这一最小元素（可以看作减

去这一最小元素的相反数）即可。

为了使未被直线覆盖的元素中出现零元素，将第二行和第三行中各元素减去未被直线覆盖元素中的最小元素1。但这样一来，第一列中出现了负元素，因而再对第一列各元素分别加上1，即

此时，试指派后，可得独立零元素5个，故已可得最优指派方案。所以，本题最优解为！ 也就是说，最优指派方案为：让A1承建B3，A2承建B2，A3承建B1，A4承建B4，A5承建B5。这样，总的建设费用最少，为34万元。

则以C为系数矩阵的最大化指派问题和以B为系数矩阵的最小化指派问题有相同最优解。

当系数矩阵为利润矩阵、产量矩阵等时，就产生最大化指派问题。

例：张、王、李、赵4位老师被分配教语文，数学，物理，化学4门课程，每位老师教一门，每门课程由一位老师教。根据以往情况分别教这四门课程的平均成绩：

问：确定哪一位老师上哪门课，使四门课平均成绩之和

最高。

2、人数和事数不等的指派问题

若人少事多，则添上一些虚拟的“人”。这些虚拟的“人”做各事的费用系数可取0（理解为这些费用实际上不会发生），也可取足够大的数M（理解为若指派这些虚拟的“人”去做那些事，则那些事实际上没人去做）。 若人多事少，则添上一些虚拟的“事”，这些“事”被各人做的费用系数同样可取0，也可取足够大的数M。

3、一个人可做几件事的指派问题:若某人可做几件事，则可将该人化作相同的几个“人”来接受指派，这几个“人”做同一件事的费用系数当然都一样。

4、某事一定不能由某人做的指派问题:若某事一定不能由某人做，则可将相应的费用系数取作足够大的数M。

3.有四个工人，分别指派四项工作，问如何指派可是时间最少？ 甲 乙 丙 丁 A 15 19 26 19 B 18 23 17 21 C 21 22 16 23 D 24 18 19 17

四、目标规划(同时考虑多个决策目标的问题) 目标优先级：先将目标等级化。

若多目标规划问题的解能使所有的目标都达到，就称该解为多目标规划的最优解；若解只能满足部分目标，就称该解为多目标规划的次优解；若找不到满足任何一个目标的解，就称该问题为无解。

1、多目标的处理：优先因子和权系数

优先因子Pk ：为了将不同级别的目标的重要性用数量表示，引进P1，P2，?,用它表示一级目标，二级目标，?，的重要程度。规定Pk 》Pk+1 ：表示Pk比Pk+1 有绝对的优先权。即：首先保证P1级目标实现，不考虑其他级, P2级目标是在保证P1级目标值不变前提下考虑的。

权系数wj:具有相同优先因子的多个目标用wj来区别（越重要，w值越大）。 2、约束方程的处理：偏差变量 决策变量：x1 ，x2 ，x3??

偏差变量：正偏差量：实际决策值超过目标值bi的部分记di+ 负偏差量：实际决策值不足目标值bi的部分记di -。 di+ >=0, di- >=0 且 fi (x)- di+ + di-= bi 恒有： di+ . di-＝0（不可能既超过目标值又低于目标值）

目标约束：由决策变量x，正、负偏差变量和要追求的目标值组成的软约束，具有一定的弹性。（目标约束不会不满足，但可能偏差过大）

3、目标函数：

1）不含决策变量：由各目标约束的偏差变量及相应的优先因子和权系数构成。 2）总是极小化（总是希望尽可能缩小偏差） 3）应用时，有三种基本表达式：（1）要求恰好达到目标值。这时决策值超过或不足目标值

都是不希望的，故有min(di+ + di-)（2）要求不超过目标值。这时不希望决策值超过目标值，允许不足目标值。故有min(di+)（3）要求不低于目标值。这时不希望决策值低于目标值，允许超过目标值。故有min(di-)

某电器公司经营的唱机和录音机均有车间A、B流水作业组装。要求按以下目标制订月生产计划： (1)库存费用不超过4600元；(2)每月销售唱机不少于80台；(3)不使A、B车间停工（权数由生产费用确定）；(4)A车间加班时间限制在20小时内； (5)每月销售录音机为100台；(6)两车间加班时数总和要尽可能小（权数由生产费用确定）

设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1

线性目标规划的单纯形法：

目标规划的数学模型实际上是最小化形式的线性规划问题，可以用单纯形法求解。

在用单纯形法解目标规划时，检验数是各优先因子的线性组合。因此，在判别各检验数的正负及大小时，必须注意

P1》P2》P3》?。当所有检验数都已满足最优性条件(西格玛>=0) 时，从最终单纯形表上就可以得到目标规划的解。

解： (1) 引入松驰变量，将目标规划模型化为线性规划标准形式(2)用单纯形法解上面的标准形式，解题过程的单纯形表见下表 。

该表中，单纯形表Ⅰ为初始单纯形表。其中，非基变量x1的检验数-p1-6p3<0,其它非基变量检验数均非负，故确定x1为换入变量。按最小比值规则，确定基变量d1-为换出变量。经迭代变换得单纯形表Ⅱ。

在单纯形表Ⅱ中，非基变量x2和d1+的检验数皆负，但x2的检验数更小些，故确定x2为换入变量。按最小比值规则,d3-为换出变量。经迭代变量得单纯形表Ⅲ。

在单纯形表Ⅲ中，由于非基变量d1+和d3+的检验数都是零，故知例题有多重最优解（满意解）。如以d1+为换入变量继续进行迭代，可得单纯形表Ⅳ；

如以d3+为换入变量继续进行迭代，可单纯形表Ⅴ从单纯形表Ⅳ和Ⅴ中，分别可得到例题的另两个满意解，即x1=6,x2=3和x1=8,x2=0。

与单目标方法不同处：1、检验数：按k级优先因子分解为k项，写成k行；2、最优性检验：首先判别Pk行检验数是否已达最优。若是；再考虑Pk+1级，且同时保证Pk级最优值不被劣化。

某工厂生产甲乙两种产品，单位甲产可获利6元，单位乙产可获利4元.甲乙产品所需机器台时数分别为2和3个单位，劳工时数分别为4和2个单位。可提供100个机器台时和120个劳工工时数。劳动力不足可组织加班。 第一目标：利润达到或超过180元 第二目标：机器台时数充分利用 第一目标：尽量减少加班

第一目标：甲不少于22件，乙不大于18件。

写出该目标规划的数学模型。并用图解法，单纯形法（表格形式）分别求解。

2.某工厂生产唱机和录音机两种产品，每种产品均需经过A，B两个车间加工才能完成。 车间A 唱机 2小时/台 录音机 1小时/台 所能提供的工时 生产费用 120小时/台 80元/小时 车间B 仓库费用 1小时/台 50元/月·台 3小时/台 30元/月·台 150小时/台 40元/小时 第一目标：仓库费用每月不超过4600元 第一目标：唱机每月至少售出50台 第一目标：A加班不超过20小时 第一目标：录音机至少售出50台

第一目标：A,B加班时数总和要限制（权系数有两车间生产费用决定） 列出目标规划数学模型

五、非线性规划

正定：特征值>0；各阶主子式>0(Ai>0) 半正定：特征值≥0；detA=0, Ai ≥ 0 负定：特征值<0； Ai <0(i为奇）, Ai >0(i为偶）

半负定：特征值≤0； detA=0，Ai ≤0(i为奇）, Ai ≥0(i为偶） 不定：特征值有> 0及< 0；除了上述情况外即为不定。

黄金分割法：通过取试探点使包含极小点的区间（不确定区间）不断缩短，当区间长度小到一定程度时，区间上各点的函数值均接近极小值，因此任意一点都可作为极小值点的近似。

牛顿法：在估计点x(k)附近用二阶泰勒多项式近似目标函数f(x)，进而求得极小点的估计值。

1.求f(x)?x?6x?2得极小点。

（1）用黄金分割法求解，迭代三次，并求出所达的精度。 （2）用牛顿法求解，给定初始点x1?1

2

抛物线逼近法：

2.用抛物线逼近法求f(x)?e?5x在区间[1，2]上的极小点。初始点x1?1，初始步长

xh1?0.1，只迭代两次。

求f(x)?x1?2x2?4x1?2x1x2得极小点，初始点x22(1)?(1,1)T

试用变量轮换法，单纯形搜索法（初始长度h1?2），最速下降法，阻尼牛顿法，共轭梯度法，变尺度法分别求解，只迭代两次。并求所达精度。

五、动态规划

分别采用逆序递推，顺序递推方法计算A到E得最短路径。

2.用动态规划求解下列整数非线性规划问题

22minf(x)?x12?2x2?x3?2x1?4x2?2x3x1?x2?x3?3x1,x2,x3是非负整数

六、图与网络分析

有九个城镇，v1······v9。弧旁数字表示公路长度，从v1到v9哪条路最短

七、决策论

某商店从外地运来一批西瓜，当地需求量可能为10000,15000,20000,25000千克。商店支出为0.25元/千克，售价为0.35元/千克。 （1）写出损益值表

（2）分别用等可能性准则，乐观准则，悲观准则，折中准则，后悔值准则确定商店应进货的数量。

本文来源：https://www.bwwdw.com/article/ls47.html