haker.info | Etyczny hacking |

 Optymalizacja rozmieszczenia w elastycznej linii produkcyjnej

Napisane  07 maja 2019 godz. 14:52 przez  Dawid Farbaniec

Wyznaczyć liniowe, jednostkowe rozmieszczenie maszyn o następujących długościach:

  • M1 = 5
  • M2 = 2
  • M3 = 3
  • M4 = 6
  • M5 = 3
  • M6 = 4

Dane wejściowe:

  • [cij] — macierz jednostkowych kosztów przewozu (transportu)
  • [dij] — macierz minimalnych odstępów pomiędzy maszynami
  • [fij] — macierz przepływów pomiędzy maszynami
[cij] = 0 9 1 8 1 1
9 0 5 8 4 9
1 5 0 5 6 5
8 8 5 0 6 1
1 4 6 6 0 5
1 9 5 1 5 0

[dij] = 0 1 1 1 2 1
1 0 1 1 1 1
1 1 0 1 1 1
1 1 1 0 3 1
2 1 1 3 0 2
1 1 1 1 2 0

[fij] = 0 63 26 45 80 14
63 0 43 74 35 52
26 43 0 89 25 42
45 74 89 0 29 74
80 35 25 29 0 65
14 52 42 74 65 0

1. Wyznaczamy macierz zmodyfikowanych przepływów

Należy obliczyć:
F = [cij] × [fij]

I powinniśmy otrzymać:

F = 0 567 26 360 80 14
567 0 215 592 140 468
26 215 0 445 150 210
360 592 445 0 174 74
80 140 150 174 0 325
14 468 210 74 325 0
Wskazówka:
Mnożenie macierzy to mnożenie wierszy pierwszej macierzy przez kolumny drugiej macierzy.
(dane liczbowe z powyższego rysunku nie są związane z zadaniem)

2. Rysujemy rozmieszczenie bazowe maszyn

Narysowanie rozmieszczenia bazowego maszyn pozwoli potem wyznaczyć macierz odległości.

Długości maszyn były podane na początku, a odległości zostały wzięte z podanej również na początku macierzy [dij].

3. Wyznaczamy macierz odległości [lpq]

Dane do poniższej macierzy odległości można obliczyć z narysowanej wcześniej osi z rozmieszeniem bazowym maszyn.

[lpq] = ... M1 M2 M3 M4 M5 M6
M1 0 4,5 8 13,5 21 26,5
M2 4,5 0 3,5 9 16,5 22
M3 8 3,5 0 5,5 13 18,5
M4 13,5 9 5,5 0 7,5 13
M5 21 16,5 13 7,5 0 5,5
M6 26,5 22 18,5 13 5,5 0

4. Obliczamy funkcję celu

Obliczenie funkcji celu można wykonać mnożąc wartości z macierzy F przez wartości z macierzy [lpq].

Fc1 = F × [lpq]

Rezultat obliczeń:

Fc1 = (567 × 4,5) + (26 × 8) + (360 × 13,5) + (80 × 21) + (14 × 26,5) + (215 × 3,5) + (592 × 9) + (140 × 16,5) + (468 × 22) + (445 × 5,5) + (150 × 13) + (210 × 18,5) + (174 × 7,5) + (74 × 13) + (325 × 5,5) = 40694

5. Wyznaczamy macierz wektor przemieszczenia

Wyznaczamy macierz wektor przemieszczenia:

  1. Szukamy maksymalnej wartości w macierzy F
  2. Jest to 592 w wierszu 2 i kolumnie 4 (wykreślamy wartość 592).
  3. Ustawienie maszyn: ... 2 — 4 ...
  4. Szukamy maksymalnej wartości biorąc pod uwagę stanowisko 2 oraz 4.
  5. Jest to wartość 567 w kolumnie 2 i wierszu 1 (wykreślamy wiersz i kolumnę 2).
  6. Ustawienie maszyn: ... 1 — 2 — 4 ...
  7. Szukamy maksymalnej wartości biorąc pod uwagę stanowisko 1 oraz 4.
  8. Jest to wartość 445 w kolumnie 3 i wierszu 4 (wykreślamy wiersz i kolumnę 4).
  9. Ustawienie maszyn: ... 1 — 2 — 4 — 3 ...
  10. Szukamy maksymalnej wartości biorąc pod uwagę stanowisko 1 oraz 3.
  11. Jest to wartość 210 w kolumnie 3 i wierszu 6 (wykreślamy wiersz i kolumnę 3).
  12. Ustawienie maszyn: ... 1 — 2 — 4 — 3 — 6 ...
  13. Szukamy maksymalnej wartości biorąc pod uwagę stanowisko 1 oraz 6.
  14. Jest to wartość 325 w kolumnie 1 i wierszu 5 (wykreślamy wiersz i kolumnę 6).
  15. Ustawienie maszyn: 1 — 2 — 4 — 3 — 6 — 5

6. Wyznaczamy macierz odległości [lpq2]

Nowe rozmieszczenie maszyn:

[lpq2] = ... M1 M2 M3 M4 M5 M6
M1 0 4,5 15 9,5 25 19,5
M2 4,5 0 10,5 5 20,5 15
M3 15 10,5 0 5,5 10 4,5
M4 9,5 5 5,5 0 15,5 10
M5 25 20,5 10 15,5 0 5,5
M6 19,5 15 4,5 10 5,5 0

7. Obliczamy nową funkcję celu

Obliczenie funkcji celu można wykonać mnożąc wartości z macierzy F przez wartości z macierzy [lpq2].

Fc2 = F × [lpq2]

Rezultat obliczeń:

Fc2 = (567 × 4,5) + (26 × 15) + (360 × 9,5) + (80 × 25) + (14 × 19,5) + (215 × 10,5) + (592 × 5) + (140 × 20,5) + (468 × 15) + (445 × 5,5) + (150 × 10) + (210 × 4,5) + (174 × 15,5) + (74 × 10) + (325 × 5,5) = 33859

8. Porównanie funkcji celu Fc1 > Fc2

Nowe rozmieszczenie maszyn jest bardziej optymalne gdyż:

33859 < 40694 == Fc2 < Fc1

9. Implementacja w C#.NET — kod źródłowy

/* http://haker.info/     Użycie:     Prod1Calc calc = new Prod1Calc(m, cij, dij, fij);     calc.Calculate(); */ public class Prod1Calc { private float[] m { get; set; } private float[,] cij { get; set; } private float[,] dij { get; set; } private float[,] fij { get; set; } private float[,] F { get; set; } private float[,] lpq { get; set; } private float Fc1 { get; set; } private float Fmax1 { get; set; } private float Fmax2 { get; set; } private int FmaxRow { get; set; } private int FmaxCol { get; set; } public Prod1Calc(float[] _m, float[,] _cij, float[,] _dij, float[,] _fij) { m = _m; cij = _cij; dij = _dij; fij = _fij; } public void Calculate() { F = new float[6, 6]; for (int i = 0; i < cij.GetLength(0); i++) { for (int j = 0; j < fij.GetLength(0); j++) { F[i, j] = cij[i, j] * fij[i, j]; } } lpq = new float[6, 6]; lpq[0, 0] = 0; lpq[0, 1] = lpq[0, 0] + (m[0] / 2f) + (m[1] / 2f) + dij[0, 1]; lpq[0, 2] = lpq[0, 1] + (m[1] / 2f) + (m[2] / 2f) + dij[1, 2]; lpq[0, 3] = lpq[0, 2] + (m[2] / 2f) + (m[3] / 2f) + dij[2, 3]; lpq[0, 4] = lpq[0, 3] + (m[3] / 2f) + (m[4] / 2f) + dij[3, 4]; lpq[0, 5] = lpq[0, 4] + (m[4] / 2f) + (m[5] / 2f) + dij[4, 5]; lpq[1, 0] = lpq[0, 1]; lpq[1, 1] = 0; lpq[1, 2] = (m[1] / 2f) + (m[2] / 2f) + dij[1, 2]; lpq[1, 3] = (m[1] / 2f) + m[2] + (m[3] / 2f) + dij[1, 2] + dij[2, 3]; lpq[1, 4] = (m[1] / 2f) + m[2] + m[3] + (m[4] / 2f) + dij[1, 2] + dij[2, 3] + dij[3, 4]; lpq[1, 5] = (m[1] / 2f) + m[2] + m[3] + m[4] + (m[5] / 2f) + dij[1, 2] + dij[2, 3] + dij[3, 4] + dij[4, 5]; lpq[2, 0] = lpq[0, 2]; lpq[2, 1] = lpq[1, 2]; lpq[2, 2] = 0; lpq[2, 3] = (m[2] / 2f) + (m[3] / 2f) + dij[2, 3]; lpq[2, 4] = (m[2] / 2f) + m[3] + (m[4] / 2f) + dij[2, 3] + dij[3, 4]; lpq[2, 5] = (m[2] / 2f) + m[3] + m[4] + (m[5] / 2f) + dij[2, 3] + dij[3, 4] + dij[4, 5]; lpq[3, 0] = lpq[0, 3]; lpq[3, 1] = lpq[1, 3]; lpq[3, 2] = lpq[2, 3]; lpq[3, 3] = 0; lpq[3, 4] = (m[3] / 2f) + (m[4] / 2f) + dij[3, 4]; lpq[3, 5] = (m[3] / 2f) + m[4] + (m[5] / 2f) + dij[3, 4] + dij[4, 5]; lpq[4, 0] = lpq[0, 4]; lpq[4, 1] = lpq[1, 4]; lpq[4, 2] = lpq[2, 4]; lpq[4, 3] = lpq[3, 4]; lpq[4, 4] = 0; lpq[4, 5] = (m[4] / 2f) + (m[5] / 2f) + dij[4, 5]; lpq[5, 0] = lpq[0, 5]; lpq[5, 1] = lpq[1, 5]; lpq[5, 2] = lpq[2, 5]; lpq[5, 3] = lpq[3, 5]; lpq[5, 4] = lpq[4, 5]; lpq[5, 5] = 0; for (int i = 0; i < F.GetLength(0); i++) { for (int j = 0; j < lpq.GetLength(0); j++) { if (i > j) Fc1 += F[i, j] * lpq[i, j]; } } for (int i = 0; i < F.GetLength(0); i++) { for (int j = 0; j < F.GetLength(0); j++) { if (F[i, j] > Fmax1) { Fmax1 = F[i, j]; FmaxRow = i; //+1 FmaxCol = j; //+1 } } } List<float> machines = new List<float>(); F[FmaxRow, FmaxCol] = -1; machines.Add(FmaxRow); machines.Add(FmaxCol); int oldCol = 0, oldRow = 0; oldCol = FmaxCol; oldRow = FmaxRow; int step = 4; while(step > 0) { step--; Fmax1 = 0; Fmax2 = 0; for (int j = 0; j < F.GetLength(0); j++) { if (F[oldRow, j] > Fmax1) { Fmax1 = F[oldRow, j]; FmaxCol = j; //+1 } } for (int i = 0; i < F.GetLength(0); i++) { if (F[i, oldCol] > Fmax2) { Fmax2 = F[i, oldCol]; FmaxRow = i; //+1 } } if (Fmax1 > Fmax2) { for (int k = 0; k < F.GetLength(0); k++) F[oldRow, k] = -1; for (int k = 0; k < F.GetLength(0); k++) F[k, oldRow] = -1; machines.Insert(0, FmaxCol); oldRow = FmaxCol; } else { for (int k = 0; k < F.GetLength(0); k++) F[k, oldCol] = -1; for (int k = 0; k < F.GetLength(0); k++) F[oldCol, k] = -1; machines.Add(FmaxRow); oldCol = FmaxRow; } } } }

Tagi:  c-sharp  inne 
Wszystkie treści umieszczone na tej witrynie są chronione prawem autorskim. Surowo zabronione jest kopiowanie i rozpowszechnianie zawartości tej witryny bez zgody autora. Wszelkie opublikowane tutaj treści (w tym kody źródłowe i inne) służą wyłącznie celom informacyjnym oraz edukacyjnym. Właściciele tej witryny nie ponoszą odpowiedzialności za ewentualne niezgodne z prawem wykorzystanie zasobów dostępnych w witrynie. Użytkownik tej witryny oświadcza, że z zamieszczonych tutaj danych korzysta na własną odpowiedzialność. Wszelkie znaki towarowe i nazwy zastrzeżone zostały użyte jedynie w celach informacyjnych i należą wyłącznie do ich prawnych właścicieli. Korzystając z zasobów witryny haker.info oświadczasz, że akceptujesz powyższe warunki.