Распределительный метод решения транспортной задачи. На 1 курсе д/о во 2 семестре 2011-2012

На 1 курсе д/о во 2 семестре 2011-2012

График проведения семинарских занятий

На 1 курсе д/о во 2 семестре 2011-2012

График чтения лекций по ТГП

Дата	Темы	Часов
30.01.12	Правоотношения
02.02.12	Правоотношения
06.02.12	Реализация норм права
13.02.12	Толкование права
20.02.12	Правомерное поведение
27.02.12	Правонарушения и юридическая ответственность
05.03.12	Право, правосознание, правовое воспитание
12.03.12	Гражданское общество, правовое государство, правовая политика
Итого:

Дата	Темы	Часов
06-11 февр.	Правоотношения
13-18 февр.	Правоотношения
20-25 февр.	Правоотношения
27 февр.-03 март.	Реализация норм права
05-10 марта	Реализация норм права
12-17 марта	Реализация норм права
19-24 марта	Толкование права
26-31 марта	Толкование права
02.-07 апреля	Правомерное поведение
09-14 апреля	Правомерное поведение
16-21 апреля	Правонарушения и юридическая ответственность
23-28 апреля	Правонарушения и юридическая ответственность
30 апр.-5 мая	Право, правосознание, правовое воспитание
07-12 мая	Законность и правопорядок
14-19 мая	Гражданское общество, правовое государство, правовая политика
Итого:

Далее поступаем так, как поступили бы при решении задачи симплекс- методом: переменную , например, коэффициент при которой отрицателен, будем переводить в базисные (основные) переменные. Перевод поставки в свободную клетку вызывает перераспределение поставок (передвижение поставки по циклу).

Циклом в матрице будем называть ломаную с вершинами в клетках и звеньями, лежащими вдоль строк и столбцов матрицы, удовлетворяющую условиям:

· ломаная должна быть связной, т.е. из любой ее вершины мож­но попасть в любую другую вершину по звеньям ломаной;

· в каждой вершине ломаной встречаются два звена, одно из которых располагается по строке, другое — по столбцу.

Циклом пересчета называется такой цикл в таблице с базисным распределением поставок, при котором одна из его вершин лежит в свободной клетке, остальные - в заполненных. Цикл пересчета называется означенным, если в его вершинах расставлены знаки "+" и "-" так, что в свободной клетке стоит знак "+", а соседние вершины имеют противоположные знаки.

Пример 5. Найти оптимальное распределение поставок в задаче 1.

Решение. Начнем с базисного распределения поставок, по­лученного в задаче 3. Как было установлено ранее (см. задачу 4), данное распределение не оптимально. Оценки свободных клеток приведены в (9).

Цикл пересчета для клетки (1,3) показан на рис. 3.

Рис. 3

Увеличиваем поставку в клетке (1,3) до тех пор, пока поставка в одной заполненных клеток не станет равной нулю (дальнейшее увеличение приводит в область недопустимых решений). Эта клетка принадлежит, конечно, циклу, построенному на рис. 3 для клет­ки (1,3).

Найдем ее. Если в клетку (1,3) передать поставку, равную , то поставка в клетках цикла со знаком "+" увеличится на z, а в клетках со знаком "-" - уменьшится на z. Поэтому искомая клетка находится среди клеток цикла, имеющих знак «-» Более того, она имеет минимальную поставку среди таких клеток. Так как min{60,40} = 40 (рис. 3), то в нашем случае - это клетка (3,3), и для обнуления поставки в этой клетке по циклу следует передать 40 единиц груза. Таким образом, поставка, передаваемая по циклу, определяется как минимум среди поставок в клетках цикла со зна ком «-». После этого клетка (1,3) считается заполненной, а клет­ка (3,3) — свободной.

В клетках со знаком "+" цикла поставка увеличивается на пе­редаваемую поставку: поставка клетки (3,2) станет равной 90 еди­ницам, поставка клетки (1,3) - 40 единицам. Аналогично в клет­ках со знаком " - " поставка уменьшится на передаваемую постав­ку, например, поставка клетки (1,2) станет равной 20 единицам, что видно из табл. 12. Нетрудно доказать, что вновь полученное распределение поставок - базисное.

Оптимальность базисного рас­пределения поставок.

Найдем оценки свободных клеток (матрицу оценок) распределе­ния поставок. Для этого, как и прежде, подберем потенциалы так, чтобы коэффициенты затрат заполненных клеток стали равными нулю (табл.12). Тогда матрица оценок примет вид (10).

Табл.12

	20

. (10)

-2

-1

-3

0 0 -3 -1

Так как среди свободных клеток есть клетка (1,1) с отрица­тельной оценкой, то найденное распределение не оптимально и передача поставки в клетку (1,1) ведет к уменьшению суммарных затрат на перевозку. Означенный цикл пересчета для клетки (1,1) приведен на рис. 4. По правилу, сформулированному выше, поставка, передаваемая по циклу = {20, 20, 10}= = 10. Передви­гая эту поставку по циклу (рис. 4), приходим к новому рас­пределению поставок (табл. 13).

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

Рис. 4

Табл. 13

. (11)

Суммарные затраты на перевозку согласно этого распределения поста­вок в денежных единицах составляют:

F_min = 1*10 +2*10 +5*40+1*10 +2*110 + 3*100 = 760.

Замечание 1. Поставка, передаваемая по циклу, не может быть ни меньше, ни больше минимума поставок клеток цикла со знаком " - ". Действительно, в первом случае ни одна из клеток цикла не будет иметь нулевой поставки, а потому общее число заполненных клеток таблицы будет равно и, следователь­но, распределение не будет базисным. Во втором случае ухо­дим в область недопустимых решений.

Замечание 2. Оптимальное распределение поставок, найден­ное в задаче 7 (табл.13), не единственное, так как среди оценок свободных клеток есть нулевые, например клетка (2,3) в матрице (11).

.

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

1.Для данного базисного распределения поставок подбираем потенциалы строк и столбцов таблицы поставок так, чтобы коэф­фициенты затрат заполненных клеток стали равны нулю. Состав­ляем матрицу оценок.

2.Если оценки всех свободных клеток неотрицательны, то найденное распределение оптимально — решение закончено. Ес­ли среди оценок свободных клеток есть отрицательные, то выби­раем одну из них для передачи в нее поставки (для определенно­сти можно брать, например, одну из клеток с наименьшей оцен­кой).

3.Для избранной свободной. клетки строится означенный цикл пересчета. Поставка z, передаваемая по циклу, определяет­ся как минимум среди поставок в клетках со знаком " - ". Най­денная поставка передвигается по циклу. При этом поставка в клетках цикла со знаком "+" увеличивается на z, а в клетках со знаком " - " уменьшается на z. Клетка, поставка в которой при этом станет равной нулю, будет считаться свободной (далее рас­смотрен случай, когда таких клеток несколько), остальные клет­ки цикла — заполненными. Таким образом, получено новое базисное распределение поставок.

4.Переходим к п. 1 алгоритма.

Рассмотрим особые случаи, которые могут возникнуть при ре­шении транспортной задачи.

1.В некоторых случаях поставка, переводимая по циклу, может оказаться равной нулю. Это возможно тогда, когда клетка цикла со знаком "-" содержала нулевую поставку. В этом случае по циклу передается нулевая поставка. В результате та свободная клетка, для которой был построен цикл, становится заполненной (нулевой поставкой), а клетка с нулевой поставкой — свободной.

2.Если при переводе поставки по циклу поставка обращается в нуль сразу в нескольких заполненных клетках, то свободной из них следует считать только одну (любую), остальные клетки, по­ставка в которых стала равной нулю, следует считать заполнен­ными нулевой поставкой. Разберем перечисленные особые случаи на примере.

Пример 8. Завершить решение транспортной задачи из примера 4.

Решение. Установим сначала, оптимально ли распределение поставок, полученное в указанном примере методом "северо-западного" угла (табл. 8). Подберем потенциалы строк и столбцов этой таблицы поставок так, чтобы коэффициенты затрат заполненных клеток стали равны нулю (табл. 14).

Табл. 14

. (12)

-1 -3 -2

Это приводит к матрице оценок (12). Так как среди свободных клеток таблицы есть клетка (3,2) с отрицательной оценкой, то дан­ное базисное распределение поставок не оптимально. Переведем поставку в клетку (3,2) с отрицательной оценкой. Строя для клетки (3,2) означенный цикл пересчета (рис. 5), находим, что объем передаваемой поставки в данном случае равен х ₃₂ =min{0,10}= 0. Передавая по построенному циклу нулевую поставку, приходим к новому базисному распределению (табл. 15).

Рис. 5

Табл. 15

. (13)

-2

1 -1 -2

Подбирая потенциалы к строкам и столбцам табл. 15, нахо­дим матрицу (13) оценок данного распределения. Так как среди свободных клеток таблицы есть клетка (1,3) с отрицательной оценкой, то данное базисное распределение не оптимально. Най­дем новое базисное распределение, передавая поставку в клетку (1,3) с отрицательной оценкой. Построим цикл для клетки (1,3), показанный на рис. 6.

Поставка, передаваемая в клетку (1,3): При передаче по циклу (рис. 6) 10 еди­ниц груза станут равными нулю поставки в клетках (1,2) и (3,3). Полагаем, что только одна из них стала свободной, например клетка (3,3), а клетка (1,2) заполнена нулевой поставкой. Таким образом, будет получено базисное распределение поставок, пред­ставленное в табл. 16.

Рис. 6

Табл. 16

. (14)

-1

0 -2 -2

Определяя матрицу оценок (14), видим, что среди оценок свободных клеток найденного распределения нет отрицательных, т.е. найденное распределение (табл. 16) оптимально.

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

Открытая транспортная задача решается сведением ее к закры­той транспортной задаче.

Пример 9. Найти оптимальное распределение поставок для транспорт­ной задачи (табл. 17).

Табл. 17 Табл. 18

Решение. В данном случае суммарный спрос потребителей больше, чем суммарное предложение поставщиков (45+35+55+ +65 = 200 > 40+60+90 = 190). Введем "фиктивного поставщика" и в таблицу поставок добавим дополнительную строку (табл. 18) так, чтобы задача стала закрытой. Для этого мощность фиктивно­го поставщика следует принять равной 10 = 200—190. Коэффици­енты затрат этой добавленной строки определяются издержками ввиду недогрузки мощностей потребителей. Если информация об этих издержках отсутствует, то их принимают равными одному и тому же числу (например, нулю, как в табл. 18). Согласно тео­реме 3, конкретное значение этого числа не влияет на опти­мальное распределение поставок.

Первоначальное распределение поставок для сформулиро­ванной закрытой транспортной задачи найдем, например, по методу наименьших затрат. Для удобства укажем последова­тельность заполнения таблицы поставок: . В результате приходим к следующему базисному распределению поставок (табл. 19).

Табл.19

. (15)

-2

-3

-4

-2

0 1 0 2

Установим, оптимально ли это распределение - найдем для него матрицу оценок (15). Так как среди оценок свободных кле­ток есть отрицательные, то найденное распределение не опти­мально. Переведем поставку в одну из клеток с наименьшей от­рицательной оценкой, например в клетку (4,3). Цикл для этой клетки изображен на рис 7. Поставка, передаваемая по циклу, равна х₄₃ = min {50, 35, 10} = 10. Передвигая по циклу поставку, равную 10 единицам, приходим к следующему распределению поставок (табл. 20).

Найдем оценки свободных клеток данного распределения (20). Так как оценки всех свободных клеток неотрицательны, то распределение поставок табл. 20 оптимальное.

Рис. 7

Табл. 20

. (16)

В случае, когда суммарная мощность поставщиков больше суммарной мощности потребителей, в рассмотрение вводится "фиктивный потребитель", а к таблице поставок присоединяется дополнительный столбец. Коэффициенты затрат этого добавлен­ного столбца соответствуют затратам на хранение неотправленного груза (поставки последнего столбца – неотправленный груз для каждого из поставщиков). Если информация об этих затратах отсутствует, то их принимают равными какому-либо значению (например, нулю).

Дата добавления: 2014-01-05