WOJSKOWA AKADEMIA TECHNICZNA

Podstawy optymalizacji

Laboratoria numer 1

Rafał Łańcucki

I9X5S1

1. Zadanie do wykonania

Przy wykorzystaniu programu WinQSB zbadać istnienie rozwiązania

optymalnego dla zadanego zadania optymalizacji.

Dokonać analizy wrażliwości dla współczynników funkcji celu rozwiązywanego zadania optymalizacyjnego

1. Rozwiązanie przykładu pierwszego

Zadanie:

12x1 + 5x2 + 7x3 -> min

3x1 + 2x2 + 3x3 >= 7

x1 + x2 + x3 >= 5

2x1 + 4x3 >= 6

xi >= 0

Rozwiązanie za pomocą programu WinQSB.

Rozwiązanie metodą poznaną na ćwiczeniach.

Doprowadzenie do postaci normalnej:

3x1 + 2x2 + 3x3 –x4 = 7

x1 + x2 + x3 – x5 = 5

2x1 + 4x3 – x6 = 6

xi >= 0

Jak łatwo zauważyć zadanie musimy rozwiązać m-metodą. Kolejne kroki zostały

przedstawione w poniższych tabelach.

Cj – Zj <= 0 – warunek stopu. Mamy rozwiązanie optymalne!

x1 = 0

x2 = 3,5

x3 = 1,5

Zarówno program jak i metoda z zajęć doprowadziły do tego samego rozwiązania. Można

więc śmiało stwierdzić, że jest ono poprawne.

Zamiana na zadanie dualne:

c = [12, 5, 7]

d = [7, 5, 6]

A = [3, 2, 3 | 1, 1, 1 | 2, 0, 4]

nowa funkcja celu:

7y1 + 5y2 + 6y3 -> max

AT = [3, 1, 2 | 2, 1, 0 | 3, 1, 4]

3y1 + y2 + 2y3 <= 12

2y1 + y2 <= 5

3y1 + y2 + 4y3 <= 7

Rozwiązanie :

y1 = 0

y2 = 5

y3 = 0,5

analiza wrażliwości dla współczynników funkcji celu:

- manipulowanie współczynnikiem zmiennej x1 w zakresie od 6 w górę nie ma wpływu

na wartość funkcji rozwiązania optymalnego oraz na jego rozwiązanie końcowe,

- zmniejszenie współczynnika zmiennej x1 poniżej wartości 6 zmniejsza wynik funkcji

celu oraz zmienia rozwiązanie zadania na takie, w którym zmienna x1 występuje ze

współczynnikiem różnym od zera,

- zmiana współczynnika zmiennej x2 w zakresie od 0 do 7 nie powoduje zmiany

rozwiązania końcowego, ale zmienia dla niego wartość funkcji celu,

- zwiększenie współczynnika zmiennej x2 powyżej wartości 7 powoduje zmianę

rozwiązania na takie, w którym zmienna x2 występuje ze współczynnikiem równym

zero oraz zmianę wartości funkcji celu,

- manipulacja wartością współczynnika zmiennej x3 w zakresie od 5 do 19 nie zmienia

rozwiązania, ale zmienia wartość funkcji celu,

- zmniejszenie wartości współczynnika zmiennej x3 poniżej wartości 5 skutkuje zmianą

rozwiązanie na takie, w którym występuje tylko zmienna x3 oraz co za tym idzie,

zmianę wartości funkcji celu

- zwiększenie wartości współczynnika zmiennej x3 powyżej 19 skutkuje zmianą

rozwiązania na takie, w którym zmienna x3 ma współczynnik równy zero, oraz zmianą

wartości funkcji celu.

1. Rozwiązanie przykładu drugiego

Zadanie:

- 40x1 - 20x2 - 40x3 ->min

3x1 + 5x2 + 3x3 <= 30

2x1 + 5x2 + 8x3 <= 25

4x1 + 1x2 + 4x3 <= 20

xi >= 0

Rozwiązanie

1. Analiza rozwiązania zadania nr2.

Rozwiązaniem tego zadania są wyniki:

• x₁ = 4.17

• x₂ = 3.33

• x₄ = 0.83

• Wartość funkcji celu wynosi: - 233,33.

Rozwiązaniem zadania jest wektor = [4.17 , 3.33 , 0 , 0.83 , 0 , 0].

1. Wnioski

Program WinQSB pozwala w prosty sposób skorzystać z algorytmu simplex w celu rozwiązania zadania optymalizacyjnego metodą prymalną. Przydatna jest również opcja analizy wrażliwości, która to zobrazowuje w jaki sposób zmiana parametrów funkcji celu wpłynie na rozwiązanie oraz wartość funkcji celu.