Zadanie 367
Do przedsiębiorstwa nadchodzą, półfabrykaty w postaci arkuszy dykty. Na dostawy składają się dwie partie materiałów. Pierwsza zawiera 400 arkuszy, druga - 250 arkuszy dykty. Z otrzymanych arkuszy dykty wytwarza się określone komplety złożone z czterech detali typu 1, trzech detali typu 2 i dwóch detali typu 3. Jeden arkusz dykty w każdej partii można rozcinać dowolnymi sposobami.
Liczbę detali każdego typu, które otrzymujemy w wyniku cięcia jednego arkusza odpowiedniej partii dowolnym sposobem podano w tablicy.
Trzeba tak rozkroić dyktę, aby otrzymać największa, liczbę kompletów.
Pierwsza partia |
Druga partia |
|||||
Sposoby cięcia Detale |
1 |
2 |
3 |
Sposoby cięcia Detale |
1 |
2 |
1 |
0 |
6 |
9 |
1 |
6 |
5 |
2 |
4 |
3 |
4 |
2 |
5 |
4 |
3 |
10 |
16 |
0 |
3 |
8 |
0 |
Zmienne strategiczne:
X1...., X5 - ilości arkuszy dykty pociętych pięcioma sposobami
Funkcja celu:
Zmax = X1 + X2 + X3 + X4 + X5
Ograniczenia:
ze względu na skład kompletu:
-16X1 + 6X2+ 11 X3-2X4-X5 = 0
-20X1 - 26X2 + 9X3 - 10 X4 + 5X5 =0
ze względu na ilość arkuszy dykty:
X1 + X2 + X3 <= 400
X4 + X5 <= 250
Liczbowe rozwiązanie zadania:
Iteracja 0
BAZA |
C(j) |
X1 |
X2 |
X3 |
X4 |
X5 |
A1 |
A2 |
S3 |
S4 |
B(i) |
B(i) A(i,j) |
|
|
1 |
1 |
1 |
1 |
1 |
-M |
-M |
0 |
0 |
|
|
A1 |
-M |
-16 |
6 |
11 |
-2 |
-1 |
1 |
0 |
0 |
0 |
0 |
0 |
A2 |
-M |
-20 |
-26 |
9 |
-10 |
5 |
0 |
1 |
0 |
0 |
0 |
0 |
S3 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
400 |
0 |
S4 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
250 |
0 |
C(j)-Z(j) *Big M |
1.00 0 |
1.00 0 |
1.00 0 |
1.00 0 |
1.00 0 |
0 -1.00 |
0 -1.00 |
0 0 |
0 0 |
0 0 |
|
|
Iteracja 1
BAZA |
C(j) |
X1 |
X2 |
X3 |
X4 |
X5 |
A1 |
A2 |
S3 |
S4 |
B(i) |
B(i) A(i,j) |
|
|
1 |
1 |
1 |
1 |
1 |
-M |
-M |
0 |
0 |
|
|
A1 |
-M |
-16 |
6 |
11 |
-2 |
-1 |
1 |
0 |
0 |
0 |
0 |
0 |
A2 |
-M |
-20 |
-26 |
9 |
-10 |
5 |
0 |
1 |
0 |
0 |
0 |
0 |
S3 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
400 |
400 |
S4 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
250 |
Inf. |
C(j)-Z(j) *Big M |
1.00 -36.0 |
1.00 -20.0 |
1.00 20.00 |
1.00 -12.0 |
1.00 4.00 |
0 0 |
0 0 |
0 0 |
0 0 |
0 0 |
|
|
Iteracja 2
BAZA |
C(j) |
X1 |
X2 |
X3 |
X4 |
X5 |
A1 |
A2 |
S3 |
S4 |
B(i) |
B(i) A(i,j) |
|
|
1 |
1 |
1 |
1 |
1 |
-M |
-M |
0 |
0 |
|
|
X3 |
1 |
-1.450 |
0.545 |
1 |
-0.182 |
-0.091 |
0.091 |
0 |
0 |
0 |
0 |
Inf. |
A2 |
-M |
-6.910 |
-30.9 |
0 |
-8.360 |
5.818 |
-0.818 |
1 |
0 |
0 |
0 |
0 |
S3 |
0 |
2.455 |
0.455 |
0 |
0.182 |
0.091 |
-0.091 |
0 |
1 |
0 |
400 |
4000 |
S4 |
0 |
0 |
0 |
0 |
1.000 |
1.000 |
0 |
0 |
0 |
1 |
250 |
250.0 |
C(j) - Z(j) *BIG M |
2.455 -6.91 |
0.455 -30.9 |
0 0 |
1.182 -8.36 |
1.091 5.818 |
-0.091 -1.82 |
0 0 |
0 0 |
0 0 |
0 0 |
|
|
Iteracja 3
BAZA |
C(j) |
X1 |
X2 |
X3 |
X4 |
X5 |
A1 |
A2 |
S3 |
S4 |
B(i) |
B(i) A(i,j) |
|
|
1 |
1 |
1 |
1 |
1 |
-M |
-M |
0 |
0 |
|
|
X3 |
1 |
-1.560 |
0.063 |
1 |
-0.313 |
0 |
0.078 |
0.016 |
0 |
0 |
0 |
0 |
X5 |
1 |
-1.190 |
-5.310 |
0 |
-1.440 |
1 |
-0.141 |
0.172 |
0 |
0 |
0 |
Inf. |
S3 |
0 |
2.563 |
0.938 |
0 |
0.313 |
0 |
-0.078 |
-0.016 |
1 |
0 |
400 |
426.7 |
S4 |
0 |
1.188 |
5.313 |
0 |
2.438 |
0 |
0.141 |
-0.172 |
0 |
1 |
250 |
47.06 |
C(j) - Z(j) *BIG M |
3.750 0.000 |
6.250 0.000 |
0 0 |
2.750 0.000 |
0 0 |
0.063 -1.00 |
-0.188 -1.00 |
0 0 |
0 0 |
0 0 |
|
|
Iteracja 4
BAZA |
C(j) |
X1 |
X2 |
X3 |
X4 |
X5 |
A1 |
A2 |
S3 |
S4 |
B(i) |
B(i) A(i,j) |
|
|
1 |
1 |
1 |
1 |
1 |
-M |
-M |
0 |
0 |
|
|
X2 |
1 |
-25 |
1 |
16 |
-5 |
0 |
1.250 |
0.250 |
0 |
0 |
0 |
Inf. |
X5 |
1 |
-134 |
0 |
85 |
-28 |
1 |
6.500 |
1.500 |
0 |
0 |
0 |
Inf. |
S3 |
0 |
26 |
0 |
-15 |
5 |
0 |
-1.25 |
-0.250 |
1 |
0 |
400 |
15.38 |
S4 |
0 |
134 |
0 |
-85 |
29 |
0 |
-6.50 |
-1.500 |
0 |
1 |
250 |
1.866 |
C(j) - Z(j) *BIG(M) |
160 0.00 |
0 0 |
-100 0 |
34 0.0 |
0 0 |
-7.75 -1.00 |
-1.75 -1.00 |
0 0 |
0 0 |
0 0 |
|
|
Iteracja 5
BAZA |
C(j) |
X1 |
X2 |
X3 |
X4 |
X5 |
A1 |
A2 |
S3 |
S4 |
B(i) |
B(i) A(i,j) |
|
|
1 |
1 |
1 |
1 |
1 |
-M |
-M |
0 |
0 |
|
|
X2 |
1 |
0 |
1 |
0.142 |
0.410 |
0 |
0.037 |
-0.030 |
0 |
0.187 |
46.64 |
328.9 |
X5 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
250 |
Inf. |
S3 |
0 |
0 |
0 |
1.493 |
-0.627 |
0 |
0.011 |
0.041 |
1 |
-0.194 |
351.5 |
235.5 |
X1 |
1 |
1 |
0 |
-0.634 |
0.216 |
0 |
-0.049 |
-0.011 |
0 |
0.007 |
1.866 |
Inf. |
C(j) - Z(j) *BIG M |
0 0 |
0 0 |
1.493 0 |
-0.627 0 |
0 0 |
0.011 -1.00 |
0.041 -1.00 |
0 0 |
-1.19 0 |
298.5 0 |
|
|
Iteracja 6
BAZA |
C(j) |
X1 |
X2 |
X3 |
X4 |
X5 |
A1 |
A2 |
S3 |
S4 |
B(i) |
B(i) A(i,j) |
|
|
1 |
1 |
1 |
1 |
1 |
-M |
-M |
0 |
0 |
|
|
X2 |
1 |
0 |
1 |
0 |
0.470 |
0 |
0.036 |
-0.034 |
-0.095 |
0.205 |
13.25 |
28.19 |
X5 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
250 |
250.0 |
X3 |
1 |
0 |
0 |
1 |
-0.420 |
0 |
0.008 |
0.027 |
0.670 |
-0.130 |
235.5 |
Inf. |
X1 |
1 |
1 |
0 |
0 |
-0.050 |
0 |
-0.044 |
0.006 |
0.425 |
-0.075 |
151.2 |
Inf. |
C(j) - Z(j) *BIG M |
0 0 |
0 0 |
0 0 |
0 0 |
0 0 |
0 -1.00 |
0 -1.00 |
-1 0 |
-1 0 |
650.0 0 |
|
|
Iteracja 7
BAZA |
C(j) |
X1 |
X2 |
X3 |
X4 |
X5 |
A1 |
A2 |
S3 |
S4 |
B(i) |
B(i) A(i,j) |
|
|
1 |
1 |
1 |
1 |
1 |
-M |
-M |
0 |
0 |
|
|
X4 |
1 |
0 |
2.128 |
0 |
1 |
0 |
0.077 |
-0.072 |
-0.202 |
0.436 |
28.19 |
0 |
X5 |
1 |
0 |
-2.130 |
0 |
0 |
1 |
-0.077 |
0.072 |
0.202 |
0.564 |
221.8 |
0 |
X3 |
1 |
0 |
0.894 |
1 |
0 |
0 |
0.040 |
-0.003 |
0.585 |
0.053 |
247.3 |
0 |
X1 |
1 |
1 |
0.106 |
0 |
0 |
0 |
-0.040 |
0.003 |
0.415 |
-0.053 |
152.7 |
0 |
C(j) - Z(j) *BIG M |
0 0 |
0 0 |
0 0 |
0 0 |
0 0 |
0 -1.00 |
0 -1.00 |
-1 0 |
-1 0 |
650.0 0 |
|
|
Wyliczone wartości
Nazwa zmiennej |
Wartość |
Nazwa zmiennej |
Wartość |
X1 |
152.6596 |
A1 |
0 |
X2 |
0.0000 |
A2 |
0 |
X3 |
247.3404 |
S3 |
0 |
X4 |
28.1915 |
S4 |
0 |
X5 |
221.8085 |
|
|
Zmax = 650 |
|||
Interpretacja
Z pierwszej partii należy pociąć 153 arkuszy pierwszym sposobem i 247 - trzecim sposobem, z drugiej partii 28 arkuszy pierwszym sposobem i 222 arkusze drugim sposobem.
Zadanie 367
Strona 4 z 4