4 线性规划方法.pdf

第5章 线性规划方法
 线性规划及其单纯形求解方法
 线性规划的对偶理论
 运输问题的求解方法:表上作业法
线性规划是运筹学中发展较快、应用较
广和比较成熟的一个分支 。它在实际应用中
日益广泛与深入,已经被广泛地应用到工业、
农业、商业与交通运输规划，工程技术的优
化设计，以及企业管理等各个领域。
在地理学领域，线性规划，作为传统的
计量地理学方法之一，是解决有关规划、决
策和系统优化问题的重要手段。
第1节 线性规划及其单纯形求解方法
线性规划的数学模型
线性规划的标准形式及方法
线性规划的解及其性质
线性规划问题的求解方法——单纯形法
应用实例: 农场种植计划模型
一、线性规划的数学模型
（一）线性规划模型之实例
线性规划研究的两类问题：
某项任务确定后，如何统筹安排，以最少的
人力、物力和财力去完成该项任务；
面对一定数量的人力 、物力和财力资源，如
何安排使用，使得完成的任务最多。它们都属于
最优规划的范畴。
以下为一些实例。
运输问题
假设某种物资（譬如煤炭、钢铁、石油
等）有m个产地，n个销地。第i产地的产量
为ai（i=1，2，…，m），第j 销地的需求量
为bj(j=1, 2，…，n)，它们满足产销平衡条件
m n
ai  b j 。
i11j
如果产地i到销地j的单位物资的运费为
Cij，要使总运费达到最小，可这样安排物资
的调运计划：
设xij表示由产地i供给销地j 的物资数量，则
上述问题可以表述为：
求一组实值变量xij(i=1，2，…，m；j=1，
2，…，n)，使其满足
 m
 xij b j ( j  1,2,, n)
 i1
 n
 xij  ai (i  1,2,, m)
 j1
x  0(i  1,2, , m; j  1,2, , n)
 ij  

而且使 mn
z  cij xij  min
ij11
资源利用问题
假设某地区拥有m种资源，其中，第i种资
源在规划期内的限额为bi(i=1，2，…，m)。这m
种资源可用来生产n种产品，其中，生产单位数
量的第j种产品需要消耗的第i种资源的数量为
aij(i=1，2，…，m；j=1,2, …,n)，第j种产品的单
价为cj(j=1，2， …，n)。试问如何安排这几种产
品的生产计划，才能使规划期内资源利用的总
产值达到最大?
设第j种产品的生产数量为xj(j=1，2，…，n)，
则上述资源问题就是：
求一 组实数变量xj(j=1 ，2，…，n)，使其
满足
 n
 aij x j  bi (i  1,2,,m)
 j1

x j  0 ( j  1,2,,n)
n
Z  c j x j  max
j1
合理下料问题
用某种原材料切割零件A1，A2, …,Am的毛
坯，现已设计出在一 块原材料上有B1，B2，…，
Bn种不同的下料方式，如用Bj下料方式可得Ai
种件种零件aij个，设Ai种件种零件的需要量为bi个。试问
应该怎样组织下料活动，才能使得既满足需要，
又节约原材料？
设采用Bj方式下料的原材料数为xj，则上述
问题可表示为：
求一组整数变量xj(j=1，2，…，n)，使得
 n
 aij x j  bi (i  1,2,,m)
 j1

x j  0 ( j  1,2,,n)
n
Z   x j  min
j1