【数模】整数规划模型

2024-07-13 07:42| 来源: 网络整理| 查看: 265

文章目录一、整数规划定义分类二、常用算法1.分支定界算法（1）步骤（2）算法基本原理（3）matlab代码 2.割平面算法三、指派问题1. 0-1变量的使用2. 指派问题的标准形式3. 匈牙利解法1）一般步骤：2） matlab代码

一、整数规划定义

1.数学规划中的变量（部分或全部）限制为整数时，称为整数规划。 2.若在线性规划模型中，变量限制为整数，则称为整数线性规划。 3.目前所流行的求解整数规划的方法，往往只适用于整数线性规划。目前还没有一种方法能有效地求解一切整数规划。

分类纯整数规划（完全整数规划）全整数规划混合整数规划0-1整数规划（指派问题、固定分配问题）（一个人干一件事）——一般用于工作安排，运动员分配

纯整数规划：所有决策变量要求取非负整数（这时引进的松弛变量和剩余变量可不要求取整数）全整数规划：除了所有决策变量要求取非负整数外，系数aij和常数bi也要求取整数（这时引进的松弛变量和剩余变量也必须是整数）混合整数规划：只有一部分的决策变量要求取非负整数，另一部分可以取非负实数 0－1整数规划：所有决策变量只能取 0 或 1 两个整数

在这里插入图片描述

- 松弛变量与剩余变量在这里插入图片描述

二、常用算法 1.分支定界算法（1）步骤

在这里插入图片描述

（2）算法基本原理

在这里插入图片描述

（3）matlab代码 //intprog.m function [x,fval,status] = intprog(f,A,B,I,Aeq,Beq,lb,ub,e) %整数规划求解函数 intprog() %其中 f为目标函数向量 % A和B为不等式约束 % Aeq与Beq为等式约束 % I为整数约束（决策变量的个数） % lb与ub分别为变量下界与上界 % x为最优解，fval为最优值 %例: % maximize 20 x1 + 10 x2 % S.T. % 5 x1 + 4 x2

【本文地址】

公司简介

联系我们