Симплексный метод

1. Глава 4. Симплексный метод

4.1. Графическая интерпретация

2. Пример

1
10
9
8
?
7
6
Оптимальный план
5
4
3
2
Множество
планов
1
1
2
3
4
5
6
7
8
9
10
2

3. Гипотезы

2
Гипотезы
3

4. Гипотезы

2
Гипотезы
В общем многомерном случае эти гипотезы нужно доказать!
4

5.

4.2. Свойства планов задачи ЛП

6.

Алгебраический подход
6

7. Свойство 1

1
Свойство 1
7

8. Свойство 2

2
Свойство 2
8

9. Опорные планы

3
Как найти крайнюю точку чисто алгебраическим способом?
Частные решения
системы ЛУ
Неотрицательные
частные решения
(планы)
С алгебраической точки зрения
решить задачу линейного
программирования – значит
найти
Оптимальный план
Базисные решения
Неотрицательные
базисные решения
(опорные планы)
1) неотрицательное
2) частное решение
системы линейных
уравнений,
3) дающее экстремум
целевой функции
9

10. Опорные планы

3
Пример
10
9
8
7
6
5
4
3
2
1
Гипотеза?
1
2
3
4
5
6
7
8
9
10
10

11. Свойство 3

4
Свойство 3
11

12. Свойство 3

4
Свойство 3
Достаточность самостоятельно
12

13. Общая схема решения задачи ЛП

5
Общая схема решения задачи ЛП
Пример
Чем плох этот метод?
13

14.

4.3. Теория симплексного метода

15. Общая идея – упорядочение перебора

1
Общая идея – упорядочение перебора
15

16. Ограничение перебора

2
Ограничение перебора
16

17. Ограничение перебора

2
Ограничение перебора
17

18. Ограничение перебора

2
Ограничение перебора
18

19. Ограничение перебора

2
Ограничение перебора
19

20. Ограничение перебора

2
Пример
20

21. Ограничение перебора

2
10
9
8
7
6
5
4
3
2
1
1
2
3
4
5
6
7
8
9
10
21

22. Направленность перебора

3
Направленность перебора
22

23. Направленность перебора

3
Направленность перебора
23

24. Направленность перебора

3
Направленность перебора
24

25. Направленность перебора

3
Направленность перебора
25

26. Критерий оптимальности

4
Критерий оптимальности
26

27. Критерий оптимальности

4
Критерий оптимальности
27

28. Критерий оптимальности

4
Критерий оптимальности
28

29. Критерий оптимальности

4
Критерий оптимальности
29

30. Критерий оптимальности

4
Критерий оптимальности
30

31. Критерий оптимальности

4
Критерий оптимальности
31

32. Схема симплексного метода

5
Схема симплексного метода
32

33. Схема симплексного метода

5
Схема симплексного метода
33

34. Иллюстрация в трехмерном пространстве

34

35.

4.4. Практический алгоритм
симплексного метода

36. Симплексная таблица

1
Симплексная таблица
36

37. Алгоритм

2
Алгоритм
37

38. Алгоритм

2
Алгоритм
38

39. Алгоритм

2
Алгоритм
39

40. Пример

3
Пример
Задача о производственном плане
Подготовительный этап
40

41. Пример

3
Пример
Итерация 1
41

42.

4.5. Метод искусственного базиса

43. Идея

1
Идея
Исходная задача
Расширенная задача
43

44. Пример

2
Пример
Расширенная задача
44

45. Пример

2
Пример
Первый этап
45

46. Пример

2
Пример
Первый этап
Второй этап
46