第四章 整数规划

运筹学第四章多目标规划

习题四 4.1 分别用图解法和单纯形法求解下述目标规划问题 （1） min z ＝p 1（+1d ＋+2d ）＋p 2-3d st. －x 1＋ x 2＋ d －1－ d ＋ 1＝1 －0.5x 1＋ x 2＋ d － 2－d ＋ 2＝2 3x 1＋3x 2＋ d －3－ d ＋3＝50 x 1，x 2≥0；d －i ，d ＋i ≥0（i =1，2，3） （2） min z ＝p 1（2+1d ＋3+2d ）＋p 2-3d ＋p 3+4d st. x 1＋ x 2＋d －1－d ＋ 1 ＝10 x 1 ＋d －2－d ＋2 ＝4 5x 1＋3x 2＋d －3－d ＋3 ＝56 x 1＋ x 2＋d －4－d ＋4 ＝12 x 1，x 2≥0；d －i ，d ＋i ≥0（i =1， (4) 4.2 考虑下述目标规划问题 min z ＝p 1（d ＋1＋d ＋2）＋2p 2d －4＋p 2d －3＋p 3d －1 st. x 1 ＋d －1－d ＋1＝20 x 2＋d －2－d ＋2＝35 －5x 1＋3x 2＋d － 3－d ＋ 3＝220 x 1－x 2＋d －4－d ＋4＝60 x 1，x 2≥0；d －i ，d ＋i ≥0（i =1， (4) （1）求满意解； （2）当第二个约束右端项由35改为75时，求解的变化； （3）若增加一个新的目标约束：－4x 1＋x 2＋d －5－d ＋5＝8，该目标要求尽量达 到目标值，并列为第一优先级考虑，求解的变化； （4）若增加一个新的变量x 3，其系数列向量为（0，1，1，－1）T ，则满意解如何变化？ 4.3 一个小型的无线电广播台考虑如何最好地来安排音乐、新闻和商业节目时间。依据法律，该台每天允许广播12小时，其中商业节目用以赢利，每小时可收入250美元，新闻节目每小时需支出40美元，音乐节目每播一小时费用为17.50美元。法律规定，正常情况下商业节目只能占广播时间的20％，每小时至少安排5分钟新闻节目。问每天的广播节目该如何安排？优先级如下： P 1：满足法律规定要求； P 2：每天的纯收入最大。 试建立该问题的目标规划模型。

运筹学第四章

运筹学第四章习题答案 4.1若用以下表达式作为目标规划的目标函数，其逻辑是否正确？为什么？ （1）max ｛- d -+d ｝ （2）max ｛-d ++ d ｝ （3）min ｛-d ++d ｝ （4）min ｛-d -+ d ｝ （1）合理，令f （x ）+- d -+ d =b,当f （x ）取最小值时，- d -+ d 取最大值合理。 (2)不合理，+ d 取最大值时，f （x ）取最大值，- d 取最大值时，f （x ）应取最小值 （3）合理，恰好达到目标值时，- d 和+ d 都要尽可能的小。 （4）合理，令f （x ）+- d -+ d =b,当f （x ）取最大值时，- d -+ d 取最小值合理。 4.2用图解法和单纯形法解下列目标规划问题 （1）min ｛P 13 +d ，P 2- 2d ，P 3（- 1d ++ 1d ）｝ 24261121=-+++- d d x x 52221=-+++- d d x x 155331=-++-d d x 3,2,1,0,,,21=≥+-i d d x x i i （2）min{P 1(+++43d d ),P 2+1d ,P 3-2d ,P 4(--+4 35.1d d )} 401121=-+++-d d x x 1002221=-++--d d x x 30331=-++-d d x 15442=-++-d d x 4,3,2,1,0,,,21=≥+-i d d x x i i (1)图解法

0 A B C X 1 由图可知，满足域为线段EG,这就是目标规划方程的解，可求得：E,G 的坐标分别为（0，12），（3,3） 故该问题的解为)312,3()3,3()12,0(21221a a a a a +=+ )1,0,(2121=+≥a a a a (2)图解法 2 1 由图可知，满足域为线段AB A(25,15),B(30,10)故该问题的解可 表示为)1015,3025()10,30()15,25(212121a a a a a a ++=+ )1,0(212,1=+≥a a a a

运筹学课件第四章目标规划

第四章目标规划 一、学习目的与要求 1、掌握目标规划的图解法模型； 2、掌握目标规划的单纯形的求解模型； 3、掌握目标规划的灵敏度分析。 二、课时6学时 第一节目标规划问题及其数学模型 一、问题的提出 应用线性规划可以处理许多线性系统的最优化问题，但线性规划，整数规划和非线性规划都只有一个目标函数，而在实际问题中，常常需要考虑多个目标：如设计一个新产品的工艺过程，不仅希望获利大，而且希望产量高，消耗低，质量好，投入少等。而这些目标之间通常是矛盾的。所以这类问题多目标问题比单目标问题要复杂得多，我们把这一类问题称为目标规划问题。 目标规划与线性规划相比，有以下优点： 1.线性规则只讨论一个线性目标函数在一组线性约束条件下的极值问题。 实际问题中，往往要考虑多个目标的决策问题，这些目标可能互相矛盾，也可能没有统一的度量单位，很难比较。目标规划就能够兼顾地处理多种目标的关系，求得更切合实际的解。 2.线性规划是在满足所有约束条件的可行解中求得最优解。而在实际问题 中往往存在一些相互矛盾的约束条件，如何在这些相互矛盾的约束条件下，找到一个满意解就是目标规划所要讨论的问题。 3.线性规划问题中的约束条件是不分主次、同等对待的，是一律要满足的“硬约束”。而在实际问题中，多个目标和多个约束条件不一定是同等重要的，而是有轻重缓急和主次之分的，如何根据实际情况确定模型和求解，使其更合实际是目标规划的任务。 4.线性规划的最优解可以说是绝对意义下的最优，为求得这个最优解，往往要花去大量的人力、物力和才力。而在实际问题中，却并不一定需要去找这种最优解。目标规划所求的满意解是指尽可能地达到或接近一个或几个已给定的指标值，这种满意解更能够满足实际的需要。 因此可以认为，目标规划更能够确切描述和解决经济管理中的许多实际问题。目前目标规划的理论和方法已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到广泛的应用。 二、目标规划的数学模型 例1 某工厂生产两种产品，受到原材料和设备工时的限制。在单件利润等有关数据已知的条件下，要求制定一个获利最大的生产计划，具体数据见表：

运筹学整数规划

实验报告 课程名称：___ 运筹学 ____ 项目名称：整数规划问题_ 姓名：__专业：、班级：1班学号：同组成员：_ __ 1注：1、实验准备部分包括实验环境准备和实验所需知识点准备。 2、若是单人单组实验，同组成员填无。

例4.5设某部队为了完成某项特殊任务，需要昼夜24小时不间断值班，但每天不同时段所需要的人数不同，具体情况如表4-4所示。假设值班人员分别在各时间段开时上班，并连续工作8h。现在的问题是该部队要完成这项任务至少需要配备多少名班人员？ 解： 根据题意，假设用i x（i=1,2,3,4,5,6）分别表示第i个班次开始上班的人数， 每个人都要连续值班8h，于是根据问题的要求可归结为如下的整数规划模型：目标函数： i i x z 6 1 min = ∑ = 约束条件： ? ? ? ? ? ? ? ? ? ? ? = ≥） 且为整数（6 ... 1 ,0 x 30 >= x6 + x5 20 >= x5 + x4 50 >= x4 + x3 60 >= x3 + x2 70 >= x2 + x1 60 >= x6 + x1 i i model: sets: num/1,2,3,4,5,6/:b,x; endsets data: b=60,70,60,50,20,30; enddata [obj]min=@sum(num(i):x(i)); x(1)+x(6)>=60; x(1)+x(2)>=70; x(2)+x(3)>=60; x(3)+x(4)>=50; 2注：实验过程记录要包含实验目的、实验原理、实验步骤，页码不够可自行添加。

解： 目标函数： y3*2000-y2*2000-y1*5000-x3*200)-(300+x2*30)-(40+x1*280)-(400=z max 约束条件：???????y3 *300<=x3*2y2*300<=x2*0.5y1*300<=x1*32000<=x3*4+x2+x1*5 model : sets : num/1,2,3/:x,y; endsets [obj]max =(400-280)*x(1)+(40-30)*x(2)+(300-200)*x(3)-5000*y(1)-2000*y(2)-2000*y(3); 5*x(1)+x(2)+4*x(3)<=2000; 3*x(1)<=300*y(1); 0.5*x(2)<=300*y(2); 2*x(3)<=300*y(3); @for (num(i):x(i)>=0;@bin (y(i));); end

运筹学--第四章 多目标规划汇总

习题四 4.1 分别用图解法和单纯形法求解下述目标规划问题 （1）min z ＝p1（＋）＋p2 st. －x1＋ x2＋ d－1－ d＋1＝1 －0.5x1＋ x2＋ d－2－d＋2＝2 3x1＋3x2＋ d－3－ d＋3＝50 x1，x2≥0；d－i，d＋i≥0（i =1，2，3） （2） min z ＝p1（2＋3）＋p2＋p3 st. x1＋ x2＋d－1－d＋1 ＝10 x1 ＋d－2－d＋2 ＝4 5x1＋3x2＋d－3－d＋3 ＝56 x1＋ x2＋d－4－d＋4 ＝12 x1，x2≥0；d－i，d＋i ≥0（i =1， (4) 4.2 考虑下述目标规划问题 min z ＝p1（d＋1＋d＋2）＋2p2d－4＋p2d－3＋p3d－1 st. x1 ＋d－1－d＋1＝20 x2＋d－2－d＋2＝35 －5x1＋3x2＋d－3－d＋3＝220 x1－x2＋d－4－d＋4＝60 x1，x2≥0；d－i，d＋i ≥0（i =1， (4) （1）求满意解； （2）当第二个约束右端项由35改为75时，求解的变化；

（3）若增加一个新的目标约束：－4x1＋x2＋d－5－d＋5＝8，该目标要求尽量达到目标值，并列为第一优先级考虑，求解的变化； （4）若增加一个新的变量x3，其系数列向量为（0，1，1，－1）T，则满意解如何变化？ 4.3 一个小型的无线电广播台考虑如何最好地来安排音乐、新闻和商业节目时间。依据法律，该台每天允许广播12小时，其中商业节目用以赢利，每小时可收入250美元，新闻节目每小时需支出40美元，音乐节目每播一小时费用为17.50美元。法律规定，正常情况下商业节目只能占广播时间的20％，每小时至少安排5分钟新闻节目。问每天的广播节目该如何安排？优先级如下： P1：满足法律规定要求； P2：每天的纯收入最大。 试建立该问题的目标规划模型。 4.4 某企业生产两种产品，产品Ⅰ售出后每件可获利10元，产品Ⅱ售出后每件可获利8元。生产每件产品Ⅰ需3小时的装配时间，每件产品Ⅱ需2小时装配时间。可用的装配时间共计为每周120小时，但允许加班。在加班时间内生产两种产品时，每件的获利分别降低1元。加班时间限定每周不超过40小时，企业希望总获利最大。试凭自己的经验确定优先结构，并建立该问题的目标规划模型。 4.5 某厂生产A、B两种型号的微型计算机产品。每种型号的微型计算机均需要经过两道工序I、II。已知每台微型计算机所需要的加工时间、销售利润及工厂每周最大加工能力的数据如下： A B每周最大加工能力 I 4 6 150 II 3 2 70 利润（元/台）300 450 工厂经营目标的期望值及优先级如下： P1：每周总利润不得低于10000元；

运筹学第4章整数规划习题.doc

第四章 整数规划 4.1 某工厂生产甲、乙两种设备，已知生产这两种设备需要消耗材料A 、材料B ，有关数据如下，问这两种设备各生产多少使工厂利润最大？（只建模不求解） 解：设生产甲、乙这两种设备的数量分别为x 1、x 2，由于是设备台数，则其变量都要求为整数，建立模型如下： 2123max x x z += ????? ? ?≥≤+≤+为整数 21212121,0,5 .45.01432x x x x x x x x 4.2 2197max x x z += ??? ??≥≤+≤+-且为整数 0,35 76 3.212121x x x x x x t s 割平面法求解。（下表为最优表） 线性规划的最优解为： 63max ,0,2/7,2/94321=====z x x x x 由最终表中得： 2 7 221227432=++ x x x ④ 将系数和常数项分解成整数和非负真分式之和，上式化为； 2 132********+=++x x x 移项后得： ①②③④ ①②③

即： 2 1221227212212274343-≤--→≥+x x x x 只要把增加的约束条件加到B 问题的最优单纯形表中。 由x 1行得： 7 32 7171541= -+ x x x 将系数和常数项分解成整数和非负真分数之和： 74476715541+=+-+x x x x 得到新的约束条件： 74 767154-≤--x x 7 47671654-=+--x x x 在的最优单纯形表中加上此约束，用对偶单纯形法求解： 则最优解为3,421 ==x x ，最优目标函数值为z *=55。 4.3 max z ＝4x 1＋3x 2＋2x 3

运筹学实验报告四整数规划

2018-2019学年第一学期 《运筹学》 实验报告（四） 班级：交通运输171 学号： 1000000000 姓名： ***** 日期： 2018.11.22

实验一： 用Lingo 软件求解下列整数规划问题（要求附程序和结果） 12 121212max 2506221 0,1,2i z x x x x x x x x x i =++≤?? -+≤?? +≤??≥=?且取整数 12312323123123 123max 232 45 2244 ,,01 z x x x x x x x x x x x x x x x x x =+-++≤??+≤?? +-≤??+-≤?=??或 解：例题（左）解题程序及运行结果如下： sets : bliang/1,2/:x,a; yshu/1,2,3/:b; xshu(yshu,bliang):c; endsets data : a=2,1; b=5,0,21; c=1,1 -1,1 6,2; enddata max =@sum (bliang(i):a(i)*x(i)); @for (yshu(j):@sum (bliang(i):x(i)*c(j,i))<=b(j)); @for(bliang(i):@gin(x(i))); Global optimal solution found. Objective value: 7.000000 Objective bound: 7.000000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost X( 1) 3.000000 -2.000000 X( 2) 1.000000 -1.000000 A( 1) 2.000000 0.000000