线性规划
1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》
1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论.
1. 问题
例1 作物种植安排
一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为 110元, 75元, 60元. 如何规划经营使经济效益最大.
分析:以取得最高的产值的方式达到收益最大的目标.
1. 求什么?分别安排多少亩地种蔬菜、棉花、水稻? x1 亩、 x2 亩、 x3 亩
2. 优化什么? 产值最大 max f=10x1+75x2+60x3
3. 限制条件? 田地总量 x1+x2+x3 £ 50 劳力总数 1/2x1+1/3x2+1/4x3 £ 20
模型 I : 设决策变量:种植蔬菜 x1 亩, 棉花 x2 亩, 水稻 x3 亩,
求目标函数 f=110x1+75x2+60x3
在约束条件x1+x2+x3 £ 50 1/2x1+1/3x2+1/4x3 £20 下的最大值
规划问题:求目标函数在约束条件下的最值,
规划问题包含3个组成要素: 决策变量、目标函数、约束条件。
当目标函数和约束条件都是决策变量的线性函数时,称为线性规划问题, 否则称为非线性规划问题。
2. 线性规划问题求解方法
称满足约束条件的向量为可行解,称可行解的集合为可行域,
称使目标函数达最值的可行解为最优解.
命题 1 线性规划问题的可行解集是凸集.
因为可行解集由线性不等式组的解构成。两个变量的线性规划问题的可行解集是平面上的凸多边形。
命题2 线性规划问题的最优解一定在可行解集的某个极点上达到.
图解法: 解两个变量的线性规划问题,在平面上画出可行域,计算目标函数在各极点处的值,经比较后,取最值点为最优解。
命题3 当两个变量的线性规划问题的目标函数取不同的目标值时,构成一族平行直线,目标值的大小描述了直线离原点的远近。
于是穿过可行域的目标直线组中最远离(或接近)原点的直线所穿过的凸多边形的顶点即为取的极值的极点—最优解。
单纯形法 : 通过确定约束方程组的基本解, 并计算相应目标函数值, 在可行解集的极点中搜寻最优解.
正则模型:
决策变量: x1,x2,…,xn. 目标函数: Z=c1x1+c2x2+…+cnxn.
约束条件: a11x1+…+a1nxn≤b1, …… am1x1+…+amnxn≤bm,
模型的标准化
10. 引入松弛变量将不等式约束变为等式约束.
若有 ai1x1+…+ainxn≤bi, 则引入 xn+i≥ 0, 使得 ai1x1+…+ainxn+ xn+i =bi
若有 aj1x1+…+ajnxn≥bj, 则引入 xn+j≥ 0, 使得 aj1x1+…+ajnxn- xn+j =bj.
且有 Z=c1x1+c2x2+…+cnxn+0xn+1+…+0xn+m.
20. 将目标函数的优化变为目标函数的极大化. 若求 min Z, 令 Z’=–Z, 则问题变为 max Z’ .
30. 引入人工变量,使得所有变量均为非负. 若 xi 没有非负的条件,则引入 xi’≥ 0 和 xi’’≥0, 令 xi= xi’– xi’’, 则可使得问题的全部变量均非负.
标准化模型
求变量 x1, x2,…, xn,
max Z = c1x1+…+ cnxn,
s. t. a11x1+…+ a1nxn= b1,
……
am1x1+…+ amnxn= bm,
x1 ≥ 0,…, xn ≥ 0,
定义: 若代数方程AX=B的解向量有n-m个分量为零, 其余m个分量对应A的m个线性无关列, 则称该解向量为方程组的一个基本解.在一个线性规划问题中, 如果一个可行解也是约束方程组的基本解, 则称之为基本可行解.
命题 4 一个向量 x 是线性规划问题可行解集的一个极点, 当且仅当它是约束方程的一个基本可行解。
于是寻找取得极值的凸集极点的几何问题变成了求代数方程基本解的问题,形成了解优化问题的单纯形方法,改进单纯形方法等。按这些计算方法编制程序,产生了Matlab优化工具箱和专门解优化问题的软件 Lindo、Lingo 。
用Matlab求解:
标准的线性规划的模型:
min f=cTx
s.t. Ax £ b
A1x=b1
LB £ x £ UB
Matlab求解程序: [x,f]=linprog(c,A,b,A1,b1,LB,UB)
还有软件Excel 也可应用于解优化问题。
一个农场有50亩土地, 20个劳动力, 计划种蔬菜,棉花和水稻. 种植这三种农作物每亩地分别需要劳动力 1/2 1/3 1/4, 预计每亩产值分别为 110元, 75元, 60元. 如何规划经营使经济效益最大.
分析:以最经济的投入达到收益最大的目标.
(或者说以直接出售土地和劳动力的方式达到收益最大的目标.)
1 求什么?土地成本价格 y1 劳动力成本价格 y2
2. 优化什么? 成本价格最低 Min g=50y1+20y2
3. 限制条件?
蔬菜的市场价 y1+1/2y2 ³ 110
棉花的市场价 y1+1/3y2 ³ 75
水稻的市场价 y1+1/4y2 ³ 60
设决策变量: 对单位土地和对单位劳力投入成本价格分别为 y1 y2
求目标函数 g=50y1+20y2
在约束条件 y1+1/2y2 ³ 110 y1+1/3y2 ³ 75 y1+1/4y2 ³ 60 下的最小值.
设 A 是m ´ n 矩阵,
c 是 n ´ 1向量,b 是 m ´ 1向量
x是 n ´ 1向量, y是1 ´ m 向量
问题: max f=cTx s.t. Ax £ b xi³0, i=1,2,¼,n.
对偶问题: min f=yb s.t. yA ³ c yi³0, i=1,2,¼,m.
对偶定理: 互为对偶的两个线性规划问题, 若其中一个有有穷的最优解, 则另一个也有有穷的最优解, 且最优值相等. 若两者之一有无界的最优解, 则另一个没有可行解
模型 I II构成对偶问题.
模型 I 解得最优解(optimun solution) Xopt=(30 0 20), 最大值 f(xopt)=4500
模型 II 解得最优解 yopt=(10 200), 最小值 g(yopt)=4500.
模型I 给出了生产中的资源最优分配方案
模型 II 给出了生产中资源的最低估价.
进一步问:如果增加对土地和劳动力的投入,每种资源的单位投入增加会带来多少产值?
由最优解 y=(10,200) 可见, 多耕一亩地增加10元收入,多一个劳动力增加200元收入。也就是说, 此时一个劳动力的估价为200元,而一亩土地估价为10元.
这种价格涉及到资源的有效利用, 它不是市场价格, 而是根据资源在生产中做出的贡献确定的估价, 被称为“影子价格”.
再进一步问,棉花价格提高到多少才值的生产?
由 y1+1/3y2=10+200/3=76.6>75, (而其它两个约束条件是等式)可见,只有当棉花价格提高到 76.6元时才值得生产.