Беклемишев - Дополнительные главы линейной алгебры (947281), страница 68

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 68)

системы неехзанств и линепноз пгогглммиговлниа группы и вычтем из них сумму строк второй группы. Если каждый столбец содержит две единицы, то эти единицы расположены в стро- ках из разных групп, и составленная нами разность — нулевая строка, Переставим столбец, содержащий одну единицу, на первое место, а строку, в которой расположена эта единица, также сделаем первой. Теперь, как легко видеть, подматрица Т" матрицы Т', расположенная в строках и столбцах с новыми номерами, большими двух, также невырождена. Применяя к ней те же соображения, что н к Т', выделим матрицу Т" и т. д.

Таким образом, за конечное число шагов мы приведем матрицу Т' к верхнему треугольному виду. Отметим, что в полученной матрице в каждом столбце выше главной диагонали расположено ие больше одной единицы, а осталь- ные элементы равны нулю. Кроме того, все диагональные элементы также равны единице. Поэтому имеет место П р е ало же н и е 2. 7юбой базисный минор матрицы Т ао абсолютной величине равен единице. Определим теперь ранг матрицы Т и вместе с тем укажем способ построения вершины многогранного множестваох допустимых то- чек транспортной задачи. Рассмотрим матрицу С, составленную из элементов с».

Пусть с„з — — ппп си и а„ ( ЬЗ. Тогда полагаем х„з = а„ и х„~ — — О для ау всех 1Ф р, и исключаем из дальнейшего рассмотрения строку матрицы С с номером а. Число Ьа заменяется на Ьа — а„. Еслиа„) Ьз,то полагаем х„а — — Ьа и хм — — О при1~ а, число а„ заменяем на а„— Ьа и исключаем из рассмотрения столбец мат- рицы С с номером р. При равенстве можно аналогичным образом исключить или строку, или столбец, но что-нибудь одно. Если исключили, напри- мер, строку, то Ьз заменяется на нуль. Однако если в матрице имеется одна строка и несколько столбцов, то исключается столбец, а если один столбец и несколько строк, то исключается строка. Такое присвоение значений переменным хц соответствует тому, что мы отправляем по самому дешевому маршруту столько, сколько возможно, и тем самым либо удовлетворяем потребность одного потребителя, либо исчерпываем запасы одного поставщика.

После этого к оставшейся части С' матрицы С применяется тот же процесс до тех пор, пока не будут исключены все столбцы и строки, Всего имеется т + и столбцов и строк, и на каждом шагу, кроме последнего, исключается одна строка или один столбец. На последнем шагу исключаются и строка и столбец.

Таким обра- зом, процесс состоит из т + и — 1 шагов, и построенная матрица Х = и хи и будет содержать т + и — 1 не обязательно равных нулю элементов. -' ' 'Докажем, что элементы так построенной матрицы Х удовлет- воряют системе ограничений транспортной задачи, и выделенные Э К ПРИЛОЖЕНИЯ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ нами переменные являются базисными переменными. Для доказательства проследим еще раз за процессом построения матрицы Х. Пусть для определенности на первом шагу была исключена строка. Значение переменной х„,а„выделенной на первом шагу, однозначно определено по а, и Ьэ, при условии, что х„и = 0 для всех 1~ Р.

Это значение таково, что уравнение с номером а, из первой группы выполнено. Уменьшенная матрица С' соответствует сбалансированной тпанспортной задаче, в которой на одного потребителя меньше, и Ьм = = Ьв, — а,. Выделяемая на втором шагу переменная х,~, также однозначно определена по а„', и Ьэ, при условии, что х л = 0 (или соответственно хп, = О, если на втором шагу исключался столбец). Так как а,'„, и ЬЕ, определены по а, и Ь,, значение х„,э, однозначно определено по а; и Ь„причем выполнено одно ограничение, соответствующее уменьшенной матрице. Если ~, = ~„это ограничение отличается от ограничения исходной задачи, но, учитывая значение х лни изменение Ьм, мы увидим, что выполнено и ограничение исходной задачи.

Продолжая рассуждать таким же образом, мы получим в конце концов уменьшенную матрицу размеров 1 Х 1 и два равных между собой числа а и Ь. Последнюю переменную полагаем равной а и тем удовлетворяем сразу два последних оставшихся уравнения. Таким образом, все уравнения удовлетворены, н выделенные переменные однозначно определены как линейные мвогочлены относительно а„..., а и Ь„..., Ь„при условии, что остальные переменные равны нулю. Это означает, что выделенные переменные являются базисными. Отсюда следует, что КЯТ=т+и — 1.

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

Мы видим, что построение начального базиса в транспортной задаче затруднений не вызывает. В силу описанного нами строения базисного мннора матрицы Т вычисления по формулам (10), (15) и (! б) 5 4 осуществляются крайне просто: для решения соответствующих систем линейных уравнений требуется сравнительно небольшое число сложений и вычитаний и совсем не требуется умножений и делений. Поэтому все трудности в применении симплекс-метода к транспортной задаче сводятся к выбору переменных, вводимых в базис и выводимых из базиса. Это позволяет создать для транспортной задачи весьма эффективную модификацию симплекс-метода. Эта модификация (под,назва- 3!О ГЛ Ч, СИСТЕМЫ НЕРАВЕНСТВ И ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ нием метода лотенииалов) была построена раньше, чем общий симплекс-метод.

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

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

Пусть сеть содержит л узлов, кроме источника и стока. Источнику присвоим номер О, стоку — номер л + 1. Сеть может быть задана матрицей Р порядка л + 1. Элемент д„, 1 = О, ..., л; / = = 1, ..., л + 1, этой матрицы равен пропускной способности дуги, если 1-й и 1-й узлы соединены дугой, и нулю в остальных случаях. В частности, диагональные элементы дп равны нулю. Стоит заметить, что для большинства реальных сетей матрица Р разреженная, и потому записывать ее целиком нет смысла.

Данные о сети можно хранить и во многих других формах. Однако для теоретических рассуждений удобнее представлять себе матрицу. Обозначим через ху величину потока по дуге из 1-го узла в )сй. Для того чтобы упростить запись уравнений, будем считать, что величины потоков определены для всех пар 1, 1, 1 = О, ..., л; 1 = = 1, ....

л + 1, но фактически отсутствующим дугам соответствуют нулевые пропускные способности и нулевые величины потоков. Тогда ограничения на потоки, накладываемые пропускными способностями, имеют вид О м='. х» ~ ду (1) двя всех пар 1, !. З к пгиложения линвиного пеогекммиеовлния зы Уравнение баланса в /-м узле для / = !, ..., п можно записать так: а в+! ~~ ху — ~ ху, =О.

(2) с=о Следствием уравнений баланса является требование, чтобы сумма потоков, исходящих из источника, равнялась сумме потоков, входящих в сток: л+1 л ~; х; =,'У', х, „. (3) !=! с=о Последнее уравнение можно также рассматривать как уравнение баланса, если представить себе, что сток и источник соединены дугой с большой пропускной способностью, которая возвращает в источник все, протекшее через сеть, и тем самым объединяет источник и сток в одну точку. Под величиной потока через сеть мы будем понимать левую часть равенства (3). Эту сумму мы и должны сделать максимальной при условии, что выполнены ограничения (1), (2).

Характеристики

Список файлов книги