1. Wyjaśnij znaczenie słowa liniowe w nazwie programowanie liniowe.
Programowanie liniowe to klasa problemów programowania matematycznego, w której wszystkie warunki ograniczające oraz funkcja celu mają postać liniową. Warunki ograniczające mają postać:
Znaleść maksimum (minimum) funkcji:
przy założeniu że zmienne x₁ ,x₂,...., x_n czynią zadość następującym warunkom:

oraz

$${\sum_{i = 1}^{m}{x_{\text{ij}} = a_{i}}\ \ \ \ \ \ (i = 1,\ldots.,m)\backslash n}{\sum_{j = 1}^{n}{x_{\text{ij}} = b_{j}\ \ \ \ \ \ (j = 1,\ldots.n)}\backslash n}{x_{\text{ij}} \geq 0\ \ \ \ \ (i = 1,\ldots.m;j = 1\ldots.n)\backslash n}$$

???????3. Opisz wykorzystanie programowania liniowego do zagadnienia rozkroju materiałów? 
np. krojenie prętów jest to
rozkład jednowymiarowy:
-funkcja celu: minimalizacja zużycia prętów;
-warunek ograniczający: wycięcie ilości prętów zgodnie z zamówieniem
rozkład dwuwymiarowy- obywa się w dwóch wymiarach, np. przemysł włókienniczy;

Model rozkroju nazywany jest również w literaturze modelem minimalizacji odpadów. Do rozwiązywania tych problemów wykorzystuje się metodę programowania liniowego.
liniowy model ma następującą postać:

x_j ≥ 0

F =

gdzie:

a_ij – liczba sztuk elementu „i” otrzymana z jednostki materiału wyjściowego przy danej strategii rozkroju „j”
x_j – liczba jednostek materiału wyjściowego, która będzie rozkrojona daną strategią „j”
b_i – założona liczba elementów
c_j – odpad jednostki materiału wyjściowego przy strategii rozkroju „j”

Przykład nr 1

 

Proces technologiczny wymaga, żeby do wytworzenia pewnego produktu gotowego  wytwarzać trzy rodzaje elementów. Mogą to być elementy drewniane, papierowe ewentualnie metalowe – w każdym razie są wycinane z jednorodnego arkusza danego materiału o ustalonych wymiarach: 5 metrów na 10 metrów. Element pierwszy e1 jest trapezem prostokątnym: podstawa dolna 5 m, podstawa górna 3 m, wysokość 4 m. Drugi element e2 jest prostokątem o wymiarach: 3m x 4m. Trzeci element e3 jest również prostokątem o wymiarach: 2m x 5m. Wiadomo, że należy wytworzyć co najmniej 12000 elementów e1, co najmniej 6000 elementów e2, co najmniej 8000 elementów e3.

 

Należy zbudować zadanie PL w celu udzielenia odpowiedzi na pytanie: jak rozcinać standardowe arkusze, aby zminimalizować liczbę zużytych arkuszy i wytworzyć wymaganą liczbę wymienionych, trzech elementów?

 

 

4. Wyjaśnij na przykładzie znaczenie pojęcia obszar rozwiązań dopuszczalnych.
Rozwiązanie dopuszczalne- układ zmiennych , które spełniają wszystkie nierówności, jest to taki układ decyzyjnych, który spełnia wszystkie ograniczenia ; np. x1=0, x2=0, x3=0 , x4=0 dopuszcza teoretycznie istnienie takich zmiennych, albo np.: x1=3, x2=2, x3=0 x4=1

5. Wyjaśnij na przykładzie znaczenie pojęcia rozwiązanie optymalne.
Rozwiązanie optymalne- rozwiązanie dopuszczalne, które gwarantuje ekstremum funkcji celu. Jeżeli rozwiązanie dopuszczalne jest zbiorem pustym, to rozwiązanie optymalne nie istnieje ! Ekstremum oznacza minimum lub maksimum funkcji.
Np. Funkcja celu : Z=4x1+5x2+9x3+2x4->max
to rozwiązanie optymalne jest w 3 iteracji i wyniki to x1=7,14 x2=0, x3=7,86 x4=0
F.C=99,29

6. Co to jest rozwiązanie kompromisowe (optymalne w sensie Pareto)? 
Programowanie w sensie Pareto należy do programowania wielokryterialnego. Czasem istnieje kilka kryteriów oceny, która z decyzji dopuszczalnych jest najlepsza. Każde kryterium może wskazywać inne rozwiązanie optymalne. Są to optima cząstkowe.
W takiej sytuacji musimy znaleźć kompromis – ustalić jedną (albo zbiór)  decyzję/rozwiązanie kompromisowe.
Służą ku temu różne metody, np.:
Rozwiązanie optymalne w sensie Pareto / optimum Pareto / zbiór decyzji sprawnych / zbiór decyzji efektywnych / zbiór decyzji niezdominowanych – Czyli rozwiązanie najlepsze z punktu widzenia wszystkich funkcji celu - takie rozwiązania, że nie istnieje żadne inne rozwiązanie od nich lepsze chociaż dla jednej funkcji celu, przy pozostałych funkcjach przynajmniej zachowujących swoje wartości. Innymi słowy - jest to takie rozwiązanie (tak dobre rozwiązanie), że żeby je polepszyć (tzn. znaleźć inne lepsze rozwiązanie) dla jednej funkcji celu to tylko kosztem pogorszenia dla innej funkcji.
Cechy rozwiązania optymalnego Pareto?
-zaletą rozwiązania optymalnego w sensie Pareto jest to że wyznaczenie rozwiązania najlepszego nie wymaga uzyskania informacji o preferencjach
-wyznaczając decyzję Pareto-optymalne ograniczamy się do operacji porównawczych, czyli w skali porządkowej. Jest to taka skala, w której w zależności od rozpatrywania cechy decyzja A jest lepsza od decyzji B. Wyróżniamy wobec tego:
-rozwiązanie zdominowane- rozwiązanie , które jest gorsze od innego, z punktu widzenia wszystkich kryteriów optymalizacji;
-rozwiązanie dominujące-jest lepsze od innego z punktu widzenia wszystkich kryteriów optymalizacji;

7. Wyjaśnij na przykładzie znaczenie pojęcia funkcja celu.
Funkcja Celu- kryterium według którego można oceniać dokonywany wybór rozwiązania najlepszego spośród dopuszczalnych rozwiązań czyli jak dany system w procesie swojego działania zbliża się do osiągnięcia wyznaczonego celu. FC określa więc zależność między celem systemu a środkami służącymi do jego realizacji.

Np. przedsiębiorstwo produkuje wyroby i za każdy wyrób ma zysk f celu będzie maksymalny zysk za każdy wyrób

Z=4x1+6x2+3x3+12x4->max

8. Wyjaśnij na przykładzie znaczenie pojęcia warunki ograniczające.
Warunkami ograniczające to przeszkody jakie mogą sie pojawić w trakcie realizacji celu.

Np. limity przedsiębiorstwo produkuje wyroby z limitami 90000 i 120000

Warunki ograniczające:

X1+ x2+x3+x4<=90000

2x1+2x2+2x3+2x4<=120000

$$\mathbf{x =}\sum_{\mathbf{i = 1}}^{\mathbf{12}}{\mathbf{R}_{\mathbf{i}}\mathbf{- 6}}\backslash n\backslash n$$