logo

Решение контрольных по математике!!!

Home Методички по математике Линейное программирование 29. Метод потенциалов решения транспортной задачи

29. Метод потенциалов решения транспортной задачи

Для транспортной задачи (ТЗ), как и для любой ЗЛП, существует двойственная к ней задача.

Исходная задача:

; (6.6)

; (6.7)

; (6.8)

. (6.9)

Обозначим двойственные переменные для каждого ограничения вида (6.7) через Ui (i = 1,..., m) и вида (6.8) – Vj (j = 1,..., n), тогда двойственная задача имеет вид

; (6.10)

. (6.11)

Переменные задачи, двойственной к транспортнoй, Ui и Vj называют потенциалами.

Теорема 6.3. Для оптимальности плана X = (Xij)m*n ТЗ необходимо и достаточно существования чисел (потенциалов) V1, V2,..., Vn и U1, U2,..., Um, таких, что:

для i = 1,..., m, j = 1,..., n;

, если Xij > 0.

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

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

; (6.12)

Б) для каждой незанятой клетки (Xij = 0) сумма потенциалов должна быть меньше или равна стоимости перевозки единицы груза

. (6.13)

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

, Xij > 0.

Систему потенциалов можно построить только для невырожденного опорного плана. Такой план содержит m + n – 1 занятых клеток, поэтому для него можно составить систему из m + n – 1 линейно-независимых уравнений вида (6.12) с неизвестными Ui и Vj. Уравнений на одно меньше, чем переменных, поэтому система является неопределенной и одному неизвестному (обычно Ui) придают нулевое значение. После этого остальные потенциалы определяются однозначно.

Проверка выполнения условия оптимальности для незанятых клеток

Просматриваем строки и для каждой незанятой клетки проверяем выполнения условия (6.13), т. е. суммируем потенциалы тех строк и столбцов, на пересечении которых стоит незанятая клетка. Если для всех незанятых клеток Ui + Vj ≤ Cij, то по теореме (6.3) проверяемый план является оптимальным. Если для некоторых клеток Ui + Vj > Cij, то план является неоптимальным. Тогда для каждой клетки, в которой не выполняется условие оптимальности, находим величину (Ui + Vj) – Cij > 0.

Выбор клетки, в которую необходимо поместить перевозку

Загрузке подлежит в первую очередь клетка, которой соответствует

Max((Ui + Vj) – Cij).

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

Для определения количества единиц груза, подлежащих перераспределению, отмечаем знаком «+» незанятую клетку, которую надо загрузить. Это означает, что клетка присоединяется к занятым клеткам. Занятых клеток стало m + n, поэтому появляется цикл, все вершины которого за исключением клетки, отмеченной знаком «+», находятся в занятых клетках, причем этот цикл единственный. Отыскиваем цикл и, начиная движение от клетки, отмеченной знаком «+», поочередно проставляем знаки «–» и «+». Затем находим = min Xij, где Xij – перевозки, стоящие в вершинах цикла, отмеченных знаком «–». Величина определяет, сколько единиц груза можно перераспределить по найденному циклу. Значение записываем в незанятую клетку, отмеченную знаком «+». Двигаясь по циклу, вычитаем из объемов перевозок, расположенных в клетках, которые отмечены знаком «–», и прибавляем к объемам перевозок, находящихся в клетках, отмеченных знаком «+». Если соответствует несколько минимальных перевозок, то при вычитании оставляем в соответствующих клетках нулевые перевозки в таком количестве, чтобы во вновь полученном опорном плане занятых клеток было m + n – 1.

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

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

Пример 6.1. Решить ТЗ:

5 4 6 3 200

1 10 2 1 300

2 3 3 1 100

150 150 250 50 600

600

Условие баланса выполнено. Следовательно, имеем ТЗ закрытого типа.

Предварительный этап: находим исходный опорный план X° методом «минимального элемента».

Таблица 6.1

100

100

200

150

150

300

50

50

100

150

150

250

50

Число занятых клеток равно 6 и совпадает с рангом матрицы ограничений ТЗ:

R = m + n – 1 = 3 + 4 – 1 = 6.

Итерация 1. Для проверки полученного опорного плана на оптимальность находим систему потенциалов для занятых клеток (xij > 0).

Для этого, например, полагаем U1 = 0 (записываем U1 = 0 слева в табл. 6.2).

Таблица 6.2

Vj

Ui

V1 = 5

V2 = 4

V3 = 6

V4 = 2

U1 = 0

5

100+

100–

2

200

U2 = –4

150–

0

150+

–2

300

U3 = –1

4

50–

5

50

100

150

150

250

50

Далее, исходя из занятых клеток (1,2) и (1,3), находим V2 = 4 – 0 = 4, V3 = 6 – 0 = 6 (записываем сверху в таблице). На основе базисной клетки (2,3) получаем U2 = 2 – 6 = –4, затем V1 = 1 – (–4) = 5; U3 = 3 – 4 = –1; V4 = 2.

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

U3 + V1 = 4 > 2,

U3 + V3 = 5 > 3,

То полученный опорный план не оптимальный. Так как

D31 = U3 + V1 – Cij = 2 = D33,

То в любую из клеток, например, в (3,1), проставляем некоторое число .

Для того чтобы не нарушился баланс в 3-й строке, вычитаем из величины перевозки, стоящей в клетке (3,2), прибавляем к X12 = 100, вычитаем от X13, прибавляем к X23 и вычитаем от X21, т. е. составляем цикл:

(3,1) → (3,2) → (1,2) → (1,3) → (2,3) → (2,1) → (3,1).

Знаки «+» и «–» в клетках чередуются.

Заметим, что движение от одной клетки к другой происходит только по занятым, кроме первой, в которую проставляется. Максимальное значение равно наименьшему уменьшаемому: = 50. Если взять больше, то получаем отрицательную величину в плане перевозок, а если меньше, то нарушается опорность плана.

Новый опорный план приведен в табл. 6.3

Таблица 6.3

Vj

Ui

5

4

6

4

5

 

4

 

3

 

6

 
0

5

150

50-

4 q2

1

 

2

 

3

 

10

 

1

 

1

 

3

 

2

 
–4

100-

0

200+

0

–3

50+

1

3

50-

Итерация 2. Проверяем полученный план X(1) на оптимальность. Находим систему потенциалов (они записаны в таблице слева и сверху). Вычисляем сумму потенциалов для свободных клеток (записаны в левом верхнем углу клетки). Так как

U1 + V4 = 4 > 3,

То план X(1) не является оптимальным. Для построения нового опорного плана проставляем величину в клетку (1,4) и составляем цикл:

(1,4) → (3,4) → (3,1) → (2,1) → (2,3) → (1,3) → (1,4).

Определяем значение = 50, при этом две клетки (1,3) и (3,4) обращаются в нулевые. Следовательно, план Х(2) будет вырожденным. Для дальнейшего решения необходимо оставить нуль в одной из клеток и считать ее за базисную. Целесообразнее нуль оставить в клетке с меньшей стоимостью перевозок, т. е. в клетке (3,4). Новый опорный план приведен в табл. 6.4.

Таблица 6.4

Vj

Ui

V1=4

V2=4

V3=5

V4=3

U1 = 0

4

4

150

5

3

50

U2 = -3

50

1

250

0

U3 = -2

100

2

3

1

Итерация 3. Число занятых клеток равно 6. Находим значения потенциалов и их сумму для свободных клеток. Критерий оптимальности выполняется:

Ui +Vj ≤ Cij для Xij = 0; i = 1, m; j = 1, n,

Поэтому полученный план является оптимальным:

и F (x*) = 1500.

Пример 6.2. Решить задачу:

Решение. Объем ресурсов: 80 + 60 + 60 = 200 – превышает общие потребности 30 + 70 + + 60 = 160 на 40 ед., следовательно, ТЗ является задачей открытого типа. Вводим дополнительный (балансовый) пункт потребления с объемом потребностей b4 = 40 и полагаем
c14 = c24 = c34 = 0. В результате получаем ТЗ закрытого типа.

Предварительный этап. Находим исходный опорный план методом «минимального элемента» (табл. 6.5).

Таблица 6.5

Vj

Ui

7

3

4

2

0

7

3

4

4

2

0

10–

70

–2

5

1

7

2

8

0

20+

40–

–2

5

3

1

8

2

0

60

0

Данный план является вырожденным, поэтому ставим «0» – перевозку в клетку с минимальным значением cij, но так, чтобы не образовалось замкнутого маршрута (цикла). В нашем примере c14 = c34 = 0, но занять клетку (1,4) нельзя, так как образуется цикл:

(1,4) → (2,4) → (2,1) → (1,1) → (1,4).

Поэтому ставим «0» в клетку (3,4).

Итерация 1. Проверяем план на оптимальность. Положив , находим потенциалы (см. табл. 6.5). Далее находим сумму потенциалов для свободных клеток (они записаны в левом верхнем углу клетки). Так как

;

,

То полученный опорный план неоптимальный. Для клеток (1,4) и (3,1) оценки одинаковы: и , поэтому выбираем любую, например, (1,4). Проставляем в эту клетку и составляем цикл, чередуя знаки «+» и «–»; получим . Новый опорный план представлен в табл. 6.6.

Таблица 6.6


Vj

Ui

5

3

2

0

0

5

7

3

2

4

0

70

10

0

5

3

7

2

8

0

30–

30+

0

5

3

3

8

2

0

60

0–

Итерация 2. Находим систему потенциалов (см. слева и сверху табл. 6.6). Сумма потенциалов для небазисных клеток записана в левом верхнем углу. Критерий оптимальности не выполняется для клетки (3,1):

.

Проставим в эту клетку и составим замкнутую цепочку, в результате получаем . Опорный план Представлен в таблице 6.7.

Итерация 3. Найдя систему потенциалов, убеждаемся в оптимальности плана (табл. 6.7).

Таблица 6.7

Vj

Ui

5

3

4

0

0

5

7

3

4

4

0

70

10

0

5

3

7

4

8

0

30

30

–2

3

1

8

2

-2

0

0

60

Транспортные издержки составляют 480 и . Так как четвертый потребитель фиктивный, то 10 ед. груза останутся у первого поставщика, 30 ед. – у второго.

Пример 6.3. Методом потенциалов решите следующую ТЗ:

 

Прочерк между пунктами A2 и B2, A3 и B4 означает, что перевозки между указанными пунктами запрещены.

Проверяем условие баланса:

80 + 320 + 150 = 550 = 250 + 100 + 150 + 50.

Для решения задачи полагаем, что стоимости перевозки единицы груза по запрещенным маршрутам равны достаточно большому числу М > 0. Далее эта М-задача решается обычным методом потенциалов, но потенциалы будут зависеть от коэффициента М. Если оптимальный план М-задачи содержит положительные перевозки по запрещенным маршрутам, то исходная ТЗ неразрешима (множество ее планов пусто). В противном случае получаем решение исходной ТЗ.

Предварительный этап. Составляем методом «минимального элемента» исходный опорный план (табл. 6.8).

Итерация 1. Вычисляем потенциалы и проверяем план на оптимальность (см. табл. 6.8).

Таблица 6.8

Vj

Ui

10 – M

2

1

7 – M

0

10-M

6

2

6

1

7-M

4

80

M – 2

8

M

M-1

6

5

250

20–

50

2

12-M

5

4

3

9-M

M

80+

70–

В клетке (2,3) имеем

,

Т. е. планНе является оптимальным. Проставляем в эту клеткуИ составляем замкнутый маршрут. Получаем . Опорный план Приведен в табл. 6.9.

Итерация 2. Проверяем план На оптимальность. Так как для всех свободных клеток

,

То план – оптимальный и не содержит положительных перевозок по запрещенным маршрутам.

Таблица 6.9

Vj

Ui

V1 = 3

V2 = 2

V3 = 1

V4 = 0

U1 = 0

3

6

2

6

1

0

4

80

U2 = 5

8

7

M

6

5

250

20

50

U3 = 2

5

5

4

3

2

M

100

50

Минимальные транспортные расходы составляют 3000.

 
Яндекс.Метрика
Наверх