实用运筹学线性规划.pptx

《实用运筹学线性规划.pptx》由会员分享，可在线阅读，更多相关《实用运筹学线性规划.pptx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实用运筹学线性规划实用运筹学线性规划本章内容要点线性规划问题及其数学线性规划问题及其数学模型；模型；线性规划的电子表格建线性规划的电子表格建模；模；线性规划的多解分析。线性规划的多解分析。第1页/共18页本章内容1.1 1.1 1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型线性规划问题及其数学模型线性规划问题及其数学模型1.2 1.2 1.2 1.2 线性规划问题的图解法线性规划问题的图解法线性规划问题的图解法线性规划问题的图解法1.3 1.3 1.3 1.3 用用用用ExcelExcelExcelExcel“规划求解规划求解规划求解规划求解”功能求解线性规划功能求解线性规划

2、功能求解线性规划功能求解线性规划问题问题问题问题1.4 1.4 1.4 1.4 线性规划问题求解的几种可能结果线性规划问题求解的几种可能结果线性规划问题求解的几种可能结果线性规划问题求解的几种可能结果第2页/共18页本章主要内容框架图第3页/共18页1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型 例例例例1.11.11.11.1 某某某某工工工工厂厂厂厂要要要要生生生生产产产产两两两两种种种种新新新新产产产产品品品品：门门门门和和和和窗窗窗窗。经经经经测测测测算算算算，每每每每生生生生产产产产一一一一扇扇扇扇门门门门需需需需要要要要在在在在车车车车间间间间1 1 1 1加加加

3、加工工工工1 1 1 1小小小小时时时时、在在在在车车车车间间间间3 3 3 3加加加加工工工工3 3 3 3小小小小时时时时；每每每每生生生生产产产产一一一一扇扇扇扇窗窗窗窗需需需需要要要要在在在在车车车车间间间间2 2 2 2和和和和车车车车间间间间3 3 3 3各各各各加加加加工工工工2 2 2 2小小小小时时时时。而而而而车车车车间间间间1 1 1 1每每每每周周周周可可可可用用用用于于于于生生生生产产产产这这这这两两两两种种种种新新新新产产产产品品品品的的的的时时时时间间间间为为为为4 4 4 4小小小小时时时时、车车车车间间间间2 2 2 2为为为为12121212小小小小时时时时

4、、车车车车间间间间3 3 3 3为为为为18181818小小小小时时时时。已已已已知知知知每每每每扇扇扇扇门门门门的的的的利利利利润润润润为为为为300300300300元元元元，每每每每扇扇扇扇窗窗窗窗的的的的利利利利润润润润为为为为500500500500元元元元。而而而而且且且且根根根根据据据据经经经经市市市市场场场场调调调调查查查查得得得得到到到到的的的的该该该该两两两两种种种种新新新新产产产产品品品品的的的的市市市市场场场场需需需需求求求求状状状状况况况况可可可可以以以以确确确确定定定定，按按按按当当当当前前前前的的的的定定定定价价价价可可可可确确确确保保保保所所所所有有有有新新新新

5、产产产产品品品品均均均均能能能能销销销销售售售售出出出出去去去去。问问问问该该该该工工工工厂厂厂厂如如如如何何何何安安安安排排排排这这这这两两两两种种种种新新新新产产产产品品品品的的的的生生生生产产产产计计计计划划划划，可使总利润最大？可使总利润最大？可使总利润最大？可使总利润最大？第4页/共18页1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型 在在在在该该该该问问问问题题题题中中中中，目目目目标标标标是是是是总总总总利利利利润润润润最最最最大大大大化化化化，所所所所要要要要决决决决策策策策的的的的变变变变量量量量是是是是新新新新产产产产品品品品的的的的产产产产量量量量，而而

6、而而新新新新产产产产品品品品的的的的产产产产量量量量要要要要受受受受到到到到三三三三个个个个车车车车间间间间每每每每周周周周可可可可用用用用于于于于生生生生产产产产新新新新产产产产品品品品时时时时间间间间的的的的限限限限制制制制。因因因因此此此此，该该该该问问问问题题题题可可可可以以以以用用用用目目目目标标标标、决决决决策策策策变变变变量量量量和和和和约约约约束束束束条条条条件件件件三三三三个个个个因因因因素素素素加加加加以以以以描描描描述述述述。实实实实际际际际上上上上，所所所所有有有有的的的的线线线线性性性性规规规规划划划划问问问问题题题题都都都都包包包包含这三个因素：含这三个因素：含这三

7、个因素：含这三个因素：（1 1 1 1）决决决决策策策策变变变变量量量量是是是是问问问问题题题题中中中中有有有有待待待待确确确确定定定定的的的的未未未未知知知知因因因因素素素素。例例例例如如如如决决决决定定定定企业经营目标的各产品的产量等。企业经营目标的各产品的产量等。企业经营目标的各产品的产量等。企业经营目标的各产品的产量等。（2 2 2 2）目目目目标标标标函函函函数数数数是是是是指指指指对对对对问问问问题题题题所所所所追追追追求求求求的的的的目目目目标标标标的的的的数数数数学学学学描描描描述述述述。例例例例如如如如利润最大、成本最小利润最大、成本最小利润最大、成本最小利润最大、成本最小等

8、。等。等。等。（3 3 3 3）约约约约束束束束条条条条件件件件是是是是指指指指实实实实现现现现问问问问题题题题目目目目标标标标的的的的限限限限制制制制因因因因素素素素。如如如如原原原原材材材材料料料料供供供供应应应应量量量量、生生生生产产产产能能能能力力力力、市市市市场场场场需需需需求求求求等等等等，它它它它们们们们限限限限制制制制了了了了目目目目标标标标值值值值所能到达的程度。所能到达的程度。所能到达的程度。所能到达的程度。第5页/共18页1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型解：解：解：解：例例例例1.11.11.11.1可用表可用表可用表可用表1 1 1 11

9、 1 1 1表示。表示。表示。表示。车间车间单位产品的生产时间（小时）单位产品的生产时间（小时）每周可获得的生产每周可获得的生产时间（小时）时间（小时）门门窗窗1 11 10 04 42 20 02 212123 33 32 21818单位利润（元）单位利润（元）300300500500第6页/共18页1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型（1 1）决策变量）决策变量）决策变量）决策变量本问题的决策变量是每周门和窗的产量。本问题的决策变量是每周门和窗的产量。本问题的决策变量是每周门和窗的产量。本问题的决策变量是每周门和窗的产量。可设：可设：可设：可设：x x1 1为每

10、周门的产量（扇）；为每周门的产量（扇）；为每周门的产量（扇）；为每周门的产量（扇）；x x2 2为每周窗的产量（扇）。为每周窗的产量（扇）。为每周窗的产量（扇）。为每周窗的产量（扇）。（2 2）目标函数）目标函数）目标函数）目标函数本本本本问问问问题题题题的的的的目目目目标标标标是是是是总总总总利利利利润润润润最最最最大大大大。由由由由于于于于门门门门和和和和窗窗窗窗的的的的单单单单位位位位利利利利润润润润分分分分别别别别为为为为300300元元元元和和和和500500元元元元，而而而而其其其其每每每每周周周周产产产产量量量量分分分分别别别别为为为为x x1 1和和和和x x2 2，所以每周总

11、利润，所以每周总利润，所以每周总利润，所以每周总利润z z为：为：为：为：z=z=300300 x x1 1500500 x x2 2 （元）（元）（元）（元）第7页/共18页1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型（3 3）约束条件）约束条件本问题的约束条件共有本问题的约束条件共有四四个。个。车间车间车间车间1 1 1 1每周可用工时限制：每周可用工时限制：每周可用工时限制：每周可用工时限制：x x1 1 4 4 4 4车车车车间间间间2 2 2 2每每每每周周周周可可可可用用用用工工工工时时时时限限限限制制制制：2 2 2 2x x2 2 12121212车车车车间

12、间间间3 3 3 3每每每每周周周周可可可可用用用用工工工工时时时时限限限限制制制制：3 3 3 3x x1 1 +2+2+2+2x x2 2 18 18 18 18非负约束非负约束非负约束非负约束:x x1 1 0,0,0,0,x x2 2 0 0 0 0第8页/共18页1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型例例1.11.1的的线线性性规规划划模型模型:这是一个典型的这是一个典型的利润最大化利润最大化的生产计划问题。其中，的生产计划问题。其中，“Max”是英文单词是英文单词“Maximize”的缩写，含义为的缩写，含义为“最大化最大化”；“s.t.”是是“subje

13、ct to”的缩写，表示的缩写，表示“满足于满足于”。因此，上述模型的含义是：在给定的条件限制下，求使得目标函数。因此，上述模型的含义是：在给定的条件限制下，求使得目标函数z达到最大时达到最大时x1，x2的取值。的取值。第9页/共18页1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型 本本章章讨讨论论的的问问题题均均为为线线性性规规划划问问题题。所所谓谓“线线性性”规规划划，是是指指如如果果目目标标函函数数是是关关于于决决策策变变量量的的线线性性函函数数，而而且且约约束束条条件件也也都都是是关关于于决决策策变变量量的的线线性性等等式式或或线线性性不不等等式式，则则相相应应的的规

14、划问题就称为线性规划问题。规划问题就称为线性规划问题。第10页/共18页1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型例例1.21.2 某某公公司司有有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 6第1

15、1页/共18页1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型 该该公公司司想想达达到到的的目目标标为为：投投资资风风险险最最小小，每每年年红红利利至至少少为为6.56.5万万元元，最最低低平平均均增增长长率率为为12%12%，最最低低平平均均信信用用度度为为7 7。请请用用线线性性规规划划方方法求解该问题。法求解该问题。第12页/共18页1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型解：解：解：解：（1 1 1 1）决策变量）决策变量）决策变量）决策变量 本本本本问问问问题题题题的的的的决决决决策策策策变变变变量量量量是是是是在在在在每每每每种种种种投投投投

16、资资资资项项项项目目目目上上上上的的的的投投投投资资资资 额额额额。设设设设 x xi i为为为为 项项项项 目目目目 i i的的的的 投投投投 资资资资 额额额额（万万万万 元元元元）（i i=1,2,=1,2,=1,2,=1,2,6,6,6,6）（2 2 2 2）目标函数）目标函数）目标函数）目标函数 本问题的目标为总投资风险最小，即本问题的目标为总投资风险最小，即本问题的目标为总投资风险最小，即本问题的目标为总投资风险最小，即第13页/共18页1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型（3 3 3 3）约束条件）约束条件）约束条件）约束条件本问题共有五个约束条件本问

17、题共有五个约束条件本问题共有五个约束条件本问题共有五个约束条件:各项目投资总和为各项目投资总和为各项目投资总和为各项目投资总和为100100100100万元万元万元万元;每年红利至少为每年红利至少为每年红利至少为每年红利至少为6.56.56.56.5万元万元万元万元;最低平均增长率为最低平均增长率为最低平均增长率为最低平均增长率为12%;12%;12%;12%;最低平均信用度为最低平均信用度为最低平均信用度为最低平均信用度为7;7;7;7;非负约束。非负约束。非负约束。非负约束。第14页/共18页1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型得到的线性规划数学模型为：得到的线

18、性规划数学模型为：得到的线性规划数学模型为：得到的线性规划数学模型为：这是一个典型的这是一个典型的成本成本（或风险）（或风险）最小化最小化问题。其中，问题。其中，“MinMin”是英文单词是英文单词“MinimizeMinimize”的缩写，含义为的缩写，含义为“最小化最小化”。因此，上述模型的含义是：在给定的条件限制下，求使得目标函数。因此，上述模型的含义是：在给定的条件限制下，求使得目标函数z z达到最小时的达到最小时的x1,x2,x3,x4,x5,x6取值取值 第15页/共18页1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型线性规划的模型结构线性规划的模型结构:从从从从

19、以以以以上上上上两两两两个个个个例例例例子子子子中中中中可可可可以以以以归归归归纳纳纳纳出出出出线线线线性性性性规规规规划划划划问问问问题题题题的的的的一一一一般般般般形式：对于一组决策变量形式：对于一组决策变量形式：对于一组决策变量形式：对于一组决策变量x x1 1,x,x2 2,x xn n，取，取，取，取第16页/共18页1.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型在在在在线线线线性性性性规规规规划划划划模模模模型型型型中中中中，也也也也直直直直接接接接称称称称z z z z为为为为目目目目标标标标函函函函数数数数；称称称称x xj j(j=1,2,(j=1,2,n)

20、,n)为为为为决决决决策策策策变变变变量量量量；称称称称c cj j(j=1,2,(j=1,2,n),n)为为为为目目目目标标标标函函函函数数数数系系系系数数数数或或或或价价价价值值值值系系系系数数数数或或或或费费费费用用用用系系系系数数数数；称称称称 b bi i(i=1,2,(i=1,2,m),m)为为为为函函函函数数数数约约约约束束束束右右右右端端端端常常常常数数数数或或或或简简简简称称称称右右右右端端端端值值值值，也也也也称称称称资资资资源源源源常常常常数数数数；称称称称a aij ij(i=1,2,(i=1,2,m;j=1,2,m;j=1,2,n),n)为为为为约约约约束束束束系系系系数数数数或或或或技技技技术术术术系数系数系数系数或或或或工艺系数工艺系数工艺系数工艺系数。这里，。这里，。这里，。这里，c cj j，b bi i，a aij ij均为常数。均为常数。均为常数。均为常数。线性规划的数学模型可以表示为下列简洁的形式：线性规划的数学模型可以表示为下列简洁的形式：线性规划的数学模型可以表示为下列简洁的形式：线性规划的数学模型可以表示为下列简洁的形式：第17页/共18页感谢您的观看。感谢您的观看。第18页/共18页