Начальное допустимое базисное решение

Начальное допустимое базисное решение, или опорный план перевозок транспортной задачи, которая представлена транспортной таблицей 3 находится методом «северо-западного угла».

Таблица 3 – Исходная транспортная задача

Заводы	Объекты строительства	Объем производства, м3/ч
	3 x11	x12	10 x13	7 x14
2	x21	6 x22	0 x23	2 x24
3	5 x31	8 x32	15 x33	x34
Спрос					--

Процедура поиска начального базисного решения, согласно правилу северо - ­западного угла, начинается с придания переменной Х₁₁ максимально возможного, исходя из спроса и объема производства, значения. Остальные переменные первой строки или первого столбца (т. е. Х_1j или Х_i1) полагаются равными нулю. Если одновременно выполняются ограничения и на спрос и на производство, то можно вычеркивать или столбец, или строку (по желанию). В этом случае последующая включаемая в базис переменная имеет обязательно нулевое значение. Последующий этап предусматривает корректировку спроса и предложения во всех остальных строках и столбцах с учетом заданного максимального значения Х₁₁. Далее максимально допустимое значение приписывается первому невычеркнутому элементу следующего столбца (строки). Заканчивается эта процедура, когда остается невычеркнутым только один столбец (или строка).

Таблица 4 - Начальное допустимое базисное решение, полученное методом «северо-западного угла»

Заводы	Объекты строительства	Объем производства, м3/ч
	3	2	10	7
	4	6
	5	8	15	9
Спрос

Небазисные переменные (остальные Х_ij) равны нулю. Число базисных переменных в таблице 4 равно нужному числу: m + n — 1= 4 + 3 — 1=6.

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