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

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

оптимальности плана Х0 Т-задачи необходимо и достаточно существование таких чисел v1, v2., vn, – u1, – u2., – um, что vj – ui cij, i = 1., m; j=1., n… (1.8) При этом, если  это vj – ui = cij. Cправедливость этой теоремы вытекает из общих идей теории двойственности линейного программирования (в частности, теоремы 2.5, 2.7). Дадим экономическую интерпретацию условий теоремы 2. Разность между потенциалами пунктов Bj и Ai, т.е. величину vj – ui, можно рассматривать

как приращение ценности единицы продукции при перевозке из пункта Ai в пункт Bj. Поэтому, если vj – ui < cij, то перевозка по коммуникации Ai Bj нерентабельна, и . Если vj – ui = cij, то такая перевозка рентабельна, и  (см. Теорему 2.7). Транспортная задача с ограниченными пропускными способностями. Важной в практическом отношении является Тd - задача, в которой существуют ограничения на пропускные способности коммуникаций. Пусть - пропускная

способность коммуникации Ai Bj. Тогда (1.9) Т-задача состоит в минимизации Ц.Ф. (1.3) при условиях (1.1), (1.2), (1.9). Даже в случае разрешимости Т-задачи, Тd – задача может оказаться неразрешимой, поскольку величины пропускных способностей будут недостаточны для полного вывоза продукта из п. Аі, и полного ввоза продукта в п. Вj. Поэтому для Тd – задачи вводят еще два условия: (1.10) (1.11) Но и при добавочных условиях (1.10), (1.11) Тd – задача не всегда

разрешима. Для установления совместимости всех условий делают попытку построить любой план Т-задачи. Если удается, то система уравнений (1.1), (1.2), (1.9) – (1.11) совместна. В противном случае Тd – задача неразрешима. Теорема 3. Для оптимальности плана Х0 Тd – задачи необходимо и достаточно существование таких чисел v1, v2., vn, – u1, – u2., – um, при которых  если , (1.12)  если 0 <, (1.13)  если. (1.14) Смысл условий оптимальности (1.12) – (1.14)

состоит в следующем: если приращение стоимости продукта vj – uj меньше транспортных расходов cij, то такая перевозка убыточна, а потому . Если же приращение стоимости продукта vj – uj больше транспортных расходов cij (3.1.14), то эта перевозка прибыльна, а потому ее величина должна быть максимальной, т.е. . Таким образом, теорема 3.3 по существу выражает принцип рентабельности для Td – задачи. Открытые транспортные модели. Существует ряд

практических задач, в которых условие баланса не выполняется. Такие модели называются открытыми. Возможные два случая: 1) 2) В первом случае полное удовлетворение спроса невозможно. Такую задачу можно привести к обычной транспортной задаче следующим образом. Обозначим через величину штрафа из-за неудовлетворения запросов на единицу продукта в пункте Bj. Тогда требуется минимизировать (1.15) при условиях где - неудовлетворенный