Составление опорного плана методом северо-западного угла - Транспортная задача

Заполнение таблицы 1 начинаем с левого верхнего угла.

Сумма поставок по строке равна запасу соответствующего пункта отправления, а сумма поставок по столбцу - заявке соответствующего пункта назначения; значит, все заявки удовлетворены, все запасы исчерпаны (сумма запасов равна сумме заявок и выражается числом 1220, стоящим в правом нижнем углу таблицы).

Таблица 1 - Решение транспортной задачи методом потенциалов

Пункт отправления

Пункт назначения

Запас

B6

B9

B10

B1

B2

A5

4

200

2

150

1

5

4

350

A8

4

1

70

4

200

7

1

270

A9

1

4
    1 200
    9 10

4

210

A10

8

6

3

7

190

3

190

A1

3

2

6

3

10

7

190

200

Заявка

200

220

400

210

190

1220

Во всех транспортных таблицах проставляем только отличные от нуля поставки, а клетки, соответствующие нулевым поставкам, оставляем пустыми.

Далее, проверяем, является ли план, приведенный в таблице 1, опорным. Так как число занятых клеток с нулевыми поставками составляет m + n - 1 = 5 + 5 - 1 = 9, то план - опорный.

Получившийся план поставок отвечает одному из условий - вся мощность поставщиков полностью распределена, весь спрос потребителей полностью удовлетворен.

Стоимость транспортных работ L составляет:

4*200 + 2*150 + 1*70 + 4*200 + 1*200 + 9*10 + 7*190 + 3*10 + 7*190 = 4950 тыс. руб.

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

Транспортный поставка microsoft mathcad

Таблица 2 - Решение транспортной задачи методом потенциалов (шаг 1)

Лесозаготовительные предприятия и их запасы, тыс.

Пункт назначения

Потенциалы строк

B6

B9

B10

B1

B2

200

220

400

210

190

A5

350

4

2

1

5

4

200

150

-4

-8

-13

A8

270

4

1

4

7

1

-1

70

(-)200

(+)

1

-5

-15

A9

210

1

4

1

9

4

-4

(+)200

(-)10

1

6

-9

A10

190

8

6

3

7

3

-6

190

10

10

4

-8

A1

200

3

2

6

3

7

-10

(+)10

()190

9

10

11

Потенциалы столбцов

4

2

5

13

17

При распределении поставок составляем цепи, для которых характерны следующие особенности:

Цепь является замкнутым многоугольником;

Вершинами цепи являются клетки таблицы, причем одна из вершин - свободная клетка, а все остальные - базисные;

Все углы цепи прямые, и каждый отрезок цепи, ограниченный двумя вершинами, целиком принадлежит одному столбцу или одной строке таблицы;

Число вершин в цепи - четное;

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

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

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

Обозначив потенциалы строк, потенциалы столбцов - и показатели критерия оптимальности - .

Характеристики свободных клеток цепи обозначим, тогда, зная потенциалы строки и столбца, ее можно вычислить по формуле:

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

Для всех базисных клеток характеристики равны нулю.

Характеристики свободных клеток укажем в нижней части клеток поставок.

Наибольшая по абсолютной величине - отрицательная характеристика клетки. Перераспределим поставки по цепи к этой клетке. Составим цепь с вершинами, отмеченными в таблице 2 стрелками. Положительные вершины в этой цепи обозначены знаком "плюс", отрицательные - знаком "минус". Наименьшая по величине поставка в отрицательных вершинах цепи равна 10 тыс. к поставкам в положительных вершинах и вычтем по 10 тыс. из поставок в отрицательных вершинах цепи. Получившийся план поставок запишем в таблицу 3 и определим новые потенциалы, произвольно приняв потенциал равным нулю.

Таблица 3- Решение транспортной задачи методом потенциалов (шаг 2)

Лесозаготовительные предприятия и их запасы, тыс.

Пункт назначения

Потенциалы строк

B6

B9

B10

B1

B2

200

220

400

210

190

A5

350

4

2

1

5

4

0

200

150

-4

7

2

A8

270

4

1

4

7

1

-1

70

()190

(+)10

1

10

A9

210

1

4

1

9

4

-4

210

1

6

15

6

A10

190

8

6

3

7

3

9

(+)

()190

-5

-5

-11

-8

A1

200

3

2

6

3

7

5

(+)20

()180

-6

-5

-4

Потенциалы столбцов

4

2

5

-2

2

Значение целевой функции при новом плане поставок будет равен L=4800 тыс. руб.

Наибольшая по абсолютной величине - отрицательная характеристика клетки. Перераспределим поставки по цепи к этой клетки. Составим цепь с вершинами, отмеченными в таблице 3 стрелками. Положительные вершины в этой цепи обозначены знаком "плюс", отрицательные - знаком "минус". Наименьшая по величине поставка в отрицательных вершинах цепи равна 180 тыс. к поставкам в положительных вершинах и вычтем по 180 тыс. из поставок в отрицательных вершинах цепи. Получившийся план поставок запишем в таблицу 4 и определим новые потенциалы, произвольно приняв потенциал равным нулю.

Таблица 4 - Решение транспортной задачи методом потенциалов (шаг 3)

Лесозаготовительные предприятия и их запасы, тыс.

Пункт назначения

Потенциалы строк

B6

B9

B10

B1

B2

200

220

400

210

190

A5

350

4

2

1

5

4

200

(-)150

(+)

-4

-4

2

A8

270

4

1

4

7

1

-1

(+)70

(-)10

190

1

-1

A9

210

1

4

1

9

4

-4

210

1

6

4

6

A10

190

8

6

3

7

3

-2

180

10

6

6

3

A1

200

3

2

6

3

7

-6

200

5

6

7

11

Потенциалы столбцов

4

2

5

9

2

Значение целевой функции при новом плане поставок будет равен: L=2820 тыс. руб

Наибольшая по абсолютной величине - отрицательная характеристика клетки. Перераспределим поставки по цепи к этой клетки. Составим цепь с вершинами, отмеченными в таблице 4 стрелками. Положительные вершины в этой цепи обозначены знаком "плюс", отрицательные - знаком "минус". Наибольшая по величине поставка в отрицательных вершинах цепи равна 10 тыс. к поставкам в положительных вершинах и вычтем по 10 тыс. из поставок в отрицательных вершинах цепи. Получившийся план поставок запишем в таблицу 5 и определим новые потенциалы, произвольно приняв потенциал равным нулю.

Таблица 5 - Решение транспортной задачи методом потенциалов (шаг 4)

Лесозаготовительные предприятия и их запасы, тыс.

Пункт назначения

Потенциалы строк

B6

B9

B10

B1

B2

200

220

400

210

190

A5

350

4

2

1

5

4

0

()200

140

(+)10

2

A8

270

4

1

4

7

1

-1

80

190

1

4

3

A9

210

1

4

1

9

4

0

(+)

(-)210

-3

2

4

2

A10

190

8

6

3

7

3

2

180

10

2

2

-1

A1

200

3

2

6

3

7

-2

200

1

2

7

7

Потенциалы столбцов

4

2

1

5

2

Значение целевой функции при новом плане поставок будет равен: L=2780 тыс. руб.

Наибольшая по абсолютной величине - отрицательная характеристика клетки. Перераспределим поставки по цепи к этой клетки. Составим цепь с вершинами, отмеченными в таблице 4 стрелками. Положительные вершины в этой цепи обозначены знаком "плюс", отрицательные - знаком "минус". Наибольшая по величине поставка в отрицательных вершинах цепи равна 200 тыс. к поставкам в положительных вершинах и вычтем по 200 тыс. из поставок в отрицательных вершинах цепи. Получившийся план поставок запишем в таблицу 6 и определим новые потенциалы, произвольно приняв потенциал равным нулю.

Таблица 6 - Решение транспортной задачи методом потенциалов (шаг 5)

Лесозаготовительные предприятия и их запасы, тыс.

Пункт назначения

Потенциалы строк

B6

B9

B10

B1

B2

200

220

400

210

190

A5

350

4

2

1

5

4

0

()140

(+)210

3

2

A8

270

4

1

4

7

1

-1

(+)80

()190

4

4

3

A9

210

1

4

1

9

4

0

200

10

2

4

2

A10

190

8

6

3

7

3

2

(-)180

10

(+)

5

2

-1

A1

200

3

2

6

3

7

-2

200

4

2

7

7

Потенциалы столбцов

1

2

1

5

2

Значение целевой функции при новом плане поставок будет равен: L=2180тыс. руб.

Наибольшая по абсолютной величине - отрицательная характеристика клетки. Перераспределим поставки по цепи к этой клетки. Составим цепь с вершинами, отмеченными в таблице 4 стрелками. Положительные вершины в этой цепи обозначены знаком "плюс", отрицательные - знаком "минус". Наибольшая по величине поставка в отрицательных вершинах цепи равна 140 тыс. к поставкам в положительных вершинах и вычтем по 140 тыс. из поставок в отрицательных вершинах цепи. Получившийся план поставок запишем в таблицу 7 и определим новые потенциалы, произвольно приняв потенциал равным нулю.

Таблица 7 - Решение транспортной задачи методом потенциалов (шаг 6)

Лесозаготовительные предприятия и их запасы, тыс.

Пункт назначения

Потенциалы строк

B6

B9

B10

B1

B2

200

220

400

210

190

A5

350

4

2

1

5

4

0

350

3

1

3

A8

270

4

1

4

7

1

0

220

50

3

3

2

A9

210

1

4

1

9

4

0

200

10

3

4

3

A10

190

8

6

3

7

3

2

40

10

140

5

3

A1

200

3

2

6

3

7

-2

200

4

3

7

8

Потенциалы столбцов

1

1

1

5

1

Значение целевой функции при новом плане поставок будет равен: L=2040 тыс. руб.

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

Следовательно, найденный план распределение поставок - оптимальный.

Похожие статьи




Составление опорного плана методом северо-западного угла - Транспортная задача

Предыдущая | Следующая