1、决策与计划解:解:(1)决策决策1 1S1S1S2S2决策决策2 2S3S3S4S4建大厂建大厂-700-700建小厂建小厂-300-300销路好销路好0.70.7销路好销路好销路好销路好 0.7 0.7销路好销路好销路差销路差0.30.3销路差销路差0.30.321021021021090906060-40-40前三年前三年后七年后七年扩建扩建-400不扩建不扩建(2)145789623606060609090-40-40210210-40-40210210-40-40建大厂建大厂 建小厂建小厂 销路好销路好0.70.7 销路差销路差0.30.3 销路好销路好0.70.7 销路差销路差0.3
2、0.3 销路好销路好0.90.9 销路差销路差0.10.1 扩建扩建 不扩建不扩建 销路好销路好0.90.9 销路差销路差0.10.1 销路好销路好0.90.9 销路差销路差0.10.1 3 3年内年内 7 7年内年内 1227.51227.51247.51247.512951295-280-280895895420420895895609609例子例子 可选地有可选地有3个(个(A、B、C),其固定成本,其固定成本分别为:分别为:30、60、110万元;单位变动成本万元;单位变动成本分别为:分别为:750、450、250元,估计年销售元,估计年销售量为量为2000个。售价相同。个。售价相同。
3、问题问题:选择在哪个地选择在哪个地 方建厂?方建厂?如果年销售量在如果年销售量在3000个个,则选择何地则选择何地?ABC100025003060110选址决策选址决策:下表列出了四个可能成为工厂所下表列出了四个可能成为工厂所在地的地点的固定成本和可变成本,在地的地点的固定成本和可变成本,假定售假定售价、销量相同。价、销量相同。地址地址每年的固定成本每年的固定成本/美元美元每单位的可变成本每单位的可变成本/美元美元ABCD 250000 100000 150000 20000011302035a.在一张图上绘出各地点的总成本线在一张图上绘出各地点的总成本线b.指出使每个被选地点产出最优的区间(
4、即总成本最低)指出使每个被选地点产出最优的区间(即总成本最低)c.如果要选择的地点预期每年产量为如果要选择的地点预期每年产量为8000个单位,哪一地的总成本个单位,哪一地的总成本最低?最低?DBCAB superiorC superiorA superior b.图中显示出了各个供选择地点的总成本最低时的区间。请注意D地从未优于其它任何一地。因此可以从B线和C线的交点以及A线和C线交点所得到的产出水平求出确切的区间。为了得到这点,使他们的总成本公式相等,求Q,即得到他们最优产出水平的界限。对于对于B和和C来说:来说:(B)(C)100000+30Q=150000+20Q解之,解之,Q=5000
5、 单位单位/年年对于对于C和和A来说:来说:(C)(A)150000+20Q=250000+11Q解之,解之,Q=11111 单位单位/年年 C.从这张图中你可看出,每年产出从这张图中你可看出,每年产出8000单位,地单位,地点点C的成本总额最低。的成本总额最低。DBCAB superiorC superiorA superior某公司计划建一新厂,初步选择A、B、C三个候选厂址,有关资料如下:项目年固定成本/元年生产能力/台单位产品变动成本/元单价/(元/台)厂址A250000350002035厂址B350000300001835厂址C200000280002535问题(1)绘制总成本线。(
6、2)指出各方案产出的最佳区间。(3)确定预期产量25000台的最优方案。运筹学线性规划一、问题的提出一、问题的提出12,I,IIxx 设设分分别别表表示示计计划划生生产产产产品品的的数数量量,称称它它们们为为决决策策变变量量。12121228 416 412,;xxxxxx生生产产的的数数量量多多少少,受受资资源源拥拥有有量量的的限限制制,这这是是约约束束条条件件。即即120,xx生生产产的的产产品品不不能能是是负负值值,即即如如何何安安排排生生产产,使使利利润润最最大大,这这是是目目标标。一、问题的提出1212121223284164120:max,zxxxxxxxx目目标标函函数数约约束束
7、条条件件例例1:生产计划问题。某企业在计划期内计划生产甲、乙两种产生产计划问题。某企业在计划期内计划生产甲、乙两种产品。按工艺资料规定,每件产品甲需要消耗材料品。按工艺资料规定,每件产品甲需要消耗材料A 2公斤,消耗公斤,消耗材料材料B 1公斤,每件产品乙需要消耗材料公斤,每件产品乙需要消耗材料A 1公斤,消耗材料公斤,消耗材料B 1.5公斤。已知在计划期内可供材料分别为公斤。已知在计划期内可供材料分别为A 40、B 30公斤;每公斤;每生产一件甲、乙两产品,企业可获得利润分别为生产一件甲、乙两产品,企业可获得利润分别为40、30元,如元,如表表11所示。假定市场需求无限制。企业决策者应如何安
8、排生所示。假定市场需求无限制。企业决策者应如何安排生产计划,使企业在计划期内总的利润收入最大。产计划,使企业在计划期内总的利润收入最大。12max300400Zxx【解】设【解】设x1、x2分别为甲、乙产品的产量,数学模型为:分别为甲、乙产品的产量,数学模型为:产品产品 资源资源 甲甲 乙乙现有资现有资源源材料材料A2140材料材料B11.530利润(元利润(元/件)件)3004001212122401.5300,0 xxxxxx表表1-1x1x2O1020304010203040(300,400)(15,10)最优解最优解X=(15,10)最优值最优值Z=850040221xx305.121
9、xx0,0305.1402212121xxxxxx12max300400Zxx246x1x2246最优解最优解X=(3,1)最优值最优值Z=5(3,1)006346321212121xxxxxxxx、min Z=x1+2x2(1,2)246x1x2246X(2)(3,1)X(1)(1,3)(5,5)006346321212121xxxxxxxx、min Z=5x1+5x2有无穷多个最优解有无穷多个最优解即具有多重解即具有多重解,通解为通解为 01,)1()2()1(XXX 当当=0.5时时=(x1,x2)=0.5(1,3)+0.5(3,1)=(2,2)246x1x2246(1,2)006346
10、321212121xxxxxxxx、无界解无界解(无最优解无最优解)max Z=x1+2x2x1x2O102030401020304050500,050305.140221212121xxxxxxxx无可行解无可行解即无最优解即无最优解max Z=10 x1+4x2 这个问题可以用下面的这个问题可以用下面的数学模型来描述。设计划数学模型来描述。设计划期内产品期内产品、的产量分的产量分别为别为x1,x2,可获利润用可获利润用z表示,则有:表示,则有:例例2 某工厂在计划期内要安排生产某工厂在计划期内要安排生产、两种产两种产品,已知生产单位产品所需的设备台时和原料品,已知生产单位产品所需的设备台时
11、和原料A、B的消耗量如下表。的消耗量如下表。该工厂该工厂每生产一件产品每生产一件产品可获利可获利2元,每生产一件产品元,每生产一件产品可可获利获利3元,问应如何安排生元,问应如何安排生产计划能使该厂获利最多?产计划能使该厂获利最多?8 16 12 1 2 4 0 0 4设 备原料A原料B拥有量 max z=2x1+3x2x1+2x284x1 16 4x212x1,x20 对于对于只有两个变量只有两个变量的线性规划问题,可以在二维直的线性规划问题,可以在二维直角坐标平面上作图表示线性规划问题的有关概念,并角坐标平面上作图表示线性规划问题的有关概念,并求解。图解法求解线性规划问题的步骤如下:求解。
12、图解法求解线性规划问题的步骤如下:分别取决策变量分别取决策变量x1,x2 为坐标向量建立直角坐标系为坐标向量建立直角坐标系;对每个约束对每个约束(包括非负约束包括非负约束)条件,先取其等式在坐条件,先取其等式在坐标系中作出直线,通过判断确定不等式所决定的半平标系中作出直线,通过判断确定不等式所决定的半平面。各约束半平面交出来的区域面。各约束半平面交出来的区域(存在或不存在存在或不存在),若若存在,其中的点表示的解称为此线性规划的存在,其中的点表示的解称为此线性规划的可行解可行解。这些符合约束限制的点集合,称为这些符合约束限制的点集合,称为可行集或可行域可行集或可行域。进行进行;否则该线性规划问
13、题无可行解。;否则该线性规划问题无可行解。图解法图解法 (3)任意给定目标函数一个值作一条目标函数)任意给定目标函数一个值作一条目标函数的等值线,并确定该等值线平移后值增加的方向,的等值线,并确定该等值线平移后值增加的方向,平移此目标函数的等值线,使其达到既与可行域平移此目标函数的等值线,使其达到既与可行域有交点又不可能使值再增加的位置(有时交于无有交点又不可能使值再增加的位置(有时交于无穷远处,此时称穷远处,此时称无界解无界解)。若有交点时,此目标)。若有交点时,此目标函数等值线与可行域的交点即最优解(一个或多函数等值线与可行域的交点即最优解(一个或多个),此目标函数的值即最优值。个),此目
14、标函数的值即最优值。图解法简单、直观图解法简单、直观,便于初学者了解线性规划便于初学者了解线性规划基本原理和几何意义基本原理和几何意义;唯一最优解无穷多最优解x1x2x1x2 解无界无可行解 线性规划问题线性规划问题如果有最优解如果有最优解,则最则最优解一定在可行域优解一定在可行域的边界上取得的边界上取得,特别特别地地,一定可在可行域一定可在可行域的顶点上取得的顶点上取得.max z=2x1+3x2 x1+2x28 4x1 16 4x212 x1,x20图解法图解法综上,得到以下结论:线性规划问题的解具有四种类型:唯一最优线性规划问题的解具有四种类型:唯一最优解、无穷多最优解、无界解、无可行解。解、无穷多最优解、无界解、无可行解。线性规划问题如果有最优解,则最优解一定线性规划问题如果有最优解,则最优解一定在可行域的边界上取得,特别地,一定可以在可行域的边界上取得,特别地,一定可以在可行域的顶点处取得在可行域的顶点处取得。图解法图解法此课件下载可自行编辑修改,仅供参考!此课件下载可自行编辑修改,仅供参考!感谢您的支持,我们努力做得更好!谢谢感谢您的支持,我们努力做得更好!谢谢