Исследование математических операций 2 (стр. 12 из 28)
(3.5)Вместо матрицы стоимостей перевозок (cij ) могут задаваться матрицы расстояний. В таком случае в качестве целевой функции рассматривается минимум суммарной транспортной работы. Как видно из выражения (3.1), уравнение баланса является обязательным условием решения транспортной задачи. Поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае, если
потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;
запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.
Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая.
Транспортным задачам присущи следующие особенности:
распределению подлежат однородные ресурсы;
условия задачи описываются только уравнениями;
все переменные выражаются в одинаковых единицах измерения;
во всех уравнениях коэффициенты при неизвестных равны единице;
каждая неизвестная встречается только в двух уравнениях системы ограничений.
Транспортные задачи могут решаться симплекс-методом. Однако перечисленные особенности позволяют для транспортных задач применять более простые методы решения.
Опорный план является допустимым решением транспортной задачи и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. "Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.
Все существующие методы нахождения опорных планов отличаются только способом выбора клетки для заполнения. Само заполнение происходит одинаково независимо от используемого метода.
Назад | Содержание | Далее
3.2. Методы составления начального опорного плана
Базисный план составляется последовательно, в несколько шагов (точнее, m + n - 1 шагов). На каждом из этих шагов заполняется одна клетка, притом так, что, либо полностью удовлетворяется один из заказчиков (тот, в столбце которого находится заполняемая клетка), либо полностью вывозится весь запас груза с одной из баз (с той, в строке которой находится заполняемая клетка).
В первом случае мы можем исключить столбец, содержащий заполненную на этом шаге клетку, и считать, что задача свелась к заполнению таблицы с числом столбцов, на единицу меньшим, чем было перед этим шагом, но с тем же количеством строк и с соответственно измененным запасом груза на одной из баз (на той базе, которой был удовлетворен заказчик на данном шаге).
Во втором случае исключается строка, содержащая заполняемую клетку, и считается, что таблица сузилась на одну строку при неизменном количестве столбцов и при соответствующем изменении потребности заказчика, в столбце которого находится заполняемая клетка.
Начиная с первоначально данной таблицы и повторив (m + n - 2) раз описанный шаг, мы придем к “таблице”, состоящей из одной строки и одного столбца (иначе говоря, из одной пустой клетки). Другими словами, мы пришли к задаче с одной базой и с одним потребителем, причем потребности этого единственного заказчика равны запасу груза на этой единственной базе. Заполнив последнюю клетку, мы освобождаем последнюю базу и удовлетворяем потребность последнего заказчика. В результате, совершив (m + n - 1) шагов, мы и получим искомый опорный план.
Замечание. Может случиться, что уже на некотором (но не на последнем!) шаге потребность очередного заказчика окажется равной запасу груза на очередной базе. Тогда после заполнения очередной клетки объем таблицы как бы одновременно уменьшается на одни столбец и на одну строку. Но и при этом мы должны считать, что уменьшение объема таблицы происходит либо на один столбец, а на базе сохраняется "остаток" равный нулю, либо на одну строку, а у заказчика еще осталась неудовлетворенная "потребность" в количестве нуля единиц груза, которая и удовлетворяется на одном из следующих шагов. Этот нуль ("запас" или "потребностью" – безразлично) надо записать в очередную заполняемую клетку на одном из последующих шагов. Так как при этом оказывается равной нулю одна из базисных неизвестных, то мы имеем дело с вырожденным случаем.
1. Диагональный метод, или метод северо-западного угла. При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного x11 и заканчивается в клетке неизвестного xmn , т. е. идет как бы по диагонали таблицы перевозок.
Пример
Заполнение таблицы начинается с ее северо-западного угла, т.е. клетки с неизвестным x11. Первая база A1 может полностью удовлетворить потребность первого заказчика B1 (a1=300, b1=170, a1 > b1). Полагая x11= 170, вписываем это значение в клетку x11 и исключаем из рассмотрения первый столбец. На базе A1 остается измененный запас
. В оставшейся новой таблице с тремя строками A1,A2,A3 и четырьмя столбцами B1,B2,B3,B4; северо-западным углом будет клетка для неизвестного x12 . Первая база с запасом может полностью удовлетворить потребность второго заказчика B2 
. Полагаем x12 = 110, вписываем это значение в клетку x12 и исключаем из рассмотрения второй столбец. На базе A1 остается новый остаток (запас) 
. В оставшейся новой таблице с тремя строками A1,A2,A3 и тремя столбцами B3,B4,B5 северо-западным углом будет клетка для неизвестного x13. Теперь третий заказчик B3 может принять весь запас с базы A1 
. Полагаем x13 = 20, вписываем это значение в клетку x13 и исключаем из рассмотрения первую строку. У заказчика из B3 осталась еще не удовлетворенной потребность 
.Теперь переходим к заполнению клетки для неизвестного x23 и т.д.
Через шесть шагов у нас останется одна база A3 с запасом груза (остатком от предыдущего шага)
и один пункт B5 с потребностью b5=200 . Соответственно этому имеется одна свободная клетка, которую и заполняем, положив x35=200. План составлен. Базис образован неизвестными x11,x12,x13,x23,x24,x34,x35. Правильность составленного плана легко проверить, подсчитав суммы чисел, стоящих в заполненных клетках по строкам и столбцам.Общий объем перевозок в тонно-километрах для этого плана составит
2. Метод наименьшей стоимости. При этом методе на каждом шаге построения опорного плана первою заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф. Если такая клетка не единственная, то заполняется любая из них.
Пример
В данном случае заполнение таблицы начинается с клетки для неизвестного x32, для которого мы имеем значение c32 = 10, наименьше из всех значений cij . Эта клетка находится на пересечении третьей строки и второго столбца, соответствующим третьей базе A3 и второму заказчику B2. Третья база A3 может полностью удовлетворить потребность второго заказчика B2 (a3=250, b2=110, a3 > b2) . Полагая x32 = 110, вписываем это значение в клетку x32 и исключаем из рассмотрения второй столбец. На базе A3 остается изменённый запас
. В оставшейся новой таблице с тремя строками A1,A2,A3 и четырьмя столбцами B1,B3,B4,B5 клеткой с наименьшим значением cij клетка, где c34=11. Заполняем описанным выше способом эту клетку и аналогично заполняем следующие клетки. В результате оказываются заполненными (в приведенной последовательности) следующие клетки: 
На пятом шаге клеток с наименьшими значениями cij оказалось две (c11=c15=70) . Мы заполнили клетку для x15 , положив x15 = 180. Можно было выбрать для заполнения другую клетку, положив x11 = 170, что приведет в результате к другому опорному плану. Общий объем перевозок в тонно-километрах для этого плана составит