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

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

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

Очевидно

Так как

, то

, отсюда

 Скачать реферат