Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
". Выбирается клетка с минимальным тарифом и заполняется максимально возможным числом, при этом исчерпываются либо запасы, либо потребности (вычеркивается строка или столбец), выбирается следующая клетка с минимальным тарифом и т.д.
в) Метод аппроксимации Фогеля.
Для заполнения каждой клетки необходимо найти разности между двумя минимальными тарифами по всем столбцам и строкам, записать их, соответственно, внизу и справа таблицы. Среди найденных разностей выбирают максимальную. В строке (или столбце), которой соответствует данная разность, заполняют клетку с минимальным тарифом. Если максимальных разностей несколько одинаковых, выбирают ту, которой соответствует минимальный тариф. Если минимальный тариф одинаков для нескольких клеток в строке (столбце), то заполняют ту, которая стоит в столбце (строке), имеющем наибольшую разность между двумя минимальными тарифами.
Как правило, при построении опорного плана этими тремя методами выполняется следующее соотношение: Fв(x)Fб(x) Fа(x).
Схема решения.
1. Строят опорный план одним из методов.
. Построенный опорный план следует проверить на оптимальность, для чего используют следующую теорему.
ТЕОРЕМА. Если для некоторого опорного плана транспортной задачи существуют такие числа и , что
при xij > 0 (4)
и при xij = 0 (5)
для всех и, то этот план является оптимальным.
ОПРЕДЕЛЕНИЕ 4. Числа и (,) называются потенциалами, соответственно, поставщиков и потребителей.
Т.о., найдя потенциалы поставщиков и потребителей, удовлетворяющие условиям теоремы, мы докажем оптимальность построенного плана. Как их найти? Т.к. число заполненных клеток, xij > 0, равно n+m-1 (невырожденный план), то система (4) с n+m неизвестными содержит n+m-1 уравнение. Положим одно из неизвестных равным нулю и последовательно найдем значения остальных неизвестных. Затем для всех свободных клеток, xij = 0, определим числа .
Если среди чисел нет положительных, то условия теоремы выполнены, и план является оптимальным. Если существует > 0, то построенный план не оптимален, и его следует улучшить.
. Алгоритм улучшения плана:
1) среди всех > 0 выбирают максимальное;
2) для соответствующей клетки строят цикл пересчета;
3) помечают вершины цикла пересчета последовательно знаками "+" и "-" , начиная с "+" в исходной клетке;
4) среди чисел, стоящих в клетках, помеченных "-" , определяют минимальное;
5) к значениям, стоящим в "+"-клетках, прибавляют это минимальное число, а из значений, стоящих в "-"-клетках, это число вычитают.
ОПРЕДЕЛЕНИЕ 5. Циклом пересчета называется ломаная линия, вершины которой расположены в занятых клетках, а звенья - вдоль строк и столбцов, причем в каждой вершине цикла может быть только два звена.
. Измененный таким образом план опять проверяют на оптимальность, т.е. переход к п. 2.
3. Метод дифференциальных рент
В отличие от метода потенциалов, для которого сначала строился опорный план, а затем он последовательно улучшался, при решении задачи методом дифференциальных рент сразу наилучшим образом распределяют часть продукции между потребителями и на последующих итерациях постепенно уменьшают общую величину нераспределенных поставок.
Для определения решения транспортной задачи методом дифференциальных рент используют следующий алгоритм:
. В каждом столбце определяют минимальный тариф и выделяют сответствую-щую клетку.
2. Выделенные клетки заполняют максимально возможными числами.
3. Т.к. в общем случае это распределение не удовлетворяет всех потребите-лей, чтобы на последующих шагах сокращать величину неудовлетворенных потребностей, необходимо оценить поставщиков.
ОПРЕДЕЛЕНИЕ 6. Строки, соответствующие поставщикам, запасы которых исчерпаны, а потребности выделенных потребителей не удовлетворены, являются отрицательными.
ОПРЕДЕЛЕНИЕ 7. Строки, соответствующие поставщикам, запасы которых не исчерпаны полностью, являются положительными.
ОПРЕДЕЛЕНИЕ 8. Строки, соответствующие поставщикам, запасы которых исчерпаны, а потребности выделенных потребителей удовлетворены, имеют нулевую оценку. При этом, если вторая заполненная клетка, стоящая в столбце, связанном с данной строкой еще одной заполненной клеткой, расположена в положительной строке, данная строка с нулевой оценкой считается положительной. В противном случае - отрицательной.
4. Для каждого столбца, имеющего выделенный тариф в отрицательной строке, находят разности между выделенным тарифом и ближайшим к нему по величине тарифом, стоящим в положительной строке.
5. Среди полученных разностей определяют минимальную. Это число называют промежуточной рентой.
6. Строят новую таблицу, при этом тарифы, стоящие в положительных строках, переписываются без изменения, а тарифы, стоящие в отрицательных строках, увеличиваются на величину промежуточной ренты.
7. Переходят к п.1.
ЗАМЕЧАНИЕ: а) если в строке или столбце оказывается более одной выделенной клетки, то заполняют, в первую очередь, те выделенные клетки, которые являются единственными в столбце или строке;
б) если удается распределить все запасы, то получают оптимальный план транспортной задачи.
4. Дополнительные ограничения транспортной задачи
1. Запрещенные маршруты.
Если по каким-либо причинам невозможно поставлять продукцию из п. Аi в п. Вj , предполагают тариф этого пути сколь угодно большой величиной М, сij =