2.2. Опис використаного варіанту симплекс-метода

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

Нехай дана функція, для якої необхідно знайти найбільше або найменше значення, якщо значення всіх невідомих невід'ємні.

ƒ = C₀ + C₁x₁ + C₂x₂ +...+ C_nx_n

і система m лінійних рівнянь з n невідомими. Це називається системою обмежень:

a ₁₁x₁ + a₁₂x₂ +...+ a_1nx_n = b₁

a₂₁x₁ + a₁₂x₂ +...+ a_2nx_n = b₂

...

a_m1x₁ +a_m2x₁₂ +...+ a_mnx_n = b_m

Цільову функцію представимо у вигляді:

ƒ - C₁x₁-C₂x₂ -...-C_nx_n= C₀

Складемо симплекс-таблицю. Надалі будемо вважати, що ранг матриці системи обмежень дорівнює r. В системі обмежень обраний базис (основні невідомі) x1, x2, ... xn і коефіцієнти в правій частині не негативні.

В цьому випадку система обмежень матиме вигляд:

x₁ +...+ a_1,r+1x_r+1 +...+ a_1nx_n = b₁

x₂ + a_2,r+1x_r+1 +...+ a_2nx_n = b₂

...

x_r+ a_r,r+1x_r+1 +...+ a_rnx_n = b_r

Тоді цільова функція має вигляд:

ƒ +C_r+1x_r+1 + C_r+2x_r+2 -...- C_nx_n= C₀

Знаходження оптимального плану симплексним методом включає наступні етапи:

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

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

Базисні невідомі	Вільні члени	x1	x2	...	xr	xr+1	xj	xn
x1 x2 ... xi ... xr	b1 b2 ... bi ... br	1 0 ... 0 ... 0	0 1 0 0		0 0 ... 0 ... 1	a1,r+1 a2,r+1 ... ai,r+1 ... ar,r+1	a1j a2j ... aij ... arj	a1n a2n ... ain ... arn
ƒ	C0	0	0	...	0	Cr+2	Cj	Cn

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

4. Нехай елемент Сj <0, тоді в j-му стовпці необхідно знайти позитивний елемент. Якщо всі коефіцієнти цього стовпця негативні, то рішення не існує.

5. Якщо позитивний коефіцієнт в j-му стовпці один, то обраний рядок з номером «i» треба поділити всі коефіцієнти на число aij. Результат ділення записуємо в нову симплекс-таблицю. Якщо ж позитивних коефіцієнтів декілька, необхідно скласти ставлення bi / aij і з отриманих значень вибрати найменше, відповідне i-ому рядку.

6. У новій симплекс-таблиці у стовпці базисних невідомих замість xi пишеться xj. Заповнюється таблиця. У стовпці з номером j необхідно отримати нулі (включаючи рядок з цільовою функцією). Для цього треба помножити i-й записаний рядок на потрібне число і скласти з іншими рядками.

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

Розділ 3. Опис розробленого програмного забезпечення