排列与统筹学结合的经典问题,非高手勿入。

qq222ee 2007-11-26 05:46:17
加精
问题:
设方程组(如下)有解:
X1+3+X12=X2
X2+4+X13=X3
X2+4+X14=X4
X3+5+X15=X5
X4+7+X16=X5
X5+8+X17=X6
X6+1+X18=48
X7+5+X19=X8
X8+1+X20=X9
X8+1+X21=X10
X10+2+X22=29
X9+9+X23=X11
X11+7+X24=29
(Xi≥0;i =1,2,…24)

集合:
A={X1,X3,X5,X7,X8,X10,X11};
B={X2,X4,X6,X9};

设A中元素组成m组排列,B中元素组成n组排列.
每个集合中的元素取且仅取一次.(如A中可以形成3组排列:X3X8X7,X1,X5X10X11)
每个排列中元素按照排列顺序满足条件:
Xi+Txi≤Xj (j为排在i后元素,Txi为Xi所在上述方程式左侧时,该方程式中的常量,如Tx2=4)

(如:排列X1X3X7,满足条件
X1+3≤X3
X3+5≤X7 )


求满足方程组时,m+n最小时的排列.
...全文
5143 59 打赏 收藏 转发到动态 举报
写回复
用AI写文章
59 条回复
切换为时间正序
请发表友善的回复…
发表回复
eion 2011-03-20
  • 打赏
  • 举报
回复
很明显,这是一个整数规划问题,如果把原题改写成:


X1+X12- X2 = -3
X2+X13- X3 = -4
...
// 以下依次类推,不再赘述


再整理一下,即可得到一个标准的线性方程组,不过方程有24个变量而已
由于要求每个变量都取整数,因此是整数规划
如果用 lingo 语言求解,估计不到1分钟即可求出来


如果要详细了解,
see also: 数学建模 线性代数 整数规划 lingo 线性方程组
tyzqqq 2010-12-23
  • 打赏
  • 举报
回复
没看懂
codesnail 2010-09-27
  • 打赏
  • 举报
回复
围观一下能死啊?
world_broken 2010-09-09
  • 打赏
  • 举报
回复
我也发了个类似的帖子,最小子集覆盖,这问题本身是NP难。
据资料讲,貌似只能用 启发式算法,SA GA之类的,数据集较小时可以用贪心穷举,较大时就没办法了。
xero_123 2010-09-05
  • 打赏
  • 举报
回复
mark一下
b11ght 2010-05-21
  • 打赏
  • 举报
回复
a
bupt_xiaoz 2010-05-17
  • 打赏
  • 举报
回复
非高手,求围观
INGDI 2010-05-15
  • 打赏
  • 举报
回复
mark
学习了
chensb666 2010-03-29
  • 打赏
  • 举报
回复
Mark
ling301a 2009-12-16
  • 打赏
  • 举报
回复
mark
lostcountrymen 2008-07-30
  • 打赏
  • 举报
回复
zhenming_liu ,不知为什么,我觉得你很恶心。
你个死假洋鬼子
ffzhzhll 2008-07-27
  • 打赏
  • 举报
回复
直接找AMPLE源码……
kdliang031220 2008-07-24
  • 打赏
  • 举报
回复
不怎么懂...
超级大笨狼 2008-07-14
  • 打赏
  • 举报
回复
www.dullwolf.cn/chess/
效果:
代码:
www.dullwolf.cn/chess.rar
next163 2008-07-13
  • 打赏
  • 举报
回复
我*,居然快一年了....
ascent2006 2008-07-12
  • 打赏
  • 举报
回复
mark
panzi667 2008-07-12
  • 打赏
  • 举报
回复
up
YukiCEO 2008-07-11
  • 打赏
  • 举报
回复
[Quote=引用 27 楼 anjie4402211 的回复:]
在计算机帮人解决折磨人的问题的时候,
先是人被计算机折磨了
[/Quote]
bluefloat 2008-07-10
  • 打赏
  • 举报
回复
怎么觉得像是《运筹学》啊,里面都有解题的算法,只要有可以解题的模型,就能用计算机仿真。曾经完整实现过AHP层次模型。只要有算法就能实现。
iloveppmm 2008-07-09
  • 打赏
  • 举报
回复
汗啊 居然是07年的帖子。

有点疑问:

这样的题的意义在哪里?不是从某一特定问题抽象出来的数学模型吗?

这题有没有正确答案??存不存在正解?

要知道,这种形式的,既然是题,就应该本身就有答案的。否则,只能说那是猜想了。

题可不是随便出的。别最后是个无解题,只是因为它的复杂度一时无法证明无解。那就没什么意义了。

编程应该不是搞数学理论研究,数学在编程中的作用我想应该是解决问题而不是制造问题的。如果要是纯数学理论,那真看不出来对编程的有什么意义。
当然,也许限于我相对无知,还没理解到那个高度。

加载更多回复(39)

33,006

社区成员

发帖
与我相关
我的任务
社区描述
数据结构与算法相关内容讨论专区
社区管理员
  • 数据结构与算法社区
加入社区
  • 近7日
  • 近30日
  • 至今
社区公告
暂无公告

试试用AI创作助手写篇文章吧