航班指派问题(matlab)_OK_XIAOCHEN的博客-程序员秘密_指派问题matlab代码

技术标签: matlab  算法  矩阵  线性代数  

问题:

某航空公司经营 A B C 三个城市的航线,这些航线每天班次起飞与到达时间如下表。 设飞机在机场停留的 损失费用大致与停留 时间的平方成正比. 又每架飞机从降落 到下班起飞至少需 2 小时准备时间, 试决定一个使停留 费用损失为最小的 分配飞行方案。
航班
起飞
城市
起飞
时间
到达
城市

到达

时间

101
A
9:00
B
12:00
102
A
10:00
B
13:00
103
A
15:00
B
18:00
104
A
20:00
C
24:00
105
A
22:00
C
2:00 (次日)
106
B
4:00
A
7:00
107
B
11:00
A
14:00
108
B
15:00
A
18:00
109
C
7:00
A
11:00

110

C
15:00
A
19:00
111
B
13:00
C
18:00
112
B
18:00
C
23:00
113
C
15:00
B
20:00
114 C 7:00 B 12:00
A城市损失费用:

 B城市损失费用:

  C城市损失费用:

 

解题思路:
把从 A B C 城市起飞当作要完成的 “任务”, 则到达的飞机可看作待分派 去完成任务的“人”。
只要飞机到达两小时,即可分派去完成起飞任务。 则可分别对城市 A B C 列出分配问题的效率矩阵, 其中数字为飞机停留的 损失费用。
matlab代码如下:
%适用于任意n阶系数矩阵
clear all;
C=[4 9 64 169 225 
361 400 625 36 64 
225 256 441 4 16 
484 529 16 81 121 
196 225 400 625 9 ];%效率矩阵C
n=size(C,1);%计算C的行列数n
C=C(:);%计算目标函数系数,将矩阵C按列排成一个列向量即可。
A=[];B=[];%没有不等式约束
Ae=zeros(2*n,n^2);%计算等约束的系数矩阵a
for i=1:n
for j=(i-1)*n+1:n*i
Ae(i,j)=1;
end
for k=i:n:n^2
Ae(n+i,k)=1;
end
end
Be=ones(2*n,1);%等式约束右端项b
Xm=zeros(n^2,1);%决策变量下界Xm
XM=ones(n^2,1);%决策变量上界XM
[x,z1]=linprog(C,A,B,Ae,Be,Xm,XM);%使用linprog求解
x=reshape(x,n,n);%将列向量x按列排成一个n阶方阵
disp('最优解矩阵为:');%输出指派方案和最优值
Assignment=round(x)%使用round进行四舍五入取整
disp('最优解为:');
z1
%%
%适用于任意n阶系数矩阵
clear all;
C=[256 529 9 625 36 
225 484 4 576 25 
100 289 441 361 576 
64 225 361 289 484 
256 529 9 625 36 ];%效率矩阵C
n=size(C,1);%计算C的行列数n
C=C(:);%计算目标函数系数,将矩阵C按列排成一个列向量即可。
A=[];B=[];%没有不等式约束
Ae=zeros(2*n,n^2);%计算等约束的系数矩阵a
for i=1:n
for j=(i-1)*n+1:n*i
Ae(i,j)=1;
end
for k=i:n:n^2
Ae(n+i,k)=1;
end
end
Be=ones(2*n,1);%等式约束右端项b
Xm=zeros(n^2,1);%决策变量下界Xm
XM=ones(n^2,1);%决策变量上界XM
[x,z2]=linprog(C,A,B,Ae,Be,Xm,XM);%使用linprog求解
x=reshape(x,n,n);%将列向量x按列排成一个n阶方阵
disp('最优解矩阵为:');%输出指派方案和最优值
Assignment=round(x)%使用round进行四舍五入取整
disp('最优解为:');
z2
%%
%适用于任意n阶系数矩阵
clear all;
C=[49 225 225 49 
25 169 169 25 
169 441 441 169 
64 256 256 64];%效率矩阵C
n=size(C,1);%计算C的行列数n
C=C(:);%计算目标函数系数,将矩阵C按列排成一个列向量即可。
A=[];B=[];%没有不等式约束
Ae=zeros(2*n,n^2);%计算等约束的系数矩阵a
for i=1:n
for j=(i-1)*n+1:n*i
Ae(i,j)=1;
end
for k=i:n:n^2
Ae(n+i,k)=1;
end
end
Be=ones(2*n,1);%等式约束右端项b
Xm=zeros(n^2,1);%决策变量下界Xm
XM=ones(n^2,1);%决策变量上界XM
[x,z3]=linprog(C,A,B,Ae,Be,Xm,XM);%使用linprog求解
x=reshape(x,n,n);%将列向量x按列排成一个n阶方阵
disp('最优解矩阵为:');%输出指派方案和最优值
Assignment=round(x)%使用round进行四舍五入取整
disp('最优解为:');
z3
%%
z=z1+z2+z3

结果如下:

Optimal solution found.

最优解矩阵为:

Assignment =

     0     1     0     0     0
     0     0     0     1     0
     0     0     0     0     1
     0     0     1     0     0
     1     0     0     0     0

最优解为:

z1 =

   273


Optimal solution found.

最优解矩阵为:

Assignment =

     0     0     0     0     1
     1     0     0     0     0
     0     1     0     0     0
     0     0     0     1     0
     0     0     1     0     0

最优解为:

z2 =

   848


Optimal solution found.

最优解矩阵为:

Assignment =

     0     1     0     0
     0     0     1     0
     0     0     0     1
     1     0     0     0

最优解为:

z3 =

   627


z =

        1748

z1结果:

z2结果:

 

z3结果:

 

所以使停留费用损失最小的方案为:

101(A)→110(C) →104(A) →107(B) →103(A) →109(C) →112(B) →101(A)

102(A) →106(B) →102(A)

105(A) →108(B) →114(C) →111(B) →113(C) →105(A)

损失费:273K+848K+627K=1748K

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/OK_XIAOCHEN/article/details/124523838

智能推荐

[Android] 修图工具Draw9patch使用小结(附ubuntu快捷截图方法)_qq_35521087的博客-程序员秘密

做项目的时候,素材图遇到点问题,然后老大大概给我讲了讲android下面图片格式.9.png和draw 9-patch的用法,感觉很清楚也很有用,所以记录一下。原文地址请保留http://www.cnblogs.com/rossoneri/p/4024090.html 关于 9-patch的介绍我就不说了,网上一大堆。下面根据我做android项目的经历一点点来认识它的作用。首先,先看

C-01 手写数字识别_小猿取经的博客-程序员秘密

文章目录手写数字识别应用程序导入模块图像转向量训练并测试模型模型转应用程序展示图片处理图片预测图片手写数字识别应用程序导入模块import osimport pylabimport numpy as npfrom PIL import Imageimport matplotlib.pyplot as pltfrom sklearn.svm import SVC%matplotl...

JavaScript入门(part12)--内置对象_GoatGui的博客-程序员秘密

学习笔记,仅供参考,有错必纠参考自:pink老师教案文章目录JavaScript入门内置对象Math对象日期对象数组对象字符串对象JavaScript入门内置对象Math对象​ Math对象具有数学常数和函数的属性和方法。跟数学相关的运算(求绝对值,取整、最大值等)都可以使用 Math 中的成员,例如:属性、方法名功能Math.PI圆周率Math.floor()向下取整Math.ceil()向上取整Math.round()四舍五入,就近

动态修改页面标题title_hangGe0111的博客-程序员秘密

1.html<!DOCTYPE html><html> <head> <meta charset=utf-8 /> <meta name="viewport" content="width=device-width, initial-scale=1,"> <title>修改页面标题

面向特定问题的开源算法管理和推荐(一) | [email protected]_郭德纲闭门弟子的博客-程序员秘密

[email protected]一.课题总体概述二.课题总体任务三.组内分工情况四.核心代码分析情况五.编程环境配置​

Duilib 拖放按钮时获取当前按钮和拖放位置的布局名称_顾小白xx的博客-程序员秘密

最近由于公司要换界面 库所以想起了我之前用过的DUIlib 虽然之前也没有多深入但是能趁着这个机会把这个库用好。这个库由于网上版本较多,所以选择了旗舰版的一个分支,到目前还不错。功能其实比较简单,就是窗口有一排按钮要将按钮拖放到一块区域内然后根据按钮名创建对应得节点,这个功能在MFC 上其实很好实现,我这里有现成的例子,但是DUILIB虽然消息跟MFC 一样但是毕竟两个界面库肯定不能像MFC 那样做。好在这个库比较成熟了提供不少机制。这个问题其实也困扰了我好几天,首先按钮类要实现拖拽的效果并且加移动的阴影,

随便推点

创建list ALV tree[RS_TREE_LIST_DISPLAY]_banin4739的博客-程序员秘密

ABAP程序中的ALV显示是很常用的一种数据展示手段,除了常规的alv,有时也会用到ALV tree这种有层次结构的展示方式更好的展现数据,下面介绍一个创建list alv tree的方法:1)用函数RS_TREE_CONSTRUCT构造alv 树的层次结构,alv tree的节点类型(node type)分两种:T和P,区别如下:区别就是个文件夹的图标。&amp...

POJ - 1704 Georgia and Bob_k909397116的博客-程序员秘密

Georgia and Bob题意:一个水平网格上有N个棋子Georgia和Bob每到自己回合时可以向左移动网格上任意一个棋子任意步数棋子与棋子之间不能重叠和相互跨越假设Georgia和Bob都采用最优策略,谁会赢得比赛?输入要求:第一行依次输入网格上所有棋子所在的位置,如:1 3 6 7第二行输入先手者的名字,如:Georgia输出要求:如果Georgia赢的比赛,输出:“Georgia will win”如果Bob赢的比赛,输出:“Bob will win”思路:

Swift - 文本输入框内容改变时响应,并获取最新内容___zhangheng的博客-程序员秘密_swift获取输入框内容

1,问题描述有时我们开发的时候需要先把“确认”按钮初始设置为不可用,当文本框中输入文字以后,再将输入按钮变为可用。 2,实现原理(1)要检测文本框内容的变化,我们需要让新界面的Controller遵循一个文本协议UITextFieldDelegate。同时在viewDidLoad方法内将文本框的代理设置为当前实例。然后实现textFil...

Docker+springboot+mysql+nginx部署vue_傻蛋丫的博客-程序员秘密

一、Docker安装,参考上篇二、下载相关镜像网易云镜像中心https://c.163yun.com/hub#/library

Spring整合webSocket无法注入mapper,service的解决办法_往日时光--的博客-程序员秘密_websocket注入mapper

一、为什么webSocket无法注入mapper,service本质原因:spring管理的都是单例(singleton),和 websocket (多对象)相冲突。详细解释:项目启动时初始化,会初始化 websocket (非用户连接的),spring 同时会为其注入 service,该对象的 service 不是 null,被成功注入。但是,由于 spring 默认管理的是单例,所以只会注入一次 service。当新用户进入聊天时,系统又会创建一个新的 websocket 对象,这时矛盾出现了:sp

作为程序员,这个月我在坚持做的一些事_weixin_30426879的博客-程序员秘密

博客同步:http://blog.cxycs.com/article/269继上一篇《作为程序员,我意识到我有的一些毛病》之后,我决定去做一些事情来改变自己以及自己的生活。1、选择坚持在做决定去做与坚持在做是两个不同的概念。我不记得是在哪里看到这么一句话,如果你是懒惰的、有拖延症的,不妨找上自己能接受的一两件事儿坚持去做,最终你会慢慢的变得自律。于是,我找了下面几件事坚持...

推荐文章

热门文章

相关标签