公告:1)网站程序升级:Q2A升级到1.8.6,Wordpress升级到5.7.2
2)修复了头像加载慢与提交问题反应慢等问题
2021-06-16

欢迎来到 Mathematica 问答社区

提问时请贴上文本代码

语法高亮:在编辑器中点击

被禁止的话题:广告破解

请阅读:《提问的智慧》

备用域名:mma.ooo

支持LaTex数学公式
行内公式标识符:\$ 或“$\backslash ($”+“$\backslash )$”,
行间公式标识符:\$\$ 或 “$\backslash [$”+“$\backslash ]$”

社区建议QQ群:365716997

分类

0 投票
1.2k 浏览

模型如下   

主要是求解一个四个人面试问题 面试分为3阶段每个阶段限制一人每个人面试时间不同 求如何安排次序可以让面试时间最短  其中$t_{ij}$表示第i个人第j阶段面试所用时间 $x_{ij}$表示第i个人第j阶段面试开始时刻  $y_{ik}$表示第k个人是不是排在第j个人后面(1为是0为不是) 第一个约束表示每个人只有完成前面的面试才能进入下一阶段的面试 第二,三个约束一个阶段面试只有一个人 最后一个约束保证最后一个人完成时间为最短的T时间。

运行的代码如下

NMinimize[{T, T >= 20 + x13, T >= 18 + x23, T >= 10 + x33, 
  T >= 15 + x43, 13 + x11 <= x12, 15 + x12 <= x13, 10 + x21 <= x22, 
  20 + x22 <= x23, 20 + x31 <= x32, 16 + x32 <= x33, 8 + x41 <= x42, 
  10 + x42 <= x43, 13 + x11 - x21 <= T y12, 
  10 - x11 + x21 <= T (1 - y12), 15 + x12 - x22 <= T y12, 
  20 - x12 + x22 <= T (1 - y12), 20 + x13 - x23 <= T y12, 
  18 - x13 + x23 <= T (1 - y12), 13 + x11 - x31 <= T y13, 
  20 - x11 + x31 <= T (1 - y13), 15 + x12 - x32 <= T y12, 
  16 - x12 + x32 <= T (1 - y13), 20 + x13 - x33 <= T y13, 
  10 - x13 + x33 <= T (1 - y13), 13 + x11 - x41 <= T y14, 
  8 - x11 + x41 <= T (1 - y14), 15 + x12 - x42 <= T y14, 
  10 - x12 + x42 <= T (1 - y14), 20 + x13 - x43 <= T y14, 
  15 - x13 + x43 <= T (1 - y14), 10 + x21 - x31 <= T y23, 
  20 - x21 + x31 <= T (1 - y23), 20 + x22 - x32 <= T y23, 
  16 <= T (1 - y23), 18 + x23 - x33 <= T y23, 
  10 - x23 + x33 <= T (1 - y23), 10 + x21 - x41 <= T y24, 
  8 - x21 + x41 <= T (1 - y24), 20 + x22 - x42 <= T y24, 
  10 - x22 + x42 <= T (1 - y24), 18 + x23 - x43 <= T y24, 
  15 - x23 + x43 <= T (1 - y24), 20 + x31 - x41 <= T y34, 
  8 - x31 + x41 <= T (1 - y34), 16 + x32 - x42 <= T y34, 
  10 - x32 + x42 <= T (1 - y34), 10 + x33 - x43 <= T y34, 
  15 - x33 + x43 <= T (1 - y34), 1 >= y12 >= 0, 1 >= y13 >= 0, 
  1 >= y14 >= 0, 1 >= y23 >= 0, 1 >= y24 >= 0, 
  1 >= y34 >= 0, (y12 | y13 | y14 | y23 | y24 | y34) \[Element] 
   Integers}, {T, x11, x12, x13, x21, x22, x23, x31, x32, x33, x41, 
  x42, x43, y12, y13, y14, y23, y24, y34}]

可是求解不出来 用别的软件却可以 想知道有什么方法吗?

用户: 新手 (81 分)
修改于 用户:新手
你的条件限制没打错??
£是小于等于号 我是直接复制老师ppt的条件 ppt上是用lingo解出来的
哪些条件都是啥关系,与还是或???
我怎么看不清楚呢,T是变量还是目标函数?
还有里面的£,以及上下脚标,都看不清楚,重新整理。
另外,社区支持LaTex数学公式。

2 个回答

+1 投票
 
已采纳

直接穷举吧

In[50]:= t = {{13, 15}, {10, 20}, {20, 16}, {8, 10}};
{#, Fold[{#1[[1]] + #2[[1]], 
        Max[#1[[1]] + #2[[1]], #1[[2]]] + #2[[2]]} &, {0, 0}, 
      t[[#]]][[2]]} & /@ Permutations[Range@Length[t]] // 
 MinimalBy[#, Last] &

Out[51]= {{{4, 2, 1, 3}, 69}, {{4, 2, 3, 1}, 69}}

Permutations表示所有可能的排列顺序,对每种排列顺序用Fold算出所需时间,最后用MinimalBy选出用时最短的就行了

Fold里面的具体含义是假设第i个人离开第轮的时刻为${t_{i,1},t_{i,2}}$

如果t中元素的长度不为2,更一般的写法如下

{#, Fold[Block[{i = 2, list = #2}, 
FoldList[Max[#2, #1 + list[[i++]]] &, #1 + list]] &, 
ConstantArray[0, Length@t[[1]]], t[[#]]][[-1]]} & /@ 
Permutations[Range@Length[t]] // MinimalBy[#, Last] &

中间那个FoldList的作用就是替代嵌套的Max,只要搞清楚#1、#2分别代表什么还是很容易看懂的(注意#1 + list中的#1和#1 + list[[i++]]中的#1不同)

===========================9月10日编辑===================================

在下面瓦屋的答案里提到了用LinearProgramming做0-1规划,所以来补充一下做法

首先需要承认MMA里LinearProgramming的帮助并不是特别的好懂,虽然道理都说得挺明白了然而看着总是有些蛋疼,所以我特意写了下注释,对照帮助应该就能比较清楚了

(t = {{13, 15, 20}, {10, 20, 18}, {20, 16, 10}, {8, 10, 15}};
{n, m} = Dimensions[t];(*n个人,共m轮*)
max = n*Max@Total[t, {2}];(*总时间不超过用时最多的一个人的n倍*)
(*待规划变量,x[i,j]为第i个人开始第j轮的时间,
y[i,k]表示第k个人是不是排在第i个人后面(1为是0为不是),
T为总时间*)
X = Flatten[{Array[x, {n, m}], 
Table[y[i, k], {i, 1, n - 1}, {k, i + 1, n}], T}];

cons = Flatten[{
(*每个人只有完成前面的面试才能进入下一阶段的面试*)
Table[
x[i, j + 1] - x[i, j] >= t[[i, j]], {i, 1, n}, {j, 1, m - 1}],
(*每个阶段面试不超过一个人*)
Table[
x[i, j] - x[k, j] + max y[i, k] <= max - t[[i, j]], {i, 
n - 1}, {k, i + 1, n}, {j, m}],
Table[
x[i, j] - x[k, j] + max y[i, k] >= t[[k, j]], {i, n - 1}, {k, 
i + 1, n}, {j, m}],
(*总时间大于等于每个人完成的时间*)
Table[T - x[i, m] >= t[[i, m]], {i, n}]
}];

ans = LinearProgramming[
(*使得c.X为T*)
ReplacePart[ConstantArray[0, Length@X], -1 -> 1],
(*将约束整理为矩阵形式*)
Function[cond, Coefficient[cond[[1]], #] & /@ X] /@ cons,
{cons[[All, 2]], 
cons[[All, 0]] /. {GreaterEqual -> 1, LessEqual -> -1, 
Equal -> 0}}\[Transpose],
(*变量取值范围,x[i,j]与T为0到max,y[i,j]为0或1*)
X /. {x[__] :> {0, max}, y[__] :> {0, 1}, T -> {0, max}},
(*求解数域为整数域*)
Integers]) // AbsoluteTiming
(*将结果处理为顺序形式*)
rules = Thread[X -> ans];
{ans[[-1]], Sort[Range[n], (y[##] /. rules) == 1 &]}

结果如下

{0.0109446, {8, 21, 36, 21, 36, 56, 31, 56, 74, 0, 8, 18, 1, 1, 0, 1, 
0, 0, 84}}

{84, {4, 1, 2, 3}}

可以看到用时只有0.011s,虽然还是比直接枚举慢一个数量级,然而已经比Minimize高到不知哪里去了

(好吧我仔细试了一下,发现LinearProgramming快主要是因为用了浮点数,把Minimize换成NMinimize速度就基本一样了。。。。。)

用户: 无影东瓜 (1.2k 分)
修改于 用户:无影东瓜
t = {{13, 15, 20}, {10, 20, 18}, {20, 16, 10}, {8, 10, 15}};
{#, Fold[{#1[[1]] + #2[[1]],
        Max[#1[[1]] + #2[[1]], #1[[2]]] + #2[[2]],
        Max[Max[#1[[1]] + #2[[1]], #1[[2]]] + #2[[2]], #1[[3]]] + \
#2[[3]]} &, {0, 0, 0}, t[[#]]][[3]]} & /@
  Permutations[Range@Length[t]] // MinimalBy[#, Last] &
这个是根据你的写的3个阶段版的
想问一下第三阶段的Max的那部分可以简化吗?
可以简化,方法已更新至答案
+2 投票

主要问题应该是在于对诸x变量没有加非负限制(mma需要手动添加而非类似其他软件如lingo自动默认),于是无限迭代;其次最好不要在类似13+ x11 - x21 <= T y12这样的条件中出现T变量,这样会变成二次规划,及其耗时且不能保证收敛到最优解,解决的办法通常采用一个足够大的数M来降次。 下面是在你的源代码上修改后的结果,可运行,结果正确,但是为了尽量少改动于是很难看:

NMinimize[{T, T >= 20 + x13, T >= 18 + x23, T >= 10 + x33, 
   T >= 15 + x43, 13 + x11 <= x12, 15 + x12 <= x13, 10 + x21 <= x22, 
   20 + x22 <= x23, 20 + x31 <= x32, 16 + x32 <= x33, 8 + x41 <= x42, 
   10 + x42 <= x43, 
   "{13+x11-x21\[LessEqual]T y12,10-x11+x21\[LessEqual]T \
(1-y12),15+x12-x22\[LessEqual]T y12,20-x12+x22\[LessEqual]T \
(1-y12),20+x13-x23\[LessEqual]T y12,18-x13+x23\[LessEqual]T \
(1-y12),13+x11-x31\[LessEqual]T y13,20-x11+x31\[LessEqual]T \
(1-y13),15+x12-x32\[LessEqual]T y12,16-x12+x32\[LessEqual]T \
(1-y13),20+x13-x33\[LessEqual]T y13,10-x13+x33\[LessEqual]T \
(1-y13),13+x11-x41\[LessEqual]T y14,8-x11+x41\[LessEqual]T \
(1-y14),15+x12-x42\[LessEqual]T y14,10-x12+x42\[LessEqual]T \
(1-y14),20+x13-x43\[LessEqual]T y14,15-x13+x43\[LessEqual]T \
(1-y14),10+x21-x31\[LessEqual]T y23,20-x21+x31\[LessEqual]T \
(1-y23),20+x22-x32\[LessEqual]T y23,16\[LessEqual]T \
(1-y23),18+x23-x33\[LessEqual]T y23,10-x23+x33\[LessEqual]T \
(1-y23),10+x21-x41\[LessEqual]T y24,8-x21+x41\[LessEqual]T \
(1-y24),20+x22-x42\[LessEqual]T y24,10-x22+x42\[LessEqual]T \
(1-y24),18+x23-x43\[LessEqual]T y24,15-x23+x43\[LessEqual]T \
(1-y24),20+x31-x41\[LessEqual]T y34,8-x31+x41\[LessEqual]T \
(1-y34),16+x32-x42\[LessEqual]T y34,10-x32+x42\[LessEqual]T \
(1-y34),10+x33-x43\[LessEqual]T y34,15-x33+x43\[LessEqual]T (1-y34)}" \
// StringReplace[#, "T" :> "M"] & // ToExpression, M == 1000, 
   1 >= y12 >= 0, 1 >= y13 >= 0, 1 >= y14 >= 0, 1 >= y23 >= 0, 
   1 >= y24 >= 0, 
   1 >= y34 >= 0, (y12 | y13 | y14 | y23 | y24 | y34) \[Element] 
    Integers, # >= 0 & /@ {x11, x12, x13, x21, x22, x23, x31, x32, 
     x33, x41, x42, x43}} // Flatten, {T, x11, x12, x13, x21, x22, 
  x23, x31, x32, x33, x41, x42, x43, y12, y13, y14, y23, y24, y34}]
 

不过线性规划不建议采用类似x12的命名方式,后面调用变量时不易使用且不易查错。我以前的笔记是这么写的(也很难看):

Block[{data, bigM, subsets, varx, vary, T, vars, con0, con1, cons, 
  obj, ans},
 data =
  {{13, 15, 20},
   {10, 20, 18},
   {20, 16, 10},
   {8, 10, 15}};
 bigM = Max[Total@data];
 subsets = Subsets[Range@4, {2}];
 varx = Array[x, {4, 3}];
 vary = y @@@ subsets;
 vars = Flatten@{varx, vary, T};
 con0 = {# >= 0 & /@ vars, # <= 1 & /@ vary};
 con1 = {Table[
    x[#, i + 1] >= x[#, i] + data[[#, i]] & /@ Range@4, {i, 2}], 
   Table[x[#1, i] + data[[#1, i]] - x[#2, i] <= y[#1, #2] bigM & @@@ 
     subsets, {i, 3}],
   Table[x[#2, i] + data[[#2, i]] - 
        x[#1, i] <= (1 - y[#1, #2]) bigM & @@@ subsets, {i, 3}], 
   T >= x[#, 3] + data[[#, 3]] & /@ Range@4};
 cons = Flatten@{con0, con1};
 obj = T;
 ans = Minimize[obj, cons, vars, Integers];
 {First@ans, 
  Range@4 //. {a___, p_, b___, q_, c___} /; (y[p, q] /. Last@ans) == 
      1 :> {a, q, p, b, c}}
 ]

之所以没用穷举法,据说是复杂度比穷举低些,此处存疑,求问大神0-1规划用的是分支定界法还是其他方法,它的复杂度应该是多少?

用户: 瓦屋青衣 (321 分)
修改于 用户:瓦屋青衣
复杂度是不是比穷举低我不确定,反正我这试了下你这例子穷举只要0.0011s,Minimize要3.35s。。。。
以及0-1规划的话其实用LinearProgramming更好些,用法我更新到答案里了
...