Езу9у. Учебное пособие Рекомендовано методическим советом Уральского федерального университета в качестве учебного пособия для студентов вуза, обучающихся по направлениям подготовки
 Скачать 5.85 Mb.
|
|
Пример 6.5. Рассмотрим транспортную задачу, заданную распределитель- ной таблицей из примера 6.4 (табл. 6.19). Таблица 6.19 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 4 5 1 60 2 2 3 9 4 70 3 3 4 20 5 20 Объемы потребления 40 30 30 50 Ранее мы уже находили начальное базисное решение данной задачи и мето- дом «северо-западного угла», и методом «минимальной стоимости», при этом значение целевой функции при первом методе получилось равным 680, а при втором — 710. Поскольку в транспортной задаче целевая функция минимизи- руется, то очевидно, что лучше решение, полученное методом «северо-запад- ного угла», поэтому проверим сейчас его на оптимальность. Напомним, что это решение выглядело следующим образом (табл. 6.20). 174 Таблица 6.20 Пункты отправления Пункты назначения Объемы поставок 1 2 3 4 1 2 40 4 20 5 1 60 20 2 2 3 10 9 30 4 30 70 60 30 3 3 4 20 5 20 20 Объемы потребления 40 30 10 30 50 20 Вначале сразу проверим, что план не вырожден, т. е., что заполненных клеток будет в точности m + n − 1 штука, в нашем случае 3 + 4 − 1 = 6. Более того, начальный базисный план и не мог получиться вырожденным согласно договоренностям в методе «северо-западного угла». Далее составляем систему потенциалов. Всего у нас 3 пункта отправления и 4 пункта назначения, значит, потенциалы будут следующими: u 1 , u 2 , u 3 , v 1 , v 2 , v 3 , v 4 . Напомним, что система составляется только для заполненных клеток. Например, у нас заполнена клетка первой строки и столбца «1», при этом цена в этой клетке равна 2, тогда u 1 + v 1 = 2. Аналогично составляя для других запол- ненных клеток, получаем систему: 2 2 2 1 1 1 2 3 2 4 3 4 2, 4, 3, 9, 4, 5. u v u v u v u v u v u v + = + = + = + = + = + = В данной системе семь неизвестных и шесть уравнений, как и обсуждалось после приведения алгоритма. При этом была договоренность взять u 1 = 0. Тогда из первого уравнения получаем v 1 = 2, далее аналогичным образом находим зна- чения остальных потенциалов, в итоге получим следующее решение системы: u 1 = 0, u 2 = −1, u 3 = 0, v 1 = 2, v 2 = 4, v 3 = 10, v 4 = 5. Затем необходимо проверить выполнение критерия оптимальности, т. е. условие: ∆ ij = u i + v j − c ij ≤ 0. Сделать это будет удобно, если мы перепишем рас- пределительную таблицу следующим образом (табл. 6.21). То есть вместо номеров пунктов отправления и назначения мы записыва- ем соответствующие значения потенциалов, объемы поставок и потребления в таблицу не включаем за их ненадобностью при дальнейшем решении. Далее для каждой клетки по составленной таблице считаем оценку ∆ ij , записываем 175 ее значение в нижний правый угол соответствующей ячейки и для удобства восприятия обводим в прямоугольник, получаем табл. 6.22. Таблица 6.21 v j u i 2 4 10 5 0 2 40 4 20 5 1 –1 2 3 10 9 30 4 30 0 3 4 20 5 20 Таблица 6.22 v j u i 2 4 10 5 0 2 40 0 4 20 0 5 5 1 4 –1 2 –1 3 10 0 9 30 0 4 30 0 0 3 –1 4 0 20 –10 5 20 0 Обратите внимание, что все оценки для заполненных клеток (элементов базисного плана) нулевые, что естественно следует из пояснения к критерию оптимальности. И такая ситуация будет всегда, поэтому можно не находить значения оценок для заполненных клеток, но советуем это делать для проверки правильности нахождения потенциалов. Ведь если хотя бы одна оценка на за- полненной клетке будет ненулевой, то это указывает на ошибку в решении системы потенциалов. В нашем случае среди оценок пустых клеток имеются положительные, что говорит о неоптимальности первоначального базисного решения. Следовательно, необходимо перейти к новому базисному решению (новому плану поставок), которое ближе к оптимальному, чем предыдущее. Необходимо ввести в базис свободную переменную, имеющую наибольшую положительную оценку. В нашем примере наибольшая оценка равна пяти, и ей соответствует клетка, стоящая в первой строке в третьем столбце. Именно в эту клетку вводим новую переменную, которую обозначаем θ. Далее строим цикл по занятым клеткам, получим табл. 6.23. Таблица 6.23 v j u i 2 4 10 5 0 2 40 0 4 20 0 5 θ 5 1 4 –1 2 –1 3 10 0 9 30 0 4 30 0 0 3 –1 4 0 20 –10 5 20 0 176 Вершинам цикла присвоим знаки: в клетке, в которой стоит θ, ставим « + », далее поочередно «−», « + », «−», имеем табл. 6.24. Далее находим θ как наименьшее значение из элементов плана, стоящих в минусовых клетках, т. е. в нашем случае θ = 20, далее в минусовых клетках вычитаем 20, а в плюсовых прибавляем. При этом в клетке, стоящей в первой строке во втором столбце, после вычитания получается ноль, это означает, что данный элемент плана выводится из базиса, и этот ноль не записываем. В итоге получим табл. 6.25. Таблица 6.24 v j u i 2 4 10 5 0 2 40 0 4 20 – 0 5 θ + 5 1 4 –1 2 –1 3 10 + 0 9 30 – 0 4 30 0 0 3 –1 4 0 20 –10 5 20 0 Таблица 6.25 v j u i 2 4 10 5 0 2 40 0 4 0 5 20 5 1 4 –1 2 –1 3 30 0 9 10 0 4 30 0 0 3 –1 4 0 20 –10 5 20 0 Имеем новое базисное решение, которое также невырожденное, так как элементов в нем по-прежнему шесть. Проверяем теперь его аналогичным обра- зом на оптимальность, для чего составляем систему потенциалов для непустых клеток: 3 2 2 1 1 1 2 3 2 4 3 4 2, 5, 3, 9, 4, 5. u v u v u v u v u v u v + = + = + = + = + = + = Учитывая договоренность, что u 1 = 0, имеем решением системы: u 1 = 0, u 2 = 4, u 3 = 5, v 1 = 2, v 2 = −1, v 3 = 5, v 4 = 0. Далее для каждой клетки по составленной таблице считаем оценку ∆ ij и записываем ее значение в нижний правый угол соответствующей ячейки и для удобства восприятия обводим в прямоугольник, получаем табл. 6.26. И снова присутствуют положительные оценки, значит, полученный базис- ный план неоптимальный, необходимо его улучшать. Для этого вновь ищем наибольшую оценку, у нас это 4, причем их две одинаковых. Выбираем соглас- 177 но алгоритму ту, у которой цена наименьшая, т. е. клетку, стоящую во второй строке, первом столбце, и присваиваем ей θ. Затем строим цикл, отмечаем плюсовые и минусовые клетки, получаем табл. 6.27. Таблица 6.26 v j u i 2 –1 5 0 0 2 40 0 4 –5 5 20 0 1 –1 4 2 4 3 30 0 9 10 0 4 30 0 5 3 4 4 0 20 –10 5 20 0 Таблица 6.27 v j u i 2 –1 5 0 0 2 40 – 0 4 –5 5 20 + 0 1 –1 4 2 θ + 4 3 30 0 9 10 – 0 4 30 0 5 3 4 4 0 20 –10 5 20 0 Величине θ присваиваем наименьшее значение из минусовых клеток, т. е. 10. В плюсовых клетках прибавляем 10, в минусовых — вычитаем 10. При этом стоит обратить внимание, что тем самым мы вывели из базиса элемент с самой дорогой ценой, равной 9, получаем табл. 6.28. Таблица 6.28 v j u i 2 –1 5 0 0 2 30 0 4 –5 5 30 0 1 –1 4 2 10 4 3 30 0 9 0 4 30 0 5 3 4 4 0 20 –10 5 20 0 Имеем новое базисное невырожденное решение. Проверим его на опти- мальность. Для этого составляем систему потенциалов: 3 2 1 1 1 1 2 2 2 4 3 4 2, 5, 2, 3, 4, 5. u v u v u v u v u v u v + = + = + = + = + = + = 178 Ее решением являются u 1 = 0, u 2 = 0, u 3 = 1, v 1 = 2, v 2 = 3, v 3 = 5, v 4 = 4. Далее для каждой клетки по составленной таблице считаем оценку ∆ ij , записываем ее значение в нижний правый угол соответствующей ячейки и для удобства восприятия обводим в прямоугольник, получаем табл. 6.29. И вновь имеется положительная оценка, следовательно, полученное новое решение не является оптимальным. Повторяем действия алгоритма, в клетку с положительной оценкой вводим элемент θ, строим цикл по указанным выше правилам, отмечаем плюсовые и минусовые клетки, получаем табл. 6.30. Таблица 6.29 v j u i 2 3 5 4 0 2 30 0 4 –1 5 30 0 1 3 0 2 10 0 3 30 0 9 –4 4 30 0 1 3 0 4 0 20 –14 5 20 0 Таблица 6.30 v j u i 2 3 5 4 0 2 30 – 0 4 –1 5 30 0 1 θ + 3 0 2 10 + 0 3 30 0 9 –4 4 30 – 0 1 3 0 4 0 20 –14 5 20 0 Величина θ равна наименьшему значению элементов, стоящих в минусо- вых клетках, т. е. 30. Далее в плюсовых клетках прибавляем 30, в минусовых вычитаем. После вычитания у нас в двух клетках получаются нули, но согласно алгоритму один ноль оставляем, а второй убираем, например тот, который стоит в клетке с наименьшей ценой, имеем табл. 6.31. Благодаря тому, что один ноль мы оставили, новое базисное решение невы- рожденное. Проверим его на оптимальность. Для этого составляем систему потенциалов: 3 1 4 2 1 2 2 3 3 4 1 1 5, 1, 2, 3, 3, 5. u v u v u v u v u v u v + = + = + = + = + = + = Ее решением являются u 1 = 0, u 2 = 3, u 3 = 4, v 1 = −1, v 2 = 0, v 3 = 5, v 4 = 1. Далее для каждой клетки по составленной таблице считаем оценку ∆ ij , получаем табл. 6.32. 179 Таблица 6.31 v j u i 2 3 5 4 0 2 0 4 –1 5 30 0 1 30 3 0 2 40 0 3 30 0 9 –4 4 0 1 3 0 0 4 0 20 –14 5 20 0 Таблица 6.32 v j u i –1 0 5 1 0 2 –3 4 –4 5 30 0 1 30 0 3 2 40 0 3 30 0 9 –1 4 0 4 3 0 0 4 0 20 –11 5 20 0 Все оценки неположительные, значит, полученное решение является оп- тимальным. Найдем значение целевой функции Z (X) = 5 · 30 + 1 · 30 + 2 · 40 + + 3 · 30 + 0 · 3 + 5 · 20 = 450. Заметим, что при первоначальном решении получен- ным методом «северо-западного угла» целевая функция была равной 680, что значительно больше, чем 450. З а м е ч а н и я: 1. Если оценки равны нулю только в заполненных клетках (при базисных элементах), то решение определяется однозначно. Если нулевые оценки есть и в пустых клетках, то решение определяется неоднозначно. В предыдущем примере нулевые оценки имеются в пустых клетках, значит, решение опреде- ляется неоднозначно. 2. Метод потенциалов является относительно простым для решения транс- портной задачи на бумаге, при этом схема расчетов не совсем очевидна, поэтому в большинстве случаев для решения с использованием ЭВМ применяется метод дифференциальных рент. В нем сначала наилучшим образом распределяют между пунктами назначения часть груза и на последующих итерациях посте- пенно уменьшают общую величину нераспределенных поставок. 6.4. Решение транспортной задачи открытого типа При нарушении баланса между объемами производства и потребления в алгоритм решения транспортной задачи вносятся следующие дополнения. Если суммарные поставки меньше суммарных потребностей, то есть 1 1 , m n i j i j a b = = < ∑ ∑ 180 то вводят фиктивный пункт производства с объемом 1 1 1 n m m j i j i a b a + = = = − ∑ ∑ При этом в распределительной таблице появляется дополнительная строка. Цены в клетках этой строки определяются издержками (штрафами, неустой- ками) ввиду недогрузки мощностей потребителей. Если информация об этих издержках неизвестна, то их принимают равными одному и тому же числу (чаще всего нулю). Если суммарные поставки больше суммарных потребностей, то есть 1 1 , m n i j i j a b = = > ∑ ∑ то вводят фиктивный пункт потребления с объемом 1 1 1 m n n i j i j b a b + = = = − ∑ ∑ После вычисления в распределительной в таблице появляется дополнитель- ный столбец. Цены в клетках этого столбца соответствуют затратам на хранение неотправленного груза (поставки последнего столбца — неотправленный груз для каждого из поставщиков). Если информация об этих затратах отсутствует, то их принимают равными одному и тому же числу (чаще всего нулю). Модель задачи становится закрытой, и далее задачу решают по общей схеме. Оптимальное решение задачи выписывается из таблицы без фиктивной строки (столбца), и в расчете целевой функции фиктивные поставки (потребление) не учитываются. 6.5. Применение транспортных моделей в экономических задачах Алгоритм и методы решения транспортной задачи могут быть использо- ваны при решении некоторых экономических задач, не имеющих непосредст- венного отношения к транспортировке грузов. В этом случае величины цен c ij имеют различный смысл в зависимости от конкретной задачи. 1. Оптимальное закрепление за станками операций по обработке деталей. В них величина c ij является производительностью. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения c ij берутся с отрицательным значением. 181 2. Оптимальные назначения или проблема выбора. Имеется m механизмов, которые могут выполнять n различных работ с производительностью c ij . Зада- ча позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности. 3. Задача о сокращении производства с учетом суммарных расходов на из- готовление и транспортировку продукции. 4. Увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега, сокращение которого позволит уменьшить количество автомобилей для перевозок за счет увеличения их производитель- ности. 5. Решение задач с помощью метода запрещения перевозок. Использует- ся в том случае, если груз от некоторого поставщика по каким-то причинам не может быть направлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение цены. Задачи для самостоятельного решения 6.1. С трех оптовых баз осуществляется доставка товара в сеть из четырех магазинов. В таблице заданы количество товара, имеющегося на каждой базе, объем товара, необходимого каждому магазину, а также стоимость (ден. ед.) перевозки единицы товара с базы в магазин. Составить математическую модель транспортной задачи. Оптовые базы Магазины Объемы поставок М 1 М 2 М 3 М 4 1 5 1 3 4 30 2 1 2 4 3 10 3 7 1 2 8 40 Объемы потребления 24 16 25 15 6.2. Данные для транспортной задачи приведены в таблице. 1) Определить, закрытого типа данная задача или открытого. 2) Найти первоначальный план перевозки методом «северо-западного» угла и соответствующую суммарную стоимость перевозки. 3) Найти первоначальный план перевозки методом «минимальной стои- мости» и соответствующую суммарную стоимость перевозки. 4) Определить, какой план более выгодный. 182 Пункты отправки Пункты потребления Объемы поставок А В С 1 2 5 3 25 2 4 1 5 15 3 3 6 7 60 Объемы потребления 20 30 50 6.3. Решить транспортную задачу открытого типа двумя способами: 1) методом «северо-западного угла»; 2) методом «минимальной стоимости». Сравнить результаты. Пункты отправки Пункты потребления Объемы поставок А В С 1 3 4 2 20 2 5 6 3 10 3 7 1 6 40 Объемы потребления 14 16 20 6.4. Решить транспортную задачу. Пункты отправки Пункты потребления Объемы поставок А В С 1 4 2 3 40 2 5 10 8 80 3 5 8 12 90 Объемы потребления 50 70 75 6.5. Решить транспортную задачу методом «минимальной стоимости». Оптовые базы Магазины Объемы поставок М 1 М 2 М 3 М 4 1 26 15 10 8 25 2 10 6 20 11 10 3 11 70 50 35 20 4 21 15 5 15 30 5 11 30 6 4 15 Объемы потребления 40 10 20 25 183 6.6. Фирма поставляет бытовую технику с трех складов в четыре магазина. На складах имеется 120, 65 и 35 ед. техники соответственно. Магазинам тре- буется 90, 70, 40 и 20 ед. техники соответственно. Стоимость перевозки одной единицы техники приведена в таблице. Как спланировать перевозку, чтобы суммарные транспортные затраты были минимальны? Склады Магазины М |