Транспортная задача с ограничениями на пропускную способность
Транспортная задача
Задача коммивояжера
Задача о назначениях
Метод Гомори
Симплекс-метод
Распределительный метод
Метод потенциалов
Метод Фогеля
Открытые и закрытые задачи
Новое на сайте
Задачи параметрического программирования
Критерий Манна-Уитни
Интервалы возрастания и убывания функции
Коэффициент контингенции
Коэффициент конкордации
Смешанное произведение векторов
Метод Фибоначчи

Транспортная задача линейного программирования


Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Формулировка транспортной задачи


Однородный груз сосредоточен у k поставщиков в объемах a 1 , а2,..., а k. Данный груз необходимо доставить и потребителям в объемах b1, b2, ..., bn. Известны сiji= 1, 2, ..., k и  j = 1, 2, ..., n — стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех поставщиков будут вывезены полностью, запросы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны.
Исходные данные транспортной задачи обычно записываются в таблицу –

 

b 1

b 2


bn

a 1

с 11

с 12

 

с 1n

a2

с 21


 

с 2n






ak

с k1



с kn

Исходные данные задачи могут быть представлены также в виде вектора запасов поставщиков А = (a1, а2,..., аk), вектора запросов потребителей В= (b1, b2, ..., bn) и матрицы стоимостей C={сij}

В транспортных задачах под поставщиками и потребителями понимаются различные промышленные и сельскохозяйственные предприятия, заводы, фабрики, склады, магазины и т.д. Однородными считаются грузы, которые могут быть перевезены одним видом транспорта. Под стоимостью перевозок понимаются тарифы, расстояния, время, расход топлива и т.п.

Математическая модель транспортной задачи


Переменными (неизвестными) транспортной задачи являются xij ..,i-(=1,2, ..., k), j= 1,2, ..., n — объемы перевозок от каждого i -го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок:

или

 

a 1

a2


an

b 1

x 11

x 12

 

x 1n

b 2

x 21


 

x 2n






bk

x k1



x kn

Так как произведение cijxij . определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция задачи имеет вид:

Система ограничений задачи состоит из двух групп уравнений. Первая группа из k уравнений описывает тот факт, что запасы всех k поставщиков вывозятся полностью:

Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех nпотребителей:

Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:




В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.

Такая задача называется задачей с правильным балансом, а ее модель — закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель — открытой.
Математическая формулировка транспортной задачи такова: найти переменные X =(xij ) задачи удовлетворяющие системе ограничений:

условиям неотрицательности и обеспечивающие минимум целевой функции.

Математическая модель транспортной задачи может быть записана в векторном виде. Для этого рассмотрим матрицу A системы уравнений-ограничений задачи.

Сверху над каждым столбцом матрицы указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы ограничений. Каждый столбец матрицы A, соответствующий переменной хij.., является вектором-условием задачи и обозначается через Aij. Каждый вектор имеет всего k+ n координат, и только две из них, отличные от нуля, равны единице. Первая единица вектора Aij стоит на i-м месте, а вторая - на (k+j)-м  месте, т.е.

Таким образом в векторной форме задача будет выглядеть так:

Пример. Составить математическую модель транспортной задачи, исходные данные которой приведены в таблице:

 

20

30

40

40

3

5

7

50

4

6

10

Решение. Введем переменные задачи (матрицу перевозок)

x11

x12

x13

x21

x22

x23

Запишем матрицу стоимостей

Целевая функция задачи равна сумме произведений всех соответствующих элементов матриц С и X:
F(X )=3 x 11 +5 x 12 +7x13+4x21+6x22+10x23.
Данная функция, определяющая суммарные затраты на все перевозки, должна достигать минимального значения.
Составим систему ограничений задачи. Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам 1-го поставщика, а сумма перевозок во второй строке матрицы X — запасам 2-го поставщика. Следовательно:
x11  + x 12 + x 13 = 40;       и х21 + х22 + х23 = 50.
Это означает, что запасы поставщиков вывозятся полностью.
Суммы перевозок, стоящих в каждом столбце матрицы X, должны быть равны запросам соответствующих потребителей:
x11  + x 21 = 20; x 12 + x22= 30; и х31 + х32 = 40.
Это означает, что запросы потребителей удовлетворяются полностью.
Необходимо также учитывать, что перевозки не могут быть отрицательными:
х ij ≥ 0 , i = 1, 2,    j= 1,2,3.
Следовательно, математическая модель рассматриваемой задачи такова: найти переменные задачи, обеспечивающие минимум функции:

и удовлетворяющие системе ограничений

 \2

и условиям неотрицательности х ij ≥0, (i= 1, 2;    j=l,2,3 ).
Необходимое и достаточное условия разрешимости транспортной задачи
Теорема 6.1. Для того чтобы транспортная задача линейного программирования имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей:

т.е. задача должна быть с правильным балансом.
Доказательство . Необходимость. Пусть задача имеет допустимое решение

Докажем, что . Подставив X0 в уравнения системы огра ничений (6.2), (6.3), получим

Просуммируем первую и вторую группы тождеств по отдельности:

Отсюда следует, что задача имеет правильный баланс
Достаточность. Пусть задача имеет правильный баланс

Докажем, что в этом случае задача имеет оптимальное решение.
Сначала покажем, что область допустимых решений задачи – непустое множество. Легко проверить, что

является допустимым решением. Подставив X 0 в левые части уравнений получим

т. е. уравнения обращаются в тождества. Очевидно, что  X 0  удовлетворяет и условиям неотрицательности.
Далее покажем, что существует оптимальное решение. Учитывая, что стоимости перевозок  единиц груза ограничены сверху и снизу  C≤cij≤ D;      i=1,2,…,k;        j=1,2,…,n, где C и D — конечные постоянные, можно записать

X &..

Следовательно, целевая функция ограничена на множестве допустимых решений и, как всякая непрерывная функция, достигает своего наименьшего (а также и наибольшего) значения. Теорема доказана полностью.
Свойство системы ограничений транспортной задачи
□ Теорема 6.2. Ранг системы векторов-условий транспортной задачи равен N = k+ n- 1. Доказательство. Как известно из линейной алгебры для нахождения базиса системы векторов A1А2, ..., Аn необходимо составить однородную систему уравнений
A1 x 12 x 2 + ... Аn x 2 = θ.
(здесь θ - нулевой вектор)
Эту систему с помощью преобразований Жордана приводят к равносильной разрешенной; в базис включают векторы, соответствующие разрешенным неизвестным. Ранг системы векторов равен числу векторов, входящих в базис, т.е. числу разрешенных неизвестных этой системы. Системе векторов-условий транспортной задачи Aij., i = 1, 2, ..., k;    j = 1, 2, ..., n соответствует однородная система уравнений

где θ = (0, 0, ..., 0) T — нулевой вектор (транспонированный).
Запишем матрицу этой системы (она является также матрицей системы ограничений транспортной задачи):

Если к последней строке (уравнению) прибавить ( n - 1) строку (уравнение), начиная с (k + 1)-й, и вычесть первые k строк, то получится строка, состоящая из нулей. Это значит, что число разрешенных неизвестных в этой системе и ранг r системы векторов-условий не могут быть равны числу k + n уравнений. Следовательно, r< k+ n- 1.
Покажем, что найдутся N = k + n - 1 линейно независимых векторов-условий.   Из векторов-условий задачи выберем следующие:
A 1 n А2 n , ..., Аkn A 11 А12, ..., А1( n -1)  и убедимся, что они линейно независимы. Для этого составим систему уравнений
A1n x 1 n2nx2n+…+ Akn xkn12 x 12 + ... А1(n-1) x 1( n -1) = θ.

т

Матрица этой системы, как легко показать, приводится к единичной. Следовательно система уравнений имеет единственное нулевое решение x1n= x2n= … = xkn = x11= x12=…= x1(n-1)=0,а система векторов линейно независима. Теорема доказана.
Все права защищены и охраняются законом. Copyright © ООО Новый семестр 2006-2013 Линейное программирование онлайн