[数学]整数规划.ppt

整数规划 整数规划 第4章例4中，要求决策变量都是整数。当时我们将此题作为线性规划问题处理，得到解后四舍五入得到最优解。 求整数解的线性规划问题，不是用四舍五入法或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决。 整数规划：要求其中全部或者部分决策变量是整数的规划问题。 整数规划 纯整数规划问题：所有的变量都为非负整数 混合整数规划问题：有一部分变量为非负整数 0-1变量：变量的取值只限于0和1 0-1规划：所有的变量都为0-1变量 松弛问题：将决策变量是整数的约束取消后的线性规划问题 整数规划的图解法 例：某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如表所示。甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大。 整数规划的图解法 解：设x1 、 x2分别为甲、乙两种货物托运的件数，建立模型 目标函数： max z = 2x1 +3x2 约束条件： s.t. 195 x1 + 273 x2 ≤ 1365 4 x1 + 40 x2 ≤ 140 x1 ≤ 4 x1，x2 ≥ 0 为整数 整数规划的图解法 得到线性规划的最优解为x1=2.44, x2=3.26,目标函数值为14.66。 由图表可看出，整数规划的最优解为x1=4, x2=2,目标函数值为14。 整数规划问题的性质 性质1： 任何求最大目标函数值的纯整数规划或混合整数规划的最大目标函数值小于或等于松弛问题的最大目标函数值； 任何求最小目标函数值的纯整数规划或混合整数规划的最小目标函数值大于或等于松弛问题的最小目标函数值。 整数规划的应用——投资场所的选择 例：京成畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Aj (j＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定：在东区由A1，A2，A3 三个点至多选择两个；在西区由A4，A5 两个点中至少选一个；在南区由A6，A7 两个点中至少选一个；在北区由A8，A9，A10三个点中至少选两个。Aj 各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见表所示 (单位：万元)。但投资总额不能超过720万元，问应选择哪几个销售点，可使年利润为最大? 整数规划的应用——投资场所的选择 解：设：0-1变量 xi = 1 (Ai 点被选用）或 0 (Ai 点没被选用）。 这样我们可建立如下的数学模型： max z =36x1+40x2+50x3+22x4+20x5+30x6+25x7+48x8+58x9+61x10 s.t. 100x1+120x2+150x3+80x4+70x5+90x6+80x7+140x8+160x9+180x10 ≤ 720 x1 + x2 + x3 ≤ 2 x4 + x5 ≥ 1 x6 + x7 ≥ 1 x8 + x9 + x10 ≥ 2 xi ≥ 0 且xi 为0-1变量，i = 1,2,3,……,10 整数规划的应用——固定成本问题 例：高压容器公司制造小、中、大三种尺寸的金属容器，所用资源为金属板、劳动力和机器设备，制造一个容器所需的各种资源的数量如表所示。不考虑固定费用，每种容器售出一只所得的利润分别为 4万元、5万元、6万元，可使用的金属板有500吨，劳动力有300人/月，机器有100台/月，此外不管每种容器制造的数量是多少，都要支付一笔固定的费用：小号是l00万元，中号为 150 万元，大号为200万元。现在要制定一个生产计划，使获得的利润为最大。 整数规划的应用——固定成本问题 解：设x1，x2， x3 分别为小号容器、中号容器和大号容器的生产数量。 各种容器的固定费用只有在生产该种容器时才投入，为了说明固定费用的这种性质，设 yi = 1(当生产第 i 种容器, 即 xi ＞ 0 时) 或 0（当不生产第 i种容器即 xi = 0 时）。 引入约束 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