实用运筹学-线性规划.pptx
实用运筹学运用Excel建模和求解第第1 1章章线性规划线性规划本章内容要点线性规划问题及其数学模型；线性规划问题及其数学模型；线性规划的电子表格建模；线性规划的电子表格建模；线性规划的多解分析。线性规划的多解分析。本章内容1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型1.2 1.2 线性规划问题的图解法线性规划问题的图解法1.3 1.3 用用ExcelExcel“规划求解规划求解”功能求解线性规划问功能求解线性规划问题题1.4 1.4 线性规划问题求解的几种可能结果线性规划问题求解的几种可能结果本章主要内容框架图1.1 线性规划问题及其数学模型例例 某某工工厂厂要要生生产产两两种种新新产产品品：门门和和窗窗。经经测测算算，每每生生产产一一扇扇门门需需要要在在车车间间1 1加加工工1 1小小时时、在在车车间间3 3加加工工3 3小小时时；每每生生产产一一扇扇窗窗需需要要在在车车间间2 2和和车车间间3 3各各加加工工2 2小小时时。而而车车间间1 1每每周周可可用用于于生生产产这这两两种种新新产产品品的的时时间间为为4 4小小时时、车车间间2 2为为1212小小时时、车车间间3 3为为1818小小时时。已已知知每每扇扇门门的的利利润润为为300300元元，每每扇扇窗窗的的利利润润为为500500元元。而而且且根根据据经经市市场场调调查查得得到到的的该该两两种种新新产产品品的的市市场场需需求求状状况况可可以以确确定定，按按当当前前的的定定价价可可确确保保所所有有新新产产品品均均能能销销售售出出去去。问问该该工工厂厂如如何何安安排排这这两两种种新新产产品品的的生生产产计计划划，可可使使总总利利润最大？润最大？1.1 线性规划问题及其数学模型在在该该问问题题中中，目目标标是是总总利利润润最最大大化化，所所要要决决策策的的变变量量是是新新产产品品的的产产量量，而而新新产产品品的的产产量量要要受受到到三三个个车车间间每每周周可可用用于于生生产产新新产产品品时时间间的的限限制制。因因此此，该该问问题题可可以以用用目目标标、决决策策变变量量和和约约束束条条件件三三个个因因素素加加以以描描述述。实实际际上上，所所有有的的线线性性规规划划问问题题都都包包含含这这三三个个因素：因素：（1 1）决决策策变变量量是是问问题题中中有有待待确确定定的的未未知知因因素素。例例如如决决定定企企业经营目标的各产品的产量等。业经营目标的各产品的产量等。（2 2）目目标标函函数数是是指指对对问问题题所所追追求求的的目目标标的的数数学学描描述述。例例如如利润最大、成本最小利润最大、成本最小等。等。（3 3）约约束束条条件件是是指指实实现现问问题题目目标标的的限限制制因因素素。如如原原材材料料供供应应量量、生生产产能能力力、市市场场需需求求等等，它它们们限限制制了了目目标标值值所所能能到达的程度。到达的程度。1.1 线性规划问题及其数学模型解：解：例可用表例可用表1 11 1表示。表示。车间车间单位产品的生产时间（小时）单位产品的生产时间（小时）每周可获得的生产每周可获得的生产时间（小时）时间（小时）门门窗窗1 11 10 04 42 20 02 212123 33 32 21818单位利润（元）单位利润（元）3003005005001.1 线性规划问题及其数学模型（1）决策变量）决策变量本问题的决策变量是每周门和窗的产量。本问题的决策变量是每周门和窗的产量。可设：可设：x1为每周门的产量（扇）；为每周门的产量（扇）；x2为每周窗的产量（扇）。为每周窗的产量（扇）。（2）目标函数）目标函数本本问问题题的的目目标标是是总总利利润润最最大大。由由于于门门和和窗窗的的单单位位利利润润分分别别为为300元元和和500元元，而而其其每每周周产产量量分分别别为为x1和和x2，所以每周总利润，所以每周总利润z为：为：z=300 x1500 x2（元）（元）1.1 线性规划问题及其数学模型（3 3）约束条件）约束条件本问题的约束条件共有本问题的约束条件共有四四个。个。车间车间1 1每周可用工时限制：每周可用工时限制：x1 4 4车间车间2 2每周可用工时限制：每周可用工时限制：2 2x2 12 12车间车间3 3每周可用工时限制：每周可用工时限制：3 3x1 +2+2x2 18 18非负约束非负约束:x1 0,0,x2 0 01.1 线性规划问题及其数学模型例的线性规划模型例的线性规划模型:这是一个典型的这是一个典型的利润最大化利润最大化的生产的生产计划问题。其中，计划问题。其中，“Max”是英文单是英文单词词“Maximize”的缩写，含义为的缩写，含义为“最大化最大化”；“s.t.”是是“subject to”的缩写，的缩写，表示表示“满足于满足于”。因此，上述模。因此，上述模型的含义是：在给定的条件限制下，型的含义是：在给定的条件限制下，求使得目标函数求使得目标函数z达到最大时达到最大时x1，x2的取值。的取值。1.1 线性规划问题及其数学模型 本本章章讨讨论论的的问问题题均均为为线线性性规规划划问问题题。所所谓谓“线线性性”规规划划，是是指指如如果果目目标标函函数数是是关关于于决决策策变变量量的的线线性性函函数数，而而且且约约束束条条件件也也都都是是关关于于决决策策变变量量的的线线性性等等式式或或线线性性不不等等式式，则则相相应应的的规规划划问问题题就就称称为为线性规划问题。线性规划问题。1.1 线性规划问题及其数学模型 某某公公司司有有100100万万元元的的资资金金可可供供投投资资。该该公公司司有有六六个个可可选选的的投投资资项项目目，其其各各种种数数据据如如表表1 12 2所示所示。投资项目投资项目风险（风险（%）红利（红利（%）增长（增长（%）信用度信用度1 118184 422224 42 26 65 57 710103 310109 912122 24 44 47 78 810105 512126 615154 46 68 88 88 86 61.1 线性规划问题及其数学模型 该该公公司司想想达达到到的的目目标标为为：投投资资风风险险最最小小，每每年年红红利利至至少少为为万万元元，最最低低平平均均增增长长率率为为12%12%，最最低低平平均均信信用用度度为为7 7。请请用用线线性性规规划划方方法法求求解该问题。解该问题。1.1 线性规划问题及其数学模型解：解：（1 1）决策变量）决策变量 本本问问题题的的决决策策变变量量是是在在每每种种投投资资项项目目上上的的投投资资 额额。设设 xi为为 项项 目目 i的的 投投 资资 额额（万万 元元）（i=1,2,=1,2,6,6）（2 2）目标函数）目标函数 本问题的目标为总投资风险最小，即本问题的目标为总投资风险最小，即1.1 线性规划问题及其数学模型（3 3）约束条件）约束条件本问题共有五个约束条件本问题共有五个约束条件:各项目投资总和为各项目投资总和为100100万元万元;每年红利至少为万元每年红利至少为万元;最低平均增长率为最低平均增长率为12%;12%;最低平均信用度为最低平均信用度为7;7;非负约束。非负约束。1.1 线性规划问题及其数学模型得到的线性规划数学模型为：得到的线性规划数学模型为：这是一个典型的这是一个典型的成本成本（或风险）（或风险）最小化最小化问题。其中，问题。其中，“MinMin”是英文单词是英文单词“MinimizeMinimize”的缩写，含义为的缩写，含义为“最小化最小化”。因此，上述模型的含义是：在给定的。因此，上述模型的含义是：在给定的条件限制下，求使得目标函数条件限制下，求使得目标函数z z达到最小时的达到最小时的x1,x2,x3,x4,x5,x6取值取值 1.1 线性规划问题及其数学模型线性规划的模型结构线性规划的模型结构:从从以以上上两两个个例例子子中中可可以以归归纳纳出出线线性性规规划划问问题题的的一一般般形式：对于一组决策变量形式：对于一组决策变量x1,x2,xn，取，取1.1 线性规划问题及其数学模型在在线线性性规规划划模模型型中中，也也直直接接称称z 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均为常数。均为常数。线性规划的数学模型可以表示为下列简洁的形式：线性规划的数学模型可以表示为下列简洁的形式：
