SHPORA.net :: PDA

[ Back ]

С помощью рассмотренных методов построения первоначального опорного плана можно получить вырожденный или невырожденный опорный план. Построенный план транспортной задачи как задачи линейного программирования можно было бы довести до оптимального с помощью симплексного метода. Однако из-за громоздкости симплексных таблиц, содержащих mn неизвестных, и большого объема вычислительных работ для получения оптимального плана используют более простые методы. Наиболее часто применяются метод потенциалов (модифицированный распределительный метод) и метод дифференциальных рент.

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

Теорема 12.2 (критерий оптимальности). Для того чтобы допустимый план перевозок в транспортной задаче был оптимальным, необходимо и достаточно, чтобы существовали такие числа и , что

(12.4)

(12.5)

Числа и называют потенциалами пунктов отправления и назначения соответственно.

Сформулированная теорема позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Пусть одним из рассмотренных выше методов найден опорный план. Для этого плана, в котором m + n – 1 базисных клеток, можно определить потенциалы и так, чтобы выполнялось условие (12.4). Поскольку система (12.4) содержит m + n – 1 уравнений и m + n неизвестных, то одну из них можно задать произвольно (например, приравнять к нулю). После этого из m + n – 1 уравнений (12.4) определяются остальные потенциалы и для каждой из свободных клеток вычисляются величины . Если оказалось, что , то план оптимален. Если же хотя бы в одной свободной клетке , то план не является оптимальным и может быть улучшен путем переноса по циклу, соответствующему данной свободной клетке.

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

Процесс улучшения плана продолжается до тех пор, пока не будут выполнены условия (12.5).

Пример. На три базы поступил однородный груз, который требуется перевезти в четыре пункта назначения . Тарифы перевозок, запасы и потребности указаны в таблице 12.3. Спланировать перевозки так, чтобы их общая стоимость была минимальной.

Таблица12.3

Пункты

отправления Пункты назначения Запасы



7 8 1 2 160

4 5 9 8 140

9 2 3 6 170

Потребности 120 50 190 110

Имеем задачу с правильным балансом, так как суммарный объем запасов (470) равен суммарному объему потребностей (470).

Пусть – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения.

Составим математическую модель задачи:



при условиях



Для определения опорного плана воспользуемся методом северо-западного угла, методом наименьшей стоимости (минимального элемента) и методом двойного предпочтения.

1. Метод северо-западного угла.

Процесс получения плана можно оформить в виде таблицы:

Запасы

120 40 – – 160 40 0 0 0 0

– 10 130 – 140 140 140 130 0 0

– – 60 110 170 170 170 170 170 0

Потребности 120 50 190 110

0 50 190 110

0 10 190 110

0 0 190 110

0 0 60 110

0 0 0 0

План – невырожденный, .

2. Метод наименьшей стоимости.

Запасы

7

– 8

– 1

160 2

– 160 0 0 0 0 0

4

120 5

– 9

– 8

20 140 140 140 140 20 0

9

– 2

50 3

30 6

90 170 170 120 90 90 0

Потребности 120 50 190 110





120 50 30 110

120 0 30 110

120 0 0 110

0 0 0 110

0 0 0 0

План – невырожденный, .

3. Метод двойного предпочтения.

Запасы

7

– 8

– vv1

160 v2

– 160 0 0 0 0 0

vv4

120 5

– 9

– 8

20 140 140 140 20 20 0

9

– vv2

50 3

30 6

90 170 170 120 120 90 0

Потребности 120 50 190 110





120 50 30 110

120 50 30 110

120 0 30 110

0 0 0 110

0 0 0 0

План – невырожденный, .

Проверим план на оптимальность методом потенциалов.

Добавим в распределительную таблицу столбец и строку :



7

8

1

160 2



4

120 5

9

8

20

9

2

50 3

30 6

90

Составим систему уравнений , , для занятых клеток:



Предположим, что =0, тогда =1, =2, =0, =4, =4, =0.

Составим матрицу косвенных тарифов



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

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

7

8

1

160 – * 2

+

4

120 5

9

8

20

9

2

50 3

30 + - 6

90



Вершины цикла помечаем знаками (+) и (–), начиная с (+) в свободной клетке.

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

В результате получаем невырожденный план , .

Проверим план на оптимальность.

Добавим в распределительную таблицу столбец и строку :



7

8

1

70 2

90

4

120 5

9

8

20

9

2

50 3

120 6



Найдем значения потенциалов из системы уравнений



Пусть =0, тогда =1, =2, =2, =0, =6, =-2.

Составим матрицу косвенных тарифов

.

и сравним ее элементы с элементами матрицы тарифов.

Получили, что , следовательно, план не оптимален.

Перераспределим перевозки, осуществив поставку груза со второй базы второму потребителю. Для этого строим цикл с началом в клетке (2; 2):

7

8



1

70 – 2

90 +

4

120 + 5

* 9

– 8

20

9

- 2

50 + 3

120 6



.

Составляем новый план . Затраты на перевозку по данному плану составят .

Проверим план на оптимальность.



7

8

1

50 2

110

4

120 5

20 9

8



9

2

30 3

140 6



Значения потенциалов найдем из системы



Пусть =0, тогда =1, =2, =2, =0, =5, = –1.

Составим матрицу косвенных тарифов и сравним ее с матрицей тарифов:

.

Так как , , , то план является оптимальным и минимальные затраты на перевозку составляют 1330 у.е.

Ответ: , .

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

Найдем первоначальный опорный план данной задачи методом аппроксимации Фогеля.

Запасы Столбец-разность

7

– 8

– 1

50 2

110 160 1 <6> к

4

120 5

20 9

– 8

– 140 1 1 1 1 1

9

– 2

30 3

140 6

– 170 1 1 1 <7> к

Потребности 120 50 190 110

Строка-

разность 3 3 2 <4>

3 3 2 к

5 3 <6>

5 3 к

к к





План – невырожденный: , в данной задаче он является оптимальным.