Полная версия

Главная arrow Математика, химия, физика arrow Математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Нахождение опорного плана

Решение ТЗ, как и всякой задачи линейного программирования, начинается с нахождения опорного решения, или, как мы будем говорить, опорного плана. В отличие от общего случая ОЗЛП с произвольными ограничениями и минимизируемой функцией, решение ТЗ всегда существует. Вполне очевидно, что какой-нибудь допустимый план существовать должен. Среди допустимых планов непременно имеется оптимальный (может быть, не один), потому что линейная функция L — стоимость перевозок заведомо неотрицательна (ограничена снизу нулем). Как построить опорный план? Для этого существуют различные способы. Рассмотрим простейший из них, так называемый способ северо- западного угла. Поясним его на примере.

ОПРИМЕР 3.12. Условия ТЗ заданы табл. 3.29.

Таблица 3.29

пн

по

Д

Д

Вг

в4

В5

Запасы ai

Д

1 0

8

5

6

9

48

Д

6

7

8

6

5

30

д

8

7

1 0

8

7

27

д

7

5

4

6

8

20

Заявки bt

1 8

27

42

1 2

26

125

Требуется найти опорное решение ТЗ (построить опорный план).

Решение. Перепишем табл. 3.29 и будем заполнять ее перевозками постепенно, начиная с левой верхней клетки (1, 1) (с северо-западного угла таблицы). Будем рассуждать при этом следующим образом. Пункт Вх подал заявку на 18 единиц груза. Удовлетворим эту заявку за счет запаса 48, имеющегося в пункте Ар и запишем перевозку 18 в клетке (1,1) (табл. 3.30). После этого заявка пункта Вх удовлетворена, а в пункте А осталось еще 30 единиц груза. Удовлетворим за счет них заявку пункта В2 (27 единиц), запишем 27 в клетке (1,2); оставшиеся 3 единицы пункта Ах назначим пункту Ву В составе заявки пункта В3 остались неудовлетворенными 39 единиц, 30 из которых покроем за счет пункта А2 (чем его запас будет исчерпан) и еще 9 возьмем из пункта Ау Из оставшихся 18 единиц пункта 12 выделим пункту В4, а 6 единиц назначим пункту В у что вместе со всеми 20 единицами пункта А4 покроет его заявку (см. табл. 3.30).

На этом распределение запасов закончено: каждый пункт назначения получил груз согласно своей заявке. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце — заявке.

Таблица 3.30

пн

по

А

А

А

А

Запасы а,

А

48

А

30

А

27

А

20

Заявки bj

1 8

27

42

12

26

125

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

Число базисных клеток удовлетворяет условию г = т + п- = &. Число свободных клеток равно (п - 1 ){т - 1) = 12. Значит, наш план — не только допустимый, но и опорный, и поставленная задача построения опорного плана решена. ?

Возникает вопрос: является ли этот план оптимальным по стоимости? Разумеется, нет! Ведь при его построении мы совсем не учитывали стоимостей перевозок с... Стоимость полученного плана (если умножить каждую перевозку на соответствующую стоимость) равна

18 -10+ 27- 8 + 3*5 +30- 8 + 9-10+ 12- 8 + 6- 7 +20- 8 = 1039.

Попробуем улучшить этот план, перенеся, например, 18 единиц из клетки (1, 1) в клетку (2, 1) и, чтобы не нарушить баланса, перенеся те же 18 единиц из клетки (2, 3) в клетку (1, 3). Получим новый план, приведенный в табл. 3.31.

Нетрудно убедиться, что стоимость нового плана равна

27- 8 +21- 5+18-6 + 12- 8 + 9-10+ 12- 8 + 6- 7 +20- 8 = 913, т.е. на 126 единиц меньше стоимости плана, приведенного в табл. 3.30.

Таблица 3.31

пн

по

А

А

А

А

Запасы а.

А

48

А

30

А

27

А

20

Заявки bt

1 8

27

42

1 2

26

125

Таким образом, за счет перестановки 18 единиц груза из одних клеток в другие нам удалось понизить стоимость плана. На этом способе уменьшения стоимости в дальнейшем и будет основан алгоритм оптимизации плана перевозок.

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

>ПРИМЕР 3.13. Дана транспортная таблица (табл. 3.32) (без стоимости перевозок, так как речь идет только о построении опорного плана).

Таблица 3.32

пн

по

А

А

А

А

А

Запасы а,

А

20

А

30

А

25

А

20

Заявки bj

10

10

20

35

20

95

Составить опорный план перевозок.

Решение. Применяя способ северо-западного угла, получим табл. 3.33.

Таблица 3.33

ПН

ПО

А

А

А

А

А

Запасы а.

А

10

10

20

А

20

1 0

30

А

25

25

А

20

20

Заявки bj

10

10

20

35

20

95

Опорный план составлен. Особенностью его является то, что в нем только шесть, а не восемь + п - 1 =8), как должно быть, отличных от нуля перевозок. Значит, некоторые базисные перевозки, оказались равными нулю. Нетрудно заметить, отчего это произошло: при распределении запасов по пунктам назначения в некоторых случаях остатки оказывались равными нулю и в соответствующую клетку не попадали. ?

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

В дальнейшем нам удобно будет всегда иметь в транспортной таблице т + п - 1 базисных клеток, хотя в некоторых из них, может быть, будут нулевые значения перевозок. Для этого можно ничтожно мало изменить запасы или заявки, так чтобы общий баланс не нарушился, а лишние, “промежуточные” балансы уничтожились, т.е. приняли тривиальное значение. Достаточно в нужных местах изменить запасы или заявки, например, на величину е, а после нахождения оптимального решения положить ? = 0.

Покажем, как перейти от вырожденного плана к невырожденному на примере табл. 3.33. Изменим запасы в первой строке и положим их равными 20 + ? (табл. 3.34). Кроме того, в третьей строке проставим запасы 25 + ?. Чтобы “свести баланс”, в четвертой строке ставим запасы 20 - 2?. Для этой таблицы строим опорный план способом северо-западного угла.

Таблица 3.34

пн

по

А

А

А

А

А

Запасы а.

А

1 0

1 0

?

20 + е

А

20-е

1 0 + ?

30

А

25-е

2 ?

25 + е

А

20-2е

20-е

Заявки Ь/

1 0

1 0

20

35

20

95

В табл. 3.34 уже содержится столько базисных переменных, сколько требуется: т + п - 1 = 8. В дальнейшем, после оптимизации плана, можно будет положить ? = 0.

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>