Транспортные задачи

ЦЕЛЬ РАБОТЫ: овладеть методикой построения опорных планов транспортных задач, и их оптимизации.

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ. В общем виде транспортные задачи записываются и решаются в виде таблицы:

Пункт отправления	Пункты назначения	Количество прибывающих туристов
В1	В 2	… Вj	…Вn
А1	c 11 x 11	c 12 x 12	c1j x1j	c1n x1n	a1
А 2	c 21 x 21	c 22 x 22	c 2 j x 2 j	c 2 n x 2 n	а 2
… Аj	c i 1 x i 1	c i 2 x i 2	c ij x ij	c in x in	… ai
…Аm	c m1 x m1	c m 2 x m 2	c mj xmj	c mn x mn	…am
Количество мест размещения	b 1	b 2	… bj	… bn	∑ bj = ∑ ai

c_ij – тарифы на перевозку (стоимость билета), x_ij – количество перевозимых пассажиров.

К задачам закрытого типа относятся такие, у которых суммарное количество прибывающих туристов равно суммарному количеству мест размещения: ∑ a_i = ∑ b_j.

К задачам открытого типа относятся такие, у которых: ∑ a_i ≠ ∑ b_j.

Чтобы решить транспортную задачу открытого типа, необходимо:

1. Если ∑ a_i > ∑ b_j, то вводится дополнительный фиктивный столбец " j +1 " с потребностью b_{j +1} =∑ a_i - ∑ b_j. Чтобы задача не изменилась, тарифы в фиксированном столбце приравниваются к 0, то есть: c_{i(j+ 1 )} = 0.

2. Если ∑ a_i < ∑ b_j, то вводится дополнительная фиктивная строка " i +1" c запасом a_{i +1} = ∑ b_j - ∑ a_i. Чтобы задача не изменилась, тарифы в фиктивной строке приравниваются к 0, то есть c_{(i+ 1 )j} = 0.

МЕТОДИКА РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

С четырех вокзалов необходимо доставить прибывших туристов в три гостиницы. Данные о количестве туристов и мест в гостиницах приведены в табл. 1.

Таблица 1		Таблица 2
Вокзалы	Гостиницы	Кол-во туристов	Вокзалы	Гостиницы	Кол-во туристов
В 1	В 2	В 3	В 1	В 2	В 3	В 4
А 1					А 1
А 2					А 2
А 3					А 3
А 4					А 4
Кол-во мест				180	Кол-во мест

Приводим задачу к "закрытому" типу, то есть когда ∑ a_i > ∑ b_j, вводим дополнительный столбец (табл. 2.)

1. Опорный план в транспортных задачах можно составить с помощью метода "северо-западного" угла и (или) метода "минимального элемента".

Метод «северо-западного угла» Таблица 3,а

	В 1	В 2	В 3	В 4	Кол-во туристов
А 1
А 2				0 +
А 3
А 4		+
Кол-во мет

Заполнение таблицы 3, а начинают с верхней левой клетки (то есть северо-западной клетки). Из оставшихся снова выбирают северо-западную и так далее. Число заполненных клеток должно быть равно (m + n)–1. Если получается количество клеток меньше заполненных, то необходимо из рассмотрения вывести столбец (строку) с равным количеством мест и туристов. Задача решается без этого столбца (строки). На втором шаге он вводится обратно. Таким образом "разбивается" доставка.

Метод минимального элемента. Таблица 3,б

	В 1	В 2	В 3	В 4	Кол-во туристов
А 1
А 2
А 3
А4
Кол-во мест

Заполнение таблицы 3, б начинают с клетки с минимальным тарифом. Если таких тарифов несколько, то выбирают любую клетку, и таким образом поступают на любом последующем шаге. Число заполненных клеток должно быть равно (m + n) – 1.

Определяем стоимость плана (см. табл. 3, а и 3, б). Для этого составим матрицу решения:

А (4x4) = S_a= 740 руб.

B (4x4) =

S_b = 550 руб.

Дальнейший расчет производим по результатам, полученным любым из методов. Возьмем за основу опорный план, полученный методом Северо-западного угла.

2. Проверяем методом потенциалов, является ли опорный план оптимальным.

Теорема: если для некоторого опорного плана X (x_ij), i = 1,… m; j = 1,… n; существуют такие числа α₁, α₂…α _m и β₁, β₂…β _n, что β _j – α _i = с_ij при x_ij >0 и β _j – α _i ≤ с_ij при x_ij = 0, то план X является оптимальным:

α _i – потенциал пунктов отправления;

β _j – потенциалы гостиниц.

Для каждой незаполненной клетки определяется потенциал z_ij;

β _j – α _i – с_ij = z_ij.

Опорный план не является оптимальным, если существует положительный потенциал (не использованный).

Оптимизацию проводят по самому большому утерянному потенциалу.

Для нашего примера опорный план не является оптимальным, так как z ₃₁ =3; z ₃₂ = 9; z ₃₃ = 4; z ₄₁ = 7; z ₄₂ = 13; z ₄₃ = 5.

Для клетки с максимальным потенциалом z ₄₂ выделяем контур пересчета (см. табл. 3,а) и получаем новый опорный план (табл. 4).

Для клетки (z ₄₂) необходимо выделить контур (цикл) пересчета.

Контур пересчета – замкнутая ломаная линия, которая начинается в клетке z_ij > 0 → max. Все точки перегиба контура должны находиться в заполненных клетках, и иметь угол поворота 90⁰. Формальное пересечение не является точкой контура. Каждой вершине контура поочередно присваивают знак «+» и «–». Должно соблюдаться условие: количество «+» равно количеству «–».

Таблица 4

	В 1	В 2	В 3	В 4	Кол-во туристов
А 1
А2
А 3
А 4
Кол-во мест

В данную свободную клетку (z_ij > 0 max) переносят x_ij min из стоящих в «-» клетках. В целях соблюдения баланса перевозок одновременно это число прибавляют к xij, стоящему в «+» клетках и вычитают из x_ij, стоящего в «-» клетках. После этого получаем новый опорный план, для которого существует матрица решения.

Данный, новый опорный план необходимо проверить на оптимальность, то есть повторить методику с пункта 2 и далее.

ЗАДАНИЕ К ПРАКТИЧЕСКОЙ РАБОТЕ.

Необходимо составить план-график доставки туристов из аэропорта в гостиницы (В_j, j=1-). В распоряжении турфирмы есть несколько автобусов (A_i, i=1).

Варианты заданий

1 2

.

В1

В2

В3

В4

Кол.тур.

В1

В2

В3

В4

Кол.тур.

А1

А1

А2

А2

А3

А3

Кол. мест

Кол. мест

3 4

.

В1

В2

В3

В4

.

В1

В2

В3

В4

А1

А1

А2

А2

А3

А3

5 6

.

В1

В2

В3

В4

.

В1

В2

В3

В4

А1

А1

А2

А2

А3

А3

7 8

В1

В2

В3

В4

.

В1

В2

В3

В4

А1

А1

А2

А2

А3

А3

9 10

В1

В2

В3

В4

.

В1

В2

В3

В4

А1

А1

А2

А2

А3

А3

11 12

.

В1

В2

В3

В4

В1

В2

В3

В4

А1

А1

А2

А2

А3

А3

13 14

В1

В2

В3

В4

В1

В2

В3

В4

А1

А1

А2

А2

А3

А3

15 16

.

В1

В2

В3

В4

В1

В2

В3

В4

А1

А1

А2

А2

А3

А3

П

17 18

В1

В2

В3

В4

.

В1

В2

В3

В4

А1

А1

А2

А2

А3

А3

19 20

.

В1

В2

В3

В4

В1

В2

В3

В4

А1

А1

А2

А2

А3

А3

21 22

.

В1

В2

В3

В4

В1

В2

В3

В4

А1

А1

А2

А2

А3

А3

23 24

В1

В2

В3

В4

.

В1

В2

В3

В4

А1

А1

А2

А2

А3

А3

25 26

.

В1

В2

В3

В4

.

В1

В2

В3

В4

А1

А1

А2

А2

А3

А3

27 28

.

В1

В2

В3

В4

В1

В2

В3

В4

А1

А1

А2

А2

А3

А3

29 30

В1

В2

В3

В4

В1

В2

В3

В4

А1

А1

А2

А2

А3

А3

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Какие существуют методы для решения транспортной задачи?

2. Какие задачи называются открытыми, закрытыми?

3. Как привести задачу к закрытому типу?

4. Какой план называется оптимальным?

5. Почему в фиктивном столбце тарифы равны 0?

6. Что такое контур пересчета?

7. Назовите несколько условий для построения контура пересчета?