《实用运筹学线性规划幻灯片资料》由会员分享，可在线阅读，更多相关《实用运筹学线性规划幻灯片资料（18页珍藏版）》请在金锄头文库上搜索。
1、实用运筹学运用Excel建模和求解,第1章 线性规划,本章内容要点,线性规划问题及其数学模型； 线性规划的电子表格建模； 线性规划的多解分析。,本章内容,1.1 线性规划问题及其数学模型 1.2 线性规划问题的图解法 1.3 用Excel“规划求解”功能求解线性规划问题 1.4 线性规划问题求解的几种可能结果,1.1 线性规划问题及其数学模型,例1.1 某工厂要生产两种新产品：门和窗。 经测算，每生产一扇门需要在车间1加工1小时、在车间3加工3小时；每生产一扇窗需要在车间2和车间3各加工2小时。而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12小时、车间3为18小时。 已知每扇门的
2、利润为300元，每扇窗的利润为500元。而且根据经市场调查得到的该两种新产品的市场需求状况可以确定，按当前的定价可确保所有新产品均能销售出去。问该工厂如何安排这两种新产品的生产计划，可使总利润最大？,1.1 线性规划问题及其数学模型,在该问题中，目标是总利润最大化，所要决策的变量是新产品的产量，而新产品的产量要受到三个车间每周可用于生产新产品时间的限制。因此，该问题可以用目标、决策变量和约束条件三个因素加以描述。实际上，所有的线性规划问题都包含这三个因素： （1）决策变量是问题中有待确定的未知因素。例如决定企业经营目标的各产品的产量等。 （2）目标函数是指对问题所追求的目标的数学描述。例如利润
3、最大、成本最小等。 （3）约束条件是指实现问题目标的限制因素。如原材料供应量、生产能力、市场需求等，它们限制了目标值所能到达的程度。,1.1 线性规划问题及其数学模型,解：例1.1可用表11表示。,1.1 线性规划问题及其数学模型,（1）决策变量 本问题的决策变量是每周门和窗的产量。 可设：x1为每周门的产量（扇）； x2为每周窗的产量（扇）。 （2）目标函数 本问题的目标是总利润最大。由于门和窗的单位利润分别为300元和500元，而其每周产量分别为x1和x2，所以每周总利润z为： z = 300 x1500 x2 （元）,1.1 线性规划问题及其数学模型,（3）约束条件 本问题的约束条件共有
4、四个。 车间1每周可用工时限制：x1 4 车间2每周可用工时限制：2x2 12 车间3每周可用工时限制：3x1 +2x2 18 非负约束:x1 0, x2 0,1.1 线性规划问题及其数学模型,例1.1的线性规划模型:,这是一个典型的利润最大化的生产计划问题。其中，“Max”是英文单词“Maximize”的缩写，含义为“最大化”； “s.t.”是“subject to”的缩写，表示“满足于”。因此，上述模型的含义是：在给定的条件限制下，求使得目标函数z达到最大时x1，x2的取值。,1.1 线性规划问题及其数学模型,本章讨论的问题均为线性规划问题。所谓“线性”规划，是指如果目标函数是关于决策变量
5、的线性函数，而且约束条件也都是关于决策变量的线性等式或线性不等式，则相应的规划问题就称为线性规划问题。,1.1 线性规划问题及其数学模型,例1.2 某公司有100万元的资金可供投资。该公司有六个可选的投资项目，其各种数据如表12所示。,1.1 线性规划问题及其数学模型,该公司想达到的目标为：投资风险最小，每年红利至少为6.5万元，最低平均增长率为12%，最低平均信用度为7。请用线性规划方法求解该问题。,1.1 线性规划问题及其数学模型,解： （1）决策变量 本问题的决策变量是在每种投资项目上的投资额。设xi为项目i的投资额（万元）（i=1,2,6） （2）目标函数 本问题的目标为总投资风险最小
6、，即,1.1 线性规划问题及其数学模型,（3）约束条件 本问题共有五个约束条件: 各项目投资总和为100万元; 每年红利至少为6.5万元; 最低平均增长率为12%; 最低平均信用度为7; 非负约束。,1.1 线性规划问题及其数学模型,得到的线性规划数学模型为：,这是一个典型的成本（或风险）最小化问题。其中，“Min”是英文单词“Minimize”的缩写，含义为“最小化”。因此，上述模型的含义是：在给定的条件限制下，求使得目标函数z达到最小时的x1,x2,x3,x4,x5,x6取值,1.1 线性规划问题及其数学模型,线性规划的模型结构: 从以上两个例子中可以归纳出线性规划问题的一般形式：对于一组决策变量x1,x2,xn，取,1.1 线性规划问题及其数学模型,在线性规划模型中，也直接称z为目标函数； 称xj(j=1,2,n)为决策变量；称cj(j=1,2,n) 为目标函数系数或价值系数或费用系数；称 bi(i=1,2,m)为函数约束右端常数或简称右端值，也称资源常数；称aij(i=1,2,m;j=1,2,n)为约束系数或技术系数或工艺系数。这里，cj，bi，aij均为常数。 线性规划的数学模型可以表示为下列简洁的形式：,
