Симплексный метод решения задачи ЛП

1. СИМПЛЕКСНЫЙ МЕТОД решения (анализа) задачи ЛП

1.ПРИМЕР ИСХОДНОЙ ЗАДАЧИ ЛП
2.КАНОНИЧЕСКАЯ ФОРМА ЗАДАЧИ
3.МАТРИЧНАЯ ФОРМА ЗАПИСИ ЗАДАЧИ
4.БАЗИСНАЯ ФОРМА ЗАДАЧИ
5.СИМПЛЕКСНАЯ ТАБЛИЦА
6.ОЦЕНКИ НЕБАЗИСНЫХ ПЕРЕМЕННЫХ
7.ПРЕОБРАЗОВАНИЕ СИМПЛЕКСНОЙ ТАБЛИЦЫ
8.ОПТИМАЛЬНАЯ ТАБЛИЦА
9.АНАЛИЗ КОНЕЧНОЙ ТАБЛИЦЫ

2. 1. Пример исходной задачи ЛП

min 5 x1 8 x2
6 x1 7 x2 420
x1 2 x2 80
3 x1 4 x2 300
x 0.

3. 2. Каноническая форма задачи ЛП СТАНДАРТНАЯ

max 5 x1 8 x2
6 x1 7 x2 x3 420
x1 2 x2 x4 80
3 x1 4 x2 x5 300
x 0.

4. Приведение к стандартному виду ограничения типа «  »

Приведение к стандартному виду
ограничения типа «
Пример ограничения на уровень
выручки:
7 x1 11x 2 255.
7 x1 11x 2 x3 255, x3 0,
x3 255 7 x1 11x 2 .
»

5. 3. Матричная форма записи задачи

A aij m n
max cx ,
Ax b,
x 0.
c c1
m 3, n 5
c2
c3
c4
c5 5 8 0 0 0 ,
6 7 1 0 0
x1
420
A 1 2 0 1 0 , x , b 80 .
3 4 0 0 1
x
300
5

6. 5. БАЗИСНАЯ ФОРМА ЗАДАЧИ ЛП ПРЕДПОЧИТАЕМАЯ, СИМПЛЕКСНАЯ опорный план

5. БАЗИСНАЯ
ФОРМА ЗАДАЧИ ЛП
ПРЕДПОЧИТАЕМАЯ, СИМПЛЕКСНАЯ
max 5 x1 8 x 2
x3 420 6 x1 7 x 2
x 4 80 x1 2 x 2
x5 300 3 x1 4 x 2
L =
0
– (– 5x1 – 8x2)
опорный план
x1 0
x2 0
x3 420
x4 80
x 300
5
L=0

7. СИМПЛЕКСНОЕ ОТНОШЕНИЕ ДЛЯ НОВОЙ БАЗИСНОЙ ПЕРЕМЕННОЙ x2

max 5 x1 8 x 2
x3 420 6 x1 7 x 2
x 4 80 x1 2 x 2
x5 300 3 x1 4 x 2
420
θ1
60
7
80
θ2
40
2
300
θ3
75
4

8. Решение разрешающего уравнения относительно x2

Решение разрешающего уравнения
x 4 80 x1 2 x 2
относительно x2
1
1
x 2 40 x1 x 4
2
2

9. 5. СИМПЛЕКСНАЯ ТАБЛИЦА с е д и н и ч н о й м а т р и ц е й

5.
СИМПЛЕКСНАЯ ТАБЛИЦА
с е д и н и ч н о й
Б А З ИС
м а т р и ц е й
x1
x2
x3
x4
x5
x3
420
6
7
1
0
0
x4
80
1
2
0
1
0
x5
300
3
4
0
0
1
L
0
5
8
0
0
0

10. 5а. с о к р а щ е н н а я СИМПЛЕКСНАЯ ТАБЛИЦА

5а.
с
о
к
р
а
щ
x1 x2
е
н
н
а
я
СИМПЛЕКСНАЯ ТАБЛИЦА
Б А З ИС
x3
420
6
7
x4
80
1
2
x5
300
3
4
f
0
5
8

11. 6. ОЦЕНКИ НЕБАЗИСНЫХ ПЕРЕМЕННЫХ

Оценка
Δi небазисной переменной xi
численно равна величине приращения текущего
значения критерия, соответствующее
единичному приращению данной переменной:
ΔL = Δi ~ Δxi=+1.
В строке критерия оценки указаны
с обратным знаком !

12. Небазисная переменная, оценка которой положительна, называется перспективной

13. Если текущий опорный план содержит перспективные переменные, то его можно улучшить путем включения в базис любой из имеющихся перспективн

Если текущий опорный план
содержит перспективные
переменные, то его можно
улучшить путем включения в
базис любой из имеющихся
перспективных переменных.

14. 7.1. Преобразование СИМПЛЕКСНОЙ ТАБЛИЦЫ выбираем новую базисную переменную x2 Δ1= +5, Δ2= +8

Б А З ИС
x1
x2
x3
x4
x5
x3
420
6
7
1
0
0
x4
80
1
2
0
1
0
x5
300
3
4
0
0
1
L
0
5
8
0
0
0
Θ

15. 7.2. Преобразование СИМПЛЕКСНОЙ ТАБЛИЦЫ нахождение разрешающей строки

Б А З ИС
x1
x2
x3
x4
x5
Θ
x3
420
6
7
1
0
0
60
x4
80
1
2
0
1
0
40
x5
300
3
4
0
0
1
75
L
0
5
8
0
0
0

16. Величина симплексного отношения указывает максимально возможное значение новой базисной переменной, « разрешенное » соответствующим ура

Величина симплексного отношения
указывает максимально возможное
значение новой базисной переменной,
разрешенное
«
»
соответствующим уравнением.
Симплексное отношение для строки
(уравнения) не существует, если в
разрешающем столбце этой строки
находится нуль или отрицательное
число.

17. Признак неограниченности критерия

Если получена очередная
таблица, для которой не
найдено ни одного
симплексного отношения,
решение задачи ЛП не
существует по причине
неограниченности критерия.

18. 7.1-2. Разрешающий элемент

7.1-2.
Б А З ИС
Разрешающий элемент
x1
x2
x3
x4
x5
Θ
x3
420
6
7
1
0
0
70
x4
80
1
2
0
1
0
40
x5
300
3
4
0
0
1
75
L
0
5
8
0
0
0

19. 7.3. Преобразование разрешающей строки производится путем ее деления на разрешающий элемент x2 = 40  (0,5 x1 + 0,5 x4)

7.3. Преобразование
разрешающей строки производится путем ее деления
на разрешающий элемент
x2 = 40 (0,5 x1 + 0,5 x4)
x1
x2
x3
x4
x5
40 0,5
1
0
0,5
0
Б А З ИС
x3
x2
x5
L
Θ

20. 7.4а. Преобразование остальных строк

Из преобразуемой строки
вычитается
преобразованная разрешающая
строка,
умноженная на элемент
разрешающего столбца
преобразуемой строки.

21. 7.4.б. Преобразование строки x3

x1
x2
x3
x4
x5
6
7
1
0
0
40 1/2
1
0
1/2
0
x2 7 280 3,5
7
0
3,5
0
Б А З ИС
x3
x2
x5
L
420
Θ

22. 7.4.в. Преобразована строка x3

7.4.в. Преобразована
x3
строка
Б А З ИС
x1
x2 x3
x4
x5
x3
140 2,5
0
1
3,5
0
x2
40 1/2
1
0
1/2
0
x5
L
Θ

23. 7.4.г. Преобразованы все строки

Б А З ИС
x1
x2 x3
x4
x5
Θ
x3
140 2,5
0
1
3,5
0
56
x2
40 1/2
1
0
1/2
0
80
0
0
2
1
140
0
0
4
0
x5
140
1
L
320 1

24. 8. ОПТИМАЛЬНАЯ ТАБЛИЦА

Б А З ИС
x1 x2
x3
x4
x5
x1
56
1
0
x2
12
0
1
0,2 1,2
0
x5
84
0
0
0,4 0,6
1
L*
376
0
0
0,4 1,4
0,4
2,6
0
0

25. 8.а. ОПТИМАЛЬНАЯ ТАБЛИЦА

Б А З ИС
x1 x2
x3
x4
x5
x1
56
1
0
x2
12
0
1
0,2 1,2
0
x5
84
0
0
0,4 0,6
1
L*
376
0
0
0,4 1,4
0,4
2,6
0
0

26. 8.а. ОПТИМАЛЬНАЯ ТАБЛИЦА

x3
x4
x1
56 0,4 1,4
x2
12 0,2 1,2
x5
84 0,4 0,6
L*
376
0,4
2,6

27. Базисная форма

x1 56 0,4 x3 1,4 x4
x2 12 0,2 x3 1,2 x4
x5 84 0,4 x3 0,6 x4
L 376 0,4 x3 2,6 x4

28. Базисная форма

x1 56
x3 1,4 x4
x2 12 0,2 x3 1,2 x4
x5 84 0,4 x3 0,6 x4
L 376 0,4 x3 2,6 x4

29. 8.а. ОПТИМАЛЬНАЯ ТАБЛИЦА

Б А З ИС
x1 x2
x3
x4
x5
Отн
по
x3
x1
56
1
0
x2
12
0
1
x5
84
0
0
L*
376
0
0
0
56
0,2 1,2
0
-60
0,4 0,6
1
-24
0
0
0,4 1,4
0,4
2,6

30. 8.б. ОПТИМАЛЬНАЯ ТАБЛИЦА

Б А З ИС
x1 x2
x3
x4
x5
Отн
по
x4
x1
56
1
0
x2
12
0
1
x5
84
0
0
L*
376
0
0
0
-40
0,2 1,2
0
10
0,4 0,6
1
-24
0
0
0,4 1,4
0,4
2,6

31. 9.а. Анализ конечной таблицы ПРИЗНАК ОПТИМАЛЬНОСТИ

Если все небазисные
переменные имеют
отрицательную оценку, то
текущий опорный план
оптимален.
В финальной таблице
имеем:
Δ3=- 0,4 < 0;
Δ4=-2,6 < 0.
56
12
*
x 0
0
84

32. 9.б. Анализ конечной таблицы ПРИЗНАК единственности оптимального плана

Если в оптимальном
опорном плане все
небазисные переменные
имеют ненулевую оценку,
то этот план является
ЕДИНСТВЕННЫМ
оптимальным.

33. 9.в. Анализ конечной таблицы ПРИЗНАК множества оптимальных планов

Если в оптимальном опорном
плане имеются небазисные
переменные с нулевой
оценкой, то существует
бесконечно много
оптимальных планов.

34. 9.г. Анализ оценки дополнительной переменной x3  остаток ресурса №1

9.г. Анализ оценки
дополнительной переменной
x3 остаток ресурса №1
Небазисная переменная x3* = 0.
Ее оценка Δ3 = 0,4.
Увеличение этой переменной, например
придание ей значения
x3 = 1,
соответствует уменьшению использования
ресурса. Из имеющихся 420 единиц будет
затрачено
420 1 = 419 единиц.

35. Оптимальное значение критерия при этом получит приращение ΔL =  0,4. и станет равным 376  0,4 = 375,6 Итак, при уменьшении использования ресурса н

Оптимальное значение критерия при этом
получит приращение
ΔL = 0,4.
и станет равным
376 0,4 = 375,6
Итак, при уменьшении использования
ресурса на единицу оптимальное
значение критерия уменьшится на 0,4.

36.

Напротив, увеличение использования этого
ресурса на 1, приведет к изменению
оптимального значения критерия на
ΔL = + 0,4.
Таким образом, оценка дополнительной
переменной первого ограничения, взятая с
обратным знаком, указывает численную
меру
чувствительности критерия
к изменению доступного запаса ресурса.
Эта величина называется
«двойственная оценка ресурса».

37. ТЕМА 1-ГО ПРАКТИЧЕСКОГО ЗАНЯТИЯ

«ГРАФИЧЕСКАЯ
МОДЕЛЬ
ЗАДАЧИ ЛП»