Постановка и основные свойства транспортной задачи — страница 5
индексов (). Компонента с номером в правой части (3.1.22) не равна нулю. Следовательно, это же относится и к левой части этого равенства, т.е. среди векторов найдется хотя бы один вектор вида с коэффициентом . Перенеся его в правую чатсть равенства (1.22), получим , (1.23) где . Но поскольку , компонента с номером правой части (1.23) отлична от нуля. Поэтому среди векторов левой части (1.23) найдется хотя бы один вектор вида , для которого . Перенося его в правую часть (1.23), находим (1.24) где Этот процесс переноса векторов в правую часть можно продолжить аналогичным образом и дальше. Допустим, что уже проведено (2k-1) шагов. Тогда имеет место соотношение (1.25) где Возможные два случая: 1) при некотором 2) . В первом случае процесс переноса заканчивается, причем из векторов в правой части (1.25) можно образовать замкнутый маршрут. Таким маршрутом является Во втором случае процесс переноса продолжается, и поскольку , среди векторов Рij, где (i, j) обязательно найдется вектор с коэффициентом . Описанный процесс переноса не может длится бесконечно, так как все вектора, переносимые вправо, различны. Поэтому через конечное число шагов мы обязательно столкнемся со случаем 1, который, как показано выше, ведет к образованию замкнутого маршрута. Итак, допустив, что система векторов линейно зависима, мы пришли к противоречию с условием теоремы, согласно которому из коммуникаций системы R нельзя составить замкнутый маршрут. Остается принять, что система R состоит из линейно независимых векторов. Достаточность условий теоремы доказана. Назовем коммуникацию Т-задачи основной коммуникацией плана Х, если Тогда, используя теорему 3.4, можно сформулировать следующий признак проверки произвольного плана на опорность. План Т-задачи является опорным (базисным), если из его основных коммуникаций нельзя составить замкнутый маршрут. Теорема 5. Вектор является линейной комбинацией векторов системы R тогда и только тогда, когда из векторов этой системы можно составить маршрут, соединяющий пункты Ak и . Если этот маршрут имеет вид то . (1.26) Доказательство этой теоремы основано на теореме 3.4. Пусть выражен в виде линейной комбинации векторов системы R. Добавив к ней вектор , получим систему линейно зависимых векторов. Тогда в силу теоремы 3.4 появляется замкнутый маршрут . Этот замкнутый маршрут должен содержать коммуникацию и, следовательно, все остальные коммуникации должны соединить и . Тогда . Перенеся в правую часть, получим выражение (1.26), что и требовалось доказать. 1 2 3 4 5 6 i /j 1 + 1 1 1 2 X = 1 1 3 1 1 4 1 1 1 5 Рис. 3.3. Рассмотрим произвольную матрицу . Между
Похожие работы
- Доклады
- Рефераты
- Рефераты
- Рефераты
- Контрольные