Метод потенциалов для решения транспортной задачи (стр. 2 из 3)
Поскольку в новой таблице число заполняемых клеток больше, чем число столбцов, то при заполнении клеток следует пользоваться специальным правилом, которое состоит в следующем. Выбирают некоторый столбец (строку), в котором имеется одна клетка с помещенным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данный столбец (строку). После этого берут некоторую строку (столбец), в которой имеется одна клетка с помещенным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данную строку (столбец). Продолжая так, после конечного числа шагов заполняют все клетки, в которых помещены кружки с заключенными в них числами. Если к тому же удается распределить весь груз, имеющийся в пунктах отправления, между пунктами назначения, то получают оптимальный план транспортной задачи. Если же оптимальный план не получен, то переходят к новой таблице. Для этого находят избыточные и недостаточные строки, промежуточную ренту и на основе этого строят новую таблицу. При этом могут возникнуть некоторые затруднения при определении знака строки, когда ее нераспределенный остаток равен нулю. В этом случае строку считают положительной при условии, что вторая заполненная клетка, стоящая в столбце, связанном с данной строкой еще одной заполненной клеткой, расположена в положительной строке.
После конечного числа описанных выше итераций нераспределенный остаток становится равным нулю. В результате получают оптимальный план данной транспортной задачи.
III этап. Определение переменной, выводимой из базиса (построение цикла).
Процедура построения цикла эквивалентна использованию условия допустимости в симплекс-методе.
1. Строится замкнутый цикл, соответствующий вводимой переменной. Он состоит из последовательности горизонтальных и вертикальных связанных отрезков, концами которых должны быть базисные переменные (за исключением тех концов, которые относятся к вводимой в базис переменной). Для каждого базисного решения и соответствующей небазисной переменной можно построить лишь один цикл.
2. Нечетным вершинам цикла (начиная с вводимой в базис переменной) присваивается знак "+", четным – "-" (будем называть эти клетки плюсовыми и минусовыми).
3. Определяется выводимая из базиса переменная, которой является одна из базисных переменных, расположенных в вершинах цикла, отмеченных знаком "-" и имеющих наименьшее значение.
4. Формируется новое допустимое базисное решение. Для этого переменные, находящиеся в вершинах цикла, соответствующим образом корректируются, а именно уменьшаются или увеличиваются на величину вводимой в базис переменной в зависимости от знака вершины цикла.
Описанный выше переход от одного опорного плана транспортной задачи к другому ее опорному плану называется сдвигом по циклу пересчета. Следует отметить, что при сдвиге по циклу пересчета число занятых клеток остается неизменным и равным (n + m - 1).
Однако при определении опорного плана или в процессе решения задачи может быть получен вырожденный опорный план. Чтобы избежать зацикливания, следует соответствующие нулевые элементы опорного плана заменить сколь угодно малым числом ε и решать задачу как невырожденную. В оптимальном плане такой задачи необходимо считать ε= 0.
транспортный задача алгоритм фогель цикл
2. Пример практического решения задачи оптимального планирования
Перевозки товаров различными транспортными средствами в ряде случаев приводят к таким нежелательным явлениям, как порожние пробеги, простои, встречные и нерациональные перевозки. Для их исключения используются методы оптимального планирования перевозок, в частности такая экономико-математическая модель, как транспортная задача.
Простейшим примером транспортной задачи является задача о планировании перевозок некоторого продукта из конечного числа пунктов отправления в конечное число пунктов назначения при обеспечении минимальных затрат на выполнение данной операции.
Пример: Три поставщика некоторого товара располагают следующими запасами: первый – 120 единиц, второй – 100 единиц, третий – 80 единиц. Товар должен быть перевезен трем потребителям: спрос первого – 90 единиц; спрос второго – 90 единиц; спрос третьего – 120 единиц. Известны также показатели затрат (cij) на перевозку единицы товара от каждого поставщика к каждому потребителю.
Требуется составить оптимальный план перевозок, приводящий к наименьшим затратам на выполнение данной операции.
Под планом перевозок понимается матрица
| X11 | X12 | X13 |
| X21 | X22 | X23 |
| X31 | X32 | X33 |
в которой хij количество единиц товара, планируемого к перевозке от поставщика с номером i к потребителю с номером j.
Для решения задачи исходные данные удобно свести в таблицу:
| Поставщики | Возможности поставщиков | Потребители и их спрос | ||
| 1 | 2 | 3 | ||
| 90 | 90 | 120 | ||
| 1 | 120 | 7 | 6 | 4 |
| 2 | 100 | 3 | 8 | 5 |
| 3 | 80 | 2 | 3 | 7 |
Каждую клетку таблицы пометим двойным индексом (i, j). Первый (i) – номер поставщика, второй (j) – номер потребителя.
Числа на пересичении стоимости перевозок и обозначаются сij.
Математическая постановка данной задачи имеет вид: найти минимум целевой функции (показателя эффективности)
Z= 7х11 + 6х12 + 4х13 + Зх21 + 8х22 + 5х23 + +2х31 +3х32 + 7х33 при ограничениях:
nnn
Σx1j =120; Σx2j =100; Σx3j =80;
j=ij=ij=i
mmm
Σxi1 =90; Σxi1 =90; Σxi1 =120; хij>0
i=li=li=l
Транспортная задача относится к классу задач линейного программирования. Решение таких задач обычно связано с получением опорного (допустимого) плана и последующим его улучшением.
Опорный план может быть получен различными методами. Рассмотрим метод минимального элемента, или метод наименьших.
В соответствии с методом наименьших затрат выберем в таблице клетку, имеющую наименьший показатель затрат, т. е. клетку (3,1). Произведем поставку в эту клетку, равную 80 единицам, поскольку первому потребителю требуется .90 единиц, а у третьего поставщика в наличии лишь 80 единиц. Первому потребителю необходимо еще 10 единиц товара. Он может получить их или от первого, или от второго поставщика. Так как показатель затрат в клетке (2,1) меньше, чем в клетке (1,1), то записываем 10 единиц в клетку (2,1).
Второй поставщик, отдав 10 единиц, будет располагать 90 единицами. Их можно направить второму или третьему потребителю. В связи с тем, что показатель затрат в клетке (2, 3) меньше, чем в клетке (2, 2), направим их третьему потребителю. Недостающие 30 единиц третий потребитель получит от первого поставщика.
Оставшиеся у первого поставщика 90 единиц запишем в клетку (1, 2) и, тем самым, удовлетворим спрос второго потребителя.
На этом распределение можно считать законченным.
| Поставщики | Возможности поставщиков | Потребители и их спрос | ||
| 1 | 2 | 3 | ||
| 90 | 90 | 120 | ||
| 1 | 120 | 7 | 690 | 430 |
| 2 | 100 | 310 | 8 | 590 |
| 3 | 80 | 280 | 3 | 7 |
Получив опорный план, необходимо оценить соответствующую ему стоимость перевозок (показатель эффективности или целевую функцию). Для плана, полученного методом наименьших затрат, Z = 1300 ед.
Следующим этапом решения задачи, независимо от того, каким методом был найден опорный план, является последовательное его улучшение до получения оптимального распределения. С этой целью каждому поставщику товаров поставим в соответствие потенциалы А1, А2, А3 и запишем их в дополнительном столбце, а каждому потребителю – потенциалы B1, В2, В3, которые запишем в дополнительной строке. Один из потенциалов, например A1приравняем к нулю, а остальные найдем с использованием:
Аij = Аi + Вj
Запишем данное соотношение для всех заполненных клеток (Хij > 0) и определим А2, А3, В1, В2, В3. Для незаполненных клеток (Хij = 0) запишем аналогичную зависимость, левую часть которой принято называть псевдостоимостью.
Cij = Ai+Bj
Условие оптимальности плана заключается в том, что для каждой свободной клетки (Xij = 0)
Сij<Сij.
Найдем для свободных клеток разности Δij = Сij – CijПоскольку одна из разностей, соответствующая клетке (3,2), отрицательна, то улучшение плана начинаем именно с нее. | Поставщики | Возможности поставщиков | Потребители и их спрос | Ai | ||
| 1 | 2 | 3 | |||
| 90 | 90 | 120 | |||
| 1 | 120 | 72 | 690 | 430 | 0 |
| 2 | 100 | 310 | 87 | 590 | 2 |
| 3 | 80 | 280 | 36 | 74 | 4 |
| Bj | 7 | 6 | 3 | ||
Заметим, что если отрицательных разностей несколько, то первой выбирается клетка, для которой разность по абсолютной величине больше.
Догрузим клетку (3, 2), поставив в нее знак плюс (+), и составим цепь пересчета по правилу: цепь пересчета строится в виде прямоугольника, одна из вершин которого находится в свободной клетке (3, 2), а остальные – в занятых; все углы должны быть прямыми; в одной строке и в одном столбце не должно быть более двух вершин; всем вершинам приписываются чередующиеся знаки (плюс – догрузить, минус – разгрузить).