第一章 线性规划模型.ppt

1第一章线性规划2§1线性规划的一般模型例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制,如下表:问题:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多?3§1线性规划的一般模型例1. 某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制,如下表:问题:工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多?线性规划模型:目标函数:Max z = 50 x1 + 100 x2约束条件:. x1 + x2 ≤ 300 2 x1 + x2≤ 400 x2 ≤ 250 x1 , x2≥ 04线性规划的组成要素:目标函数Max F 或Min . (subject to) ,了解解题的目标和条件;(x1 ,x2 ,…,xn),每一组值表示一个方案;,确定最大化或最小化目标;?一般形式目标函数:Max (Min)z = c1 x1 + c2 x2 + …+ cnxn约束条件:. a11 x1 + a12 x2 + …+ a1nxn≤(=, ≥)b1a21 x1 + a22 x2 + …+ a2nxn≤(=, ≥)b2…………am1 x1 + am2 x2 + …+ amnxn≤(=, ≥)bm x1 ,x2 ,…,xn≥ 0 6?对于只有两个决策变量的线性规划问题,可以在平面直角坐标系上作图表示线性规划问题的有关概念,并求解。下面通过例1详细讲解其方法。:Max z = 50 x1 + 100 x2 约束条件:. x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E)§2线性规划的图解法7(1)画出线性规划问题的可行域,如图所示。x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图18(2)目标函数z=50x1+100x2,当z取某一固定值时得到一条直线,直线上的每一点都具有相同的目标函数值,称之为“等值线”。平行移动等值线,当移动到B点时,z在可行域内实现了最大化。得到最优解:x1 = 50,x2 = 250,最优目标值z = 27500x1x2z=20000=50x1+100x2图2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE9?重要结论:–如果线性规划有最优解,则一定有一个可行域的顶点对应一个最优解;–无穷多个最优解。若将例1中的目标函数变为max z=50x1+50x2,则线段BC上的所有点都代表了最优解;–无界解。即可行域的范围延伸到无穷远,目标函数值可以无穷大或无穷小。一般来说,这说明模型有错,忽略了一些必要的约束条件;–无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x2≥1200,则可行域为空域,不存在满足约束条件的解,当然也就不存在最优解了。10§3线性规划的Matlab标准形式?线性规划的目标函数可以是求最大值,也可以是求最小值,约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便,Matlab中规定线性规划的标准形式为?其中c和x为n维列向量,b为m维列向量,A为m*n矩阵.?例如线性规划?的Matlab标准型为?? that suchminbAxxcxT? that suchmaxbAxxcxT???? that suchmin