线性规划讲稿1.pdf

《线性规划讲稿1.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、规划数学简介1．什么是数学规划（数学规划研究什么）？ò任务一定如何安排才能节省资源（包括：人力、物力、资金、时间等等）或资源一定如何安排才能创造最大效益？ò多元函数极值问题，即f(x1,x2,?,xn)的极值问题。2．本课程主要讲授内容：线性规划非线性规划动态规划3．电力系统中的应用(与发展现状)电源规划电网规划机组组合设备检修等等1第一章：线性规划一、基本模型1．生产计划问题【例2－1】某工厂生产A、B两种产品。生产1tA产品可获利300元，生产1tB产品可获利400元。生表2－1每吨产品占用原料及设备时数产品

2、品种原料（t）占用设备（h）A32B61产1tA产品或B产品需要的原料数及占用设备时间如表2－1所示。工厂每天可得原料60t，设备每天至多工作16h。问每天生产A产品和B产品各多少吨，才能使该厂获得最大利益？解决策人可以控制的因素是第天生产A产品和B产品的产量，它们的每一组值就是一个生产方案。设每天生产A产品和B产品分别为x1、x2t。依题意，该厂每天获利可用x1、x2的函数f来表示，即f(x1,x2)=300x1+400x22显然，产量x1、x2越大，所获得利润也越大，但x1和x2的取值要受到原料及设备时间等资

3、源的限制。如对于原料，生产A和B两种产品消耗的原料为3x1+6x2不能超过原料的供应量，即必须要满足下列条件：3x+6x≤60（原料限制）12同样地，对于设备可利用时间应该有：2x+x≤16（设备时间限制）12由于x1和x2是产品的产量，所以，x1和x2的取值应该非负，即有：x1≥0,x2≥0，从而问题化为求f(x1,x2)=300x1+400x2（2-1）在条件366xx+≤0⎫12⎪21xx+≤6⎬12⎪（2-2）xx≥≥0,0⎭12下的最大值问题。这样，原来的生产计划问题就转为数学问题：3⎧maxf(x,x

4、)=300x+400x1212⎪⎪3x1+6x2≤60(LP)⎨2x+x≤16⎪12⎪x,x≥0⎩12这样的问题就称为线性规划问题。2．基本概念（1）决策变量：决策者可以决定的变量（问题模型中的自变量）（2）目标函数：判别方案好坏的函数（3）约束条件：式（2-2）那样的线性等式或不等式３．建模举例（应用）（1）运输问题产地（工厂）：A1,A2，产量：＊，＊销地（工地）：B1,B2,B3ABc运费：产地i运到销地j每单位产品运费为：ij元4问：如何调运才能使运费最省？解：设产地Ai运到销地Bj的产品数量为xij，则

5、得模型：（大家一块写模型）（考虑产销不平衡情况）（１）营养问题（考虑合理假设问题）食品：A1,A2,?,An价格：C1,C2,?,Cn营养：单位食品Aj含营养素Bi为Cij单位，i=,2,1?,m;j=,2,1?,n营养素Bi最低需求量为bi，im=1,2,?,。如何采购（食用）食品，才能既满足营养需求，又花费最少？解：设食用Aj为xj单位。则得模型：5n⎧⎪min∑cjxj⎪j=1n⎪⎪⎨∑cijxj≥bi,i=,2,1?,m⎪j=1⎪x≥,0j=,2,1?,nj⎪⎪⎩问题：能吃下吗？能吃饱吗？爱不爱吃？卖不卖

6、你？做法？等等。（带副产品的生产计划问题）（下料问题）（连续投资问题）４．线性规划问题的一般形式n⎧⎪max(min)(,fxx12,?,xnj)=∑cxj⎪j=1⎪()LPaxax⎨++?+≤ax(,)≥=b1111221nn1⎪??⎪⎪⎩axax++?+≤ax(,)≥=bmm1122mnnm二、线性规划的标准形式１．线性规划问题的标准形式6n⎧⎪max(,fxx12,?,xnj)=∑cxj⎪j=1⎪axax++?+=axb1111221nn1⎪(LP)⎨????⎪axax++?+=axb⎪mm1122mnnm

7、⎪xx,,,?x≥012n⎪⎩特点：（1）都是求目标函数最大值问题；（2）约束条件均为等式；（3）全部变量均为非负。２．化标准型及原问题和标准形式问题解之间的关系（1）若要求目标函数为最小值，即minf，可令g=−f，则以为目标函数的最小值问题与以fg为目标函数的最大值问题在同样的约束条件下有完全相同的最优解，且minf=−maxg。7n（2）若∑axijj≤bi，则引进xn+1≥0，使得j=1n∑aijxj+xn+1=bij=1并称xn+1为松驰变量。n（3）若∑axbijj≥i，则引进xn+1≥0，使j=1n

8、∑aijxj−xn+1=bij=1x也称为松驰变量。n+1（4）若某个xi无非负限制，可令12x=x−xiii（考虑若某个xi≥h，怎么办？）经过上述步骤，总可将所给线性规划问题化为标准形式，当然标准形式规划问题中的决策变量增加了，大家必须清楚新问题与原问题解之间的关系。二、线性规划问题的图解法１．可行解，可行域，最优解概念8２．图解法步骤：例2-２以生产计划问题为例。（