目标规划整数规划第五章

目标规划整数规划第五章4125210391146811求运费最小的运输方案。一、引例A1B1B216cijA21012148求最小运费的运输方案？？运输问题图示：产地销地B3B4A32214共产48共销48minZ=4x11

+12x12+4x13+11x14+2x21

+10x22

+3x23+9x24+8x31+5x32+11x33+6x34x11

+x12+x13+x14

=

16x21+x22+x23+x24

=

10x31+x32+x33

+x34

=

22x11+x21+

x31

=8x12

+x22+x32

=14x13

+x23+x33

=12x14+x24+x34=14xij

0i=1,2,3j=1,2,3,4xij

0其中，x11

x12

x13

x14

x21x22x23

x24

x31x32x33x34

111111111111111

1111111113个4个t1t2t3t4t5t6t77个条件线性相关任6个线性无关基变量6个系数矩阵的特点：(1)约束条件的系数矩阵的元素只有两个：0、1。(2)元素xij对应于每一个变量在前3个约束方程中(第i个方程中)出现1次，在后四个约束方程中（第3+j

个方程中）也出现1次。

(3)产销平衡问题为等式约束。

(4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等。(5)运输问题基变量的个数：6个A1AmB1B2Bna1……cijA2a2ambnb2b1……求最小运费的运输方案？？二.典型的运输问题：产地销地

销地产地B1B2…Bn产量A1x11x12…x1na1A2x21x22…x2na2………………Amxm1xm2…xmnam销量b1b2…bnc11c12cm1c21c22c2nc1ncmncm2i=1,2,…,mj=1,2,…,nxij

0典型运输问题的数学模型:x11

x12…

x1nx21

x22…

x2n…xm1xm2

…

xmn11…1

11…1………………

11…11…1

11…1………………

11…1mnm*n三、运输问题数学模型的特点：运输问题一定有最优解；运输问题约束条件的系数矩阵的特点：

(1)约束条件的系数矩阵的元素只有两个：0、1。

(2)元素xij

对应于每一个变量在前m个约束方程中(第i个方程中)出现一次，在后n个约束方程中（第m+j

个方程中）也出现一次。

(3)产销平衡问题为等式约束。

(4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等。3.运输问题基变量的个数：

m+n-1个设对偶变量向量为

Y=(u1,u2,…,um,v1,v2,…,vn)对偶规划为ui+vj≤cijui、vj

无约束i=1,2,3…m，j=1,2,3…n

产销平衡问题——总产量=总销量即产销不平衡问题——总产量≠总销量总产量>总销量:总产量<总销量:13第一节运输问题及其数学模型第二节用表上作业法求解运输问题解运输问题基本思想和步骤：1.基本思想：单纯形法的基本思想初始基本可行解是否为最优解换基结束YN此过程可以在运费表上直接运算，故称之为表上作业法4125210391146811初始方案的求法：三种（一）西北角法(优先考虑表中西北角的运输问题。)88866448814144125210391146811西北角法初始方案：优点：简单易行缺点：没有考虑运费4122854396111110销量产量销地产地822010100614868000060初始方案的求法（二）：最小元素法(优先考虑表中运费最低运输。)最小元素法初始方案4122854396111110销量产量销地产地82101468优点：就近供应，即优先供应运价小的业务。缺点：会出现顾此失彼（三）沃格尔法1.罚数=次小费用-最小费用2.找出最大的罚数行或列所对应的最小费用优先安排。3.重复计算步骤1和2。4125210391146811

销地产地B1B2B3B4产量行罚数A1124160A282101A3148223销量814121448列罚数21258（三）沃格尔法1.罚数=次小费用-最小费用2.找出最大的罚数行或列所对应的最小费用优先安排。3.重复计算步骤1和2。4125210391146811

销地产地B1B2B3B4产量行罚数A1124160A282101A3148223销量814121448列罚数21258解运输问题基本步骤：初始基本可行解是否为最优解换基结束YN最优解的判别（计算空格检验数）两种方法：闭回路法、对偶变量法（位势法）(一)闭回路法闭回路：从空格出发，遇到数字格可以旋转90度，最后回到空格所构成的回路。思想：初始基可行解的目标值与相邻基可行解目标值比较；由检验数体现。4125210391146811σ11=4-4+3-2=1σ22=10-3+4-11+6-5=1σ12=12-11+6-5=2σ24=9-11+4-3=-1σ31=8-2+3-4+11-6=10σ33=11-6+11-4=12设对偶变量向量为

Y=(u1,u2,…,um,v1,v2,…,vn)对偶规划为ui+vj≤cijui+vj无约束i=1,2,3…m，j=1,2,3…n对应的变量xij

检验数的计算：

一般问题：σj=Cj-CBB-1Pj=Cj-Y

Pj

运输问题：σij=Cij-CBB-1Pij=Cij-Y

Pij

=Cij-(u1,u2,…,um,v1,v2,…,vn)

Pij

=Cij-(ui+vj)

当xij为基变量时，

σij=Cij-(ui+vj)=0

由此，任选一个对偶变量为0，可求出其余所有的ui，vj。再根据σij=Cij-(ui+vj)求出所有非基变量的检验数。(二)对偶变量法（位势法）1.基本原理第三节运输问题的应用一、产销不平衡的运输问题例1：312711259435613127112594356100031271125943561000当产大于销时，即加入假想销地（假想仓库），销量为运费为0i=1,2,…,mj=1,2,…,nxij

0i=1,2,…,mj=1,2,…,n，n+1xij

0i=1,2,…,mj=1,2,…,nxij

0i=1,2,…,m，m+1j=1,2,…,nxij

0第四章目标规划目标规划问题及其数学模型一、目标规划问题的提出例4.1.某工厂计划制造I、II两种产品，受原材料和工时的限制。已知分别制造两种产品一件时所需的设备台时和原材料及产品利润如下表。问题：制定一个获利最大的计划.86利润(元)4044设备工时(h/件)60105原材料(Kg/件)限量III产品

5x1

+

10x2

60

4x1

+4x2

40x1，x2

0Z=

6x1

+8x2解:设两种产品产量分别为x1、x2maxs.t解：x1

=8，x2=2，z=64元实际情况：

物资部门销售部门计划部门财务部门12利润(元)4044设备工时(h/件)60105原材料(Kg/件)限量III产品具体要求：由于产品II销售疲软，故希望产品II的产量不超过产品I的一半原材料严重短缺，生产中应避免过量消耗最好能节约4h设备工时计划利润不少于48元。原材料使用不得超过限额产品II产量要求必须考虑设备工时问题其次考虑最后考虑计划利润的要求。描述多个目标的解决方法：引进偏差变量正偏差d+变量：决策值超过目标值的部分负偏差d-变量：决策值不足目标值的部分对每一目标引入d+、

d-，d+≥

0,d-≥0,d+·

d-=0

5x1

+

10x2

60

x1

-2x2+d1--d1+=04x1

+4x2+d2--d2+

=366x1

+8x2+d3--d3+

=48x1，x2,di+,

di-

0Min{P1d1-,P2d2+,P3d3-}maxZ=

6x1

+8x2

绝对约束和目标约束：绝对约束：必须严格满足的约束条件，决定了解的可行性目标约束：软约束用符号来表示可控制的因素优先因子和权系数：体现不同目标的主次轻重绝对优先次序：只有在满足高级优先目标的基础上才可以考虑较低级的目标，可用优先因子Pl表示，P1>>P2>>P3……>>Pn

相对优先：目标具有相同的优先因子，但他们的重要程度用权数表示

目标函数：通过各目标约束的正、偏差变量和赋于相应的优先等级来构造的。决策者的要求是尽可能从某个方向缩小偏离目标的数值。于是，目标规划的目标函数应该是求极小：1）要求恰好达到目标值，即相应目标约束的正、负偏差变量都要尽可能地小。这时取2)要求不超过目标值，即使相应目标约束的正偏差变量要尽可能地小。这时取3)要求不低于目标值，即使相应目标约束的负偏差变量要尽可能地小。这时取其基本形式有以下三种：建模步骤列出全部的约束条件把要达到指标的约束不等式加上正、负偏差变量后，化为目标约束等式对目标赋予相应的优先因子对同一级优先因子中的各偏差变量，若重要程度不一样，可根据题意赋予不同的加权系数构造一个按优先因子及加权系数对应的目标偏差量所要实现最小化的目标函数。例5.2：已知某实际问题的线性规划模型为在此基础上考虑：

1.Z的值不低于19002.资源1必须全部利用资源1资源2优先因子P1：约束转换P2：无级别：目标minf=转化后的模型为s.t.目标minf=例4.3：某公司生产两种产品A和B，每周生产线运行时间为60h，生产一台A、B产品分别需要4h、6h。根据市场预测，A、B产品平均销售量分别为每周9台、8台，销售利润分别为12万元、18万元。在制定生产计划时，经理考虑下述4项目标：首先，产量不能超过市场预测的销售量；其次，尽量不加班；第三，希望总利润最大；最后，要尽可能满足市场需求；当不能满足时，市场认为B产品的重要性是A产品的2倍。试建立这个问题的数学模型。分析：设决策变量为x1、x2分别为产品A，B的产量。把4个目标表示为不等式：第一个目标为：x1≤9，x2≤8;第二个目标为：4x1+6x2≤60；第三个目标为：希望总利润最大，要表示成不等式需要找到一个目标上界，这里可以估计为252(=12*9+18*8)，于是有12x1+18x2=252；第四个目标为：x1≥9，x2≥8。目标约束：根据决策者的考虑知：第二优先级要求第三优先级要求第四优先级要求这里，当不能满足市场需求时，市场认为B产品的重要性是A产品的2倍，即减少B产品其影响是A产品的2倍，因此引入2:1的权系数。第一优先级要求综合上述分析，可得到下列目标规划模型：取P=[1000100101]考虑目标规划数学模型的一些特点，作以下规定：1）目标函数为求最小化2）非基变量检验数中含有不同等级的优先因子，即j=∑kjpj，p1≫p2≫…≫pk；从每个检验数的整体看：检验数的正、负首先决定于p1的系数。若a1j≥0，j≥0

则此检验数的正、负就决定于p2的系数a2j的正负，依次类推。3)目标规划使用单纯形法求解，di-，di+视为普通变量。P1>>P2>>…>>PL解目标规划的单纯形例4.1minZ={P1d1-

，P2d2+

，P3d3-}5x1+10x2+x3=60

x1-2x2+d1-

-d1+=04x1+4x2+d2--d2+

=366x1+8x2+d3--d3+=48x1，x2，x2，di-，di+≥0,i=1,2,3第一步：minZ=P1d1-5x1+10x2+x3=60

x1-2x2+d1-

-d1+=04x1+4x2+d2--d2+

=366x1+8x2+d3--d3+=48x1，x2，x2，di-，di+≥0,i=1,2,3第二步minZ={P1d1-

，P2d2+

}5x1+10x2+x3=60

x1-2x2+d1-

-d1+=04x1+4x2+d2--d2+

=366x1+8x2+d3--d3+=48x1，x2，x2，di-，di+≥0,i=1,2,3第三步minZ={P1d1-

，P2d2+

，P3d3-}5x1+10x2+x3=60

x1-2x2+d1-

-d1+=04x1+4x2+d2--d2+

=366x1+8x2+d3--d3+=48x1，x2，x2，di-，di+≥0,i=1,2,3CBXBbx1x2p1p2p3x36003648514610-24801000-100001000-10000100-100p1

0P3-10-620-8000100000010000001P1P2p3解:初始单纯形表为：x31000000CBXBbx1x2p1p2p3x36003648010020-21220-51-4-65-146001000-100001000-1000P300000-2010600-6000010000001P1P2p3x31000000x1CBXBbx1x2p1p2p3x31224/536/512/50100000112/5-2/5-3/10-1-2/52/53/10001000-10-11/10-3/51/201-1/103/5-1/200000000000106000000010001000P1P2p3x31000000x1x2三个目标均达到CBXBbx1x2p1p2p3x31224/536/512/50100000112/5-2/5-3/10-1-2/52/53/10001000-10-11/10-3/51/201-1/103/5-1/200000000000106000000010001000P1P2p3x31000000x1x2CBXBbx1x2p1p2p3x320848010010/34/3-4/310/3000-10001001000-10-5/61/6-2/31/60000000000106000000010001000P1P2p3x31000000x15/6-1/62/3-1/6优先目标规划：按照目标先后顺序，逐一满足优先级较高的目标，最终得到一个满意解；等级森严，可能高级目标偏差小，后边的目标偏差比较大分多步进行建模和求解加权目标规划：各目标没有很明确的优先级，所有的偏差都有相应的权数以偏差加权和为目标函数，求最小值一步建模和求解。加权目标规划：minZ=P1d1-

+P2d2+

+P3d3-

5x1+10x2+x3=60

x1-2x2+d1-

-d1+=04x1+4x2+d2--d2+

=366x1+8x2+d3--d3+=48x1，x2，x2，di-，di+≥0,i=1,2,3第五章整数规划§1整数规划的数学模型及其解的特点§2解纯整数规划的割平面法§3分枝定界法§40—1型整数规划§5指派问题本章要求理解整数规划的含义掌握分枝定界法的思想和方法掌握0-1变量的含义和用法掌握指派问题的算法第五章整数规划§1整数规划的数学模型及其解的特点§2解纯整数规划的割平面法§3分枝定界法§40—1型整数规划§5指派问题一、整数规划问题整数规划问题（IP）:是指要求部分或全部决策变量的取值为整数的规划问题。模型为j=1,2,…,mxj

中取部分或全部为整数松弛问题：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题。整数线性规划问题分为以下几种类型：纯整数规划问题（pureintegerlinearprogramming）:是指全部决策变量的取值为整数的线性规划问题。混合整数规划问题(mixedintegerlinearprogramming):是指决策变量中有一部分必须取整数值，另一部分可以不取整数的线性规划问题。（如：奖金人数及其奖金数额之决策）0-1型整数规划问题(zero-oneintegerlinearprogramming)是指决策变量只能取0或1的整数线性规划问题。二、应用案例上班时间安排投资组合问题运输问题背包问题例1.某服务部门各时段（每2h为一时段）需要的服务员人数见下表。按规定，服务员连续工作8h（即4个时段）为一班。现要求安排服务员的工作时间，使服务部门服务员总数最少。9810服务员最少数目321时段411513687583设在第j班开始上班的服务员人数为xj.j=1…8注意：在第j班开始上班的服务员在3班后下班。MinZ=x1+x2+x3+x4+x5+x6+x7+x8x1

≥10x1+x2≥

8x1+x2+x3≥

9x1+x2+x3+x4≥

11x2+x3+x4+x5≥

13x3+x4+x5≥

8x4+x5≥

5x5≥

3xi≥0,且为整数问题的数学模型为整数规划证券投资：把一定的资金投入到合适的有价证券上以规避风险并获得最大的利润项目投资：财团或银行把资金投入到若干项目中以获得中长期的收益最大。投资问题例2：现有资金总额为B。可供选择的投资项目共n个，项目j所需投资额和预期收益分别为aj和cj（j=1…n)。此外由于种种原因，有三个附加条件：（1）若选择项目一，必须选项目二，反之不一定。（2）项目3和项目4中至少选择一个；（3）项目5、6、7中恰好选择两个。问：应当怎样选择投资项目，才能使总预期收益最大？模型

约束

目标—总收益最大变量—每个项目是否投资(1)选1必选2(2)3、4中必选一(3)5、6、7中恰选两个(4)总金额不超过限制0-1规划模型投资问题（二）某公司在今后五年内对以下4个项目投资。已知：项目A：从第1-4年每年年初需要投资，于次年末回收本利115%，但要求第一年投资最低金额为4万元，第2-4年不限；项目B：第3年初需要投资，到第5年末能回收本利128％，但规定最低投资金额为3万元，最高金额为5万元；项目C：第2年初需要投资，到第5年末能回收本利140%，但规定其投资额或为2万元或为4万元或为6万元或为8万元。项目D：5年内每年初可购买公债，于当年末归还，并加利息6%，此项投资金额不限。该部门现有资金10万元，问它应如何确定给这些项目的每年投资额，使到第五年末拥有的资金本利总额为最大?解：1)设xiA、xiB、xiC、xiD(i＝1，2，3，4，5)分别表示第i年年初给项目A，B，C，D的投资额；建立如下的决策变量：第1年第2年第3年第4年第5年

Ax1A

x2A

x3A

x4A

B

x3B

Cx2C

Dx1D

x2D

x3D

x4D

x5D

约束条件：第1年：年初10万元，D项目在年末可收回投资，故第一年年初应把全部资金投出去，x1A+x1D=10；第2年：A的投资第二年末才收回，故第二年年初的资金为1.06x1D第3年：年初资金：1.15x1A+1.06x2D，第4年：年初资金：1.15x2A+1.06x3D，第5年：年初资金：1.15x3A+1.06x4D，x3A+x3B+x3D=1.15x1A+1.06x2D；x4A+x4D=1.15x2A+1.06x3D；x5D=1.15x3A+1.06x4D。2）关于项目的投资额规定的处理：设yiA，yiB，是0—1变量，规定第i年给A、B投资时取1，否则取0（i=1,2,3,4,5）。设yiC是非负整数变量：第2年不投资C项目时，取0；第2年投资C项目2万元时，取1；第2年投资C项目4万元时，取2；第2年投资C项目6万元时，取3；第2年投资C项目8万元时，取4；关于项目A第一年投资额规定:x1A≥4y1A，x1A≤10y1A；保证当y1A=0时，x1A=0；当y1A=1时，x1A≥4。关于项目B的投资额规定:x3B≥3y3B，x3B≤5y3B；保证当y3B=0时，x3B=0；当y3B=1时，5≥x3B≥3。关于项目C的投资额规定:x2C=2y2C，y2C=0，1，2，3，4。3）目标函数及模型：

Maxz=1.15x4A+1.40x2C+1.28x3B+1.06x5Ds.t.x1A+x1D=10；x2A+x2C+x2D=1.06x1D；

x3A+x3B+x3D=1.15x1A+1.06x2D；x4A+x4D=1.15x2A+1.06x3D；x5D=1.15x3A+1.06x4D；x1A≥4y1A，

x1A≤10y1A，x3B≥3y3B，

x3B≤5y3B；x2C=2y2C，yiA，yiB=0或1，i=1,2,3,4,5y2C=0，1，2，3，4xiA，xiB，xiC，xiD≥0,i=1、2、3、4、5）

问题：有n项不同的任务，恰好n个人可分别承担这些任务。由于每人特长不同，完成各项任务的效率也不同。现假设必须指派每个人去完成一项任务，怎样把n项任务指派给n个人.目标：使得完成n项任务的总的效率最高。这就是指派问题。例1．有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示，问应如何指派工作，才能使总的消耗时间为最少。指派问题Minz=15x11+18x12+21x13+24x14+19x21+23x22+22x23+18x24

+26x31+17x32+16x33+19x34+19x41+21x42+23x43+17x44s.t.x11+x12+x13+x14=1(甲只能干一项工作)

x21+x22+x23+x24=1(乙只能干一项工作)x31+x32+x33+x34=1(丙只能干一项工作)x41+x42+x43+x44=1(丁只能干一项工作)x11+x21+x31+x41=1(A工作只能一人干)

x12+x22+x32+x42=1(B工作只能一人干)x13+x23+x33+x43=1(C工作只能一人干)x14+x24+x34+x44=1(D工作只能一人干)xij为0--1变量，i,j=1,2,3,4解：工厂A3或A4开工后，每年的生产费用估计分别为1200万元或1500万元。现要求决定应该建厂A3还是A4，才能使今后每年的总费用最少。选场问题例：两生产地、四需求地、供不应求，需再建一厂。有两个建厂方案。各厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费cij见表：设xij

表示由Ai运往Bj的物资数量，i,j=1…4x11

+x12+x13+x14

=

400x21+x22+x23+x24

=

600x31+x32+x33

+x34

=

200x11+x21+

x31

=350x12

+x22+x32

=400x13

+x23+x33

=300x14+x24+x34=150xij

0minZ=2x11

+9x12+3x13+4x14+8x21

+3x22

+5x23+7x24+7x31+6x32+x23+2x34+1200建A3,总费用为：x11

+x12+x13+x14

=

400x21+x22+x23+x24

=

600x41+x42+x43

+x44

=

200x11+x21+

x41

=350x12

+x22+x42

=400x13

+x23+x43

=300x14+x24+x44=150xij

0minZ=2x11

+9x12+3x13+4x14+8x21

+3x22

+5x23+7x24+4x41+5x42+2x43+5x44+1500建A4,总费用为：x11

+x12+x13+x14

=

400x21+x22+x23+x24

=

600x31+x32+x33

+x34

=

200yx41+x42+x43

+x44

=

200(1-y)x11+x21+

x31

=350y;x11+x21+

x41

=350(1-y);x12

+x22+x32

=400y;x12

+x22+x42

=400(1-y);x13

+x23+x33

=300y;x13

+x23+x43

=300(1-y);x14+x24+x34=150y;x14+x24+x44=150(1-y)xij

0y=0,1minZ=2x11

+9x12+3x13+4x14+8x21

+3x22

+5x23+7x24+y(7x31+6x32+x23+2x34+1200)+(1-y)(4x41+5x42+2x43+5x44+1500)y=建A3建A4minZ=2x11

+9x12+3x13+4x14+8x21

+3x22

+5x23+7x24+7x31+6x32+x23+2x34+y1200+4x41+5x42+2x43+5x44+1500(1-y)1,0,混合整数规划背包(knapsack)问题背景旅行背包：容量一定的背包里装尽可能的多的物品

一位旅行者出发前准备在自己的背包里携带必需的物品,已知可供选择的物品有n种,第j种物品的重量为aj公斤,其价值为cj,若背包所带物品的总重量不得超过b公斤,问他应如何选择所带物品，以使总价值最大。则背包问题的数学模型如下：解：设实例一一个徒步旅行者要在背包中选择一些有价值的物品携带，他最多携带115kg的物品、现共有5件物品，分别重54kg、34kg、57kg、45kg、19kg，其价值依次为7、5、9、6、3.问该旅行者携带哪些物品，使总价值最大？实例二某人出国留学打点行李，现有三个旅行包，容积大小分别为1000毫升、1500毫升和2000毫升。根据需要列出需带物品清单：必带物品共有7件，其体积大小分别为400、300、150、250、450、760、190、（单位毫升）；10件可带可不带物品，如果不带将在目的地购买，通过网络查询知其在目的地的价格（单位美元）。这些物品的容量及价格分别见下表试给出一个合理的安排方案把物品放在三个旅行包里.物品12345678910体积200350500430320120700420250100价格1545100705075200902030解：变量:xij为第i个物品是否放在第j个包裹中约束:包裹容量限制必带物品限制选带物品限制目标函数:未带物品购买费用最小模型固定成本问题例高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为150万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。解：这是一个整数规划的问题。设x1，x2，x3分别为小号容器、中号容器和大号容器的生产数量。各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设yi=1(当生产第i种容器,即xi＞0时)或0（当不生产第i种容器即xi=0时）。引入约束xi≤Myi，i=1，2，3，M充分大，以保证当yi=0时，xi=0。建立如下的数学模型：Maxz=4x1+5x2+6x3-100y1-150y2-200y3s.t.2x1+4x2+8x3≤5002x1+3x2+4x3≤300

x1+2x2+3x3≤100xi≤Myi，i=1，2，3，M充分大xj≥0yj为0--1变量，i=1,2,3分布系统设计例某企业在A1地已有一个工厂，其产品的生产能力为30千箱，为了扩大生产，打算在A2，A3，A4，A5地中再选择几个地方建厂。已知在A2，A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千元、500千元，另外，A1产量及A2，A3，A4，A5建成厂的产量，那时销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。问应该在哪几个地方建厂，在满足销量的前提下，使得其总的固定成本和总的运输费用之和最小?解：设xij为从Ai运往Bj的运输量(单位千箱)，yk=1(当Ak被选中时)或0（当Ak没被选中时),k=2,3,4,5．这可以表示为一个整数规划问题：Minz=175y2+300y3+375y4+500y5+8x11+4x12+3x13+5x21+2x22+3x23+4x31+3x32+4x33+9x41+7x42+5x43+10x51+4x52+2x53其中前4项为固定投资额，后面的项为运输费用。s.t.x11+x12+x13≤30(A1厂的产量限制)

x21+x22+x23≤10y2(A2厂的产量限制)x31+x32+x33≤20y3(A3厂的产量限制)x41+x42+x43≤30y4(A4厂的产量限制)x51+x52+x53≤40y5(A5厂的产量限制)x11+x21+x31+x41+x51=30(B1销地的限制)

x12+x22+x32+x42+x52=20(B2销地的限制)x13+x23+x33+x43+x53=20(B3销地的限制)xij≥0，i=1,2,3,4,5；j=1,2,3，yk为0--1变量，k=2,3,4,5。例.用隐枚举法求解旅行售货员(货郎担)问题（TSP）

有一旅行团从v0出发要游遍城市v1,v2，……，vn，已知从vi到vj的旅费为cij,

应如何安排行程是总费用最小？20个城市哈密顿图：不重复的走遍所有的点再返回出发点。分析变量—是否从i第个城市（出）到第j个城市（进）目标—总费用最小约束—每个城市只能离开一次、到达一次数学模型每座城市恰好出一次每座城市恰好进一次直接从vi进入vj

其它三、整数规划与松弛问题的联系（1）松弛问题（一般线性规划问题）可行解集为一凸集，即任意可行解的图组合仍为可行解。整数规划问题的可行解是松弛问题可行解集的一个子集，但任意两个可行解的凸组合不一定为整数解，故不一定为可行解（2）整数规划问题的可行解一定是松弛问题的可行解，故整数规划最优值不会优于松弛问题的最优值。（3）一般的，松弛问题的最优解不会恰好是整数，故不是整数规划问题的最优解。不可用四舍五入法或去尾法对线性规划的非整数解加以处理来解决整数规划。整数规划问题的求解方法：目前，常用的求解整数规划的方法有：割平面法、分支定界法和完全枚举法321(一）整数规划图解法x2x11234567（4,2)(18/7,19/7)x1+2x