Определение оптимального целочисленного решения

Страницы работы

6 страниц (Word-файл)

Содержание работы

Вывод ограничения, отсекающего нецелочисленное решение.

Постановка задачи ЛП с ЦЧР

Σ сj*xj   ->  max                     (5)

Σ aij*xj   =  bj ,  i = 1,..,m        (6)

xj  ≥  0    и целочисленные   (7)

            Пусть оптимальное решение существует и имеет конечное значение и

Пусть                                                             Σ aj*xj   =  b                (8)

сумма  нескольких уравнений из (6), каждое из которых умножено   на свою постоянную.

Поэтому решение, удовлетворяющее   (6),  удовлетворяет и (8).

Пусть некоторые  коэффициенты  aj    и   b   не целочисленные.  Так как xj  должны  быть

целочисленными,   то нецелочисленные  aj    и   b   надо заменить на целочисленные [aj]    и  [ b] ,

такие, что     aj  = [aj]    +   fj                  и     b   =  [ b]  + f,  где           0 ≤ fj  , f     1. 

Тогда         (8)  станет   неравенством      Σ [aj]*xj    ≤  [b]      (9)

            Покажем, что это так на примере       7*X1   +4.5*X2  =  31.5   

Заменим   4.5    на    4  и  31.5  на  31,   тогда    7*X1   +4*X2  =  28   ≤  31.

Добавим слева в (9)  неизвестную   x.    Получим        Σ [aj]*xj   +   x   =  [b]      (10).

Очевидно, что    x  -   целочисленная.

Значит   (10)  - ограничение, отсекающее нецелочисленное решение. 

При решении задачи ЦЛП  удобнее использовать другую форму этого ограничения, получаемую вычитанием   (8)     из (10).  Получаем   Σ [aj]*xj  - Σ aj*xj  +   x   =  b  -  [b] , или     

                                                           Σ [-fj]*xj  +   x   =  -f          (11)

Вывод ограничения из уравнения базисной переменной

Алгоритм определения оптимального целочисленного решения

1.  Решить задачу ЛП симплекс-методом.

2.  Если решение целочисленное, прекратить решение.

3.  Добавить целочисленное ограничение, полученное из уравнения базисной переменной и перейти к п. 1.

Пусть уравнение базисной переменной имеет вид:

xk  +   Σ tij*xj   =  b,    i -  строка,  j – небазисные переменные            (18).

Пусть некоторые  tij  = [tij]    +   fij       и     b   =  [ b]  + f       нецелочисленные,     тогда добавляется целочисленное ограничение, отсекающее нецелочисленное решение задачи:        

xk  +   Σ [-fj]*xj  +   x   =  -f          (19).

Пример

21*X1  +  11*X2    ->   max

7*X1 + 4*X2 + X3 = 13

Получить целочисленное решение.

X0  -  21*X1  - 11*X2                                                    =  0

X0                        + X2 +   3*X3                                    = 39

                X1 + 4/7*X2 + 1/7*X3                                   = 1 6/7

                       - 4/7*X2 - 1/7*X3        + X4                    = - 6/7

X0                                 +2¾*X3    +7/4*X4                  = 37 1/2

                            X1                                         +  X4                 =  1

                                             X2 + 1/4*X3  - 1¾*X4                  = 1 ½

                                                   - 1/4*X3  - ¼*X4       +  X5     = - ½

X0                                                      - X4       +11*X5  =   32

                            X1                                     +  X4                      =  1

                                             X2                 - 2*X4      + X5        =   1

                                                            X3  +    X4    - 4*X5       =   2

X0       + X1                                                   +11*X5    =   32

                            X1                                     +  X4                      =  1

                        2*X1       +   X2                                                  =   3

                         - X1                         + X3                    - 4*X5    =   1

Задания по целочисленному программированию

Пример 1

00

21x1 + 11x2  -> max

7x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

01

22x1 + 11x2  -> max

7x1 + 3x2 + x3 = 13   x1,x2,x3  => 0

02

21x1 + 12x2  -> max

7x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

03

21x1 + 11x2  -> max

7x1 + 3x2 + x3 = 13   x1,x2,x3  => 0

04

21x1 + 11x2  -> max

8x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

05

22x1 + 11x2  -> max

7x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

06

21x1 + 12x2  -> max

7x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

07

21x1 + 11x2  -> max

7x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

08

21x1 + 11x2  -> max

7x1 + 5x2 + x3 = 13   x1,x2,x3  => 0

09

21x1 + 11x2  -> max

8x1 + 3x2 + x3 = 13   x1,x2,x3  => 0

10

21x1 + 11x2  -> max

8x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

11

21x1 + 11x2  -> max

7x1 + 4x2 + x3 = 14   x1,x2,x3  => 0

12

21x1 + 11x2  -> max

7x1 + 4x2 + x3 = 15   x1,x2,x3  => 0

13

21x1 + 13x2  -> max

7x1 + 4x2 + x3 = 15   x1,x2,x3  => 0

14

23x1 + 11x2  -> max

7x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

15

21x1 + 11x2  -> max

7x1 + 5x2 + x3 = 13   x1,x2,x3  => 0

16

21x1 + 13x2  -> max

7x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

17

21x1 + 12x2  -> max

7x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

18

23x1 + 11x2  -> max

7x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

19

21x1 + 12x2  -> max

7x1 + 4x2 + x3 = 14   x1,x2,x3  => 0

20

21x1 + 11x2  -> max

7x1 + 4x2 + x3 = 16   x1,x2,x3  => 0

21

21x1 + 11x2  -> max

7x1 + 4x2 + x3 = 14   x1,x2,x3  => 0

22

20x1 + 11x2  -> max

7x1 + 4x2 + x3 = 15   x1,x2,x3  => 0

23

21x1 + 10x2  -> max

7x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

24

21x1 + 12x2  -> max

7x1 + 3x2 + x3 = 13   x1,x2,x3  => 0

25

21x1 + 14x2  -> max

7x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

26

21x1 + 12x2  -> max

7x1 + 4x2 + x3 = 17   x1,x2,x3  => 0

27

22x1 + 11x2  -> max

7x1 + 5x2 + x3 = 13   x1,x2,x3  => 0

28

21x1 + 12x2  -> max

9x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

29

21x1 + 11x2  -> max

7x1 + 4x2 + x3 = 13   x1,x2,x3  => 0

30

20x1 + 11x2  -> max

7x1 + 4x2 + x3 = 11   x1,x2,x3  => 0

31

21x1 + 11x2  -> max

7x1 + 4x2 + x3 = 15   x1,x2,x3  => 0

32

21x1 + 10x2  -> max

7x1 + 4x2 + x3 = 17   x1,x2,x3  => 0

Пример 2

00

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

01

3x1 + 4x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

02

4x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

03

3x1 + 3x2 + 14x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

04

3x1 + 3x2 + 13x3  ->  max

-4x1 + 6x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

05

3x1 + 3x2 + 13x3  ->  max

-3x1 + 7x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

06

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 8x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

07

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 8     5x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

08

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 8     6x1 – 4x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

09

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

10

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 8     6x1 – 3x2 + 8x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

11

4x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 9     6x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

12

3x1 + 4x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 9   0 ≤ x1,x2,x3 ≤ 5

13

3x1 + 3x2 + 14x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

14

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 9     6x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

15

3x1 + 3x2 + 13x3  ->  max

-4x1 + 6x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 9   0 ≤ x1,x2,x3 ≤ 5

16

3x1 + 3x2 + 13x3  ->  max

-3x1 + 7x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 9   0 ≤ x1,x2,x3 ≤ 5

17

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 8x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 9   0 ≤ x1,x2,x3 ≤ 5

18

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 9     7x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

19

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 9     6x1 – 4x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

20

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 9     6x1 – 3x2 + 8x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

21

5x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 9   0 ≤ x1,x2,x3 ≤ 5

22

3x1 + 5x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 9   0 ≤ x1,x2,x3 ≤ 5

23

3x1 + 3x2 + 15x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 9   0 ≤ x1,x2,x3 ≤ 5

24

5x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 9     6x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

25

3x1 + 5x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 9     6x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

26

3x1 + 3x2 + 15x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 9     6x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

27

3x1 + 3x2 + 13x3  ->  max

-5x1 + 6x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 9   0 ≤ x1,x2,x3 ≤ 5

28

3x1 + 3x2 + 13x3  ->  max

-3x1 + 8x2 + 7x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 9   0 ≤ x1,x2,x3 ≤ 5

29

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 9x3 ≤ 8     6x1 – 3x2 + 7x3 ≤ 9   0 ≤ x1,x2,x3 ≤ 5

30

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 9     8x1 – 3x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

31

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 9     6x1 – 5x2 + 7x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

32

3x1 + 3x2 + 13x3  ->  max

-3x1 + 6x2 + 7x3 ≤ 9     6x1 – 3x2 + 9x3 ≤ 8   0 ≤ x1,x2,x3 ≤ 5

Похожие материалы

Информация о работе