Jeśli jesteś studentem inżynierii lub inżynierem, wiesz, co to znaczy zoptymalizować system, aby uzyskać jak najlepszy wynik.
Optymalizacja rozwiązania jest kluczem do sukcesu we wszystkim, od budowania mostów po tworzenie oprogramowania.
W tym momencie pojawia się pomysł podstawowego wykonalnego rozwiązania.
Jest to podstawowa idea programowania liniowego, która pozwala określić, które ze zbioru możliwych rozwiązań jest najlepsze.
Ale dlaczego to ma takie znaczenie? W tym artykule omówię podstawowe wykonalne rozwiązania i sposoby ich wykorzystania do rozwiązywania problemów inżynierskich w prawdziwym świecie.
Opowiem o tym, jak je znaleźć, z czego są zrobione i dlaczego są ważne.
Niezależnie od tego, czy jesteś doświadczonym inżynierem, czy dopiero rozpoczynającym naukę, dołącz do nas, gdy zanurzę się w świat podstawowych wykonalnych rozwiązań i pokażę, jak wykorzystać moc programowania liniowego.
Zrozumienie podstawowego wykonalnego rozwiązania
Formalna definicja:
Podstawowe rozwiązanie liniowego modelu programu, w którym wszystkie zmienne są nieujemne.
Podstawowe wykonalne rozwiązanie (BFS) to kluczowa idea w programowaniu liniowym, która pomaga znaleźć najlepsze rozwiązania.
BFS to rozwiązanie z najmniejszą możliwą liczbą niezerowych zmiennych.
Jest to róg wielościanu dopuszczalnych rozwiązań.
Innymi słowy, BFS jest rozwiązaniem podstawowym, które spełnia nieujemne ograniczenia i znajduje się w obszarze wykonalnym lub obszarze problemowym.
Znalezienie optymalnego podstawowego wykonalnego rozwiązania
Aby znaleźć najlepszy BFS, musimy wykonać następujące czynności:
- Napisz program w postaci standardowej dla ciągu liniowego.
- Zamień system nierówności w rozszerzoną macierz.
- Dowiedz się, które zmienne są podstawowe, a które nie.
- Dowiedz się, jakie są podstawowe zmienne w odniesieniu do innych zmiennych.
- Umieść te wyrażenia w funkcji celu, aby uzyskać funkcję tylko tych zmiennych, które nie są podstawowe.
- Znajdź niepodstawową zmienną, którą można zwiększyć bez łamania jakichkolwiek ograniczeń i która poprawi funkcję celu.
Ta zmienna jest teraz zmienną podstawową, a jedna z pozostałych zmiennych podstawowych nie jest już zmienną podstawową.
Jeśli istnieje rozwiązanie optymalne, musi ono znajdować się na jednym z końców lub wierzchołków regionu, w którym rozwiązania są możliwe.
Tak więc, jeśli LP ma rozwiązanie optymalne, ma rozwiązanie optymalne w skrajnym punkcie zbioru wykonalnego.
Ponadto zawsze istnieje optymalny BFS, jeśli istnieje optymalne rozwiązanie.
Korzystanie z metody Simplex w celu znalezienia optymalnego BFS
Metoda Simplex jest algorytmem rozwiązywania problemów w programowaniu liniowym.
Przechodzi z jednego BFS do „sąsiedniego” BFS za pomocą procedury obrotu.
W procedurze przestawnej zmienna inna niż podstawowa jest wybierana jako zmienna podstawowa, a następnie do rozwiązania dla nowych zmiennych podstawowych używany jest bieżący BFS.
Gdy żadna inna niż podstawowa zmienna nie może zostać zmieniona, aby poprawić funkcję celu, algorytm jest zakończony.
Dlaczego podstawowe wykonalne rozwiązania mają kluczowe znaczenie dla rozwiązywania złożonych problemów inżynierskich
Nadal trudno to zrozumieć? Zmienię trochę punkt widzenia:
Kto i tak potrzebuje prostych, praktycznych odpowiedzi? Po prostu złóż wszystko razem i miej nadzieję na najlepsze.
W końcu kto potrzebuje optymalizacji, kiedy chaos jest o wiele przyjemniejszy? Witamy w świecie zmiennych nieujemnych, gdzie wszystko jest tylko sugestią, a porażka jest prawie pewna.
Albo to jest?
Zbadajmy, dlaczego pozornie podstawowa koncepcja podstawowych wykonalnych rozwiązań wcale nie jest podstawowa i dlaczego mogą one być kluczem do rozwiązania nawet najbardziej złożonych problemów inżynierskich.
Dobra, to był tylko żart upozorowany na reklamę telewizyjną.
Wróćmy teraz do wyjaśnienia.
Znalezienie podstawowego wykonalnego rozwiązania
Podstawowe wykonalne rozwiązanie (BFS) to rozwiązanie problemu optymalizacji liniowej, które spełnia wszystkie ograniczenia i ma najmniejszą liczbę niezerowych zmiennych.
Każdy BFS jest narożnikiem wielościanu możliwych rozwiązań z geometrycznego punktu widzenia.
Jeśli istnieje najlepsze rozwiązanie, musi istnieć również najlepszy pierwszy krok.
W tym artykule porozmawiamy o tym, jak znaleźć początkowe podstawowe wykonalne rozwiązanie, jak znaleźć wszystkie podstawowe wykonalne rozwiązania oraz jak znaleźć podstawowe wykonalne rozwiązanie bez zmiennych zapasowych.
Znalezienie początkowego podstawowego wykonalnego rozwiązania
Możemy użyć różnych metod, w zależności od tego, jak problem jest ustawiony, aby znaleźć początkowe podstawowe rozwiązanie, które działa dla problemu optymalizacji liniowej.
Jednym ze sposobów jest dodanie zmiennych luźnych do ograniczeń dotyczących nierówności i ustawienie wszystkich pozostałych zmiennych na zero.
Zmienne luźne stają się zmiennymi podstawowymi, a pozostałe to zmienne niepodstawowe.
Dwufazowa Metoda Simplex to kolejny sposób na rozwiązanie problemu.
Ta metoda polega na rozwiązaniu dodatkowego problemu programowania liniowego w celu znalezienia początkowego podstawowego rozwiązania, które jest wykonalne.
Po znalezieniu początkowego podstawowego wykonalnego rozwiązania można użyć metody Simplex, aby przejść od jednego podstawowego wykonalnego rozwiązania do drugiego, a następnie do najlepszego rozwiązania.
Znalezienie wszystkich podstawowych wykonalnych rozwiązań
Może istnieć więcej niż jedno podstawowe rozwiązanie, które działa dla programu liniowego.
Możemy zmienić system, dodając zmienne luźne, a następnie użyć nowego systemu do znalezienia wszystkich podstawowych możliwych rozwiązań dla programu liniowego.
Następnie te podstawowe wykonalne rozwiązania są wykorzystywane do znalezienia podstawowych wykonalnych rozwiązań pierwotnego problemu.
Znalezienie podstawowego wykonalnego rozwiązania bez zmiennych typu Slack
Musimy użyć zmiennych wolnych, aby pozbyć się ograniczeń mniej niż, abyśmy mogli znaleźć podstawowe rozwiązanie, które działa bez zmiennych wolnych.
Zmienna luzu to po prostu różnica między prawą stroną ograniczenia a lewą stroną.
Na przykład dla pierwszego ograniczenia definiujemy zmienną luzu x4 = 14 - 2x1 - x2 - x3. Jeśli chodzi o tę nową zmienną, pierwsze ograniczenie jest równoważne po prostu x4 ≥ 0, co jest ograniczeniem dodatnim dla x4.
Gdy dodamy te wolne zmienne, otrzymamy program liniowy, który jest taki sam jak oryginalny, z wyjątkiem tego, że wszystkie ograniczenia są albo równaniami, albo ograniczeniami, które mówią, że coś jest dodatnie.
Zbiór zmiennych podstawowych, które w rozwiązaniu podstawowym mają wartości różne od zera, nazywamy bazą.
Zmienne, które w rozwiązaniu podstawowym mają wartość zero, nie są zmiennymi podstawowymi.
Aby znaleźć najlepsze rozwiązanie, musimy znaleźć wektor x, który spełnia wszystkie reguły i uzyskuje największą lub najmniejszą wartość dla celu.
Ale znalezienie najlepszego rozwiązania wymaga więcej kroków niż tylko znalezienie rozwiązania, które działa i nie ma luźnych zmiennych.
Nie zawsze jest możliwe znalezienie podstawowego rozwiązania bez luźnych zmiennych, szczególnie w przypadku problemów z ograniczeniami mniejszymi niż.
Aby znaleźć podstawowe wykonalne rozwiązanie, musisz użyć metody simplex lub innego algorytmu programowania liniowego, aby znaleźć rozwiązanie, które spełnia wszystkie ograniczenia i ma najmniej zmiennych niezerowych.
Właściwości i znaczenie podstawowego wykonalnego rozwiązania
Właściwości podstawowego wykonalnego rozwiązania
Podstawowe wykonalne rozwiązanie ma co najwyżej m zmiennych, które nie są równe zeru i co najmniej nm zmiennych, które są równe zeru, gdzie n to liczba zmiennych decyzyjnych, a m to liczba ograniczeń.
BFS jest narożnikiem wielościanu możliwych rozwiązań, a każdy BFS ma n aktywnych wiązań, które są liniowo niezależne.
Jeśli istnieje najlepsze rozwiązanie, musi istnieć również najlepszy pierwszy krok.
Najważniejszą rzeczą w podstawowych możliwych rozwiązaniach jest to, że są one końcami zbioru rozwiązań wypukłych dla problemu programowania liniowego.
Aby znaleźć najlepszą odpowiedź, algorytm simplex przechodzi przez serię BFS.
Algorytm Simplex przeszukuje wszystkie podstawowe możliwe rozwiązania w uporządkowany sposób, aby znaleźć najlepsze.
Znaczenie podstawowego wykonalnego rozwiązania
Znalezienie podstawowego rozwiązania, które jest możliwe, jest ważne, ponieważ pomaga znaleźć najlepszą odpowiedź na problemy programowania liniowego.
Daje również początek złożonym algorytmom i może być wykorzystany do ustalenia, czy program liniowy jest możliwy, czy nie.
Aby znaleźć wszystkie podstawowe możliwe rozwiązania dla programu liniowego, możesz zmienić system, dodając zmienne luźne, a następnie użyć zmienionego systemu do znalezienia wszystkich podstawowych możliwych rozwiązań.
Następnie te podstawowe wykonalne rozwiązania są wykorzystywane do znalezienia podstawowych wykonalnych rozwiązań pierwotnego problemu.
Wideo: podstawowe wykonalne 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: | BFS można wykorzystać do podziału ograniczonych zasobów między kilka projektów, tak aby jak najwięcej można było zrobić najmniejszym kosztem. Ta metoda może być stosowana w wielu różnych dziedzinach, takich jak transport, rolnictwo i finanse. |
| Optymalizacja sieci: | BFS można wykorzystać do usprawnienia działania sieci komunikacyjnych, transportowych i logistycznych. BFS może pomóc znaleźć najlepsze trasy dla towarów i usług, skrócić czas i pieniądze wydawane na transport oraz przyspieszyć i zapewnić dokładniejsze dostawy. |
| Planowanie produkcji: | BFS można wykorzystać do planowania produkcji w taki sposób, aby zasoby, takie jak siła robocza, surowce i sprzęt, były wykorzystywane w najlepszy możliwy sposób, aby uzyskać z nich jak najwięcej. BFS może pomóc obniżyć koszty produkcji, ograniczyć ilość odpadów i poprawić wydajność. |
| Planowanie finansowe: | W planowaniu finansowym BFS można wykorzystać do optymalizacji portfeli inwestycyjnych, obniżenia ryzyka i uzyskania jak największego zwrotu pieniędzy. BFS może pomóc znaleźć najlepszy sposób podziału aktywów, obniżyć koszty transakcji i zarobić więcej pieniędzy. |
| Zarządzanie łańcuchem dostaw: | BFS można wykorzystać do usprawnienia przepływu towarów i usług od dostawców do klientów w ramach zarządzania łańcuchem dostaw. BFS może pomóc w ustaleniu najlepszej ilości zapasów do utrzymania pod ręką, skróceniu czasu realizacji i poprawie obsługi klienta. |
Wniosek
Gdy to spojrzenie na podstawowe wykonalne rozwiązania dobiega końca, jasne jest, że są one ważnym narzędziem dla każdego inżyniera lub studenta inżynierii.
Od znalezienia najlepszego sposobu na zbudowanie skomplikowanego systemu po maksymalne wykorzystanie dostępnych zasobów, podstawowe wykonalne rozwiązania zapewniają ramy dla uzyskania najlepszego możliwego wyniku.
Ale nie tylko są przydatne, pokazują, jak elegancka i piękna może być matematyka.
To niesamowite, że można sprowadzić skomplikowane problemy do prostego zestawu równań, a następnie użyć tych równań do rozwiązywania problemów w prawdziwym świecie.
To dobre przypomnienie, że inżynieria polega na rozwiązywaniu problemów, a dzięki mocy matematyki możemy znaleźć odpowiedzi, które kiedyś uważano za niemożliwe.
Tak więc, gdy dowiesz się więcej o inżynierii, pamiętaj o tym, czego nauczyłeś się o prostych rozwiązaniach, które działają i wykorzystują je, aby uczynić świat lepszym i wydajniejszym miejscem.
Linki i referencje
Książki:
- Programowanie liniowe: podstawy i rozszerzenia
- Programowanie liniowe: teoria i zastosowania
Podziel się na…
