3.1整数规划问题.ppt

文档介绍：第3章整数规划
线性规划模型:
实际问题要求xi为整数!
如机器的台数,人数等
线性整数规划
非线性整数规划
简称整数规划
整数规划问题
一、实例
胜利家具厂生产桌子和椅子两种家具。桌子售价50元/个,椅子售价30元/个,生产桌子和椅子需要木工和油漆工两种工种。生产一个桌子需要木工4个小时,油漆工2小时。生产一个椅子需要木工3个小时,油漆工1小时。该厂每月可用木工工时为120小时,油漆工工时为50小时。问该厂如何组织生产才能使每月的销售收入最大?
纯整数规划
例(背包问题)一个旅行者,为了准备旅行的必备物品,要在背包里装一些有用的东西,但他最多只能携带b公斤的东西,而每件物品都只能整件携带,于是他给每件物品规定了一个“价值”,以表示其有用程度。如果共有m件物品,第i件件物品的重量为bi,价值为ci,问题就变成:在携带的物品总重量不超过b公斤的条件下,携带哪些物品可使总价值最大
解:
Z表示所带物品的总价值
携带物品的总重量
数学模型:
0-1规划
解:
数学模型:
混合型整数规划
纯整数规划
0—1规划
混合型整数规划
纯整数规划的数学模型:
0--1规划的数学模型:
例
×
√
√
√
√
Z=130
√
√
√
√
,可行且Z=140
不可行
可行
二、整数规划解的理论
(IP)
(IP)问题的松弛问题