当前位置：文档之家 › (完整word版)整数规划的数学模型及解的特点

(完整word版)整数规划的数学模型及解的特点

  • 格式：doc
  • 大小：185.00 KB
  • 文档页数：14

下载文档原格式

  / 14

合集下载

4.1-整数规划的特点及作用

4.1-整数规划的特点及作用

结束！
例2 利用0-1变量将下述条件表示成一般线性 约束条件

变量x只能取值0,3,5或7中的一个
定义 1 假定x取到第i个值 yi (i 1, 2,3, 4) 0 否则 则 x 0 y1 3 y2 5 y3 7 y4 y1 y2 y3 y4 1
纯整数规划

例1.某集装箱运输公司有甲乙两种货物 可供装运，相关数据如下表，问如何装 运使得每车的收益最高？
约束 货物 甲
5 2
2000
乙
4 5
1000
限量
体积（M3） 重建模
max z 2000x1 1000x2 5 x1 4 x2 24 s.t.2 x1 5 x2 13 x , x 0且为整数 1 2
§2设置逻辑变量建立整数规划模型

约束条件的右端项可能是r个值中的某一个,即
a x
定义
j 1 j
n
j
b1或b2或或br
1 假定约束右端项为bi yi (i 1, , r ) 0 否则 则
r n a j x j bi yi i 1 j 1 y y y 1 1 2 r

例3.某公司拟投资800万元开辟新的商业网点,可供 选择的店铺有6个,有三个附加条件:第一,若选择项 目1,就必须同时选择项目2;第二,项目2、3、4中至 少选择一个;第三,项目5、6中最多选择一个.怎样选 择项目才能使总预期收益最大？
店铺
1
投资额（万元） 投资收益（万元/年）
240 80
2
3 4
§2设置逻辑变量建立整数规划模型

两组条件中满足其中一组 若x1 4, 则x2 1; 否则 x1 4 , x2 3

运筹学CH4整数规划

运筹学CH4整数规划
解决方案
使用整数规划求解器进行求解，得到最优的员工任务指派 方案。
05
整数规划软件实现
MATLAB实现整数规划
MATLAB优化工具箱
MATLAB提供了专门的优化工具箱，其中包含用于解决整 数规划问题的函数和算法。
intlinprog函数
该函数用于解决线性整数规划问题，可以处理大规模问题， 并提供多种求解选项。
CPLEX提供了多种建模方式，包括使 用API接口、编程语言（如Python、 Java）和交互式界面等。
CPLEX采用了先进的分支定界算法和启发式 算法，能够快速有效地求解大规模整数规划 问题。同时，CPLEX还提供了多种参数设置 和求解选项，以满足不同问题的需求。
06
整数规划总结与展望
整数规划研究现状
跨学科融合
整数规划与运筹学、计算机科学、数学等多个学 科密切相关，跨学科融合将为整数规划的研究和 应用带来更多机遇。
THANK YOU
感谢聆听
求解过程
在LINGO中，用户需要编写包含目标函数和约束条件的模型文件，然后调用 LINGO求解器进行求解。LINGO会自动选择合适的算法，并输出最优解和相关 信息。
CPLEX实现整数规划
CPLEX优化器
建模方式
求解算法
CPLEX是IBM提供的一款高性能数学 优化软件，支持线性规划、混合整数 规划和二次规划等多种问题类型。
在物流领域，整数规划可用于 优化运输路线和配送计划，以 减少运输时间和成本。
金融投资
在金融领域，整数规划可用于 投资组合优化，选择最佳的投 资组合以最大化收益并降低风 险。
城市规划
在城市规划中，整数规划可用 于优化城市布局和交通网络设 计，以提高城市运行效率和居 民生活质量。

运筹学第5章：整数规划

运筹学第5章：整数规划
1 xj 0 对项目j投资 对项目j不投资 （j 1， ，n） 2，
则问题可表示为：
max z c j x j
j 1 n
n a j x j B j 1 x1 x2 0 s.t. x3 x4 1 x x x 2 7 5 6 x j 0或1 j 1,2, , n 【例5-3】工厂A1和A2生产某种物资，由于该种物资供不应 求，故需要再建一家工厂，相应的建厂方案有A3和A4两个。这 种物资的需求地有B1、B2、B3、B4四个。各工厂年生产能力、各 地年需求量、各厂至各需求地的单位物资运费cij(j=1,2,3,4) 见表5-2。
三、割平面法的算法步骤
步骤1：将约束条件系数及右端项化为整数，用单纯形法求 解整数规划问题(ILP)的松弛问题(LP)。设得到最优基B，相应 的基最优解为X*。 步骤2：判别X*的所有分量是否全为整数？如是，则X*即为 (ILP)的最优解，算法终止；若否，则取X*中分数最大的分 量 x * ，引入割平面(5.7)。
表5-2
Ai cij A1 A2 Bj B1 2 8 B2 9 3 B3 3 5 B4 4 7 生产能力 (千吨/年) 400 600
A3
A4 需求量(千吨/年)
7
4 350
6
5 400
1
2 30025 150200200工厂A3或A4开工后，每年的生产费用估计分别为1200万元或 1500万元。现要决定应该建设工厂A3还是A4，才能使今后每年 的总费用(即全部物资运费和新工厂生产费用之和)最少。
一般来说，整数线性规划可分为以下几种类型：
1. 纯整数线性规划(Pure Integer Linear Programming)： 指全部决策变量都必须取整数值的整数线性规划，也称为全整 数规划。 2. 混合整数线性规划(Mixed Integer Linear Programming)：指决策变量中一部分必须取整数值，而另一部 分可以不取整数值的整数线性规划。 3. 0-1整数线性规划(Zero-one Integer Linear Programming)：指决策变量只能取0或1两个值的整数线性规划。

整数规划模型

整数规划模型
决策变量全部取 0 或1的规划称为0-1 整数规划
王秋萍：整数规划模型
为(非负)整数
仅一部分变 量为整数
4
有些问题用线性规划数学模型无法描述，可以 通过设置逻辑变量建立整数规划的数学模型。
王秋萍：整数规划模型
5
逻辑变量在建立数学模型中的作用
m个约束条件中只有k个起作用
设m个约束条件可表为
∑a x
ij j =1
n
j
≤ bi
i = 1, 2, " , m
定义 又M为任意大的正数，则
n ⎧ ⎪ ∑ aij x j ≤ bi + Myi j =1 ⎨ ⎪ y + y +" + y = m − k 2 m ⎩ 1
王秋萍：整数规划模型
6
逻辑变量在建立数学模型中的作用
约束条件的右端项可能是r个值 ( b1 , b2 ," , br ) 中的一个，即 n
( i = 1," , m; j = 1," , m ) 则分配问题的数学模型为 min z = ∑∑ a x
m m i =1 j =1 ij
ij
⎧ m xij = 1 ( i = 1,", m ) ⎪ ∑ j =1 ⎪ m ⎪ ( j = 1,", m ) ⎨ ∑ xij = 1 ⎪ i =1 ⎪ xij = 0或1 ( i = 1," , m; j = 1," , m ) ⎪ ⎩
j = 1, 2, 3 ⎧ x j − My j ≤ 0 ⎪ x + x + x ≥ 4000 ⎪ 1 2 3 ⎨ ⎪ x1 ≤ 1500, x2 ≤ 2000 ⎪ ⎩ x j ≥ 0, y j = 1或0, j = 1, 2, 3

整数规划的数学模型及解的特点-推荐下载

整数规划的数学模型及解的特点-推荐下载

变量 xi 称为 0—1 变量，或称为二进制变量。 0—1 型整数规划中 0—1 变量作为逻辑变量(logical variable)，常被用来表 示系统是否处于某一特定状态，或者决策时是否取某个方案。
1 如果决策i为是或有 xi 0 如果决策i为否或无
一、0—1 型整数规划的典型应用问题 例 1：背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、 绳索、帐篷、照相器材、通信器材等。每种物品的重量和重要性系数如表所示。 设登山队员可携带的最大重量为 25kg,试选择该队员所应携带的物品。
对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行高中资料试卷调整试验；通电检查所有设备高中资料电试力卷保相护互装作置用调与试相技互术通关，1系电过，力管根保线据护敷生高设产中技工资术艺料0不高试仅中卷可资配以料置解试技决卷术吊要是顶求指层，机配对组置电在不气进规设行范备继高进电中行保资空护料载高试与中卷带资问负料题荷试2下卷2，高总而中体且资配可料置保试时障卷，各调需类控要管试在路验最习；大题对限到设度位备内。进来在行确管调保路整机敷使组设其高过在中程正资1常料中工试，况卷要下安加与全强过，看度并22工且22作尽22下可22都能22可地护以缩1关正小于常故管工障路作高高；中中对资资于料料继试试电卷卷保破连护坏接进范管行围口整，处核或理对者高定对中值某资，些料审异试核常卷与高弯校中扁对资度图料固纸试定，卷盒编工位写况置复进.杂行保设自护备动层与处防装理腐置，跨高尤接中其地资要线料避弯试免曲卷错半调误径试高标方中高案资等，料，编试要5写、卷求重电保技要气护术设设装交备备置底4高调、动。中试电作管资高气，线料中课并敷3试资件且、设卷料中拒管技试试调绝路术验卷试动敷中方技作设包案术，技含以来术线及避槽系免、统不管启必架动要等方高多案中项；资方对料式整试，套卷为启突解动然决过停高程机中中。语高因文中此电资，气料电课试力件卷高中电中管气资壁设料薄备试、进卷接行保口调护不试装严工置等作调问并试题且技，进术合行，理过要利关求用运电管行力线高保敷中护设资装技料置术试做。卷到线技准缆术确敷指灵设导活原。。则对对：于于在调差分试动线过保盒程护处中装，高置当中高不资中同料资电试料压卷试回技卷路术调交问试叉题技时，术，作是应为指采调发用试电金人机属员一隔，变板需压进要器行在组隔事在开前发处掌生理握内；图部同纸故一资障线料时槽、，内设需，备要强制进电造行回厂外路家部须出电同具源时高高切中中断资资习料料题试试电卷卷源试切，验除线报从缆告而敷与采设相用完关高毕技中，术资要资料进料试行，卷检并主查且要和了保检解护测现装处场置理设。备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况，然后根据规范与规程规定，制定设备调试高中资料试卷方案。

(完整word版)整数规划的数学模型及解的特点

(完整word版)整数规划的数学模型及解的特点

整数规划的数学模型及解的特点整数规划IP (integer programming ）:在许多规划问题中,如果要求一部分或全部决策变量必须取整数。

例如,所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP 。

松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。

若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear programming)。

一、整数线性规划数学模型的一般形式∑==nj jj x c Z 1min)max(或中部分或全部取整数n j nj i jij x x x mj ni x b xa ts ,...,,...2,1,...,2,10),(.211==≥=≥≤∑=整数线性规划问题可以分为以下几种类型1、纯整数线性规划（pure integer linear programming ）:指全部决策变量都必须取整数值的整数线性规划。

有时,也称为全整数规划.2、混合整数线性规划(mixed integer liner programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。

3、0—1型整数线性规划（zero —one integer liner programming ）：指决策变量只能取值0或1的整数线性规划。

1 解整数规划问题0—1型整数规划0-1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的变量xi 称为0-1变量，或称为二进制变量.⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤+≥+≤-+=且为整数0,5210453233max 2121212121x x x x x x x x x x z0—1型整数规划中0—1变量作为逻辑变量(logical variable ），常被用来表示系统是否处于某一特定状态,或者决策时是否取某个方案。

运筹学基础及应用_(第四章_整数规划与分配问题)

运筹学基础及应用_(第四章_整数规划与分配问题)
号与7号必须同时开采；
（d） 8
（e）1号、
4号、6号、9号开采时不能超过两个，试表示上
述约束条件。
Next
基础教研室
（a）当x8=1 当x8=0 ∴ x8 x6
x6=1，x6≠0 x6=1，x6=0
（b）当x5 =1 当x5 =0 ∴ x5 + x3 1
x3=0， x3 ≠1 x3=0， x3 =1
基础教研室
【例1】求下述整数规划的最优解
Max z= 3x1 + 2x2 st . 2x1 + 3x2 14 x1 + 0.5x2 4.5 x10，x20，且为整数
基础教研室
x2 x1+0.5x2=4.5
4
(3.25, 2.5) 2 2x1+3x2=14
2
4
6
x1
3x1+2x2=6
二、整数规划的求解方法
1 －选择电网供应 设 y1 0 －不选择电网供应
10 d j x j f (1 y1 ) M j 1 10 0.3d j x j p (1 y2 ) M j 1 y1 y2 1 y1 , y2 0或1
基础教研室
【例3】投资决策问题 某公司准备1000万元资金在10个地点中选择若干个建立 工厂（工厂名称用地点名来命名），有关数据如下：
由于各个工厂之间有配套和协作关系，因此必须满足条件： 1、 建工厂1就必须同时建工厂2； 2、 若建工厂2就不允许建工厂3； 3、 工厂4和工厂5至少建一个； 4、 工厂6，7，8恰好建2个； 5、 工厂8，9，10最多建2个； 6、 建工厂4或者建工厂6，就不能建工厂8，反过来也一样； 7、 条件2，3，5最多满足2个。 问选择哪几个地点建厂最有利？ Next

第五章-整数规划

第五章-整数规划

在E点取得最优解。即
x2
x1＝2, x2 =3, Z(211)＝－17
找到整数解，问题已探明，此枝 3
停止计算。
求（LP212），如图所示。此时
F在点取得最优解。即x1＝3, x2
=2.5,
1
Z(212)＝－31/2≈－15.5 > Z(211)
如对LP212继续分解，其最小值
也不会低于－15.5 ，问题探明,
例5.2 现有资金总额为B。可供选择的投资项目有n个，项目j 所需投资额和预期收益分别为aj和cj（j＝1,2,..,n），此外由 于种种原因，有三个附加条件：
若选择项目1，就必须同时选择项目2。反之不一定; 项目3和4中至少选择一个； 项目5,6,7中恰好选择2个。 应该怎样选择投资项目，才能使总预期收益最大。
现求整数解(最优解):如用舍
入取整法可得到4个点即(1，3),(2 x2
⑴
⑵
，3),(1，4),(2，4)。显然，它们 都不可能是整数规划的最优解。 3
(3/2,10/3)
按整数规划约束条件，其可行 解肯定在线性规划问题的可行域 内且为整数点。故整数规划问题 的可行解集是一个有限集，如右
图所示。其中(2,2),(3,1)点的目 标函数值最大，即为Z=4。
考虑纯整数规划问题：
设其中aij和bi皆为整数（若不为整数时，可乘上 一个倍数化为整数）。
割平面法（纯整数）
割平面法是R.E.Gomory于1958年提出的一种方法， 它主要用于求解纯ILP。
割平面法是用增加新的约束来切割可行域，增加的新 约束称为割平面方程或切割方程。其基本思路为：
若其松弛问题的最优解X*不满足整数约束，则从X*的 非整分量中选取一个，用以构造一个线性约束条件，将其加 入原松弛问题中，形成一个新的线性规划，然后求解之。若 新的最优解满足整数要求，则它就是整数规划的最优解；否 则重复上述步骤，直到获得整数最优解为止。

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

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

匈牙利法思路：若能在 [Cij] 中找出 n 个位于
不同行不同列的0元素(称为独立0元素)，则
令解矩阵[xij]中对应这n个独立0元素的元素
取值为 1 ，其他元素取值为 0 ，则它对应目
标函数zb=0是最小的。这就是以[Cij]为系数
矩阵分配问题的最优解，也得原问题的最
优解。
定理1 若从分配问题效率矩阵[cij]的每一行元素中分别减去 (或加上)一个常数ui(称为该行的位势)，从每一列分别减去 (或加上)一个常数vj(称为该列的位势)，得到一个新效率矩阵 [bij]，若其中bij=cij-ui-vj，则[bij]的最优解等价于[cij]的最优解
第1步：找出效率矩阵每行的最小元素，并分别从每行
中减去。
第2步：再找出矩阵每列的最小元素，并分别从各列中 减去。
2 10 9 7 2 15 4 14 8 4 13 14 16 11 11 4 15 13 9 4
0 8 7 5 11 0 10 4 0 3 5 0 0 11 9 5
表明m个约束条件中有(m-k)个的右端项为( bi+M )，不起约 束作用，因而，只有k个约束条件起作用。 ② 约束条件的右端项可能是r个值b1 , b2 ,, br 中的某一个 即： 定义：
n
aij x j b1 或b2或或br
j 1
1 假定约束右端项为 bi yi 否则 0
现用下例来说明： max z=40x1+90x2 9x1+7x2≤56 7x1+20x2≤70 x1，x2≥0 x1，x2整数 ① ② ③ ④ ⑤
解：先不考虑条件⑤，即解相应的线性规划B,①～④(见图5-2)， 得最优解x1=4.81，x2=1.82，z0=356

整数规划

整数规划

7
二、固定成本问题 例2．高压容器公司制造小、中、大三种尺寸的金属容器， 所用资源为金属板、劳动力和机器设备，制造一个容器所需 的各种资源的数量如表所示。不考虑固定费用，每种容器 售出一只所得的利润分别为 4万元、5万元、6万元，可使用的 金属板有500吨，劳动力有300人/月，机器有100台/月，此外 不管每种容器制造的数量是多少，都要支付一笔固定的费用： 小号是l00万元，中号为 150 万元，大号为200万元。现在要制 定一个生产计划，使获得的利润为最大。
=0。
这样我们可建立如下的数学模型： Max z = 4x1 + 5x2 + 6x3 - 100y1 - 150y2 - 200y3 s.t. 2x1 + 4x2 + 8x3 ≤ 500 2x1 + 3x2 + 4x3 ≤ 300 x1 + 2x2 + 3x3 ≤ 100 xi ≤ M yi ，i =1，2，3，M充分大 xj ≥ 0 yj 为0--1变量，i = 1,2,3
线性规划的最优解为x1=2.44, x2=3.26,目标函数值为14.66。由图表
可看出，整数规划的最优解为x1=4, x2=2,目标函数值为14。 一般求整数解的线性规划问题，不可用四舍五入法或去尾法对线性规
划的非整数解加以处理来解决整数规划。
在整数规划中，如果所有的变量都为非负整数，则称为纯整数规划问 题；如果有一部分变量为负整数，则称之为混合整数规划问题。在整 数规划中，如果变量的取值只限于0和1，这样的变量我们称之为0-1 变量。在纯整数规划和混合整数规划问题中，如果所有的变量都为01变量，则称之为0-1规划。
9
三、分布系统设计 例3．某企业在 A1 地已有一个工厂，其产品的生产能力为 30 千箱，为了 扩大生产，打算在 A2，A3，A4，A5地中再选择几个地方建厂。已知在 A2 ， A3，A4，A5地建厂的固定成本分别为175千元、300千元、375千 元、500千元，另外， A1产量及A2，A3，A4，A5建成厂的产量，那时 销地的销量以及产地到销地的单位运价(每千箱运费)如下表所示。

整数规划简介

整数规划简介

4.1
整数规划的数学模型
4.2
分枝定界法
4.3
指派问题
4.4
指派问题的Excel处理
4.1 整数规划的数学模型
4.1.1 案例
• 例4.1 某厂生产A、B两种产品，这两种 产品的单位利润分别为25元和40元。
• 生产每种产品都需要3道工序，其各种产 品的工时（单位：时）、每一工序每周可 供使用的时间如表4.1所示，问工厂如何安 排生产，使其获利最大？
4.1.2 整数规划数学模型的一般形式
• 整数规划数学模型一般可以表示如下：
• 式中opt即optimize（最优化）的缩写，根 据问题要求不同，可以表示为max（最大化） 或min（最小化）。
• 整数规划可分为以下3种类型。
（1）纯整数规划（pure integer linear programming）
• 例如，所求解是机器的台数、工人的人 数或装货的车数、场址的选定等，都必须 部分或者全部满足整数要求，这样的问题 称为整数线性规划问题，简称为整数规划， 记为ILP。
• 整数规划的应用范围是极其广泛的，它 不仅在工业、工程设计和科学研究方面有 许多应用，而且在计算机设计、系统可靠 性、编码、经济分析等方面也有新的应用。
• 因此不能简单地将松弛问题的最优解舍 入化整（如四舍五入），得出整数规划的 最优解。
• 通过仔细分析，从图4.1可知，整数规划 问题的可行解集是相应的线性规划问题的 可行域内的整数格子点，它是一个有限集。
• 因此，我们可以用另一种方法进行讨论， 即将所有的可行解依次代入目标函数，比较 所得的目标函数值的大小，从而得到最优解。
• 在这类决策问题中，问题是在“要”或 者“不要”之间进行选择，我们可以令决 策变量是整数，且只取0或1，分别表示不 投资或者投资。

整数规划(数据模型与决策)

整数规划(数据模型与决策)

0-1型整数线性规划：决策变量只能取值0或1的整数线性 规划。
整数规划的特点及应用
Page 4
例:指派问题或分配问题。人事部门欲安排四人到四个不同岗 位工作，每个岗位一个人。经考核四人在不同岗位的成绩 （百分制）如表所示，如何安排他们的工作使总成绩最好。
工作
人员 甲 乙 丙 丁
A 85 95 82 86
1 x ij 0
指派第 i个 人 做 第 j件 事 ( i , j 1,2,..., n) 不指派第 i个 人 做 第 j件 事
分配问题与匈牙利法
指派问题的数学模型为：
Page 8
min Z
c
i 1 j 1
n
n
ij
x ij
n x ij 1 ( i 1.2. .n) j 1 n x ij 1 ( j 1.2. .n) i 1 x ij 取0或1(i , j 1.2. .n)
Page 19
0 13 7 0 6 0 6 9 0 5 3 2 0 1 0 0
0 Ø 6 0 ◎ Ø 0
13 7 ◎ 0 ◎ 0 6 9 5 3 2 1 ◎ 0 Ø 0
独立0元素的个数为4 , 指派问题的最优指 派方案即为甲负责D工作，乙负责B工作， 丙负责A工作，丁负责C工作。这样安排 能使总的工作时间最少，为4＋4＋9＋11 ＝28。
2）试指派（找独立0元素）
Page 22
2 2 4 4 0
0 4 2 4 5 0 3 0 1 0 1 3 0 3 5 1 2 3 0 5
2 2 4 4 ◎ 0
◎ 0
5 1 0 Ø 2
4 2 4 0 3 ◎ 0 Ø ◎ 0 1 3 3 5 1 3 Ø 0 5

第五章 整数规划

第五章 整数规划

令 x3′=1-x3, x4′=1-x4, x5′=1-x5，得 Max z=2x2+4x3′+5x5′+7x4′+8x1-16 3x2- x3′- 3x5′- 2x4′+3x1≤-2 ① 3x2+2x3′- x5′+ x4′+5x1≤6 ② x2, x3′,x5′,x4′,x1 =0或1
z=8,不可行 x2 =x3′=x5′ = x4
若某行(列)已有0元素，那就不必再减了。例1的计算为：
2 15 10 4 ) 9 14 8 7 4 14 15 16 13 11 9 13
( c ij
-2 -4 -9 -7
0 6 0 0
13 0 0 1
11 10 7 4
2 11 4 2
R0: z0=356 x1=4.81 x2=1.82
x1 ≤4
x1≥5
R2:z2=341 x1=5.00 x2=1.57 x1 ≤1 x1≥2
R1:z1=349 问题R2为: x1=4.00 Max z=40x1+90x2 x2=2.10 9x1+7x2≤56 7x1+20x2 ≤ 70 x1 ≥ 5 x2 ≤2 x2≥3 x1,x2 ≥ 0
指派问题的数学模型可写成如下页形式：
min z

i1 j1
n
n
c ij x ij
第j项工作由 一个人做 第i人做 一项工作

i1
n
x ij 1 x ij 1
( j 1 , , n)

j1
n
( i 1 , , n ) (i 1, , n; j 1, , n)

第五章 整数线性规划

第五章 整数线性规划

整数线性规划问题的最优解
A
第1节 整数线性规划的数学模型及解的特点
例2：某宝石加工厂最近新到6粒大小、质量等级 相似的钻石毛料，管理层有两种选择，一是切 磨成一般的皇冠形，每粒可获利2.5千元；一 是切磨成虽然较难切磨但当前市场较流行的心 形，每粒可获利4千元。若切磨成皇冠形则每 粒需要5个工作日，若切磨成心形则每粒需要9 个工作日，由于工厂切工师傅较忙，最多只有 45个工作日来做这批工作。另外，由于毛料自 身形状的关系，其中只有4粒毛料可以切磨成 皇冠形，而6粒毛料中任何一粒都可以切磨成 心形。那么，管理层应如何决策才能使这批钻 石获利最大？
例5：某服务部门各时段（每2h为一时 段）需要的服务员人数见下表。按规 定，服务员连续工作8h（即四个时段 ）为一班。现要求安排服务员的工作 时间，使服务部门服务员总数最少。
时段 1 2 3 4 5 6 7 8
服务员最少数目
10
8
9
11 13
8
5
3
第3节 0-1型整数线性规划
例5： 解：设在第j时段开始时上班的服务员人数为xj。
min z cij xij 1200 y 1500 1 y
i 1 j 1 4 4
x11 x21 x31 x41 350 x x x x 400 12 22 32 42 x13 x23 x33 x43 300 x14 x24 x34 x44 150 x x x x 400 11 12 13 14 x x x x 600 21 22 23 24 x31 x32 x33 x34 200 y x41 x42 x43 x44 200 1 y x 0，， (i j =1， 2， 3， 4) ij y 0或1

《运筹学》胡运权清华版-5-01整数规划的数学模型及解的特点

《运筹学》胡运权清华版-5-01整数规划的数学模型及解的特点

分析：
A3与A4不可兼
＝>y1+y2=1
＝>y2=1－y1
因此：二选一时候也常常只引入一个0－1
变量y即可
a
23
综上：A3与A4中选一处建厂可表示成 x31＋x32 ＋ x33 ＋ x34＝200y x41＋x42 ＋ x43 ＋ x44＝200（1－y）
这里y＝1表示选A3，y＝0表示选A4
y
1
用0－1变量表示选择： 1——选；0——不选
a
8
解：设决策变量
1 对项目j投资 x j 0 对项目j不投资 j 1,2,...n
a
9
约束： 1、若选项目1，就必须选项目2；反之则不一定；
x1 1x2 1 x21 时 ， x10 或 1均 可
满足此约束的项目1、2全部选择组合
x1 x2
11
x1 x2
01
00
a
10
约束： 2、项目3和4中至少选一个；
项目3、4的全部选择组合
x3 x4 00 01 10 11
x3 x4 1
a
11
约束： 3、项目5、6、7中恰好选两个；
x5x6x7 2
a
12
约束： 4、总金额限制——总金额为B
a x 项目 j 的实际投资额 =
aj
0
xj 1
jx j j 0
0
若建厂A3 若建厂A4
a
24
目标：min （运费＋生产费）
运费
cij
A1 A2 A3 A4 需求
B1
B2
2x11
8x21 7x31
9x12 3x22 6x32
4x41 5x42
350 400

第05章整数规划(胡运权)

第05章整数规划(胡运权)
j=1
n
n ai j x j (或=，或 )bi (i 1, 2,.., m) j=1 s.t. x j 0( j 1, 2,.., n) x1 , x2 ,..., xn中全部取整数
0-1 整 数 规 划 模 型
max(或min)= ci x j
ij ij ij

非基变量下标集合
aij f aij aij
符号[*]表示不超过“*”的最大整数，f(*) 表示“*”的非负真分数。
对整数规划问题 IP： max z CX AX b s.t X 0 x j 为整数
不妨设
其松弛问题 L0 max z CX AX b s.t X 0

有一旅行团从 v0出发要遍游城 市 v1 , v 2 ,...,v n，已知从 v i 到 v j 的旅费为 cij，问应如何安排行 程使总费用最小？


旅游 售货 员问 题模 型
变量—是否从i第个城市到第j个城市； 约束—每个城市只能到达一次、离开 一次； 目标—总费用最小；
min
c
线性规划 L1 : max z CX AX b nm f s.t im j x m j f i 0 j 1 X 0
… 0 ︰
… 1
… 0 ︰
… 0
a1m+1 ︰
aim+1
[aim j ] f im j n … λm+j … λn 0 f im j 1 … a j 1 ,1m+j 2,n … m a1n
i 0 j 0
n
n
ij x ij
n xij 1; i 1,2,...,n j 0 n s.t. xij 1; j 1,2,...,n i 0 u u nx n 1;1 i j n j ij i xij 1,0, i 1,2,...,n, j 1,2,...,n
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

整数规划的数学模型及解的特点整数规划IP (integer programming)：在许多规划问题中，如果要求一部分或全部决策变量必须取整数。

例如，所求的解是机器的台数、人数、车辆船只数等，这样的规划问题称为整数规划，简记IP 。

松弛问题(slack problem)：不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为该整数规划问题的松弛问题。

若松弛问题是一个线性规化问题，则该整数规划为整数线性规划(integer linear programming)。

一、整数线性规划数学模型的一般形式∑==nj jj x c Z 1min)max(或中部分或全部取整数n j nj i jij x x x mj ni x b xa ts ,...,,...2,1,...,2,10),(.211==≥=≥≤∑=整数线性规划问题可以分为以下几种类型1、纯整数线性规划(pure integer linear programming)：指全部决策变量都必须取整数值的整数线性规划。

有时，也称为全整数规划。

2、混合整数线性规划(mixed integer liner programming)：指决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。

3、0—1型整数线性规划(zero —one integer liner programming)：指决策变量只能取值0或1的整数线性规划。

1 解整数规划问题0—1型整数规划0—1型整数规划是整数规划中的特殊情形，它的变量仅可取值0或1，这时的⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤+≥+≤-+=且为整数0,5210453233max 2121212121x x x x x x x x x x z变量xi 称为0—1变量，或称为二进制变量。

0—1型整数规划中0—1变量作为逻辑变量(logical variable)，常被用来表示系统是否处于某一特定状态，或者决策时是否取某个方案。

⎩⎨⎧=为否或无如果决策为是或有如果决策i i x i 01一、0—1型整数规划的典型应用问题例1：背包问题：一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。

每种物品的重量和重要性系数如表所示。

设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。

解：引入0—1变量xi, xi=1表示应携带物品i ，,xi=0表示不应携带物品i⎩⎨⎧==≤++++++++++++=7,...,2,1,10254212625510481418152076543217654321i x x x x x x x x x x x x x x x naxz i 或上述问题就是一个标准的0-1整数规划问题，解得：X*=(1,1,1,1,0,1,1)’ Z*=81例2：集合覆盖和布点问题某市消防队布点问题。

该市共有6个区，每个区都可以建消防站，市政府希望设置的消防站最少，但必须满足在城市任何地区发生火警时，消防车要在15min 内赶到现场。

据实地测定，各区之间消防车行驶的时间见表，请制定一个布点最少的计划。

解：引入0—1变量xi, xi=1表示在该区设消防站，,xi=0表示不设⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧=≥++≥++≥++≥+≥++≥++++++=01111111min 6526545434362121654321或i x x x x x x x x x x x x x x x x x x x x x x x z解得： X*=(0,1,0,1,0,0)’ Z*=2二、特殊约束的处理1.矛盾约束：建模时，有时会遇到相互矛盾的约束，而模型只能两者取一或，例如下面两个约束)2(0)()1(3)(≤≥x f x f先不等式同向处理，原式可化为：)4(0)()3(0)(3≤≤-x f x f ，再引入一个0－1变量y, 及一个很大的正数M ，)6()1()()5()(3y M x f My x f -≤≤-y=0时，(5)与(1)相同，(6)自然满足，实际上不起作用 y=1时，(6)与(2)相同，(5)自然满足，实际上起作用对于形似)0()( a a x f ≥，可以用以下一对约束代替a x f a x f -≤≥)()(约束同向处理，改为()()f x a f x a-≤-≤-引入0—1变量后，()()(1)f x a My f x a M y -≤-+≤-+-2.多中选一的约束模型希望在下列几个约束中，只能有一个约束有效：)1(),...,2,1(0)(n i x f i =≤引入n 个0－1整数变量yi, i=1,2,…,n.则上式可改写为：yi=0时，（2）自然满足，此时约束不起作用 yi=1时，约束起作用。

而和式保证了在0—1整数变量中有一个且也只有一个取值1，其余取0值。

若希望有k 个约束有效，只需将(3)改为ky y y n =+++ (21)3、某市为方便学生，拟在新建的7个居民小区增设若干所学校。

已知各备选校址代号及其能覆盖的居民小区编号如表1所示，问要覆盖所有居民小区至少应建多少所学校？对应的校址代号是哪些？ 表1解：对每一个学校定义一个变量j x1，当某居民小区可由第j 个学校负责 j x＝0，当某居民小区不可由第j 个学校负责)3(1...)2(),...,2,1()1()(21=+++=-≤n i i y y y n i y M x f则对于第1个小区：1231x x x ++≥对于第2个小区：241x x +≥ 对于第3个小区：351x x +≥ 对于第4个小区：461x x +≥ 对于第5个小区：12341x x x x +++≥ 对于第6个小区：561x x +≥ 对于第7个小区：11x = Min z =61jj X=∑解得：()*1,0,0,1,1,0TX = *Z =3例2 有两个相互排斥的约束条件244521≤+x x 或 453721≤+x x 。

为了统一在一个问题中，引入10-变量y ，则上述约束条件可改写为：⎪⎩⎪⎨⎧=-+≤++≤+10)1(453724452121或y M y x x yM x x其中M 是充分大的数。

例3 约束条件01=x 或 8005001≤≤x可改写为⎩⎨⎧=≤≤108005001或y y x y3.1.3 关于固定费用的问题（Fixed Cost Problem ）在讨论线性规划时，有些问题是要求使成本为最小。

那时总设固定成本为常数，并在线性规划的模型中不必明显列出。

但有些固定费用（固定成本）的问题不能用一般线性规划来描述，但可改变为混合整数规划来解决，见下例。

例5 某工厂为了生产某种产品，有几种不同的生产方式可供选择，如选定的生产方式投资高（选购自动化程度高的设备），由于产量大，因而分配到每件产品的变动成本就降低；反之，如选定的生产方式投资低，将来分配到每件产品的变动成本可能增加。

所以必须全面考虑。

今设有三种方式可供选择，令j x 表示采用第j 种方式时的产量；j c 表示采用第j 种方式时每件产品的变动成本； jk 表示采用第j 种方式时的固定成本。

为了说明成本的特点，暂不考虑其它约束条件。

采用各种生产方式的总成本分别为⎪⎩⎪⎨⎧=>+= 0 ,00,j j j j j j x x x c k P 当当 3,2,1=j .在构成目标函数时，为了统一在一个问题中讨论，现引入10-变量jy ，令⎪⎩⎪⎨⎧==>.00,0,1时种生产方式，即当不采用第时，种生产方式，即当采用第j x j j x j j y于是目标函数)()()(m in 333322221111x c y k x c y k x c y k z +++++= （3）（3）式这个规定可表为下述3个线性约束条件：3,2,1,=≤≤j M y x y j j j ε （4）其中ε是一个充分小的正常数，M 是个充分大的正常数。

（4）式说明，当>j x 时jy 必须为1；当=j x 时只有j y为0时才有意义，所以（4）式完全可以代替（3）式。

例8 求解下列指派问题，已知指派矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡1096109532485724679278310283，求最小指派问题。

数学模型为：Min z=3*x11+8*x12+2*x13+10*x14+3*x15+8*x21+7*x22+…+ 5511*ijijj i ax ==∑∑……+9*x51+10*x52+6*x53+9*x54+10*x55 X11+x12+x13+x14+x15=1……511 1..5ijj xi ===∑X51+x52+x53+x54+x55=1 X11+x21+x31+x41+x51=1 …..X15+x25+x35+x45+x55=1 Xi,j=0,1Lingo 程序为： model:sets:row/1..5/: ;col/1..5/: ;link(row,col):a,x;endsetsdata:a=3 8 2 10 38 7 2 9 76 4 27 58 4 2 3 59 10 6 9 10;enddatamin = @sum(link(i,j):a(i,j)*x(i,j));@for(row(i):@sum(col(j):x(i,j))=1);@for(col(j):@sum(row(i)|i#le#2:x(i,j))+@sum(row(i)|i#ge#3:x(i,j))=1);end篮球队需要选择5名队员组成出场阵容参加比赛。

8名队员的身高和擅长位置见下表：出现阵容应满足以下条件：中锋只能有一个上场；x1+x2=1至少有一名后卫；x6+x7+x8>=1如1号和4号上场，则6号不出场； y=x1+x4 ,if y=2 x6=0X1 <= x62号和6号至少保留一个不出场。

X2+x6 <=1应当选择哪5名队员上场，才能使出场队员平均身高最高？\\\\公司生产A 、B 、C 三种产品，售价分别为12元、7元和6元。

生产每单位A 需要1小时技术服务、10小时直接劳动、3千克材料；生产每单位B 需要2小时技术服务、4小时直接劳动、2千克材料；生产每单位C 需要1小时技术服务、5小时直接劳动、1千克材料；现在最多能提供100小时技术服务、700小时直接劳动、400千克材料；生产成本是生产量的非线性函数，如下所示：要求建立一个总利润最大的生产计划数学模型。

设产品A 的产量为1x ，且1111040y x ⎧=⎨≤≤⎩0，其他， 121140100y x ⎧=⎨<≤⎩0，其他， 1311100150y x ⎧=⎨<≤⎩0，其他， 1411150y x ⎧=⎨>⎩0，其他，设产品B 的产量为2x ，且：2121050y x ⎧=⎨≤≤⎩0，其他， 222150100y x ⎧=⎨<≤⎩0，其他，2321100y x ⎧=⎨>⎩0，其他，设产品C 产量为3x ，且：31310100y x ⎧=⎨≤≤⎩0，其他， 3231100y x ⎧=⎨>⎩0，其他，设总利润为：y[][][]1112131412122232313231231231231112131421222331321111121131112(10987)7(643)6(54)100,10425700,324001,1,1040,40100,100150..Max y y y y y x y y y x y y x x x x x x x x x x y y y y y y y y y x y x y x y s t x y =-++++-+++-+++≤++≤++≤+++=++=+=≤≤<≤<≤3242212223233313123150,050,50100,100,0100,100,0(1,2,3)0(1,2,3)0(1,2,3)0(1,2)j j j j x y x y x y x y x y x j y j y j y j ⎧⎪⎪⎪⎪⎨>≤≤<≤⎪⎪>≤≤>≥=⎪======⎪⎩或1，或1，或12 某钻井队要从以下10个可供选择的井位中确定5个钻井采油，目的是使总的钻井费用最小。