运筹学ppt课件

运筹学必备知识 基础微积分知识：极限，一元函数微分积分基本知识，多元函数的微分、重积分基本知识； 线性代数知识：行列式，矩阵的相关知识，向量相关知识，方程组求解； 概率统计知识：概率的概念及其计算方法，随机变量及其特征，一般分布的特征及其概率的计算方法，基本统计知识。文献资料运筹学手册（1999）徐光辉.北京：科学出版社优化建模与LINDO/LINGO软件谢金星.薛毅.北京：清华大学出版社数学模型谭永基等.上海：复旦大学出版社生产与运作管理制造与服务ProductionandOperationsManagementManufacturingandServicesRichardB.Chase&NicholasJ.Aquilano&F.RobertJacobs北京：机械工业出版社管理科学导论AnIntroductiontoManagementScienceQuantitativeApproachestoDecisionMakingDavidR.Anderson&DennisJ.SveeneyThomasA.Williams北京：机械工业出版社目录线性规划规划软件的应用库存论对策分析图与网络组合分析排队论多目标规划管理信息系统随机规划计算机随机模拟序序一、运筹学性质运筹学是从上世纪三四十年代发展起来的一门新兴学科，它的研究对象是人类对各种资源的运用及筹划活动，目的在于了解和发现这种运用以及筹划活动的基本规律，以便发挥有限资源的最大效益，达到总体、全局最优的目标。运筹学研究的特点有三个：一是强调研究过程的完整性，从问题开始，到构建模型、提出解案、进行检验、建立控制，直到付诸实施为止的所有环节构成了运筹学研究过程的全过程。二是运筹学研究的多学科交叉性，一个复杂的研究对象，需要物理学家、化学家、数学家、经济学家、工程师等组成联合研究队伍，才能了解和完成研究工作。三是运筹学研究强调理论与实践的结合，从这个意义看，研究过程需要从实际出发，不要太过于强调“最优”，必要时先求可行“解”，在看有没有“寻优”的必要。二、我国古代运筹思想斗马术齐将田忌与齐王经常赛马，孙膑发现田忌的马虽然不如齐王的，但相差不多，于是在一次赛马中给田忌献策：以下马对齐王的上马，以上马对齐王的中马，以中马对齐王的下马，结果田忌以一负两胜而获胜。这就是现代运筹学的对策论分支的基本分析方法：从不利的设想出发，不求能大胜，但保不大败，顾全大局。军事后勤北宋时期大科学家、军事家沈括（1031-1095年）关于军事后勤问题，通过分析计算从军各类人员可以背负粮食的基本数据出发，计算了后勤人员与作战士兵在不同行军天数中的比例关系，同时也分析了各种畜牲运粮与人力运粮的比例利弊，最后得出“因粮于敌”的重要决策。即应该从敌国就地征粮，保障前方供应，以便减少后勤人员的比例，提高军队的作战能力。城市规划宋真宗祥符年间（1008-1017年）宫廷失火，需要重建，当时采用了一个取土、弃土、材料运输，以及施工次序统筹安排的综合 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ：先在需要重建的通衢大道上就近取土，取土后，通衢变成深沟，于是引卞水，成为一条人工小河，因此基建材料便可以由水路运入工地；宫殿修成后，又将基建费料弃置沟中，重新建成通衢大道。这样的方案取土、弃土近，运输便，一举三得，节省巨额费用。作物轮作我国北魏时期科学家贾思勰《齐民要术》（533-544年）记载了我国古代劳动人民在耕作、播种、选种、育种、肥田等方面的经验： 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 中按照不同的作物把播种时间分为上、中、下三时；不同的作物连作时。茬口也安排为上、中、下三等，并指出许多作物之间的先后关系，如种谷“二月上旬为上时，三月下旬为中时，四月上旬为下时.”。以“绿豆、小豆底（即前茬作物）为上，麻黍、胡麻次之，芜青、大豆为下.”且谷田不可连作，“必须岁易”。这就是现代运筹学的多阶段决策问题的典范。三、现代运筹学发展史1908年丹麦电话工程师Erlang关于电话局中继线数目的话务理论是现代排队论研究的起源；英国的Lanchester关于战争中兵力部署的理论是现代军事运筹学最早的模型；20年代美国的Levinson关于最优发货量的研究是现代库存论和决策论发展的最初启示；30年代末苏联的康托诺维奇(Konterovitch)总结他研究工作而写成的小册子《生产组织与计划中的数学方法》是线性规划对工业生产问题的典型应用；30年代中后期英国应用新雷达系统对付德国飞机的骚扰的成功，促使了在英美两国各个军事部门都相继成立了运筹小组，直到二战结束，相继转入民用部门。1949年著名的RAND公司成立；1959年，由英、美、法三国运筹学学会发起成立了国际运筹学会联合会（IFORS）；我国1982年加入该运筹学会联合会。线性规划线性规划是运筹学中最基本的模型，从数学上说，是一个特殊的条件极值问题：寻求一个线性函数在一组线性不等式条件下的最大值或最小值。1939年Konterovitch首先提出生产配套问题；接着Hitchcok和Koopmans等分别提出运输问题(1940)和有限资源分配问题(1941)；1947年，Dantzig提出了单纯形方法(simplexmethod)后，线性规划变成为一个独立学科，迅猛发展。1975年，Konterovitch和Koopmans由于创建了经济模型，经济理论以及数理经济方法，获得了Nobel经济学奖。其中包含他们对线性规划的卓越贡献。线性规划由于广泛的应用和强有力的算法，是目前最成熟最成功的运筹学分支之一。案例1生产决策某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 所示，问如制订生产计划，使得该企业获利最大。 资源产品 A B C 资源限量 I 9 8 6 500 II 5 4 7 450 Ⅲ 8 3 2 300 Ⅳ 7 6 4 550 每件产品利润 100 80 70问题理解：1对该企业来说，什么是生产计划？当前资料和条件是不是制定生产计划的确定和必须条件？有没有需要补充的条件？本企业追求利润最大，与什么有关？成本、产量、销售量、收益、利润的关系是什么？234你是否清楚该企业的目标和实际约束（困难）？如何表述（表达）你所希望的目标和约束？假设：该企业产品都能够销售出去，即产量等于销售量。分析问题：1变量设置设A、B、C三种产品的产量分别为根据问题，利润表达为（产品单位）企业所获得的总利润为y（货币单位）。三种产品消耗每种资源的总量不应该超过资源限量，即第I种资源限制条件第II种资源限制条件第III种资源限制条件第IV种资源限制条件 资源产品 A B C 资源限量 I 9 8 6 500 II 5 4 7 450 Ⅲ 8 3 2 300 Ⅳ 7 6 4 550 每件产品利润 100 80 70特别注意，由于A、B、C的产量为绝对产量，故不为负，即那么该问题转化为数学问题就是求三元函数y在多个约束条件下的最大值，表达为s.tsubjectto目标函数条件约束变量约束 资源产品 A B C 资源限量 I 9 8 6 500 II 5 4 7 450 Ⅲ 8 3 2 300 Ⅳ 7 6 4 550 每件产品利润 100 80 70我们称其中，max表示企业目标欲望（利润越大越好，如果是成本等，可能是越小越好，用min表示）。x1，x2，x3表示企业的决策变量，企业的一切行为和结果都与这些决策变量有关。该实际问题的数学模型。12注意到，目标函数和所有约束不等式（等于，大于等于，小于等于）都是决策变量x1，x2，x3的一次函数表达式，在代数上称为线性关系表达式，所以，这个数学模型又称为线性规划数学模型。3目标函数是决策变量的一次和函数，表示目标利润（成本，效率，时间等）可以由各个决策变量所代表的产品各自利润的和（按比例贡献）；第i个线性约束（决策变量的一次和函数）表示每种产品对第i种资源的消耗是按照比例分配的，且这种消耗的累积不超过该种资源要求。如果一个问题的目标是由各个决策变量对应的产品按照比例累积（和），且各种产品对每种资源的消耗都是严格按照比例分配的，那么该问题就可以描述为线性规划模型。模型求解利用目前最好的优化软件lingo8.0，输入模型可以直接求解。模型输入完毕，并且没有错误，按这个按钮就可以。求解结果：Globaloptimalsolutionfoundatiteration:3Objectivevalue:5712.121VariableValueReducedCostX124.242420.000000X20.0000008.484848X346.969700.000000RowSlackorSurplusDualPrice15712.1211.00000020.00000010.6060630.0000000.9090909412.121210.0000005192.42420.000000决策变量非零分量的个数不超过条件约束的个数，且等于独立的条件约束的个数。在建立模型时，尽量写出全部独立的约束不等式。约束越全面，非零分量就越多，也就是，市场信息越复杂，产品就越应该多样化。针对这个求解结果，还应该做解可行性分析，灵敏度分析等，这些都放在对偶分析中讲解。本问题，建立更全面的模型如下：设x1，x2，x3表示A、B、C三种产品的产量；c1，c2，c3表示A、B、C三种产品的市场利润；b1，b2，b3，b4表示I、II、III、IV四种原材料的限量；rij表示第j种产品消耗第i种资源的比例系数(j=1,2,3;i=1,2,3,4)。则数学模型为 资源产品 A(x1) B(x2) C(x3) 资源限量 I 9(r11) 8(r12) 6(r13) 500(b1) II 5(r21) 4(r22) 7(r23) 450(b2) Ⅲ 8(r31) 3(r32) 2(r33) 300(b3) Ⅳ 7(r41) 6(r42) 4(r43) 550(b4) 每件产品利润 100(c1) 80(c2) 70(c3)引入向量和矩阵记法，有其中，价值向量决策向量资源向量技术系数矩阵 资源产品 A(x1) B(x2) C(x3) 资源限量 I 9(r11) 8(r12) 6(r13) 500(b1) II 5(r21) 4(r22) 7(r23) 450(b2) Ⅲ 8(r31) 3(r32) 2(r33) 300(b3) Ⅳ 7(r41) 6(r42) 4(r43) 550(b4) 每件产品利润 100(c1) 80(c2) 70(c3)线性规划模型的向量写法sets:juece/1..3/:x,c;ziyuan/1..4/:b;jishu(ziyuan,juece):a;endsetsmax=@sum(juece:c*x);@for(ziyuan(i):@sum(juece(j):a(i,j)*x(j))<=b(i));data:c=100,80,70;b=500,450,300,550;a=9,8,65,4,78,3,27,6,4;enddata这种输入模型的方法叫做集合式输入法，真对大型模型有利Globaloptimalsolutionfoundatiteration:0Objectivevalue:5712.121VariableValueReducedCostX(1)24.242420.000000X(2)0.0000008.484848X(3)46.969700.000000C(1)100.00000.000000C(2)80.000000.000000C(3)70.000000.000000B(1)500.00000.000000B(2)450.00000.000000B(3)300.00000.000000B(4)550.00000.000000问题的解A(1,1)9.0000000.000000A(1,2)8.0000000.000000A(1,3)6.0000000.000000A(2,1)5.0000000.000000A(2,2)4.0000000.000000A(2,3)7.0000000.000000A(3,1)8.0000000.000000A(3,2)3.0000000.000000A(3,3)2.0000000.000000A(4,1)7.0000000.000000A(4,2)6.0000000.000000A(4,3)4.0000000.000000RowSlackorSurplusDualPrice15712.1211.00000020.00000010.6060630.0000000.9090909412.121210.0000005192.42420.000000sets:juece/1..3/:x,c;ziyuan/1..4/:b;jishu(ziyuan,juece):a;endsetsdata:c=100,80,70;b=500,450,300,550;a=9,8,65,4,78,3,27,6,4;enddatamax=@sum(juece:c*x);@for(ziyuan(i):@sum(juece(j):a(i,j)*x(j))<=b(i));集合段模型段数据段集合段以sets：开始，以endsets结束。给出下标集合名称，下标范围，以及与此下标有关的符号变量。数据段是以data：开始，enddata结束；注意向量都是行写法，每个向量间用“；”隔开；注意矩阵的写法，先行后列输入方式，每行间回车，完毕用分号。模型段主要书写目标函数和约束函数，各行之间用分号隔开，变量默认非负。案例2运输问题某部门有3个生产同类产品的工厂（产地），生产的产品由4个销售点（销地）出售，各工厂的生产量、各销售地的销售量（单位：吨）以及各个工厂到各个销售点的单位运价（元/吨）表示在下表中，要求研究产品如何调运，才能使得总运费最小。 产地\销地 B1 B2 B3 B4 产量 A1 4 12 4 11 16 A2 2 10 3 9 10 A3 8 5 11 6 22 销量 8 14 12 14问题理解1什么叫做一个完整的调运方案？2产地的总产量和销售地的总销售量的关系如何？3总运费与什么有关？4产地的调出量和销地的销售量应该有什么限制？分析问题并建立模型设xij表示从第i产地调往第j销地的调运量；i=1,2,3;j=1,2,3,4，cij表示从第i产地调往第j销地的单位运费（运价）；ai表示第i产地的产量；bj表示第j销地的销量；y表示总运费。A1A2A3B4B3B2B1a1a2a3b1b2b3b4x11x21x31x12x22x32x13x23x33x14x24x34运输问题的网络示意图该问题的总产量等于总销售量，所以有每个销地的销量约束每个产地的产量约束各条可能路线运费总和即该运输问题的数学模型为 产地\销地 B1 B2 B3 B4 产量 A1 4(c11) 12(c12) 4(c13) 11(c14) 16(a1) A2 2(c21) 10(c22) 3(c23) 9(c24) 10(a2) A3 8(c31) 5(c32) 11(c33) 6(c34) 22(a3) 销量 8(b1) 14(b2) 12(b3) 14(b4)运输问题的进一步讨论1产销不平衡产大于销，即这时，数学模型为产小于销，即2计算程序编写注意本问题所涉及的不同下标范围，不同下标形式的字符变量有哪些？单下标和双下标的不同定义方式。 a书写集合段单下标集合有产地产量集合和销地销量集合，与这两个集合有关的是运价和运量两个集合，称为派生集合（生成集合），或者称为由产量集合和销量集合组合成的笛卡尔集合，定义如下：endsetschanliang/1..3/:a;表示生成产量a(1),a(2),a(3);xiaoliang/1..4/:b；表示生成销量b(1),b(2),b(3),b(4)值得注意的是，这里的1,2,3,4表示变量下标自然顺序，不因为书写而改变。sets:chanliang/1,2,3/:a;xiaoliang/1,2,3,4/:b;yunjia(chanliang,xiaoliang):c,x;集合初始语句与前两个变量的下标都有关系的是运价和运量，所以，派生集合yunjia是双下标，第一个下标是chanliang集合的下标，第二下标是xiaoliang集合的下标,决策变量x和价值系数c都与此集合下标有关，表示为c(i,j),i=1,2,3;j=1,2,3,4;x(i,j),i=1,2,3;j=1,2,3,4。表示集合定义结束。注意，集合定义中，每个集合定义后，都用分号结束，每个集合有关的变量之间用逗号隔开。b书写模型段把所有的c(i,j)*x(i,j),求和，则用如下表达方式c(1,1)*x(1,1)+c(1,2)*x(1,2)+c(1,3)*x(1,3)+c(1,4)*x(1,4)+…+c(3,1)*x(3,1)+…+c(3,4)*x(3,4)。min=@sum(yunjia(i,j):c(i,j)*x(i,j));min=@sum(yunjia:c*x);对yunjia集合中每个元素(i,j),对c(i,j)*x(i,j)求和，表示如果对每对下标都求和，则上述两种表达方式一样。对每个销地，所有产地运来的货物量恰好等于销售量：@for(xiaoliang(j):@sum(chanliang(i):x(i,j))=b(j));对每个产地，运出的货物量总合恰好等于该产地的产量：@for(chanliang(i):@sum(xiaoliang(j):x(i,j))=a(i));data:a=16,10,22;B=8,14,12,14;C=4,12,4,112,10,3,98,5,11,6;enddata 产地\销地 B1 B2 B3 B4 产量 A1 4(c11) 12(c12) 4(c13) 11(c14) 16(a1) A2 2(c21) 10(c22) 3(c23) 9(c24) 10(a2) A3 8(c31) 5(c32) 11(c33) 6(c34) 22(a3) 销量 8(b1) 14(b2) 12(b3) 14(b4)sets:chanliang/1..3/:a;xiaoliang/1..4/:b;yunjia(chanliang,xiaoliang):c,x;endsetsmin=@sum(yunjia:c*x);@for(chanliang(i):@sum(xiaoliang(j):x(I,j))=a(i));@for(xiaoliang(j):@sum(chanliang(i):x(I,j))=b(j));data:a=16,10,22;B=8,14,12,14;C=4,12,4,112,10,3,98,5,11,6;enddata程序组合及调试：注意：这三个模块，在lingo中放置与顺序无关。且，lingo读取程序与字母大小写无关。如果是产销不平衡，把某些=改成≤，≥即可。sets:chanliang/1..3/:a;xiaoliang/1..4/:b;yunjia(chanliang,xiaoliang):c,x;endsetsdata:a=16,10,22;B=8,14,12,14;C=4,12,4,112,10,3,98,5,11,6;enddatamin=@sum(yunjia:c*x);@for(chanliang(i):@sum(xiaoliang(j):x(I,j))=a(i));@for(xiaoliang(j):@sum(chanliang(i):x(I,j))=b(j));Globaloptimalsolutionfoundatiteration:6Objectivevalue:244.0000VariableValueReducedCostX(1,1)4.0000000.000000X(1,2)0.0000002.000000X(1,3)12.000000.000000X(1,4)0.0000000.000000X(2,1)4.0000000.000000X(2,2)0.0000002.000000X(2,3)0.0000001.000000X(2,4)6.0000000.000000X(3,1)0.0000009.000000X(3,2)14.000000.000000X(3,3)0.00000012.00000X(3,4)8.0000000.000000与运输问题有关的进一步思考：12该问题一般从生产销售单位考虑，如果从运输公司出发，会怎么样？有这类现象吗？那种场合会出现？VariableValueReducedCostX(1,1)4.0000000.000000X(1,2)0.0000002.000000观察这组最优解，如果想要直接从产地1运输货物到销地2，应该有什么政策？如何实施。3如果运送的货物有若干种类，怎么办？这些货物有些可以混合运输，有些则不能混合运送，怎么办？如果有不同的交通运输工具怎么分配？如果货物有运输时间限制，怎么办？垄断案例3货物装载问题一艘轮船分前、中、后三个舱位，它们的容积与最大允载重量如表1。现有三种货物待运，已知有关数据列在表2。又为了安全，前、中、后的实际载重量大体保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间的载重量比例上偏差不超过15%，前、后舱之间不超过10%。问轮船应装载A、B、C各多少件才能使运费收入最大？表1三舱的允载重量与体积约束表2三种货物的数量指标问题理解1一个完整的货物装载方案是什么？2如何理解“为了安全，前、中、后的实际载重量大体保持各舱最大允许载重量的比例关系。”建立模型设xij表示第i种商品装入第j舱的件数，其中，i=1,2,3表示A、B、C三种商品；j=1,2,3表示前、中、后三个舱位。商品参数符合变量：ai表示第i商品的数量上限；i=1,2,3vi表示第i商品的单位体积；wi表示第i商品的单位重量；pi表示第i商品的运输单价；船的装载参数约束：uj表示第j舱位的体积上限；mj表示第j舱位的重量上限；J=1,2,3;舱位间的重量比利系数：t1表示中舱与前、后舱位的载重比利系数；t2表示前后舱位之间载重比利系数。s.t装入三个舱位的商品带来的总运费。装入的每种商品的总件数不超过商品总数。每个舱位，装入的三种商品重量总和不超过舱位最大载重量。每个舱位，装入的三种商品总体积不超过舱位最大体积容量。前舱的实际载重量和中舱的实际载重量的偏差不超过0.15%后舱载重量与中舱载重量的偏差不超过0.15后舱与前舱载重量的偏差不超过10%。计算程序sets:shangpin/1..3/:a,w,v,p;cangwei/1..3/:u,m;fenpei(shangpin,cangwei):x;endsetsdata:a=600,1000,800;v=10,5,7;w=8,6,5;p=1000,700,600;m=2000,3000,1500;u=4000,5400,1500;t1=0.15;t2=0.10;enddatamax=@sum(shangpin(i):p(i)*@sum(cangwei(j):x(i,j)));@for(shangpin(i):@sum(cangwei(j):x(i,j))<=a(i));@for(cangwei(j):@sum(shangpin(i):w(i)*x(i,j))<=m(j));@for(cangwei(j):@sum(shangpin(i):v(i)*x(i,j))<=u(j));(1-t1)*@sum(shangpin(i):w(i)*x(i,2))<=@sum(shangpin(i):w(i)*x(i,1));(1-t1)*@sum(shangpin(i):w(i)*x(i,2))<=@sum(shangpin(i):w(i)*x(i,3));(1-t2)*@sum(shangpin(i):w(i)*x(i,1))<=@sum(shangpin(i):w(i)*x(i,3));Globaloptimalsolutionfoundatiteration:5Objectivevalue:608921.6VariableValueReducedCostX(1,1)208.33330.000000X(1,2)220.58820.000000X(1,3)75.000000.000000X(2,1)0.00000050.00000X(2,2)0.00000050.00000X(2,3)150.00000.000000X(3,1)0.00000025.00000X(3,2)0.00000025.00000X(3,3)0.00000040.00000特别注意，模型在lingo中的输入方式：Max=@sum(shangpin(i):p(i)*@sum(cangwei(j):x(i,j)));0.85*@sum(shangpin(i):w(i)*x(i,2))<=@sum(shangpin(i):w(i)*x(i,1));0.85*@sum(fenpei(i,j)|j#eq#2:w(i)*x(i,j))<=@sum(shangpin(i)|j#eq#1:w(i)*x(i,j));优化软件介绍Lingo的优化软件的使用方法Lingo安装完成，启动后，可以看到如下界面+(加法）-（减法）*（乘法）/(除法）^(乘幂）#AND#(与)#OR#(或)#NOT#(非)#EQ#(等于)#NE#(不等于)#GT#(大于)#GE#(大于等于)#LT#(小于)#LE#(小于等于)<(<=)小于等于=（等于）>(>=)大于等于算术运算符号逻辑运算符号逻辑运算的结果只有“真”（TRUE)和“假”（FALES)，lingo用1表示True,其它的都是False。关系运算符号在lingo程序下字母的大小写是没有区别的Lingo8.0的基本运算符号常见运算函数@abs@cos@exp@floor(取整）@lgm(自变量的gama函数的自然对数）@smax(list)（返回列数的最大值）@smin@sin@tan@sign(示性函数）变量约束函数@gin（取整约束）@bin（0-1变量约束）@free（自由变量约束）@bnd（上下界约束函数）Lingo基本函数@function(setname(set_index_list)|condition：expression_list);集合循环函数@for对集合setname的每个元素独立生成约束，约束由expression_list描述。@max、@min、@sum依次返回集合setname上的表达式的最大值、最小值、和。0.85*@sum(fenpei(i,j)|j#eq#2:w(i)*x(i,j))<=@sum(shangpin(i)|j#eq#1:w(i)*x(i,j));其中，function是集合函数名，有for,max,min,sum四种；setname是集合名；set_index_list是集合索引列表；condition是逻辑表达式描述的条件；expression_list是一个表达式，对@for函数可以有一组表达式。@for(jihe1(i)|i#LE#5#and#i#GE#2:x(i)<=2);利用sets建立一个序列的下标集合，这个问题就是建立了x1-x6,y1-y7这13个变量，Z11-z67由前面两个集合的下标共同生成了42个变量。由sets:开始，endsets结束。sets:jihe1/1..6/:x;jihe2/1..7/:y;link(jihe1,jihe2):z;endsets表示的意义为基本运算、集合、函数的表达@sum(jihe2(j)|j#NE#3:y(j))<=4;@for(jihe1(k)|k#GE#2:@gin(x));@for(jihe1:@bnd(1,x,10)）;@for(jihe2:@bnd(0,y,20));表示表示xk取整数，yk取0-1变量，k≥2表示对所有i，xi满足1≤xi≤10对所有j，yj满足0≤yi≤20@for(jihe2(k)|k#GE#2:@bin(y));求和的表达sets:subnb/1..10/:x;endsets@sum(subnb(i):x(i))=a;sets:subnb1/1..5/:;subnb2/4,5,6,7,8/:;link(subnb1,subnb2):c,x;endsetsMin=@sum(link(i,j):c(i,j)*x(i,j));或写成Min=@sum(link:c*x);写出下列lingo程序表示的意义sets:sub1/1..5/:x,y;sub2/3,4,5,9/:z;link(sub1,sub2):p,q;endsetsmax=@sum(link:p*q+10);@for(sub2(i)|i#ne#4:z(i)<=4);@for(sub1(j)|j#LT#3:x(j)>=3;y(j)>=3);@for(link(i,j):x(i)*z(j)<=10-p(i,j);y(i)*Z(j)<=15-q(i,j));@for(sub1:@gin(x);@gin(y));@for(sub2:@gin(z));注意，i下标只下标顺序，不是真的3，4，5，9这些值;案例4指派问题某商业公司计划开办五家新的商店，为了尽早建成营业，商业公司决定由5家建筑公司来分别承建。已知建筑公司Ai对新商店Bj的承建报价为（万元）为Cij见下表。商业公司应当对5家建筑公司怎样的分配建筑任务，才能使得总的建筑费用最低？ Ai\Cij\Bj B1 B2 B3 B4 B5 A1 4 8 7 15 12 A2 7 9 17 14 10 A3 6 9 12 8 7 A4 6 7 14 6 10 A5 6 9 12 10 6问题理解1如何理解：为了尽早建成营业，商业公司决定由5家建筑公司来分别承建。2根据问题，如何才算是一个完整的可行任务分配方案？根据问题“分别承建”，即每家建筑公司只承建一家商业公司，一家商业公司只承包给一家建筑公司。即n个人去完成n项任务，每个人只能完成一项，每项任务只能有一个人完成。这类问题叫做单指派问题。如果人数和任务数不等，即m个人完成n项任务，这样的指派问题，称为复指派问题。根据问题叙述，比如，A1（B5），A2（B4），A3（B3），A4（B2），A5（B1），就是一个完整的满足要求的任务分配方案。剩下的问题就是在这些可能的分配方案中寻找最优方案。补充知识0-1变量满足某个条件p不满足条件p例如条件和只需要满足一个条件就行。则令那么两个不等式条件满足且只需要满足一个的数学等价为其中M为任意大正数。当y1=1时，y2=0，第1个不等式有效，如果y1=0，y2=1，第2个不等式有效。由于y1+y2=1，故有且只有1个不等式有效。思考如果有m个不等式，只要求有1个不等式有效，怎么办？如果有m个不等式，要求有p个不等式有效怎么办？建立指派问题的数学模型设置0-1变量Cij表示第i建筑公司对第j商业公司的成本（造价），i=1,2,3,4,5;j=1,2,3,4,5注意：这里一共定义了25个0-1变量。但是，根据问题，有且只有5个变量取1，其它的20个变量取0。针对每个商业公司，由且只能由一家建筑公司承包。对每家建筑公司，仅能承包一家商业公司的建筑。指派问题求解sets:shangdian/1..5/:;jianzhugs/1..5/:;link(shangdian,jianzhugs):x,c;endsetsdata:c=4,8,7,15,127,9,17,14,106,9,12,8,76,9,14,6,106,9,12,10,6;enddatamin=@sum(link:c*x);@for(shangdian(j):@sum(jianzhugs(i):x(i,j))=1);@for(jianzhugs(i):@sum(shangdian(j):x(i,j))=1);@for(link:@bin(x));Globaloptimalsolutionfoundatiteration:0Objectivevalue:34.00000VariableValueReducedCostX(1,3)1.0000007.000000X(2,2)1.0000009.000000X(3,1)1.0000006.000000X(4,4)1.0000006.000000X(5,5)1.0000006.000000根据计算，B1建筑公司承建A3商业公司，B2建筑公司承建A2商业公司，B3建筑公司承建A1商业公司，B4建筑公司承建A4商业公司，B5建筑公司承建A5商业公司，最小总造价为34（万元）。案例5固定费用问题有三种资源用于生产三种产品，资源量、产品单件可变费用、售价、资源单位消耗量及组织三种产品生产的固定费用如下表。求制订一个生产计划，使总利润最大。 产品1 产品2 产品3 资源量 资源A 2 4 8 500 资源B 2 3 4 300 资源C 1 2 3 100 单件可变费 4 5 6 固定费用 100 150 200 单件售价 8 10 12问题分析利润=总收入-可变成本-固定成本。如果某类产品的产量为0，则可变成本为0，这时，固定成本也应该为0，相反，如果可变成本大于0，则固定成本一定不为0。所以，应该考虑到产品可生产也可不生产。变量设置：bj表示第j种资源的限量；j=1，2，3ci表示第i种产品的售价；i=1，2，3di表示第i种产品的单件固定费用；ei表示第i种产品的单件可变费用；fij表示第i种产品消耗第j种资源的单位消耗量。yi表示第i种产品是否生产的选择xi表示第i种产品的产量；yi=0，表示第i种产品不生产，即xi=0；否则yi=1，表示第i种产品生产，即xi>0;建立模型s.t其中，M为产品的最大产量，根据问题，产品的最大产量不超过100件，故设M=100；计算程序：sets:ziyuan/1..3/:b;chanpin/1..3/:c,x,y,d,e;link(chanpin,ziyuan):f;endsetsdata:b=500,300,100;c=8,10,12;e=4,5,6;d=100,150,200;f=2,2,14,3,28,4,3;M=100;enddatamax=@sum(chanpin:c*x)-@sum(chanpin:e*x)-@sum(chanpin:d*y);@for(ziyuan(j):@sum(chanpin(i):f(i,j)*x(i))<=b(j));@for(chanpin:x<=M*y);@for(chanpin:@bin(y));Globaloptimalsolutionfoundatiteration:4Objectivevalue:300.0000VariableValueReducedCostX(1)100.00000.000000X(2)0.0000000.000000X(3)0.0000001.500000Y(1)1.000000-50.00000Y(2)0.000000150.0000Y(3)0.000000200.0000计算结果：根据计算结果，只需要安排生产第1种产品，可以获得最大利润300。案例6混合配料问题某糖果厂用原料A，B，C加工成三种不同牌号的糖果甲、乙、丙。已知各种牌号糖果中A，B，C含量、原料成本、各种原料的每月限制用量、三种牌号糖果的单位加工费及售价如下表所示。问该厂每月生产这三种牌号的糖果各多少kg，使该厂获利最大。试建立这个问题的线性规划的数学模型。分析问题设xi表示第i种糖果的产量(kg)，i=1,2,3;yij表示第i种糖果中原料j的含量；i=1,2,3,j=1,2,3qi表示每种糖果的加工费；pi表示每种糖果的售价；dj表示每种原料的单价；bj表示每种原料的每月限用量；cij表示第i种糖果中原料j的含量要求（%）。s.tmax=@sum(tangguo:p*x)-@sum(tangguo:q*x)-@sum(yuanliao(j):d(j)*@sum(tangguo(i):y(i,j)));@for(tangguo(i):x(i)=@sum(yuanliao(j):y(i,j)));@for(yuanliao(j):@sum(tangguo(i):y(i,j))<=b(j));@for(link(i,j)|j#le#2:y(i,j)>=x(i)*c(i,j));@for(link(i,j)|j#ge#3:y(i,j)<=x(i)*c(i,j));sets:tangguo/1..3/:p,x,q;yuanliao/1..3/:d,b;link(tangguo,yuanliao):y,c;endsetsdata:c=0.6,0.3,00,0,00.2,0.5,0.6;p=3.4,2.85,2.25;q=0.5,0.4,0.3;d=2.0,1.5,1.0;b=200,200,1200;enddataVariableValueReducedCostX(1)333.33330.000000X(2)66.666670.000000Y(1,1)200.00000.000000Y(1,2)133.33330.000000Y(2,2)66.666670.000000Globaloptimalsolutionfoundatiteration:0Objectivevalue:430.0000案例7钢管下料问题（2）零售商如果采用的不同切割方式太多，将会导致过程复杂化，从而增加成本，所以该零售商决定采用不同的切割方式不能超过3种，此外，用户需要（1）中的3种钢管外，还需要10根长5m的钢管，问应如何下料才省？某钢管零售商从钢管厂家进货，将钢管按照顾客要求的长度进行切割，成为下料。假定进货时的原料钢管的长度都是19米。（1）现有一客户需要50根长4m、20根长6m和15根长8m的钢管，问应该如何下料，最省？对于下料问题，首先需要确定下料的组合方式：切割模式，即按照客户要求的长度在原料钢管上安排的切割组合。例如，一根长19m的原料钢管，可以切割成3根长4m的钢管，剩下7米；或者切割成4m、6m和8m的钢管个1根，剩下1m,…显然，在所有的切割模式中，余料大于客户要求得最短尺寸的，时不合理的切割。我们将所有的切割模式组合如下表：问题1分析1一根19米的钢管，怎么切割，有哪些可能的切割？2钢管的余料如何设置？3如何理解“最省”？这里的目标是材料最省：余料最少和原料钢管数最少两种理解，我们下面就两种方式分别求解。 模式 4m根数 6m根数 8m根数 余料/m 1 4 0 0 3 2 3 1 0 1 3 2 0 1 3 4 1 2 0 3 5 1 1 1 1 6 0 3 0 1 7 0 0 2 3建立问题1模型设x(i)表示按照上表排列的第i种方式切割的原料钢管的根数（i=1,2,3,4,5,6,7）则钢管余料最少原料钢管用料最省客户要求以及变量取整要求。问题2分析在问题1中的切割模式中，引入5米的用户需求，重新建立规划模型即可。 模式 4m根数 6m根数 8m根数 5m根数 余料/m 1 4 0 0 0 3 2 3 1 0 0 1 3 2 0 1 0 3 4 1 2 0 0 3 5 1 1 1 0 1 6 0 3 0 0 1 7 0 0 2 0 3 8 1 0 0 3 0 9 0 0 1 2 1 10 0 1 0 2 3 11 2 0 0 2 1令x(i)表示第i种模式切割的原料钢管根数；y(i)=1表示选择第i种切割模式；i=1,2,…,16y(i)=0表示不选择第i种切割模式。a(i,j)表示第i种切割模式生产第j用户规格的钢管根数；j=1,2,3,4b(i)表示第i种切割模式产生的余料(m/根）；c(j)表示第j用户钢管的需求数。 模式 4m根数 6m根数 8m根数 5m根数 余料 12 0 1 1 1 0 13 1 0 1 1 2 14 2 1 0 1 0 15 0 2 0 1 2 16 3 0 0 1 2s.tmin=@sum(moshi:x);!min=@sum(moshi:b*x);@for(yonghu(j):@sum(moshi(i):x(i)*y(i)*a(i,j))>=c(j));@sum(moshi:y)<=3;@for(moshi:x/100<=y);@for(moshi:y<=x);@for(moshi:@gin(x));@for(moshi:@bin(y));sets:moshi/1..16/:x,y,b;yonghu/1..4/:c;link(moshi,yonghu):a;endsetsa=4,0,0,03,2,0,02,0,1,01,2,0,01,1,1,00,3,0,00,0,2,01,0,0,30,0,1,20,1,0,22,0,0,20,1,1,11,0,1,12,1,0,10,2,0,13,0,0,1;data:b=3,1,3,3,1,1,3,0,1,3,1,0,2,0,2,2;c=50,20,15,10;enddata问题2的计算程序及结果第1个目标计算结果Globaloptimalsolutionfoundatiteration:1Objectivevalue:25.00000VariableValueReducedCostX(2)10.000000.000000X(3)5.0000000.000000X(13)10.000000.000000Y(2)1.000000-5.000000Y(3)1.0000000.000000Y(13)1.000000-5.000000第2个目标计算结果Globaloptimalsolutionfoundatiteration:1Objectivevalue:0.000000VariableValueReducedCostX(12)15.000000.000000X(14)25.000000.000000Y(12)1.0000000.000000Y(14)1.0000000.000000关于问题2的进一步讨论按照上述问题2的方法，增加一个客户要求，要写出全部切割模式，非常复杂，如果再增加客户，问题规模庞大，所以，必须对方法进一步讨论。换一个角度考虑，一根长19m的原料钢管，不管采用什么切割模式，总是希望得到用户要求的4m、5m、6m、8m的规格钢管。不妨设那么问题需要的不超过3种切割模式的每种切割模式都可能会产生这些不同规格的需求钢管，所以设置如下变量：x(i,j)表示第i种切割模式分别产生第j规格的钢管的根数；其中，i=1,2,3；j=1,2,3,4表示4种规格要求.y(i)表示按照第i切割模式切割的原料钢管根数；c(j)表示第j用户要求的规格钢管根数；b(j)表示第j用户钢管的规格(m)s.t.非线性整数规划sets:moshi/1..3/:y;yonghu/1..4/:b,c;link(moshi,yonghu):x;endsetsdata:b=4,5,6,8;c=50,10,20,15;enddatamin=@sum(moshi:y);!min=@sum(moshi(i):y(i)*(19-@sum(yonghu(j):b(j)*x(i,j))));@for(yonghu(j):@sum(moshi(i):y(i)*x(i,j))>=c(j));@for(moshi(i):16<=@sum(yonghu(j):b(j)*x(i,j)));@for(moshi(i):@sum(yonghu(j):b(j)*x(i,j))<=19);@for(link:@gin(x));@for(moshi:@gin(y));Globaloptimalsolutionfoundatiteration:7968Objectivevalue:28.00000第1个目标计算结果VariableValueReducedCostY(1)10.000001.000000Y(2)8.0000001.000000Y(3)10.000001.000000X(1,1)3.0000000.000000X(1,3)1.0000000.000000X(2,4)2.0000000.000000X(3,1)2.0000000.000000X(3,2)1.0000000.000000X(3,3)1.0000000.000000第2个目标计算结果sets:moshi/1..3/:y;yonghu/1..4/:b,c;link(moshi,yonghu):x;endsetsdata:b=4,5,6,8;c=50,10,20,15;enddata!min=@sum(moshi:y);min=@sum(moshi(i):y(i)*(19-@sum(yonghu(j):b(j)*x(i,j))));@for(yonghu(j):@sum(moshi(i):y(i)*x(i,j))>=c(j));@for(moshi(i):@sum(yonghu(j):b(j)*x(i,j))>=16);@for(moshi(i):@sum(yonghu(j):b(j)*x(i,j))<=19);@for(link:@gin(x));@for(moshi:@gin(y));@for(moshi:y<=15);@for(link:x<=3);在解决第1个问题基础上，增加这两个条件，计算收敛速度快10倍。否则，可能存不可行。这个上界不宜太小，也不宜太大！！Globaloptimalsolutionfoundatiteration:4862Objectivevalue:0.000000VariableValueReducedCostY(1)14.000000.000000Y(2)15.000000.000000Y(3)11.000000.000000X(1,1)2.0000000.2596895E-07X(1,2)1.0000000.000000X(1,3)1.0000000.1517287E-06X(2,2)1.0000000.000000X(2,3)1.0000000.1067591E-06X(2,4)1.0000000.4043221E-07X(3,1)2.0000000.000000X(3,2)1.0000000.000000X(3,3)1.0000000.000000航班编排问题某航空公司经营A，B，C三个城市的航线，这些航线每天班次起飞与到达时间如下表所示。设飞机在机场停留的损失费大致与停留时间的平方成正比，又每架飞机从降落到下班起飞至少需2小时准备时间，试决定一个使停留费用损失为最小的分派飞行方案。航班号 起飞城市 起飞时间 到达城市 到达时间101 A9：00B 12：00102 A 10：00 B 13：00103 A 15：00B 18：00104 A 20：00 C 24：00航班号 起飞城市 起飞时间 到达城市 到达时间105 A 22：00C 2：00106 B04：00A07：00107 B 11：00A 14：00108 B 15：00A 18：00109 C07：00A 11：00110 C15：00A 19：00111 B13：00C 18：00112 B 18：00  C 23：00113 C 15：00B 20：00114 C 07：00B 12：00问题分析根据所给资料，城市A每天有五个航班进出，城市B每天有5个航班进出，城市C每天有4个航班进出，根据已知数据，绘制成如下图的飞行网络图部分合理假设（1）飞机在某个城市，经过2小时准备时间后，任何时刻都可以起飞，且安全；（2）飞机到达一个城市后，经准备，可以飞往任何下一个城市；（3）同一架飞机不能够同时出现两个不同的航线上；（4）飞机的停留损失费用为停留时间的平方倍；（5）计算一天24小时内的损失总费用；（6）航班准时起飞，准时到达；先将达到航班和离开航班的时间对应绘制表1和表2表1 toform A B C A \ 9-12(101)10-13(102)15-18(103) 20-24(104)22-2(105) B 4-7（106）11-14（107）15-18（108） \ 13-18(111)18-23(112) C 7-11（109）15-19(110) 7-12(113)15-20(114) \到达离开表2x(i,j)城市A第i航班飞机用于第j航班，x(i,j)=1,否则，x(i,j)=0y(i,j)城市B第i航班飞机用于第j航班，y(i,j)=1,否则，y(i,j)=0z(i,j)城市C第i航班飞机用于第j航班，z(i,j)=1,否则，z(i,j)=0对于城市A各种可能的调度等待时间时间如表3表3t1(i,j),t2(i,j),t3(i,j)城市A,B,C的第i航班飞机用于第j航班的停留时间；变量设置 t1(i,j) 1 2 3 4 5 6 2 3 8 13 15 7 22 23 4 9 11 8 19 20 25 6 8 9 15 16 21 2 4 10 14 15 20 25 3城市B的各种调度等待时间如表4城市C的各种调度等待时间如表5表4表5 t2(i,j) 6 7 8 11 12 1 16 23 3 25 6 2 15 22 2 24 5 3 10 17 21 19 24 13 16 23 3 25 6 14 8 15 19 17 22 t3(i,j) 9 10 13 14 4 7 7 15 15 5 7 7 15 15 11 13 13 21 21 12 8 8 16 16由于各个航班按时到达和出发，故不用考虑航线之间飞机调用的冲突问题，故只需要考虑每个城市的飞机的调度问题。且最优调度方案与飞行时间的比例系数无关。所以模型为建立模型城市A的航班调度约束。城市B的航班调度约束。城市C的航班调度约束。