Быстрый поиск

Контрольная работа: Постановка и основные свойства транспортной задачи

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

Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О.Н. Толстым [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.

Пункт потребления Пункт производства	B1	B2	.	Bn	Bj ai
A1	C11	C12	.	C1n	a1
A2	C21	C22	.	C2n	a2
Am	Cm1	Cm2	.	Cmn	am
Ai bj	b1	b2	.	bn	Объем производства Объем потребления

Пусть количество продукта, перевозимого из пункта 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).

Транспортная задача с ограниченными пропускными способностями.

Важной в практическом отношении является Т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 – задачи.

Открытые транспортные модели. Существует ряд практических задач, в которых условие баланса не выполняется. Такие модели называются открытыми. Возможные два случая:

В первом случае полное удовлетворение спроса невозможно.

Такую задачу можно привести к обычной транспортной задаче следующим образом. Обозначим через величину штрафа из-за неудовлетворения запросов на единицу продукта в пункте Bj.

Тогда требуется минимизировать

(1.15)

при условиях

где - неудовлетворенный спрос.

Задачу (3.1.15) приводят к обычной Т-задаче введением фиктивного пункта производства Аm+1, с объемом производства и транспортными издержками В таком случае Т-задача будет иметь вид

минимизировать

при условиях

В найденном решении хопт полагаем все перевозки из фиктивного пункта Аm+1 равными нулю, т.е. .

Рассмотрим теперь второй случай. Введем фиктивный пункт Bn+1 с объемом спроса . Пусть - это убытки (штраф) в пункте Аі за единицу невывезенного продукта. Обозначим через сии,n+1 = удельные транспортные издержки на перевозку единицы продукта с Аі в Вn+1. Тогда соответствующая Т-задача запишется так:

минимизировать (1.16)

при условиях

(1.17) – (1.18)

В найденном решении все перевозки в фиктивный пункт Вn+1 считают равными нулю.

Опорные планы Т-задачи

Опорным (базисным) планом Т-задачи называют любое ее допустимое, базисное решение. Понятие опорного плана имеет наглядную геометрическую интерпретацию.

Последовательность коммуникаций

Страницы: 1, 2, 3, 4, 5