Lista zadań z programowania liniowego i całkowitego

Zadanie 1. Rozwiązać metodą graficzną zadania:

max z = 5x1 + 4x2 x1 + 2x2 ≤ 6 -2x1 + x2 ≤ 4 5x1 + 3x2 ≤15 x1, x2 ≥ 0

max z = x1 + x2 x1 + x2 ≤ 4 -x1 + x2 ≤ 2 x1 ≤ 3 x1, x2 ≥ 0

max z = 2x1 + x2 x1 + x2 ≤ 6 -x1 + 2x2 ≤ 2 x1, x2 ≥ 0

Rozwiązanie:

x₁ + 2x₂ ≤ 6, x₁ = 0, x₂ = 3

x₂ = 0, x₁ = 6

Funkcja celu:

20 = z = 5x1 + 4 x₂

f (z) (0, 5)

(4, 0)

Układ dwóch równań o z niewiadomych rozwiązujemy, które mogą być wycinkiem lub punktem.

Zadanie 2. Rozwiązać wszystkie modele i zadania 1 algorytmem sympleks. Dla trzeciego modelu należy zastosować M-metodę. Dla drugiego modelu wyznaczyć alternatywne rozwiązanie optymalne.

Zadanie 3. Rozwiązać algorytmem sympleks następujące zadanie:

max z = 4x₃ - x₁ - x₂

x₁ + x₂ + 2x₃ ≤ 9

x₁ + x₂ - x₃ ≤ 2

-x₁ + x₂ + x₃ ≤ 4

x₁, x₂, x₃ ≥ 0

Rozwiązanie metoda sympleks:

x₁ + x₂ + 2x₃ + S₁ = 9

x₁ + x₂ - x₃ + S₂ = 2

-x₁ + x₂ + x₃ + S₃ = 4

Z B = { S₁, S₂, S₃}

ZB	Rozw.	x1	x2	x3	S1	S2	S3
S1 S2 S3	9 2 4	1 1 -1	1 1 1	2 -1 1	1 0 0	0 1 0	0 0 1	9/1=9 2/1=2 -
z	0	1	1	1	0	0	0

Która zmienna wchodzi do bazy?

Element centralny

ZB	Rozw.	x1	x2	x3	S1	S2	S3
0 4 0	4 2	0	0	3	1	-2	0

Zadanie 4. Rozwiązać algorytmem sympleks następujące zadanie:

max z = -x₁ - 5x₂ + 1x₃

x₁ + 4x₂ - x₃ ≤ 4

x₁ + 2x₂ + 4x₃ ≤ 10

x₁, x₂, x₃ ≥ 0

Zadanie 5. Stosując M-metodę rozwiązać zadania:

max z = 5x1 + 2x2 + x3 2x1 - x2 + x3 ≥ 2 x1 + x2 + x3 = 5 x1, x2, x3 ≥ 0

max z = -x1 - x2 x1 - x2 - x3 =1 -x1 + x2 + 2x3 ≥ 1 x1, x2, x3 ≥ 0

Zadanie 6. Stosując M-metodę pokazać, że następujący model jest sprzeczny:

max z = x₁ + 3x₂ - x₃

x₁ + x₂ + 2x₃ ≤ 4

-x₁ + x₃ ≤ 4

x₃ ≥ 3

x₁, x₂, x₃ ≥ 0

Zadanie 7. Dla pewnego problemu maksymalizacji dana jest następująca końcowa (optymalna) tablica sympleksowa (nad każdą zmianą podany jest jej współczynnik w funkcji celu).

		2 x1	12 x2	7 x3	2 x4	0 x5
2 7	x4 x3	-3 2	-1 2	0 1	1 0	2 1	2 4
	z	6	0	0	0	11	32

Odczytać optymalne rozwiązanie i wartości funkcji celu. Czy istnieje alternatywne rozwiązanie optymalne? Jeżeli tak to je wyznaczyć. Dla jakich współczynników funkcji celu dla zmiennej x₃ baza {x₃, x₄} pozostanie optymalna?

Zadanie 8. Rozwiązać algorytmem podziału i ograniczeń (zbuduj drzewo podziału i ograniczeń) zadanie:

max z = 5x₁ + 4x₂

x₁ + 2x₂ ≤ 6

-2x₁ + x₂ ≤ 4

5x₁ + 3x₂ ≤15

x₁, x₂ ≥ 0, x₁, x₂ - całkowite

Uwaga: Ponieważ są tylko dwie zmienne, więc odpowiednie relaksacje najprościej rozwiązać metodą graficzną.

Zadanie 9. Rozwiąż algorytmem podziału i ograniczeń następujący problem plecakowy (zbuduj drzewo podziału i ograniczeń):

max z = 8x₁ + 5x₂ + 6x₃ + 4x₄ + 3x₅

8x₁ + 4x₂ + 7x₃ + 6x₄ + 3x₅ ≤ 20

-x₁ + x₃ ≤ 4

x₃ ≥ 3

x₁, x₂, x₃, x₄, x₅

z/-1 ← NIE!

← nie dzielimy przez ujemne

4/1

Wektor pkt

f (z)

---