基本要求。
一、将线性规划化为标准型和写出相应的对偶规划；
二、用**法求解具有两个决策变量的线性规划问题；
三、用单纯形方法及人工变量法求解线性规划问题；
四、灵敏度分析；
五、整数规划与分枝定界法，0-1规划与隐枚举法，指派问题。
六、求解产销平衡的运输问题和产销不平衡的运输问题；
七、动态规划与求解；
八*、带**的资源利用问题及连续型的动态规划求解；
九*、存储问题求解（无限供货能力下不容许缺货及容许缺货模型）
例题选讲。例：某工厂在计划期内要安排生产ⅰ、ⅱ两种产品，这些产品分别需要在a、b、c、d四种不同的设备上加工。
按工艺规定：产品ⅰ和ⅱ在个设备上所需要的加工时数于下表中。已知各设备在计划期内的有效台时数分别是和12。
该工厂每生产一件产品ⅰ可得利润2圆，每生产一件产品ⅱ可得利润3圆，问：应如何安排生产，可获得最大利润。
解设生产产品ⅰ和ⅱ分别为和件，则由条件可得关系。
⑴标准型的概念：
①目标函数为极大化；
②资源常数；
③约束条件关系为等式；
④决策变量。
例： 将下面的线性规划化为标准型。
无非负限制。
解 二、**法。
例用**法求解线性规划问题。
极大化 解：最优解。
三、单纯形方法。
对于具有两个以上决策变量的线性规划问题，我们采用单纯形方法进行求解。具体过程是：
⑴建立单纯形表，在单纯形表中，务必使基变量的价值系数为零，则检验数行是价值系数行的相反数；
⑵若检验数则当前解为最优解（当前解是基变量取相应的资源常数，非基变量取为零）；若存在检验数，则要进行相应的换基，即：迭代；
⑶①进基：进基变量。
②出基：出基变量为第行所对应的基变量，由下面的关系确定。
③以主元进行迭代，目标：主元化为1，该列的其余元化为零。
⑷再一次判定当前解是否为最优解。
例用单纯形法求解线性规划。
极大化 解引入松弛变量，得到原规划的标准型。
极大化 单纯形表为。
所以，最优解为最优解值为21.
人工变量法。
对于约束条件中没有阶单位阵的线性规划，通过引入适当的人工变量，再加以求解。
1. **。
在**中，引入的人工变量的价值系数为，而相应的约束条件系数向量为单位向量。
2.二阶段法。
例用人工变量法求解线性规划。
符号不限。例求解规划。
建立对偶规划的要点。
⑴原规划是极大化，则对偶规划是极小化；
原规划的价值系数是对偶规划中的资源常数；
⑶原规划与对偶规划的约束条件系数矩阵为矩阵的转置关系；
⑷原规划中的第个决策变量无非负限制，则对偶规划中的第个约束条件为等式；
⑸原规划中的第个决策变量非正，则对偶规划中的第个约束条件取反向不等式；
例求下面问题的对偶规划。
极大化 无非负限制。
解极小化 对偶单纯形法。
基本要求：检验数；资源常数存在负值。
解法：1． 列出对偶单纯形表；
2． 将基变量在目标函数中系数化为零，检验数为新目标函数中系数的相反数；
3． 判断，若，则当前解为最优解；
若中存在负项，则进行迭代，确定出基和进基变量；
出基：记为第r行对应的变量；
进基：，为进基变量；
以为主元进行迭代。目标：将主元化为1，该列的其余元化为0。
灵敏度分析。
灵敏度分析的任务：确定各个变量使得最优解保持不变的变化范围；以及在最优解改变的时候求出相应的最优解。
⑴非基变量的价值系数的变化范围，使最优解保持不变。
⑵基变量的价值系数的变化范围，使最优解保持不变。
若最优解改变，则对两种情况有。
⑶资源常数变化范围使最优基不变：
⑷非基变量的系数向量的增量的变化范围使最优解不变：
⑸增加新的决策变量使最优解保持不变：
例：设线性规划。
求：1.最优解；
2.确定的范围，使最优解不变； 取，求最优解；
3.确定的范围，使最优基不变， 取求最优解；
4.引入求最优解；
解 1.由单纯形方法得。
即，原问题的最优解为。
2.因为非基变量，故当时，即时， 最优解不变；
为基变量，由公式，当最优解不变， 即。
时，最优解不变。
现对最优解改变，此时原最优表为。
即相应的最优解为。
3.此时。得最优基不变。即。
最优基不变。
当最优解改变，此时。
此时最优表为。
即最优解为。
4.此时。故最优解改变。
相应的最优表为。
例用分枝定界法求解整数规划。
用隐枚举法求解0-1规划。
运输问题（产销平衡）的求解方法：表上作业法。
1.用最小元素法求初始解；
2.用位势法求出当前解所对应的位势：若为基变量，则行位势和列位势满足关系。
3.用位势法计算非基变量的影响系数：若为非基变量，则影响系数与行位势和列位势满足关系。
4.最优解的判定：若影响系数则当前解为最优解；否则通过解的调整求出最优解；
5.解的调整：
记： 令为所对应的非基变量，以为当前变量，构造闭回路；
在闭回路上确定最大调整量；
求出新解。6.重新判定当前解是否为最优解。
产销不平衡的运输问题的求解方法：设置虚拟产地或销地以达到产销平衡。
指派问题的求解：
1.的指派问题的最小值解的求解方法：
用行缩减和列缩减在每行和每列至少产生一个零；
用划线法判定是否有个独立的零；
如果有个独立的零，则可以求出最小值解；
若没有个独立的零，重新进行调整，以求出个独立的零。
2.的指派问题的最小值解的求解方法：设置虚拟变量，其价值系数取为零。
3.指派问题中的最大值求解。
例求下面运输问题的最小值解：
解：由最小元素法得到初始解：
则：，最小值为-6，非基变量为，闭回路，最大调整量为1，得新解：
重新计算位势及影响系数，得下表：
最小值为-5，非基变量为，闭回路，最大调整为2，得新解：
重新计算位势及影响系数，得下表：
此时，，故当前解为最优解。最优解值为：
产销不平衡的运输问题：对产销不平衡的运输问题，求解的基本方法是设置虚拟变量，其单位运输成本为0，从中求出最优解。
例：求下面运输问题的最小运费解：
例： 求解运输问题。
例：求下面指派问题的最小值解：
解：故最优解为：，最优解值为。
例：求下面指派问题的最小值及最大值解：
例：求下面指派问题的最大值解：
例：最短路问题：求下面从到的最**路和最短距离：
解：所以：
所以：例：设有某种肥料共6个单位，准备给4块粮田用，其每块粮田施肥数量与增产粮食的关系如下表所示。试求对每块田施多少单位重量的肥料，才能使总的粮食增产最多。
解：表1，对两块田的施肥：
表2，对三块田的施肥：
表3，对四块田的施肥：
所以最优解为2，2，0，2，最大增产量为134。
例某工厂有100太机器，拟分四个周期使用，在每一周期中有两种生产任务，据经验，把台机器投入第一种生产任务，则在一个周期内有台机器作废；余下的机器全部投入第二种生产任务，且有机器作废。在第一种任务中，每台机器可收益10个单位，而第二种任务中每台机器可收益7个单位，问怎样分配机器，能使总收益为最大？
运筹学总复习
运筹学 总复习。第1章线性规划及其对偶问题。基本概念。基本要素 决策变量 目标函数 约束条件。线性规划定义 决策变量为可控的连续变量，目标函数和约束条件为决策变量的线性函数。标准形式 目标函数取 max 约束条件取 约束右端项非负 决策变量非负。解的概念 凡满足约束条件的决策变量的取值称为线性规划的...
运筹学总复习
0 绪论。1 什么是运筹学？2 运筹学起源？3 运筹学的分支？1 线性规划。1 什么是线性规划？2 线性规划数学模型三要素 矩阵形式？3 法的步骤 说明线性规划问题什么特点？4 线性规划解的四种形式？5 线性规划问题化标准形式 标准形式的特点 min型目标函数化为max形式。6 基本解 基本可行解。...
运筹学总复习
一 判断题。线性规划问题目标函数可以同时在两个顶点上达到最优解。二 选择题。存贮策略达到最优时，达到了什么目标 b a.平均订购费用最低b.平均的运营费用最低 c.订货周期最短d.订货量最小。三 填空题。如下图所示的网络图，弧上数为 为了使为可行流，则 2 1 3 3 找一条增广链 s 2 1 4 ...