数学建模算法与应⽤（python实现）第⼆章整数规划第⼆章整数规划 整数规划⼀般指整数线性规划
1. 概述
整数规划的分类
整数线性规划⼀般可分为两类：
1. 完全整数规划
2. 混合整数规划
整数规划的特点
1. 原线性规划有最优解
1. 原线性规划最优解全是整数，最优解⼀致
2. 整数规划⽆可⾏解
3. 有可⾏解，但最优解值会变差
2. 整数规划最优解不能按照师叔最优解简单的取证获得
求解⽅法分类
1. 分枝界定法——可求纯或混合整数线性规划。
2. 割平⾯法——可求纯或混合整数线性规划。
3. 隐枚举法——可求“0-1”整数规划。
1. 过滤隐枚举法
2. 分枝隐枚举法
4. 匈⽛利法——解决指派问题（“0-1”规划特殊情形）。
陆航飞行员开箱国产最先进武装直升机
5. 蒙特卡洛法——求解各种类型规划。
2. 0-1 型线性规划
强迫状态
x j
0-1规划的变量仅取值0或1。
相互排斥的约束条件
有两种运输⽅式可供选择，但只能选⼀种：
为解决问题，引⼊0-1变量则上述条件改写为
其中M为充分⼤的数。
关于固定费⽤的问题(Fixed Cost Problem)
在某要求成本最⼩化的问题中，往往需要投⼊固定成本，例如，选定的⽣产⽅式投资⾼，由于产量⼤，因⽽分配到每件产品的成本就降低，反之初期成本投⼊低，因⽽每件产品的⽣产成本就偏⾼。分别表⽰三种⽅式： 表⽰采⽤第 j ⽅式的产量
表⽰采⽤第种⽅式时每件产品的成本变动
表⽰第种⽅式时的固定成本
5x +14x ≤224 或 7x +13x ≤245(2.1)
y
y ={1，当采⽤船运⽅法时
0，当采⽤车运⽅法时(2.2)
人大释法⎩⎪⎨⎪⎧5x +4x ≤24+yM ,127x +3x ≤45+yM ,12y =0或1(2.3)
j =1,2,3x j c j j k j j
暂不考虑其他约束条件，采⽤各种⽅式的总成本为：
为了统⼀讨论，引⼊0-1变量，令
浅沼稻次郎于是⽬标函数转化为
公式可表⽰为下述三个线性约束条件
式中为充分⼩⼆点正常数；为充分⼤的正常数
指派问题的数学模型
分配⼈去做项⼯作，每⼈做且仅作⼀项⼯作，若分配第⼈去做第项⼯作，需花费单位时间，如何分配时⼯⼈花费的总时间最少引⼊0-1变量：
上述问的数学模型为求出最佳的x矩阵即可得到最优解，可使⽤匈⽛利算法，拍卖算法等算法。匈⽛利算法python 代码： P =j {k +c x , 当x >0时
j j j j 0, 当x =0时, j =1,2,3j (2.4)
y j y =j {1，当采⽤第i 种⽣产⽅式时
0，当不采⽤该⽣产⽅式时(2.5)
min z =(k y +11c x )+11(k y +22c x )+22(k y +33c x )33(2.6)
(2.4)y m ≤j x ≤j y M j (2.7)
m M n n i j C ij x =ij {1，第i ⼈做第j 项⼯作
0，第i ⼈不做第j 项⼯作(2.8)
min c xij ,i =1
∑n j =1∑n ij s .t .⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧x =1,i =1,...,n ,∑j =1n ij x =1,j =1,...,n ,∑i =1n ij x =0或1, i ,j =1,...,n .
ij
from scipy .optimize import linear_sum_assignment
cost =np .array ([[4,1,3],[2,0,5],[3,2,2]])
row_ind ,col_ind =linear_sum_assignment (cost )
print (row_ind )#开销矩阵对应的⾏索引
print (col_ind )#对应⾏索引的最优指派的列索引
print (cost [row_ind ,col_ind ])#提取每个⾏索引的最优指派列索引所在的元素，形成数组
print (cost [row_ind ,col_ind ].sum ())#数组求和
# 输出：
# [0 1 2]
# [1 0 2]
# [1 2 2]
# 5
3. 蒙特卡洛法（随机取样法)
蒙特卡洛法也成为计算机随机模拟法，使⽤该⽅法必须使⽤计算机⽣成相关分布的随机数，例：
import random
n = 10000000
x_min , x_max = 0.0, 12.0
y_min , y_max = 0.0, 9.0
total = 0.0
for i in range (n ):
x = random .uniform (x_min , x_max )
y = random .uniform (y_min , y_max )
if (y < x * x and x <= 3) or (y < 12 - x and x >= 3):
total += 1
print (12*9*total /10**7)
# 输出：
49.511304
输出应在49.5附近，由于时随机模拟，因此每次输出结果都不完全相同
在⼀定计算量的情况下，蒙特卡洛法完全可以的出⼀个满意解。
例:
对于⾮线性整数规划，可使⽤蒙特卡洛法进⾏估算：
由于python下np随机耗时较⼤，使⽤C++
y =x , y =212−x 与x 轴在第⼀象限围成⼀个曲边三⾓形。设计⼀个随机试验，求该图形⾯积的近似值。max z =x +12x +223x +324x +422x −528x −12x −23x −3x −42x 5s .t .=⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧0≤x ≤99,i x +x +x +x +x ≤400,12345x +2x +2x +x +6x ≤800,123452x +x +6x ≤200,123x +x +5x ≤500.345(2.9)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i, lim) for(int i=0;i<lim;++i)
const int inf =0x3f3f3f3f;
int x[10];
int check(){
哈尔滨体育学院学报int sum =0;
REP(i,5) sum+=x[i];
if(sum>400)return0;
if(x[0]+2*x[1]+2*x[2]+x[3]+6*x[4]>800)return0;
if(2*x[0]+x[1]+6*x[2]>200)return0;
if(x[2]+x[3]+5*x[4]>200)return0;
return1;
}
void getRadom(int i){
srand((unsigned)time(NULL)*i);
REP(i,5) x[i]=rand()%100;
while(!check())REP(i,5) x[i]=rand()%100;
}
ll get_tot(){
ll ans = x[0]*x[0]+ x[1]*x[1]+3*x[2]*x[2]+4*x[3]*x[3]+2*x[4]*x[4]-8*x[0]+2*x[1]-3*x[2]-x[3]-2*x[4];
return ans;
}
int main()
{
int lim =2e7;
ll tot =-inf;
REP(i, lim){
getRadom(i);
ll tmp =get_tot();
tot = tot>tmp ? tot:tmp;
}
cout<<tot<<endl;
return0;
mpeg编码}
/*
输出：
51549
*/
python代码:
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议