管理运筹学-线性规划的计算机求解ppt课件.ppt

第三章第三章 线性规划问题的计算机求解线性规划问题的计算机求解运运运运 筹筹筹筹 学学学学1经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第三章第三章 线性规划问题的计算机求解线性规划问题的计算机求解1“1“管理运筹学管理运筹学”软件的操作方法软件的操作方法2“2“管理运筹学管理运筹学”软件的输出信息分析软件的输出信息分析2经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第三章第三章 线性规划问题的计算机求解线性规划问题的计算机求解 随随书书软软件件为为“管管理理运运筹筹学学”2.52.5版版(Window(Window版版)，是是2.02.0版版(Window(Window版版)的的升升级级版版。它它包包括括：线线性性规规划划、运运输输问问题题、整整数数规规划划(0-1(0-1整整数数规规划划、纯纯整整数数规规划划和和混混合合整整数数规规划划和和指指派派问问题题)、目目标标规规划划、对对策策论论、最最短短路路径径、最最小小生生成成树树、最最大大流流量量、最最小小费费用用最最大大流流、关关键键路路径径、存存储储论论、排排队队论论、决决策策分分析析、预预测测问问题题和和层次分析法，共层次分析法，共1515个子模块。个子模块。3经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例例1.目标函数：目标函数：Max z=50 x1+100 x2 约束条件：约束条件：s.t.x1+x2 300 (A)2x1+x2 400 (B)x2 250 (C)x1 0 (D)x2 0 (E)1“1“管理运筹学管理运筹学”软件的操作方法软件的操作方法1.1.软件使用演示：（演示例软件使用演示：（演示例1 1）第第一一步步:点点击击“开开始始”-“-“程程序序”-“-“管管理理运运筹筹学学2.5”,2.5”,弹弹出出主主窗口窗口.4经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用1“1“管理运筹学管理运筹学”软件的操作方法软件的操作方法第第二二步步：选选择择所所需需子子模模块块，点点击击主主窗窗口口中中的的相相应应按按钮钮。本本题题中中选选用用“线线性性规规划划”方方法法。点点击击按按钮钮弹弹出出如如下下界界面：面：例例1.目标函数：目标函数：Max z=50 x1+100 x2 约束条件：约束条件：s.t.x1+x2 300 (A)2x1+x2 400 (B)x2 250 (C)x1 0 (D)x2 0 (E)5经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用1“1“管理运筹学管理运筹学”软件的操作方法软件的操作方法第第三三步步：点点击击“新新建建”按按钮钮，输输入入数数据据。本本题题中中共共有有2 2个个变变量量，4 4个个约约束束条条件件，目目标标函函数数取取MAXMAX。点点击击“确确定定”后后，在在表表中中输输入入C Cj j,b,bi i和和a aijij等等值值，并并确确定定变变量量的的正负约束。输入数值后的界面如下。正负约束。输入数值后的界面如下。例例1.目标函数：目标函数：Max z=50 x1+100 x2 约束条件：约束条件：x1+x2 300 (A)2x1+x2 400 (B)x2 250 (C)x1 0 (D)x2 0 (E)6经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用1“1“管理运筹学管理运筹学”软件的操作方法软件的操作方法第四步：点击第四步：点击“解决解决”按钮，得出计算结果。本题的按钮，得出计算结果。本题的运行结果界面如下。运行结果界面如下。7经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例例1.目标函数：目标函数：Maxz=50 x1+100 x2 约束条件：约束条件：s.t.x1+x2300 (A)2x1+x2400 (B)x2 250 (C)x1 0 (D)x2 0 (E)相相差差值值表表示示相相应应的的决决策策变变量量的的目目标标系系数数需需要要改改进进的的数数量量，使使得得决决策策变变量量为为正正值值，当当决决策策变变量已为正数时，相差数为零。量已为正数时，相差数为零。8经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用松松弛弛/剩剩余余变变量量的的数数值值表表示示还还有有多多少少资资源源没没有有被被使使用用。如如果果为为零零，则则表表示示与与之之相相对对应应的的资资源源已经全部用上。已经全部用上。例例1.目标函数：目标函数：Maxz=50 x1+100 x2 约束条件：约束条件：s.t.x1+x2300 (A)2x1+x2400 (B)x2 250 (C)x1 0 (D)x2 0 (E)9经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用对对偶偶价价格格表表示示其其对对应应的的资资源源每每增增加加一一个个单单位位，将将增增加加多多少少个个单位的最优值。单位的最优值。例例1.目标函数：目标函数：Maxz=50 x1+100 x2 约束条件：约束条件：s.t.x1+x2300 (A)2x1+x2400 (B)x2 250 (C)x1 0 (D)x2 0 (E)10经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用目目标标函函数数系系数数范范围围表表示示最最优优解解不不变变的的情情况况下下,目目标标函函数数的的决决策策变变量量系系数数的的变变化化范范围围.当当前前值值是是指当前的最优解中的系数取值指当前的最优解中的系数取值.例例1.目标函数：目标函数：Maxz=50 x1+100 x2 约束条件：约束条件：s.t.x1+x2300 (A)2x1+x2400 (B)x2 250 (C)x1 0 (D)x2 0 (E)11经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例例1.目标函数：目标函数：Maxz=50 x1+100 x2 约束条件：约束条件：s.t.x1+x2300 (A)2x1+x2400 (B)x2 250 (C)x1 0 (D)x2 0 (E)常常数数项项范范围围是是指指约约束束条条件件的的右右端端常常量量。上上限限值值和和下下限限值值是是指指当当约约束束条条件件的的右右端端常常量量在在此此范范围围内内变变化化时时，与与其其对对应应的的约约束束条条件件的的对对偶偶价价格格不不变变。当当前值是指现在的取值。前值是指现在的取值。12经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用2“2“管理运筹学管理运筹学”软件的输出信息分析软件的输出信息分析第五步：分析运行结果。第五步：分析运行结果。以以上上计计算算机机输输出出的的目目标标函函数数系系数数和和约约束束条条件件右右边边值值的的灵灵敏敏度度分分析析都都是是在在其其他他系系数数值值不不变，只有一个系数变化的基础上得出的！变，只有一个系数变化的基础上得出的！2.当有多个系数变化时，需要进一步讨论。当有多个系数变化时，需要进一步讨论。百百分分之之一一百百法法则则：对对于于所所有有变变化化的的目目标标函函数数决决策策系系数数(约约束束条条件件右右边边常常数数值值)，当当其其所所有有允允许许增增加加的的百百分分比比与与允允许许减减少少的的百百分分比比之之和和不不超超过过100%时时，最最优优解解不不变变(对对偶偶价价格格不不变变，最优解仍是原来几个线性方程的解最优解仍是原来几个线性方程的解)。13经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用2“2“管理运筹学管理运筹学”软件的输出信息分软件的输出信息分析析 *允许增加量允许增加量=上限上限-现在值现在值 c1 的允许增加量为的允许增加量为 100-50=50 b1 的允许增加量为的允许增加量为 325-300=2514经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 *允许减少量允许减少量=现在值现在值-下限下限 c2 的允许减少量为的允许减少量为 100-50=50 b3 的允许减少量为的允许减少量为 250-200=50 *允许增加的百分比允许增加的百分比=增加量增加量/允许增加量允许增加量 *允许减少的百分比允许减少的百分比=减少量减少量/允许减少量允许减少量 15经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用例：例：c1 变为变为 74,c2 变为变为 78,则则(74-50)/50+(100-78)/50=92%故最优解不变。故最优解不变。b1 变为变为 315,b3 变为变为 240,则则(315-300)/25+(250-240)/50=80%故故对对偶偶价价格格不不变变（最最优优解解仍仍是是原原来来几几个个线线性性方方程程的解）的解）。16经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用3.2“3.2“管理运筹学管理运筹学”软件的输出信息分析软件的输出信息分析在在使使用用百百分分之之一一百百法法则则进进行行灵灵敏敏度度分分析析时时，要注意：要注意：1 1）当当允允许许增增加加量量（允允许许减减少少量量）为为无无穷穷大大时时，则则对对任任意意增增加加量量（减减少少量量），其其允允许许增增加加（减少）百分比均看作（减少）百分比均看作0 0；2 2）百百分分之之一一百百法法则则是是充充分分条条件件，但但非非必必要要条条件；也就是说超过件；也就是说超过100%100%并不一定变化；并不一定变化；3 3）百百分分之之一一百百法法则则不不能能用用于于目目标标函函数数决决策策变变量量系系数数和和约约束束条条件件右右边边常常数数值值同同时时变变化化的的情情况。这种情况下，只有重新求解。况。这种情况下，只有重新求解。17经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用下面用下面用“管理运筹学管理运筹学”软件来分析第二章的例软件来分析第二章的例2,其数学模型如下其数学模型如下目标函数：目标函数：Min f=2x1+3 x2约束条件：约束条件：s.t.x1+x2 350 x1 125 2 x1+x2 600 x1 ,x2 0 从上图可知，当购进原材料从上图可知，当购进原材料A 250t，原料，原料B 100t时，购进成本最低，为时，购进成本最低，为800万元。万元。3.2“3.2“管理运筹学管理运筹学”软件的输出信息分析软件的输出信息分析18经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 在在松松弛弛/剩剩余余变变量量栏栏中中，约约束束条条件件2的的值值为为125，它它表表示示对对原原料料A的的最最低低需需求求，即即对对A的的剩剩余余变变量量值值为为125；同同理理可可知知约约束束条条件件1的的剩剩余余变变量量值值为为0；约约束束条条件件3的的松松弛弛变变量量值为值为0.3.2“3.2“管理运筹学管理运筹学”软件的输出信息分析软件的输出信息分析19 在在对对偶偶价价格格栏栏中中，约约束束条条件件3的的对对偶偶价价格格为为1万万元元，也也就就是是说说如如果果把把加加工工时时数数从从600小小时时增增加加到到601小小时时，则则总总成成本本将将得得到到改改进进，由由800万万减减少少到到799万万。也也可可知知约约束束条条件件1的的对对偶偶条条件件为为-4万万元元，也也就就是是说说如如果果把把购购进进原原料料A的的下下限限从从125t增增加加到到126t,那那么么总总成成本本将将加加大大,由由800万万增增加加到到804万万。当当然然如如果果减减少少对对原原料料A的的下下限限，那那么么总总成成本将得到改进。本将得到改进。20在在常常数数项项范范围围一一栏栏中中，知知道道当当约约束束条条件件1的的常常数数项项在在300475范范围围内内变变化化，且且其其他他约约束束条条件件不不变变时时，约约束束条条件件1的的对对偶偶价价格格不不变变；当当约约束束条条件件2的的常常数数项项在在负负无无穷穷到到250范范围围内内变变化化，而而其其他他约约束束条条件件的的常常数数项项不不变变时时，约约束束条条件件2的的对对偶偶价价格格不不变变，仍仍为为0；当当约约束束条条件件3的的常常数数项项在在475700内内变变化化，而而其其他他约约束束条条件件的的常常数数项项不不变变时时，约约束束条条件件3的的对对偶偶价价格格不不变变，仍为仍为1。21经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用注意：注意：1.当约束条件中的常数项增加一个单位时，当约束条件中的常数项增加一个单位时，最优目标函数值增加的数量称之为最优目标函数值增加的数量称之为影子价影子价格格。在求目标函数最大时，当约束条件中。在求目标函数最大时，当约束条件中的常数项增加一个单位时，目标函数值增的常数项增加一个单位时，目标函数值增加的数量就为改进的数量，所以影子价格加的数量就为改进的数量，所以影子价格等于对偶价格；在求目标函数值最小时，等于对偶价格；在求目标函数值最小时，改进的数量就是减少的数量，所以影子价改进的数量就是减少的数量，所以影子价格即为负的对偶价格。格即为负的对偶价格。3.2“3.2“管理运筹学管理运筹学”软件的输出信息分析软件的输出信息分析22经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用注意：注意：2.“管理运筹学管理运筹学”软件可以解决含有软件可以解决含有100个个变量变量50个约束方程的线性规划问题，可个约束方程的线性规划问题，可以解决工商管理中大量的问题。如果想要以解决工商管理中大量的问题。如果想要解决更大的线性规划问题，可以使用由芝解决更大的线性规划问题，可以使用由芝加哥大学的加哥大学的L.E.Schrage开发的开发的Lindo计计算机软件包的微型计算机版本算机软件包的微型计算机版本Lindo/PC。3.2“3.2“管理运筹学管理运筹学”软件的输出信息分析软件的输出信息分析23经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用完完第三章第三章 线性规划问题的计算机求解线性规划问题的计算机求解24