有哪些信誉好的足球投注网站- 1、本文档共69页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
第五章 整数规划
第一节 整数规划数学模型及解的特点
第二节 割平面法
第四节 0-1型整数规划
第五节 指派问题
1/68
第一节 整数规划 模型及解的特点
一、整数规划模型一般形式
2/68
3/68
Max z=CX
s.t. AX ≤或=或≥ b
X≥0， b≥0
C=(c1, c2, … , cn )
X=(x1, x2, … , xn )T 有些或全部xj取整数
b=(b1, b2, … , bm )T
a11 a12 … a1n
A= a21 a22 … a2n
. . .
. . .
. . . mn
am1 am2 … amn
4/68
若对决策变量不提整数要求，则上述规划问题称为该整数规划问题的松弛问题。若松弛问题是线性规划问题，则该整数规划问题叫做整数线性规划。
整数线性规划有如下几种类型：
1. 纯整数线性规划——全部决策变量须取整数，亦称全整数规划。
2. 混合整数线性规划——部分决策变量须取整数。
3. 0-1型整数线性规划——决策变量只取0或1的整数线性规划。
5/68
二、 整数规划之例
[例1]某商场拟用集装箱托运两种货物，每箱体积、重量、可获利润以及所受限制如下表。
问：两种货物各托运多少，利润最大？
货物
体积
立方米/箱
重量
百斤/箱
利润
千元/箱
服装
5
2
20
玩具
4
5
10
托运限制
24
13
6/68
用x1和x2将表示服装和玩具的托运箱数，则该问题可表示如下：
Max z=20x1+10x2 (1)
s.t. 5x1 +4x2 ≤24 (2)
2x1+5x2 ≤13 (3)
x1，x2≥0， (4)
x1，x2取整数 (5)
7/68
[例2]某地区要建水电站，有15处可行，可用资金总额为B。各处所需投资和预期收益分别为aj和cj (j=1, 3, …, 15)。
要求是：
若在第一处建，第二处也要建；但是，第二处建；第一处不一定建；
第三和第四处至少有一处必须建；
第五、六和第七处建两个。
问：如何在这15处布置水电站，才能预期最大收益？
8/68
9/68
[例3]现有A1和A2生产某产品，在B1、B2 、B3和B4销售。因供不应求，计划再建一厂。新厂有方案A3和A4，建成后年生产费用分别为1200和1500万元。从产地到销地运费见下表。问哪一方案使新厂建成后年运费与生产费用总和最少？
B1
B2
B3
B4
产能（千吨/年）
A1
2
9
3
4
400
A2
8
3
5
7
600
A3
7
6
1
2
200
A4
4
5
2
5
200
需求量（千吨/年）
350
400
300
150
10/68
11/68
三、解的特点
整数线性规划的解一定是松弛问题的解，可行域是松弛问题可行域的子集。
目标函数值不会超过松弛问题目标函数值。
反过来，不一定成立。
不能将松弛问题的解四舍五入当作整数线性规划的解。
xj=1或0， j=1, 3, …, 15
12/68
现在看托运问题：
Max z=20x1+10x2
s.t. 5x1 +4x2 ≤24
2x1+5x2 ≤13
x1，x2≥0，
x1，x2取整数
先用图解法解松驰问题，得
13/68
4
x1
x2
3
2
2
5x1+4x2=24
z=20x1+10x2=96
z=15
o
A
(4.8, 0)
2x1+5x2 =13
6
z=90
(4, 1)
z=10
14/68
最优解是(x1,
文档评论（0）