Problem:
Solution:
(1) is pretty easy, it is obvious that we can have at most 5 items of size 6, and at most 3 items of size 10, so a simple addition table would show what the configurations are
So there are 13 configurations.
(2) The linear program is
Minimize $ \sum{x_c} $
Subject to $ \sum{x_c a_{s,c}} \ge n_s $
To see if a given solution is feasible for the linear program, we simply check. First, recall $ a_{s,c} $ is the number of items of size $ s $ in configuration $ c $, so we have:
$ a_{6,1} = 5 $
$ a_{10,1} = 0 $
$ a_{6,2} = 0 $
$ a_{10,2} = 3 $
And also $ n_s $ is the number of items of size $ s $, so
$ n_{6} = 14 $
$ n_{10} = 8 $
The constraints are now
$ x_{c_1} a_{6,1} + x_{c_2} a_{6,2} \ge n_{6} $
$ x_{c_1} a_{10,1} + x_{c_2} a_{10,2} \ge n_{10} $
Putting in the values, now we get
$ \frac{14}{5} 5 + \frac{8}{3} 0 \ge 14 $
$ \frac{14}{5} 0 + \frac{8}{3} 3 \ge 8 $
Now it is obvious the given solution is feasible!
(3) The solution is sparse, as we have only two nonzero entries.
(4) Following the given algorithm, we would round down the given $ x_c $ values, so we have
$ \lfloor x_{c_1} \rfloor = \lfloor \frac{14}{5} \rfloor = 2 $ bins in configuration 1 and
$ \lfloor x_{c_2} \rfloor = \lfloor \frac{8}{3} \rfloor = 2 $ bins in configuration 2.
(5) With the solution above, we have covered
$ 2 \times 5 = 10 $ items of size $ 6 $
$ 2 \times 3 = 6 $ items of size $ 10 $
So we have $ 14  10 = 4 $ items of size $ 6 $ and $ 8  6 = 2 $ items of size $ 10 $ to go in the problem $ \bar I $.
(6) For $ P_1 $, we will be opening two more bins, one for each configuration.
(7) Now we run next fit as follow
[6,6,6,6] [10,10]
So we also open two bins with next fit, so again, we are using two more bins.
(8) The total size is $ 6 \times 14 + 8 \times 10 = 164 $, we will need at least $ \lceil \frac{164}{30} \rceil = 6 $ bins. The solution above use 4 bins in the linear programming solution and 2 more bins with the rest using either method, so it is using 6 bins. As there is no way we can do any better than 6 bins, so the solution is optimal.
Solution:
(1) is pretty easy, it is obvious that we can have at most 5 items of size 6, and at most 3 items of size 10, so a simple addition table would show what the configurations are
0

10

20

30


0

0

10

20

30

6

6

16

26

36

12

12

22

32

42

18

18

28

38

48

24

24

34

44

54

30

30

40

50

60

So there are 13 configurations.
(2) The linear program is
Minimize $ \sum{x_c} $
Subject to $ \sum{x_c a_{s,c}} \ge n_s $
To see if a given solution is feasible for the linear program, we simply check. First, recall $ a_{s,c} $ is the number of items of size $ s $ in configuration $ c $, so we have:
$ a_{6,1} = 5 $
$ a_{10,1} = 0 $
$ a_{6,2} = 0 $
$ a_{10,2} = 3 $
And also $ n_s $ is the number of items of size $ s $, so
$ n_{6} = 14 $
$ n_{10} = 8 $
The constraints are now
$ x_{c_1} a_{6,1} + x_{c_2} a_{6,2} \ge n_{6} $
$ x_{c_1} a_{10,1} + x_{c_2} a_{10,2} \ge n_{10} $
Putting in the values, now we get
$ \frac{14}{5} 5 + \frac{8}{3} 0 \ge 14 $
$ \frac{14}{5} 0 + \frac{8}{3} 3 \ge 8 $
Now it is obvious the given solution is feasible!
(3) The solution is sparse, as we have only two nonzero entries.
(4) Following the given algorithm, we would round down the given $ x_c $ values, so we have
$ \lfloor x_{c_1} \rfloor = \lfloor \frac{14}{5} \rfloor = 2 $ bins in configuration 1 and
$ \lfloor x_{c_2} \rfloor = \lfloor \frac{8}{3} \rfloor = 2 $ bins in configuration 2.
(5) With the solution above, we have covered
$ 2 \times 5 = 10 $ items of size $ 6 $
$ 2 \times 3 = 6 $ items of size $ 10 $
So we have $ 14  10 = 4 $ items of size $ 6 $ and $ 8  6 = 2 $ items of size $ 10 $ to go in the problem $ \bar I $.
(6) For $ P_1 $, we will be opening two more bins, one for each configuration.
(7) Now we run next fit as follow
[6,6,6,6] [10,10]
So we also open two bins with next fit, so again, we are using two more bins.
(8) The total size is $ 6 \times 14 + 8 \times 10 = 164 $, we will need at least $ \lceil \frac{164}{30} \rceil = 6 $ bins. The solution above use 4 bins in the linear programming solution and 2 more bins with the rest using either method, so it is using 6 bins. As there is no way we can do any better than 6 bins, so the solution is optimal.
No comments :
Post a Comment