Початковий базисний розв’язок

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

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

де базисними змінними вибрано перші т змінних математичної моделі задачі.

Перша симплекс-таблиця будується з математичної моделі розширеної форми.

Структура симплекс-таблиці наступна:

– рядок переліку змінних та ;

– рядок коефіцієнтів при відповідних змінних з цільової функції та ;

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

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

– індексний рядок з коефіцієнтами та .

Початкову симплекс-таблицю заповнюють у такій послідовності.

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

Оскільки всі додаткові та штучні змінні з коефіцієнтами +1 утворюють одиничний базис, то

Такі змінні позначають та записують у середню базисну колонку, а коефіцієнти при цих змінних з цільової функції у ліву базисну колонку. До правої базисної колонки записують праві частини з обмежень моделі.

Кожний рядок таблиці зображує одне обмеження моделі за допомогою коефіцієнтів при відповідних змінних. Взагалі такий запис обмежень моделі утворює матрицю .

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

Іноді індексний рядок зображують двома рядками, в одному з яких записують значення

а в іншому – коефіцієнти (- ); таким чином, індексний рядок набирає огляду .

Загальний вигляд основної частини симплекс-таблиці наступний:

			Коефіцієнти
Змінні
			Коефіцієнти при змінних з обмежень тобто
	Коефіцієнти

Базис

Індексний рядок

Для кожного допустимого розв’язку задачі всі змінні, які записано до базису, дорівнюють

а всі вільні змінні, тобто змінні, які не ввійшли до базису, .