lecture 5.pdf

AdamKasperski,MichałKulejBadaniaOperacyjneWykład3

PROGRAMOWANIE LINIOWE

CAŁKOWITOLICZBOWE

Zadanie programowania liniowego w którym zmienne decyzyjne

musz¸a przyjmować wartości całkowite nazywamy zadaniem

programowania liniowego całkowitoliczbowego (krótko PLC).

MAX(MIN)z = c 1 x 1 + c 2 x 2 + + c N x N

[Funkcjacelu]

a 11 x 1 + a 12 x 2 + + a 1N x N ≤ (≥, =)b 1

[Ograniczenie1]

. . .

a M1 x 1 + a M2 x 2 + + a MN x N ≤ (≥, =)b M [Ograniczenie m]

x 1 ≥ 0, . . . , x R ≥ 0, r ≤ n

[Ograniczenianaznak]

x I −całkowite, i = 1, . . . , n 1 (n 1 ≤ n).

Jeśli n 1 = n, zagadnienie nazywamy czystym zagadnieniem

programowania liniowego (PCL) natomiast, gdy n 1 < n zagadnienie

nazywamy mieszanym (MCL).

AdamKasperski,MichałKulejBadaniaOperacyjneWykład3

P1Zagadnienie rozkroju . Klient zamówił w tartaku 100 desek o

szerokości 2 cm, 150 desek o szerokości 3 cm i 80 desek o szerokości

4 cm. Wszystkie zamawiane przez klientów deski są tej samej

długości l. Deski wycinane s¸a ze standardowych desek o długości l i

szerokości 10 cm. W jaki sposób zrealizować zamówienie aby ilość

ci¸etych desek standardowych była minimalna? Poniższa tabela

pokazuje wszystkie możliwe sposoby poci¸ecia standardowej deski:

AdamKasperski,MichałKulejBadaniaOperacyjneWykład3

Sposób Ilość 4 cm Ilość 3 cm Ilość 2 cm

1 2 0 1

2 1 2 0

3 1 1 1

4 1 0 3

5 0 3 0

6 0 2 2

7 0 1 3

8 0 0 5

Zmienne decyzyjne:

• x i ilość desek ci¸eta itym sposobem i = 1, . . . , 8.

AdamKasperski,MichałKulejBadaniaOperacyjneWykład3

Model:

i=1 x i → MIN

2x 1 + x 2 + x 3 + x 4 ≥ 80

[Deski 4 cm]

2x 2 + x 3 + 3x 5 + 2x 6 + x 7 ≥ 150 [Deski 3 cm]

x 1 + x 3 + 3x 4 + 2x 6 + 3x 7 + 5x 8 ≥ 100 [Deski 2 cm]

x i ≥ 0, x i − całkowite, i = 1, . . . , 8

AdamKasperski,MichałKulejBadaniaOperacyjneWykład3

Zadanie w którym wszystkie zmienne decyzyjne musz¸a przyjmować

wartość 0 lub 1 nazywamy zadaniem programowania 0-1 .

MAX(MIN)z = c 1 x 1 + c 2 x 2 + + c n x n

[Funkcja celu]

a 11 x 1 + a 12 x 2 + + a 1n x n ≤ (≥, =)b 1

[Ograniczenie 1]

. . .

a m1 x 1 + a m2 x 2 + + a mn x n ≤ (≥, =)b m [Ograniczenie m]

x i ∈ {0, 1}, i = 1, . . . , n

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: