运筹学第四章--整数规划和分配问题(新)aPPT课件

性规划，也称为全整数线性规划。 • 混合整数线性规划 • 决策变量中的一部分必需取整数值，
而其他的可以不取整数值的整数线性规 划。 • ０－１型整数线性规划 • 决策变量只能取０或１的整数线性规
4.1.3 建立整数规划模型
• 实例分析： • 一家电子厂消费两种产品Ａ１和Ａ２，
需经过三道工序加工：Ｂ１，Ｂ２，Ｂ ３。单件加工利润以及各工时每周限额 如表所示。应该如何安排消费才干获得 最大利润？
• 最后求得最优解为 A＝４，B＝１， 目的函数为１４。
问题二上 界14.5下界
13
松弛问
题上界 14.75下 界13
问题三上界 13.5下界13
问题四 A=3B=2Z=13
问题五 A=4B=1Z=14
• 利用分枝定界法求解整数规划问题的步 骤:
• 第一步：求解相应的线性规划问题，并 确定目的函数值的上下界。
4.4.2 0-1规划的解题过程
• 实例分析： • ＡＫ公司预备开发几种新产品，该公司的四个
工程小组分别都提出了各自的方案，但是由于 公司的投资金额有限，不能对一切工程进展投 资，必需在其中作出选择。表４－５列出了各 个工程对于资金、任务人员以及将会产生的净 现值的情况。总的投资额为１１００万元，可 以调用的任务人员一共有２２人。关于投资的 工程，还有一个附加条件，即工程１和工程４ 由于某些缘由不得同时投资。应该如何挑选投 资工程？
工程
产品
A
〔件〕
1
A 产品 〔件〕 2
工时限额 〔小时/周〕
工序B1 0.4 0.5 200
工序B2 0.4 0.3 180
工序B3 0.3 0.2 120
利润〔元/件〕 30 28 --
解题过程：

ΣXij=1 j=1,…,n
Xij=0或1
任务 甲 乙 丙 丁
E
J G
R
2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9
指派问题解法—匈牙利法

第一步 造0—— min各行各列减其最小元素
2 15 13 4 2 0 13 11 2 0 13 7 0 10 4 14 15 4 6 0 10 11 6 0 6 9 B C 9 14 16 13 9 0 5 7 4 0 5 3 2 7 8 11 9 7 0 1 4 2 0 1 0 0 4 2 min 第二步 圈0——寻找不同行不同列的 0元素，圈
1、不考虑整数约束，解相应LP问题 2、检查是否符合整数要求，是，则得最优解， 完毕。否则，转下步 3、任取一个非整数变量xi=bi，构造两个新的 约束条件：xi ≤[bi] ,xi ≥ [bi]+1,分别加入到上 一个LP问题，形成两个新的分枝问题。 4、不考虑整数要求，解分枝问题。若整数解 的Z值>所有分枝末梢的Z值，则得最优解。否 则， 取Z值最大的非整数解，继续分解，Go to 3
5 5 20 15
2 18
6 14
12 8
2 4
4 10
背包问题的数学模型

解：设01变量表示携带物品i，表示不携 带物品i，则问题可写为
maxZ 20 x1 15 x2 18 x3 14 x4 8 x5 4 x6 10 x7 5 x1 5 x2 2 x3 6 x4 12 x5 2 x6 4 x7 ≤ 25 s.t. xi 取 0 或 1，i 1, 2, ,7

松弛问题 Z0=5.545 x1=1.477 x2=4.068 x1≤1 子问题 B1 Z0=5.533 x1=1 x2=4.333 x2≤4 子问题 B3 Z0=5 x1=1 x2=4 x1≥2 子问题 B2 Z0=4.5 x1=2 x2=2.5

整数规划的特点及应用
解：对每个投资项目都有被选择和不被选择两种可能，因此 分别用0和1表示，令xj表示第j个项目的决策选择，记为：
j投 资 1 对 项 目 xj ( j 1,2,..., n) j不 投 资 0 对 项 目
投资问题可以表示为：
max z
c
j 1
n
j
xj
n a j x j B j 1 x2 x1 s .t x 3 x4 1 x5 x6 x7 2 ） x j 0或者1 （j 1, 2, L n
B1 B2 B3 B4 年生产能力
A1
A2 A3 A4 年需求量
2
8 7 4 350
9
3 6 5 400
3
5 1 2 300
4
7 2 5 150
400
600 200 200
工厂A3或A4开工后，每年的生产费用估计分别为1200万或1500万元。 现要决定应该建设工厂A3还是A4，才能使今后每年的总费用最少。
0-1型整数线性规划：决策变量只能取值0或1的整数线性 规划。
整数规划的特点及应用
整数规划的典型例子
例4.1 工厂A1和A2生产某种物资。由于该种物资供不应求，故需要 再建一家工厂。相应的建厂方案有A3和A4两个。这种物资的需求地 有B1,B2,B3,B4四个。各工厂年生产能力、各地年需求量、各厂至各 需求地的单位物资运费cij，见下表：
例4.3 设整数规划问题如下
max Z x1 x 2 14x1 9 x 2 51 6 x1 3 x 2 1 x , x 0且 为 整 数 1 2
首先不考虑整数约束，得到线性规划问题（一般称为松弛问 题）。

三、投资问题
某公司在今后五年内考虑给以下的项目投资。已知： 项目A：从第一年到第四年每年年初需要投资，并于次年末
回收本利115%，但要求第一年投资最低金额为4万元，第 二、三、四年不限； 项目B：第三年初需要投资，到第五年未能回收本利128％， 但规定最低投资金额为3万元，最高金额为5万元； 项目 C：第二年初需要投资，到第五年未能回收本利140%， 但规定其投资额或为2万元或为4万元或为6万元或为8万元。 项目 D：五年内每年初可购买公债，于当年末归还，并加利 息6%，此项投资金额不限。
= 1.15x1A+ 1.06x2D； 第四年：年初的资金为 1.15x2A+1.06x3D，于是 x4A + x4D =
1.15x2A+ 1.06x3D； 第五年：年初的资金为 1.15x3A+1.06x4D，于是 x5D =
引入约束 xi ≤ M yi ，i =1，2，3，M充分大，以 保证当 yi = 0 时，xi = 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
一、投资场所的选择
京成畜产品公司计划在市区的东、西、南、北四区建立销售
门市部，拟议中有10个位置 Aj ( j＝1，2，3，…，10)可供 选择，考虑到各地区居民的消费水平及居民居住密集度，规