[ 初めての方へ | 一覧(最新更新順) | 全文検索 | 過去ログ ]
『制約条件下での最適な組み合わせの算出方法』（ららら）
以下のようなモデルについて、最適な組み合わせを見つける方法が
分からず困っております。ご教示いただきたく存じます。
※要約しますと、制約条件を満たしつつ、総工数バラツキの値が最少と
なる稼働日G1,G2,G3の振り分けをEXCELで算出する方法が知りたいと
思っております。ソルバーという機能を使ってみましたが、私の知識が
足りずうまく動作できませんでした。
■データ (実際は?@?A?Bの振り分けは分からない状態とする)
モデル 工数 稼働日
A 10 G2
B 20 G2
B 20 G3
B 20 G1
C 30 G1
C 30 G2
C 30 G3
C 30 G4
C 30 G5
■制約条件 (実際は総工数は関数で算出されているものとする)
稼働日 総工数
G1 80 <= 100
G2 90 <= 100
G3 50 <= 100
■目的条件 (同上)
総工数バラツキ 16.99673171
恐れ入りますが、よろしくお願いいたします。
＜ 使用 Excel：Excel2019、使用 OS：Windows10 ＞
１．こんな表を作る
(1) F2セル =SUMIF(C$2:C$10,E2,B$2:B$10) 下にコピー
(2) F5セル =STDEV.P(F2:F4)
行 ___A___ __B__ _C_ _D_ _E_ ___F___ 1 モデル 工数 G G 総工数 2 A 10 1 0 3 B 20 2 0 4 B 20 3 0 5 B 20 0 6 C 30 7 C 30 8 C 30 9 C 30 10 C 30
２．ソルバーで以下に諸元をセットして、解決ボタンクリック
目的セル $F$5 目標値 最小値 変数セル $C$2:$C$10 成約条件 $C$2:$C$10 int (整数) $C$2:$C$10 <=3 $C$2:$C$10 >=1 $F$2:$F$4 <=100
<結果図> 行 ___A___ __B__ _C_ _D_ _E_ _____F_____ 1 モデル 工数 G G 総工数 2 A 10 2 1 80 3 B 20 3 2 60 4 B 20 1 3 80 5 B 20 2 9.428090416 6 C 30 3 7 C 30 1 8 C 30 2 9 C 30 1 10 C 30 3
（半平太） 2021/08/19(木) 23:19
ご教示いただきありがとうございます。
実際にやってみました。完璧に自分が実現したいことができました。
すごくスマートなやり方で勉強になります。ありがとうございます。
恐れ入りますが、もしよろしければもう一つお教え願えないでしょうか。
今回のモデルは単純化したもので、実際はモデル/工数/Gは500行、
Gの数値は20を考えてます。当然組み合わせ数が膨大になるので
ソルバー解決に途方もない時間がかかると予測しております。
こういった問題の対策にはどのような解決手段があるのでしょうか。
※恥ずかしながら知識を得ようにも検索ワードすら思い浮かばず悩んでおります。
以上、よろしくお願いいたします。
（ららら） 2021/08/20(金) 10:33
＞当然組み合わせ数が膨大になるので ＞ソルバー解決に途方もない時間がかかると予測しております。
全く異論はありませんが、私は詳しくないので助言できません。 ここにも詳しい人が居るので、その人の目に止まるといいですね。
個人的見解ですけども、ご参考まで。 この種の問題の解法はある程度決まっているんでしょうが、 私は、一つひとつのケースが別個の解法を必要としている問題だと思っています。 実際にどんなデータなのか示されないと、どんな方法がいいのかアイデアが出にくいし、 テストしてみようにもデータ作りから初めなければならなので、敬遠されがちになる。
まぁ、500行並べられても参るので、実データに近いサンプルが簡単に作り出せる情報の提示が好ましい。 これだけでは不十分。 ↓ ＞実際はモデル/工数/Gは500行、Gの数値は20を考えてます。
モデルの種類、工数のバリエーションが全く分からない。 制約条件も実物に近いものが示されないとテスト自体が虚しいものになる。
（半平太） 2021/08/20(金) 11:28
ご教示いただきありがとうございます。
実際にどんなデータなのか示されないと、どんな方法がいいのかアイデアが出にくいし、 テストしてみようにもデータ作りから初めなければならなので、敬遠されがちになる。
問題の規模や種類を正確に把握していなかったこと、大変恥ずかしく思っております。
せっかくアドバイスをいただいているなか、ぼかしたモデルケースのまま質問しては
意味が薄れてしまうと認識しました。
＞実データに近いサンプルが簡単に作り出せる情報の提示が好ましい。
よい提示が思いつきませんので、ほぼ実データに近いものを以下のアドレスに
アップロードしました。
https://35.gigafile.nu/0827-b31f394766fa9d924851fd2a9dbf11882
おっしゃる通り、半平太様をはじめ、この質問に目にとめていただいた方々に
失礼のないようにしたい思いのみです。もちろん解法自体は自身でも考えております。
もしよろしければお教えいただければ幸いです。
以上、よろしくお願いいたします。
（ららら） 2021/08/20(金) 12:25
こんにちは。
Excelのソルバーは、変数の個数は上限200、制約条件の上限100という制約があるので、 半平太さんが提示された方式をそのまま使うことはできないようです。(変数が431個あるので)
そこで、工数ごとにまとめて、どのグループにいくつ割り振るか（下記L2:T21)を 変数にすることで、9*20 = 180個の変数で済ますことができます。 以下が、シートレイアウトと、ソルバー実行結果です。
K L M N O P Q R S T U V W
0.5 0.6 0.8 1 1.2 1.3 1.4 1.5 1.6 合計 制約 標準偏差
2 1 0 1 7 10 2 0 0 0 0 18.6 21.5 1.30172
3 2 0 2 0 15 0 2 0 0 0 18.8 21.5
4 3 0 0 0 17 1 0 0 0 0 18.2 21.5
5 4 0 4 6 9 1 1 0 0 0 18.7 21.5
6 5 0 5 4 10 0 2 0 0 0 18.8 21.5
7 6 0 0 0 17 0 0 0 0 1 18.6 21.5
8 7 0 6 0 13 0 0 0 2 0 19.6 21.5
9 8 0 0 0 17 2 0 0 0 1 21.0 21.5
10 9 0 2 19 0 0 0 0 0 3 21.2 21.5
11 10 0 3 11 5 0 1 0 2 1 21.5 21.5
12 11 0 0 0 19 2 0 0 0 0 21.4 21.5
13 12 0 0 0 16 0 2 1 1 0 21.5 21.5
14 13 0 0 20 1 0 0 0 3 0 21.5 21.5
15 14 0 3 0 17 1 0 0 1 0 21.5 21.5
16 15 0 11 8 3 0 2 1 1 0 21.5 21.5
17 16 0 2 8 10 2 0 0 1 0 21.5 21.5
18 17 0 1 11 4 0 4 1 1 0 21.5 21.5
19 18 0 0 1 18 0 1 1 0 0 21.5 21.5
20 19 2 5 2 5 0 5 1 2 0 21.5 21.5
21 20 2 0 16 5 1 0 0 1 0 21.5 21.5
22 4 45 113 211 12 20 5 15 6 409.9
23 4 45 113 211 12 20 5 15 6 409.9
(計算式のセット）
U2 =SUMPRODUCT($L$1:$T$1,L2:T2)
以下、U21までコピー
L22 =SUM(L2:L21)
以下、U22まで右にコピー
L23 =COUNTIF($B$2:$B$432,L$1)
以下、T23まで右にコピー
U23 409.9
W2 =STDEV.P($U$2:$U$21)
(ソルバーのセット）
目的セル $W$2
目標値 最小値
変数セル $L$2:$T$21
制約条件 $L$2:$T$21 int (整数)
$L$2:$T$21 >= 0変数は非負数
L22 <= L23 (23行には予め個数合計をセット）
...
T22 <= T23
U2:U22 <= 21.5
U22 = U23
ソルバーのアルゴリズムは、3つの中の"GRG非線形"を使用しました。
なお、この結果をもとに、もとのC列に埋める部分は考えていません（ソルバーに限定して回答）
（また、Excelを離れたソルバーを使用すれば、制約は緩和され、元の問題どおりの対応が可能だと 思いますが、質問者さんには参考にはならないだろうと考え、コメントを控えます。） （γ） 2021/08/20(金) 16:47
「実データに近い」と言うのが本当なら、ソルバーを使わなくても出来そうな気がします。
単位工数の多いモデルから(W,X,AE,AF・・）、工数の途中累計が少ないグループ(1〜20)に 優先割振りをしていけば自然と出来上がりそう。
最適な組み合わせと言っても、そんな厳密な話じゃないですよね？
試した限りでは、自然体で制約条件(21.5）に引っかかることもなく、標準偏差は、0.201183995 でした。
（半平太） 2021/08/20(金) 20:11
コードを整理しましたので、アップします。 制約条件は「数値で21.5」と入れてください。
<本番 シート 実行前> 行 ___A___ __B__ _C_ ____D____ _E_ ___F___ ____G____ _H_ _____I_____ 1 モデル 工数 G G 総工数 制約条件 目的 2 A 1 1 0 21.5 0 3 B 1.2 2 0 21.5 4 C 1.3 3 0 21.5 5 C 1.3 4 0 21.5 6 C 1.3 5 0 21.5 : : : : : :
<本番 シート 実行後> 行 ___A___ __B__ _C_ ____D____ _E_ ___F___ ____G____ _H_ _____I_____ _J_ ___K___ __L__ __M__ 1 モデル 工数 G モデル-1 G 総工数 制約条件 目的 モデル 工数 個数 2 A 1 12 A-1 1 20.3 21.5 0.201183995 W 1.6 3 3 B 1.2 19 B-1 2 20.3 21.5 X 1.6 3 4 C 1.3 13 C-1 3 20.3 21.5 AE 1.5 1 5 C 1.3 14 C-2 4 20.3 21.5 AF 1.5 14 6 C 1.3 15 C-3 5 20.3 21.5 P 1.4 4
当該シートのシートモジュールに貼り付ける（つまり標準モジュールではないー重要）
修正版が出来たので、ここにあったコードは削除します。
（半平太） 2021/08/20(金) 22:34
無駄なロジックがあったので修正しました。
Gの増減に動的に対応できるようにしました。
ソルバーじゃないので、 検証用数式は割振り完了後に動的に入力することにしました。 (数式は手入力して置く必要はないです。)
Sub AssignMent()
Dim lastArow As Long
Dim lastKrow As Long
Dim lastErow As Long
Dim i As Long, k As Long, g As Long
Dim vLeft3
Dim limits
Dim vTTL()
Dim manHour, vMin, gMin, PosRw
'結果表示用数式をクリアする
Range("F2:F10000,I2").ClearContents
'モデル別出現数を算出
lastArow = Cells(10000, "A").End(xlUp).Row 'A列の最終行を取得
With Range("D1").Resize(lastArow)
.FormulaR1C1 = "=RC[-3]&""-""&COUNTIF(R1C[-3]:RC[-3],RC[-3])"
.Value = .Value
End With
lastErow = Cells(10000, "E").End(xlUp).Row 'グループ種類列の最終行を取得
Columns("K").Resize(, 3).ClearContents
'重複の無いモデル名を抽出
Columns("A:A").Copy Range("K1")
Range("$K$1:$K$432").RemoveDuplicates Columns:=1, Header:=xlYes
lastKrow = Cells(10000, "K").End(xlUp).Row
'モデル別の工数と個数を算出
Range("L2").Resize(lastKrow - 1).FormulaR1C1 = "=VLOOKUP(RC[-1],C[-11]:C[-10],2,FALSE)"
Range("M2").Resize(lastKrow - 1).FormulaR1C1 = "=COUNTIF(C[-12],RC[-2])"
Range("L2:M2").Resize(lastKrow - 1) = Range("L2:M2").Resize(lastKrow - 1).Value
Range("K1:M1") = Array("モデル", "工数", "個数") 'タイトル
Me.Sort.SortFields.Clear
Me.Sort.SortFields.Add Key:=Range("L2:L" & lastKrow), SortOn:=xlSortOnValues, Order:=xlDescending
With Me.Sort
.SetRange Range("K1:M" & lastKrow)
.Header = xlYes
.Apply
End With
limits = Range("G2").Resize(lastErow)
vLeft3 = Range("K1").Resize(lastKrow, 3)
ReDim vRight(1 To lastErow - 1)
ReDim vTTL(1 To lastErow - 1)
For i = 2 To lastKrow
manHour = vLeft3(i, 2)
For k = 1 To vLeft3(i, 3) '個数分だけ処理する
'途中累計が最少の「g」を見つける
vMin = 8 ^ 16
For g = 1 To lastErow - 1
If vTTL(g) < vMin Then
'制約条件に合致するかチェック
If vTTL(g) + manHour <= limits(g, 1) Then
vMin = vTTL(g)
gMin = g
End If
End If
Next g
If vMin = 8 ^ 16 Then
MsgBox "解が得られませんでした。"
Exit Sub
End If
'割り当てるべき行番号を取得
PosRw = Application.Match(vLeft3(i, 1) & "-" & k, Columns("D"), 0)
Cells(PosRw, "C") = gMin
'途中累計を更新する
vTTL(gMin) = vTTL(gMin) + manHour
Next k
Next i
'集計結果の評価をする数式を入力
Range("F2:F" & lastErow).FormulaLocal = "=SUMIF(C$1:C$" & lastArow & ",E2,B$1:B$" & lastArow & ")"
Range("I2").FormulaLocal = "=STDEV.P(F2:F" & lastErow & ")"
End Sub
（半平太） 2021/08/21(土) 10:29
（γ） 2021/08/21(土) 10:57
さっそくソルバーを実施してみました。標準偏差0.42834の時点で算出を中止しましたが
それでも満足のいく結果です。とにかく結果が現れて嬉しく思っております。
ありがとうございました。
(無駄話)今回の機をきっかけに「最適化問題」について興味がわきました。
私はPython言語なら少し触ったことがございますので、もっと学習して
いつか自分で解法が出せる様スキルアップしたいと思っております。
（ららら） 2021/08/21(土) 12:52
さっそく実行(修正前/後ともに)してみました。自分では思いつかないような
コード描写も多く、それだけでも勉強になります。動作自体も非常に高速で驚いております。
また、実行結果にも満足しております。本当にありがとうございました。
ご指摘の通り、確かにこのモデルは"最適な組み合わせ"といった大層な問題ではなく
ご提示いただいたアルゴリズムで解けるもののようですね。実は類似の問題を抱えた
モデルが他にも20個ほどあり、今回は最もデータ数の多いモデルをアップロードしました。
制約条件はモデル毎にまったく異なるため、どうすればよいか頭を悩ませていたところ
ソルバーという機能に注目した経緯がございます。
ですが、今回作成いただいたマクロコードをベースに他モデルにも展開できそうです。
勝手ながらいろいろ触ってみて、現場への改善につなげたいと思っております。
（ららら） 2021/08/21(土) 13:16
[ 一覧(最新更新順) ]
YukiWiki 1.6.7 Copyright (C) 2000,2001 by Hiroshi Yuki.
Modified by kazu.