Свойства транспортной задачи
Постановка и основные свойства транспортной задачи
Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О.Н. Толстым [18; 59]. Первая строгая постановка Т-задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее называют проблемой Хичкока. Первый точный метод решения Т-задачи разработан Л.В. Канторовичем и М.К. Гавуриным. Постановка Т-задачи. Пусть в пунктах А1,…,Am производят некоторый однородный продукт, причем объем производства в пункте Ai составляет ai единиц, i = 1,…, m. Допустим, что данный продукт потребляют в пунктах B1., Bn, a объем потребления в пункте Вj составляет bj одиниць j = 1., n. Предположим, что из каждого пункта производства возможно транспортировка продукта в любой пунктпотребления. Транспортные издержки по перевозке единицы продукции из пункта Ai в пункт Вj равны cij (i = 1., m; j = 1., n). Задача состоит в определении такого плана перевозок, при котором запросы всех потребителей Вj полностью удовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны. Условия Т-задачи удобно представить в виде табл. 1.1. Таблица. 1.1.
Пусть количество продукта, перевозимого из пункта Ai в пункт Вj. Требуется определить множество переменных , i = 1., m, j = 1., n, удовлетворяющих условиям
(1.1) (1.2)
и таких, что целевая функция
(1.3)
достигает минимального значения. Условие (1.1) гарантирует полный вывоз продукта из всех пунктов производства, а (1.2) означает полное удовлетворение спроса во всех пунктах потребления. Таким образом, Т-задача представляет собой задачу ЛП с числом переменных, и (m + n) числом ограничений равенств. Переменные удобно задавать в виде матрицы
(1.4)
Матрицу X, удовлетворяющую условиям Т-задачи (1.1) и (1.2) называют планом перевозок, а переменные – перевозками. План , при котором целевая функция минимальна, называется оптимальным, а матрица С= – матрицей транспортных затрат. Графический способ задания Т-задач показан на рис. 1
Рис. 1
Отрезок AiBj называют коммуникацией. На всех коммуникациях ставят величины перевозок xij. Вектор Pij, компоненты которого состоят из коэффициентов при переменных xij в ограничениях (3.1.1) и (3.1.2), называют вектором коммуникаций:
Вводят также вектор производства-потребления P0, где
.
Тогда ограничение (3.1.1) и (3.1.2) можно записать в векторной форме
, (1.5)
Свойства транспортной задачи 1. Для разрешимости Т-задачи необходимо и достаточно, чтобы выполнялось условие баланса
, (1.6)
то есть, чтобы суммарный объем производства равнялся объему потребления. Доказательство. Пусть переменные xij, i = 1., m; j = 1., n удовлетворяют условиям (1.1), (1.2). Суммируя (1.1) по , а (1.2) по , получим:
.я
Отсюда , что и доказывает необходимость условия баланса Т-задачи. Пусть справедливо условие (1.6). Обозначим , где . Нетрудно доказать, что хij составляет план задачи. Действительно
Таким образом, доказана достаточность условия баланса для решения Т-задачи. 2. Ранг системы ограничений (1.1), (1.2) равен Доказательство. Так как количество уравнений (1.1), (1.2) равно , то ранг этой системы . Пусть, набор удовлетворяет всем уравнениям, кроме первых. Покажем, что он удовлетворяет также и первому уравнению. Очевидно
Так как
, то , отсюда ,
Учитывая условие баланса (1.6), получим
,
т.е. первое уравнение системы (1.1) тоже удовлетворяется. Таким образом, ранг системы уравнений (1.1), (1.2) . Докажем, что ранг системы уравнений (1.1), (1.2) равен точно . Для этого составим матрицу из первых ( ) компонентов векторов
Очевидно, что эта матрица не вырождена. Поэтому векторы { } образуют базис. Так как базис системы состоит из ( ) векторов, то и ранг системы (1.1), (1.2) . Двойственная транспортная задача ( – задача). Для Т-задачи, как и для любой задачи ЛП, существует двойственная задача к ней -задача. Переменные -задачи обозначим v1, v 2., v n, – u1, – u2., – um… Теорема 1. -задача имеет решение и если Xопт = , – оптимальные решения T и -задачи соответственно, то
. (1.7)
Если учесть, что ui – стоимость единицы продукции в пункте Аі, а vj – стоимость после перевозки в пункт Bj, то смысл теоремы будет такой: Суммарные транспортные расходы при оптимальном плане перевозок равны приращению суммарной стоимости продукции после ее перевозки в пункты потребления. Переменные uiиvj называют потенциалами пунктов AiиBj для Т-задачи. Таким образом, теорема 1. утверждает, что при оптимальных решениях значения целевой функции прямой и двойственной Т-задач равны между собой. Справедливость теоремы 1. следует из основной теоремы двойственной ЛП (теорема 2.5). Сформулируем необходимые и достаточные условия оптимальности плана Т-задачи. Теорема 2. Для оптимальности плана Х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).
Популярное: ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (235)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |