Билет № 5

1. Методы построения опорного решения транспортной задачи. Метод вычёркивания.

Теорема 6.4. Решение транспортной задачи, построенное по методу северо-западного угла, является опорным.

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

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

Теорема 6.5. Решение транспортной задачи, построенное по методу минимальной стоимости, является опорным.

Доказательство аналогично доказательству опорности решения, построенного по методу северо-западного угла.

Билет № 6

Теорема о существовании и единственности цикла.

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

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

В каждой строке и в каждом столбце таблицы, входящих в цикл, две и только две клетки, одна из которых отмечена знаком "+", а другая  знаком "". Поэтому в одной клетке объем перевозки увеличивается на , а в другой уменьшается на , при этом сумма всех перевозок в строке (или столбце) таблицы остаётся неизменной. Следовательно, после сдвига по циклу по-прежнему и запасы всех поставщиков вывозятся полностью, и запросы всех потребителей удовлетворяются полностью. Так как сдвиг по циклу осуществляется на величину , то все объёмы перевозок будут неотрицательными. Следовательно, новое решение является допустимым.

Если оставить свободной одну из клеток с нулевым объёмом перевозки, соответствующих , то число занятых клеток будет равно N = m + n 1.

Одна клетка загружается (отмеченная знаком "+"), одна  освобождается. Так как цикл единственный, то удаление из него одной клетки разрывает его. Цикл из оставшихся занятых клеток образовать нельзя, соответствующие векторы-условия линейно независимы, а решение является опорным.

Билет № 8

2. Теорема об единичном базисе.

Теорема 3.2. О единичном базисе системы векторов. Если система m-мерных векторов содержит m различных единичных векторов , то они образуют базис этой системы.

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

, , . . . , .