Смекни!
smekni.com

Постановка и основные свойства транспортной задачи (стр. 1 из 7)

Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О.Н. Толстым [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 Bjai
A1 C11 C12 . C1n a1
A2 C21 C22 . C2n a2
Am Cm1 Cm2 . Cmn am
Aibj 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, что