Простейшие свойства транспортной задачи
Теорема 1. Для любой транспортной задачи существует план (то есть для любой транспортной задачи допустимая область не пуста).
Доказательство
Действительно, по смыслу задачи, .
Так как ,
| то возьмем план в виде
| .
Величины .
| Далее
|
то есть ограничения выполняются. Поэтому составляют план. Теорема доказана.J
Теорема 2. Транспортная задача всегда имеет оптимальный план.
Доказательство
Действительно, допустимая область не пуста. Далее, так как по смыслу , то для любого плана перевозок
.
В силу того, что значения целевой функции ограничены снизу, транспортная задача всегда имеет решение. Теорема доказана.
Теорема 3. Любой опорный план имеет не более
|
| положительных компонент.
Доказательство
Действительно, исходная система содержит всего ограничений типа равенств:
, то есть m ограничений;
то есть n ограничений.
Однако в силу соотношения одно из этих ограничений является следствием всех остальных. Действительно, сложим все первые m ограничений
| (1)
| а из второй группы сложим первые n- 1 ограничение
| (2)
| Вычитая теперь (2) из (1), получим:
,
и мы получили последнее, n-ое ограничение второй группы.
Таким образом, независимых ограничений всего не более . Поэтому
каждый опорный план имеет не более
| компонент.
| Следствие. Оптимальный план содержит не более, чем перевозку.
4.3. Методы определения первоначального опорного плана
4.3.1. Построение исходного опорного плана (метод северо-западного угла)
Для начала решения транспортной задачи необходимо иметь какой-то исходный опорный план, то есть оказаться в какой-то вершине допустимой области. Приведем конструктивный прием построения такого опорного плана, получивший название "метод северо-западного угла".
Итак, пусть имеется m складов с запасами
| и n пунктов
|
потребления с потребностями .
| Пусть запасы и потребности
|
сбалансированы, то есть .
|
| Представим это в виде таблицы,
где в столбце справа указаны запасы, в строке снизу - потребности, а пустые клетки оставлены для будущего плана перевозок.
Начнем заполнение с клетки, расположенной вверху слева, то есть с "северо-западного угла". Вместо впишем число . Возможны два варианта.
- , то есть . Тогда, запланировав перевозку из первого склада в первый пункт потребления в объеме мы полностью опустошим первый склад и там ничего не останется. Поэтому все остальные перевозки из первого склада могут быть только нулевые.
Ну, а потребность в первом пункте потребления останется в объеме . Наша таблица примет вид:
Обратите внимание на то, что оставшаяся незаполненной часть таблицы вновь по структуре та же, что и исходная таблица, только в ней на одну строку меньше.
- , то есть . Тогда, запланировав перевозку из первого склада в первый пункт потребления в объеме , мы полностью удовлетворим его потребности. Перевозить туда больше будет ничего не надо, поэтому остальные перевозки туда будут равны нулю.
Ну, а в первом складе еще останется запасов продукта. Наша таблица примет вид:
Обратите внимание на то, что оставшаяся незаполненной часть таблицы вновь по структуре та же, что и исходная таблица, только в ней на один столбец меньше.
Ну, а дальше все можно повторить, продолжая заполнять оставшуюся часть таблицы перевозок начиная с левого верхнего, "северо-западного" угла, пока не будут исчерпаны запасы всех складов и не удовлетворены потребности всех пунктов потребления.
У нас всего в таблице m строк и n столбцов. Каждый раз исчезает, как минимум, либо строка, либо столбец (могут исчезнуть сразу и строка, и столбец, если запасы какого-то подмножества складов полностью удовлетворят потребности какого-то подмножества пунктов потребления). Однако при последней перевозке исчезает сразу и последняя строка, и последний столбец. Поэтому получающийся план перевозок содержит не
более
| компонент.
| Мы не будем доказывать, что план, полученный методом северо-западного угла, является опорным. Заметим лишь, что если получающийся план содержит ровно компоненту, то он называется невырожденным. Если число положительных компонент плана перевозок меньше , то он называется вырожденным.
Рассмотрим два примера. С целью экономии места, вся таблица не переписывается, а лишь приписываются последние строки и столбцы.
Пример 1
Пусть
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| В данном случае число
|
|
|
|
| складов m =3, число пунктов
|
|
|
|
| потребления n =4, так что
|
|
|
|
| m+n-1=6. Получившийся
|
|
|
|
| опорный план содержит ровно
|
|
|
|
| 6 компонент, и поэтому являет-
|
|
|
|
| ся невырожденным.
| Пример 2
Пусть Аналогичная процедура приводит к таблице, изображенной ниже.
В этом случае получившийся опорный план имеет всего 5 компонент, то есть является вырожденным. Это
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| В данном случае число скла-
|
|
|
|
| дов m =3, число пунктов потре-
|
|
|
|
| бления n =4, так что m+n-1=6.
|
|
|
|
| Получившийся опорный план
|
|
|
|
| содержит 5 компонент, и поэтому
|
|
|
|
| является вырожденным.
| произошло потому, что запасы складов и полностью удовлетворили потребности пунктов потребления и и поэтому в тот момент, когда эти сбалансированные потребности удовлетворились ( ), обнулились сразу и строка, и столбец.
Ниже вся теория будет строится для случая, когда все опорные планы невырожденные, то есть все они имеют компоненту. Как бороться с явлением вырождения, которое в транспортных задачах встречается достаточно часто - будет рассказано в самом конце
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|