西华大学上机实验报告
一、实验目的
掌握线性规划求解的基本方法，熟悉灵敏度分析的步骤和内容；掌握运输问题的模型，概念，求解方法；掌握整数规划的算法。在熟悉lingo软件基本功能基础上，能熟练操作，正确完成模型求解过程及分析过程。
二、实验内容或设计思想
1．lingo软件或运筹学实验软件的安装及菜单熟悉了解.
2．lingo软件或运筹学实验软件应用内容之：任选几种不同类型的LP输入计算程序，运行求解；完成产销平衡的运输问题求解；求解任一整数规划。
三、实验环境与工具
计算机，lingo软件，运筹学软件
四、实验过程或实验数据
1用lingo求解线性规划
某企业在计划期内要安排生产A、B两种产品。已知生产单位产品的利润与所需劳动力、
用、TABLES
max=60*desks+30*tables+20*chairs;
8*desks+6*tables+chairs<=48;
4*desks+2*tables+1.5*chairs<=20;
2*desks+1.5*tables+.5*chairs<=8;
tables<=5;
求解这个模型，并激活灵敏性分析。这时，查看报告窗口（Reports Window）,可以看到如下结果。
Global optimal solution found at iteration: 3
Objective value: 280.0000
Variable Value Reduced Cost DESKS 2.000000 0.000000 TABLES 0.000000 5.000000 CHAIRS 8.000000 0.000000 Row Slack or Surplus Dual Price
1 280.0000 1.000000
2 24.00000 0.000000
3 0.000000 10.00000
4 0.000000 10.00000
5 5.000000 0.000000
2 用运筹学软件求解线性规划
（例子和过程参照教材）
使用LINGO软件计算运输问题和整数规划问题
model:
!6发点8收点运输问题;
sets:
warehouses/wh1..wh6/: capacity;
vendors/v1..v8/: demand;
links(warehouses,vendors): cost, volume;
endsets
!目标函数;
min=@sum(links: cost*volume);
!需求约束;
@for(vendors(J):
@sum(warehouses(I): volume(I,J))=demand(J));
!产量约束;
@for(warehouses(I):
@sum(vendors(J): volume(I,J))<=capacity(I));
!这里是数据;
data:
capacity=60 55 51 43 41 52;
demand=35 37 22 32 41 32 43 38;
cost=6 2 6 7 4 2 9 5
4 9
5 3 8 5 8 2
5 2 1 9 7 4 3 3
7 6 7 3 9 2 7 1
2 3 9 5 7 2 6 5
5 5 2 2 8 1 4 3;
enddata
end
Global optimal solution found at iteration: 20
Objective value: 664.0000
Variable Value Reduced Cost CAPACITY( WH1) 60.00000 0.000000 CAPACITY( WH2) 55.00000 0.000000 CAPACITY( WH3) 51.00000 0.000000 CAPACITY( WH4) 43.00000 0.000000 CAPACITY( WH5) 41.00000 0.000000 CAPACITY( WH6) 52.00000 0.000000 DEMAND( V1) 35.00000 0.000000 DEMAND( V2) 37.00000 0.000000 DEMAND( V3) 22.00000 0.000000 DEMAND( V4) 32.00000 0.000000 DEMAND( V5) 41.00000 0.000000 DEMAND( V6) 32.00000 0.000000 DEMAND( V7) 43.00000 0.000000 DEMAND( V8) 38.00000 0.000000 COST( WH1, V1) 6.000000 0.000000 COST( WH1, V2) 2.000000 0.000000 COST( WH1, V3) 6.000000 0.000000 COST( WH1, V4) 7.000000 0.000000 COST( WH1, V5) 4.000000 0.000000 COST( WH1, V6) 2.000000 0.000000 COST( WH1, V7) 9.000000 0.000000 COST( WH1, V8) 5.000000 0.000000 COST( WH2, V1) 4.000000 0.000000 COST( WH2, V2) 9.000000 0.000000 COST( WH2, V3) 5.000000 0.000000 COST( WH2, V4) 3.000000 0.000000 COST( WH2, V5) 8.000000 0.000000 COST( WH2, V6) 5.000000 0.000000 COST( WH2, V7) 8.000000 0.000000 COST( WH2, V8) 2.000000 0.000000 COST( WH3, V1) 5.000000 0.000000 COST( WH3, V2) 2.000000 0.000000 COST( WH3, V3) 1.000000 0.000000 COST( WH3, V4) 9.000000 0.000000 COST( WH3, V5) 7.000000 0.000000 COST( WH3, V6) 4.000000 0.000000 COST( WH3, V7) 3.000000 0.000000 COST( WH3, V8) 3.000000 0.000000 COST( WH4, V1) 7.000000 0.000000 COST( WH4, V2) 6.000000 0.000000 COST( WH4, V3) 7.000000 0.000000 COST( WH4, V4) 3.000000 0.000000 COST( WH4, V5) 9.000000 0.000000 COST( WH4, V6) 2.000000 0.000000 COST( WH4, V7) 7.000000 0.000000 COST( WH4, V8) 1.000000 0.000000 COST( WH5, V1) 2.000000 0.000000 COST( WH5, V2) 3.000000 0.000000 COST( WH5, V3) 9.000000 0.000000
COST( WH5, V4) 5.000000 0.000000 COST( WH5, V5) 7.000000 0.000000 COST( WH5, V6) 2.000000 0.000000 COST( WH5, V7) 6.000000 0.000000 COST( WH5, V8) 5.000000 0.000000 COST( WH6, V1) 5.000000 0.000000 COST( WH6, V2) 5.000000 0.000000 COST( WH6, V3) 2.000000 0.000000 COST( WH6, V4) 2.000000 0.000000 COST( WH6, V5) 8.000000 0.000000 COST( WH6, V6) 1.000000 0.000000 COST( WH6, V7) 4.000000 0.000000 COST( WH6, V8) 3.000000 0.000000 VOLUME( WH1, V1) 0.000000 5.000000 VOLUME( WH1, V2) 19.00000 0.000000 VOLUME( WH1, V3) 0.000000 5.000000 VOLUME( WH1, V4) 0.000000 7.000000 VOLUME( WH1, V5) 41.00000 0.000000 VOLUME( WH1, V6) 0.000000 2.000000 VOLUME( WH1, V7) 0.000000 6.000000 VOLUME( WH1, V8) 0.000000 6.000000 VOLUME( WH2, V1) 1.000000 0.000000 VOLUME( WH2, V2) 0.000000 4.000000 VOLUME( WH2, V3) 0.000000 1.000000 VOLUME( WH2, V4) 32.00000 0.000000 VOLUME( WH2, V5) 0.000000 1.000000 VOLUME( WH2, V6) 0.000000 2.000000 VOLUME( WH2, V7) 0.000000 2.000000 VOLUME( WH2, V8) 0.000000 0.000000 VOLUME( WH3, V1) 0.000000 4.000000 VOLUME( WH3, V2) 11.00000 0.000000 VOLUME( WH3, V3) 0.000000 0.000000 VOLUME( WH3, V4) 0.000000 9.000000 VOLUME( WH3, V5) 0.000000 3.000000 VOLUME( WH3, V6) 0.000000 4.000000 VOLUME( WH3, V7) 40.00000 0.000000 VOLUME( WH3, V8) 0.000000 4.000000 VOLUME( WH4, V1) 0.000000 4.000000 VOLUME( WH4, V2) 0.000000 2.000000 VOLUME( WH4, V3) 0.000000 4.000000 VOLUME( WH4, V4) 0.000000 1.000000 VOLUME( WH4, V5) 0.000000 3.000000 VOLUME( WH4, V6) 5.000000 0.000000 VOLUME( WH4, V7) 0.000000 2.000000 VOLUME( WH4, V8) 38.00000 0.000000 VOLUME( WH5, V1) 34.00000 0.000000 VOLUME( WH5, V2) 7.000000 0.000000 VOLUME( WH5, V3) 0.000000 7.000000 VOLUME( WH5, V4) 0.000000 4.000000 VOLUME( WH5, V5) 0.000000 2.000000 VOLUME( WH5, V6) 0.000000 1.000000 VOLUME( WH5, V7) 0.000000 2.000000 VOLUME( WH5, V8) 0.000000 5.000000 VOLUME( WH6, V1) 0.000000 3.000000 VOLUME( WH6, V2) 0.000000 2.000000 VOLUME( WH6, V3) 22.00000 0.000000 VOLUME( WH6, V4) 0.000000 1.000000 VOLUME( WH6, V5) 0.000000 3.000000 VOLUME( WH6, V6) 27.00000 0.000000 VOLUME( WH6, V7) 3.000000 0.000000 VOLUME( WH6, V8) 0.000000 3.000000
Row Slack or Surplus Dual Price
1 664.0000 -1.000000
2 0.000000 -4.000000
3 0.000000 -5.000000
4 0.000000 -4.000000
5 0.000000 -3.000000
6 0.000000 -7.000000
7 0.000000 -3.000000
8 0.000000 -6.000000
9 0.000000 -2.000000
10 0.000000 3.000000
11 22.00000 0.000000
12 0.000000 3.000000
13 0.000000 1.000000
14 0.000000 2.000000
15 0.000000 2.000000
model:
!3发点4收点运输问题;
sets:
warehouses/wh1..wh3/: capacity;
vendors/v1..v4/: demand;
links(warehouses,vendors): cost, volume;
endsets
!目标函数;
min=@sum(links: cost*volume);
!需求约束;
@for(vendors(J):
@sum(warehouses(I): volume(I,J))=demand(J));
!产量约束;
@for(warehouses(I):
@sum(vendors(J): volume(I,J))<=capacity(I));
!这里是数据;
data:
capacity=60 55 51 ;
demand=35 37 22 72 ;
cost=6 2 6 7
4 9
5 3
5 2 1 9;
enddata
end
Global optimal solution found at iteration: 5
Objective value: 561.0000
Variable Value Reduced Cost CAPACITY( WH1) 60.00000 0.000000 CAPACITY( WH2) 55.00000 0.000000 CAPACITY( WH3) 51.00000 0.000000 DEMAND( V1) 35.00000 0.000000 DEMAND( V2) 37.00000 0.000000 DEMAND( V3) 22.00000 0.000000 DEMAND( V4) 72.00000 0.000000 COST( WH1, V1) 6.000000 0.000000 COST( WH1, V2) 2.000000 0.000000 COST( WH1, V3) 6.000000 0.000000 COST( WH1, V4) 7.000000 0.000000 COST( WH2, V1) 4.000000 0.000000 COST( WH2, V2) 9.000000 0.000000 COST( WH2, V3) 5.000000 0.000000 COST( WH2, V4) 3.000000 0.000000 COST( WH3, V1) 5.000000 0.000000 COST( WH3, V2) 2.000000 0.000000 COST( WH3, V3) 1.000000 0.000000 COST( WH3, V4) 9.000000 0.000000 VOLUME( WH1, V1) 6.000000 0.000000 VOLUME( WH1, V2) 37.00000 0.000000 VOLUME( WH1, V3) 0.000000 4.000000 VOLUME( WH1, V4) 17.00000 0.000000 VOLUME( WH2, V1) 0.000000 2.000000 VOLUME( WH2, V2) 0.000000 11.00000 VOLUME( WH2, V3) 0.000000 7.000000 VOLUME( WH2, V4) 55.00000 0.000000 VOLUME( WH3, V1) 29.00000 0.000000 VOLUME( WH3, V2) 0.000000 1.000000 VOLUME( WH3, V3) 22.00000 0.000000 VOLUME( WH3, V4) 0.000000 3.000000 Row Slack or Surplus Dual Price
1 561.0000 -1.000000
2 0.000000 -6.000000
3 0.000000 -2.000000
4 0.000000 -2.000000
5 0.000000 -7.000000
6 0.000000 0.000000
7 0.000000 4.000000
8 0.000000 1.000000
示例3 分配问题
model:
!4个工人，4个工作的分配问题;
sets:
workers/w1..w4/;
jobs/j1..j4/;
links(workers,jobs): cost,volume;
endsets
!目标函数;
min=@sum(links: cost*volume);
!每个工人只能有一份工作;
@for(workers(I):
@sum(jobs(J): volume(I,J))=1;
);
!每份工作只能有一个工人;
@for(jobs(J):
@sum(workers(I): volume(I,J))=1;
);
data:
cost= 6 2 6 7
4 9
5 3
5 2 1 9
7 6 7 3 ;
enddata
end
Global optimal solution found at iteration: 0
Objective value: 10.00000
Variable Value Reduced Cost COST( W1, J1) 6.000000 0.000000 COST( W1, J2) 2.000000 0.000000 COST( W1, J3) 6.000000 0.000000 COST( W1, J4) 7.000000 0.000000 COST( W2, J1) 4.000000 0.000000 COST( W2, J2) 9.000000 0.000000 COST( W2, J3) 5.000000 0.000000 COST( W2, J4) 3.000000 0.000000 COST( W3, J1) 5.000000 0.000000 COST( W3, J2) 2.000000 0.000000 COST( W3, J3) 1.000000 0.000000 COST( W3, J4) 9.000000 0.000000 COST( W4, J1) 7.000000 0.000000 COST( W4, J2) 6.000000 0.000000 COST( W4, J3) 7.000000 0.000000 COST( W4, J4) 3.000000 0.000000 VOLUME( W1, J1) 0.000000 1.000000 VOLUME( W1, J2) 1.000000 0.000000 VOLUME( W1, J3) 0.000000 0.000000 VOLUME( W1, J4) 0.000000 3.000000 VOLUME( W2, J1) 1.000000 0.000000 VOLUME( W2, J2) 0.000000 8.000000 VOLUME( W2, J3) 0.000000 0.000000 VOLUME( W2, J4) 0.000000 0.000000 VOLUME( W3, J1) 0.000000 5.000000 VOLUME( W3, J2) 0.000000 5.000000 VOLUME( W3, J3) 1.000000 0.000000 VOLUME( W3, J4) 0.000000 10.00000 VOLUME( W4, J1) 0.000000 3.000000 VOLUME( W4, J2) 0.000000 5.000000 VOLUME( W4, J3) 0.000000 2.000000 VOLUME( W4, J4) 1.000000 0.000000 Row Slack or Surplus Dual Price
1 10.00000 -1.000000
2 0.000000 -1.000000
3 0.000000 0.000000
4 0.000000 4.000000
5 0.000000 0.000000
6 0.000000 -4.000000
7 0.000000 -1.000000
8 0.000000 -5.000000
9 0.000000 -3.000000
示例4 解整数规划，在lingo窗口输入以下代码，
min=3*x1+x2+3*x3+3*x4+x5+x6+3*x7;
4*x1+3*x2+2*x3+x4+x5>=50;
x2+2*x4+x5+3*x6>=20;
x3+x5+2*x7>=15;
@gin(x1);@gin(x2);@gin(x3);
@gin(x4);@gin(x3);@gin(x6);@gin(x7);
END
运行结果为：
Global optimal solution found.
Objective value: 27.00000
Extended solver steps: 0
Total solver iterations: 5
Variable Value Reduced Cost
X1 0.000000 3.000000
X2 12.00000 1.000000
X3 0.000000 2.000000
X4 0.000000 3.000000
X5 15.00000 0.000000
X6 0.000000 1.000000
X7 0.000000 1.000000
Row Slack or Surplus Dual Price
1 27.00000 -1.000000
2 1.000000 0.000000
3 7.000000 0.000000
4 0.000000 -1.000000
2 用运筹学实验软件计算运输问题和整数规划问题
五、总结
对上机实践结果进行分析，问题回答，上机的心得体会及改进意见。要用自己的语言表达，不得抄袭雷同
例1：生产计划问题 某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如下表。若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费O.2万元。现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低。试建立模型。 解： 法1 设每个季度分别生产x1,x2,x3,x4 则要满足每个季度的需求x4≥26 x1+ x2≥40 x1+ x2+ x3≥70 x1+ x2+ x3+ x4=80 考虑到每个季度的生产能力 0≤x1≤30 0≤x2≤40 0≤x3≤20 0≤x4≤10 每个季度的费用为：此季度生产费用+上季度储存费用 第一季度15.0x1 第二季度14 x2 0.2(x1-20) 第三季度15.3x3+0.2(x1+ x2-40) 第四季度14.8x4+0.2(x1+ x2+ x3-70)
工厂一年的费用即为这四个季度费用之和, 得目标函数；minf=15.6 x1+14.4 x2+15.5 x3+14.8 x4-26 s.t．x1+ x2≥40 x1+ x2+ x3≥70 x1+ x2+ x3+ x4=80 20≤x1≤30 0≤x2≤40 0≤x3≤20 0≤x4≤10。 法2：设第i季度生产而用于第j季度末交货的产品数量为xij吨 根据合同要求有： xll=20 x12+x22=20 x13+x23+x33=30 x14+x24+x34+x44=10 又根据每季度的生产能力有： xll+x12+x13+x14≤30 x22+x23+x24≤40 x33+x34≤20 x44≤10 第i季度生产的用于第j季度交货的每吨产品的费用cij=dj+0.2(j-i)，于是，有线性规划模型。 minf=15.Oxll+15.2x12+15.4xl3+15.6xl4+14x22+14.2x23+14.4x24+15.3 x33+15.5x34+14.8x44 s．t． xll=20， x12+x22=20， x13+x23+x13=30， x14+x24+x34+x44=10， x1l+x12+x13+x14≤30， x22+x23+x24≤40， x33+x34≤20，
线性规划在运输问题中的应用 【摘要】用运筹学的思想探讨运筹学课程的教学方法。运筹学中的指派问题、最短路问题，最小费用流问题可转化为运输问题或转运问题，从而可以统筹安排这些教学内容，为提高教学效果，减少教学时间找出更优的教学方法。 【关键词】运输问题；转运问题；运筹学；线性规划；教学方法 引言： 随着我国国民经济的不断发展，企业之间的交易活动更加频繁,同地区、不同地区、甚至跨国的交易活动也不断发生，运输则成为交易的活动重点了。交通运输作为国民经济的一个重要部门，作为人类进步、社会发展的一个重要推动力，其发展模式正在对环境产生越来越重要的影响。传统的运输方式已经不能满足环境保护、经济发展以及交通运输本身发展的需求，探寻与环境、资源条件相适应的运输是非常重要的一个问题。人们在运输方面趋利避害建立更好的运输方法，让交通运输的方法达到一个更高的水平。 1．线性规划简介 线性规划法是解决多变量最优决策的方法，是在各种相互关联的多变量约束条件下，解决或规划一个对象的线性目标函数最优的问题，即给与一定数量的人力、物力和资源，如何应用而能得到最大经济效益。当资源限制或约束条件表现为线性等式或不等式，目标函数表示为线性函数时，可运用线性规划法进行决策。线性规划法就是在线性等式或不等式的约束条件下，求解线性目标函数的最大值或最小值的方法。其中目标函数是决策者要求达到目标的数学表达式，用一个极大或极小值表示。约束条件是指实现目标的能力资源和内部条件的限制因素，用一组等式或不等式来表示。线性规划是决策系统的静态最优化数学规划方法之一。它作为经营管理决策中的数学手段，在现代决策中的应用是非常广泛的，它可以用来解决科学研究、工程设计、生产安排、军事指挥、经济规划；经营管理等各方面提出的大量问题。 最近几年，我国物流产业快速发展，形成了物流热。在物流作业的管理活动中，有着大量的规划问题，物资的合理调运就是其中一个比较重要的问题。求物资调运的最优调运方案，就是要在满足各种资源限制的条件下，找到使运输总费用最小的调运方案。 2.线性规划在运输中的应用 在现实的生产经营、商品销售、经济建设和物资管理过程中，常常会遇到各类物资的分配和调运问题，即将各种生产资料或生活资料消耗品从供给基地调运到需求基地，这里就需要如何根据现有条件科学、合理的安排调运方案，提高运输经济效益。这就是属于线性规划中网络配送的以最小的成本完成货物的运输问题。运输问题就是讨论有关物资调运的问题，即将数量和单位运价都给定的某种物资从供应站运送到消费站，要求在供给和需求平衡的同时，制定出流量与流向，使总运输成本最低。运输问题是特殊的线性规划问题，根据问题的要求，建立数学模型，用表上作业法或线性规划软件求解，即可得出最佳的调运方案，取得了较好的经济效益。在运输问题中，确定的需求限制占据着重要的地位，即必须确定需求以及相应地确定需求的约束条件。 3.运输问题的特征 运输问题关心的是以最低的总配送成本把供应中心（出发地）的任何产品运送到每一个接收中心（目的地）。每一个出发地都有一定供应量配送到目的地，每一个目的地都需要一定的需求量。运输问题在供应量和需求量两方面都做出了如下的假设：需求假设。每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之类似，每一个目的地都有
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将下述线性规划问题化成标准形式。 ????? ? ?≥≥-++-≤+-+-=-+-+-+-=无约束 43 214321432143214321,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 z 2-3分别用图解法和单纯形法求解下述线性规划问题，并对照指出单纯形表中的各基 可行解对应图解法中可行()?????≥≤≤-+-=++-+-=无约束 321 3213213 21,0,06 24 .322min 2x x x x x x x x x st x x x z 域的哪一顶点。 ()??? ??≥≤+≤++=0,8259 43.510max 12 1212121x x x x x x st x x z ()??? ??≥≤+≤++=0,242615 53.2max 22 121212 1x x x x x x st x x z 2-4已知线性规划问题，写出其对偶问题： 5 43212520202410max x x x x x z ++++=
Lingo12软件培训教案 Lingo 主要用于求解线性规划，整数规划，非线性规划，V10以上版本可编程。 例1 一个简单的线性规划问题 0 , 600 2 100 350 st. 3 2max >=<=+=<<=++=y x y x x y x y x z ! 源程序 max = 2*x+3*y; [st_1] x+y<350; [st_2] x<100; 2*x+y<600; !决策变量黙认为非负; <相当于<=; 大小写不区分 当规划问题的规模很大时，需要定义数组(或称为矩阵)，以及下标集(set) 下面定义下标集和对应数组的三种方法，效果相同:：r1 = r2 = r3, a = b = c. sets : r1/1..3/:a; r2 : b; r3 : c; link2(r1,r2): x; link3(r1,r2,r3): y; endsets data : ALPHA = ; a=11 12 13 ; r2 = 1..3; b = 11 12 13; c = 11 12 13; enddata
例2 运输问题 解： 设决策变量ij x = 第i 个发点到第j 个售点的运货量，i =1,2,…m; j =1,2,…n; 记为ij c =第i 个发点到第j 个售点的运输单价，i =1,2,…m; j =1,2,…n 记i s =第i 个发点的产量， i =1,2,…m; 记j d =第j 个售点的需求量， j =1,2,…n. 其中，m = 6; n = 8. 设目标函数为总成本，约束条件为（1）产量约束；（2）需求约束。 于是形成如下规划问题： n j m i x n j d x m i s x x c ij j n i ij i m j ij m i n j ij ij ,...,2,1,,...,2,1,0 ,...,2,1, ,...,2,1, st. z min 11 11==>=<==<==∑∑∑∑==== 把上述程序翻译成LINGO 语言，编制程序如下： ! 源程序
简单的线性规划问题 [ 学习目标 ] 1.了解线性规划的意义以及约束条件、目标函数、可行解、可行域、最优解等基本概念 .2. 了解线性规划问题的图解法，并能应用它解决一些简单的实际问题． 知识点一线性规划中的基本概念 知识点二线性规划问题 1．目标函数的最值 线性目标函数 z＝ax＋by (b≠0)对应的斜截式直线方程是 y＝－a x＋z，在 y 轴上的 截距是z， b b b 当 z 变化时，方程表示一组互相平行的直线． 当 b>0，截距最大时， z 取得最大值，截距最小时， z 取得最小值； 当 b<0，截距最大时， z 取得最小值，截距最小时， z 取得最大值． 2．解决简单线性规划问题的一般步骤在确定线性约束条件和线性目标函数的前提下，解决简单线性规划问题的步骤可以概括为：“画、移、求、答”四步，即， (1)画：根据线性约束条件，在平面直角坐标系中，把可行域表示的平面图形准确地画出来，可行域可以是封闭的多边形，也可以是一侧开放的无限大的平面区域．(2)移：运用数形结合的思想，把目标函数表示的直线平行移动，最先通过或最后通过的顶点 (或边界 )便是最优解． (3)求：解方程组求最优解，进而求出目标函数的最大值或最小值． (4)答：写出答案．
知识点三简单线性规划问题的实际应用 1．线性规划的实际问题的类型 (1)给定一定数量的人力、物力资源，问怎样运用这些资源，使完成的任务量最大，收到的效益最大； (2)给定一项任务，问怎样统筹安排，使完成这项任务耗费的人力、物力资源量最小．常见问题有： ①物资调动问题例如，已知两煤矿每年的产量，煤需经两个车站运往外地，两个车站的运输能力是有限的，且已知两煤矿运往两个车站的运输价格，煤矿应怎样编制调动方案，才能使总运费最小？ ②产品安排问题例如，某工厂生产甲、乙两种产品，每生产一个单位的甲种或乙种产品需要的A、B、C 三种 材料的数量，此厂每月所能提供的三种材料的限额都是已知的，这个工厂在每个月中应如何安排这两种产品的生产，才能使每月获得的总利润最大？ ③下料问题例如，要把一批长钢管截成两种规格的钢管，应怎样下料能使损耗最小？2．解答线性规划实际应用题的步骤 (1)模型建立：正确理解题意，将一般文字语言转化为数学语言，进而建立数学模型，这需要在学习有关例题解答时，仔细体会范例给出的模型建立方法． (2)模型求解：画出可行域，并结合所建立的目标函数的特点，选定可行域中的特殊点作为最优解． (3)模型应用：将求解出来的结论反馈到具体的实例中，设计出最佳的方案． 题型一求线性目标函数的最值 y≤2， 例 1 已知变量 x，y 满足约束条件 x＋y≥1，则 z＝3x＋y 的最大值为 ( ) x－y≤1， A ． 12 B ．11 C ．3 D ．－ 1 答案 B 解析首先画出可行域，建立在可行域的基础上，分析最值点，然后通过解方程组得最值点 的坐标，代入即可．如图中的阴影部分，即为约束条件对应的可行域，当直线y＝－3x＋z 经 y＝2，x＝ 3，
《管理运筹学》实验报告 实验日期：2016年04月21日——2016年05月18日 实验目的： 通过实验学生应该熟练掌握“管理运筹学 3.0”软件的使用，并能利用“管理运筹学 3.0” 对具体问题进行问题处理，且能对软件处理结果进行解释和说明。实验所用软件及版本：管理运筹学3.0 实验过程：（含基本步骤及异常情况记录等―） 一、实验步骤（以P31页习题1为例） 1?打开软件“管理运筹学3.0” 2?在主菜单中选择线性规划模型，屏幕中会出现线性规划页面 3?在点击“新建”按钮以后，按软件的要求输入目标函数个数和约束条件个数，输入目标函数级约束条件的歌变量的系数和b值，并选择好“w”、“》”或“二”, 如图二所示，最后点击解决 班级2014级04班姓名杨艺玲学号2014190456实验 名称 管理运筹学问题的计算机求解 n 幵 目标的数 娈童个数约束条件个数 芙 遇出 保存解决关于
X 4?注意事项： (1)输入的系数可以是整数、小数，但不能是分数，要把分数化为小数再输入。 (2)输入前要合并同类项。 当约束条件输入完毕后，请点击“解决”按钮，屏幕上讲显现线性规划问题的结果, 如 图所示 D tiff 0% 关于遇出 变童个数约朿条件个数F目标的数3V 标淮北结杲: 上一曲
5.输出结果如下 me車最优解如下***#尊1林*祜除目标函数最优值知2?20 变1 最优解相差値 XI 4.00 0.00 X2 8.00 0100 釣束松弛颅11余变量对偶价格 01. 00 16. 5€ 0.00 13.33 目标函数系数范園: 娈1下限当前值上限 XI 120. 30 200.00430. 00 X2 100. 0D 240.00400.00 常数【页范園； 的束T眼当前值上限 143.00120 00152.00 240.00 64.00 160.00 5.课后习题： 一、P31习题1 某家具公司生产甲、乙两种型号的组合柜，每种组合柜需要两种工艺（制白坯和油漆）.甲型号组合柜需要制白坯6工时，油漆8工时：乙型号组合柜需要制白坯12工时，油漆4工时.已知制白坯工艺的生产能力为120工时/天，油漆工艺的生产能力为64工时/天，甲型号组合柜单位利润200元，乙型号组合柜单位利润为240 元. max z = 200x 240y; 约束条件：6x，12心2°, 8x +4y 兰64, x 一0, y -0. 问题： （1）甲、乙两种柜的日产量是多少？这时最大利润是多少？ 答：由实验过程中的输出结果得甲组合柜的日产量是4个，乙的事8个
线性规划在运输问题中的 应用 Newly compiled on November 23, 2020
线性规划在运输问题中的应用 【摘要】用运筹学的思想探讨运筹学课程的教学方法。运筹学中的指派问题、最短路问题，最小费用流问题可转化为运输问题或转运问题，从而可以统筹安排这些教学内容，为提高教学效果，减少教学时间找出更优的教学方法。 【关键词】运输问题；转运问题；运筹学；线性规划；教学方法 引言： 随着我国国民经济的不断发展，企业之间的交易活动更加频繁,同地区、不同地区、甚至跨国的交易活动也不断发生，运输则成为交易的活动重点了。交通运输作为国民经济的一个重要部门，作为人类进步、社会发展的一个重要推动力，其发展模式正在对环境产生越来越重要的影响。传统的运输方式已经不能满足环境保护、经济发展以及交通运输本身发展的需求，探寻与环境、资源条件相适应的运输是非常重要的一个问题。人们在运输方面趋利避害建立更好的运输方法，让交通运输的方法达到一个更高的水平。 1．线性规划简介 线性规划法是解决多变量最优决策的方法，是在各种相互关联的多变量约束条件下，解决或规划一个对象的线性目标函数最优的问题，即给与一定数量的人力、物力和资源，如何应用而能得到最大经济效益。当资源限制或约束条件表现为线性等式或不等式，目标函数表示为线性函数时，可运用线性规划法进行决策。线性规划法就是在线性等式或不等式的约束条件下，求解线性目标函数的最大值或最小值的方法。其中目标函数是决策者要求达到目标的数学表达式，用一个极大或极小值表示。约束条件是指实现目标的能力资源和内部条件的限制因素，用一组等式或不等式来表示。线性规划是决策系统的静态最优化数学规划方法之一。它作为经营管理决策中的数学手段，在现代决策中的应用是非常广泛的，它可以用来解决科学研究、工程设计、生产安排、军事指挥、经济规划；经营管理等各方面提出的大量问题。 最近几年，我国物流产业快速发展，形成了物流热。在物流作业的管理活动中，有着大量的规划问题，物资的合理调运就是其中一个比较重要的问题。求物资调运的最优调运方案，就是要在满足各种资源限制的条件下，找到使运输总费用最小的调运方案。 2.线性规划在运输中的应用 在现实的生产经营、商品销售、经济建设和物资管理过程中，常常会遇到各类物资的分配和调运问题，即将各种生产资料或生活资料消耗品从供给基地调运到需求基地，这里就需要如何根据现有条件科学、合理的安排调运方案，提高运输经济效益。这就是属于线性规划中网络配送的以最小的成本完成货物的运输问题。运输问题就是讨论有关物资调运的问题，即将数量和单位运价都给定的某种物资从供应站运送到消费站，要求在供给和需求平衡的同时，制定出流量与流向，使总运输成本最低。运输问题是特殊的线性规划问题，根据问题的要求，建立数学模型，用表上作业法或线性规划软件求解，即可得出最佳的调运方案，取得了较好的经济效益。在运输问题中，确定的需求限制占据着重要的地位，即必须确定需求以及相应地确定需求的约束条件。 3.运输问题的特征 运输问题关心的是以最低的总配送成本把供应中心（出发地）的任何产品运送到每一个接收中心（目的地）。每一个出发地都有一定供应量配送到目的地，每一个目的地都需要一定的需求量。运输问题在供应量和需求量两方面都做出了如下的假设：需求假设。每一个出发地都有一个固定的供应量，所有的供应量都必须配送到目的地。与之类似，每一个目的地都有一个固定的需求量，整个需求量都必须由出发地满足成本假设。从任何一个出发地到任何一个目的地的货物配送成本和所配送的数量成线性比例关系。因此，这个成本就等于配送的单位成本乘以所配送的数量。运输问题所需要的数据仅仅是供应量、需求量和单位成本，这些就是模型参数。如果一个问题可以完全描述成
数学建模与实验课程实验报告 实验名称三、线性规划与整数规划实验地点日期2014-10-28 姓名班级学号成绩 【实验目的及意义】 [1] 学习最优化技术和基本原理，了解最优化问题的分类； [2] 掌握规划的建模技巧和求解方法； [3] 学习灵敏度分析问题的思维方法； [4] 熟悉MATLAB软件求解规划模型的基本命令； [5] 通过范例学习，熟悉建立规划模型的基本要素和求解方法。 通过该实验的学习，使学生掌握最优化技术，认识面对什么样的实际问题，提出假设和 建立优化模型，并且使学生学会使用MATLAB、Lingo软件进行规划模型求解的基本命令， 并进行灵敏度分析。解决现实生活中的最优化问题是本科生学习阶段中一门重要的课程，因 此，本实验对学生的学习尤为重要。 【实验要求与任务】 根据实验内容和步骤，完成以下实验，要求写出实验报告（符号说明—模型的建立—模型 的求解（程序）—结论） A组 高校资金投资问题 高校现有一笔资金100万元，现有4个投资项目可供投资。 项目A：从第一年到底四年年初需要投资，并于次年年末回收本利115%。 项目B：从第三年年初需要投资，并于第5年末才回收本利135%，但是规定最大投资总 额不超过40万元。 项目C：从第二年年初需要投资，并于第5年末才回收本利M%，但是规定最大投资总 额不超过30万元。(其中M为你学号的后三位+10) 项目D：五年内每年年初可以买公债，并于当年年末归还，并可获得6%的利息。 试为该校确定投资方案，使得第5年末他拥有的资金本利总额最大。 该校在第3年有个校庆，学校准备拿出8万元来筹办，又应该如何安排投资方案，使得 第5年末他拥有的资金本利总额最大。 B组题 1)最短路问题, 图1中弧上的数字为相邻2点之间的路程，求从1到7的最短路。 图1 图 2 r为你的学号后2位+10 其中 1 2)最大车流量, 图1中弧上的数字为相邻2点之间每小时的最大车流量。求每小时1到7最大
线性规划常见题型及解法 由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下六类常见题型。 一、求线性目标函数的取值范围 例1、 若x 、y 满足约束条件222x y x y ≤?? ≤??+≥? ，则z=x+2y 的取值范围是 （ ） A 、[2,6] B 、[2,5] C 、[3,6] D 、（3,5] 解：如图，作出可行域，作直线l ：x+2y ＝0，将 l 向右上方平移，过点A （2,0）时，有最小值 2，过点B （2,2）时，有最大值6，故选A 二、求可行域的面积 例2、不等式组260302x y x y y +-≥?? +-≤??≤? 表示的平面区域的面积为 （ ） A 、4 B 、1 C 、5 D 、无穷大 解：如图，作出可行域，△ABC 的面积即为所求，由梯形OMBC 的面积减去梯形OMAC 的面积即可，选B 三、求可行域中整点个数 例3、满足|x|＋|y|≤2的点（x ，y ）中整点（横纵坐标都是整数）有（ ） A 、9个 B 、10个 C 、13个 D 、14个 x y O 2 2 x=2 y =2 x + y =2 B A 2x + y – 6= 0 = 5 x ＋y – 3 = 0 O y x A B C M y =2
解：|x|＋|y|≤2等价于2(0,0)2(0,0)2(0,0) 2 (0,0)x y x y x y x y x y x y x y x y +≤≥≥??-≤≥? ? -+≤≥??--≤? 作出可行域如右图，是正方形内部（包括边界），容易得到整 点个数为13个，选D 四、求线性目标函数中参数的取值范围 例4、已知x 、y 满足以下约束条件5503x y x y x +≥?? -+≤??≤? ，使z=x+ay(a>0) 取得最小值的最优解有无数个，则a 的值为 （ ） A 、－3 B 、3 C 、－1 D 、1 解：如图，作出可行域，作直线l ：x+ay ＝0，要使目标函数z=x+ay(a>0)取得最小值的最优解 有无数个，则将l 向右上方平移后与直线x+y ＝5重合，故a=1，选D 五、求非线性目标函数的最值 例5、已知x 、y 满足以下约束条件220240330x y x y x y +-≥?? -+≥??--≤? ，则z=x 2+y 2的最大值和最小值分别是（ ） A 、13，1 B 、13，2 C 、13，4 5 D 、 5 解：如图，作出可行域,x 2+y 2是点（x ，y ）到原点的距离的平方，故最大值为点A （2,3）到原点的距离的平方，即|AO|2=13，最小值为原点到直线2x ＋y －2=0的距离的平方，即为 4 5 ，选C 六、求约束条件中参数的取值范围 例6、已知|2x －y ＋m|＜3表示的平面区域包含点 （0,0）和（－ 1,1），则m 的取值范围是 （ ） A 、（-3,6） B 、（0,6） C 、（0,3） D 、（-3,3）
《运筹学》线性规划部分练习题 一、思考题 1.什么是线性规划模型，在模型中各系数的经济意义是什么？ 2 .线性规划问题的一般形式有何特征？ 3. 建立一个实际问题的数学模型一般要几步？ 4. 两个变量的线性规划问题的图解法的一般步骤是什么？ 5. 求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 6. 什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 7?试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 8?试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 9. 在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 10. 大M法中，M的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问 题呢？ 11 ?什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续 第二阶段？ 二、判断下列说法是否正确。 1 .线性规划问题的最优解一定在可行域的顶点达到。 2 .线性规划的可行解集是凸集。 3. 如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。 4. 线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的 范围一般将扩大。 5 .线性规划问题的每一个基本解对应可行域的一个顶点。 6. 如果一个线性规划问题有可行解，那么它必有最优解。 7. 用单纯形法求解标准形式（求最小值）的线性规划问题时，与j 0对应的变量都可以被 选作换入变量。 8 .单纯形法计算中，如不按最小非负比值原则选出换出变量，则在下一个解中至少有一 个基变量的值是负的。 9. 单纯形法计算中，选取最大正检验数k对应的变量x k作为换入变量，可使目 标函数值得到最快的减少。 10 . 一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形 表中删除，而不影响计算结果。 三、建立下面问题的数学模型 1 .某公司计划在三年的计划期内，有四个建设项目可以投资：项目I从第一年到 第三年年初都可以投资。预计每年年初投资，年末可收回本利120%，每年又可以重新将所获本利纳入投资计划；项目n需要在第一年初投资，经过两年可收回本利150% , 又可以重新将所获本利纳入投资计划，但用于该项目的最大投资额不得超过20万元；项目川需要在第二年年初投资，经过两年可收回本利160%，但用于该项目的最大投资额 不得超过15万元；项目"需要在第三年年初投资，年末可收回本利140%，但用于该项目的最大投资额不得超过10万元。在这个计划期内，该公司第一年可供投资的资金有 30万元。问怎样的投资方案，才能使该公司在这个计划期获得最大利润？ 2 .某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、 100克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单 价如下表2—1所示：
有限制的运输问题：6个发点6个收点，其供应量、接收量和运费如下表1（”-”表示某个 设：发点i向收点j的货物供应量为xij. 目标函数： MinZ=20x11+15x12+16x13+5x14+4x15+7x16+17x21+15x22+33x23+12x24+8x25+6x26+9x31 +12x32+18x33+16x34+30x35+13x36+12x41+8x42+11x43+27x44+19x45+14x46+7x52+10x53+ 21x54+10x55+32x56+6x64+11x65+13x66 供应限制：x11+x12+x13+x14+x15+x16=20 x21+x22+x23+x24+x25x+26=30 x31+x32+x33+x34+x35+x36=50 x41+x42+x43+x44+x45+x46=40 x52+x53+x54+x55+x56=30 x64+x65+x66=30 需求限制：x11+x21+x31+x41=30 x12+x22+x32+x42+x52=50 x13+x23+x33+x43+x53=40 x14+x24+x34+x44+x54+x64=30 x15+x25+x35+x45+x55+x65=30 x16+x26+x36+x46+x56+x66=20 LINGO代码: min=20*x11+15*x12+16*x13+5*x14+4*x15+7*x16+17*x21+15*x22+33*x23+12*x24+8*x25+ 6*x26+9*x31+12*x32+18*x33+16*x34+30*x35+13*x36+12*x41+8*x42+11*x43+27*x44+19* x45+14*x46+7*x52+10*x53+21*x54+10*x55+32*x56+6*x64+11*x65+13*x66; x11+x12+x13+x14+x15+x16=20; x21+x22+x23+x24+x25+x26=30; x31+x32+x33+x34+x35+x36=50; x41+x42+x43+x44+x45+x46=40; x52+x53+x54+x55+x56=30; x64+x65+x66=30; x11+x21+x31+x41=30;
《管理运筹学》实验报告实验日期： 2016年 04月 21日—— 2016 年 05 月 18 日
3.在点击“新建”按钮以后，按软件的要求输入目标函数个数和约束条件个数，输入目标函数级约束条件的歌变量的系数和b值，并选择好“≤”、“≥”或“＝”，如图二所示，最后点击解决
4.注意事项： （1）输入的系数可以是整数、小数，但不能是分数，要把分数化为小数再输入。（2）输入前要合并同类项。 当约束条件输入完毕后，请点击“解决”按钮，屏幕上讲显现线性规划问题的结果，如图所示
5.输出结果如下
5.课后习题： 一、P31习题1 某家具公司生产甲、乙两种型号的组合柜，每种组合柜需要两种工艺（制白坯和油漆）.甲型号组合柜需要制白坯6工时，油漆8工时：乙型号组合柜需要制白坯12工时，油漆4工时.已知制白坯工艺的生产能力为120工时/天，油漆工艺的生产能力为64工时/天，甲型号组合柜单位利润200元，乙型号组合柜单位利润为240元. 约束条件： 问题： （1）甲、乙两种柜的日产量是多少？这时最大利润是多少？ 答：由实验过程中的输出结果得甲组合柜的日产量是4个，乙的事8个。 . 0,0,6448,120126;240200 z max ≥≥≤+≤++=y x y x y x y x
（2）图中的对偶价格13.333的含义是什么？ 答： 对偶价格13.333的含义是约束条件2中，每增加一个工时的油漆工作，利润会增加13.33元。 （3）对图中的常数项围的上、下限的含义给予具体说明，并阐述如何使用这些信息。 答：当约束条件1的常数项在48~192围变化，且其他约束条件不变时，约束条件1的对偶价格不变，仍为15.56；当约束条件2的常数项在40~180围变化，而其他约束条件的常数项不变时，约束条件2的对偶价格不然，仍为13.333。 （4）若甲组合柜的利润变为300，最优解不变？为什么？ 答：目标函数的最优值会变，因为甲组合柜的利润增加，所以总利润和对偶价格增加；甲、乙的工艺耗时不变，所以甲、乙的生产安排不变。 二、学号题 约束条件： 无约束条件 （学号）学号43214321432143214321 0 0,30 9991285376)(53432max x x x x x x x x x x x x x x x x x x x x z ≤≥≤-+-+≥-+-+=-++-+++=??????????????-≥?-?-?-?-?-7606165060~5154050~414 )30(40~313)20(30~21210 20~11 10~1）（学号）（学号）（学号学号学号）（学号不变学号规则
线性规划常见题型及解法 由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下六类常见题型。 一、求线性目标函数的取值范围 例1、若x、y满足约束条件 ，则z=x+2y的取值范围是（） A、[2,6] B、[2,5] C、[3,6] D、（3,5] 解：如图，作出可行域，作直线l：x+2y＝0，将 l向右上方平移，过点A（2,0）时，有最小值 2，过点B（2,2）时，有最大值6，故选A 二、求可行域的面积
例2、不等式组 表示的平面区域的面积为（） A、4 B、1 C、5 D、无穷大 解：如图，作出可行域，△ABC的面积即为所求，由梯形OMBC的面积减去梯形OMAC的面积即可，选B 三、求可行域中整点个数 例3、满足|x|＋|y|≤2的点（x，y）中整点（横纵坐标都是整数）有（） A、9个 B、10个 C、13个 D、14个
解：|x|＋|y|≤2等价于 作出可行域如右图，是正方形内部（包括边界），容易得到整点个数为13个，选D 四、求线性目标函数中参数的取值范围 例4、已知x、y满足以下约束条件 ，使z=x+ay(a>0)取得最小值的最优解有无数个，则a的值为（） A、－3 B、3 C、－1 D、1
解：如图，作出可行域，作直线l：x+ay＝0，要使目标函数z=x+ay(a>0)取得最小值的最优解有无数个，则将l向右上方平移后与直线x+y＝5重合，故 a=1，选D 五、求非线性目标函数的最值 例5、已知x、y满足以下约束条件 ，则z=x2+y2的最大值和最小值分别是（） A、13，1 B、13，2 C、13， D、 ， 解：如图，作出可行域,x2+y2是点（x，y）到原点的距离的平方，故最大值为点A（2,3）到原点的距离的平方，即|AO|2=13，最小值为原点到直线2x＋y－2=0的距离的平方，即为
2013届学士学位毕业论文线性规划在运输问题中的应用 学号：09404323 姓名：李勇 班级：信息0901 指导教师：董建新 专业：信息与计算科学 系别：数学系 完成时间：2013年6月
学生诚信承诺书 本人郑重声明：所呈交的论文《线性规划在运输问题中的应用》是我个人在导师董建新指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得长治学院或其他教育机构的学位或证书所使用过的材料。所有合作者对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 签名：日期： 论文使用授权说明 本人完全了解长治学院有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 签名：日期： 指导教师声明书 本人声明：该学位论文是本人指导学生完成的研究成果，已经审阅过论文的全部内容，并能够保证题目、关键词、摘要部分中英文内容的一致性和准确性。 指导教师签名：时间
摘要 随着我国市场经济的不断完善，同地区、不同地区、甚至跨国间的企业交易更加的频繁。因此，在运输中如何降低运输费用、减少运输路线等问题，已经成为交易活动的重点，而随着社会分工的细化，物流和运输业不断的发展，运输问题也就变的越来越复杂，运输量有时候非常巨大，所以科学的组织运输显得十分重要。线性规划主要应用于解决最优化问题，而运输问题可以看作是一类特殊的线性规划问题。本文结合案例，分析了运输问题的基本特征及解决策略，并通过实例对运输问题进行了优化分析建立了线性规划的数学模型，并借助计算机进行求解，在本篇文章中主要应用的是excel求解，能快速准确的得到最优化方案，提高了实际运输工作中的经济效益。 关键词：线性规划；运输问题；excel
用线性规划方法求解运输问题 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料.二是生产组织与计划的改进，即合理安排人力物力资源.线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好.一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。满足线性约束条件的解叫做可行解，由所有可行解组成的集合叫做可行域。决策变量、约束条件、目标函数是线性规划的三要素. 运输问题的提出及其数学模型：现在人们生产活动中，不可避免的要进行物资调运工作，如某时期内将生产基地的蔬菜，粮食等各类物资，分别运到需要这些物资的地区。如何根据各地的生产量和需求量及各地之间的运输费用，如何制定一个运输方案，使总的运输量费用最小，这类的问题称
为运输问题。假设有m 个产地，记为A 1、A 2….A m ,生产某种物资，可供应的产量分别为a 1,a 2….a m ,有n 个销地，记为B 1、B 2…B n ,其需求量分别为b 1、b 2…b n ,假设在供需平衡的情况下，即∑=m i ai 1=∑=n j bj 1 ，从第i 个产地到j 个销地的单位物资的运费为c ij ，在满足各地需求的前提下，求运费最小的方案。 设x ij （i=1、2…m,j=1、2…n ）为第i 个产地到第j 个销地的运量，则运输问题的数学模型为 Min Z = ∑=m i 1∑=n j cijxij 1
实验三 线性规划 程序： linprog c=[-0.4 -0.28 -0.32 -0.72 -0.64 -0.6]; A=[0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08]; b=[850;700;100;900]; Aeq=[]; beq=[]; vlb=[0;0;0;0;0;0]; vub=[]; [x,fval]=linprog(c,A,b,Aeq,beq,vlb,vub) Exam5: function f=fun3(x); f=-x(1)-2*x(2)+(1/2)*x(1)^2+(1/2)*x(2)^2 实验目的 2、掌握用数学软件包求解线性规划问题。 1、了解线性规划的基本内容。 例1 max 6543216.064.072.032.028.04.0x x x x x x z +++++= 85003.003.003.001.001.001.0..654321≤+++++x x x x x x t s 70005.002.041≤+x x 10005.002.052≤+x x 90008.003.063≤+x x 6,2,10 =≥j x j
x0=[1;1]; A=[2 3 ;1 4]; b=[6;5]; Aeq=[];beq=[]; VLB=[0;0]; VUB=[]; [x,fval]=fmincon('fun3',x0,A,b,Aeq,beq,VLB,VUB) 书 求下列非线性规划 2221232212322 1232 12223123min 8020 ..2023,,0x x x x x x x x x s t x x x x x x x +++?-+≥?++≤??--+=??+=? ?≥? 在Matlab 2013软件中输入如下程序： （i ）编写M 文件fun1.m 定义目标函数 function f=fun1(x); f=sum(x.^2)+8; （ii ）编写M 文件fun2.m 定义非线性约束条件 function [g,h]=fun2(x); g=[-x(1)^2+x(2)-x(3)^2 x(1)+x(2)^2+x(3)^3-20]; %非线性不等式约束 h=[-x(1)-x(2)^2+2 x(2)+2*x(3)^2-3]; %非线性等式约束 （iii ）编写主程序文件example2.m 如下： options=optimset('largescale','off'); [x,y]=fmincon('fun1',rand(3,1),[],[],[],[],zeros(3,1),[], ... 'fun2', options) 就可以求得当1230.5522 1.2033,,0.9478x x x ===时，最小值y =10.6511。 4. 选修课的策略 决策目标为选修的课程总数最少，即 921min x x x +++ 约束条件： (1) 满足课程要求：（至少２门数学课程，３门运筹学课程和２门计算机课程）
运用线性规划对运输问题研究 班级：金融103班姓名：王纬福学号：5400210132摘要：由于企业选择运输路线或运输工具不合理而导致物流运输成本不能最小化的问题普遍存在而管理运筹学却能很好的解决此问题。通过科学的方法对问题进行具体化再建立数学模型并求解，就能找到运输成本最小的运输组合。 关键词：物流运输成本、输成本、管理运筹学、WinQSB2.0、线性规划 一、引言 日常生活中，人们经常需要将某些物品由一个空间位置移动到另一个空间位置，这就产生了运输。如何判定科学的运输方案，使运输所需的总费用最少，就是管理运筹学在运输问题上的运用需要解决的问题。 运输问题是一类应用广泛的特殊的线性规划问题，在线性规划的一般理论和单纯形法出现以前，康托洛维奇（L.V.Kant）和希奇柯克（F.L.Hitchcock）已经研究了运输问题。所以，运输问题又有“康-希问题”之称。对于运输问题（Transportation Problem TP）当然可用前面所讲的单纯形法求解，但由于该问题本身的特殊性，我们可以找到比标准单纯形法更简单有效的专门方法，从而节约计算时间和费用。主要是因为它们的约束方程组的系数矩阵具有特殊结构，使得这类问题的求解方法比常规的单纯形法要更为简便。 一、研究现状 运输问题的研究较多，并且几乎所有的线性规划书中都有论述。遗憾的是一些书中所建立的数学模型都不够全面和系统的。但是也有一些模型是严谨的没有漏洞和缺陷，并且很容易在此基础上修改或添加一些其他约束条件便于在实际工程中进行应用。管理运筹学在运输问题上的研究较为深入、全面、系统。对于计算机软件的引用也很前言，winQSB2.0对于普通甚至深入研究运输问题就已经是简单而又使用、耐用、好用的了。现在相关的杂志、期刊都越来越多关于管理运筹学，关于运输问题的文章论文初版，越来越得到重视。 二、文献回顾 随着物流行业和企业对物流运输要求的不断提高，企业的面临着更大的市场竞争，其运输活动在企业不断发展过程中，面临着越来越大难度的运输组合的选择决策问题。如何正确解决这个问题，是企业能够持续经营和发展不可忽视和必须面对的。这个问题同时也引起了企业界、学术界等社会各界的广泛关注。运输问题的实质是企业与运输组合的经济性问题，成功的企业通常都会面临如何选取最佳运输组合或运输路线这样一个重要问题，即以企业运输成本最小化作为确定最佳运输组合或运输路线的原落脚点。 四、案例分析 例：某公司下设生产同类产品的加工厂A1、A2、A3，生产的产品由4个销售点B1、B2、B3、B4出售。各工厂的生产量、各销售点的销量以及各工厂到各销售点的单位运价如下表：