《运筹学》教学课件 第四章 整数规划.pdfVIP

Operations Research 第四章 整数规划 cmLiu@shufe Operations Research 第四章 整数规划 整数规划问题——部分变量或全部变量要 求取整数的线性规划问题 如果所有的变量都要求取整数，这样的整 数规划问题称为纯整数规划；如果部分变 量要求取整数，这样的整数规划称为混合 整数规划问题。 cmLiu@shufe Operations Research 第四章 整数规划 本章主要介绍整数规划问题的提出、整数 规划问题的求解、0-1型整数规划及其求解、 指派问题、电子表格的建模和求解以及案 例分析。 cmLiu@shufe Operations Research 第四章 整数规划 4.1 整数规划问题的提出 4.2 整数规划问题的求解 4.3 0-1型整数规划 4.4 指派问题 4.5 电子表格建模和求解 4.6 案例研发新药项目 cmLiu@shufe Operations Research 4.1.1 整数规划的数学模型 例4.1 某厂可生产甲、乙两种设备，其生产数量受A 、B两 种主要资源供应量的限制，生产单位设备需要消耗Ａ、Ｂ 资源的数量及单位设备所获得的利润见下表。问该厂应安 排甲、乙两种设备各生产多少台，才能使利润达到最大？ cmLiu@shufe Operations Research 4.1.1 整数规划的数学模型 设备的台数必须 为整数 cmLiu@shufe Operations Research 4.1.1 整数规划的数学模型 一般地，整数规划的数学模型可以表示为： n max z ∑c x j j j 1 n ∑a x b (i 1,2,..., m)  ij j i j 1 s t ≥ j n . .xj 0( 1,2,..., )  xj 全为整数或部分变量为整数(j 1,2,...,n )   cmLiu@shufe Operations Research 4.1.2 整数规划的解 考虑与例4.1相对应的线性规划问题： * 5