Problemy, rozwiązania i aplikacje programowania liniowego [z przykładem]

Data science ma wiele zastosowań, jednym z najważniejszych jest optymalizacja. Wszyscy skupiamy się na optymalizacji rzeczy. Optymalizacja skupia się na uzyskaniu najbardziej pożądanych wyników przy ograniczonych zasobach, jakie posiadasz.

Dostępne są różne rodzaje problemów optymalizacyjnych, niektóre są małe, inne są bardzo skomplikowane. Przeglądając je, znajdziesz specyficzną kategorię zwaną problemami programowania liniowego. W tym artykule omówiliśmy, czym one są i jak możesz nad nimi pracować.

Załóżmy, że jesteś sprzedawcą owoców, który może kupić pomarańcze lub jabłka albo pewną ich kombinację. Jednak masz tylko budżet w wysokości 5000 INR i możesz przechowywać tylko 30 torebek. Teraz musisz je kupować w sposób, który przyniesie Ci największy zysk.

Teraz jedna torba pomarańczy kosztuje Cię 500 INR, podczas gdy torba jabłek kosztuje 750 INR. Możesz zarobić 100 INR ze sprzedaży jednej torby pomarańczy i 200 INR ze sprzedaży jednej torby jabłek.

Ten problem ma różne możliwości. Możesz kupić tylko pomarańcze, ale wtedy będziesz mieć tylko 10 torebek w magazynie, a Twój zysk wyniesie 1000 INR. Podobnie możesz zdecydować się na zakup samych jabłek i zarobić 1500 INR jako zysk. Możesz także kupić kombinację tych dwóch.

Takie problemy nazywamy problemami programowania liniowego i omówimy je szczegółowo. Zacznijmy:

Co to jest programowanie liniowe?

Programowanie liniowe to metoda przedstawiania złożonych relacji za pomocą funkcji liniowych. Naszym celem w programowaniu liniowym jest znalezienie najbardziej odpowiednich rozwiązań dla tych funkcji. Rzeczywista zależność między dwoma punktami może być bardzo złożona, ale możemy użyć programowania liniowego, aby zobrazować je z prostotą. Programowanie liniowe znajduje zastosowanie w wielu branżach.

Podstawy programowania liniowego

Oto kilka podstawowych terminów programowania liniowego:

Ograniczenie

Ograniczenia (lub ograniczenia) zmiennych decyzyjnych nazywane są ograniczeniami. Większość ograniczeń czasowych to ograniczenia, jakie masz w zakresie zasobów potrzebnych do rozwiązania problemu.

Zmienna decyzyjna

Te zmienne definiują twoje dane wyjściowe. Twój wynik zależy od tych zmiennych, dlatego nazywamy je „zmiennymi decyzyjnymi”.

Ograniczenie nieujemności

Zmienne decyzyjne problemu programowania liniowego mogą mieć tylko wartość nieujemną. Oznacza to, że wartości zmiennych decyzyjnych mogą być równe lub większe od zera.

Funkcja celu

Funkcja celu to cel podejmowania decyzji. Mówiąc prościej, jest to ostateczny wynik twojego problemu z programowaniem liniowym. Na przykład, gdy znajdujesz maksymalny zysk, jaki możesz osiągnąć z danym zestawem zasobów, maksymalny zysk jest funkcją celu.

Formułowanie problemów programowania liniowego

Powinieneś wiedzieć, jak sformułować programowanie liniowe, aby zastosować je w prawdziwym życiu. Załóżmy, że jesteś producentem zabawek i produkujesz tylko dwie zabawki: A i B. Z grubsza mówiąc, Twoje zabawki wymagają dwóch zasobów X i Y do wytworzenia. Oto wymagania Twoich zabawek:

• Jedna jednostka zabawki A wymaga jednej jednostki zasobu X i trzech jednostek zasobu Y

• Jedna jednostka zabawki B wymaga jednej jednostki zasobu X i dwóch jednostek zasobu Y

Masz pięć jednostek zasobu X i 12 jednostek zasobu Y. Twoje marże zysku ze sprzedaży tych zabawek wynoszą:

• 6 INR za każdą sprzedaną sztukę zabawki A
• 5 INR za każdą sprzedaną jednostkę zabawki B

Ile sztuk każdej zabawki wyprodukowalibyście, aby uzyskać maksymalny zysk?

Rozwiązanie

Przedstawmy nasz problem programowania liniowego w równaniu:

Z = 6a + 5b

Tutaj z oznacza całkowity zysk, a oznacza całkowitą liczbę sztuk zabawek A, a b oznacza całkowitą liczbę sztuk B. Naszym celem jest maksymalizacja wartości Z (zysku).

Twoja firma chciałaby wyprodukować jak najwięcej sztuk tych zabawek, ale masz ograniczone zasoby. Ograniczenia naszych zasobów są ograniczeniami tego problemu. Mamy tylko w sumie

a + b 5

Teraz każda jednostka zabawki A i B wymaga odpowiednio 3 i 2 jednostek zasobu Y. A w sumie mamy tylko 12 jednostek zasobu Y, więc matematycznie wyglądałoby to tak:

3a + 2b 12

Pamiętaj, że wartości jednostek zabawki A mogą być tylko liczbami całkowitymi. Oznacza to, że mamy również ograniczenia a->0 i b<-0.

Więc teraz masz właściwy problem z programowaniem liniowym. Możesz sformułować inne problemy programowania liniowego, postępując zgodnie z tym przykładem. Chociaż ten przykład był dość prosty, problemy z LP mogą stać się bardzo skomplikowane.

Przeczytaj: Pomysły i tematy projektów programowania liniowego

Etapy formułowania problemów programowania liniowego

Aby sformułować problem programowania liniowego, wykonaj następujące kroki:

• Znajdź zmienne decyzyjne
• Znajdź funkcję celu
• Zidentyfikuj ograniczenia
• Pamiętaj o ograniczeniu braku negatywności

Jeśli problem spełnia powyższe kryteria, jest to problem programowania liniowego. Warto pamiętać o tym kryterium podczas pracy nad identyfikacją typu problemu.

Rozwiązywanie problemów programowania liniowego za pomocą R

Jeśli używasz R, rozwiązywanie problemów programowania liniowego staje się znacznie prostsze. To dlatego, że R ma pakiet lpsolve, który zawiera różne funkcje zaprojektowane specjalnie do rozwiązywania takich problemów. Jest wysoce prawdopodobne, że będziesz bardzo często używać R do rozwiązywania problemów LP jako naukowiec danych. Dlatego udostępniliśmy dwa różne przykłady, które pomogą Ci lepiej zrozumieć jego implementację:

Przykład

Zacznijmy od podstawowego problemu. Organizacja ma dwa produkty o cenach sprzedaży 25 INR i 20 INR i są one nazywane odpowiednio produktem A i B. Każdego dnia mają 1800 jednostek surowców do produkcji tych produktów. Produkt A wymaga 20 jednostek surowców, a B wymaga 12 jednostek surowców. Czas produkcji obu tych produktów wynosi cztery minuty, a organizacja ma w sumie osiem godzin pracy dziennie. Problem w tym, jaka powinna być wielkość produkcji każdego z tych produktów, aby zmaksymalizować zyski firmy?

Rozwiązanie:

Zaczniemy rozwiązywać ten problem od zdefiniowania jego funkcji celu:

maks. (sprzedaż) = maks. ( 25 r. 1 + 20 r. 2 )

Tutaj 25 i 20 to ceny odpowiednio produktu A i B, y1 to całkowita liczba wyprodukowanych jednostek produktu A, a y2 to całkowita liczba wyprodukowanych jednostek produktu B. Nasze zmienne decyzyjne to y1 i y2.

Ustawimy teraz ograniczenia dla naszego problemu:

Ograniczenie zasobów:

20 lat 1 + 12 lat 2 1800

Ograniczenie czasowe:

4 lata 1 + 4 lata 2 8*60

Naszym celem jest znalezienie odpowiedniej liczby produktów, które musimy wyprodukować, aby uzyskać maksymalny zysk.

Używanie R do rozwiązania problemu:

Użyjemy lpsolve do rozwiązania tego problemu z LP i zaczniemy od ustawienia funkcji celu:

> wymagaj(lpRozwiąż)

Ładowanie wymaganego pakietu: lpSolve

> cel.in <- c(25, 20)

> cel.in

[1] 25 20

Następnie zbudujemy macierz ograniczeń:

> const <- matrix(c(20, 12, 4, 4), nrow=2, byrow=TRUE)

> stała

[,1] [,2]

[1,] 20 12

[2,] 4 4

> ograniczenia_czasowe <- (8*60)

> ograniczenia_zasobu <-1800

> ograniczenia_czasowe

[1] 480

> ograniczenia_zasobu

[1] 1800

Stwórzmy teraz już zdefiniowane równania:

> rhs <- c(ograniczenia_zasobu, ograniczenia_czasu)

> prawa strona

[1] 1800 480

> kierunek <- c(„<=”, „<=”)

> kierunek

[1] „<=” „<=”

Po dodaniu wszystkich niezbędnych informacji możemy zacząć szukać optymalnej odpowiedzi. Składnia naszego pakietu to:

lp( kierunek, cel, const.mat, const.dir, const.rhs )

> optimum <- lp(kierunek=”max”, cel.in, const, kierunek, prawa oś)

> optymalne

Sukces: funkcja celu to 2625

> podsumowanie (optymalne)

Tryb klasy długości

kierunek 1 -brak- numeryczny

x.count 1 -brak- numeryczny

cel 2 -brak- liczbowy

const.count 1 -brak- numeryczne

ograniczenia 8 -brak- numeryczne

int.count 1 -brak- numeryczne

int.vec 1 -none- numeryczne

bin.count 1 -none- numeryczne

binary.vec 1 -none- numeryczne

num.bin.solns 1 -brak- numeryczne

objval 1 -brak- numeryczne

rozwiązanie 2 -brak- numeryczne

rozwiązać 1 -brak- numeryczne

compute.sens 1 -none- numeric

sens.coef.od 1 -brak- numeryczne

sens.coef.to 1 -none- numeryczne

podwójna 1 -brak- numeryczna

duals.from 1 -brak- numeryczne

duals.to 1 -none- numeryczne

skala 1 -brak- numeryczna

use.dense 1 -none- numeryczne

gęsty.col 1 -none- numeryczne

gęsty.val 1 -brak- numeryczny

gęsta.stała.nrow 1 -brak- numeryczna

gęsty.ctr 1 -none- numeryczne

use.rw 1 -none- numeryczne

tmp 1 -brak- znak

status 1 -brak- numeryczny

Po uruchomieniu powyższego kodu możesz uzyskać pożądane rozwiązania naszego problemu.

Optymalne wartości dla y1 i y2:

Pamiętaj, że y1 i y2 były jednostkami produktu A i produktu B, które musieliśmy wyprodukować:

> $rozwiązanie optymalne

[1] 45 75

Optymalna wielkość sprzedaży:

Maksymalny zysk jaki możemy wygenerować przy uzyskanych wartościach y1 i y2 to:

> optymalna$objval

[1] 2625

Przeczytaj także: Algebra liniowa do uczenia maszynowego

Zastosowania programowania liniowego

Jak wspomnieliśmy wcześniej, programowanie liniowe znajduje zastosowanie w wielu branżach. Oto kilka obszarów, w których go używamy:

• Wraz z rosnącą popularnością usług dostawczych, programowanie liniowe stało się jedną z najchętniej wybieranych metod znajdowania optymalnych tras. Kiedy weźmiesz Olę lub Ubera, oprogramowanie użyje programowania liniowego, aby znaleźć najlepszą trasę. Firmy kurierskie, takie jak Amazon i FedEx, również używają go do określania najlepszych tras dla swoich dostawców. Koncentrują się na skróceniu czasu i kosztów dostawy.
• Uczenie nadzorowane w uczeniu maszynowym działa na podstawowych koncepcjach programowania liniowego. W nadzorowanym uczeniu się musisz znaleźć optymalny model matematyczny do przewidywania wyników na podstawie dostarczonych danych wejściowych.
• Sektor detaliczny wykorzystuje programowanie liniowe do optymalizacji przestrzeni na półkach. Przy tak wielu dostępnych markach i produktach ustalenie, gdzie je umieścić w sklepie, jest bardzo rygorystycznym zadaniem. Umieszczenie produktu w sklepie może znacząco wpłynąć na jego sprzedaż. Duże sieci handlowe, takie jak Big Bazaar, Reliance, Walmart itp., używają programowania liniowego do określania lokowania produktu. Muszą mieć na uwadze interes konsumentów, zapewniając jednocześnie najlepsze lokowanie produktu, aby uzyskać maksymalny zysk.
• Firmy korzystają z programowania liniowego, aby usprawnić swoje łańcuchy dostaw. Wydajność łańcucha dostaw zależy od wielu czynników, takich jak wybrane trasy, harmonogramy itp. Korzystając z programowania liniowego, mogą znaleźć najlepsze trasy, harmonogramy i inne alokacje zasobów, aby zoptymalizować ich wydajność.

Dowiedz się więcej o programowaniu liniowym i analizie danych

Programowanie liniowe to jedna z najważniejszych koncepcji nauki o danych. Jest to również podstawowy temat, o którym powinieneś wiedzieć, aby zostać biegłym naukowcem zajmującym się danymi. Jak wspomnieliśmy, istnieje wiele zastosowań tej koncepcji i można znaleźć jej przypadki użycia w codziennym życiu.

Możesz dowiedzieć się więcej o data science i powiązanych z nią koncepcjach, odwiedzając nasz blog. Mamy wiele cennych zasobów, które pomogą Ci dowiedzieć się więcej. Oto kilka do dalszej lektury:

• Najważniejsze powody, by zostać analitykiem danych
• Algorytmy, które powinien znać każdy analityk danych
• Jak zostać analitykiem danych

Z drugiej strony możesz wziąć udział w kursie nauki o danych, aby uczyć się od ekspertów branżowych. Będziesz mógł uczyć się interaktywnie dzięki filmom, quizom i projektom. Uczestnictwo w kursie pomoże Ci zdobyć umiejętności niezbędne do zostania profesjonalnym naukowcem danych. Sprawdź IIIT-B i upGrad's PG Diploma in Data Science, który jest stworzony dla pracujących profesjonalistów i oferuje ponad 10 studiów przypadków i projektów, praktyczne warsztaty praktyczne, mentoring z ekspertami branżowymi, 1 na 1 z mentorami branżowymi, ponad 400 godzin pomocy w nauce i pracy z najlepszymi firmami.