Решение задач линейного программирования. Решение целочисленной задачи методом Гомори

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

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

Фрагмент текста работы

Типовой расчет

Задание 1. Решить задачу линейного программирования:  a) графически, b) симплекс-методом.

1. f(x) = 2x1 + 4x2 ® max

   

2. f(x) = x1 + x2 ® max

     

3. f(x) = 3x1 + 2x2 ® max

     

4. f(x) = 2x1 + 5x2 ® max

   

5. f(x) = 4x1 + 5x2 ® max

     

6. f(x) = 2x1 - 3x2 ® max

     

7. f(x) = x1 - x2 ® max

   

8. f(x) = 6x1 + 5x2 ® max

   

9. f(x) = 2x1 + 4x2 ® max

   

10. f(x) = 5x1 + 4x2 ® max

   

11. f(x) = 2x1 + x2 ® max

     

12. f(x) = x1 + 3x2 ® max

     

13. f(x) = 7x1 + 4x2 ® max

   

14. f(x) = 2x1 - x2 ® max

     

15. f(x) = 2x1 - x2 ® max

     

16. f(x) = 3x1 + 4x2 ® max

   

17. f(x) = x1 - x2 ® max

     

18. f(x) = 5x1 + 6x2 ® max

     

19. f(x) = 3x1 - x2 ® max

   

20. f(x) = x1 + x2 ® max

     

21. f(x) = 4x1 + x2 ® max

     

22. f(x) = 2x1 - x2 ® max

   

23. f(x) = 2x1 +3x2 ® max

   

24. f(x) = x1 - x2 ® max

   

25. f(x) = 3x1 - 2x2 ® max

   

26. f(x) = 5x1 + 3x2 ® max

   

27. f(x) = 2x1 + 7x2 ® max

   

28. f(x) = 3x1 + 5x2 ® max

   

29. f(x) = 4x1 + 3x2 ® max

   

30. f(x) = 2x1 + 6x2 ® max

   

Задание 2. Решить задачу линейного программирования  симплекс-методом.

1. f(x) = x1 + x2 + x3 - x4 - 2x- 7 ® min

   

2. f(x) =21 x1 + 2x2 + 30x3  + x ® min

   

3. f(x) = 2x1 + x2 + x3 - x4 - 2x+ 12 ® min

   

4. f(x) =2 x1 + 2x2 + 3x3  + x ® min

   

5. f(x) = 2x1 + 4x2 + x3 - x4 - 5x+ 15® min

   

6. f(x) = x1 + 2x2 + 2x3  + x ® min

   

7. f(x) = x1 + 4x2 + 2x3 + 4x4 - 5x® min

   

8. f(x) = 5x1 + 2x2 + 5x3  + x ® min

   

9. f(x) = 10x1 + 4x2 + 2x3 + 4x4 - 5x ® min

   

10. f(x) = 4x1 + 2x2 + 3x3  + 2x ® min

   

11. f(x) = x1 + 4x2 + 2x3 - 2x4 - x- 10 ® min

   

12. f(x) = 3x1 + 2x2 + 8x3  + x ® min

   

13. f(x) = x1 + 4x2 + 2x3 + 2x4 + x+ 2 ® min

   

14. f(x) = 4x1 + 2x2 + 3x3  + 5x ® min

   

15. f(x) = x1 + 7x2 + 2x3 + x4 + 4x- 5 ® min

   

16. f(x) = 7x1 + 2x2 - 3x3  + 5x ® min

   

17. f(x) = x1 + 2x2 + 2x3 + 9x4 + 4x ® min

   

18. f(x) = x1 + 2x2 - 3x3  + x ® min

   

19. f(x) = 5x1 + 7x2 + 9x3 + x4 + x+ 1 ® min

    

20. f(x) = 2x1 + 2x2 - 2x3  + x ® min

   

21. f(x) = 3x1 + 2x2 + x3 + x4 + x5  + 4 ® min

    

22. f(x) = 8x1 + 2x2 - 2x3  + 5x ® min

   

23. f(x) = 4x1 + 2x2 + 3x3 + x4 + x+ 1 ® min

    

24. f(x) = 4x1 + 2x2 - 2x3  + 3x ® min

   

25. f(x) = 9x1 + 2x2 + 3x3 + 2x4 + x® min

    

26. f(x) = - x1 + 2x2 - 2x3  + 3x ® min

   

27. f(x) = 2x1 + 2x2 + 3x3 + 5x4 + x5  ® min

    

28. f(x) = - 4x1 + 2x2 - 2x3  + 7x ® min

   

29. f(x) = 21x1 + 2x2 + 30x3 + 5x4 + x® min

    

30. f(x) = - 5x1 + 7x2 - 5x3  + 8x ® min

   

Задание 3. Решить задачу линейного программирования симплекс-методом, составить двойственную задачу и найти ее решение.

1. f(x) = 5x1 + 3x2 + 2x3  ® mах

   

2. f(x) = 4x1 + 5x2 + 4x3  ® mах

      

3. f(x) = 6x1 + 4x2 + x3 ® mах

   

4. f(x) = 6x1 - 5x2 + 4x3  ® mах

      

5 f(x) = 2x1 + 4x2 - x3 ® mах

  

6. f(x) = 3x1 - 5x2 + 4x3  ® mах

      

7. f(x) = 5x1 + 4x2 - 2x3 ® mах

   

8. f(x) = 5x1 - 5x2 + 6x3  ® mах

      

9. f(x) = x1 - 2x2 + 2x3 ® mах

   

10. f(x) = 9x1 - 5x2 + 8x3  ® mах

      

11. f(x) = 5x1 - 5x2 + 6x3 ® mах

   

12. f(x) = x1 - 5x2 + x3  ® mах

     

13. f(x) = -5x1 + 7x2 + 6x3 ® mах

   

14. f(x) = x2 + x3  ® mах

     

15. f(x) = -3x1 + 5x2 + 6x3 ® mах

   

16. f(x) = 10x1 - 3x2 + 2x3  ® mах

     

17. f(x) = - x1 + x2 + 2x3 ® mах

    

18. f(x) = x1 - 3x2 + 2x3  ® mах

     

19. f(x) = - x1 + 3x2 + 2x3 ® mах

      

20. f(x) = 7x1 - 3x2 + 8x3  ® mах

     

21. f(x) = - 7x1 + 8x2 + 7x3 ® mах

      

22. f(x) = 4x1 - x2 + 4x3  ® mах

     

23. f(x) = - 9x1 + 5x2 + 4x3 ® mах

      

24. f(x) = 2x1 - x2 + 5x3  ® mах

     

25. f(x) = - 4x1 + 8x2 + 7x3 ® mах

      

26. f(x) = 2x1 - 5x2 + 3x3  ® mах

     

27.  f(x) = 4x1 + 5x2 + 7x3 ® mах

      

28. f(x) = 2x1 + 8x2 + 3x3  ® mах

     

29. f(x) = 5x1 + 5x2 + 6x3 ® mах

      

30. f(x) = 5x1 + 4x2 + 3x3  ® mах

     

Задание 4. Решить целочисленную задачу методом Гомори.

1. f(x) = 3x1 + 4x2 ® max

   

2. f(x) = 7x1 + x2 ® max

     

3. f(x) = 3x1 + 2x2 ® max

     

4. f(x) = 2x1 + 15x2 ® max

   

5. f(x) = 4x1 + 5x2 ® max

     

6. f(x) = 2x1 - 3x2 ® max

     

7. f(x) = 9x1 + 7x2 ® max

   

8. f(x) = 7x1 + 10x2 ® max

     

9. f(x) = x1 + 3x2 ® max

     

10. f(x) = 5x1 + 4x2 ® max

   

11. f(x) = x1 + 2x2 ® max

     

12. f(x) = 2x1 - x2 ® max

     

13. f(x) = 3x1 + 2x2 ® max

   

14. f(x) = x1 - x2 ® max

     

15. f(x) = 7x1 + 6x2 ® max

     

16. f(x) = 3x1 - x2 ® max

   

17. f(x) = 2x1 + x2 ® max

     

18. f(x) = 4x1 + x2 ® max

     

19. f(x) = 4x1 - x2 ® max

   

20. f(x) = 2x1 +9x2 ® max

   

21. f(x) = x1 - x2 ® max

   

22. f(x) = 3x1 - 2x2 ® max

   

23. f(x) = 5x1 + 3x2 ® max

   

24. f(x) = 11x1 + 7x2 ® max

   

25. f(x) = 3x1 + 5x2 ® max

   

26. f(x) = 4x1 + 3x2 ® max

   

27. f(x) = 2x1 + 6x2 ® max

   

28. f(x) = 9x1 + 5x2 ® max

   

29. f(x) = 9x1 + 5x2 ® max

   

30. f(x) = 5x1 + 4x2 ® max

   

Задание 5. Решить транспортную задачу.

В 1

В 2

 

B1

B2

B3

B4

B1

B2

B3

B4

A1

1

8

2

10

190

A1

2

2

5

1

140

A2

20

21

7

8

120

A2

1

8

11

1

190

A3

7

11

5

9

240

A3

9

8

7

2

230

210

120

170

50

120

210

190

40

В 3

В 4

B1

B2

B3

B4

B1

B2

B3

B4

A1

3

3

3

2

200

A1

4

3

2

5

250

A2

1

7

5

11

180

A2

22

2

5

8

130

A3

4

3

9

3

190

A3

10

16

22

3

230

130

230

80

130

70

230

240

70

В 5

В 6

B1

B2

B3

B4

B1

B2

B3

B4

A1

5

1

1

2

25

A1

6

3

14

10

25

A2

7

2

4

3

13

A2

3

15

4

5

13

A3

4

7

2

4

23

A3

8

11

5

2

25

7

23

24

7

16

20

20

7

В 7

В 8

B1

B2

B3

B4

B1

B2

B3

B4

A1

7

12

5

9

50

A1

8

10

5

11

10

A2

4

2

9

21

30

A2

7

6

4

5

30

A3

12

3

4

7

35

A3

7

2

8

2

35

15

25

25

50

5

30

20

20

В 9

В 10

B1

B2

B3

B4

B1

B2

B3

B4

A1

9

15

10

1

10

A1

10

8

12

18

20

A2

3

8

3

2

30

A2

23

1

4

25

20

A3

6

2

5

8

25

A3

25

18

4

6

25

15

10

15

25

15

20

10

20

В 11

В 12

B1

B2

B3

B4

B1

B2

B3

B4

A1

11

9

4

4

30

A1

12

18

23

14

15

A2

5

7

10

5

10

A2

4

5

3

16

25

A3

3

5

4

6

65

A3

11

8

17

4

35

30

10

5

60

25

20

15

15

В 13

В 14

 

B1

B2

B3

B4

B1

B2

B3

B4

A1

13

8

20

10

10

A1

14

10

25

10

45

A2

22

2

7

8

12

A2

12

8

11

15

95

A3

7

11

5

9

24

A3

9

8

7

12

23

21

5

15

5

33

50

35

45

В 15

В 16

B1

B2

B3

B4

B1

B2

B3

B4

A1

15

11

3

22

20

A1

10

3

2

5

45

A2

10

10

5

11

80

A2

2

2

5

8

100

A3

14

22

11

22

90

A3

10

6

2

3

55

35

20

85

50

45

60

50

45

В 17

В 18

B1

B2

B3

B4

B1

B2

B3

B4

A1

17

15

10

11

10

A1

18

8

12

18

20

A2

9

8

14

12

30

A2

9

16

4

5

20

A3

6

12

15

8

25

A3

25

18

14

6

25

15

10

15

25

15

20

10

20

В 19

В 20

B1

B2

B3

B4

B1

B2

B3

B4

A1

19

9

6

7

30

A1

20

18

23

14

25

A2

5

7

10

9

20

A2

14

5

12

16

25

A3

8

5

8

6

65

A3

11

8

17

14

35

30

10

15

60

25

20

25

15

В 21

В 22

 

B1

B2

B3

B4

B1

B2

B3

B4

A1

21

8

9

10

30

A1

22

10

15

10

45

A2

11

2

7

8

12

A2

12

8

11

15

95

A3

7

12

5

9

24

A3

9

8

17

12

50

21

15

15

15

40

60

35

55

В 23

В 24

B1

B2

B3

B4

B1

B2

B3

B4

A1

23

11

14

22

50

A1

24

3

12

5

40

A2

10

10

15

11

80

A2

2

12

5

8

100

A3

14

22

11

12

90

A3

10

6

2

3

60

35

50

85

50

40

60

50

50

В 25

В 26

B1

B2

B3

B4

B1

B2

B3

B4

A1

25

15

10

1

30

A1

26

8

12

18

40

A2

3

8

3

2

30

A2

23

12

4

25

20

A3

6

2

5

8

25

A3

25

18

4

6

25

15

20

25

25

25

20

20

20

В 27

В 28

B1

B2

B3

B4

B1

B2

B3

B4

A1

27

9

4

4

30

A1

28

8

23

4

45

A2

5

7

10

5

30

A2

4

5

3

6

25

A3

3

5

4

6

65

A3

11

8

7

4

35

30

10

25

60

25

20

25

35

В 29

В 30

 

B1

B2

B3

B4

B1

B2

B3

B4

A1

29

8

10

10

30

A1

30

10

5

10

45

A2

12

2

7

8

42

A2

12

8

11

5

85

A3

7

11

5

9

24

A3

9

8

7

12

23

21

25

15

35

33

40

35

45

Задание 6. Дана платежная матрица игры. Найти седловые точки и оптимальные стратегии игроков.

1.

9

8

10

10

2.

2

8

10

10

12

2

7

8

1

2

7

8

7

7

5

9

0

1

5

9

3.

12

8

8

10

4.

9

8

10

5

12

2

7

8

12

2

7

4

7

11

5

9

7

11

5

0

5.

4

6

0

3

6.

9

8

1

6

1

7

7

8

2

2

7

5

7

7

8

9

7

11

8

6

7.

6

8

5

10

8.

19

18

10

10

12

7

7

8

12

2

7

8

7

11

5

9

7

11

5

9

9.

5

7

1

1

10.

20

8

6

8

12

7

7

8

12

2

3

8

7

1

5

9

7

11

5

9

11.

6

8

4

9

12.

21

8

9

5

12

2

3

8

12

2

7

5

7

11

3

9

7

7

5

4

13.

7

8

9

10

14.

22

18

17

10

7

9

7

8

12

2

27

8

7

11

5

9

17

11

5

9

15.

8

8

10

10

16.

23

18

10

10

12

8

7

8

12

12

1

18

7

6

5

9

7

11

5

9

17.

9

8

6

5

18.

24

8

3

2

2

2

7

4

12

2

3

8

7

1

5

0

12

14

3

3

19.

10

10

10

10

20.

25

28

100

10

12

10

17

18

12

2

10

8

17

11

15

19

70

10

5

9

21.

11

8

11

11

22.

26

18

16

9

12

2

7

8

12

2

7

8

17

11

15

11

10

11

12

9

23.

12

18

18

12

24.

27

12

14

10

12

2

7

8

12

12

17

18

7

11

12

9

7

11

5

12

25.

13

8

5

4

26.

28

7

4

5

4

2

3

2

12

2

4

8

7

4

5

3

7

11

5

9

27.

14

10

10

12

28.

29

28

20

20

12

2

1

8

12

20

7

8

7

11

5

10

20

11

5

9

29.

15

7

1

1

30.

30

15

5

40

12

6

6

8

12

9

7

8

17

1

5

6

10

11

9

9

Задание 7. Дана платежная матрица игры. Решить графически игру.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.

30.

Задание 8. Дана платежная матрица игры. Найти решение  игры путем сведения ее к задаче линейного программирования.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

27.

29.

30.

Примеры решения  заданий

Задачи линейного программирования

Пример 1. Решить ЗЛП                  f(x) = 3x1 + 2x2 ® max

x1 + x2 £ 4,

 2x1 + x2 £ 6,

   x1 ³ 0, x2 ³ 0,

a) графически,  b) симплекс-методом.

a) Шаг 1. Строится множество D допустимых решений  задачи, оно представляет собой  четырехугольник ОABC на плоскости x1О x2 с вершинами в точках О, А, В, С,  с координатами (0; 0), (0; 4), (2; 2), (3; 0), соответственно.

Шаг 2. Из начала координат откладывается вектор-градиент функции f(x), указывающий направления ее возрастания.

Шаг 3. Строится прямая 3x1 + 2x= const  – линия уровня функции f(x), перпендикулярная вектору градиента .

Шаг 4. Линия уровня 3x1 + 2x= const  передвигается в направлении вектора до тех пор, пока она не покинет область D. Крайняя точка области, в которой линия уровня покидает допустимую область, и является решением задачи. В данном случае – это точка В(2; 2).

Шаг 5.Находится оптимальное значение функции.

f *(2; 2) =3x1 + 2x2 = 3 × 2 + 2 × 2 = 10.

b) Шаг 1. Задача приводится к специальному виду, для этого к левым частям неравенств прибавляются дополнительные переменные x3 и x4, превращающие неравенства в равенства.

         f(x) =3x1 + 2x2 ® max

x1 + x2 + x3 = 4,

2x1+ x2 + x4 = 6,

    xj ³ 0,

Переменные x3 и x4 входят в первое и второе уравнения соответственно с коэффициентами единица, тогда х3 , х– начальный базис,  x1 , x– свободные переменные, b  – вектор ограничений.

   Шаг 2. Составляется соответствующая симплекс - таблица:

базис

свободные

Отноше-

ние

x1

x2

b

x3

1

1

4

   4

x4

2

1

6

   3 Ü min

f(x)

-3

-2

0

Ýmin

Так как свободные переменные всегда равны нулю, то для данного начального базиса f(x) будет равна нулю:

f(x) = с0 - åci хi = 0 × 2 + 0 × 6 = 0.

Так как имеются сj < 0, приступаем к улучшению плана.

   Шаг 3. Выбирается разрешающий j-й столбец, соответствующий наименьшему отрицательному сj.

         Шаг 4. Разрешающую строку определяют следующим образом: рассчитываются так называемые симплексные отношения, т. е. отношения текущих значений базисных переменных к положительным  коэффициентам разрешающего столбца, соответствующим данным базисным переменным. Затем берется минимальное из этих отношений и по тому, какой строке оно соответствует, определяется ведущая строка.

         Шаг 5.  Находится разрешающий элемент, он расположен на пересечении разрешающей строки и разрешающего столбца (в нашем случае он равен 2).

         Шаг 6.  Определяются переменные, которые будут исключены из базиса и включены в него. Переменную, которой соответствует разрешающий столбец, включаются в базис вместо переменной, которой соответствует разрешающая строка.  В базис вводим переменную x1, которому соответствует минимальное значение cj. Из базиса выводится x4, так как минимальное q достигается в этой строке формулой  .

 Таким образом, элемент a41 будет разрешающим (в таблице выделен серым цветом).

Шаг 7. Заполняем таблицу, соответствующую новому базисному решению.

свободные

q

базис

х4

х2

b

х3

- 0,5

0,5

1

0,5 / 1Ü min

х1

0,5

0,5

3

 0,5 / 3

f(x)

1,5

- 0,5

9

Ýmin 

 Шаг 8.  Так как в строке f(x) оценок полученного нового плана имеется отрицательное значение сj , приступаем к следующей итерации, продолжая улучшать план.

б\с

x4

x3

b

x2

2

x1

2

f(x)

1

1

10

  Поскольку все сj ³ 0, то план, представленный в данной таблице, будет оптимальным.

Ответ:  f *(x) =10; x1* = 0; x2*= 6

Пример 2.  Решить каноническую задачу линейного программирования:

         f(Х) = х1 - 2х2 - 2x3 ® max

                                                      x1 + 4x2 + x3 = 5,

                                                      x1 - 2x2 - x3 = -1,          

                                                       xj ³ 0,

Данная каноническая задача линейного программирования (КЗЛП) не является специальной (СЗЛП), поэтому применяем метод искусственного базиса.  Строим вспомогательную задачу линейного программирования и приводим ее к специальному виду,  выражая целевую функцию через небазисные переменныеxj ,  j=1,…,3. Эта задача имеет вид:

h(Х) = – ( t1+ t2) =  – 6 + 6 x2 + 2 x3 ® max

                                x1 + 4x2 + x3 + t1 = 5,

 x1 - 2x2 - x3 + t2 = -1,

                                                       все  xj  ≥ 0, ti  ≥ 0.

Решаем специальную задачу линейного программирования симплекс-методом:

б\с

x1

x2

x3

b

б\с

x1

x2

t2

b

б\с

t1

x2

t2

b

t1

1

4

1

5

t1

2

2

-1

4

¬

x1

0.5

1

-0,5

2

t2

-1

2

1

1

¬

x3

-1

2

1

1

x3

0,5

3

0,5

3

h

0

-6

-2

-6

h

-2

-2

2

-4

h

1

0

1

0

­

­

f

-1

2

2

0

f

1

-2

2

-2

f

-0,5

-3

5/2

-4

Так как max h = 0, то множество Х допустимых решений КЗЛП не пусто, т. е.

Х ¹ Æ, поэтому существует СЗЛП, эквивалентная данной КЗЛП. Эта задача имеет вид:f(Х) = - 4 + 3х2 ® max            

 x1 + x2  = 2,

 3x2 + x3 = 3,

                                                         все  xj  ≥ 0.

Линейные уравнения этой системы и f(Х)  получены из завершающей симплекс-таблицы вспомогательной задачи.

Решаем специальную задачу линейного программирования симплекс-методом:

б\с

х2

b

б\с

х3

b

х1

1

2

х1

-1/3

1

х3

3

3

¬

х2

1/3

1

f

-3

-4

f

1

-1

­

Отсюда оптимальный план Х*(1; 1; 0), fmax = -1.

Пример 3. Решить задачу линейного программирования симплекс-методом, составить двойственную задачу и найти ее решение.

            Z = 6x1 + 5 x2 + 4x3 + 3x4 ® max

2x1+ 3x2 + 2x3 + x4 £ 25,

4x1 + x2 + 3x3 + 2x4 £ 30,

  3x1 +5 x2 + 2x3 + 2x4 £ 42,

                                                    все  xj  ≥ 0.

Математическая модель

прямой задачи

Z = 6x1 + 5x2 + 4x3 + 3x4 ® max

2x1 + 3x2 + 2x3 + x4 £ 25,

4x1 + x2 + 3x3 +2x4 £ 30,

3x1 + 5x2 + 2x3 + 2x4 £ 42,

x1≥ 0,

x2≥ 0,

x3≥ 0,

x4≥ 0.

Математическая модель

двойственной задачи

f = 25y1+ 30y2 + 42y3 ® min

y1 ≥ 0,

y2 ≥ 0,

y3 ≥ 0,

2y1 + 4y2 + 3y≥ 6,

3y1 + y2 + 5y≥ 5,

2y1 + 3y2 + 2y≥ 4,

y1 + 2y2 + 2y3 ≥ 3.

Специальный вид

Z= 6x1+5x2+4x3+3x4 ® max

         2x1+3x2+2x3+x4+S1=25,

4x1+x2+3x3+2x4+S2=30,

 3x1+5x2+2x3+2x4+S3=42,

   x1, x2, x3, x4, S1, S2, S3 ≥ 0

S2

x2

x3

x4

b

 

S1

-0,5

2,5

0,5

0

10

4

 

x1

0,25

0,25

0,75

0,5

7,5

30

 

S3

-0,75

4,25

-0,25

0,5

19,5

4,58

 

Z

1,5

-3,5

0,5

0

45

 

­

 
 

x1

x2

x3

x4

b

S2

x2

x3

x4

b

 

S1

2

3

2

1

25

12,5

x2

4

 

S2

4

1

3

2

30

7,5

x1

6,5

 

S3

3

5

2

2

42

14

S3

2,5

 

Z

-6

-5

-4

-3

0

Z

0,8

1,4

1,2

0

59

 

­

Х*(6.5, 4, 0, 0),    Z*=59.

Решение двойственной  задачи можно найти с помощью второй теоремы двойственности:

 (2x1+ 3x2 + 2x3 + x4 - 25) у1 = 0 Þ(2 • 6,5 + 3 • 4 - 25) у1 = 0 Þ 0 = 0,

(4x1+ x2 + 3x3 + 2x4 - 30) у2 = 0 Þ (4 • 6,5 + 4 - 30) у2 = 0 Þ 0 = 0,

(3x1 + 5x2 + 2x3 + 2x4 – 42) у3 = 0 Þ (3 • 6,5 + 5 • 4 - 42) у3 = 0Þ

Þ -2,5у3 = 0 Þ у3 = 0,

(2y1 + 4y2 + 3y3 – 6) х1 = 0 Þ (2y1 + 4y2 + 3y3 –6) 6,5 = 0 Þ (2y1 + 4y2 +3y3 – 6 = 0),

(3y1 + y2 + 5y3 – 5) х2 = 0 Þ (3y1 + y2 + 5y3 – 5) 4 = 0 Þ (3y1 + y2 + 5y3 – 5 = 0),

(2y1 + 3y2 + 2y3 – 4) х3 = 0 Þ (2y1 + 3y2 + 2y3 – 4) 0 = 0 Þ 0 = 0,

(y1 + 2y2 + 2y3 – 3) х4 = 0 Þ 0 = 0.

Решая систему  у3 = 0;  2y1 + 4y2 + 3y3 – 6 = 0; 3y1 + y2 + 5y3 – 5 = 0,

находим у1 = 1,4;  у2 = 0,8;  у3 = 0;    f * = 25 • 1,4 + 30 • 0,8 + 42 • 0 = 59.

Пример 4. Решить целочисленную задачу линейного программирования методом Гомори.                                      f(Х) =2х12® max            

                                 2x1 + x3  =3,

                                                     2х1+ 3x2 +x4 =6,          

                                                      все  xj  ≥ 0.

Сначала находится решение задачи симплекс-методом.

б\с

x1

x2

b

б\с

x3

x2

b

б\с

x3

x4

b

x3

2

0

3

¬

x1

1/2

0

3/2

x1

1/2

0

3/2

x4

2

3

6

x4

-1

3

3

¬

x2

-1/3

1/3

1

f

-2

-1

0

f

1

-1

3

f

2/3

1/3

4

­

­

Х*нц (3/2; 1; 0; 0).

Переменная х1 – дробная. Строим по строке х1 отсечение:

{1/2} x3 + {0} x4 ≥ {3/2}, т. е. x3  ≥ 1.

Здесь дробная часть числа а находится по формуле {а} = а – [a], где [a] – целая часть числа а.       

{1/2} = 1/2 - 0, {0} = 0, {3/2} = 3/2 – 1 = 1/2.

Из последней таблицы

                     f(Х) =4 - 2/3 х3 - 1/3 х® max

                                  1/2 x3 + x1  = 3/2,

                                                      -1/3 х3 + 1/3 x4 + x2 =1,         

                                                       все  xj  ≥ 0.

Составляем задачу с дополнительным ограничением:

      f(Х) =4 - 2/3 х3 - 1/3 х4 ® max

                          1/2 x3 + x1  = 3/2,

                                              -1/3 х3 + 1/3 x4 + x2 = 1,         

                                               х3 - х5 = 1,

                                               все  xj  ≥ 0.

Полученную задачу решаем М-методом:

F(X) = 4 - 2/3 х3 - 1/3 х4 – M t1 = 4 - 2/3 х3 - 1/3 х4 + M (-1 + x3 - x5) ® max

                          1/2 x3 + x1  = 3/2,

                                              -1/3 х3 + 1/3 x4 + x2 = 1,         

                                               х3 - х5 + t1 = 1,

                                               t1 ≥ 0, все  xj  ≥ 0.

б\с

x3

x4

x5

b

б\с

t1

x4

x5

b

x1

1/2

0

0

3/2

x1

-1/2

0

1/2

1

x2

-1/3

1/3

0

1

x2

1/3

1/3

-1/3

4/3

t1

1

0

-1

1

¬

x3

1

0

-1

1

f

2/3

1/3

0

4

f

-2/3

1/3

2/3

10/3

M

-1

0

1

-1

M

1

0

0

0

­

х2 = 4/3, требуется еще итерация. Из последней симплекс-таблицы

        f(Х) =10/3 - 1/3 х4 - 2/3 x5 ® max

                                                 х1 + 1/2 х5 = 1,

 х2 + 1/3 х- 1/3 х5 = 4/3,

                                                 - х5 + х3 = 1,

                                                {1/3} х4 + {-1/3} х≥ {4/3},

                                                 все  xj  ≥ 0.

{-1/3} = - 1/3 – (-1) = 2/3, {4/3} = 4/3 – 1 = 1/3.

Получаем каноническую задачу линейного программирования :

        f(Х) =10/3 - 1/3 х4 - 2/3 x5 ® max

                                                 х1 + 1/2 х5 = 1,

 х2 + 1/3 х- 1/3 х5 = 4/3,

                                                 - х5 + х3 = 1,

                                                 х4 + 2х5 - х6 = 1,

                                                 все  xj  ≥ 0.

Применяем М-метод.

                                F(Х) =10/3 -1/3 х4 - 2/3 x5 – M (1 - (х4 + 2х- х6)) ® max

х1 + 1/2 х5 = 1;    х2 + 1/3 х- 1/3 х5 = 4/3;  - х5 + х3 = 1;    х4 + 2х5 - х6 + t = 1;

                                                 t ≥ 0, все  xj  ≥ 0.

б\с

x4

x5

x6

b

б\с

t

x5

x6

b

x1

0

½

0

1

x1

1

x2

1/3

-1/3

0

4/3

x2

1

х3

0

-1

0

1

х3

1

t

1

2

-1

1

¬

x4

1

f

1/3

2/3

0

10/3

f

0

1/3

3

M

-1

-2

1

-1

M

0

0

0

­

Оптимальное целочисленное решение Х*ц (1,1,1,1).

Пример 5. Решить транспортную задачу.

Поставщики

Потребители

Запасы

В1

В2

В3

В4

А1

2

3

2

4

30

А2

3

2

5

1

40

А3

4

3

2

6

20

Потребности

20

30

30

10

90

Шаг 1. (Нахождение опорного плана перевозок методом минимального элемента.)  В  матрице стоимостей  перевозок находится наименьший элемент, это    Находится  количество единиц перевозимого груза

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

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

Тип:
Типовые расчеты
Размер файла:
1 Mb
Скачали:
0