实用运筹学线性规划实用教案

1、本章本章(bn zhn)内容要点内容要点线性规划问题线性规划问题(wnt)及其数学模型；及其数学模型；线性规划的电子表格建模；线性规划的电子表格建模；线性规划的多解分析。线性规划的多解分析。第1页/共18页第一页，共18页。本章本章(bn zhn)内内容容 1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型 1.2 1.2 线性规划问题的图解法线性规划问题的图解法 1.3 1.3 用用Excel“Excel“规划求解规划求解”功能求解线性规划问题功能求解线性规划问题 1.4 1.4 线性规划问题求解的几种可能线性规划问题求解的几种可能(knng)(knng)结结果果第2页/共18

2、页第二页，共18页。本章本章(bn zhn)主要主要内容框架图内容框架图E x c e l决 策 变 量数 学 模 型 三 要 素目 标 函 数约 束 条 件图 解 法线 性 规 划求 解软 件 求 解唯 一 解无 穷 多 解求 解 的 几 种 可 能 结 果无 解可 行 域 无 界第3页/共18页第三页，共18页。1.1 1.1 线性规划线性规划(xin xn(xin xn u u hu)hu)问题及其数学模型问题及其数学模型 例例1.1 1.1 某工厂要生产两种新产品：门和窗。某工厂要生产两种新产品：门和窗。 经测算，每生产一扇门需要在车间经测算，每生产一扇门需要在车间1 1加工加工1 1

3、小时、小时、在车间在车间3 3加工加工3 3小时；每生产一扇窗需要在车间小时；每生产一扇窗需要在车间2 2和车间和车间3 3各加工各加工2 2小时。而车间小时。而车间1 1每周可用于生产每周可用于生产这两种新产品的时间为这两种新产品的时间为4 4小时、车间小时、车间2 2为为1212小时、小时、车间车间3 3为为1818小时。小时。 已知每扇门的利润为已知每扇门的利润为300300元，元，每扇窗的利润为每扇窗的利润为500500元。而且根据经市场调查得元。而且根据经市场调查得到的该两种新产品的市场需求状况可以确定，到的该两种新产品的市场需求状况可以确定，按当前的定价可确保所有按当前的定价可确保

4、所有(suyu)(suyu)新产品均新产品均能销售出去。问该工厂如何安排这两种新产品能销售出去。问该工厂如何安排这两种新产品的生产计划，可使总利润最大？的生产计划，可使总利润最大？第4页/共18页第四页，共18页。1.1 1.1 线性规划线性规划(xin xn(xin xn u u hu)hu)问题及其数学模型问题及其数学模型 在该问题中，目标是总利润最大化，所要决策的变在该问题中，目标是总利润最大化，所要决策的变量是新产品的产量，而新产品的产量要受到三个车量是新产品的产量，而新产品的产量要受到三个车间每周可用于生产间每周可用于生产(shngchn)(shngchn)新产品时间的限新产品时间的

5、限制。因此，该问题可以用目标、决策变量和约束条制。因此，该问题可以用目标、决策变量和约束条件三个因素加以描述。实际上，所有的线性规划问件三个因素加以描述。实际上，所有的线性规划问题都包含这三个因素：题都包含这三个因素： （1 1）决策变量是问题中有待确定的未知因素。例）决策变量是问题中有待确定的未知因素。例如决定企业经营目标的各产品的产量等。如决定企业经营目标的各产品的产量等。 （2 2）目标函数是指对问题所追求的目标的数学描）目标函数是指对问题所追求的目标的数学描述。例如利润最大、成本最小等。述。例如利润最大、成本最小等。 （3 3）约束条件是指实现问题目标的限制因素。如）约束条件是指实现问

6、题目标的限制因素。如原材料供应量、生产原材料供应量、生产(shngchn)(shngchn)能力、市场需能力、市场需求等，它们限制了目标值所能到达的程度。求等，它们限制了目标值所能到达的程度。第5页/共18页第五页，共18页。1.1 1.1 线性规划线性规划(xin xn(xin xn u hu)u hu)问题及其数学模型问题及其数学模型解：例解：例1.11.1可用表可用表1 11 1表示表示(biosh)(biosh)。车间车间单位产品的生产时间（小时）单位产品的生产时间（小时）每周可获得的生产每周可获得的生产时间（小时）时间（小时）门门窗窗1 11 10 04 42 20 02 21212

7、3 33 32 21818单位利润（元）单位利润（元）300300500500第6页/共18页第六页，共18页。1.1 1.1 线性规划线性规划(xin xn(xin xn u hu)u hu)问题及其数学模型问题及其数学模型（1）决策(juc)变量本问题的决策(juc)变量是每周门和窗的产量。可设：x1为每周门的产量（扇）； x2为每周窗的产量（扇）。（2）目标函数本问题的目标是总利润最大。由于门和窗的单位利润分别为300元和500元，而其每周产量分别为x1和x2，所以每周总利润z为： z = 300 x1500 x2 （元）第7页/共18页第七页，共18页。1.1 1.1 线性规划线性规划

8、(xin xn(xin xn u hu)u hu)问题及其数学模型问题及其数学模型（3 3）约束条件）约束条件本问题的约束条件共有四个。本问题的约束条件共有四个。车间车间1 1每周可用工时每周可用工时(gngsh)(gngsh)限制：限制：x1 x1 4 4车间车间2 2每周可用工时每周可用工时(gngsh)(gngsh)限制：限制：2x2 2x2 12 12车间车间3 3每周可用工时每周可用工时(gngsh)(gngsh)限制：限制：3x1 +2x2 3x1 +2x2 18 18非负约束非负约束:x1 :x1 0, x2 0, x2 0 0第8页/共18页第八页，共18页。1.1 1.1 线

9、性规划线性规划(xin xn(xin xn u hu)u hu)问题及其数学模型问题及其数学模型例例1.11.1的线性规划的线性规划(xin xn(xin xn u hu)u hu)模型模型: :12121212Max z300500 4 212s.t. 3218, 0 xxxxxxxx这是一个典型的利润最大化的生产计这是一个典型的利润最大化的生产计划问题。其中，划问题。其中，“Max”是英文单词是英文单词“Maximize”的缩写，含义为的缩写，含义为“最最大化大化”；“s.t.”是是“subject to”的缩写，表的缩写，表示示“满足于满足于”。因此，上述模型。因此，上述模型的含义是：在

10、给定的条件限制下，求的含义是：在给定的条件限制下，求使得目标使得目标(mbio)函数函数z达到最大时达到最大时x1，x2的取值。的取值。第9页/共18页第九页，共18页。1.1 1.1 线性规划线性规划(xin xn(xin xn u hu)u hu)问题及其数学模型问题及其数学模型 本章讨论的问题均为线性规划问题。所谓本章讨论的问题均为线性规划问题。所谓“线性线性”规划，是指如果目标规划，是指如果目标函数是关于决策变量的线性函数，而且约束条件也都是关于决策变量的线函数是关于决策变量的线性函数，而且约束条件也都是关于决策变量的线性等式性等式(dngsh)(dngsh)或线性不等式或线性不等式(

11、dngsh)(dngsh)，则相应的规划问题就称，则相应的规划问题就称为线性规划问题。为线性规划问题。第10页/共18页第十页，共18页。1.1 1.1 线性规划线性规划(xin xn(xin xn u hu)u hu)问题及其数学模问题及其数学模型型例例1.2 1.2 某公司有某公司有100100万元的资金可供投资万元的资金可供投资(tu z)(tu z)。该公司有六个可选的投。该公司有六个可选的投资资(tu z)(tu z)项目，其各种数据如表项目，其各种数据如表1 12 2所示。所示。投资项目投资项目风险（风险（% %）红利（红利（% %）增长（增长（% %）信用度信用度1 118184

12、 422224 42 26 65 57 710103 310109 912122 24 44 47 78 810105 512126 615154 46 68 88 88 86 6第11页/共18页第十一页，共18页。1.1 1.1 线性规划线性规划(xin xn(xin xn u hu)u hu)问题及其数学模型问题及其数学模型 该公司该公司( (nn s) s)想达到的想达到的目标为：投资风险最小，每年红利目标为：投资风险最小，每年红利至少为至少为6.56.5万元，最低平均增长率万元，最低平均增长率为为12%12%，最低平均信用度为，最低平均信用度为7 7。请用。请用线性规划方法求解该问题

13、。线性规划方法求解该问题。第12页/共18页第十二页，共18页。1.1 1.1 线性规划线性规划(xin xn(xin xn u hu)u hu)问题及其数学模型问题及其数学模型解：解：（1 1）决策变量）决策变量 本问题本问题(wnt)(wnt)的决策变量是在每种投资项的决策变量是在每种投资项目上的投资额。设目上的投资额。设xixi为项目为项目i i的投资额（万元）的投资额（万元）（i=1,2,i=1,2,6,6）（2 2）目标函数）目标函数 本问题本问题(wnt)(wnt)的目标为总投资风险最小，的目标为总投资风险最小，即即123456Min z0.180.060.100.040.120.

14、08xxxxxx第13页/共18页第十三页，共18页。1.1 1.1 线性规划线性规划(xin xn(xin xn u hu)u hu)问题及其数学模型问题及其数学模型（3 3）约束条件）约束条件本问题共有五个约束条件本问题共有五个约束条件: : 各项目投资总和为各项目投资总和为100100万元万元; ; 每年每年(minin)(minin)红利至少为红利至少为6.56.5万元万元; ; 最低平均增长率为最低平均增长率为12%;12%; 最低平均信用度为最低平均信用度为7;7; 非负约束。非负约束。第14页/共18页第十四页，共18页。1.1 1.1 线性规划线性规划(xin xn(xin x

15、n u hu)u hu)问题及其数学模型问题及其数学模型得到得到(d do)(d do)的线性规划数的线性规划数学模型为：学模型为：12345612345612345612345Min z=0.180.060.100.040.120.08 1000.040.050.090.070.060.086.5 s.t. 0.220.070.120.080.150 xxxxxxxxxxxxxxxxxxxxxxx6123456123456.0812 4 10 2 10 4 6700 0 xxxxxxxxxxxxx，这是一个典型的成本（或风险）最小化问题。其中，这是一个典型的成本（或风险）最小化问题。其中，“

16、Min”“Min”是英文单词是英文单词“Minimize”“Minimize”的缩写，的缩写，含义为含义为“最小化最小化”。因此，上述模型的含义是：在给定的条件限制下，求使得。因此，上述模型的含义是：在给定的条件限制下，求使得(sh de)(sh de)目标函目标函数数z z达到最小时的达到最小时的x1,x2,x3,x4,x5,x6x1,x2,x3,x4,x5,x6取值取值 第15页/共18页第十五页，共18页。1.1 1.1 线性规划线性规划(xin xn(xin xn u hu)u hu)问题及其数学模型问题及其数学模型线性规划的模型结构线性规划的模型结构(jigu):(jigu):从以上

17、两个例子中可以归纳出线性从以上两个例子中可以归纳出线性规划问题的一般形式：对于一组决规划问题的一般形式：对于一组决策变量策变量x1,x2,x1,x2,xnxn，取，取112211112211211222221122Max(Min) z (1-1) ( , ) ( , ) s.t. (1-2)( , ) nnnnnnmmmnnmc xc xc xa xa xa xba xaxaxbaxaxaxb LLLML12 , , , 0 (1-3)nxxxL第16页/共18页第十六页，共18页。1.1 1.1 线性规划线性规划(xin xn(xin xn u hu)u hu)问题及其数学模型问题及其数学模型在线性规划模型中，也直接称在线性规划模型中，也直接称z z为目标函数为目标函数(hnsh)(hnsh)； 称称xj(j=1,2,xj(j=1,2,n),n)为决策变量；称为决策变量；称cj(j=1,2,cj(j=1,2,n) ,n) 为目标函为目标函数数 ( h n s h )( h n s h ) 系 数 或 价 值 系 数 或 费 用 系 数 ； 称系 数 或 价 值 系 数 或 费 用 系 数 ； 称 bi(i=1,2,bi(i=1,2,m),m)为函数为函数(hnsh)(hnsh)约束右端常数或简称右约束右端常数或简称右端值，也称资源常数