7.29某运输问题的产销平衡表与单位运价

下表给出某运输问题的产销平衡表与单位运价表。

将此问题转化为最小费用最大流问题，画出网络图并求数值解。

产量销地123产量AB2030242252087销量456网络图如下，弧旁数字为(,)ij ijb c. 设ijf为边(i, j ) 上的数量，ij c为边(i, j ) 上的单位运费，则最小费用最大流的数学iju为边(i, j ) 上的额定容量，规划表达(,)min;ij iji j Ec f∈∑(,)(,),,0,,f ij ij f j V j V i j Ej i Ev i s f f v i ti s t ∈∈∈∈=⎧⎪-=-=⎨⎪≠⎩∑∑0,(,)ij ij f u i j E ≤≤∈sets :points/s,v1,v2,v3,v4,v5,t/; edge(points,points)/s,v1 s,v2 v1,v3 v1,v4 v1,v5 V2,v3 v2,v4 v2,v5 v3,t v4,t V5,t/:c,u,f; endsets data :c=0 0 20 24 5 30 22 20 0 0 0; u=8 7 8 8 8 7 7 7 4 5 6; vf=15; enddatamin =@sum (edge(i,j):c(i,j)*f(i,j));@for (points(i)|i#ne#@index (s) #and# i#ne#@index (t): @sum (edge(i,j):f(i,j))-@sum (edge(j, i):f(j,i))=0; ); @sum (edge(i,j)|i#eq#@index (s):f(i,j)) =vf; @sum (edge(j,i)|i#eq#@index (t):f(j,i)) =vf; @for (edge(i,j):@bnd (0,f(i,j),u(i,j))) ; endGlobal optimal solution found.Objective value: 240.0000 Total solver iterations: 1Variable Value Reduced Cost VF 15.00000 0.000000 C( S, V1) 0.000000 0.000000 C( S, V2) 0.000000 0.000000 C( V1, V3) 20.00000 0.000000 C( V1, V4) 24.00000 0.000000 C( V1, V5) 5.000000 0.000000 C( V2, V3) 30.00000 0.000000C( V2, V4) 22.00000 0.000000 C( V2, V5) 20.00000 0.000000 C( V3, T) 0.000000 0.000000 C( V4, T) 0.000000 0.000000 C( V5, T) 0.000000 0.000000 U( S, V1) 8.000000 0.000000 U( S, V2) 7.000000 0.000000 U( V1, V3) 8.000000 0.000000 U( V1, V4) 8.000000 0.000000 U( V1, V5) 8.000000 0.000000 U( V2, V3) 7.000000 0.000000 U( V2, V4) 7.000000 0.000000 U( V2, V5) 7.000000 0.000000 U( V3, T) 4.000000 0.000000 U( V4, T) 5.000000 0.000000 U( V5, T) 6.000000 0.000000 F( S, V1) 8.000000 -10.00000 F( S, V2) 7.000000 0.000000 F( V1, V3) 2.000000 0.000000 F( V1, V4) 0.000000 12.00000 F( V1, V5) 6.000000 0.000000 F( V2, V3) 2.000000 0.000000 F( V2, V4) 5.000000 0.000000 F( V2, V5) 0.000000 5.000000 F( V3, T) 4.000000 0.000000 F( V4, T) 5.000000 -8.000000 F( V5, T) 6.000000 -15.00000Row Slack or Surplus Dual Price1 240.0000 -1.0000002 0.000000 0.0000003 0.000000 -10.000004 0.000000 20.000005 0.000000 12.000006 0.000000 5.0000007 0.000000 -10.000008 0.000000 -20.00000结果其最小总费用为240。

深圳大学考研运筹学2021深圳大学硕士研究生入学考试试题第1页（共3页）2021深圳大学攻读硕士学位研究生入学考试试题招生专业：管理科学与工程考试科目：运筹学一、（26分）某厂生产三种产品，设生产量分别为x1,x2,x3，已知收益最大化模型如下：maxZ?3x1?2x2?4x3s?t?2x1?x2?3x3?40（第一种资源）2x1?2x2?3x3?4（第二种资源） 8x?10 （产品1的生产能力限制）x1，x2，x3?0（1）以x4,x5,x6表示三个约束的不足变量，写出标准型。

（4分）（2）若用单纯形法计算到下面表格 xB x4 x2 x1 x1 0 0 1 0 x2 0 1 0 0 x3 3/2 3/2 0 1 x4 1 0 0 0 x5 -1/2 1/2 0 -1 x6 -1 -1 1 -1 b 6 14 10 -58 cj?zj 指出所表达的基本可行解，目标函数值。

（4分）（3）指出上面给出的解是否最优。

若不是，求出最优解和最优目标函数值。

（6分）（4）写出本规划的对偶规划，并求出它的最优解。

（4分）（5）若产品1的单位利润从3变为4，问最优方案是什么？此时的最大收益是多少？（4分）?40??46?????（6）若资源常数列向量b??48?变为b???60?，问原最优性是否改变？求出此时的最优?10??10?????方案和最大收益。

（4分）第2页（共3页）1 / 10深圳大学硕士研究生入学考试试题二、（24分）有A1,A2,A3三个工厂，要把生产的产品运往B1,B2,B3三个需求点。

若B1,B2,B3三个需求点需求量没有得到满足，则单位罚款费用为6，3，4。

各厂的供应量、各点的需求量以及单位运价如下表。

问应如何组织调运才能使总费用（运输费用和罚款费用之和）最小？单位运单需求点工厂 A1 A2 A3 需求量 B1 6 5 2 20 B2 4 7 5 40 B3 7 8 6 30 供应量 15 30 25 （1）请将此问题化为供需平衡的运输问题；（2）用最小元素法求（1）的一个初始调运方案；（3）判断（2）中的方案是否最优，并说明原因。

第1页（共3页）2014深圳大学攻读硕士学位研究生入学考试试题招生专业：管理科学与工程 考试科目：运筹学一、（26分）某厂生产三种产品，设生产量分别为123,,x x x ，已知收益最大化模型如下：123max 324Z x x x =++s t ⋅⋅1232340x x x ++≤（第一种资源）12322348x x x ++≤（第二种资源）10x ≤ （产品1的生产能力限制）1230x x x ≥，，（1）以456,,x x x 表示三个约束的不足变量，写出标准型。

（4分）指出所表达的基本可行解，目标函数值。

（4分）（3）指出上面给出的解是否最优。

若不是，求出最优解和最优目标函数值。

（6分） （4）写出本规划的对偶规划，并求出它的最优解。

（4分）（5）若产品1的单位利润从3变为4，问最优方案是什么？此时的最大收益是多少？（4分）（6）若资源常数列向量404810b ⎛⎫ ⎪= ⎪ ⎪⎝⎭变为466010b ⎛⎫⎪'= ⎪ ⎪⎝⎭，问原最优性是否改变？求出此时的最优方案和最大收益。

（4分）第2页（共3页）二、（24分）有123,,A A A 三个工厂，要把生产的产品运往123,,B B B 三个需求点。

若123,,B B B 三个需求点需求量没有得到满足，则单位罚款费用为6，3，4。

各厂的供应量、各点的需求量以及单位运价如下表。

问应如何组织调运才能使总费用（运输费用和罚款费用之和）最小？（1）请将此问题化为供需平衡的运输问题； （2）用最小元素法求（1）的一个初始调运方案； （3）判断（2）中的方案是否最优，并说明原因。

三、（22分）设货车按泊松流到达车站，卸货后马上离开。

已知平均每天到达4辆车。

该货站有2位工人，同时为货车卸货，假设卸货时间服从负指数分布，平均每天可服务6辆车。

求：（1）该货站没有货车卸货的概率。

（4分） （2）在货站排队等候卸货的平均货车数。

（4分） （3）每辆车在货站的平均逗留时间。

运筹学复习题一、填空题1、运筹学主要研究_ 的问题，通过建立模型求解，为决策者进行决策提供科学依据。

2、可行域中任意两点间联结线段上的点均在可行域内，这样的点集叫 。

3、线形规划的标准形式有如下四个特点： 、 、 、 。

4、一个模型是m 个约束，n 个变量，则它的对偶模型为 个约束， 个变量。

5、为求解销量大于产量的运输问题，可虚设一个产地A m+1，它的销量等于_ 。

6、动态规划是解决 最优化问题的一种理论和方法。

二、单项选择题1、在用单纯形法求解某最大化问题时，如果检验数都小于等于零，而且非基变量的检验数全为负数，则表明此问题有（ ）。

A 、无穷多组最优解B 、无最优解C 、无可行解D 、唯一最优解2、互相对偶的两个线性规划问题，若其中一个无可行解，则另一个必定（ ）。

A 、无可行解 B 、有可行解C 、有最优解D 、有可行解，也可能无可行解3、运输问题求解时，m 个产地，n 个销地的初始调运表中，调运数字应该为（ ）。

A 、m+n 个 B 、m×n 个 C 、m+n -1个 D 、m+n+1个4、线性规划可行域的顶点是（ ）。

A 、可行解 B 、基本解 C 、基本可行解 D 、最优解5、如果目标规划要求实际值恰好达到目标值。

则相应的偏离变量应满足（ ）。

A 、d +>0B 、d +=0C 、min （d ++d －）D 、d －>0，d +>0 6、求解一般整数规划模型常用的方法是（ ）。

A 、分枝定界法B 、表上作业法C 、表上作业法和割平面法D 、单纯形法和表上作业法 7、下列说法错误的是（ ）。

A 、整数规划解的目标函数值一般优于其相应的线性规划问题解的目标函数值；B 、用割平面法求解纯整数规划时，要求包括松弛变量在内的全部变量必须取整数值；C 、指派问题数学模型的形式同运输问题十分相似，故也可以用表上作业法求解；D 、求解0-1规划的隐枚举法是分枝定界法的特例。

第一部分绪论第二部分线性规划与单纯形法1 判断下列说法是否正确：(a)图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的；(b)线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大；(c)线性规划问题的每一个基解对应可行域的一个顶点；(d)如线性规划问题存在可行域，则可行域一定包含坐标的原点；(e)对取值无约束的变量x i，通常令其中，在用单纯形法求得的最优解中有可能同时出现(f)用单纯形法求解标准型的线性规划问题时，与对应的变量都可以被选作换入变量；(g)单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负；(h)单纯形法计算中，选取最大正检验数δk对应的变量x k作为换入变量，将使目标函数值得到最快的增长；(i)一旦一个人工变量在迭代中变为非基变量后，则该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果；(j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示；(k)若x1，x2分别是某一线性规划问题的最优解，则也是该线性规划问题的最优解，其中λ1，λ2可以为任意正的实数；(1)线性规划用两阶段法求解时，第一阶段的目标函数通常写为X ai为人工变量)，但也可写为，只要所有k i均为大于零的常数；(m)对一个有n个变量、m个约束的标准型的线性规划问题，其可行域的顶点恰好为个；(n)单纯形法的迭代计算过程是从一个可行解转转换到目标函数值更大的另一个可行解；(o)线性规划问题的可行解如为最优解，则该可行解一定是基可行解；(p)若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解；(q)线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值，则该顶点处的目标函数值达到最优；(r)将线性规划约束条件的“≤”号及“≥”号变换成“＝”号，将使问题的最优目标函数值得到改善；(s)线性规划目标函数中系数最大的变量在最优解中总是取正的值；(t)一个企业利用3种资源生产4种产品，建立线性规划模型求解得到的最优解中，最多只含有3种产品的组合；(u)若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解；(v)一个线性规划问题求解时的迭代工作量主要取决于变量数的多少，与约束条件的数量关系相对较小。

数学建模一周论文论文题目：基于运输问题的数学模型姓名1：学号：姓名2：学号：姓名3：学号：专业：班级：指导教师：2011年12 月29 日（十五）、已知某运输问题的产销平衡表与单位运价表如下表所示（1）求最优调拨方案；（2）如产地的产量变为130，又B地区需要的115单位必须满足，试重新确定最优调拨方案。

一论文摘要一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案的问题。

本论文运用线性规划的数学模型来解决此运输问题中总费用最小的问题。

引入x变量作为决策变量，建立目标函数，列出约束条件，借助MATLAB软件进行模型求解运算，得出其中的最优解，使得把某种产品从3个产地调运到5个销地的总费用最小。

针对模型我们探讨将某产品从3个产地调运到5个销地的最优调拨方案，通过运输问题模，得到模型Z=1011x+1512x+2013x+2014x+4015x+2021x+4022x+1523x+3024x minx+3031x+3532x+4033x+5534x+2535x+3025Z=并用管理运筹学软件软件得出最优解为：min关键词：运输模型最优化线性规划二．问题的重述和分析A（i=1,2,3）和五个销地j B（j=1,2,3,4,5），已知产地i A的产量有三个产地is和销地j B的销量j d，和将物品从产地i运到销地j的单位运价ij c，请问：i将物品从产地运往销地的最优调拨方案。

A，2A，3A三个产地的总产量为50+100+150=300单位；1B，我们知道，1B，3B，4B，5B五个销地的总销量为25+115+60+30+70=300单位，总2A,2A,3A的产量全产量等于总销量，这是一个产销平衡的运输问题。

把产地1B,2B,3B,4B,5B，正好满足这三个销地的需要。

先将安排的部分配给销地1运输量列如下表中：三．模型的假设与符号说明1.模型的假设①每一个产地都有一个固定的供应量，所有的供应量都必须配送到各个销地；②每一个销地都有一个固定的需求量，整个需求量都必须由产地满足；③从任何一个产地到任何一个销地的物品运输成本和所运输的数量成线性比例关系；④这个成本就等于运输的单位成本乘以运输的数量。