《运筹学》-课程实践S1

课程实践S1线性规划学习目标通过本课程实践S1的学习，进一步熟悉线性规划在现实经济管理问题中的建模及应用规律，了解运筹学软件LINDO的特点及求解线性规划的基本过程，理解软件输出结果的含义，能够应用软件求解简单的线性规划问题。线性规划是实践中应用非常广泛的一种运筹学方法，可以解决经济管理领域很多需要量化分析的问题。但因为线性规划的求解方法需要大量的计算，所以限制了线性规划方法在实践领域的应用。随着计算机技术的飞速发展，不仅计算机的运算能力不断提高，操作的便利性也使得运筹学软件在教学和实践领域得到越来越广泛的应用。LINDO软件是一种专门用于求解数学规划问题的软件包。由于上一页下一页返回课程实践S1线性规划 LINDO执行速度很快且输入方便，易于求解和分析数学规划问题，因此在科研和工业界得到广泛应用。LINDO6.1学生版至多可求解多达300个变量和150个约束的规划问题。在大型的机器上，LINDO被用来解决一些拥有超过50000个约束条件和200000万个变量的大规模复杂问题。为了加深读者对线性规划方法的理解及线性规划问题的计算机求解，下面对教材第2章到第5章内容的实验与实践提出系统的建议。上一页返回下一页S1.1LINDO软件求解线性规划导引S1.1.1实验与实践

(1)学习并掌握LINDO软件的基本功能及求解线性规划问题的基本过程。

(2)对比教材中关于线性规划的内容，理解LINDO软件各种操作步骤及输出结果的含义。(3)每一小组结合教材中讲过的案例，进行LINDO软件的求解和结果分析，熟练掌握LINDO软件的应用。下一页返回S1.1LINDO软件求解线性规划导引S1.1.2LINDO软件求解线性规划问题案例分析

LINDO主要有三个基本使用模式。对于一些中小规模的问题，LINDO只要通过键盘输入就可以方便地实现交互性良好的操作与使用，如输入一个模型是相当简单方便的事情。另外，LINDO也可以对外建文件进行处理，只要这些文件里包含有必要的命令代码和输入数据，处理后就可以生成用于报告目的的文档。最后，我们还可以自建子程序，然后直接与LINDO相结合形成一个包括我们自己的代码和LINDO本身的优化库的综合程序。LINDO软件的基本操作比较简单，这里不再描述基本操作功能，而只列出UNDO的语法规则。LINDO语法特别简单，所以易学、易用。以下14条规则是基本语法。上一页下一页返回S1.1LINDO软件求解线性规划导引(1)目标函数以MAX或MIN开头。(2)变量名长度最长为8个字符。(3)约束的名称以括号结尾。(4)目标函数及各约束条件之间一定要用“Subjectto(ST)”分开。(5)变量与其系数间可以有空格，但不能有任何运算符号(如乘号“*”等)。(6)要输入“<=”或“>=”约束，相应以“<”或“>”代替即可。(7)括号不具有更高的运算优先级，所有运算自左至右进行。(8)注释以感叹号打头。(9)一条语句可以断行，如:max10x+4y是可以的。上一页下一页返回S1.1LINDO软件求解线性规划导引(10)不区分大小写。

(11)式子的右端只能是常数，如“x>y’’是错的，应写成“x-y>0”。

(12)式子的左端只能是变量及其系数，如“10x+y-10=0”是错的，应写成“10x+y=10”。

(13)一般LINDO中不能接受括号“()”和逗号“，”，如“400(X1+X2”需写成“400X1,+400X2“。10,000需写成10000。

(14)表达式应当已经过简化，不能出现“2X1+3X2-4X1"，而应写成“-2X1+3X2”。下面结合教材中大家很熟悉的生产计划问题讲述LINDO的基本使用过程。上一页下一页返回S1.1LINDO软件求解线性规划导引

例S1.1某工厂拥有A,B,C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数、每件产品可以获得的利润以及三种设备可利用的时数如表S1-1所示。问题:工厂应如何安排生产可获得最大的总利润?解分析上述问题可以建立如下的线性规划模型:目标函数 maxz=1500x1+2500x2约束条件上一页下一页返回S1.1LINDO软件求解线性规划导引下面讨论如何用LINDO求解上述线性规划问题。(1)打开LINDO软件，将出现如图S1-1所示窗口。(2)输入上述问题的线性规划模型，如图S1-2所示。

(3)这样我们就建立了一个简单的模型，下面我们可以开始求解了。从“Solve”菜单选择“Solve”命令，或者在窗口顶部的工具栏里按“Solve”按钮，LINDO就会开始对模型进行编译。首先，LINDO会检查模型是否具有数学意义以及是否符合语法要求。如果模型不能通过这一步检查，会看到以下报错信息:Anerroroccurredduringcompilationonline:n(产生错误的行数)，LINDO会自动跳转到发生错误的行。我们就可以检查该行的语法错误并改正过来。通过这一检查阶段后，LINDO就会正式开始求解，这由一个叫“LINDOSolves”的处理器完成。当“Solves”初始化时，会在屏幕上显示一个状态窗口，如图S1-3所示。上一页下一页返回S1.1LINDO软件求解线性规划导引这个状态窗口可以显示“Solver”的进度，表S1-2是对各数据项/控制按钮的说明。

(4)当Solve:完成优化过程后将会提示是否要进行灵敏度和范围分析。下面在S1.2部分我们会用到这个有用的信息，现在我们先按下“No”按钮关闭状态窗口。现在，屏幕将会出现一个名为“ReportsWindow”的窗口。这个窗口里显示的就是LINDO的输出结果报告，它可以显示64000个字符的信息。如果有需要，LIND()会从顶部开始刷除部分输出以腾出空间来显示新的输出。如果有一个很长的解决方案报告，需要完整地阅读使用，我们可以把这些信息从“ReportsWindow”写到另外一个磁盘文件里，方法是选取“「File」

=>「LogOutput」”命令，按快捷键是F10，然后就可以找到该文件，进行阅读使用。上一页下一页返回S1.1LINDO软件求解线性规划导引

还是回到正在讨论的案例，按“ReportsWindow”里显示的是模型的最优解决方案，如图S1-4所示。上述输出结果告诉我们这一线性规划问题的最大利润是70000，二，和二2的取值分别为5,25，与我们用单纯形法求得的结果完全一致。例S1.2某工厂熔炼一种新型不锈钢，需要用四种合金T1,T2,T3和T4为原料，经测这四种原料关于元素铬(Cr),锰(Mn}和镍(Ni)的含量(%)、单价，以及这种不锈钢所需铬(Cr)，锰(Mn}和镍(Ni)的最低含量(%)如表S1-3所示。上一页下一页返回S1.1LINDO软件求解线性规划导引假设熔炼时重量没有损耗。问:要熔炼成100吨这样的不锈钢，应选用原料T1,T2T3和T4各多少吨，能够使成本最小?解建立上述问题的线性规划模型:目标函数约束条件

上一页下一页返回S1.1LINDO软件求解线性规划导引打开LINDO软件，输入上述模型，如图S1-5所示。运算求解得到的结果如图S1-6所示。最低成本为955万元，各种原料的数量T1为26.6吨，T2为31.6吨，T3为41.8吨，T4为0。例S1.3某旅馆每日至少需要表S1-4所示数量的服务员。每班服务员从开始上班到下班连续工作八小时，为满足每班所需要的最少服务员数，这个旅馆至少需要多少服务员。上一页下一页返回S1.1LINDO软件求解线性规划导引

解根据问题描述，设xi(i=2，3，4，5，6)为第i班开始上班的服务员人数。则数学模型为:上一页下一页返回S1.1LINDO软件求解线性规划导引启动LINDO，将上述模型输入，如图S1-7所示。点击“Solve”按钮，求解得到的结果如图S1-8所示。旅馆需要的服务员至少为200个，服务员的排班安排如上图所示。上一页返回下一页S1.2对偶与灵敏度分析Sl.2.1实验与实践

(1)学习并掌握一种用于求解影子价格及灵敏度分析的计算机应用软件。

(2)体会影子价格的含义及其在现实经济管理中的应用，体会灵敏度分析在决策过程中的意义。

(3)分组制定实践调研计划，收集数据，分析、讨论影子价格及灵敏度分析的实践应用领域和模式特征。

(4)分组选择S1.2.2的案例进行讨论、分析，计算结果，并组织在班内介绍思路和计算情况。

(5)每一小组在(3)的基础上，结合实际编写一个案例并进行分析、求解，讨论解的过程及实践意义。下一页返回上一页S1.2对偶与灵敏度分析Sl.2.2案例建模与分析用LIND()软件进行线性规划的影子价格及灵敏度分析非常方便，前面S1.1提到当"Solver”完成优化过程后将会提示是否要进行灵敏度和范围分析，这时我们按下“Yes”按钮即可。显示结果的含义将在下面的具体案例中解释。例S1.4某工厂计划在下一生产周期生产3种产品A1,A2,A3这些产品都要在甲、乙、丙、丁4种设备上加工，根据设备性能和以往的生产情况知道单位产品的加工工时、各种设备的最大加工工时限制，以及每种产品的单位利润(单位:千元)如表S1-5所示。问如何安排生产计划，才能使工厂得到最大利润?从另一个角度来讨论该问题。假设工厂考虑不安排生产，而准备将所有设备出租，收取租费。于是，需要为每种设备的台时进行估价。每种设备的台时估价为多少最合适?上一页下一页返回S1.2对偶与灵敏度分析解设x1，x2，x3分别为产品A1,A2,A3的产量，构造此问题的线性规划模型为将上述线性规划模型输入LINDO软件，如图S1-9所示。点击“Slove”按钮，如果只是求出原线性规划问题中各约束条件对应的影子价格，则在提示是否要进行灵敏度和范围分析时不需要按下“Yes”按钮，求解结果如图S1-10所示。上一页下一页返回S1.2对偶与灵敏度分析

下面对结果中的各个表达式做出解释。

"OBJECTIVEFUNCTIONVALUE1)280.0000”表示最优目标值为280.00000"VALUE'，给出最优解中各变量的值。

"SLACKORSURPLUS”给出松弛变量的值。上例中SLK2=第二行松弛变量=0(模型第一行表示目标函数，所以第二行对应第一个约束)。

"REDUCECOST”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时，目标函数的变化率，其中基变量的“reducecost”值应为0。非基变量Xj相应的“reducecost”值表示Xj增加一个单位(此时假定其他非基变量保持不变)时目标函数减小的量(max型问题)。上例中X2对应的“reducecost”值为0，表示当X2=0时，目标函数值不变。上一页下一页返回S1.2对偶与灵敏度分析"DUALPRICE"(对偶价格)列出最优单纯形表中判别数所在行的松弛变量的系数，表示当对应约束有微小变动时，目标函数的变化率;输出结果中对应每一个约束有一个对偶价格，也即各个约束条件对应的影子价格。若其数值为X，表示对应约束中不等式右端项若增加一个单位，目标函数将增加X个单位(max型问题)。从上图可看出，4个约束条件对应的影子价格分别为:0.666667,0,0,4.666667,与教材中求得的4种设备的台时估价分别为2/3,0,0,14/3(单位:千元)是完全一致的。例S1.5下面的线性规划模型的实际背景为:某工厂用两种设备生产3种产品，目标函数为求最大利润(单位:元)。上一页下一页返回S1.2对偶与灵敏度分析此规划的最优单纯形表为表S1-6，其中x4，x5为引入的松弛变量。由表可知，最优解为生产第1种产品10件，第2种产品130件，不生产第3种产品，最大利润为1760元。现对目标函数系数c3=10和c1=20及右端项常数进行灵敏度分析。上一页下一页返回S1.2对偶与灵敏度分析

解打开LIND()软件，输入上述线性规划模型，结果如图S1-11所示。下面对结果中的各个表达式做出解释。图S1-12中的内容可分为两部分，第一部分给出了线性规划问题的最优解及对偶价格。第二部分(下面12行内容)则是敏感性分析，报告当目标函数的费用系数和约束右端项在什么范围变化(此时假定其他系数保持不变)时，最优基保持不变。"ALLOWABLEINCREASE”表示允许增加的最大值，"ALLOWABLEDECREASE”表示允许减少的最大值，报告中“INFINITY”表示正无穷。从图S1-12中可以看出，目标函数系数的变化范围为:上一页下一页返回S1.2对偶与灵敏度分析目标函数系数表示的是产品的利润大小，一般在经营过程中不允许出现负的利润，所以这里C:变化的下限设为0。右端项的变化范围为:与教材中分析得出的结果进行对比，可知两者是完全一致的。上一页返回下一页S1.3运输问题S1.3.1实验与实践

(1)学习并掌握一种用于求解运输问题的计算机应用软件。

(2)体会并掌握运输问题建模的特点，特别是灵活掌握虚拟产地和虚拟销地的设置。

(3)分组制定实践调研计划，收集数据，分析、讨论运输问题的实践应用领域和模式特征，尤其是可以转化为运输问题的经济管理问题。

(4)分组选择S1.4.2的案例进行讨论、分析，计算结果，并组织在班内介绍思路和计算情况。

(5)每一小组在(3)的基础上，结合实际编写一个案例并进行分析、求解，讨论解的过程及实践意义。下一页返回上一页S1.3运输问题Sl.3.2案例建模与分析运输问题的本质是线性规划问题，针对运输问题建立的线性规划模型，我们可以直接采用S1.1讲述的方法用LINDO软件来求解。例S1.6某公司从三个产地A1,A2,A3将物品运往四个销地B1，B2，B3，B4各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表S1-7所示。问:应如何调运，可使得总运输费最小?解设xij为从产地Ai运往销地Bj的运输量(i=1,2,3,4;j=1,2,3,4)，此运输问题的线性规划的模型如下。上一页下一页返回S1.3运输问题将上述运输问题模型输入LINDO，如图S1-13所示。上一页下一页返回S1.3运输问题

点击“Slove”按钮，求得结果如图S1-14所示。最小的总运输费用为85，各变量的最优解为x11=2，x13=，x21=1，x24=3，x32=6，x34=3。对比教材中用表上作业法的结果可知，这是问题的最优解之一。例S1.7某研究院有B1,B2,B3三个区。每年取暖分别需要用煤3500吨、1100吨、2400吨，这些煤都要由A1,A2两处煤矿负责供应，价格、质量均相同。A1,A2煤矿的供应能力分别为1500吨、4000吨，运价(元/吨)如表S1-8所示。由于需求大于供给，经院研究决定B1区供应量可减少。一900吨，B2区必须满足需求量，B3区供应量不少于1600吨，试求总费用为最低的调运方案。上一页下一页返回S1.3运输问题

解根据题意以及给定的数据，我们看到这是一个产销不平衡的运输问题，需求量大于生产量。由于B1区供应量可减少0~900吨，B2区必须满足需求量，B3区供应量不少于1600吨，可以把B1区和B3区分别设为两个区:一个为必须满足需求量的区域，另一个为可以调整供应量的区域。这样，原问题化为五个需求区域B1,B1‘,B2,B3,B3’的问题，同时增加一个虚设的产地A3。在运输费方面，取M代表一个很大的正数，使必须满足需求量区域的相应变量x31,x33,x34运费的取值为M，可调整需求量区域的相应变量x32,x35运费的取值为0，作出产销平衡的运价表(见表S1-9)。上一页下一页返回S1.3运输问题上述运输问题相当于下面的线性规划模型:上一页下一页返回S1.3运输问题

打开LINDO软件，输入上述线性规划模型，因为M是足够大的正数，相对于题目中的数据，这里取100000代替M。输入模型如图S1-15所示。点击“Slove”按钮，求解结果如图S1-16所示。最优运输方案为:x15=1500，x21=2600，x22=200，x23=1100，x24=100，x32=700，x35=800。最小运输费用为981700元。上一页返回下一页S1.4目标规划S1.4.1实验与实践

(1)学习并掌握一种用于求解目标规划的计算机应用软件。

(2)体会并掌握目标规划建模的特点，特别是灵活掌握目标约束和目标规划目标函数的设置。

(3)分组制定实践调研计划，收集数据，分析、讨论目标规划的实践应用领域和模式特征。

(4)分组选择S1.4.2的案例进行讨论、分析，计算结果，并组织在班内介绍思路和计算情况。

(5)每一小组在(3)的基础上，结合实际编写一个案例并进行分析、求解，讨论解的过程及实践意义。下一页返回上一页S1.4目标规划Sl.4.2案例建模与分析

LINDO不能直接求解目标规划问题，但可以采用分别求解各级目标的序贯式算法来求解目标规划问题，具体操作如下述案例所示。例S1.8某电视台考虑如何合理安排各种节目播出时间。按照有关规定:该台每天允许开播12小时，其中商业广告节目用以赢利，平均每分钟可收入300元，新闻节目每分钟需要支出50元，音乐文艺节目每分钟需要支出20元。按照上级规定，正常情况下商业广告节目只能占播出时间的20%，而每小时至少安排10分钟的新闻节目。问:此电视台每天应如何安排电视节目?其优先等级为:P1:满足有关部门规定的播出要求;P2:每天的纯收入最大。试建立此问题的目标规划模型并用LINDO软件求解。上一页下一页返回S1.4目标规划

试建立此问题的目标规划模型并用LINDO软件求解。解设安排商业广告节目的时间为x1小时，新闻节目为x2小时，音乐文艺节目为x2时，则所求模型为:上一页下一页返回S1.4目标规划下面用LINDO软件求解这一目标规划问题。(1)首先求解第一级目标，打开LINDO软件，输入下述线性规划模型:输入后的界面如图S1-17所示。上一页下一页返回S1.4目标规划点击“Slove”按钮求解得 。(2)求解第二级目标，输入下述线性规划模型:上一页下一页返回S1.4目标规划

点击“Sl。二”按钮求解得结果如图S1-18所示。满足上述两个目标要求的安排为:商业广告节目安排2.4小时，新闻节目安排2小时，音乐文艺节目安排7.6小时。例S1.9某公司分厂用一条生产线生产两种产品A和B，每周生产线运行时间为60小时，生产一台A产品需要4小时，生产一台B产品需要6小时。根据市场预测，A,B产品平均销售量分别为每周9台、8台，它们销售利润分别为12万元、18万元。在制订生产计划时，经理考虑下述4项目标:首先，产量不能超过市场预测的销售量;其次，工人加班时间最少;最后，希望总利润最大;最后，要尽可能满足市场需求，当不能满足时，市场认为B