Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Методичка по методам оптимизации.doc
Скачиваний:
179
Добавлен:
02.05.2014
Размер:
1.18 Mб
Скачать

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

Постановка транспортной задачи.

В каждом из пунктов Pi, i=1...,m, производится aiединиц некоторого однородного продукта, а в каждом из пунктов Qj, j=1...,n, потребляется bjединиц того же продукта. Возможная транспортировка продукта из каждого пункта производства Pi в каждый пункт потребления Qj. Стоимость перевозки единицы продукта из пункта Pi в пункт Qj известна и составляет сіj единиц. Считая, что суммарный объем производства равняется суммарному объему потребления, нужно составить план перевозок продукта, что минимизирует суммарные транспортные расходы.

Математическая модель транспортной задачи имеет вид:

L(x)= c11 x11 +...+ c1n x1n +...+ cm1 xm1 +...+ cmn xmn  min

xi1 +...+ xin = ai, i=1...,m

x1j +...+ xmj = bj, j=1...,n

xij0, i=1...,m, j=1...,n

a1 +...+ am = b1 +...+ bn.

Последнее условие определяет сбалансированную транспортную задачу.

В предложенной модели назовем вектор x=(x11...,x1n,...,xm1,...,xmn) вектором перевозок, вектор b=(a1...,am,b1,...,bn) т вектором запасов-потребностей, вектор Aij=(0...,0,1,0...,0,0,...,0,1,0,...,0) т вектором коммуникации PiQj (вектор Aijимеет размерность m+n, причем первая единица стоит на і-у месте, а вторая на m+j-у) и, наконец, вектор c=(c11...,c1n,...,cm1,...,cmn) - вектором транспортных расходов.

Основные определения.

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

Последовательность коммуникаций, среди которых нет одинаковых, вида:

называется маршрутом, что связывает пункты и .

Маршрут, к которому прибавленная коммуникация , называется замкнутым маршрутом (циклом).

Коммуникация PiQj называется основной коммуникацией решения x, если соответствующая ей компонента развязку xij>0.

Подобные определения имеют место и для клеточек транспортной таблицы.

Свойства транспортной задачи.

1. Сбалансированная транспортная задача всегда допустимая и имеет оптимальное решение.

2. Ранг матрицы А ограничений транспортной задачи равняется m+n1, в результате чего допустимое базисное решение задачи содержит не более m+n1 ненулевых перевозок xij.

3. Если в транспортной задаче все числа ai, i=1...,m, bj, j=1...,n цели, то хотя бы одно оптимальное решение задачи целочисленный.

Основные теоремы.

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

2. ДБР x=(xij, i=1...,m, j=1...,n) оптимальный тогда и только затем, когда существуют потенциалы ui, vjтакие, что

vj ui = сіj, если xij  базисная перевозка

vj uiсіj, если xij  небазисная перевозка.

Методы поиска выходного ДБР.

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

Метод состоит из однотипных шагов, поэтому его формальное изложение дадим лишь для 1-го шага. Заполняем северо-западную клеточку таблицы, покладая x11 = min{a1, b1}. Возможные три случая:

1. a1<b1, тогда x11=a1и вычеркивается 1-я строка таблицы;

2. a1>b1, тогда x11=b1и вычеркивается 1-й столбец таблицы;

3. a1=b1, тогда x11=a1=b1и вычеркивается как 1-я строка, так и 1-й столбец. В последнем случае в одну из вычеркнутых клеточек заносится нулевая базисная перевозка (соответствующий выходной допустимое базисное решение будет вырожденным).

Во всех случаях после заполнения базисной клеточки объемы запасов a1и потребностей b1уменьшают на величину, что равняется x11. Конец шага.

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

Метод минимального элемента.

Метод отличается от предыдущего тем, что вместо северо-западной клеточки на каждом шагу выбирается клеточка с наименьшим значением транспортных расходов сіj.

Метод вычеркивания.

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

Алгоритм метода потенциалов.

1. Находится исходное допустимое базисное решение (ДБР), например, с помощью одного из упомянутых выше методов.

2. В дальнейшем метод потенциалов состоит из однотипных шагов, на каждом из которых:

i) Вычисляются потенциалы строк ui, i=1...,m, и столбцов vj, j=1...,n, транспортной таблицы как решение системы vjui=cij, где и и j принимают такие значения, что клеточки (і,j) — базисные.

ii) Вычисляются оценки переменных xij для всех небазисных клеточек (і,j) за формулой ij=cijvj+ui (оценки базисных переменных — нулевые).

iii) Найденные оценки ij проверяются на неотъемлемость. Если все ij0, i=1...,m, j=1...,n, то текущий ДБР оптимальный. Иначе переходят к улучшению ДБР (пункт iv)).

iv) Определяют клеточку (k,l) с минимальной отрицательной оценкой, и присоединяют ее к совокупности базисных. Находят цикл (например, методом вычеркивания). Разделяют цикл на положительный и отрицательный полуциклы, последовательно помечая клеточки  вершины цикла знаками «+» и ««, начиная с клеточки (k,l), которую первой относят к положительному полцикла, следующую за ней — к отрицательному, третью — к положительному и т.д. Среди клеточек отрицательного полцикла определяют клеточку (s,r) с минимальной величиной перевозки xij (если таких клеточек несколько, то выбирают только одну из них). Возлагают =xsr. Увеличивают на значение перевозка xij в клеточках положительного полцикла и уменьшают их на то же значение в клеточках отрицательного полцикла. В результате осуществления указанных процедур клеточка (k,l) вводится к совокупности базисных, а клеточка (s,r) перестает быть базисной (на ней разрывают цикл). Конец шага.

Программное обеспечение.

Обучающий модуль, с помощью которого транспортная задача Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗМО.

Задание.

Решить методом потенциалов транспортные задачи, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1№9), а также следующие задачи:

1)

a\b

25

40

50

35

45

2)

a\b

35

30

50

25

65

20

7

3

4

8

6

50

8

6

7

3

4

60

5

7

2

3

5

50

7

4

9

3

4

45

1

4

5

2

6

55

6

1

4

5

2

70

3

4

2

7

8

50

7

8

3

4

2

3)

a\b

10

40

20

60

20

4)

a\b

70

40

30

60

50

30

5

1

5

2

4

20

6

1

7

3

3

70

5

7

6

3

2

90

7

4

4

8

4

25

1

5

4

2

6

80

8

2

3

5

7

25

1

6

3

3

5

60

3

4

2

8

5

5)

a\b

30

90

80

20

30

6)

a\b

10

30

25

15

20

95

2

8

4

6

3

20

9

1

5

7

1

55

3

2

5

2

6

15

2

8

4

8

1

40

6

5

8

7

4

45

2

3

2

8

5

60

3

4

4

2

1

20

6

1

3

4

7

7)

a\b

13

13

13

13

28

8)

a\b

11

13

26

10

10

28

8

4

6

3

1

24

9

1

3

2

7

13

9

3

8

5

7

12

6

9

4

1

5

19

7

3

5

9

8

18

9

1

2

8

5

20

2

1

4

5

7

16

3

3

9

6

8

9)

a\b

10

35

15

25

35

10)

a\b

30

80

65

35

40

30

7

3

1

5

4

60

8

2

4

9

1

25

7

5

8

3

2

55

7

5

5

3

6

45

6

4

8

3

2

85

9

4

6

2

7

20

3

1

7

6

2

50

5

3

2

6

4

Ответы:

1) L(x*)= 575. 2) L(x*)= 710. 3) L(x*)= 360. 4) L(x*)= 910. 5) L(x*)= 750.

6) L(x*)= 200. 7) L(x*)= 209. 8) L(x*)= 184. 9) L(x*)= 285. 10) L(x*)= 785.

Лабораторная работа 6.