![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
Eng | Rus | Ukr | ![]() |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
Исследование операций
|
27.01.2005
|
![]() |
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
3.1 ПОСТАНОВКА И ОСНОВНЫЕ СВОЙСТВА ТРАНСПОРТНОЙ ЗАДАЧИТранспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О. Н. Толстым [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 полностьюудовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны. Условия Т-задачи удобно представить в виде табл. 3.1.Таблица. 3.1.
Пусть Требуется определить множество переменных
и таких, что целевая функция
достигает минимального значения. Условие (3.1.1) гарантирует полный вывоз продукта из всех пунктов производства, а (3.1.2) означает полное удовлетворение спроса во всех пунктах потребления. Таким образом, Т-задача представляет собой задачу ЛП с Переменные
Матрицу X, удовлетворяющую условиям Т-задачи (3.1.1) и (3.1.2) называют планом перевозок, а переменные Графический способ задания Т-задач показан на рис. 3.1
Рис. 3.1 Отрезок AiBj называют коммуникацией. На всех коммуникациях ставят величины перевозок xij. Вектор Pij, компоненты которого состоят из коэффициентов при переменных xij в ограничениях (3.1.1) и (3.1.2), называют вектором коммуникаций: Вводят также вектор производства-потребления P0, где
Тогда ограничение (3.1.1) и (3.1.2) можно записать в векторной форме
Свойства транспортной задачи1. Для разрешимости Т-задачи необходимо и достаточно, чтобы вяполнялось условие баланса
то есть, чтобы суммарный объем производства равнялся объему потребления. Доказательство. Пусть переменные xij, i = 1,..,m; j = 1,..,n удовлетворяют условиям (3.1.1), (3.1.2). Суммируя (3.1.1) по
Отсюда Пусть справедливо условие (3.1.6). Обозначим Нетрудно доказать, что хij составляет план задачи. Действительно Таким образом, доказана достаточность условия баланса для решения Т-задачи. 2. Ранг системы ограничений (3.1.1), (3.1.2) равен Доказательство. Так как количество уравнений (3.1.1), (3.1.2) равно Очевидно Так как то
отсюда
Учитывая условие баланса (3.1.6), получим
т.е. первое уравнение системы (3.1.1) тоже удовлетворяется. Таким образом, ранг системы уравнений (3.1.1), (3.1.2) Докажем, что ранг системы уравнений (3.1.1), (3.1.2) равен точно Очевидно, что эта матрица не вырождена. Поэтому векторы { мы состоит из ( Двойственная транспортная задача ( Переменные Теорема 3.1.
Если учесть, что ui - стоимость единицы продукции в пункте Аі , а vj - стоимость после перевозки в пункт Bj , то смысл теоремы будет такой: Суммарные транспортные расходы при оптимальном плане перевозок равны приращению суммарной стоимости продукции после ее перевозки в пункты потребления. Переменные ui и vj называют потенциалами пунктов Ai и Bj для Т-задачи. Таким образом, теорема 3.1. утверждает, что при оптимальных решениях значения целевой функции прямой и двойственной Т-задач равны между собой. Справедливость теоремы 3.1. следует из основной теоремы двойственной ЛП (теорема 2.5). Сформулируем необходимые и достаточные условия оптимальности плана Т-задачи. Теорема 3.2. Для оптимальности плана Х0 Т-задачи необходимо и достаточно существование таких чисел v1, v2, ., vn, -u1, -u2, .,-um , что vj - ui При этом, если
Cправедливость этой теоремы вытекает из общих идей теории двойственности линейного программирования (в частности, теоремы 2.5, 2.7). Дадим экономическую интерпретацию условий теоремы 3.2. Разность между потенциалами пунктов Bj и Ai , т.е. величину vj - ui , можно рассматривать как приращение ценности единицы продукции при перевозке из пункта Ai в пункт Bj . Поэтому, если vj - ui < cij , то перевозка по коммуникации Ai Bj нерентабельна, и Транспортная задача с ограниченными пропускными способностями. Важной в практическом отношении является Тd - задача, в которой существуют ограничения на пропускные способности коммуникаций. Пусть Тогда Т-задача состоит в минимизации Ц.Ф. (3.1.3) при условиях (3.1.1), (3.1.2), (3.1.9). Даже в случае разрешимости Т-задачи, Тd - задача может оказаться неразрешимой, поскольку величины пропускных способностей будут недостаточны для полного вывоза продукта из п. Аі, и полного ввоза продукта в п. Вj. Поэтому для Тd - задачи вводят еще два условия:
Но и при добавочных условиях (3.1.10), (3.1.11) Тd - задача не всегда разрешима. Для установления совместимости всех условий делают попытку построить любой план Т-задачи. Если удается, то система уравнений (3.1.1), (3.1.2), (3.1.9) - (3.1.11) совместна. В противном случае Тd - задача неразрешима. Теорема 3.3. Для оптимальности плана Х0 Тd - задачи необходимо и достаточно существование таких чисел v1, v2, ., vn, -u1, -u2, .,-um , при которых
Смысл условий оптимальности (3.1.12) - (3.1.14) состоит в следующем: если приращение стоимости продукта vj - uj меньше транспортных расходов cij , то такая перевозка убыточна, а потому Таким образом, теорема 3.3 по существу выражает принцип рентабельности для Td- задачи. Открытые транспортные модели. Существует ряд практических задач, в которых условие баланса 1) 2) В первом случае полное удовлетворение спроса невозможно. Такую задачу можно привести к обычной транспортной задаче следующим образом. Обозначим через Тогда требуется минимизировать
при условиях где Задачу (3.1.15) приводят к обычной Т-задаче введением фиктивного пункта производства Аm+1 , с объемом производства минимизировать при условиях В найденном решении хопт полагаем все перевозки из фиктивного пункта Аm+1 равными нулю, т.е. Рассмотрим теперь второй случай. Введем фиктивный пункт Bn+1 с объемом спроса минимизировать при условиях В найденном решении Опорные планы Т-задачиОпорным (базисным) планом Т-задачи называют любое ее допустимое, базисное решение. Понятие опорного плана имеет наглядную геометрическую интерпретацию. Последовательность коммуникаций
называют маршрутом, соединяющим пункты
Рис. 3.2 Используя маршрут, составленный из коммуникаций, можно осуществить перевозку продукта из пункта В процессе этого движения коммуникации, стоящие на четных местах в (3.1.19), будут пройдены в противоположном направлении. Маршрут (3.1.19), к которому добавлена коммуникация Способ проверки произвольного плана Т-задачи на опорность, основан на следующих двух теоремах (прямой и обратной). Теорема 3.4. Система, составленная из векторов
которое указывает на линейную зависимость векторов
Полученное противоречие доказывает необходимость условий теоремы 3.4. Достаточность. Допустим, что из коммуникаций, отвечающих векторам
Пусть, например
где Е1 образуется вычеркиванием в Е пары индексов ( Следовательно, это же относится и к левой части этого равенства, т.е. среди векторов коэффициентом
где
где Этот процесс переноса векторов в правую часть можно продолжить аналогичным образом и дальше. Допустим, что уже проведено (2k-1) шагов. Тогда имеет место соотношение
где Возможные два случая: 1) 2) В первом случае процесс переноса заканчивается, причем из векторов в правой части (3.1.25) можно образовать замкнутый маршрут. Таким маршрутом является Во втором случае процесс переноса продолжается, и поскольку Описанный процесс переноса не может длится бесконечно, так как все вектора, переносимые вправо, различны. Поэтому через конечное число шагов мы обязательно столкнемся со случаем 1, который, как показано више, ведет к образованию замкнутого маршрута. Итак, допустив, что система векторов Достаточность условий теоремы доказана. Назовем коммуникацию План Теорема 3.5. Вектор то
Доказательство этой теоремы основано на теореме 3.4. Пусть Тогда
Перенеся
Рассмотрим произвольную матрицу
При использовании матрицы Х критерий проверки линейной независимости формулируется так: для линейной независимости системы векторов Так как из выделенных единицами позиций на рис. 3.3 нельзя составить замкнутый маршрут, то данная система линейно независима и образует базис. Введем теперь в систему
При небольших размерах матрицы Х визуальное отыскание замкнутых цепочек в ней представляет значительные трудности. В таком случае прибегают к формализованному методу вычеркивания. Метод вычеркивания позволяет выделить в произвольном плане Х Т-задачи замкнутую цепочку, если она существует. Этот метод состоит в следующем. Выделив в плане Х множество ненулевых элементов, обозначаемое через S, выясним, существуют ли во множестве элементов S циклы. Для этого просматриваем одну за другой строки плана Х и вычеркиваем строки, не содержащие элементов S, и строки, которые содержат не более одного элемента S (ненулевой элемент). Просмотрев все строки плана Х, переходим к столбцам и вычеркиваем те из них, которые содержат не более одного элемента S. При этом элементы, содержащиеся в ранее вычеркнутых строках, в расчет не принимают. Далее повторяем весь этот процесс, просматривая сначала строки, а потом столбцы оставшейся после вычеркивания строк и столбцов подматрицы. После конечного числа шагов этот процесс заканчивается одним из следующих двух исходов: 1) все строки (столбцы) матрицы вычеркнуты; 2) получена подматрица, в каждой строке и столбце которой содержится не менее двух элементов S. В первом случае из элементов множества S составить цикл невозможно. Следовательно, соответствующий план Х является опорным. Во втором случае множество S содержит цикл (циклы) и соответствующий план Х не является опорным (базисным). На рис 3.4 показаны два плана
Нахождение начальных опорных плановСуществует несколько методов построения начальных опорных планов Т-задачи. Из них самый распространенный метод северо-западного угла и метод минимального элемента [18]. Метод северо-западного угла. Основную идею метода рассмотрим на конкретном примере. Пусть дана Т-задача с четырьмя пунктами производства А1, А2, А3, А4 с объемами производства Построим матрицу Х размером 4х4, причем для удобства вычислений снизу от нее оставим строку bj, справа столбец ai. Кроме того, снизу от bj образуем строки Заполнение таблицы начинают с левого верхнего элемента таблицы X - x11, что и обусловило название метода. Сравнив Переходим к второй строке и начинаем заполнение с элемента
Таблица 3.2
Формальное описание алгоритма. I. Определяют верхний левый элемент матрицы Х: Возможные три случая: а) если
и все оставшиеся элементы первых столбцов и строки заполняют нулями. Находим на этом один шаг метода заканчивается. 2. Пусть уже проделано k шагов. (k+1)-й шаг состоит в следующем. Определяют верхний левый элемент незаполненной части матрицы Х. Пусть это будет элемент причем
где
Если Метод минимального элемента.Этот метод является вариантом метода северо-западного угла, учитывающим специфику матрицы транспортных затрат С= Формальное описание алгоритма. Элементы матрицы нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу Х0. Пусть элементом с минимальным порядковым номером оказался Дале этот процесс повторяют с незаполненной частью матрицы Х1. Пример 3.1. Найти начальный базисный план методом минимального элемента для Табл. 3.3. следующей задачи. Таблица. 3.3.
Цифры в скобках указывают порядок заполнения элементов в матрице Х0 (табл. 3.4). Соответствующее значение целевой функции равно
Таблица 3.4
|
![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Copyright © 2002-2004 | ![]() |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() |
![]() |