Jeśli jesteś inżynierem lub studentem inżynierii, być może wiesz, co to znaczy optymalizacja.
Aby uzyskać najlepszy możliwy wynik, ważne jest, aby znaleźć najlepszy sposób robienia rzeczy.
W programowaniu liniowym możesz użyć podstawowego rozwiązania, aby znaleźć najlepsze rozwiązanie.
Ale co to jest rozwiązanie podstawowe i dlaczego wiedza o nich jest tak ważna dla inżynierów? W tym artykule opowiem o tym, jakie są podstawowe rozwiązania, dlaczego są ważne w inżynierii i jak można je wykorzystać, aby uzyskać najlepsze wyniki w różnych sytuacjach.
Więc zapnij pasy i przygotuj się na zanurzenie w świecie podstawowych rozwiązań, w którym rozwieję tajemnice i pokażę, jak potężna może być ta technika.
Podstawowe rozwiązania w programowaniu liniowym
Formalna definicja:
Rozwiązanie liniowego modelu programu składającego się z m równań w n zmiennych uzyskuje się przez rozwiązanie dla m zmiennych względem pozostałych (nm) zmiennych i ustawienie (nm) zmiennych na zero.
Podstawowe rozwiązanie w programowaniu liniowym to sposób rozwiązania problemu programowania liniowego, który spełnia określone wymagania techniczne.
W szczególności wektor x jest rozwiązaniem podstawowym dla wielościanu, jeśli wektory {ai : xi = 0} są liniowo niezależne.
Oznacza to, że kolumny A, które mają zmienne xi różne od zera, są liniowo niezależne.
Podstawowe rozwiązanie z nieujemnymi składnikami nazywa się podstawowym możliwym rozwiązaniem (BFS) (BFS).
BFS spełnia wszystkie zasady definiujące wielościan.
Każdy BFS jest narożnikiem wielościanu możliwych rozwiązań z geometrycznego punktu widzenia.
Aby znaleźć podstawowe rozwiązanie, musisz ustawić nm zmiennych, które nie są podstawowe, na zero i rozwiązać m zmiennych, które są podstawowe.
Możliwe jest, że różne podstawy prowadzą do tego samego podstawowego rozwiązania, co oznacza, że może istnieć więcej niż jeden sposób rozwiązania tego samego problemu.
Metoda Simplex jest procesem iteracyjnym, który przechodzi od jednego BFS do następnego, aż do znalezienia najlepszego BFS.
Po zastosowaniu metody simplex do znalezienia BFS możemy stwierdzić, czy rozwiązanie jest najlepsze, sprawdzając, czy inne BFS w pobliżu dają lepszą wartość dla funkcji celu.
Jeśli takiego BFS nie ma, to obecny BFS jest najlepszy.
Model programowania liniowego
Model programowania liniowego obejmuje trzy główne komponenty: zmienne decyzyjne, funkcję celu i ograniczenia.
Zarówno funkcja celu, jak i ograniczenia muszą być funkcjami liniowymi, a zmienne decyzyjne muszą być ciągłe.
Funkcja celu służy do zwiększania lub zmniejszania liczby reprezentującej zysk, koszt, liczbę wyprodukowanych produktów itp.
Ograniczenia to limity lub ograniczenia dotyczące całkowitej ilości określonego zasobu potrzebnego do wykonania zadań, które określą poziom sukcesu w zmiennych decyzyjnych.
Ponadto niektóre programy liniowe wymagają, aby wszystkie zmienne decyzyjne były nieujemne.
W modelach programowania liniowego można również używać zmiennych całkowitych i binarnych.
Zmienne binarne mogą mieć tylko wartość 0 lub 1, więc mogą mieć tylko wartość 0 lub 1.
Metoda Simplex
Jednym z najczęściej używanych sposobów rozwiązywania problemów programowania liniowego jest metoda simplex.
Rozwiązania podstawowe są ważne w metodzie simplex, ponieważ odpowiadają punktom narożnym obszaru wykonalnego, a metoda simplex przechodzi od jednego rogu do drugiego, aż do znalezienia optymalnego rozwiązania.
Metoda simplex to szybki sposób na znalezienie najlepszej odpowiedzi na problem programowania liniowego przy użyciu właściwości podstawowych rozwiązań.
Aby użyć metody simplex do znalezienia najlepszego BFS, musimy znaleźć bazę B dla macierzy ograniczeń A i rozwiązać układ Ax = b ze wszystkimi zmiennymi innymi niż podstawa równa zero.
Otrzymane wartości dla podstawowych zmiennych tworzą BFS.
Jeśli istnieje optymalne rozwiązanie, to istnieje optymalny BFS.
Metoda Simplex przesuwa się z jednego BFS do sąsiedniego BFS, aż do osiągnięcia optymalnego BFS za pomocą procedur obrotu.
Porównanie podstawowych rozwiązań i wykonalnych rozwiązań
Różnica między rozwiązaniem podstawowym a rozwiązaniem wykonalnym polega na tym, że rozwiązanie podstawowe nie musi spełniać żadnych warunków.
W szczególności musi mieć wektory, które są liniowo niezależne i mają niezerowe wartości dla xi, a x musi być mniejsze od 0.
Z drugiej strony, wykonalnym rozwiązaniem jest każdy punkt, który mieści się w granicach problemu.
Ale nie wszystkie możliwe rozwiązania są podstawowymi możliwymi rozwiązaniami.
Podstawowe możliwe rozwiązania (BFS) to tylko te, które pasują do narożników wielościanu możliwych rozwiązań.
Powrót do podstaw: odblokowywanie mocy podstawowych rozwiązań w inżynierii
Nadal trudno to zrozumieć? Zmienię trochę punkt widzenia:
Masz dość używania skomplikowanych metod i algorytmów do rozwiązywania trudnych problemów? Czy chciałbyś, aby istniał prostszy, bardziej bezpośredni sposób radzenia sobie z problemami z modelem programu liniowego?
Cóż, nie martw się, ponieważ odpowiedź jest tutaj: rozwiąż m zmiennych pod względem pozostałych (nm) zmiennych i ustaw zmienne (nm) na zero.
Kto potrzebuje algorytmów, które brzmią fantazyjnie, skoro można wrócić do podstaw? Odłóż więc kalkulatory i zacznijmy poznawać proste rozwiązania.
Dobra, to był tylko żart upozorowany na reklamę telewizyjną.
Wróćmy teraz do wyjaśnienia.
Podstawowe programowanie liniowe rozwiązania
Wskazówka: włącz przycisk napisów, jeśli go potrzebujesz. Wybierz „automatyczne tłumaczenie” w przycisku ustawień, jeśli nie znasz języka mówionego. Może być konieczne kliknięcie najpierw języka filmu, zanim Twój ulubiony język będzie dostępny do tłumaczenia.
Przypadków użycia
| Stosuje się w: | Opis: |
|---|---|
| Alokacja zasobów: | Podstawowe rozwiązanie może być stosowane w problemach alokacji zasobów, gdzie celem jest podział ograniczonych zasobów pomiędzy konkurujące ze sobą potrzeby. Na przykład firma może potrzebować podzielić swój budżet między różne działy lub projekty. Korzystając z podstawowych rozwiązań, mogą znaleźć najlepszy sposób wykorzystania swoich zasobów, aby zarobić jak najwięcej pieniędzy lub wydać jak najmniej. |
| Planowanie produkcji: | W planowaniu produkcji podstawowe rozwiązanie może być wykorzystane do znalezienia najlepszego zestawu produktów do wytworzenia, aby zarobić jak najwięcej pieniędzy. Firmy mogą znaleźć najlepszą kombinację produkcji, która przynosi najwięcej pieniędzy i kosztuje najmniej, korzystając z podstawowego rozwiązania. |
| Planowanie: | Podstawowe rozwiązanie może służyć do ustalenia, jak zaplanować zadania lub zadania, aby można je było wykonać w najbardziej efektywny sposób. Na przykład firma może potrzebować zaplanować godziny pracy swoich pracowników, aby upewnić się, że mają wystarczającą liczbę pracowników, gdy firma jest zajęta. Korzystając z podstawowego rozwiązania, mogą znaleźć najlepszy sposób na zaplanowanie rzeczy, tak aby było jak najmniej przestojów i jak najwięcej pracy zostało wykonane. |
| Zarządzanie łańcuchem dostaw: | W zarządzaniu łańcuchem dostaw celem jest zapewnienie jak najpłynniejszego przepływu towarów i usług od dostawcy do klienta. Na przykład firma może potrzebować znaleźć najlepsze trasy transportu towarów, aby ograniczyć koszty do minimum i dostarczyć towary na czas. Korzystając z podstawowych rozwiązań, mogą znaleźć najlepszy plan zarządzania łańcuchem dostaw, który utrzymuje niskie koszty i zapewnia zadowolenie klientów. |
| Optymalizacja portfela: | W optymalizacji portfela, gdzie celem jest znalezienie najlepszej kombinacji inwestycji, aby zarobić jak najwięcej pieniędzy przy jak najmniejszym ryzyku, można zastosować podstawowe rozwiązania. Na przykład firma inwestycyjna może potrzebować znaleźć najlepszą kombinację akcji, obligacji i innych papierów wartościowych, aby pomóc swoim klientom osiągnąć cele inwestycyjne. Korzystając z prostego rozwiązania, mogą znaleźć najlepszy sposób mieszania swoich portfeli, aby uzyskać najlepsze zwroty przy najmniejszym ryzyku. |
Wniosek
Podsumowując, idea rozwiązania podstawowego jest bardzo ważna w dziedzinie inżynierii i może być wykorzystywana na wiele różnych sposobów.
Wiedząc, czym jest podstawowe rozwiązanie i co robi w programowaniu liniowym, możemy ulepszać rozwiązania, obniżać koszty i zwiększać ich wydajność.
Należy jednak pamiętać, że podstawowe rozwiązanie nie jest rozwiązaniem uniwersalnym, mimo że jest potężnym narzędziem.
Aby uzyskać najlepsze wyniki, każdy problem musi być dokładnie przeanalizowany i przemyślany.
Jako inżynierowie musimy stale analizować, w jaki sposób podstawowe rozwiązania i inne techniki optymalizacyjne mogą pomóc nam w poczynieniu postępów i opracowaniu nowych pomysłów.
Uznajmy więc siłę prostych rozwiązań i przesuwajmy granice tego, co jest możliwe, stosując nowe techniki i strategie.
Linki i referencje
Książki:
- Programowanie liniowe Vasek Chvatal
- Modelowanie i rozwiązywanie programowania liniowego za pomocą R autorstwa Jose M. Sallana
Podziel się na…
