Симплекс-метод. Тема 4

ТЕМА 4. Симплекс-метод (СМ)
4.1 Ідея симплекс – методу
4.2 Перетворена задача
4.3 Спосіб переходу від одного ДБР до іншого
4.4 Умова оптимальності ДБР
4.5 Схема симплекс – методу
4.6 Збіжність симплекс – методу

Основні визначення та теореми ЛП
(з Теми 3)

Теорема про оптимальність вершини багатогранника

Базисні розв’язки
(Алгебраїчне представлення вершин)

Процедура знаходження базисних розв’язків (БР)

Допустимі базисні розв’язки (ДБР)

Теорема (ДБР=вершина)

4.1 Ідея симплекс-методу (СМ)

Принципова схема розв’язання ЗЛП
1. Знайти всі базисні розв’язки (БР).
2. Виділити серед них ДБР.
3. Обчислити для кожного ДБР відповідне значення ЦФ.
4. Порівняти значення ЦФ і визначити найкращий розв’язок.

Ідея СМ

Складові СМ
Cимплекс-метод базується на ідеї послідовного покращення розв’язку.
Для реалізації цієї ідеї метод повинен включати три основні складові:
1. Спосіб визначення початкового ДБР.
2. Критерій, по якому можна визначити оптимальність знайденого розв’язку або необхідність його подальшого покращення.
3. Правило переходу до наступного ДБР.

4.2 Перетворена задача

Перетворена задача
(5)

Перетворена задача

4.3 Спосіб переходу від одного ДБР до іншого

4.3.1 Спосіб переходу від одного ДБР до іншого на конкретному прикладі
ЗЛП (в СФ): ЗЛП в КФ:

Ця система є діагональною відносно змінних

Ця перетворена задача відповідає ДБР, у якого базисними є
За визначенням, небазисними є

4.3.2 Спосіб переходу від одного ДБР до іншого у загальному вигляді

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

При цьому розглянемо можливість того, що тільки одна небазисна змінна почне зростати, приймаючи додатні значення, в той час, як решта небазисних змінних залишиться нульовими
Перепишемо систему обмежень (5) перетвореної задачі по стовпцях:

і в новому ДБР маємо:
Якщо в нуль перетворюються одночасно дві або більш базисних змінних (маємо справу з виродженим випадком), вибрати ми повинні тільки одну з них.

Описаний спосіб переходу від одного ДБР до іншого називається операцією заміщення.

4.3.3 Часткові випадки, які виникають при операції заміщення

Базисні змінні приймають значення:
⇒

Базисні змінні приймають значення:
⇒

4.4 Умова оптимальності ДБР

Перетворена задача

Теорема «Умова оптимальності»
Перетворена задача

Доведення

Теорема «Умова оптимальності». Частина 2

;
;
;
.

Визначення.
ЗЛП називається не виродженою, якщо всі її ДБР не вироджені.

Теореми, що стосуються умов оптимальності (задача на максимум)

Теореми, що стосуються умов оптимальності (задача на мінімум)
≤
≤
≤

Розглянемо приклад до теореми (екз.):

В
x2=0
x1=0
s1=0
s2=0
В
s1=0
s2=0
s1=0
В
x1=0
x1=0
s2=0
Оптимальна (вироджена) вершина, ій відповідає ТРИ вироджених ДБР:
Небазисні змінні = це ті змінні, які відповідають прямим, перетином яких є аналізована точка

В
s1=0
s2=0
Умова оптимальності НЕ виконується

В
Умова оптимальності НЕ виконується

В
Умова оптимальності виконується

4.5 Схема симплекс-методу

Схема симплекс – методу
Зазвичай в спрощених програмних продуктах

Схема симплекс – методу
Перейти на крок 1.

Теорема «Умова оптимальності»

Довести, що з того, що ми обираємо , не випливає, що отримаємо максимальний приріст ЦФ.
(+ підібрати числовий приклад, коли буде навпаки)
A
B
C
D
E
F
Самостійно №

A
B
C
D
F
G
H
E
ABHG
ABHGF
ABHF
BCDFH
BHE

Максимально та мінімально можлива кількість аналізованих ДБР (екз+тести)
max
min
max
min
нормаль
Напрямок оптимізації

Максимально та мінімально можлива кількість аналізованих ДБР (екз.!)
max
min
Задача на min
Кількість аналізованих ДБР: 1
A
Задача на max
Кількість аналізованих ДБР: 3
A B C

Максимально та мінімально можлива кількість аналізованих ДБР (екз.!)
max
min
Задача на min
Кількість аналізованих ДБР: 1
A
Кількість аналізованих ДБР: 4
A B C D
Задача на max
Коректно: Яка максимальна можлива кількість аналізованих ДБР (за умови відсутності зациклення)

Максимально та мінімально можлива кількість аналізованих ДБР (екз.!)
Min кількість: 3
A Ej D
Max кількість: 8
A E1 E2 E3 E4 E5 E6 D
max
min
Задача на max
Коректно: Яка максимальна можлива кількість аналізованих ДБР за умови відсутності зациклення

4.6 Збіжність симплекс – методу

4.6 Збіжність симплекс – методу

Зациклення

Причини зациклення
З геометричної точки зору зациклення пояснюється виродженістю поточного розв’язку
З практичної точки зору виродженість пояснюється наявністю надлишкових обмежень
З обчислювальної точки зору, причина зациклення – це не єдиний вибір змінної, що виводиться

Відстань від т. В до прямих (1), (2), (3) одна і та ж