Модифікований симплекс-метод

 

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

 

,	(1.7.1)
,	(1.7.2)
.	(1.7.3)

 

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

Визначимо вектор

,

(1.7.4)

тоді

.

(1.7.5)

 

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

Допоміжна таблиця (табл.1.22) відрізняється від звичайної симплекс-таблиці тим, що має додаткові рядки та стовпчики, в яких записують значення та координати векторів , отримані в процесі знаходження розв’язку задачі.

Основна таблиця (табл.1.23) має декілька відмінностей від звичайної симплекс-таблиці:

1) замість стовпчиків векторів з відповідними коефіцієнтами числової функції записують стовпчики векторів , координатами яких є відповідні стовпчики матриці ;

2) у -му рядку записують компоненти векторів , а не числа ;

3) основна таблиця має один додатковий стовпчик, у перших рядках якого записують координати вектора в базисі і який слід включити до базису на наступній ітерації.

 

Таблиця 1.22.

 

№

Базис

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

…

m

…

…

m+1

…

m+2

…

…

…

…

…

…

…

…

…

m+k

…

 

 

Таблиця 1.23.

 

№	Базис
						…
						…
…	…	…	…	…	…	…	…	…
r						…
…	…	…	…	…	…	…	…	…
m						…
m+1						…

 

Спочатку визначають вектор як скалярний добуток вектора на відповідні вектори , тобто за формулою (1.7.4). Знайдені компоненти вектора записують в останньому рядку табл.1.22 і в стовпчику табл.1.22. Потім за формулою (1.7.5) знаходять елементи -го рядка допоміжної таблиці 1.22.

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

В перших рядках цього стовпчика записують компоненти вектора в базисі , які отримують в результаті множення матриці , записаної в табл.1.23, на вектор , компоненти якого вказано в табл. 1.22.

Якщо серед чисел немає додатних, то задача не має розв’язку. Якщо додатні числа є, то знаходять відношення і визначають серед них мінімальне. Нехай . Тоді новий базисний розв’язок визначається базисом, що отримується з вихідного заміною вектора на вектор .

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

Отже, процес розв’язування задачі модифікованим симплекс-методом включає такі етапи:

1. Знаходять опорний план задачі.

2. З компонент векторів початкового базису складають матрицю і обчислюють обернену матрицю .

3. Знаходять вектор .

4. Підраховують числа . Якщо всі , то базисний розв’язок є оптимальним розв’язком задачі. Якщо серед є від’ємні, то обирають серед них найбільше за модулем. Нехай це буде .

5. Обчислюють компоненти вектора у вихідному базисі. Якщо серед них немає додатніх, то цільова функція задачі не обмежена на множині допустимих планів. Якщо серед компонент вектора є додатні, то переходять до нового базисного розв’язку.

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

7. Перевіряють новий базисний розв’язок на оптимальність, тобто повертаються до п.3.

Приклад 1.15. Розв’язати модифікованим симплекс-методом наступну задачу:

Ця задача має базисний розв’язок , який визначається базисом, що утворений векторами . Компоненти цих векторів визначають одиничну матрицю , обернена до якої також є одиничною.

Складемо допоміжну та основну таблиці (табл.1.24 і табл.1.25). На підставі початкових даних заповнимо перші три рядки стовпчиків векторів допоміжної таблиці, а також перші три рядки стовпчиків векторів основної таблиці.

Знайдемо компоненти вектора за формулою (1.7.4):

Запишемо їх в четвертому рядку табл. 1.25, де також заповнимо клітинку стовпчика , яка містить значення цільової функції:

Знайдені компоненти вектора запишемо в табл.1.24 і за формулою (1.7.5) підрахуємо числа :

,

,

,

.

Оскільки серед чисел є від’ємні, то початковий базисний розв’язок не оптимальний . Тому останній стовпчик табл. 1.24 відводимо для вектора , в якому запишемо компоненти розкладу вектора за векторами даного базису. Вони визначаються як добуток матриці (табл. 1.25) на стовпчик вектора (табл. 1.24):

.

Таблиця 1.24.

 

№	Базис
												10/3
4				-7	-10	-12
5					-1
6						4/3	10/3

 

Таблиця 1.25.

								↓
	№	Базис
←								4	120/4 — min
									96/3
									180/3
	4							-12

 

Серед компонент вектора є додатні числа, тому можна перейти до нового опорного плану. Знайдемо мінімальне відношення , яке досягається при . Вважаючи рядок і стовпчик провідними, перейдемо за відомими правилами переходу від табл. 1.25 до нової симплекс-таблиці 1.26.

 

Таблиця 1.26

 

								↓
	№	Базис
←					1/4			3/4	30/(3/4) — min
					-3/4			-1/4	-
					-3/4			3/4	90/(3/4)
	4							-1

 

Знайдемо компоненти вектора :

,

,

.

Запишемо їх в четвертому рядку табл. 1.26 і у відповідному стовпчику табл. 1.24. Підрахуємо числа :

,

,

,

,

,

.

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

.

Знайдені числа записуємо у стовпчику вектора (табл. 1.26). Оскільки серед них є додатні, то переходимо до нового базисного розв’язку (табл. 1.27). Для цього вводимо в базис вектор і виводимо .

Таблиця 1.27

 

№	Базис
				1/3
				-2/3
				-1
4				10/3

 

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

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