作者查詢 / illousion

總覽項目：發文 | 留言 | 暱稱

作者 illousion 在 PTT [ Math ] 看板的留言(推文), 共46則

限定看板：Math

首頁

尾頁

[其他] TC題 (18) 線性規劃/整數

[ Math ]90 留言, 推噓總分: +18

作者: TimcApple - 發表於 2020/05/25 20:53(5年前)

46^F推illousion: 在求「整數線型規劃」時，線型規劃的目標函數（放05/27 09:10

47^F→illousion: 鬆整數限制）只能是一個bound，以本題來說，是上界05/27 09:10

48^F→illousion: 。整數線型規劃的解不能從放鬆後的線性規劃來推論05/27 09:10

49^F→illousion: ，也跟目標函數斜率無關。上面推文沒有錯，(mixed)05/27 09:10

50^F→illousion: integer (linear) programming 的最佳化都是NP-ha05/27 09:10

51^F→illousion: rd問題。再來求整數規劃的演算法是Branch-and-boun05/27 09:10

52^F→illousion: d，是一種divide and conquer approach，求解放鬆05/27 09:10

53^F→illousion: 線型規劃後再去針對有整數限制的變數分枝，然後upd05/27 09:10

54^F→illousion: ate bound或是fathom。上面推文有人說convex hull05/27 09:10

55^F→illousion: 這是一個非常正確的觀念，當我們知道整數線型規劃05/27 09:10

56^F→illousion: 的convex hull之後，最佳化可以reduce to線型規劃05/27 09:10

57^F→illousion: 進而變成一個簡單的問題，因為此時所有extreme poi05/27 09:10

58^F→illousion: nts都是整數，只要使用線型規劃的算法(interior po05/27 09:10

59^F→illousion: int method, which is polynomial，而simplex則不05/27 09:10

60^F→illousion: 是)找解就可以。但是convex hull只有在二維的時候05/27 09:10

61^F→illousion: 有可能看出來，高維度一般都是未知。做整數線型規05/27 09:10

62^F→illousion: 劃研究的人，一般都是做cutting plane method或是s05/27 09:10

63^F→illousion: trong formulation，讓可行區間越小越靠近包含所有05/27 09:10

64^F→illousion: 的整數點集合，也就是convex hull。05/27 09:10

67^F推illousion: 這是作業研究中的整數規劃內容，任何一本作業研究05/27 10:07

68^F→illousion: 的書都會講到整數規劃跟branch-and-bound，就是因05/27 10:07

69^F→illousion: 為整數規劃跟線型規劃性質完全不同所以要獨立出來05/27 10:07

70^F→illousion: 講，而我說到的cutting plane那些是屬於碩博等級的05/27 10:07

71^F→illousion: 知識，而且是要專門做整數規劃的人才會去研究，小05/27 10:07

72^F→illousion: 弟我剛好博士研究就是整數規劃。另外數學系跟CS也05/27 10:07

73^F→illousion: 可能會有人研究這些。整數規劃因為NP-hard，如何設05/27 10:07

74^F→illousion: 計有效率的精確或近似算法很重要，或是怎麼把一個05/27 10:07

75^F→illousion: 很大的問題分解做decomposition method，因此也必05/27 10:07

76^F→illousion: 須具備動態規劃dynamic programming 還有CS中的算05/27 10:07

77^F→illousion: 法知識，至少要了解時間複雜度，我老闆都叫我們組05/27 10:07

78^F→illousion: 去上幾門CS或數學系的課。05/27 10:07

Re: [其他] 三題線性規劃（作業研究/管理科學）贈P幣-第三題

[ Math ]14 留言, 推噓總分: +3

作者: illousion - 發表於 2020/05/07 07:54(5年前)

8^F→illousion: 原問題如果對於不同天招聘的人有不同的成本05/07 09:31

9^F→illousion: 那可能就會有唯一的最佳解這樣的cover問題05/07 09:32

10^F→illousion: 在polyhedral的概念來說對稱性很嚴重 symmetric05/07 09:32

11^F→illousion: 所以有多重最佳解是很常見的問題難度也是NP-hard05/07 09:32

Re: [其他] 三題線性規劃（作業研究/管理科學）贈P幣

[ Math ]7 留言, 推噓總分: +2

作者: calculusking - 發表於 2020/05/04 23:31(5年前)

7^F→illousion: 答案是錯的，這組解不滿足週四週五的人力需求05/06 12:11

Re: [線代] 作業研究 simplex method 一題請問

[ Math ]7 留言, 推噓總分: +1

作者: chemmachine - 發表於 2020/04/26 14:41(5年前)

1^F推illousion: 如果我沒有理解錯的你逐一消去變數的算法叫做04/26 14:57

2^F→illousion: Fourier-Motzkin Elimination 確實可以解線性規劃04/26 14:58

3^F→illousion: 可是他的計算時間對於高維的問題非常的慢不實用04/26 14:58

6^F→illousion: 如果有m個不等式n個變數時間複雜度為O(m^(2^n))04/26 15:00

7^F→illousion: 現代線性規劃的求解器solver的code都是基於單形法04/26 15:00

[線代] 作業研究 simplex method 一題請問

[ Math ]35 留言, 推噓總分: +3

作者: fish890315 - 發表於 2020/04/26 00:33(5年前)

28^F→illousion: 等等回一篇好了....04/26 01:18

33^F推illousion: 我已經回文了可以看看我講的你懂不懂04/26 01:46

34^F→illousion: 我大學也念商但目前唸作研博士你一定也可以懂04/26 01:47

35^F→illousion: chem大說的KKT方法會在「非線性規劃」的章節學到04/26 01:48

[其他] optimization (linear function)

[ Math ]8 留言, 推噓總分: +5

作者: star66 - 發表於 2013/04/26 08:21(12年前)

8^F推illousion:用Lagrange multiplier算04/29 20:36

首頁

尾頁