运筹学 第四章 整数规划与分配问题

整数规划与分配问题整数规划的特点及作用分支定界法割平面法应用举例分配问题与匈牙利法

例1、合理下料问题设用某型号的圆钢下零件A1,

A2,…,Am

的毛坯。在一根圆钢上下料的方式有B1,B2,…Bn

种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？一、整数规划的模型第一节整数规划的特点及作用零件毛坯数零件方个数式零件设：xj

表示用Bj

(j=1.2…n)

种方式下料根数模型：x1xn…例2、某公司计划在m个地点建厂，可供选择的地点有A1,A2…Am

，他们的生产能力分别是a1,a2,…am（假设生产同一产品）。第i个工厂的建设费用为fi

(i=1.2…m),又有n个地点B1,B2,…Bn

需要销售这种产品，其销量分别为b1.b2…bn

。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？单销地厂址价生产能力建设费用销量设：xij

表示从工厂运往销地的运量(i=1.2…m、j=1.2…n),1在Ai建厂又设Yi＝（i=1.2…m）

0不在Ai建厂设：

xij

表示从工厂运往销地的运量(i=1.2…m、j=1.2…n),1在Ai建厂

又设Yi＝（i=1.2…m）

0不在Ai建厂模型：

例3、机床分配问题设有m台同类机床，要加工n种零件。已知各种零件的加工时间分别为a1,a2,…an

，问如何分配，使各机床的总加工任务相等，或者说尽可能平衡。设：1分配第i台机床加工第j种零件；

xij＝（i=1.2…m,j=1.2…n）

0相反。又由于一个零件只能在一台机床上加工，所以有:于是，第i台机床加工各种零件的总时间为:因此，求xij

，使得问如何分配，使各机床的总加工时间相等，或者说尽可能平衡。?在上一章讨论的LP问题中,对决策变量只限于不能取负值的连续型数值,即可以是正分数或正小数。然而在许多实际问题中，决策变量只有非负整数才有实际意义。对求整数最优解的问题，称为整数规划(IntegerProgramming)(简记为IP)。又称约束条件和函数均为线性的IP为整数线性规划(IntegerLinearProgramming)(简记为ILP)。纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可以不要求取整数）。全整数规划：除了所有决策变量要求取非负整数外，系数aij和常数bi也要求取整数（这时引进的松弛变量和剩余变量也必须是整数）。混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数。

0－1整数规划：所有决策变量只能取0或1两个整数。整数规划与线性规划的关系

从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。例4、设整数规划问题如下首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。用图解法求出最优解x1＝3/2,x2=10/3且有Z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解（最优解）：如用“舍入取整法”可得到4个点：(1,3)(2,3)(1,4)(2,4)。显然，它们都不可能是整数规划的最优解。按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集，如图所示。因此，可将集合内的整数点一一找出，其最大目标函数的值为最优解，此法为完全枚举法。如上例：其中（2，2）（3，1）点为最大值，Z=4。目前，常用的求解整数规划的方法有：

分支定界法和割平面法；对于特别的0－1规划问题采用隐枚举法和匈牙利法。人们对IP感兴趣，还因为有些经济管理中的实际问题的解必须满足如逻辑条件和顺序要求等一些特殊的约束条件。此时需引进逻辑变量（又称0-1变量），以“0”表示“非”，以“1”表示“是”。凡决策变量均是0-1变量的IP为0-1规划。逻辑变量的应用(3)两组条件满足其中一组又Ｍ为任意大正数，则问题表达为：若，则；否则（即时）定义(4)在实际中经常会遇到这样的问题，有n项不同的任务，需要n个人分别完成其中的一项，但由于任务的性质和各人的专长不同，因此各人去完成不同的任务的效率（或花费的时间或费用）也就不同。于是产生了一个问题，应指派哪个人去完成哪项任务，使完成n项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分配问题。第二节分配问题与匈牙利法（一）、指派问题的数学模型设n个人被分配去做n件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j件工作的的效率（时间或费用）为aij(i=1.2…n;j=1.2…n)并假设aij≥0。问应如何分配才能使总效率（时间或费用）最高？设决策变量1分配第i个人去做第j件工作

xij

=0相反(i,j=1.2.…n)其数学模型为：（二）、解题步骤：指派问题是0-1规划的特例，也是运输问题的特例，当然可用整数规划，0-1规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法.匈牙利法是从这样一个明显的事实出发:如果效率矩阵的所有元素,而其中存在一组位于不同行不同列的零元素，则只要令这些零元素位置的，其余的，则就是问题的最优解．最优解为如效率矩阵为匈牙利法的基本思想是：对同一项工作（任务）j来说，同时提高或降低每人相同的效率（常数ti），不影响其最优指派；同样，对同一个人i来说，完成各项工作的效率都提高或降低相同的效率（常数di），也不影响其最优指派;因此可得到新的效率矩阵(bij)nxn，其中bij=aij+ti+dj

（对所有的i,j）则新的目标函数为其中为常数这说明Z与Z同时达到最小值。因而最优解相同。故指派问题有以下性质：若从效率矩阵(aij)nxn的一行（列）各元素中分别减去该行（列）的最小元素，得到的新效率矩阵(bij)nxn不改变原指派问题的最优解。匈牙利法:第一步：变换指派问题的系数矩阵（aij）为(bij)，使在(bij)的各行各列中都出现0元素，即(1)从(aij)的每行元素都减去该行的最小元素；(2)再从所得新系数矩阵的每列元素中减去该列的最小元素。

第二步：进行试指派，以寻求最优解。在(bij)中找尽可能多的独立0元素，若能找出n个独立0元素，就以这n个独立0元素对应解矩阵(xij)中的元素为1，其余为0，这就得到最优解。找独立0元素，常用的步骤为：

(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎

。然后划去◎

所在列(行)的其它0元素，记作Ø

；这表示这列所代表的任务已指派完，不必再考虑别人了。

(2)给只有一个0元素的列(行)中的0元素加圈，记作◎；然后划去◎

所在行的0元素，记作Ø

．

(3)反复进行(1)，(2)两步，直到尽可能多的0元素都被圈出和划掉为止。

(4)若仍有没有划圈的0元素，且同行(列)的0元素至少有两个，则从剩有0元素最少的行(列)开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈(表示选择性多的要“礼让”选择性少的)。然后划掉同行同列的其它0元素。可反复进行，直到所有0元素都已圈出和划掉为止。（5）若◎

元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m<n,则转入下一步。第三步：作最少的直线覆盖所有0元素。

(1)对没有◎的行打√号；

(2)对已打√号的行中所有含Ø元素的列打√号；

(3)再对打有√号的列中含◎

元素的行打√号；

(4)重复(2),(3)直到得不出新的打√号的行、列为止；

(5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数l。l应等于m，若不相等，说明试指派过程有误，回到第二步(4)，另行试指派；若l＝m<n，须再变换当前的系数矩阵，以找到n个独立的0元素，为此转第四步。第四步：变换矩阵(bij)以增加0元素。在没有被直线覆盖的所有元素中找出最小元素，然后打√各行都减去这最小元素；打√各列都加上这最小元素（以保证系数矩阵中不出现负元素）。新系数矩阵的最优解和原问题仍相同。转回第二步。例1有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？

任务人员ABCD甲67112乙4598丙31104丁5982求解过程如下：第一步，变换系数矩阵：-5第二步，试指派：◎◎◎ØØ找到3个独立零元素但m=3<n=4。第三步，作最少的直线覆盖所有0元素：◎◎◎ØØ√√√独立零元素的个数m等于最少直线数l，即l＝m=3<n=4；第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派：000

0

00得到4个独立零元素，所以最优解矩阵为：◎◎◎ØØ√√√◎◎◎ØØ15◎◎◎ØØ◎Lingo求解例2有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？

任务人员ABCD甲21097乙154148丙13141611丁4151392109715414813141611415139行减0875110104235001195082511054230001145列减试指派082511054230001145◎Ø◎◎Ø082511054230001145◎Ø◎◎Ø√√√调整0603110542300092306031105423000923指派◎◎Ø◎Ø◎0010010000011000Lingo求解例4：求下面问题的最优指派115764戊69637丁96458丙9117129乙118957甲EDCBA费工作用人员11576469637964589117129118957造“零”520436725042441025340363402317123150240315试指派5032015304310140305242402◎Ø◎◎◎ØØ打勾√√√5032015304310140305242402◎Ø◎◎◎ØØ划线√√√5032015304310140305242402◎Ø◎◎◎ØØ调整最小值为11-13133-12400630200000试指派5033004203310240306231301◎Ø◎Ø◎Ø◎Ø√√√√√◎Ø列行交替寻找打勾时√√划线5033004203310240306231301◎Ø◎Ø◎Ø◎Ø√√√√√√√5033004203310240306231301◎Ø◎Ø◎Ø◎Ø√√√√√√√调整1031326030420133024003305◎Ø√√√√√◎◎◎ØØØ0-120215-12-12-113-106043006√√Ø31-1023024023◎ØØ◎◎Ø◎Ø◎此问题有多个最优解试指派ØLingo求解用匈牙利法求解下列指派问题，已知效率矩阵分别如下：Lingo求解Lingo求解一般指派问题最大化指派问题人数和工作数不等的指派问题一个人可做几项工作的指派问题某项工作一定不能由某人做的指派问题最大化指派问题最大值最小化指派问题Lingo求解人数和工作数不等的指派问题列减√◎Ø◎◎ØØØØ◎√√试指派划线√√√调整试指派◎◎◎◎◎ØØØØØLingo求解一个人可做几项工作的指派问题A1可同时做三项工作3195231952783298247631952行减2084120841561076025420841列减0074000740360064015300740ØØØØØØØØ√√√√√√√◎◎◎◎◎Ø列行交替寻找0074000740360064015300740√√√√√√√0074000740360064015300740调整0063000630470074004300630-136-1-1240-1350063-136-1-1-136-1-1037000070004400Ø◎◎◎◎◎ØØØØØØØ最优指派为A1作B1，B4，B5，A2作B3，A3作B2。Lingo求解某项工作一定不能由某人做的指派问题A1不能做B4;A3不能做B3Lingo求解（一）、基本思路考虑整数问题：整数问题的松弛问题：第三节分枝定界法

1、先不考虑整数约束，解(

IP)的松弛问题(LP)，可能得到以下情况之一：⑴若(LP)没有可行解,则(IP)也没有可行解,停止计算。⑵若(LP)有最优解,并符合(IP)的整数条件,则(LP)的最优解即为(IP)的最优解,停止计算。⑶若(LP)有最优解,但不符合(IP)的整数条件,转入下一步。为讨论方便，设(LP)的最优解为：

2、定界：记(

IP)的目标函数最优值为Z*,以Z(0)

作为Z*

的上界，记为＝Z(0)

。再用观察法找的一个整数可行解X′，并以其相应的目标函数值Z′作为Z*

的下界，记为Z＝Z′，也可以令Z＝－∞，则有：

Z≤Z*≤

3、分枝：在(LP)的最优解X(0)中，任选一个不符合整数条件的变量，例如xr=

（不为整数），以表示不超过的最大整数。构造两个约束条件

xr≤和xr≥＋1如此反复进行，直到得到Z＝Z*＝为止，即得最优解X*

。将这两个约束条件分别加入问题(

IP)，形成两个子问题(

IP1)和(

IP2)，再解这两个问题的松弛问题(LP1)和(LP2)。

4、修改上、下界：按照以下两点规则进行。⑴在各分枝问题中,找出目标函数值最大者作为新的上界;⑵.从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。

5、比较与剪枝：各分枝的目标函数值中,若有小于Z者,则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。3200CB

XB

b

x1x2x3x40x3921109/20x414230114/2-Z032003200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用单纯形法解对应的(LP)问题,获得最优解。初始表最终表例1

、用分枝定界法求解整数规划问题（单纯形法）x1=13/4

x2=5/2Z(0)=59/4≈14.75,选x2进行分枝，即增加两个约束，2≥x2

，x2≥3有下式：分别在(LP1)和(LP2)中引入松弛变量x5和x6

，将新加约束条件加入上表计算。即x2+x5=2,－x2+x6=－3

得下表:3200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/432000CB

XB

b

x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/4032000CB

XB

b

x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2Z(1)=29/2=14.5，LP13200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/432000CB

XB

b

x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/4032000CB

XB

b

x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/40LP2x1=5/2,x2=3Z(2)=27/2=13.5，∵Z(2)<Z(1)∴先不考虑分枝。3x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/21/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2接(LP1)继续分枝，加入约束4≤x1,

x1≤3,有下式：分别引入松弛变量x7和x8，然后进行计算。32000CB

XB

b

x1x2x3x4x53x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2CB

XB

b

x1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/20CB

XB

b

x1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/20

x1=3,x2=2Z(3)=13找到整数解，问题已探明，停止计算。LP33x17/2101/20-1/202x220100100x4100-11-200x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100x420001-3-20x310010-1-2-Z-130000-2-3CB

XB

b

x1x2x3x4x5x83x17/2101/20-1/202x220100100x4100-11-200x8-4-100001-Z-29/200-3/20-1/20

x1=4,x2=1Z(4)=14找到整数解，问题已探明，停止计算。LP43x17/2101/20-1/202x220100100x4100-11-200x8-1/2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020x4300-310-40x5100-101-2-Z-1400-200-1Lingo求解树形图如下：LPx1=13/4,x2=5/2Z(0)

＝59/4=14.75LP2x1=5/2,x2=3Z(2)＝27/2=13.5LP3x1=3,x2=2Z(3)

＝13LP4x1=4,x2=1Z(4)

＝14x2≤2x2≥3x1≤3x1≥4＃＃＃LP1x1=7/2,x2=2Z(1)＝29/2=14.5例2.用分枝定界法求解整数规划问题（用图解法计算）记为（IP）解：首先去掉整数约束，变成一般线性规划问题记为（LP）用图解法求（LP）的最优解，如图所示。x1x2⑴⑵33(18/11,40/11)⑶对于x1＝18/11≈1.64，取值x1≤1，x1≥2，先将（LP）划分为（LP1）和（LP2）,取x1≤1,x1≥2。

x1＝18/11,x2=40/11Z(0)=－218/11≈(－19.8)即Z也是(IP)最小值的下限。有下式：现在只要求出(LP1)和(LP2)的最优解即可。x1x2⑴⑵33⑶

先求（LP1）,如图所示。此时B

在点取得最优解。x1＝1,x2=3,Z(1)=-16找到整数解，问题已探明，此枝停止计算。11同理求（LP2）

,如图所示。在C

点取得最优解。即x1＝2,x2=10/3,Z(2)=-56/3≈-18.7∵Z2<Z1＝－16∴原问题有比(-16)更小的最优解，但x2不是整数，故利用4≥10/3≥3加入条件。BAC加入条件：x2≤3,x2≥4有下式：只要求出（LP3）和（LP4）的最优解即可。x1x2⑴⑵33⑶11BAC先求（LP3）,如图所示。此时D在点取得最优解。即x1＝12/5≈2.4,x2=3,Z(3)＝-87/5≈-17.4>Z≈-19.8但x1＝12/5不是整数，可继续分枝。即3≤x1≤2。D求（LP4），如图所示。无可行解，不再分枝。在(LP3)的基础上继续分枝。加入条件3≤x1,x1≤2。只要求出（LP5）和（LP6）的最优解即可。x1x2⑴⑵33⑶11BACD先求（LP5）,如图所示。此时E

在点取得最优解。即x1＝2,x2=3,Z(5)＝－17找到整数解，问题已探明，此枝停止计算。E求（LP6），如图所示。此时

F在点取得最优解。x1＝3,x2=2.5,Z(6)＝－31/2≈－15.5>Z(5)

F如对Z(6)

继续分解，其最小值也不会低于-15.5，问题探明,剪枝。至此，原问题（IP）的最优解为：

x1=2，

x2=3,

Z*=Z(5)

＝-17以上的求解过程可以用一个树形图表示如右：LP1x1=1,x2=3Z(1)

＝－16LPx1=18/11,x2=40/11Z(0)

＝－19.8LP2x1=2,x2=10/3Z(2)

＝－18.5LP3x1=12/5,x2=3Z(3)

＝－17.4LP4无可行解LP5x1=2,x2=3Z(5)

＝－17LP6x1=3,x2=5/2Z(6)

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃Lingo求解练习：用分枝定界法求解整数规划问题

（图解法）

LP1x1=1,x2=7/3Z(1)

＝10/3LPx1=3/2,x2=10/3Z(0)

＝29/6LP2x1=2,x2=23/9Z(2)

＝41/9x1≤1x1≥2LP3x1=33/14,x2=2Z(3)

＝61/14LP4无可行解x2≤2x2≥3＃LP7x1=2,x2=2Z(7)

＝4LP8x1=3,x2=1Z(8)

＝4x1≤2x1≥3＃＃LP1x1=1,x2=7/3Z(1)

＝10/3LPx1=3/2,x2=10/3Z(0)

＝29/6LP2x1=2,x2=23/9Z(2)

＝41/9x1≤1x1≥2LP5x1=1,x2=2Z(5)

＝3LP6无可行解＃＃x2≤2x2≥3LP3x1=33/14,x2=2Z(3)

＝61/14LP4无可行解x2≤2x2≥3＃LP7x1=2,x2=2Z(7)

＝4LP8x1=3,x2=1Z(8)

＝4x1≤2x1≥3＃＃Lingo求解练习：用分枝定界法求解整数规划问题

（单纯形法）LP1x1=1,x2=3Z(1)

＝－16LPx1=18/11,x2=40/11Z(0)

＝－19.8LP2x1=2,x2=10/3Z(2)

＝－18.5LP3x1=12/5,x2=3Z(3)

＝－17.4LP4无可行解LP5x1=2,x2=3Z(5)

＝－17LP6x1=3,x2=5/2Z(6)

＝－15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃Lingo求解（一）、计算步骤：1、用单纯形法求解(IP)对应的松弛问题(LP)：⑴.若(LP)没有可行解，则(IP)也没有可行解，停止计算。

⑵.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。

⑶.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。第四节割平面法

2、从(LP)的最优解中，任选一个不为整数的分量xr,,将最优单纯形表中该行的系数和分解为整数部分和小数部分之和，并以该行为源行，按下式作割平面方程：

3、将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量），用对偶单纯形法求出新的最优解，返回1。的小数部分的小数部分例1：用割平面法求解整数规划问题解：增加松弛变量x3和x4

，得到(LP)的初始单纯形表和最优单纯形表：Cj0100CBXBbx1x2x3x40x3632100x40-3201－Z00100Cj0100CBXBbx1x2x3x40x11101/6-1/61x23/2011/41/4－Z-3/200-1/4-1/4此题的最优解为：X＊=(1,3/2)，Z=3/2，但不是整数最优解，引入割平面。也即：以x2为源行生成割平面，将所需要的数分解为整数和分数，由于1/4=0+1/4,3/2=1+1/2,所以有：整数所以:带入，得到等价的割平面条件：x2≤

1见右图。由x3=6-3x1-2x2

,x4=3x1-2x2得x1x2⑴⑵33第一个割平面Cj01000CBXBbx1x2x3x4s10x11101/6-1/601x23/2011/41/400s1-1/200-1/4-1/41－Z-3/200-1/4-1/40将生成的割平面条件加入松弛变量，然后加到表中：CBXBbx1x2x3x4s10x12/3100-1/32/31x21010010x320011-4－Z-10000-1此时，X1

＝(2/3,1),Z=1,仍不是整数解。继续以x1为源行生成割平面，其条件为：用上表的约束解出x4和s1，将它们带入上式得到等价的割平面条件：x1≥x2，见图：x1x2⑴⑵33第一个割平面第二个割平面将生成的割平面条件加入松弛变量，然后加到表中：CBXBbx1x2x3x4s1s20x12/3100-1/32/301x210100100x320011-400s2-2/3000-2/3-2/31－Z-10000-10CBXBbx1x2x3x4s1s20x10100-1011x20010-103/20x3600150-60s1100011-3/2－Z000010-3/2CBXBbx1x2x3x4s1s20x1110001-1/21x210100100x310010-53/20x4100011-3/2－Z-10000-10至此得到最优表，其最优解为X＊=(1,1),Z=1,这也是原问题的最优解。由以上解题过程可见，表中含有分数元素且算法过程中始终保持对偶可行性，因此，这个算法也称为分数对偶割平面算法。例2：用割平面法求解数规划问题Cj1100CBXBbx1x2x3x40x3621100x4204501－Z1100初始表最优表CBXBbx1x2x3x41

x15/3105/6－1/61x28/301－2/31/3－Z-13/300－1/6－1/6在松弛问题最优解中，x1,x2均为非整数解，由上表有：将系数和常数都分解成整数和非负真分数之和以上式子只须考虑一个即可，解题经验表明，考虑式子右端最大真分数的式子，往往会较快地找到所需割平面约束条件。以上两个式子右端真分数相等，可任选一个考虑。现选第二个式子，并将真分数移到右边得：引入松弛变量s1后得到下式，将此约束条件加到上表中，继续求解。Cj11000CBXBbx1x2x3x4s11

x15/3105/6-1/601x28/301-2/31/300s1-2/300-1/3-1/31－Z-13/300-1/6-1/60得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解：X＊=(0,4),Z=4,Cj11000CBXBbx1x2x3x4s11

x10100-101x240101-20x320011-3－Z-40000－1/2练习：ïïîïïíì³£-£+£+-+=且为整数0,421625421411max2121212121xxxxxxxxxxZCBXBbx1x2x3x4x50x34001-1/34/34x24/30102/9-5/911x18/31001/92/9－Z000-19/9-2/9（2，3）CBXBbx1x2x3x4x5s10x30001-1064x230101/20-5/211x121000010x530001/21-9/2－Z000-20-1计算软件整数变量定义LinGo

一般整数变量:@GIN(variable_name);0-1整数变量：@BIN(variable_name);算例

max3x1+5x2+4x3subjectto2x1+3x2<=15002x2+4x3<=8003x1+2x2+5x3<=2000endginx1ginx3

model:max=3*x1+5*x2+4*x3;2*x1+3*x2<=1500;2*x2+4*x3<=800;3*x1+2*x2+5*x3<=2000;@gin(x1);@gin(x3);endGlobaloptimalsolutionfoundatiteration:3Objectivevalue:2675.000VariableValueReducedCostX1375.00000.3333333X2250.00000.000000X375.00000-4.000000

第五节应用案例例l.分配甲、乙、丙、丁四个人去完成5项工作，每人完成各项工作所需的时间见表

。由于工作数多于人数，故规定其中有一个人可兼顾完成两项工作，其余3人每人完成一项。试确定总的花费时间为最少的指派方案。工作人ABCDE甲2529314237乙3938262033丙3427284032丁3442362345解：此问题为人数与任务数不等的分配问题，由于任务数比人数多1，因此需要有一个假想的人去完成某一项工作。根据题中的要求，这个假想的人就是甲、乙、丙、丁四个人中的某一个，因此这时假想人完成每项工作所用的时间不能为零。由于要求总的花费时间最少．因此这个假想人完成各项工作所需要的时间应该取甲、乙、丙、丁中的最小者．假设第五个人是戊，则新的效率矩阵见表。工作人ABCDE甲2529314237乙3938262033丙3427284032丁3442362345工作人ABCDE甲2529314237乙3938262033丙3427284032丁3442362345戊2527262032得到如下的新效率表工作人ABCDE甲2529314237乙3938262033丙3427284032丁3442362345戊2527262032利用匈牙利法，可以得到最优分配方案为：甲完成A，乙完成C，丙完成B和E，丁完成D，需要133h.Lingo求解例2.要从甲、乙、丙、丁、戊五人中挑选4个人去完成4项工作。己知每人完成各项工作的时间见表。规定每项工作只能由一个人单独去完成，每个人最多承担一项任务．又假设对甲必须保证分配一项任务，丁因某种原因决定不同意承担第4项任务，在满足上述条件下，如何分配工作使完成4项工作总的花费时间最少。工作人ABCDE甲1051520M乙2105150丙31514130丁152760戊941580M工作人ABCDE甲1051520M乙2105150丙31514130丁1527M0戊941580应用匈牙利法可以得到最优分配为：甲完成B，乙完成C，丙完成A，戊完成D，需要21h.Lingo求解例3

某部队后勤值班室准备聘用4名兼职值班员(代号1,2,3,4)和2名兼职带班员(代号5,6)。已知每人从周一至周日每天最多可安排的值班时间及每人每h值班的报酬如下表所示：该值班室每天值班时间为上午8:00至晚上22:00,值班时间内须有且仅须一名值班员值班.要求兼职值班员每周值班不少于10h,兼职带班员每周不少于8h,每名值班员每周值班不超过4次,每次值班不少于2h,每天安排值班员不超过3人,且其中必须有一名兼职带班员,试为该值班室安排一张人员的值班表，使总支付的报酬为最少．值班员代号报酬元/h每天最多可安排的值班时间周一周二周三周四周五周六周日110.060607120210.0060600123948305121249556040125153048012061606063012(1)该值班室值班时间为上午8:00至22:00,值班时间内须有且仅须一名值班员值班.(2)规定值班员每周值班不少于10h,(3)带班员每周不少于8h,(4)每名值班员每周值班不超过4次,(5)每次值班不少于2h,(6)每天安排值班的学生不超过3人,(7)其中必须有带班员,设xij为值班员i在周j值班时间

1,安排值班员i在周j值班yij=

0,否则(1)(2)(3)(4)(5)(6)(7)值班代号报酬元/h每天最多可安排的值班时间周一周二周三周四周五周六周日11060607120210060600123948305121249556040125153048012061606063012aij为值班员i在周j的最多可值班时间得到数学模型为：

1,安排学生i在周j值班yij=

0,否则设xij为值班员i在周j值班时间Lingo求解程序Sets:num_i/1..6/:c; num_j/1..7; link(num_i,num_j):a,x,y;num_k/1..4/; endsetsdata: c=10,10,9,9,15,16;a=6,0,6,0,7,12,0,0,6,0,6,0,0,12,4,8,3,0,5,12,12,5,5,6,0,4,0,12,3,0,4,8,0,12,0,0,6,0,6,3,0,12; enddatamin=@sum(link(i,j):c(i)*x(i,j));@for(num_j(j):@sum(num_i(i):x(i,j))=14;);@for(num_k(k):@sum(num_j(j):x(k,j))>=10;);@sum(num_j(j):x(5,j))>=8;@sum(num_j(j):x(6,j))>=8;@for(num_i(i):@sum(num_j(j):y(i,j))<=4;);@for(num_j(j):@sum(num_i(i):y(i,j))<=3;);@for(num_j(j):y(5,j)+y(6,j)>=1;);@for(link(i,j):2*y(i,j)<=x(i,j)<=a(i,j)*y(i,j););//换成两个不等式@for(link(i,j):@gin(y(i,j));y(i,j)>=0;);@for(link(i,j):@gin(x(i,j));x(i,j)>=0;);例4

东方大学计算机实验室聘用4名大学生(代号1,2,3,4)和2名研究生(代号5,6)值班答疑.已知每人从周一至周五每天最多可安排的值班时间及每人每h值班的报酬如下表所示：该实验室开放时间为上午8:00至晚上10:00,开放时间内须有且仅须一名学生值班.规定大学生每周值班不少于8h,研究生每周不少于7h,每名学生每周值班不超过3次,每次值班不少于7h,每天安排值班的学生不超过3人,且其中必须有一名研究生,试为该实验室安排一张人员的值班表，使总支付的报酬为最少．学生代号报酬元/h每天最多可安排的值班时间周一周二周三周四周五110.060607210.00606039.94830549.855604510.830480611.306063学生代号报酬元/h每天最多可安排的值班时间周一周二周三周四周五110.060607210.00606039.94830549.855604510.830480611.306063(1)该实验室开放时间为上午8:00至晚上10:00,开放时间内须有且仅须一名学生值班.(2)规定大学生每周值班不少于8h,(3)研究生每周不少于7h,(4)每名学生每周值班不超过3次,(5)每次值班不少于2h,(6)每天安排值班的学生不超过3人,(7)其中必须有一名研究生,设xij为学生i在周j值班时间

1,安排学生i在周j值班yij=

0,否则(1)(2)(3)(4)(5)(6)(7)得到数学模型为：设xij为学生i在周j值班时间

1,安排学生i在周j值班yij=

0,否则Lingo