ЦЕЛЬ РАБОТЫ: овладеть методикой построения опорных планов транспортных задач, и их оптимизации.
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ. В общем виде транспортные задачи записываются и решаются в виде таблицы:
Пункт отправления | Пункты назначения | Количество прибывающих туристов | |||
В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 |
cij – тарифы на перевозку (стоимость билета), xij – количество перевозимых пассажиров.
К задачам закрытого типа относятся такие, у которых суммарное количество прибывающих туристов равно суммарному количеству мест размещения: ∑ ai = ∑ bj.
К задачам открытого типа относятся такие, у которых: ∑ ai ≠ ∑ bj.
Чтобы решить транспортную задачу открытого типа, необходимо:
1. Если ∑ ai > ∑ bj, то вводится дополнительный фиктивный столбец " j +1 " с потребностью bj +1 =∑ ai - ∑ bj. Чтобы задача не изменилась, тарифы в фиксированном столбце приравниваются к 0, то есть: ci(j+ 1 ) = 0.
|
|
2. Если ∑ ai < ∑ bj, то вводится дополнительная фиктивная строка " i +1" c запасом ai +1 = ∑ bj - ∑ ai. Чтобы задача не изменилась, тарифы в фиктивной строке приравниваются к 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 | Кол-во мест |
Приводим задачу к "закрытому" типу, то есть когда ∑ ai > ∑ bj, вводим дополнительный столбец (табл. 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) = Sa= 740 руб.
B (4x4) =
Sb = 550 руб.
Дальнейший расчет производим по результатам, полученным любым из методов. Возьмем за основу опорный план, полученный методом Северо-западного угла.
2. Проверяем методом потенциалов, является ли опорный план оптимальным.
Теорема: если для некоторого опорного плана X (xij), i = 1,… m; j = 1,… n; существуют такие числа α1, α2…α m и β1, β2…β n, что β j – α i = сij при xij >0 и β j – α i ≤ сij при xij = 0, то план X является оптимальным:
α i – потенциал пунктов отправления;
β j – потенциалы гостиниц.
Для каждой незаполненной клетки определяется потенциал zij;
β j – α i – сij = zij.
Опорный план не является оптимальным, если существует положительный потенциал (не использованный).
Оптимизацию проводят по самому большому утерянному потенциалу.
Для нашего примера опорный план не является оптимальным, так как z 31 =3; z 32 = 9; z 33 = 4; z 41 = 7; z 42 = 13; z 43 = 5.
Для клетки с максимальным потенциалом z 42 выделяем контур пересчета (см. табл. 3,а) и получаем новый опорный план (табл. 4).
Для клетки (z 42) необходимо выделить контур (цикл) пересчета.
Контур пересчета – замкнутая ломаная линия, которая начинается в клетке zij > 0 → max. Все точки перегиба контура должны находиться в заполненных клетках, и иметь угол поворота 900. Формальное пересечение не является точкой контура. Каждой вершине контура поочередно присваивают знак «+» и «–». Должно соблюдаться условие: количество «+» равно количеству «–».
Таблица 4
В 1 | В 2 | В 3 | В 4 | Кол-во туристов | |
А 1 | |||||
А2 | |||||
А 3 | |||||
А 4 | |||||
Кол-во мест |
В данную свободную клетку (zij > 0 max) переносят xij min из стоящих в «-» клетках. В целях соблюдения баланса перевозок одновременно это число прибавляют к xij, стоящему в «+» клетках и вычитают из xij, стоящего в «-» клетках. После этого получаем новый опорный план, для которого существует матрица решения.
Данный, новый опорный план необходимо проверить на оптимальность, то есть повторить методику с пункта 2 и далее.
ЗАДАНИЕ К ПРАКТИЧЕСКОЙ РАБОТЕ.
Необходимо составить план-график доставки туристов из аэропорта в гостиницы (Вj, j=1-). В распоряжении турфирмы есть несколько автобусов (Ai, 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. Назовите несколько условий для построения контура пересчета?