2. Построение начального опорного плана методом минимальной стоимости.

Для удобства выбора минимальной стоимости и вычеркивания строк и столбцов таблицы, запишем отдельно матрицу тарифов

Минимальная стоимость перевозок равна . Это стоимости перевозок от второго поставщика третьему потребителю и от третьего поставщика второму потребителю. Заполним одну из клеток или таблицы 8, например, клетку , распределяя запасы второго поставщика . В левый нижний угол данной клетки запишем максимально возможную перевозку, равную . Запасы второго поставщика и третьего потребителя уменьшаем на величину : , . Запасы второго поставщика исчерпаны, и его можно исключить из рассмотрения. Вычеркнем из матрицы тарифов вторую строку. Для наглядности справа от второй строки матрицы указано значение выбранной минимальной стоимости. В незанятых клетках строки вместо стоимости перевозок ставим прочерк, что соответствует нулевым небазисным перевозкам. Запросы третьего потребителя также удовлетворены. Но на каждом шаге мы исключаем из рассмотрения только одного поставщика или одного потребителя. Поэтому третий столбец не вычеркиваем.

Таблица 8. Матрица планирования начального опорного плана

Поставщики	Потребители				Запасы
	4 110	4 -	2	5 40	150
	5 -	3 -	1 60	2 -	60
	2 -	1 40	4 -	2 40	80
Потребности			60

На втором шаге в невычеркнутой части матрицы тарифов минимальной является стоимость в ячейке . Максимально возможная перевозка, которую можно осуществить от третьего поставщика второму потребителю, равна . Записываем значение перевозки в левом нижнем углу ячейки . Запасы третьего поставщика и потребности второго потребителя уменьшаем на количество 40 перевезенной продукции: , . Для удобства остатки запасов и потребностей можно записывать рядом с их предыдущими значениями. Потребности третьего поставщика удовлетворены. Его можно исключить из рассмотрения и вычеркнуть второй столбец в матрице тарифов. В незанятых ячейках второго столбца ставим прочерки.

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

На четвертом шаге минимальными являются стоимости . Рассмотрим, например, ячейку . Остаток запасов третьего поставщика равен , а потребности четвертого заказчика . Максимально возможная перевозка, которую можно осуществить от третьего поставщика четвертому потребителю, равна . Записываем значение перевозки в ячейку . Запасы третьего поставщика исчерпаны. В незанятых клетках третьей строки ставим прочерки и вычеркиваем ее из матрицы тарифов. Потребности четвертого поставщика уменьшаем на 40: .

На пятом шаге . Тогда . Записываем значение перевозки в ячейку . Потребности первого заказчика удовлетворены. Вычеркиваем первый столбец из матрицы тарифов. Запасы первого поставщика уменьшаем на 110: .

Осталась незаполненной ячейка . Остаток запасов первого поставщика , а неудовлетворенные потребности четвертого заказчика равны . Записывает в ячейку таблицы значение перевозки .

Все запасы распределены, все потребности удовлетворены, и все клетки таблицы либо заполнены, либо прочеркнуты.

В результате получен опорный план

Остальные значения свободных переменных равны нулю.

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

Методом вычеркивания проверяем опорность плана (линейную независимость векторов условий). Запишем матрицу перевозок . Вычеркиваем последовательно строки или столбцы, в которых есть (или остался после вычеркивания) только один положительный элемент или базисный ноль , соответствующие базисным переменным:

. .

Данное решение является «вычеркиваемым» и, следовательно, опорным.