Пошук початкового опорного розв’язку. Метод штучного базису

 

Для того, щоби застосувати симплекс – метод до задачі лінійного програмування у канонічній формі, необхідно спочатку знайти деякий початковий допустимий опорний розв’язок. У попередньому прикладі це було досягнуто завдяки безпосередньому розповсюдженню симплекс – метода (метода жорданових перетворень). Розглянемо це більш докладно на прикладі задачі про раціон, математична модель якої отримана у §1:

f = 20х₁ + 30х₂ (min)

.

Ввівши нові змінні х₃, х₄ і змінивши знаки коефіцієнтів у цільової функції, зведемо цю модель до канонічної:

f ´ = – 20х₁ – 30х₂ (mах)

.

Запишемо її у електронну симплекс – таблицю:

 

	А	B	C	D	E	F
	х1	х2	х3	х4	d	d/aij
			-1
				-1
	-20	-30

 

Ця симплекс – таблиця не приведена до початкового опорного розв’язку. Проте будемо діяти у відповідності з симплекс – методом. Змінні x₃, x₄ не можна безпосередньо використати у якості основних, оскільки тоді їх значення будуть від’ємними, а відповідні розв’язки не допустимими. Спробуємо x₁ у якості основної. Щоби знайти ведучий елемент у стовпці А перевіримо умову допустимості.

 

	А	B	C	D	E	F
	х1	х2	х3	х4	b	b/aij
			-1
				-1
	-20	-30

 

Отже, виокремимо нову симплекс – таблицю в діапазоні А6: F8. Надамо чарункам електронної таблиці таких значень:

	А	B	C	D	E	F
	=А2 – А7*$А$2	→	→	→	→
	=А3/$А$3	→	→	→	→
	=А4 – А7*$А$4	→	→	→	→

 

Звичайно, спочатку діємо у рядку 7, а потім у решті. В результаті дістанемо:

 

	А	B	C	D	E	F
	х1	х2	х3	х4	b	b/aij
		3,666667	-1	0,666667
		0,666667		-0,33333
		-16,6667		-6,66667

 

У якості другої основної змінної спробуємо x₂. Щоби знайти ведучий елемент у стовпці В перевіримо умову допустимості.

 

	А	B	C	D	E	F
	х1	х2	х3	х4	b	b/aij
		3,666667	-1	0,666667		0,545455
		0,666667		-0,33333		4,5
		-16,6667		-6,66667

 

Нам пощастило: ведучий елемент виявився саме на необхідному місці. Якщо б замість 3,666667 значення у чарунці В6 дорівнювало скажімо 0,1, то нам залишилося б замість x₂ спробувати якусь іншу змінну. Тепер виконаємо чергове жорданове перетворення з ведучим елементом у В6:

	А	B	C	D	E	F
	х1	х2	х3	х4	b	b/aij
			-0,27273	0,181818	0,545455
			0,181818	-0,45455	2,636364
				-5,45455	27,27273

Нарешті симплекс – таблиця виявляється приведеною до базису А₁, А₂ опорного розв’язку. Всі оцінки не додатні. Згідно з теоремою 1 це означає, що розв’язок є оптимальним, на цьому симплекс – метод припиняє роботу. Значення цільової функції із зміненими коефіцієнтами f ´ = – 27,27273, отже f = 27,27273. Разом з тим зауважимо, що оцінка δ₃ = 0, отже цільова функція, виражена через вільні змінні х₄, х₃ має вигляд f ´ = 27,27 – 5,45х₄. Тому, якщо обрати за нову основну змінну х₃, то хоча її значення і стане додатним замість нульового, але значення цільової функції f ´ не зміниться і ми дістанемо новий оптимальний опорний розв’язок. Отже, виконаємо жорданове перетворення ще раз. У стовпці С додатним є лише значення у чарунці С11, тому вона і є ведучим елементом. В результаті дістанемо:

 

	А	B	C	D	E	F
	1,5			-0,5	4,5
	5,5			-2,5	14,5
				-5,45455	27,27273

 

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

 

	А	B	C	D	E	F
	х1	х2	х3	х4	d	d/aij
			-1
				-1
	-20	-30
		3,666667	-1	0,666667		0,545455
		0,666667		-0,33333		4,5
		-16,6667		-6,66667
			-0,27273	0,181818	0,545455
			0,181818	-0,45455	2,636364
				-5,45455	27,27273
	1,5			-0,5	4,5
	5,5			-2,5	14,5
				-5,45455	27,27273

 

Звичайно, застосований тут метод не є ефективним алгоритмом пошуку початкового опорного розв’язку. Фактично ми просто пробували деякі пари змінних у якості основних і такий процес перебору може тривати дуже довго. Справжнім ефективним алгоритмом є наступний метод штучного базису.

Розглянемо задачу лінійного програмування у канонічній формі (3):

f = (max)

= b_i (i = 1, 2, …, m)

x_j ≥ 0 (j = 1, 2, …, n).

 

Як і завжди, вважаємо, що всі b_i ≥ 0. Для пошуку початкового опорного розв’язку побудуємо допоміжну задачу

g = (min)

+ y_i = b_i (i = 1, 2, …, m)

x_j ≥ 0 (j = 1, 2, …, n), y_i ≥ 0 (i = 1, 2, …, m). (4)