Добавлен: 11.01.2024
Просмотров: 135
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
m + n −1, где n − число поставщиков; m − число потребителей; так как в закрытой транспортной задаче сумма запасов всех поставщиков равна сумме потребностей всех потребителей.
При заполнении таблицы поставок клетки, соответствующие неосновным (свободным) переменным, оставляют пустыми, а в клетки, соответствующие базисным переменным, проставляют числа, определяющие количество поставки
. В частности, если транспортная задача вырожденная, некоторые поставки могут иметь нулевую величину и в этом случае в базисную клетку записываем число 0.
Нахождение первоначального базисного распределения – опорного плана задачи − возможно любым из известных методов: наименьшей стоимости, "северо-западного угла", Фогеля, наибольшего предпочтения.
Рассмотрим метод "северо-западного угла". "Северо-западным углом" называется ячейка таблицы поставок, соответствующая значению переменной
. В эту ячейку записываем максимально возможную поставку, определяя её по формуле
(2.7)
Если
, то запас первого поставщика распределен полностью, и переходим к заполнению клетки с 
, записывая в неё наименьшее из чисел 
и 
. Если 
, то полностью удовлетворена потребность первого потребителя, тогда переходим к заполнению клетки с 
, записывая в неё наименьшее из чисел 
и 
. Так, постепенно двигаясь по таблице поставок, распределяем все запасы и удовлетворяем все потребности. Движение по таблице поставок может быть или по горизонтали, или строго по вертикали, а повороты при движении по трассе делаются только под прямым углом.
При заполнении таблицы следим за выполнением баланса по строкам и столбцам. Число заполненных клеток в полученном распределении должно быть равным числу базисных (основных) переменных. Если поворот происходит в клетке, где размер поставки равен нулю, то говорят о вырожденном плане поставок. В этом случае нулевая поставка записывается в клетку, где трасса распределения поставок делает поворот, и клетка считается занятой.
Если распределение выполняется без вычислительных ошибок, в последнюю заполняемую клетку запишется число, получаемое автоматически и равное остатку нераспределённых количеств у последнего из участвующих в распределении поставщиков или количеству неудовлетворённого спроса последнего потребителя.
Получаемое распределение по методу "северо-западного угла" для транспортной задачи, исходные данные которой содержатся в табл. 2.1, показано в табл. 2.2.
Найденный опорный план записывается матрицей
а значение целевой функции на этом плане, равное стоимости поставок, равно
Таблица 2.2.
Другим методом определения опорного плана поставок является метод наименьшей стоимости.
В первую очередь при определении объёмов поставок занимают клетки, имеющие наименьшие тарифы перевозок. Так, в рассматриваемом примере начнём с клетки
, имеющей тариф 2. От первого поставщика ко второму потребителю поставим максимально возможное количество груза, а именно 
. Потребности второго потребителя полностью удовлетворены, и все клетки второго столбца далее не рассматриваем.
На втором шаге распределения выбираем клетку
с тарифом 2 и делаем в неё поставку 
. Теперь запас третьего поставщика полностью израсходован и все клетки третьей строки далее не рассматриваем.
Соответственно, по наименьшим значениям остающихся неиспользованными в табл. 2.3 тарифов делаем следующие поставки:
Последняя поставка получается автоматически, так как остаётся только одна клетка для заполнения и туда помещается остаток запасов и потребностей. Они равны, поскольку сумма всех запасов и сумма всех потребностей равны.
Таблица 2.3.
Найденный опорный план записывается матрицей
а значение целевой функции на этом плане равно
Методом наименьшей стоимости получился лучший опорный план, так как значение целевой функции на нем меньше на 100 единиц. Тем не менее, и этот план может быть не оптимальным.
Критерий оптимальности для транспортной задачи: базисное распределение поставок оптимально тогда и только тогда, когда оценки всех свободных клеток неотрицательны.
Для определения оценок свободных клеток используют два взаимозаменяемых метода: распределительный и потенциалов. Рассмотрим один из них, а именно метод потенциалов.
Потенциалы числа для нахождения оценок допустимого плана, полученного в ходе распределения запасов поставщиков. Потенциалы для поставщиков и потребителей вычисляются по тарифам
занятых клеток таблицы поставок. Для потенциалов поставщиков 
и потребителей 
, соответствующих занятым клеткам, справедливы равенства
(2.8)
Так как занятых клеток на одну меньше, чем число потенциалов, значение одного из потенциалов (все равно какого) назначается произвольно и может быть любым действительным числом (обычно полагают равным нулю, чтобы не усложнять вычисления остальных потенциалов).
Разрешая равенства (2.8) относительно потенциалов, получаем их числовые значения. Оценки свободных клеток таблицы поставок рассчитываются по формулам
(2.9)
Если построенное первоначальное решение не удовлетворяет критерию оптимальности, то среди свободных клеток, имеющих отрицательную оценку, выбираем ту, для которой абсолютная величина оценки наибольшая. Отмечаем эту клетку знаком " + " и строим из неё цикл.
Циклом в таблице поставок называют ломаную линию, проходящую через занятые клетки, начинающуюся и заканчивающуюся в одной и той же свободной клетке. Эта ломаная
линия имеет вершины в клетках и звенья, лежащие вдоль строк и столбцов таблицы поставок. Причём ломаная должна быть связной, и в каждой вершине ломаной встречаются два звена, одно из которых располагается по строке, а другое − по столбцу. Клетки, через которые проходит ломаная линия, не делая в них поворота, называются транзитными, и имеющиеся в них поставки не участвуют в процессе перераспределения. Таким образом, цикл проходит через занятые клетки и только через одну свободную клетку, начинаясь и заканчиваясь в ней.
Последовательно отмечаем вершины цикла знаками " + " и " − " так, чтобы соседние вершины были отмечены противоположными знаками.
Среди поставок, находящихся в клетках помеченных знаком "−", выбираем наименьшую и помещаем ее в пустую клетку, помеченную знаком " + ". Затем рассчитываем новые значения поставок, прибавляя выбранное число ко всем поставкам, стоящим в клетках, помеченных знаком " + ", и вычитая его из всех поставок, стоящих в клетках, помеченных знаком " − ". Для вновь полученного плана поставок рассчитываем по занятым клеткам потенциалы, а затем оценки новых свободных клеток.
Если критерий оптимальности выполняется для полученного плана, то задача решена. В противном случае продолжаем процесс перераспределения поставок до тех пор, пока не будет получено оптимальное решение транспортной задачи.
Для вычисления оценки свободной клетки
таблицы поставок распределительным методом необходимо построить цикл для неё и найти оценку по формуле
где записаны в порядке прохождения цикла с чередованием знаков "+" и "" тарифы перевозок для всех клеток, образующих цикл оцениваемой свободной клетки.
Пример 2.7. Решить транспортную задачу с опорным планом, заданным в табл. 2.3, методом потенциалов.
Вычислим потенциалы для занятых клеток и результаты расчётов поместим в табл. 2.4:
При заполнении таблицы поставок клетки, соответствующие неосновным (свободным) переменным, оставляют пустыми, а в клетки, соответствующие базисным переменным, проставляют числа, определяющие количество поставки
. В частности, если транспортная задача вырожденная, некоторые поставки могут иметь нулевую величину и в этом случае в базисную клетку записываем число 0.Нахождение первоначального базисного распределения – опорного плана задачи − возможно любым из известных методов: наименьшей стоимости, "северо-западного угла", Фогеля, наибольшего предпочтения.
Рассмотрим метод "северо-западного угла". "Северо-западным углом" называется ячейка таблицы поставок, соответствующая значению переменной
. В эту ячейку записываем максимально возможную поставку, определяя её по формуле (2.7)Если
, то запас первого поставщика распределен полностью, и переходим к заполнению клетки с , записывая в неё наименьшее из чисел и . Если , то полностью удовлетворена потребность первого потребителя, тогда переходим к заполнению клетки с , записывая в неё наименьшее из чисел и . Так, постепенно двигаясь по таблице поставок, распределяем все запасы и удовлетворяем все потребности. Движение по таблице поставок может быть или по горизонтали, или строго по вертикали, а повороты при движении по трассе делаются только под прямым углом.
При заполнении таблицы следим за выполнением баланса по строкам и столбцам. Число заполненных клеток в полученном распределении должно быть равным числу базисных (основных) переменных. Если поворот происходит в клетке, где размер поставки равен нулю, то говорят о вырожденном плане поставок. В этом случае нулевая поставка записывается в клетку, где трасса распределения поставок делает поворот, и клетка считается занятой.
Если распределение выполняется без вычислительных ошибок, в последнюю заполняемую клетку запишется число, получаемое автоматически и равное остатку нераспределённых количеств у последнего из участвующих в распределении поставщиков или количеству неудовлетворённого спроса последнего потребителя.
Получаемое распределение по методу "северо-западного угла" для транспортной задачи, исходные данные которой содержатся в табл. 2.1, показано в табл. 2.2.
Найденный опорный план записывается матрицей
а значение целевой функции на этом плане, равное стоимости поставок, равно
Таблица 2.2.
| Поставщики | Потребители | Запасы поставщиков,  | |||||||
 |  |  |  | ||||||
 | 7 | | 2 | | 4 | | 8 | | 340 |
| | 120 | | 170 | | 50 | | | ||
 | 8 | | 9 | | 6 | | 5 | | 200 |
| | | | | | 100 | | 100 | ||
 | 3 | | 5 | | 7 | | 2 | | 160 |
| | | | | | | | 160 | ||
| Спрос потребителей,  | 120 | 170 | 150 | 260 |   | ||||
Другим методом определения опорного плана поставок является метод наименьшей стоимости.
В первую очередь при определении объёмов поставок занимают клетки, имеющие наименьшие тарифы перевозок. Так, в рассматриваемом примере начнём с клетки
, имеющей тариф 2. От первого поставщика ко второму потребителю поставим максимально возможное количество груза, а именно . Потребности второго потребителя полностью удовлетворены, и все клетки второго столбца далее не рассматриваем.На втором шаге распределения выбираем клетку
с тарифом 2 и делаем в неё поставку . Теперь запас третьего поставщика полностью израсходован и все клетки третьей строки далее не рассматриваем.Соответственно, по наименьшим значениям остающихся неиспользованными в табл. 2.3 тарифов делаем следующие поставки:
Последняя поставка получается автоматически, так как остаётся только одна клетка для заполнения и туда помещается остаток запасов и потребностей. Они равны, поскольку сумма всех запасов и сумма всех потребностей равны.
Таблица 2.3.
| Поставщики | Потребители | Запасы поставщиков, | |||||||
| | | | | ||||||
| | 7 | | 2 | | 4 | | 8 | | 340 |
| | 20 | | 170 | | 150 | | | ||
| | 8 | | 9 | | 6 | | 5 | | 200 |
| | 100 | | | | | | 100 | ||
| | 3 | | 5 | | 7 | | 2 | | 160 |
| | | | | | | | 160 | ||
| Спрос потребителей, | 120 | 170 | 150 | 260 | | ||||
Найденный опорный план записывается матрицей
а значение целевой функции на этом плане равно
Методом наименьшей стоимости получился лучший опорный план, так как значение целевой функции на нем меньше на 100 единиц. Тем не менее, и этот план может быть не оптимальным.
Критерий оптимальности для транспортной задачи: базисное распределение поставок оптимально тогда и только тогда, когда оценки всех свободных клеток неотрицательны.
Для определения оценок свободных клеток используют два взаимозаменяемых метода: распределительный и потенциалов. Рассмотрим один из них, а именно метод потенциалов.
Потенциалы числа для нахождения оценок допустимого плана, полученного в ходе распределения запасов поставщиков. Потенциалы для поставщиков и потребителей вычисляются по тарифам
занятых клеток таблицы поставок. Для потенциалов поставщиков и потребителей , соответствующих занятым клеткам, справедливы равенства (2.8)Так как занятых клеток на одну меньше, чем число потенциалов, значение одного из потенциалов (все равно какого) назначается произвольно и может быть любым действительным числом (обычно полагают равным нулю, чтобы не усложнять вычисления остальных потенциалов).
Разрешая равенства (2.8) относительно потенциалов, получаем их числовые значения. Оценки свободных клеток таблицы поставок рассчитываются по формулам
(2.9)Если построенное первоначальное решение не удовлетворяет критерию оптимальности, то среди свободных клеток, имеющих отрицательную оценку, выбираем ту, для которой абсолютная величина оценки наибольшая. Отмечаем эту клетку знаком " + " и строим из неё цикл.
Циклом в таблице поставок называют ломаную линию, проходящую через занятые клетки, начинающуюся и заканчивающуюся в одной и той же свободной клетке. Эта ломаная
линия имеет вершины в клетках и звенья, лежащие вдоль строк и столбцов таблицы поставок. Причём ломаная должна быть связной, и в каждой вершине ломаной встречаются два звена, одно из которых располагается по строке, а другое − по столбцу. Клетки, через которые проходит ломаная линия, не делая в них поворота, называются транзитными, и имеющиеся в них поставки не участвуют в процессе перераспределения. Таким образом, цикл проходит через занятые клетки и только через одну свободную клетку, начинаясь и заканчиваясь в ней.
Последовательно отмечаем вершины цикла знаками " + " и " − " так, чтобы соседние вершины были отмечены противоположными знаками.
Среди поставок, находящихся в клетках помеченных знаком "−", выбираем наименьшую и помещаем ее в пустую клетку, помеченную знаком " + ". Затем рассчитываем новые значения поставок, прибавляя выбранное число ко всем поставкам, стоящим в клетках, помеченных знаком " + ", и вычитая его из всех поставок, стоящих в клетках, помеченных знаком " − ". Для вновь полученного плана поставок рассчитываем по занятым клеткам потенциалы, а затем оценки новых свободных клеток.
Если критерий оптимальности выполняется для полученного плана, то задача решена. В противном случае продолжаем процесс перераспределения поставок до тех пор, пока не будет получено оптимальное решение транспортной задачи.
Для вычисления оценки свободной клетки
таблицы поставок распределительным методом необходимо построить цикл для неё и найти оценку по формуле где записаны в порядке прохождения цикла с чередованием знаков "+" и "" тарифы перевозок для всех клеток, образующих цикл оцениваемой свободной клетки.
Пример 2.7. Решить транспортную задачу с опорным планом, заданным в табл. 2.3, методом потенциалов.
Вычислим потенциалы для занятых клеток и результаты расчётов поместим в табл. 2.4: