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

Имеется m поставщиков , у которых сосредоточен однородный груз в количествах соответственно . Значения именуются мощностями поставщиков. Данный груз нужно распределить между n потребителями , спрос которых равен соответственно . Известна цена перевозки единицы груза от i – го поставщика к j — му потребителю, которую обозначим через .

Нужно отыскать оптимальный замысел перевозок, что:

1) реализует мощности всех поставщиков;

2) удовлетворяет спрос всех потребителей;

3) минимизирует суммарные затраты на перевозку.

Составим экономико-математическую модель транспортной задачи. Для этого составим распределительную таблицу вида:

Спрос потребителей
…… ……
Мощности Поставщиков
……
……
…… …… …… ……. …… ……

……
……
…… …… …… ……… …… ……

……
……

В данной таблице — количество единиц груза, которое нужно доставить от i – го поставщика к j — му потребителю. Матрица, составленная из элементов именуется матрицей перевозок. Матрица, составленная из значений , именуется матрицей тарифов.

Применяя введенные обозначения, возможно записать, что транспортная задача содержится в нахождении для того чтобы замысла перевозок , дабы:

1) мощности всех поставщиков были реализованы, т.е. дабы все поставщики всецело избавились от собственного груза:

(1.1)

2) спрос всех потребителей был удовлетворен:

(1.2)

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

(1.3)

4) суммарная цена перевозок была минимальной:

(1.4)

Так, с математической точки зрения транспортная задача содержится в нахождении значений , удовлетворяющих (1.1)-(1.3), и таких, что функция (1.4) принимает минимальное значение. Несложно подметить, что транспортная задача имеется каноническая задача ЛП.

Определение 1.1. Ответ , удовлетворяющее (1.1)-(1.3), именуется базовым распределением поставок.

Определение 1.2. Базовое распределение поставок, доставляющее минимум функции (1.4), именуется оптимальным распределением поставок.

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

.

В случае если это условие не выполняется, т. е.:

,

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

Открытую транспортную задачу возможно свести к закрытой следующим образом.

В случае если , то открытая транспортная задача сводится к закрытой методом введения фиктивного потребителя со спросом . С экономической точки зрения, нового фиктивного потребителя возможно разглядывать в качестве склада. Коэффициенты в новом столбце, полагают равными 0.

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

Открытую транспортную задачу нужно сводить к закрытой в силу следующей теоремы.

Теорема о существовании допустимого замысла. Транспортная задача имеет допустимое распределение поставок тогда, в то время, когда выполняется следующее равенство:

Число переменных в транспортной задаче с m поставщиками и n потребителями равняется nm, а число уравнений в совокупностях (1.1) и (1.2) равняется n+m. Так как предполагается, что выполняется условие , то число линейных свободных уравнений равняется n+m-1. Следовательно, допустимое ответ транспортной задачи может иметь не более n+m-1 хороших от нуля малоизвестных.

В случае если в допустимом ответе транспортной задачи число ненулевых компонент равняется n+m-1, то ответ именуется невырожденным, а вдруг меньше – то вырожденным.

Как было указано выше, транспортная задача есть канонической задачей линейного программирования, и для ее решения в принципе возможно применять симплекс-способ. Но, в силу специфичности транспортной задачи, употребляются более действенные способы.

Typ


Также читать:

Понравилась статья? Поделиться с друзьями: