线性规划的**单纯形法。
一工厂生产a、b、c三种产品所需的劳力分别为和5个工作日单位，所消耗的原材料分别为和5kg，各单位产品的收益分别为和5元，工厂每日能提供的劳力数为100人，材料量为80kg。问该工厂应如何安排生产才能使总的收益达到最大。
1） 建立线性规划的数学模型；
2） 用**单纯形法求解；
3） 当劳力数增加10人，材料量增加20kg时新的最优方案；
4） 写出对偶问题和对偶问题的最优解。
5） 求x1的价值系数在什么范围变化最优解不变。
解：(1)设a、b、c三种产品的产量分别为，则数学模型为。
2)化为标准型。
最优解为x1= x2=0，x3=16，最大的利润z=80元。
3)由上表知最优基矩阵的逆。
所以新的最优解为x1= x2=0，x3=20，最大的利润z=100元。
4)对偶问题为。
对偶问题的最优解y1=0,y2=1.
互补松弛性的应用。
该问题的对偶问题为。
由互补松弛性：若分别是原问题和对偶问题的可行解，那么，当且仅当为最优解。
设为原问题的最优解。
其中为原问题约束条件的松弛变量。而。
为对偶问题的最优解。
其中为与(1)(2)(3)(4)相对应的松弛变量。
∴ 且 (3)(4)为等式，故。
1)(2)为不等式，故。由即。得。
由。即。
得。即原问题的约束条件应取等号。
解得。所以，原问题的最优解为。
目标函数最优值。
运输问题例题。
设有产量分别是8，9的两个原料产地a1, a2, 欲将原料运往需求量分别为6，5，8的三个销地，单位运价表如下，试写出该问题的数学模型并求运费最省的调运方案。(20分)
解：因总产量为17，总销量为19，所以是产小于销的运输问题，增加一个产地转化为产销平衡的运输问题为：
按表上作业法，首先用伏格尔法求得初始基可行解如下表：
用位势法求得检验数为：
由于检验数全部非负，则该初始基可行解即为最优解，最优值为53.
数学模型为。
用分枝定界法求解下面的整数规划：
已知其放松的线性规划的最优单纯形表：
解：由线性规划的最优单纯形表知其最优解为x1=5，x2=11/3，x3=4/3非整数解，最优值z0=71/3, x1=0，x2=0，x3=0为一整数可行解，目标函数值为z=0,定界。分枝，相应的问题设为，解如下表：
得到一个整数最优解x1=5，x2=3，x3=1，最优值为22，因该最优解是满足整数条件，所以该整数规划的下界z=22。
同理求解另一个线性规划问题(要写出求解的单纯形表)，因无可行解，因此该整数规划的上界也为22，所以整数规划的最优值为22，上面的这个解即为最优解。
指派问题题解。
某公司有五个经理分别派往五项五个地区负责市场开拓，预计相应的净收益如下表(单位：百万元)，试求使总收益最大的分派方案并写出该问题的数学模型（每人只负责一个地区）。
解：数学模型为。
min=1,则最优解为，最优值为48。
线性规划与灵敏度分析题解。
一工厂生产a、b、c三种产品所需的劳力分别为和5个工作日单位，所消耗的原材料分别为和5kg，各单位产品的收益分别为和5元，工厂每日能提供的劳力数为100人，材料量为80kg。问该工厂应如何安排生产才能使总的收益达到最大。
6） 建立线性规划的数学模型；
7） 用**单纯形法求解；
8） 当劳力数增加10人，材料量增加20kg时新的最优方案；
9） 写出对偶问题和对偶问题的最优解。
解：(1)设a、b、c三种产品的产量分别为，则数学模型为。
2)化为标准型。
最优解为x1= x2=0，x3=16，最大的利润z=80元。
3)由上表知最优基矩阵的逆。
所以新的最优解为x1= x2=0，x3=20，最大的利润z=100元。
4)对偶问题为。
对偶问题的最优解y1=0,y2=1.
最大流的标号法。
用标号法求下图所示的公路交通网络的最大流量（要求写出标号过程并说明得到的的确是最大流），其中，弧旁的数字是（cij,fij
解：1) 首先，给vs标上(0,)
2) 检查vs，给vs为起点的未饱和弧的未标号的终点v2标号(vs,),其中。
其它点不符合标号条件。
3) 检查，给为终点的非零流弧的未标号的起点标号(,)其中。
其它点不符合标号条件。
4) 检查，给为起点的未饱和弧的未标号的终点标号(,)其中，其它点不符合标号条件。
5) 检查，给为起点的未饱和弧的未标号的终点标号(,)其中，其它点不符合标号条件。
由于已标号，反向搜索可得增广链，在该增广链的前相弧上增加，在后向弧上减去，其它弧上的流量不变，则可得一流量的新的可行流如下图。
v25,5v5
vs （4,04,4vt
5,4v4 (4,4
v35,5v6
重新开始标号：
6) 首先，给vs标上(0,)
7) 检查vs，给vs为起点的未饱和弧的未标号的终点v2标号(vs,),其中。
其它点不符合标号条件。
8) 检查，没有以为起点的未饱和弧的未标号终点和以为终点的非零流弧的未标号起点，因此不能增加标号点，标号进行不下去了，所以该可行流必为最大流，最大流的流量为v(f)=20。
事实上，可令，则最小截集的截量。
最短路的标号法。
用dijkstra标号法求vs到vt的最短路及最短路线。
v2 6vt
vs512 v4
3 v3 解：i=0,给vs标上(,)其余各点均为t标号点，,t，记。
i=1,考察以vs为起点的弧的终点v2、v3，由于、，修改v2、v3的t标号分别为。计算，将v3的t标号改为p标号，即记。
i=2,考察以v3为起点的弧的终点v2、v4，由于，，修改v2、v4的t标号分别为。计算，将v2的t标号改为p标号，即，记。
i=3,考察以v2为起点的弧的终点v4、vt，由于，，修改、v4的t标号为，。计算，将的t标号改为p标号，即，记。
i=4,考察以v4为起点的弧的终点vt，由于，修改的t标号为，计算，将的t标号改为p标号，即，记。
由于vt得到了标号，所以得到了vs到vt的最短路，最短路的权为。
运筹学复习例题
1.某制药厂在计划期内要安排生产 两种药品，这些药品分别需要在四种不同的设备上加工 按工艺规定，每千克药品 和 在各台设备上所需要的加工台时数如表1 已知各设备在计划期内有效台时数 1台设备工作1小时称为1台时 分别是 和12 该制药厂每生产1千克药品 可得利润200元，每生产1千克药品 可得利润3...
运筹学例题
例 1 20 生产计划问题 某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表1 45所示，若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存储费0.2万元，现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低。试建立线性规划模型。表1 45例 1 ...
运筹学例题
一 绪论 例。一个班级的学生共计选修a b c d e f六门课程，其中一部分人同时选修d c a，一部分人同时选修b c f，一部分人同时选修b e，还有一部分人同时选修a b，期终考试要求每天考一门课，六天内考完，为了减轻学生负担，要求每人都不连续参加考试，试设计一个考试日程表。二 法。例1.某...