§3.6优化问题与规划模型
与最大、最小、最长、最短等等有关的问题都是优化问题.
解决优化问题形成管理科学的数学方法：运筹学•运筹学主要分支：（非）线性规划、动态
规划、图与网络分析、存贮学、排队伦、对策论、决策论.
6.1 线性规划
1939年苏联数学家康托洛维奇发表《生产组织与计划中的数学问题》1947年美国数学家乔治•丹契克、冯•诺伊曼提出线性规划的一般模型及理论.
1.问题
例1作物种植安排
一个农场有50亩土地，20个劳动力，计划种蔬菜,棉花和水稻.种植这三种农作物每亩地分别需要劳动力1/21/3 1/4,预计每亩产值分别为110元，75元,60元.如何规划经营使经济效益最大・
分析：以取得最高的产值的方式达到收益最大的目标.
1.求什么？分别安排多少亩地种蔬菜、棉花、水稻？X’亩、X：亩、X3亩2.优化什么？产值最大maxf =10x1+75x2+60x3
3.限制条件？田地总量X1+X2+X3S50劳力总数l/2xl+l/3x2+l/4x3<20模型I:设决策变量：种植蔬菜X1亩，棉花氐亩，水稻X3亩，
求目标函数f=110xi+75x2+60x3
在约束条件xx+x:+x3<501/2X】+1/3X：+1/4X3S20 下的最大值
规划问题：求目标函数在约束条件下的最值，规划问题包含3个组成要素：决策变量、目标函数、约束条件.
规划问题. 2.线性规划问题求解方法当LI标函数和约束条件都是决策变量的线性函数时，称为线性规划问题，否则称为非线性
称满足约束条件的向量为可行解,称可行解的集合为可行域，称使目标函数达最值的可行解为最优解.
命题1线性规划问题的可行解集是凸集.
因为可行解集山线性不等式组的解构成•两个变量的线性规划问题的可行解集是平面上的凸多边形.
命题2线性规划问题的最优解一定在可行解集的某个极点上达到.
图解法：解两个变量的线性规划问题，在平面上画出可行域，计算L1标函数在各极点处的值，经比较后，取最值点为最优解.
命题3当两个变量的线性规划问题的L1标函数取不同的口标值时，构成一族平行直线，目标值的大小描述了直线离原点的远近.
于是穿过可行域的U标直线组中最远离（或接近）原点的直线所穿过的凸多边形的顶点即为取的极值的极点一最优解.
单纯形法：通过确定约束方程组的基本解，并计算相应LI标函数值，在可行解集的极点中搜寻最优解.
正则模型：
决策变量:xnx2,•••, xn.U标函数：Z^xXi+CzX：+•••+crxn・
模型的标准化
1°.引入松弛变量将不等式约束变为等式约束.
若有 aiiXi+---+ainXr.^bi,则引入 0,使得 若有
aiiXi+---+axnXn+Xn-i =bxxn-j
3X1+…+5x36,则引入Xr-j^ 0,使得 且有 二bj・
Z=c1x1+c2x2+• • • +caxn+0xa-i+• • • +0XE
2°.将LI 标函数的优化变为U 标函数的极大化. 题变为max Z'・
3°.引入人工变量，使得所有变量均为非负.若 0 和x/ ' $0,令XF x/ - xj ',则可使得问题的全部变量均非负. 标准化模型
求变量xn x2,…，xn,
若求minZ,令Z'二-Z,则问
x,没有非负的条件,则引入x/M
max Z = 6Xi+…+ CnXn, s・匕 a11x1+---+ alaxR= bn
&収+…+ amxn= ba,
Xi 0, • • • X" 0,
定义：若代数方程/二B'的矗向量'有n-m 个分量为零，其余m 个分量对应A 的m 个线性无关
列，则称该解向量为方程组的一个基本解•在一个线性规划问题中，如 果一个可行解也是约
束方程组的基本解，则称之为基本可行解.
命题4 一个向量x 是线性规划问题可行解集的一个极点，当且仅当它是约束方 程的一个基本
可行解.
题的单纯形方法，改进单纯形方法等.按这些计算方法编制程序，产生了 专门解优化问题的软件Lindo、Lingo・于是寻找取得极值的凸集极点的儿何问题变成了求代数方程基本解的问题，形成了 解优化问
用Mat lab 求解：
标准的线性规划的模型：
min f=cTx
s. t・ Ax < b
Alx=bl
LB < x < UB
Mat lab 求解程序:[x, f]=l inprog (c, A, b, Al, bl, LB, UB)还有软件Excel 也可应用于解优化问题.
3 对偶问题
例1 作物种植安排
一个农场有50 亩土地，20 个劳动力，计划种蔬菜,棉花和水稻.种植这三种农 作物每亩地分别需要劳动力1/2 1/3 1/4,预计每亩产值分别为110 元，75 元, 60 元.如何规划经营使经济效益最大・
分析：以最经济的投入达到收益最大的目标.
(或者说以直接出售土地和劳动力的方式达到收益最大的U 标・) 1 求什么？ 土地成本价格刃劳动力成本价格y：
2・优化什么？成本价格最低Ming=50yi+20y2
3・限制条件？
蔬菜的市场价yx+l/2y2＞
棉花的市场价110
水稻的市场价yi+l/3y：＞
模型II・75yi+l/4y：
设决策变量：对单位土地和对单位劳力投入成本价格分别为yx兀＞60
求目标函数g^oOy^Oy：
在约束条件yi+l/2y：：nil0yi+l/3y&75yi+l/4yQ60 下的最小值.
设 | A | 是 | m | x | n | 矩 阵， |
c是nxl向量，b是mxl向量x是nx 1向量，y是1x m向量问题：maxf=cTxs.t. Ax < b Xi>0, i=l, 2, n.
对偶问题：minf=ybs. t. yA > cy^O, i=l, 2, m.
对偶定理： 互为对偶的两个线性规划问题，若其中一个有有穷的最优解，则另一个也有有穷的最优解，且最优值相等.若两者之一有无界的最优解，则另一个没有可行解
模型III构成对偶问题.
模型I解得最优解(optimunsolution)XOPt=(300 20), 最大值f(x。』二4500模型II解得最优解y°』(10200), 最小值g(y』=4500・
模型
进型I给出了生产中的资源最优分配方案
值 :如果增加对土地和劳动力的投入，每种资源的单位投入增加会带来多少
产一II给岀了生产中资源的最低估价.
模
收入•也就是说，此时一个劳动力的估价为200元，而一亩土地估价为10 元.这种价格涉及由最优解y二(10, 200)可见，多耕一亩地增加10元收入，多一个劳动力增加200元到资源的有效利用，它不是市场价格，而是根据资源在生产中做出的贡献确定的估价，被称为“影子价格”・再进一步问，棉花价格提高到多少才值的生产？
由yx+l/3y：=10+200/3=76.6>75,(而其它两个约束条件是等式)可见，只有当棉花价格提高到76.6元时才值得生产・
4灵敬度分析
当线性规划问题中的常数发生变化(山于测量误差或具有多个取值可能)时，最优解是否会随之变化？
通常假定变化的常数是某参数的线性函数•讨论参数取值与最优解的关系的问题,被称为参数线性规划.
例如，当农作物的价格发生变化时，生产计划是否应马上随之改变？参见线性规划书籍将实际问题归结为线性规划模型是一个探索创造的过程.
线性规划模型的求解仍是计算数学的一个难题.
例2 供货问题
一家公司生产某种商品.现有n个客户，第j 个客户需要货物量至少为可在m 各不同地点设厂供货.在地区i设厂的费用为供货能力为h, 向第j个客户供应单位数量的货物费用为5・如何设厂与供货使总费用最小.模型：设决策变量：Xij为在地区i 向第j个客户供货数量， 在地区i设
厂，记Yi=1 ,否则记y£=0
求目标函数f=E：(EJCij Xu + yi di )
在约束条件二 x.j 二b” | 工j x£j -h£ y£ <0, | Xi^O, Yie{0, 1}下的最小 |
值
例3钢材截短
有一批钢材，每根长7.3M.现需做100套短钢材.每套包括长2.9M, 2. 1M, 1. 5M 的各一
根.至少用掉多少根钢材才能满足需要，并使得用料最省.
分析：可能的截法和余料
第］种7.3-(2. 9 X 2+1. 5)=0
第2种 7.3-(2. 9+2. 1 X 2)=0. 2
第3种 7.3-(2. 9+1.5 X 2)=1. 4
第4种 7.3-(2. 9+2. 1+1. 5)=0. 8
第5种 7.3-(2. 1 X 2+1.5 X 2)=0. 1
第6种 7.3-(2. 1 X 3)=1
第7种 7.3-(2. 1+1.5 X 3)=0. 7
第8科|7. 3-(1. 5 X 4)=1. 3
模型：设决策变量：按第i种方法截冬根钢材.
求目标函数 f=0. 2x：+l.4x3+0. 8x«+0・ lxs+xe+O. 7x；+l・3xs
在 约束条 件2xi+xm+x3+xi 二1002X：+XI+2X5+3X6+X；二100；+4XL100 XI+2X3+X4+2X5+3X
用 Mat lab 程序解得xOp.= (40, 20, 0, 0, 30, 0, 0, (实际上应要求X、为正整数•这是一个整数规划问题). 0) , f (x 和)二7 x20 , i=l,…，8 下的最小值
6.2整数规划
如果要求决策变量取整数，或部分取整数的线性规划问题， 称为整数规划.
例4・飞船装载问题
设有n种不同类型的科学仪器希望装在登月飞船上，令6>0表示每件第j类仪器的科学价值。a,>0表示每件第j类仪器的重量.每类仪器件数不限，但装载件数只能是整数.E船总载荷不得超过数b.设计一种方案，使得被装载仪器的科学价值之和最大•建模记£为第j类仪器的装载数.
求目标函数f 二2 6Xj 在约束条件Nd X 芒b,用分枝定界法求解整数规划问题
Xj为正整数，下的最大值.
基本思想:反复划分可行域并确定最优值的界限，将原问题不断地分枝为若干个子问 题，且缩小最优质的取值范围，直到求得最优解.
例：求U 标函数f=3x:+2x:在约束条件：2Xi+3x: <14, 2xj+x 2< 9, Xj x :为自然 数下的最大值.
用Lindo 软件求解整数规划 max 3xl+2x2 2xl+3x2〈=14 2xl+x2〈二9
end
gin xl |
|
ginx2
(或者用gin2 代替ginxlgin x2)
6.307规划
如果要求决策变量只取0或1的线性规划问题，称为0-1规划.
0-1约束不一定是山变量的性质决定的，更多地是山于逻辑关系引进问题的
例5背包问题
一个旅行者的背包最多只能装6kg物品.现有4件物品的重量和价值分别为2kg , 3 kg, 3 kg, 4 kg, 1元，1.2元，0.9元，1.1元.应携带那些物品使得携带物品的价值最大？建模：记X,为旅行者携带第j件物品的件数，取值只能为0或1.
求H标函数f二xj +1. 2x 2+0. 9x 3+1. lx 4 在约束条件2x1 +3x 2+3x 3+4x 4<6 下的最大值.
用Lingo 软件求解0-1规划
Model:
Max=xl+1.2*x2+0. 9*x3+l. I*x4o
2*xl+3*x2+3*x3+4*x4<=6o
@int(xl)o
@int (x2)o
@int (x3)o
@int (x4)o
end
例6集合覆盖问题
实际问题1某企业有5种产品要存放，有些不能存放在一起，有些能存放在一起的，由于组
合不同所需费用不同.求费用最低的储存方案.实际问题2 某航空公司在不同城市之间开辟了5 条航线，一个航班可以飞不同的航线组合，
不同组合成本不同，求开通所有航线且总费用最小的方案.抽象为集合覆盖问题：
设集合 | S 二{1,2,3,4,5} | 有一个子集类 |
(|>={{1,2},{1,3, 5), {2, 4,5}, {3}, {1}, {4,5}}其中每一个元素对应一个数6,称为该元素的费用.选e的一个子集使其覆盖s,且总费用最低.
即实际问题1中5种产品能存放在一起的各种组合为
©二{{1,2},{1,3, 5), {2, 4,5}, {3}, {1}, {4,5}}第i种组合的存储费用为6, 求这五种产品费用最低的储存方案.
模型：设决策变量：设厶匸©是S的一个覆盖(一种存储方案).当©的第i个元素属于厶（即第i种组合被采用）记XF1,否则XFO
求目标函数f二匚CiXi
在约束条件 Xi +x:+ x5>l Xi + x3>l出现）
（因为第2种产品只在第1,3个组合中
X：+ X|>1 X3 + X6 >lx：+X3 + X6 >1 Xi€ {0, 1} , 1=1, 2, •…6, 下的最小值. 6.4 多目标线性规划
H 标函数 fk=c a）T x k-l, 2, ..m,
s.t・Ax< b
Alx=bl
LB< x < UB
有最优解x（k>.记f（k）=f（xO））
整体评价法
minS二工（foo - c（Jx）/f（k>（使相对偏差最小）s.t・Ax< b
Alx=bl
LB< x < UB
有最佳妥协解x*.
习题：
1.资源分配，生产甲肥1吨，需要磷酸盐0.4吨，硝酸盐1.8吨，利润1万元。生产乙肥1吨,需要磷酸盐0.1吨，硝酸盐1.5吨，利润0.5万元.现有磷酸盐10吨,硝酸盐66吨，问甲、乙肥各生产多少吨获利最大？
营养配餐，甲种食品每10克含5个单位的蛋口，10个单位的铁，单价3元。乙种食品2.
每10克含7个单位的蛋白,4个单位的铁，单价2元.现需要一份食品，含有35个单位的蛋白,40个单位的铁，问如何配餐最省钱？