行业知识
数学建模之matlab中线性规划
目录
一、线性规划的标准形式
二、整数规划
二、整数规划之分支定界
1.概念
2、代码实现
三、整数规划之割平面法
1、基本思想
2、代码实现
四、整数规划之匈牙利算法（0-1）
1、适用情况
①0-1变量的index.php/tags-602.html" >使用
② 互斥问题
③固定费用问题
④指派问题
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:5a(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 戊不参加
（感觉这个例子很实用，就引用过来了，要是有啥侵权，告诉我我删掉，不好意思）
总结
