Wykład 1

Literatura

  1. Metody rozwiązywania zadań optymalizacji
  2. braki 2—7
  3. Podstawy techniki systemów - ogolne zasady projektowania, Artur Hall 1968
  4. Algorytmy kombinatorycze, E. Reingdat, J. Nievegelt, N. Deo, PWN 1985

system - coś co możemy rozpatrywać w oderwaniu od całości

Optymalizacja - to znalezienie najlepszego rozwiazania pewnego zagadnienia przy danych warunkach.
Optymalizacja jest stosowana w projektowaniu, ekonomice, wojskowosci, polityce…

Metody optymalizacji stosowane do decyzji gospodarczych naleza do tzw. badan operacyjnych.

Problem optymalizacji jest nazywany programowaniem maematycznym, ktore mozna w sposob ogolny sformuowac nastepujaco:
zminimalizowac (albo zmaksymalizowac, pewna funkcje od x1,..,xn czyli f(x1,x2…,xn) przy spelnieniu warunków
g1(x1, x2, …, xn) ≤ b1

gm(x1, x2, …, xn)) ≤ bm

xj >= 0; j = 1, 2, …, n
f(x1,x2,…xn) jest na
funkcja celu albo kryterium ()

mega braki

Zbiory postaci (x1,x2,…,xn) nazywamy zmiennymi decyzyjnymi.
Nie istnieje jeden ogolny algorytm rozwiazujacy wszystkie zagadnienia optymalizacji. Problemy optymalizacji sa podzielone na rozne klasy i dla tych klas sa opracowane lub opracowywane algorytmy rozwiazujace te zagadnienia optymalizacji.

wymienmy podstawowe z nich:

  • programowanie liniowe,
  • programowanie calkowitoliczbowe,
  • programowanie zero—jedynkowe,
  • programowanie nieliniowe,
  • programowanie dynamiczne,
  • programowanie kwadratowe,
  • programowanie sieciowe (optymalizacja na grafach),
  • programowanie stochastyczne (losowe).

i dotyczace w/w problemow optymalizacji programowanie wielocelowe (wielokryterialne, polioptymalizacyjne)

Programowanie liniowe

  • algorytm simpleks,
  • zagadnienia,
    • planowanie produkcji,
    • model optymalnej mieszanki,
    • model transportowy pl opracowano wygodniejsze od metody simpleks algorytmy.

Interpretacja geometryczna (przyklad)
t = 3x1 + 2x2 (MAX)
(1) x1 + 2x2 ≤ 6; ograniczenia (0, 3) i (6, 0)
(2) 3x1 + x2 ≤ 7; ograniczenia (0, 7) i (21/3, 0)

Kierunek funkcji f wyznaczjaja wspolczynniki 2 i 3

braki

tu obrazek

Biorąc np f = 18 otrzymamy punkty przeciecia osi (0, 9) i (6, 0), przesuwamy rownolegle wykres funkcji f, az prosta f dotknie wielobok. W tym punkcie jest rozwiazanie optymalne

M. D. Zasoby
Sk. twarda 6,1 5,4 28000dm3
Sk. miekka 11,2 23,0 47000dm3
zysk 49zł 78zł

L = 49x1 + 78x2 (MAX)
6,1x1 + 5,4x2 ≤ 28000dm3
11,2x1 + 23,0x2 ≤ 47000dm3
x1 z2 >= 0
l1 = 49x1 + 78x2 - 3x3 (MAX)

braki - skan z ksiazki do przepisania

20 30 50
m1 1 1 4 200
m2 1 3 2 200
m3 2 1 2 200

L = 20x1 + 30x2 + 50x""3"" (MAX)
m1 = x1 + x2 + 4x3 ≤ 200
m2 = x1 + 3x2 + 2x3 ≤ 200
m3 = 2x1 + x2 + 2x3 ≤ 200

metoda eliminacji gaussa

x1 x2 x3 x4 x5 x6
20 30 50 0 0 0 0
x4 1 1 4 1 0 0 200 200/4
x5 1 3 2 0 1 0 200 200/2
x6 2 1 2 0 0 1 200 200/2

braki - gryzdoly

x1 x2 x3 x4 x5 x6
7,5 17,5 0 12,5 0 0 -2500
x3 0,25 0,25 1 0,25 0 0 50 50/0,25
x5 0,5 2,5 0 -0,5 1 0 100 100/2,5
x6 1,5 0,5 0 -0,5 0 1 100 100/0,5

braki - gryzdoly

x1 x2 x3 x4 x5 x6
4 0 0 -9 -7 0 -3200
x3 0,2 0 1 0,3 0,1 0 40
x2 0,2 1 0 -0,2 0,4 0 40
x6 1,4 0 0 -0,4 -0,2 1 80

x1 = 0, x2 = 40, x3 = 40
L = 20*0 + 30*40 + 50*40 = 3200

x1 x2 x3 x4 x5 x6
0 0 0 -76/10 -6??/7 -30/7 -3200180/7
x3 28,6
x5 28,6
x6 1 0 0 -2/7 -1/7 5/7 400/7

L = 20*400/7 + 30*28,6 + 50*28,6 = 8000/7 = 3431

braki - skan z ksiazki do przepisania

braki - skan z ksiazki do przepisania

braki - skan z ksiazki do przepisania

braki - skan z ksiazki do przepisania

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License