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

Наибольшее распространение для нахождения начальных опорных планов получили:

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

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

Метод северо-западного угла используют для нахождения произвольного опорного плана ТЗ. Основную идею метода рассмотрим на конкретном примере.

Пример 1. Условия ТЗ заданы транспортной таблицей (табл. 3.1).

Таблица 3.1

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

Решение. Будем заполнять таблицу 3.1 перевозками постепенно, начиная с левой верхней ячейки(1.1) (северо-западного угла).Будем рассуждать при этом следующим образом.

Пункт В₁ подал заявку на 18 единиц товара. Удовлетворим эту заявку за счет запаса 48, имеющегося в пункте А₁, и запишем перевозку 18 в клетке (1.1). После этого заявка пункта В₁ удовлетворена, а в пункте А₁ осталось еще 30 единиц товара. Удовлетворим за счет них заявку пункта В₂ (27 единиц), запишем 27 единиц в клетке (1,2); оставшиеся 3 единицы пункта А₁ назначим пункту В₃. В составе заявке пункта В₃ остались неудовлетворенными 39 единиц. Из них 30 покроем за счет пункта А₂, чем его запас будет исчерпан, и еще 9 возьмем из пункта А₃. Из оставшихся 18 единиц пункта А₃ 12 выделим пункту В₄; оставшиеся 6 единиц назначим пункту В₅, что вместе со всеми 20 единицами пункта А₄ покроет его заявку (табл. 3.2).

Таблица 3.2

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

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

Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными, их число удовлетворяет условию r = n + m – 1 = 8. Остальные клетки -- свободные, в них стоят нулевые перевозки, их число равно (n – 1)(m – 1) = 12.Значит, составленный план -- опорный и поставленная задача построения опорного плана решена.

Но является ли этот план оптимальным? Нет, так как при его совершенно не учитывались стоимости перевозок с_{i j} . И даже, если мы стоимость этого плана перевозок

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

гарантировать, что этот план оптимальный еще нельзя. Ниже мы рассмотрим способы улучшения

плана с целью получения оптимального.

Пример 2. Особенности построения «вырожденного плана»

План, в котором некоторые из базисных перевозок оказываются равными нулю, называют «вырожденным»

Дана транспортная таблица (табл.3.3) Построить опорный план.

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

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

быть m + n -- 1 = 8, оказались равными нулю.

Отчего это произошло? При распределении запасов по пунктам назначения

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

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

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

Таблица 3,3

Таблица 3.4

Таблица 3.5

заявки, так чтобы общий баланс не нарушился, а лишние «промежуточные» балансы уничтожались. Достаточно в нужных местах изменить запасы или заявки, например, на величину ε, а после нахождения оптимального решения положить ε = 0.

Как перейти от вырожденного плана к невырожденному можно понять на примере таблиц 3.4 и 3.5. Изменим слегка запасы в первой строке и положим их равными 20 + ε. Кроме того, в третьей строке проставим запасы 25 + ε. Чтобы «свести баланс», в четвертой строке ставим запасы 20 -- 2 ε (табл. 3,5). Для этой таблицы строим опорный план методом северо-западного угла.

В табл. 3,5 уже содержится столько базисных переменных, сколько требуется:

m + n -- 1 = 8. В дальнейшем после оптимизации плана, можно будет положить

ε = 0.

Метод минимального элемента позволяет построить начальный опорный план

транспортной задачи и является вариантом метода северо-западного угла, учитывающего специфику матрицы С = c _{i j.} В отличие от метода северо-западного угла данный метод позволяет сразу получит достаточно экономичный план, сокращая количество итераций.

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

Дата добавления: 2014-01-07