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

 

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

Поставщики находятся от потребителей на различном расстоянии.

Количество продукции в цехах-изготовителях будем именовать мощностью.

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

 

 

20.1 МАТЕМАТИЧЕСКАЯ ФОРМУЛИРОВКА ТРАНСПОРТНОЙ ЗАДАЧИ.

 

Пусть заданы векторы S_i, D_j и c_ij, где

S_i – мощность i-го цеха-изготовителя (i=1,…,m);

D_j – спрос j-го цеха-потребителя (j=1,…, n);

c_ij – расстояние между каждым i-м поставщиком и j-м потребителем;

m – количество поставщиков;

n – количество потребителей.

Необходимо найти неизвестные показатели х_ij – количество продукции, перевозимой от поставщиков к потребителю (обратите внимание, что многие показатели х_ij могут принимать нулевые значения).

Запомните:

Элементы матрицы c_ij называются критериями оптимальности.

Совокупность всех элементов матрицы х_ij называются планом перевозки.

 

Проверьте себя:

Правильны ли следующие утверждения?

1. Векторы S и D называют критериями оптимальности.

2. Элементы c_ij называют планом перевозки.

3. Элементы х_ij называют планом перевозки.

4. Элементы c_ij называют критериями оптимальности.

5. Показатели х_ij > 0.

6. Показатели х_ij < 0.

7. Показатели х_ij > 0.

8. Неизвестными являются показатели х_ij.

9. Неизвестными являются показатели с_ij.

10. Неизвестными являются показатели S_i и D_j.

Рассмотрим условия задачи с помощью таблицы.

Поставщики и их мощность	Потребители и их спрос
D1	…	Dj	…	Dn
d1	…	dj	…	dn
S1	s1	с11 х11	…	с1j х1j	…	с1n х1n
…	…	…	…	…	…	…
Si	si	ci1 xi1	…	cij хij	…	cin хin
…	…	…	…	…	…	…
Sm	sm	cm1 хm1	…		…	cmn хmn

 

 

1. Каждый поставщик должен отдать потребителям столько продукции, сколько у него есть. Это значит, что сумма поставок по строке должна быть равна мощности этой строки, т.е.

Таких соотношений столько, сколько строк в таблице.

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

Таких соотношений столько, сколько столбцов в таблице.

3. Поскольку полная сумма не зависит от того, как производилось суммирование (по строкам или по столбцам), то сумма мощностей производителя должна быть равна суммарному спросу всех потребителей, т.е.

4. Требуется составить такой план перевозок, при котором грузооборот будет минимальным

Этот план называется оптимальным.

5. Показатели мощностей и спросов должны принимать неотрицательные значения, т.е.

S_i > 0 и d_j > 0.

6. Отрицательных поставок быть не должно, т.е.

х_ij > 0.

 

 

7. К показателям c_ij с математической точки зрения не предъявляется требование неотрицательности. Это вытекает из здравого смысла, т.е.

c_ij > 0.

Проверьте себя:

Какие утверждения являются неправильными?

1. Потребитель получает всю продукцию первого же поставщика.

2. Соотношений должно быть столько, сколько столбцов в матрице задачи.

3. Соотношений должно быть столько, сколько столбцов в матрице задачи.

4. Функция цели формулируется следующим образом:

5. Показатели S_i и d_j должны быть неотрицательными.

6. Поставки х_ij должны быть неотрицательными.

 

Запомните:

Количество неизвестных в задаче равно m×n.

Количество уравнений равно m + n.

Одно (любое) уравнение линейно зависимо от остальных.

Количество линейно независимых уравнений равно m + n - 1.

 

 

20.2 БАЗИСНОЕ РАСПРЕДЕЛЕНИЕ В ТРАНСПОРТНОЙ ЗАДАЧЕ

 

Чтобы получить оптимальный план, необходимо в первую очередь получить базисное распределение плана (перевозок). Базисный план должен быть как можно более приближенным к оптимальному.

Существует несколько способов его составления.

СПОСОБ СЕВЕРО-ЗАПОДНОГО УГЛА

Чтобы воспользоваться этим способом, необходимо заполнить таблицу, начиная от левого верхнего угла и кончая нижним правым углом.

Посмотрим, как это делается, на примере.

Условия задачи представлены в таблице.

Поставщики и их мощность	Потребители и их спрос
D1	D2	D3	D4
S1
S2
S3
S4
S5

 

 

Начинаем заполнять таблицу с клетки S₁ - D₁ (20).

Поставщики и их мощность	Потребители и их спрос
D1	D2	D3	D4
S1		20
S2
S3
S4
S5

 

 

Затем последовательность заполнения выглядит следующим образом:

S₁ - D₁ (25); S₂ – D₂ (5); S₃ – D₂ (40); S₄ – D₂ (10); S₄ – D₂ (10); S₄ – D₃ (40);

S₅ – D₃ (11); S₅ – D₄ (49).

Проверьте себя.

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

Вариант 1

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

 

 

Вариант 2

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

Вариант3

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

 

 

Вариант 4

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

 

СПОСОБ НАИМЕНЬШЕГО ЭЛЕМЕНТА В СТОЛБЦЕ (СТРОКЕ)

Чтобы воспользоваться этим способом, необходимо поочередно в столбцах (строках) матрицы заполнить клетки, соответствующие минимальным значениям c_ij.

Если при записи спрос по столбцу (или мощность по строке) удовлетворен не полностью, ищем следующий по величине элемент в данном столбце (строке). Такие операции проводятся до полного удовлетворения спроса. После этого переходят к следующему столбцу (строке).

 

Обратите внимание:

Если в столбце (строке) два или несколько одинаковых по величине показателей c_{t j}, то для составления плана перевозки может быть взят любой из них.

В качестве примера заполним (построчно) методом наименьшего элемента таблицу с предыдущего примера. Заполнение начинаем с клетки S₅- D₁ (45).

 

Поставщики и их мощность	Потребители и их спрос
D1	D2	D3	D4
S1
S2
S3
S4
S5

 

Затем последовательность заполнения выглядит следующим образом:

S₁ – D₂ (20); S₂ – D₂ (30); S₅ – D₂ (5); S₅ – D₃ (10); S₃-D₃ (40); S₄ – D₃ (1); S₄ – D₄ (49).

 

Проверь себя.

Перепишите в тетрадь условия задачи и составьте опорный план способом наименьшего элемента в столбце (строке).

Вариант 5

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

Вариант 6

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

Вариант 7

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

Вариант 8

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

 

 

СПОСОБ НАИМЕНЬШЕГО ЭЛЕМЕНТА В МАТРИЦЕ

Чтобы воспользоваться этим способом, необходимо поочередно во всей матрице заполнять клетки, соответствующие минимальным значениям c_tj. Для этого находят наименьший элемент c_{t j} и матрице приносят в эту клетку первую поставку x_tj, затем наименьший из оставшихся и т.д.

Вновь рассмотрим таблицу с предыдущего примера. Начинаем заполнять ее способом наименьшего элемента в матрице с клетки S₁ – D₂ (20)

 

Поставщики и их мощность	Потребители и их спрос
D1	D2	D3	D4
S1
S2
S3
S4
S5

 

Затем последовательность заполнения клеток выглядит следующим образом:

S₂ – D₃ (30); S₅ – D₃ (21); S₅ – D₁ (39); S₄ – D₁ (6); S₃ – D₄ (40); S₄ – D₄ (9); S₄ – D₂ (35).

 

Проверь себя.

Перепишите в тетрадь условия задачи и составьте первый опорный план способом наименьшего элемента в матрице.

Вариант 9

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

Вариант 10

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

Вариант 11

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

Вариант 12

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

Запомните:

При составлении первого спорного плана возможен случай вырождения. Он возникает, когда все условия выполнены, а число элементов x_tj будет меньше числа m+n-1.

Чтобы избежать вырождения, необходимо внести фиктивную (нулевую) поставку.

В качестве примера рассмотрим опорный план, составленный методом Северо-Западного угла.

Количество заполненных клеток должно быть равно

m+n-1=4+4-1=7

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

 

В нашем примере его число равно 6, т.е. мы имеем дело со случаем вырождения. Чтобы устранить его, вводим фиктивную (нулевую) поставку в любую из свободных клеток, например в клетку S₂ – D₄. Тогда наш опорный план будет иметь вид

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос

 

Примечание

Если опорный план составлен методом «наименьшего элемента в строке (столбце)» или «наименьшего элемента в матрице», то фиктивную поставку следует вводить, в пустую клетку, которая содержит очередное минимальное значение критерия. С помощью такой простой процедуры мы избавимся от случая вырождения.

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

В этом случае задача называется открытой транспортной задачей.

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

Рассмотрим задачу по таблице.

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
Спрос					160\120

Из условия задачи видно, что суммарная мощность меньше суммарного спроса на 40 (160-120=40),т.е. мы имеем дело с открытой транспортной задачей.

Чтобы ее закрыть, введем в условия задачи фиктивного поставщика S₅. Его мощность будет равна 40 т.к. в действительности такого поставщика не существует, то мы в праве считать, что расстояние до него от каждого потребителя будет равно 0.

После такого преобразования условия задачи будут выглядеть следующим образом:

	D1	D2	D3	D4	Мощность
S1
S2
S3
S4
S5
Спрос

 

Проверь себя.

1. Можно ли избежать вырождения?

2. Количество заполненных клеток должно быть равно m+n?

3. Количество заполненных клеток должно быть равно m+n-1?

4. Что делать, если суммарный спрос превышает суммарные запасы?

 

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

Для этой цели воспользуемся методом потенциалов.