2.Опорное решение транспортной задачи.
Опорным решением транспортной задачи называется любое допустимое решение, для которого векторы условий, соответствующие положительным координатам, линейно независимы.
Ввиду того что ранг системы векторов условий транспортной задачи равен N=m+n-1, опорное решение не может иметь отличных от нуля координат больше, чем N.
Для проверки линейной независимости векторов условий, соответствующих координатам допустимого решения используют циклы.
Цикломназывается такая последовательность клеток таблицы транспортной задачи 
, 
, 
,…,
, в которой две и только две соседние клетки расположены в одной строке или столбце. Причем первая и последняя также находятся в одной строке или столбце.
Система векторов условий транспортной задачи линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимое решение транспортной задачи 
, 
является опорным только в том случае, когда на занятых им клеток таблицы нельзя образовать ни одного цикла.
Для проверки возможности образования цикла используют метод вычеркивания.
Если в строке или столбце таблицы одна занятая клетка, то она не может входить в какой-либо цикл, т.к. цикл имеет две и только две клетки в каждой строке или в столбце. Следовательно, можно вычеркнуть все строки таблицы, содержащие по одной занятой клетке, затем вычеркнуть все столбцы, содержащие по одной занятой клетке, далее вернуться к строкам и продолжить вычеркивание строк и столбцов.
Если в результате вычеркивания все строки и столбцы будут вычеркнуты, значит, из занятых клеток таблицы нельзя выделить часть, образующую цикл, и система соответствующих векторов условий является линейно независимой, а решение – опорным. Если же после вычеркивания останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов условий линейно зависима, а решение не является опорным.
Метод северо-западного угла для нахождения опорного решения.
Согласно данному методу запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используются запасы следующего по номеру поставщика.
Заполнение таблицы начинается с левого верхнего угла и состоит из ряда шагов. Суть метода проследим на примере.
Пример. Пусть исходные данные по некоторой конкретной транспортной задаче представлены в таблице, где 
- три пункта поставки, 
– четыре пункта потребления. Последний столбец содержит возможности поставок из этих пунктов, а последняя строка соответствующие потребности этих пунктов. В клетке образованной пересечением последнего столбца и последней строки, указывается суммарная возможность поставок из всех трех пунктов поставок, по условию равная суммарной потребности всех четырех пунктов потребления.
|
A | | | | | a |
| | 2 | 1 | 3 | 2 | 9 |
| | 2 | 3 | 3 | 3 | 7 |
| | 3 | 3 | 2 | 1 | 5 |
| b | 8 | 6 | 4 | 3 | 21 |
Из представленной таблицы следует, что потребность первого пункта потребления 
составляет 8 ед. продукции.
=8. Поскольку в первом пункте отправления первоначально имелось 9 ед. продукции, то оставшуюся в нем 1 ед. продукции можно адресовать второму пункту потребления 
в результате чего получаем еще один элемент таблицы: 
=1. Однако при этом потребности пункта 
удовлетворены не полностью, и недостающие ему 5 ед. можно направить из пункта отправления 
. При этом получим 
=5. Остающиеся в пункте отправления 2 ед. направим в пункт потребления 
. В результате чего 
=2. Оставшуюся потребность пункта потребления в 3 ед. продукции удовлетворим за счет возможностей пункта отправления 
: 
=2, а оставшиеся в пункте 3 ед. продукции направим для удовлетворения потребностей пункта потребления 
, в результате чего 
=3. Если все найденные значения 
расположить по центру в нижних частях соответствующих клеток (проставляя нули в остальных клетках), то получим следующую таблицу.
| A | | | | | a |
| | 2 8 | 1 1 | 3 0 | 2 0 | 9 |
| | 2 0 | 3 5 | 3 2 | 3 0 | 7 |
| | 3 0 | 3 0 | 2 2 | 1 3 | 5 |
| b | 8 | 6 | 4 | 3 | 21 |
Все отличные от нуля величины , указанные в этой таблице, называют базисными переменными данной транспортной задачи, а равные нулю – свободными.
Стоимость С всех транспортных перевозок, проводимых по этому плану, очевидно, равна сумме произведений отличных от нуля объемов перевозок (базисных переменных), предусмотренных этим планом, на соответствующие стоимости перевозок единиц продукции: 
+1
усл. ед. стоимости.
Т.о., полученное методом северо-западного угла базисное решение удовлетворяет потребности всех пунктов потребления, полностью используя при этом возможности всех пунктов поставки. Однако при этом неизвестно, является ли это решение оптимальным.
Замечание. Необходимо заметить, что рассмотренный выше метод не учитывает стоимость перевозок, поэтому опорное решение, построенное по данному методу, может быть далеким от оптимального.