Günstigste Kombination finden - Mathematisch/Exceltechnisches Thema

[Henkelzupfer]

Hallo Gemeinde,

hier eine Lösungsaufgabe, zu der ich bisher (auch nach langen probieren) keinen Weg gefunden habe.

Aufgabenstellung: 8 Anbieter haben ein Preis abgegeben für insgesamt 8 Pakete. Die Vergabe ist so, dass jeder Anbieter nur ein Paket liefern soll. Es soll nun die günstigste Kombination gefunden werden. (Anhang)

Hört sich eigentlich einfach an.Rein mathematisch gibt es also 8! (8 Fakultät=40320) Kombinationen.

Habt Ihr eine Idee, wie man hier Exceltechnisch für die Summe das Minimum findet?

Bin auf Eure Lösungsansätze gespannt!Schöne Grüße,
Sebastian

[BoskoBiati]

Antwort gelöscht

[bst]

Hallo,

hier mal eine Variante mit Bruteforce. Geht so - wegen des 'Ziffernstrings' - nur bis N = 9.

Reicht Dir das?

cu, Bernd
--

Code:

Option Explicit

Sub BruteForce()
   Dim t As Single
  
   t = Timer
  
   Const N As Integer = 8
   Dim arData As Variant
   Dim strSource As String, strPerm As String, strResult As String
   Dim i As Long, j As Integer
   Dim dblSumAct As Double, dblSumMin As Double
  
   strSource = "12345678"
   arData = Range("C3").Resize(N, N)
   dblSumMin = 1.79E+308
   For i = 0 To Application.Fact(N) - 1
      strPerm = permutation(i, strSource)
      dblSumAct = 0
      For j = 1 To N
         dblSumAct = dblSumAct + arData(j, CInt(Mid(strPerm, j, 1)))
      Next
      If dblSumAct < dblSumMin Then
         dblSumMin = dblSumAct
         strResult = strPerm
      End If
   Next
   t = Timer - t
  
   Debug.Print "Indizes der minimalen Summe: "; strResult
   Debug.Print "Minimale Summe:"; dblSumMin
   Debug.Print "Benötigte Zeit in Sekunden:"; t
End Sub

' http://en.wikipedia.org/wiki/Permutation

' Unordered generation
Function permutation(ByVal k As Long, ByVal s As String) As String
   Dim j As Long, i As Long, x As String
  
   For j = 2 To Len(s)
      i = (k Mod j) + 1
      x = Mid(s, j, 1)
      Mid(s, j, 1) = Mid(s, i, 1)
      Mid(s, i, 1) = x
      k = Int(k / j)
   Next
   permutation = s
End Function

[Henkelzupfer]

Hallo Bernd,

klasse, vielen Dank!!!
Hatte für die Kombination noch ein wenig gebraucht bis ich rausgefunden hatte, welche Zellen addiert werden. Jetzt habs auch ich verstanden.

Also, vielen Dank nocheinmal!

Schöne Grüße,
Sebastian