Лекція 13 Тема: Симплекс-метод розв’язування канонічної задачі лінійного програмування

План:

1. Суть симплекс-методу.

2. Симплекс-метод в загальному вигляді.

3. Симплекс-таблиці.

Короткий зміст лекції:

Розглянемо задачу лінійного програмування з обмеженням в формі рівнянь.

Дана система:

(1)

m лінійних рівнянь з n невідомими та лінійна форма:

.

(2)

Серед невід’ємних розв’язків системи (1) необхідно знайти такий, який мінімізує форму f (2).

Для початку роботи за симплекс-методом вимагається, щоб задана система рівнянь була зведена до такого виду, в якому будь-які невідомі були виражені через інші, причому вільні члени цих виразів невід’ємні.

Припустимо, для визначеності, що невідомі, які виражені через інші – це .

Отже, система зведена до виду:

(3)

Невідомі називаються базисними, а весь набір , який позначимо буквою Б – базисом, інші невідомі називаються небазисними або вільними.

Підставляючи в форму f замість базисних невідомих їх вирази (3), записуємо f у вигляді:

.

Надаємо вільним невідомим нульових значень: . Тоді . Одержуємо допустимий розв’язок системи: . Він називається базисним розв’язком, який відповідає базису .

Для базисного розв’язку значення форми f дорівнює .

Розв’язування задачі за симплекс-методом розпадається на ряд кроків. Кожний з кроків полягає в тому, що від даного базису Б переходимо до іншого базису так, щоб значення зменшилося або, в крайньому випадку, не збільшилося: .

Новий базис одержується із старого Б вилученням одного з невідомих і введенням замість нього іншого (з числа попередніх небазисниx). Заміна базису веде до перебудови системи (3). Після декількох кроків одержуємо базис , для якого є шуканий мінімум форми f, а відповідний базисний розв’язок є оптимальним, або з’ясовуємо, що задача розв’язку не має.

Порядок роботи за симплекс-методом полягає в наступному.

1. Зводимо систему обмежень до виду, розв’язаному відносно будь-якого базису.

2. Виражаємо форму f через небазисні невідомі. Якщо в одержаному виразі всі коефіцієнти при небазисних невідомих невід’ємні, то базисний розв’язок є оптимальним – задача розв’язана.

3. Нехай серед коефіцієнтів, заданих в попередньому пункті, є від’ємні. Беремо будь-який з них – нехай, наприклад, це буде коефіцієнт при . Продивляємося стовпчик з коефіцієнтів при в правих частинах системи обмежень. Якщо всі числа цього стовпчика невід’ємні, то min f = –∞ – задача розв’язків не має.

4. Нехай в стовпці коефіцієнтів, згаданих в пункті 3, є від’ємні числа. Для кожного з таких чисел – (так позначаємо коефіцієнт при у виразі для базисного невідомого ) знаходимо відношення (– вільний член у виразі для ). Серед цих відношень вибираємо найменше; припустимо, що воно відповідає значенню k = i. Елемент називається розв’язувальним.

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

Далі повертаємося до виконання пункту 2.

Всі труднощі описаної процедури зосереджені в пунктах 1, 2, 5.

Примітка. В основі одного кроку процесу обчислень за симплекс-методом лежить вибір від’ємного коефіцієнту при . Якщо таких коефіцієнтів не один, а декілька, то можна вибирати будь-який з них. Ця обставина вносить деякий елемент свавілля в розрахунки, оскільки одержується декілька можливостей для вибору розв’язувального елементу . Якщо обидва вибори зроблені, то далі процес обчислень продовжується однозначно – до закінчення даного кроку.

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

Нехай канонічна задача максимізації функції f зведена до виду:

(1)

та системи обмежень:

(2)

Даним (1) і (2) відповідає наступна таблиця, в яку внесені коефіцієнти при невідомих і вільні члени з (1) і (2).

Таблица 1

Базисні невідомі			…					Вільні члени
	1	0	…	0		…
	0	1	…	0		…
…	…	…	…	…	…	…	…	…
	0	0	…	1		…
Форма f	0	0	…	0		…

Якщо, то – оптимальний розв’язок і max f = l.

Якщо знайдеться і всі , то задача розв’язків не має.

Нехай знайдеться і серед чисел є додатне. Тоді переходимо до таблиці 2, яка будується за наступним алгоритмом:

а) для складемо відношення і серед них вибираємо найменше, нехай це буде (взагалі їх може бути декілька, беремо одне з них). Елемент називається розв’язувальним, а другий рядок –- розв’язуючим (виділяємо їх в таблиці);

б) для рядків таблиці 1, крім розв’язуючого, обчислюємо розв’язувальний коефіцієнт : ;

в) в таблиці 2 на місце базисного невідомого переходить ;

г) в таблиці 2 у другому рядку записуємо елементи другого рядка таблиці 1, поділені на – розв’язувальний елемент, а k-й стовпчик заповнюється нулями, крім елементу ;

д) інші і-рядки таблиці 2, i = 1, 2, 3…, r, f одержуються з відповідних і-х рядків таблиці 1, до яких додається розв’язуючий рядок 2 таблиці 1, помножений на відповідні розв’язувальні коефіцієнти , i = 1, 2, 3…, r, f.

Таблиця 2

Базисні невідомі				…					Вільні члени
	1	0+	…	…	0		0
	0		…	…	0		1
	0	0+	0	…	0		0
…
	0	0+	0	…	0		0
f	0	0+	0	…	0		0

Весь процес розв’язування задачі зводиться до послідовного складання таблиць 1, 2, … – доки не буде одержаний оптимальний розв’язок (ознакою цього є невід’ємність всіх коефіцієнтів у виразі форми f через небазисні невідомі або, що теж саме, недодатність всіх елементів останнього рядка таблиці, крім, можливо, останнього з них вільного члена) або ж не буде виявлено, що min f = –∞ (ознакою цього є наявність серед указаних вище чисел додатного числа, до того ж такого, що всі числа таблиці, які стоять над ним недодатні). В цей момент процес закінчується.