7.1.4. Алгоритм симплексного методу.

1. Вибираємо базисні змінні: ,…,. Нульове базисне рішення має вигляд: ; базисні вектори: ,…,.

2. Знайдемо розкладання векторів за обраним базисом й обчислимо значення оцінок .

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

Нехай , тоді вектор вводиться в базис. Виводитися з базису буде вектор , для якого справедливо:

Елемент називається розв’язувальним, а - тий рядок і -ий стовпець - напрямними.

Новий базис: .

Відповідні базисні змінні:

.

4. Знайдемо координати розкладання векторів по новому базису і нове базисне рішення.

Нове базисне рішення визначається за формулами:

Розкладання векторів обчислюється в такий спосіб:

Щоб знайти розкладання векторів по новому базису, треба розділити напрямний -тий рядок на розв’язувальний елемент і зробити повне виключення за методом Жордана-Гаусса в направляючому -тому стовпці.

cn	An	x1, n x2, n x r, n x m, n	zn – cn
…	…
ck	Ak	x1, k x2, k x r, k xm, k	zk – ck
…	…
cm+1	Am+1	x1,m+1 x2,m+1 xr,m+1 xm,m+1	zm+1 cm+1
cm	Am	0 0 0 1	0
…	…
cr	Ar	0 0 1 0	0
…	…
c2	A2	0 1 0 0	0
c1	A1	1 0 0 0	0
	X	x1 x2 xr xm	z0
	CБ	c1 c2 c r cm
	AБ	A1 A2 A r Am
i		1 2 r m	m+1

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

Зауваження: Якщо вирішується задача максимізації цільової функції, то функція записується у вигляді:

.

І для неї вирішується задача мінімізації