Постановка и основные свойства транспортной задачи — страница 5

  • Просмотров 510
  • Скачиваний 11
  • Размер файла 206
    Кб

индексов (). Компонента с номером  в правой части (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. Рассмотрим произвольную матрицу . Между