数学建模之matlab中线性规划
目录
一、线性规划的标准形式
二、整数规划
二、整数规划之分支定界
1.概念
2、代码实现
三、整数规划之割平面法
1、基本思想
2、代码实现
四、整数规划之匈牙利算法（0-1）
1、适用情况
①0-1变量的使用
② 互斥问题
③固定费用问题
④指派问题
2、指派问题中匈牙利法
①步骤
②举例
3、代码实现
总结
一、线性规划的标准形式
求的是max，所以f中要加符号。f中是目标函数的系数
a表示的是不等式约束的系数（有不等号的，并且不等号为 0 && bound2
测试：
f=[-20 -10]; A=[5 4;2 5]; B=[24 13]; lb=[0 0]; [x,fval,status]= intprog(f,A,B,[1,2],[],[],lb)
三、整数规划之割平面法
1、基本思想
实例：
引入松弛变量 x7 x8 x9 x10
2、代码实现
定义一个函数DIvidePlane
function [intx,intf] = DividePlane(A,c,b,baseVector)
%功能：用割平面法求解整数规划
%调用格式：[intx,intf]=DividePlane(A,c,b,baseVector)
%其中, A：约束矩阵；
% c：目标函数系数向量；
% b：约束右端向量；
% baseVector：初始基向量；
% intx：目标函数取最值时的自变量值；
% intf：目标函数的最值；
sz = size(A);
nVia = sz(2);%获取有多少决策变量
n = sz(1);%获取有多少约束条件
xx = 1:nVia;
if length(baseVector) ~= n
disp('基变量的个数要与约束矩阵的行数相等！');
mx = NaN;
mf = NaN;
return;
end
M = 0;
sigma = -[transpose(c) zeros(1,(nVia-length(c)))];
xb = b;
%首先用单纯形法求出最优解
while 1
[maxs,ind] = max(sigma);
%--------------------用单纯形法求最优解--------------------------------------
if maxs x
x =
1.0000 1.0000
>> maxz=-fval%求得最大值，加负号
maxz =
2
四、整数规划之匈牙利算法（0-1）
1、适用情况
①0-1变量的使用
② 互斥问题
③固定费用问题
④指派问题
2、指派问题中匈牙利法
①步骤
②举例
3、代码实现
例子1
c = [3 8 2 10 3;8 7 2 9 7;6 4 2 7 5;8 4 2 3 5;9 10 6 9 10]
c = c(:); % 矩阵转换为向量
a = zeros(10,25);
for i = 1:5
a(i,(i-1)*5+1:5*i) = 1;
a(5+i,i:5:25) = 1;
end % 循环将指派问题转换为线性规划问题
b= ones(10,1); % 10个约束(5*2)
[x y] = linprog(c,[],[],a,b,zeros(25,1),ones(25,1));
X = reshape(x,5,5)
opt = y
例子2：
%% 指派问题（选择队员去进行游泳接力比赛）
clear;clc
c = [66.8 75.6 87 58.6 57.2 66 66.4 53 78 67.8 84.6 59.4 70 74.2 69.6 57.2 67.4 71 83.8 62.4]'; % 目标函数的系数矩阵（先列后行的写法）
intcon = [1:20]; % 整数变量的位置(一共20个决策变量，均为0-1整数变量)
% 线性不等式约束的系数矩阵和常数项向量（每个人只能入选四种泳姿之一，一共五个约束）
A = [1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0;
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1];
% A = zeros(5,20);
% for i = 1:5
% A(i, (4*i-3): 4*i) = 1;
% end
b = [1;1;1;1;1];
% 线性等式约束的系数矩阵和常数项向量 （每种泳姿有且仅有一人参加，一共四个约束）
Aeq = [1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0;
0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0;
0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0;
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1];
% Aeq = [eye(4),eye(4),eye(4),eye(4),eye(4)]; % 或者写成 repmat(eye(4),1,5)
beq = [1;1;1;1];
lb = zeros(20,1); % 约束变量的范围下限
ub = ones(20,1); % 约束变量的范围上限
%最后调用intlinprog()函数
[x,fval] = intlinprog(c,intcon,A,b,Aeq,beq,lb,ub)
% reshape(x,4,5)'
% 0 0 0 1 甲自由泳
% 1 0 0 0 乙蝶泳
% 0 1 0 0 丙仰泳
% 0 0 1 0 丁蛙泳
% 0 0 0 0 戊不参加
（感觉这个例子很实用，就引用过来了，要是有啥侵权，告诉我我删掉，不好意思）
总结
以上为线性规划中算法代码，图片来自数学建模老哥课上ppt，仅为笔记。
