2015-10-22
574
Для предложенных транспортных задач (таблица 7.12, 7.13, 7.14 и 7.15) составить начальные опорные решения методами северо-западного угла и минимальной стоимости и сравнить значения целевой функции.
|
Таблица 7.12.
| В А | ||||
Таблица 7.13.
| В А | ||||
Таблица 7.14.
Таблица 7.15.
Практическая работа № 8.1. «Транспортная задача. Проверка оптимальности решения. Метод потенциалов»
Цель работы:
Для проверки оптимальности решения введем потенциалы строк (ui, i=1,2,…,M) и столбцов (vj, j=1,2,…,N) – числа, которые определяются системой уравнений 
, составленных по занятым клеткам. Заметим, что занятых клеток M+N-1, поэтому мы имеем систему из M+N-1 уравнений с M+N неизвестными потенциалами. Это неопределенная система, нас интересует любое частное решение, поэтому любому из потенциалов можно на первом шаге дать значение, равное нулю. Далее последовательно находятся все потенциалы, которые записываются в дополнительный правый столбец и в дополнительную нижнюю строку таблицы транспортной задачи (общую схему см. в таблице 8.1.1).
|
|
|
| B A | B1 | B2 | … | BM | Потенциалы строк |
| A1 | с11 | с12 | … | с1N | u1 |
| A2 | с21 | с22 | … | с2N | u2 |
| … | … | … | … | … | … |
| AM | сM1 | сM2 | cMN | uM | |
| Потенциалы столбцов | v1 | v2 | … | vN |
Таблица 8.1.1
После определения потенциалов находим оценки для свободных клеток по правилу 
, записываем их в верхнюю часть каждой свободной клетки. Решение является оптимальным, если все найденные оценки неположительны (меньше или равны 0).
Пример 8.1.1. Проверить оптимальность решения, построенного в примере 7.1 (см. таблицу 7.11).
Решение. Сначала по таблице 7.11 определяем потенциалы.
Занятыми являются клетки (1;1), (2;1), (2;2), (2;3), (3;2). С учетом стоимостей, записанных в этих клетках, составляем систему уравнений
|
|
Таблица 8.1.2.
Пусть 
. Далее последовательно: из первого уравнения 
, из второго уравнения 
, из третьего 
, из четвертого 
, из пятого 
. Результаты собраны в таблице 8.1.2.
Расчет оценок проводится по формуле непосредственно в таблице 8.1.3, с учетом найденных выше потенциалов
| В А | ui | |||
| 0+4-3=1>0 - | 0+(-1)-0=-1<0 - | |||
| -2+1-4=-5<0 - | -2+(-1)-0=-3<0 - | -2 | ||
| vj | -1 |
Таблица 8.1.3.
|
|
|
Итак, видно, что в ячейке (1;2) оценка положительна, т.е. предложенное решение не является оптимальным.
Оптимизация решения. Одним из основных понятий в этом пункте является цикл – последовательность клеток таблицы транспортной задачи, в которой две и только две соседние клетки расположены в одной строке или в одном столбце, причем первая и последняя клетки также находятся в одной строке или в одном столбце. Известно, что в таблице транспортной задачи, содержащей опорное решение, для любой свободной клетки можно построить единственный цикл, содержащий эту клетку и часть занятых.
Если решение не оптимальное, то среди положительных оценок выбираем наибольшую (в случае равенства наибольших оценок – выбираем ячейку с наименьшей стоимостью). Для выбранной ячейки строим цикл, включающий эту клетку и часть занятых клеток, причем свободная клетка получает знак «+», а далее знак чередуется. Для попавших в цикл ячеек определяем величину q =min{xij:(i;j) – клетки, вошедшие в цикл со знаком «-»} Перемещаем перевозки по циклу в соответствии с правилом: в ячейках со знаком «+» q добавляется к значению xij, а в ячейках со знаком «-» q из xij вычитается. При этом клетка, в которой изначально находился объем перевозок, равный q, становится пустой, а свободная с выбранной «плохой» оценкой - занятой.
Замечание. Если минимальное значение q достигается в нескольких клетках, то только одна из них становится пустой, а в остальных объем перевозок выставляется равным 0; это позволяет сохранить необходимое количество занятых клеток.
После перемещения груза по циклу новое решение проверяется на оптимальность, и в случае необходимости процесс повторяется.
Пример 8.1.2. Найти оптимальное решение для транспортной задачи (пример 7.1. практической работы № 7)
|
Решение. Условия приведены в таблице 8.1.4. Задача была открытой, поэтому сначала был введен фиктивный потребитель. Начальное опорное решение, построенное методом минимальной стоимости – в таблице 7.11. Таблица 8.1.3 (с потенциалами и оценками) свидетельствует, что построенное решение не оптимальное, а ячейка (1;2) – единственная ячейка с положительной оценкой. С нее и начнем строить цикл. По таблице 8.1.3 видно, что его образуют ячейки (1;2), (2;2), (2;1), (1;1). В силу сказанного выше ячейки
|
Таблица 8.1.5.
Проверим оптимальность этого плана. По занятым клеткам составим систему уравнений для определения потенциалов и решим ее, полагая u1=0 (самостоятельно). Затем запишем потенциалы (см. таблицу 8.1.6) и в этой же таблице высчитаем оценки свободных клеток
| В А | ui | |||
| 0+(-1)-0<0 - | ||||
| 1+3-5<0 - | ||||
| -1+1-4<0 - | -1+(-1)-0<0 - | -1 | ||
| vj | -1 |
Таблица 8.1.6.
Все оценки отрицательны, значит, найденное опорное решение является оптимальным. Для завершения решения отбрасываем столбец с фиктивным
|
Таблица 8.1.7.
Заметим, что на втором складе осталось 10 единиц продукции, но это связано с тем, что задача была открытой.
Алгоритм полного решения транспортной задачи. Подводя итог сказанному выше, определим порядок действий при решении транспортной задачи с M поставщиками и N потребителями.
|
|
|
1) Определить, является ли задача закрытой или открытой; в последнем случае ввести фиктивного потребителя или поставщика и построить новую таблицу.
2) Построить начальное опорное решение X1 (рекомендуется метод минимальной стоимости) и убедиться, что занято необходимое число клеток (M+N-1).
3) Найти потенциалы с помощью занятых клеток из неопределенной системы ((i;j) – адреса занятых клеток), а затем – оценки для свободных клеток (здесь (i;j) – адреса свободных клеток).
4) В случае, когда все оценки 
, опорный план является оптимальным, и остается найти значение целевой функции f(X1). Если же среди оценок 
оказались положительные, то выбираем ячейку с наибольшей положительной оценкой, строим для нее цикл и переходим к новому опорному решению X2. При этом должно выполняться неравенство f(X2)£ f(X1). Затем возвращаемся к п. 3) алгоритма.
