运筹学上机实验课件.ppt
运筹学实验,第一讲 实验软件介绍第二讲 动态规划第三讲 图与网络分析第四讲 排队论第五讲 存贮论,1,第一讲 实验软件介绍,目的：了解运筹学问题求解常用软件熟悉WinQSB操作界面会用WinQSB求解线性规划问题WinQSB数据(结果)的复制粘贴,2,第一讲 实验软件介绍,Lindo与LingoExcelMatlabWinQSB,3,LINDO和LINGO软件能求解的优化模型,LINGO,LINDO,优化模型,线性规划(LP),非线性规划(NLP),二次规划(QP),连续优化,整数规划(IP),第一讲 实验软件介绍,第一讲 实验软件介绍,ExcelExcel灵活性好，可求解线性规划、非线性规划、动态规划、存储论、排队论、图与网络问题、决策分析等大部分运筹学问题，而且可借助Excel的其他工具作进一步分析，但要求熟悉工作表函数。,5,第一讲 实验软件介绍,Excel,6,第一讲 实验软件介绍,Matlab具有很强的数值计算功能通过编程能求解大部分运筹学问题,7,第一讲 实验软件介绍,WinQSBQSB是Quantitative Systems for Business的缩写，早期的版本在DOS操作系统下运行，WinQSB在Windows操作系统下运行。WinQSB具有操作简便，且能给出中间步骤和图形，但要求模型规范，灵活性较差。,8,第一讲 实验软件介绍,1.线性规划,2.对偶理论,3.整数规划,8.存贮论,5.运输与指派问题,6.网络模型,4.动态规划,7.排队论,第一讲 实验软件介绍,WinQSB基本上有三种窗口：启动窗口、数据输入窗口、结果输出窗口,数据输入窗口：,第一讲 实验软件介绍,主窗口,标题栏,程序名,菜单栏,工具、格式,编辑栏,信息栏,数据输入窗口：,第一讲 实验软件介绍,1.From Excel or Word to WinQSB: Ctrl + C and Ctrl + V2.From WinQSB to Office: 2.1 data: Edit Copy; 2.2 result: File Copy to clipboard; 2.3 save the result: File Save as.,第一讲 实验软件介绍,WinQSB练习：求解线性规划问题,13,第一讲 实验软件介绍,14,运筹学实验,第一讲 实验软件介绍第二讲 动态规划第三讲 图与网络分析第四讲 排队论第五讲 存贮论,15,第二讲 动态规划,目的：熟悉WinQSB动态规划模块求解最短路问题求解背包问题求解生产存储问题,16,第二讲 动态规划,求解最短路问题 给定一个线路网络图，要从A地向E地铺设一条输油管道，各点间连线上的数字表示距离，问选择什么路线，可使距离最短？,17,第二讲 动态规划,18,求解过程：(1)启动程序。点击开始程序WinQSB Dynamic Programing。(2)建立新问题。选择Stagecoach Problem,输入标题名、网络节点数。(3)输入数据。输入节点到节点的距离。(4)求解。确定起点与终点，读写结果。,第二讲 动态规划,19,运行快捷键,修改结点名称,第二讲 动态规划,即最短路径为：AB1 C2 D1 E，最短路长为13。,20,第二讲 动态规划,求解背包问题(P211) 有一辆最大运货量为10t的货车，用以装载三种货物，每种货物的单位质量和相应单位价值如表所示。问如何装载才使总价值最大？,21,第二讲 动态规划,22,求解过程：(1)启动程序。点击开始程序WinQSB Dynamic Programing。(2) 建立新问题。选择Knapsack Problem，输入标题名、项目及物品数。(3)输入数据。分别输入每件物品可装载重量、单位物品容量（体积或重量）、单位物品的价值函数及背包容量，价值函数的变量可统一用X表示，也可以定义每种物品数为X1，X2,Xn。(4)求解。,第二讲 动态规划,23,装载物品的价值,单价重量,各物品最大装载重量及总车最大载重,装载物品的价值必须是公式，该值=物品的价值系数乘以x；x表示装载数量,表格内容居中设置,第二讲 动态规划,24,即物品1装载2t，物品2装载1t，总价值为13个单位。,第二讲 动态规划,求解生产存储问题 Number of Periods=5 某工厂要对一种产品制定今后五个时期的生产计划，根据经验已知今后五个时期的产品需求量如表所示，假定该工厂生产每批产品的固定成本为3(千元)，不生产就为0；产品的单位成本为1(千元)；每时期生产能力不超过6个单位；每个时期末未销售的产品需存储，最大存储能力4个单位，单位存储费为0.5(千元)。还假设在第一时期的初始库存和第五时期末的库存量都为0。试问该工厂如何安排各时期的生产，才能在满足市场需求的条件下，使总成本最小。,25,第二讲 动态规划,26,求解过程：(1)启动程序。点击开始程序WinQSB Dynamic Programing。(2) 建立新问题。选择Production and Inventory Scheduling，输入标题名、周期（阶段）数。(3)输入数据。分别输入每周期的需求量、生产能力、最大存储容量、生产固定成本、变动成本函数（包括生产成本、存储成本和缺货成本，不同周期的变动成本函数可以不同）。(4)求解并显示迭代表格。,第二讲 动态规划,27,调整费用,变动成本计算公式,为产量h为存储量,输入数据时此栏应空着，不可以输入数据,第二讲 动态规划,28,即5个时期的生产量依次为2,6,0,6,0，总成本为26.5个千元。,运筹学实验,第一讲 实验软件介绍第二讲 动态规划第三讲 图与网络分析第四讲 排队论第五讲 存贮论,29,第三讲 图与网络分析,目的：熟悉WinQSB网络模型模块求解最小支撑树问题求解最短路问题求解最大流问题求解旅行商问题求解分配问题求解运输问题,30,最大流问题,最小支撑树问题,旅行售货员问题,第三讲 图与网络分析,求解过程：(1)启动程序。点击开始程序WinQSB Network Modeling。(2)建立新问题。输入标题名、网络节点数。(3)输入数据。输入节点到节点的距离，需注意弧的方向。(4)求解。,31,新问题窗口：,最短路问题,第三讲 图与网络分析,求解最小支撑树问题 印第安那州的五个城市之间的距离如表所示，现必须建造连接所有这些城市的州公路系统。所需公路的最短长度是多少？,32,第三讲 图与网络分析,33,数据输入窗口,输入上(下)三角数据，下(上)三角可自动得到数据,结果输出窗口,显示网络流量图及行程路线图,第三讲 图与网络分析,求解最短路问题某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。若已知该种设备在各年年初的价格和使用不同年数的设备所需要的维修费用如下表所示。,34,制定更新计划，使总的支付费用最少。,第三讲 图与网络分析,求解最短路问题,35,第三讲 图与网络分析,36,数据输入窗口,结果输出窗口,即第1年初购置，第3年初更新，使用第第5年末，总费用52万元。,37,v1,v2,v3,v4,v5,v7,v8,v6,2,-2,-3,7,5,-3,2,6,4,3,-1,4,4,第三讲 图与网络分析,求解最短路问题求下图中v1点到v8的最短路。(P253),第三讲 图与网络分析,38,第三讲 图与网络分析,求解最大流问题求下图所示网络的最大流。,39,第三讲 图与网络分析,40,第三讲 图与网络分析,41,第三讲 图与网络分析,求解旅行商问题 某巡视组要到6个城市进行调研，从城市A出发，到B、C、D、E、F，最后返回城市A，各城市间距离如下：问应如何安排巡视路线，使总的行程最短？,42,第三讲 图与网络分析,43,运筹学实验,第一讲 实验软件介绍第二讲 动态规划第三讲 图与网络分析第四讲 排队论第五讲 存贮论,44,第四讲 排队论,目的：熟悉WinQSB的QA模块分析简单排队系统M/M分析一般排队系统G/G,45,第四讲 排队论,46,求解过程：(1)启动程序。点击开始程序WinQSB Queuing Analysis。(2)建立新问题。输入标题名、 时间单位，选择输入格式。(3)输入数据。(4)求解。,第四讲 排队论,简单排队系统例1：某加油站有3个油泵，前来加油的汽车平均30辆/h，服从泊松分布；每个油泵加油一辆汽车平均要用5min，服从指数分布。问：（1）平均等待加油的车辆数？（2）每辆车平均等待时间是多少？（3）车到时不需等待立即可加油的概率是多少？（4）至少1个油泵空闲概率是多少？（5）若1个油泵平均每小时服务成本为100元（无论忙期还是空闲），每辆车等待1小时的等待成本30元，问设几个油泵为宜？,47,第四讲 排队论,简单排队系统例1：某加油站有3个油泵，前来加油的汽车平均30辆/h，服从泊松分布；每个油泵加油一辆汽车平均要用5min，服从指数分布。问：（6）若前来加油的汽车发现系统中车辆达到15台时随即离去到别的加油站加油，所造成的该加油站的机会损失为50元，则设几个油泵为宜？,48,队长受限,第四讲 排队论,49,求解系统模拟执行敏感性分析执行系统容量分析,15,数据输入窗口：,第四讲 排队论,50,结果显示窗口：,第四讲 排队论,简单排队系统例2：设有一工人看管5台机器，每台机器正常运转的时间服从负指数分布，平均为15min。当发生故障后，每次修理时间服从负指数分布，平均为12min，试求该系统的有关运行指标。(教程P330,例6),51,第四讲 排队论,一般排队系统G/G例3：某自动取款机平均每2min到达一名顾客，服从泊松分布，顾客取款时间分布律为：试求顾客在系统中平均等待时间是多少？队长平均有多长？解：Y的期望为1.8，标准差为0.8，属于M/G/1模型,52,第四讲 排队论,53,数据输入窗口：,运筹学实验,第一讲 实验软件介绍第二讲 动态规划第三讲 图与网络分析第四讲 排队论第五讲 存贮论,54,第五讲 存贮论,目的：熟悉WinQSB的存贮论模块确定型存贮问题的求解带折扣存贮问题的求解单周期随机型存贮问题的求解多阶段动态需求存贮模型的求解一般存贮策略的分析,55,第五讲 存贮论,56,求解过程：(1)启动程序。点击开始程序WinQSB Inventory Theory and System。(2) 建立新问题。(3)输入数据。 (4)求解。,第五讲 存贮论,确定型存贮问题的求解模型一：不允许缺货，补充时间极短【例1】某商品单位成本为5元，每天保管费为成本的0.1%，每次订购费为10元。已知对该商品的需求是100件/天，不允许缺货。假设该商品的进货可以随时实现。问应该怎样组织进货，才能最经济。 分析需求变化（100件/天200件/天）对进货方式的影响。,57,第五讲 存贮论,确定型存贮问题的求解模型二：允许缺货，补充时间较长【例2】企业生产某种产品，正常生产条件下可生产10件/天。根据供货合同，需按7件/天供货。存贮费每件0.13元/天，缺货费每件0.5元/天，每次生产准备费用为80元，求最优存贮策略。,58,第五讲 存贮论,确定型存贮问题的求解模型三：不允许缺货，补充时间较长【例3】商店经销某商品，月需求量为30件，需求速度为常数。该商品每件进价300元，月存贮费为进价的2%。向工厂订购该商品时订购费每次20元，订购后需5天才开始到货，到货速度为常数，即2件/天。求最优存贮策略。,59,第五讲 存贮论,确定型存贮问题的求解模型四：允许缺货，补充时间极短【例4】商店经销某商品，月需求量为30件，需求速度为常数。该商品每件进价300元，月存贮费为进价的2%。向工厂订购该商品时订购费每次20元，订购后需5天才开始到货，到货瞬间完成。求最优存贮策略。,60,第五讲 存贮论,61,模型一,模型二,模型三,模型四,第五讲 存贮论,带折扣存贮问题的求解模型五：价格与订货批量有关的存贮模型【例5】工厂每周需要零配件32箱，存贮费每箱每周1元，每次订购费25元，不允许缺货。零配件进货时若:(1)订货量1箱9箱时，每箱12元；(2)订货量10箱49箱时，每箱10元；(3)订货量50箱99箱时，每箱9.5元；(4)订货量100箱及以上时，每箱9元。求最优存贮策略。,62,第五讲 存贮论,63,模型五,第五讲 存贮论,单周期随机型存贮问题的求解模型六：需求是离散随机变量【例6】报童每日早晨从报社以批发价购得当日的日报，然后以在市场以零售价售出，每份订购价0.6元，零售价1元；若卖不完，则每份积压报纸退还给报社每份0.2元。以往的销售量统计如下表。应订购多少份报纸为宜？,64,第五讲 存贮论,单周期随机型存贮问题的求解模型七：需求是连续的随机变量【例7】报童每日早晨从报社以批发价购得当日的日报，然后以在市场以零售价售出，每份订购价0.6元，零售价1元；若卖不完，则每份积压报纸退还给报社每份0.2元。若需求均值为140份、标准差为25份的正态分布，订货量应为多少？,65,第五讲 存贮论,模型六,66,模型七,第五讲 存贮论,多阶段动态需求存贮模型的求解【例8】已知1月月初有30件库存产品，要求四月月末有10件库存产品，其他资料如下表，求4月份的最优存贮策略。,67,第五讲 存贮论,一般存贮策略的分析(s,Q)、(s,S)、(R,S)、(R,s,S)【例9】某企业对某种材料的月需求服从参数为（40,2）的正态分布，每次订购费500元，材料进价400元/吨、单位存贮费50元、单位缺货费600元，订货提前期为3天。求(s,Q)、(s,S)。如果每次盘点需要费用500元，求(R,S)、(R,s,S),68,第五讲 存贮论,69,SQ,RsS,SS,RS,运筹学实验,第一讲 实验软件介绍第二讲 动态规划第三讲 图与网络分析第四讲 排队论第五讲 存贮论,70,
