优化问题与规划模型.doc

§3.6优化问题与规划模型
与最大、最小、最长、最短等等有关的问题都是优化问题。
解决优化问题形成管理科学的数学方法：运筹学。运筹学主要分支：（非）线性规划、动态规划、图与网络分析、存贮学、排队伦、对策论、决策论。
6.1线性规划
1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》
1947年美国数学家乔治.丹契克、冯.诺伊曼提出线性规划的一般模型及理论.
1.问题
例1作物种植安排
一个农场有50亩土地,20个劳动力,计划种蔬菜,棉花和水稻.种植这三种农作物每亩地分别需要劳动力1/21/31/4,预计每亩产值分别为110元,75元,60元.如何规划经营使经济效益最大.
分析：以取得最高的产值的方式达到收益最大的目标.
1.求什么？分别安排多少亩地种蔬菜、棉花、水稻？x1亩、x2亩、x3亩
2.优化什么？产值最大maxf=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501/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.将目标函数的优化变为目标函数的极大化.若求minZ,令Z’=–Z,则问题变为maxZ’.
30.引入人工变量,使得所有变量均为非负.若xi没有非负的条件,则引入xi’≥0和xi’’≥0,令xi=xi’–xi’’,则可使得问题的全部变量均非负.
标准化模型
求变量x1,x2,…,xn,
maxZ=c1x1+…+cnxn,
s.t.a11x1+…+a1nxn=b1,
……
am1x1+…+amnxn=bm,
x1≥0,…,xn≥0,
定义:若代数方程AX=B的解向量有n-m个分量为零,其余m个分量对应A的m个线性无关列,则称该解向量为方程组的一个基本解.在一个线性规划问题中,如果一个可行解也是约束方程组的基本解,则称之为基本可行解.

命题4一个向量x是线性规划问题可行解集的一个极点,当且仅当它是约束方程的一个基本可行解。
于是寻找取得极值的凸集极点的几何问题变成了求代数方程基本解的问题，形成了解优化问题的单纯形方法，改进单纯形方法等。按这些计算方法编制程序，产生了专门解优化问题的软件Lindo、Lingo。

用Matlab求解：
标准的线性规划的模型：
minf=cTx
s.t.Axb
A1x=b1
LBxUB
Matlab求解程序:[x,f]=linprog(c,A,b,A1,b1,LB,UB)
还有软件Excel也可应用于解优化问题。

3对偶问题
例1作物种植安排
一个农场有50亩土地,20个劳动力,计划种蔬菜,棉花和水稻.种植这三种农作物每亩地分别需要劳动力1/21/31/4,预计每亩产值分别为110元,75元,60元.如何规划经营使经济效益最大.

分析：以最经济的投入达到收益最大的目标.
（或者说以直接出售土地和劳动力的方式达