DEV Community

Cover image for Kwiaty czy zioła?
Dawid Ryłko
Dawid Ryłko

Posted on • Originally published at dawidrylko.com on

Kwiaty czy zioła?

Problem programowania liniowego z maksymalizacją liniowej funkcji celu jest matematycznym zadaniem optymalizacyjnym, w którym celem jest znalezienie optymalnych wartości zmiennych decyzyjnych, tak aby zwiększyć lub osiągnąć maksymalną wartość określonej liniowej funkcji celu. W tym kontekście, optymalizuje się alokację zasobów, by osiągnąć najlepsze możliwe wyniki, jednocześnie spełniając liniowe ograniczenia związane z danym problemem.

Problem

Rolnik dysponuje obszarem o powierzchni 100 hektarów, na którym planuje uprawiać kwiaty i zioła wykorzystywane do produkcji kosmetyków. W sezonie każdy hektar ziół wymaga 4 godzin pracy i 60 zł kapitału, natomiast każdy hektar kwiatów wymaga 16 godzin pracy i 120 zł kapitału. W ciągu sezonu rolnik chce przepracować maksymalnie 800 godzin oraz dysponuje kapitałem w wysokości 74000 zł. Zysk z hektara ziół wynosi 240 zł, a z kwiatów 300 zł. Jakie ilości hektarów ziół i kwiatów powinien uprawiać, aby maksymalizować zysk?

Rozwiązanie

W celu rozwiązania zadania, można sformułować problem jako zadanie optymalizacyjne.

Wpierw wypiszmy założenia (zmienne), które będziemy rozpatrywać:

  • xx - ilość hektarów, na których uprawiane są zioła

  • yy - ilość hektarów, na których uprawiane są kwiaty

Teraz można przejść do opisu problemu.

Maksymalizujemy funkcję zysku :

Z(x,y)=240x+300yZ(x,y)=240x+300y

Dodajemy ograniczenia :

4x+16y8004x + 16y \leq 800 - ograniczenie ilości godzin pracy

60x+120y7400060x + 120y \leq 74000 - ograniczenie kapitału

Ograniczenia dodatkowe :

x0x \geq 0 - ilość hektarów, na których uprawiane są zioła nie może być ujemna

y0y \geq 0 - ilość hektarów, na których uprawiane są kwiaty nie może być ujemna

Rozwiązanie matematyczne

4x+16y8004x + 16y \leq 800

60x+120y7400060x + 120y \leq 74000

x0x \geq 0

y0y \geq 0

Rozwiązaniem jest układ nierówności. Rozwiązując ten układ nierówności, możemy znaleźć optymalne wartości xx i yy .

Rozwiązanie programistyczne

Czas na konkrety. Jakie wartości kryją się pod xx i yy ?

Do rozwiązania powyższego problemu możemy użyć darmowego roziązania CLP , z pakietu OR-Tools od Google.

Route. Schedule. Plan. Assign. Pack. Solve.

from ortools.linear_solver import pywraplp

def main():
    solver = pywraplp.Solver.CreateSolver("CLP")
    if not solver:
        return

    x = solver.NumVar(0, 100, "Herbs")
    y = solver.NumVar(0, 100, "Flowers")

    print("Number of variables =", solver.NumVariables())

    solver.Add(x + y <= 100)
    solver.Add(4 * x + 16 * y <= 800)
    solver.Add(60 * x + 120 * y <= 74000)

    print("Number of constraints =", solver.NumConstraints())

    solver.Maximize(240 * x + 300 * y)

    print(f"Solving with {solver.SolverVersion()}")
    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL:
        print("Solution:")
        print("Max profit =", solver.Objective().Value())
        print("Area for growing herbs =", x.solution_value())
        print("Area for growing flowers =", y.solution_value())
    else:
        print("The problem does not have an optimal solution.")

if __name__ == " __main__":
    main()
Enter fullscreen mode Exit fullscreen mode

Wynik w konsoli:

Number of variables = 2
Number of constraints = 3
Solving with Clp 1.17.7
Solution:
Max profit = 26000.0
Area for growing herbs = 66.66666666666666
Area for growing flowers = 33.333333333333336
Enter fullscreen mode Exit fullscreen mode

Może nie piękne, ale praktyczne. Sami o sobie piszą tak:

OR-Tools to pakiet oprogramowania typu open source do optymalizacji zaprojektowany w celu rozwiązania najtrudniejszych na świecie problemów z routingiem, przebiegami, programowaniem liczb całkowitych i liniowych oraz programowaniem ograniczeń.

Przydatne linki

Top comments (0)

The discussion has been locked. New comments can't be added.