Wyjaśnienie simpleksowej metody optymalizacji liniowej

instagram viewer

Optymalizacja liniowa polega na optymalnej alokacji ograniczonych zasobów do różnych zastosowań. Niewielkimi zasobami mogą być na przykład moce maszyn lub wymagania przestrzenne dla towarów. Optimum określa się matematycznie, często za pomocą metody simplex.

Modelowanie programów liniowych

Podczas modelowania programów liniowych różne parametry, takie jak B. Można określić czasy obróbki detali lub wydajność maszyny. Następnie definiuje się funkcję celu, która ma być maksymalizowana pod pewnymi ograniczeniami. Funkcja celu jest często funkcją zysku, ponieważ maksymalizacja zysku netto jest kluczowym celem dla firm. Ograniczenia są opisane przez niedostatek zasobów (np. B. Pojemność, czas, przestrzeń). Następnie możesz rozwiązać problem za pomocą metody simplex.

  • Możesz nauczyć się procedury tworzenia modeli liniowych szczególnie łatwo, jeśli zrobisz sobie prosty przykład: Załóżmy, że masz trzy maszyny M1, M2 oraz m3 na którym dwa produkty P1 i p2 powinny być produkowane. Maszyny mają różne wydajności, a przetworzenie określonego produktu wymaga czasu na maszynach przez różne okresy czasu, a gotowe produkty końcowe mają różne zyski z dala.
  • Szukamy teraz programu produkcyjnego z maksymalnym zyskiem, czyli takiego programu produkcyjnego, w którym osiąga się największy zysk.

Przykład z wartościami liczbowymi i wprowadzeniem do metody simplex

W kolejnym kroku potrzebujesz konkretnych wartości liczbowych do modelowania swojego problemu. Załóżmy, że do edycji P1 na M1 2 godziny przypadają na M2 3 godziny i na M3 4 godziny. Dla p2 spaść na M1 4 godziny na M2 5 godzin i na M3 3 godziny. Możliwości maszyny dla M1 500 godzin, dla M2 300 godzin, a dla M3 600 godzin. Zyski z gotowych produktów końcowych P1 to 3 euro / sztuka, za gotowe produkty końcowe P2 4 euro/szt.

  1. Najlepiej utworzyć tabelę z trzema wierszami i trzema kolumnami, z dodatkowym miejscem na nagłówki wierszy i kolumn. Powinien opuścić kolumny. Na przykład czas przetwarzania P znajduje się w polu „Kolumna 1 i Wiersz 1”1 na M1, w polu „Kolumna 2 i Linia 3” czas przetwarzania P2 na M3. Kolumna 3 pokazuje możliwości trzech maszyn.
    2. Algorytm Gaussa liniowych układów równań wyjaśniony w skrócie

    W gimnazjum po raz pierwszy spotkasz się z liniowymi układami równań ...

  2. Teraz potrzebujesz dwóch zmiennych x1, x2 określić wielkości produkcji P1 i p2 korespondować.
  3. Więc dostajesz ograniczenia 2x1+ 4x2 ≤ 500 (maszyna 1), 3x1+ 5x2 ≤ 300 (maszyna 2) i 4x1+ 3x2 ≤ 600 (maszyna 3). W każdym przypadku istnieją nierówności, ponieważ zdolności nie muszą być w pełni wyczerpane.
  4. Funkcja celu (zysk) do maksymalizacji to G (x1, x2) = 3x1+ 4x2 -> max.
  5. Ponadto warunki nieujemności x mają zastosowanie do wielkości produkcji1, x2 ≥ 0. Widzisz, wszystkie równania są równaniami liniowymi. Jeśli spojrzysz na nie razem, otrzymasz liniowy problem optymalizacji.

Optymalizacja liniowa i zastosowanie metody simplex

Pomysł na rozwiązanie programu liniowego polega na tym, że nierówności poprzez wprowadzenie „zmiennych luźnych” w Równania a zmodyfikowany problem optymalizacji jest rozwiązany jako LGS. Metoda simpleks jest zatem bardzo podobna do algorytmu Gaussa do rozwiązywania LGS.

  1. Przykład: Samolot jest podzielony przez trzy towary G1, G2, G3 być załadowany najwyższą możliwą całkowitą wartością frachtu. Wymagają one miejsca 1, 0,2 lub 6 dm3, mają wagę 1, 0, 4 i 8 kg i wartości 10, 3 lub 50 euro. W jaki sposób samolot jest idealnie załadowany, gdy przestrzeń ładunkowa wynosi 2000dm?3 i może przewieźć maksymalnie 3000 kg ładunku?
  2. Ty definiujesz x1, x2, x3 jako ilości towaru G1, G2, G3.
  3. Możesz teraz ustawić ograniczenia za pomocą zmiennych luzu w następujący sposób: x1+ 0,4x2+ 8x3+ x4 = 3000 i x1+ 0,2x2+ 6x3+ x5 = 2000. Funkcja celu (całkowita wartość frachtu) to G (x1, x2, x3) = 10x1+ 3x2+ 50x3 -> max. Możesz to zmienić, umieszczając wszystkie zmienne na jednej stronie (G-10x1-3x2-50x3 = 0).
  4. Następnie skonfiguruj panel Simplex. Ma 3 rzędy i 7 kolumn. Po lewej stronie wpisujesz x w kolumnach1, x2, x3, x4, x5 i G jako nagłówki. Po prawej stronie b jest jedyną kolumną. Tutaj podane są optymalne ilości towaru i najwyższa możliwa łączna wartość frachtu. Trzecia linia to linia docelowa. (Kontrola: w trzech wierszach z powyższymi nagłówkami znajdują się liczby: Linia 1:1, 0,4, 8, 1, 0, 0, 3000, Linia 2: 1, 0,2 6, 0, 1, 0, 2000 i Linia 3: -10, -3, -50, 0, 0, 1, 0).
  5. Teraz postępuj jak przy użyciu metody Gaussa do rozwiązania LGS. W pierwszym kroku zmieniasz wiersz 1 ew. Linia 2 jest rozsyłana i dodawana do drugiej linii, tak że tylko 1 pojawia się w "Wiersz 1 + Kolumna 1" i 0 w "Wiersz 2 + Kolumna 1". Zmienia to również automatycznie wartości w linii docelowej.
  6. W tym przypadku możesz na przykład pomnożyć wiersz 2 przez -1 i dodać go do wiersza 1 i pomnożyć wiersz 2 przez 10 i dodaj do linii 3 (kontrola: linia 1: 0, 0.2, 2, 1, -1, 0, 1000, linia 2: pozostaje taka sama, linia 3: 0, -1, 10, 0, 10, 1, 20.000).
  7. W drugim kroku weź kolumnę 2 i utwórz 0, przekształcając „Wiersz 2 + kolumna 2”, a następnie 1 w „Wiersz 1 i kolumna 2”. Ponownie należy zauważyć, jak zmienia się linia docelowa.
  8. Etapy transformacji to na przykład pomnożenie wiersza 1 przez -1 i dodanie do wiersza 2 i wiersza 1 do 5 i dodanie do wiersza 3 (Sprawdź: po wykonaniu obu kroków wynik jest następujący: linia 1: 0, 1, 10, 5, -5, 0, 5000, linia 2: 1, 0, 4, -1, 2, 0, 1000 i linia 3: 0, 0, 20, 5, 5, 1, 25.000).
  9. Możesz teraz przeczytać rozwiązania po prawej stronie panelu. Skutkuje to całkowitą wartością frachtu 25 000 euro, 5000 jednostek towaru 1, 1000 jednostek towaru 2 i żadnej jednostki towaru 3.

Należy pamiętać, że rozwiązanie tabeli simplex daje optymalne rozwiązanie tylko wtedy, gdy w wierszu docelowym po lewej stronie po ostatnim kroku zmiany kształtu widoczne są tylko pozytywne wyniki Rachunkowość stoisko. Zinternalizowałeś system po 2-3 innych przykładach i będziesz w stanie rozwiązać takie zadania w przyszłości w zabawny sposób.

click fraud protection