建模教程-线性规划课件.ppt

文档介绍：静态最优化问题
11-Feb-18
线性规划模型与求解
线性规划 Linear Programming
运筹学中应用最广泛的方法之一
运筹学的最基本的方法之一,网络规划,整数规划,目标规划和多目标规划都是以线性规划为基础的
解决稀缺资源最优分配的有效方法,使付出的费用最小或获得的收益最大
研究对象
有一定的人力、财力、资源条件下,如何合理安排使用,效益最高
某项任务确定后,如何安排人、财、物,使之最省
线性规划的数学模型
某家具厂木器车间生产木门与木窗两种产品。加工木门收入为56元/扇、加工木窗收入为30元/扇。生产一扇木门需要木工4小时、油漆工2小时;生产一扇木窗需要木工3小时、油漆工1小时。该车间每日可用木工总工时为120小时,油漆工总工时为50小时。问该车间应如何安排生产才能使每日收入最大。
设该车间每日安排生产木门x1扇、木窗x2扇。
Model:
Max z=56x1+30x2
4x1+3x2120
2x1+ x2  50
x1,x20
解得: X*=(15, 20)T, z*=1440
假若另有一个个体经营者,手中有一批木器家具生产订单。他想利用该木器车间的木工与油漆工来加工完成他的订单。他就要事先考虑付给该车间每个工时的价格。他可以构造一个数学模型来研究如何定价才能既使木器车间觉得有利可图从而愿意为他加工这批订单、又使自己所付的工时费用总数最少。
设w1,w2分别为付给木工和油漆工每个工时的价格。则该个体经营者的目标函数为每日所付工时总费用最小。
Min f=120w1+50w2
该个体经营者所付的价格不能太低,至少不能低于该车间生产木门、木窗时所得到的收入,否则该车间觉得无利可图就不会替他加工这批订单。因此,需满足
4w1+2w256
3w1+ w230
w1,w20
解得:W*=(2,24),f*=1440
Max z=56x1+30x2 Min f=120w1+50w2
4x1+3x2120 . 4w1+2w256
2x1+ x2  50 3w1+ w230
x1,x20 w1,w20
上面两个线性规划模型称为一对对偶的线性规划模型。
任一线性规划问题都有一对偶问题。
线性规划模型特点
决策变量:向量(x1… xn)T 决策人要考虑和控制的因素,一般非负
约束条件:线性等式或不等式
目标函数:Z=ƒ(x1 … xn) 线性式,求Z极大或极小