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

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

Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О.Н. Толстым [18; 59].

Первая строгая постановка Т-задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее называют проблемой Хичкока.

Первый точный метод решения Т-задачи разработан Л.В. Канторовичем и М.К. Гавуриным.

Постановка Т-задачи. Пусть в пунктах А₁,…, A_m производят некоторый однородный продукт, причем объем производства в пункте A_i составляет a_i единиц, i = 1,…, m. Допустим, что данный продукт потребляют в пунктах B₁., B_n, a объем потребления в пункте В_j составляет b_j одиниць j = 1., n. Предположим, что из каждого пункта производства возможно транспортировка продукта в любой пунктпотребления. Транспортные издержки по перевозке единицы продукции из пункта A_i в пункт В_j равны c_ij (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	Объем производства Объем потребления

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

Отрезок A_iB_j называют коммуникацией. На всех коммуникациях ставят величины перевозок x_ij.

Вектор P_ij, компоненты которого состоят из коэффициентов при переменных x_ij в ограничениях (3.1.1) и (3.1.2), называют вектором коммуникаций:

Вводят также вектор производства-потребления P₀, где

.

Тогда ограничение (3.1.1) и (3.1.2) можно записать в векторной форме

, (1.5)

Свойства транспортной задачи