Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Ограничение (1) и условия неотрицательности переменных, исключающие обратные перевозки xij>0; i= 1, 2, …, k; j= 1, 2,., l.
Эти условия образуют систему ограничений. Любой план, компоненты которого удовлетворяют этой системе, будет допустимым.
Как видим, система ограничений задана в основном (k + l) уравнениями. Установим условия, при которых эта система будет совместной, т.е. будет иметь решения.
Сложим элементы x ij матрицы перевозок по строкам, каждая строка в сумме дает Mi, и в итоге получим . Сложим те же элементы по столбцам, каждый столбец дает Nj, и в сумме получим . Но от перестановки слагаемых сумма не меняется, поэтому для любого допустимого плана обязательно будет выполняться условие
.
Равенство является необходимым условием совместности ограничений задачи.
Докажем и достаточность этого условия: если запасы равны потребностям, то всегда имеется допустимый план.
Действительно, пусть . Рассмотрим такие числа:
Убедимся, что эти числа образуют допустимый план. Для этого достаточно проверить, что они удовлетворяют всем ограничениям задачи.
Просуммируем эти числа по индексу i:
.
Но величины Nj, от индекса i не зависят и их можно вынести за знак суммы. В результате
или
,
Следовательно, взятые числа удовлетворяют группе уравнений (1).
Просуммируем эти числа по индексу j:
Вынося постоянные Mi и за знак суммы и имея в виду, что , получаем
или в развернутом виде
Как видим, наши числа удовлетворяют группе уравнений (1). Эти числа неотрицательны, т.е. система ограничений полностью удовлетворяется. Таким образом, допустимый план существует, что и требовалось доказать.
Равенство запасов потребностям есть необходимое и достаточное условие совместности и, следовательно, разрешимости транспортной задачи.
Дата публикования: 2015-03-26; Прочитано: 291 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!