Транспортная задача (1 а л.) 1 Определение транспортной модели
Пример_3.1(метод потенциалов)
жүктеу/скачать 0.49 Mb.
|
- Бұл бет үшін навигация:
- 3.3 Транспортная модель с промежуточными пунктами
| Пример_3.1(метод потенциалов)
Рассмотрим допустимое решение, полученное методом северо-западного угла. Таблица 3.2.
Н айдем потенциалы ui vj для пунктов отправления и назначения. Для этого, составим систему уравнений по заполненным клеткам, используя формулу (3.6): Из данной системы находим: Далее для каждой свободной клетки следует вычислить kij, по формуле (3.7): k13 = 0+0-4 = -4; k21 = 1+1-2 = 0; k32 = 2+0-2 = 0; k14 = 4+0-1 = 3; k31 = 1+0-3 = -2; k33 = 0+0-4 = -4. Среди чисел kij имеются положительные, следовательно, построенный опорный план не является оптимальным. Поэтому нужно перейти к следующему, то есть к новому допустимому решению. Наибольшим среди положительных чисел kij является k14=3, следовательно, клетку, которая содержит это число, следует заполнить на следующей итерации. Для этого строится цикл и производится сдвиг грузов по этому циклу. Наименьшее из чисел в минусовых клетках равно 10. Клетка А2В4 , в которой находится это число, становится свободной на следующей итерации. Таблица 3.3
Другие числа в таблице 3.4 получаются следующим образом: к числам, стоящим в плюсовых клетках таблицы 3.3, прибавляется число 10, а из чисел, стоящих в минусовых клетках оно вычитается. Клетка, содержащая минимальный объем перевозок, равный 10, становится свободной. После этих преобразований получаем новое опорное решение, при этом общая стоимость перевозок грузов составила Z=180. Таблица 3.4
Этот опорное решение проверяем на оптимальность. Снова находим потенциалы пунктов отправления и назначения. Для этого составим систему: Из данной системы находим: Для каждой свободной клетки вычисляем число: Таблица 3.5
Данное решение не является оптимальным. Поэтому переходим к новому решению (таблица 3.6). Составляем цикл пересчета и производим сдвиг грузов по этому циклу. Таблица 3.6.
Этотo опорное решение проверяем на оптимальность. Общие транспортные расходы уменьшились и составляют Z=140 у.е. Снова находим потенциалы пунктов отправления и назначения. Для этого составим систему: Из данной системы находим: Для каждой свободной клетки вычисляем число : Сравнивая сумму новых потенциалов ui+vj, отвечающую свободным клеткам таблицы 3.6, с соответствующими числами сij, видим, что указанные суммы потенциалов для всех свободных клеток не превосходят соответствующих чисел сij. Следовательно, данный план является оптимальным, так как все . Оптимальная матрица имеет вид: При данном опорном плане стоимость перевозок равна Z=140: Z=30+20+60+10+20=140. Схема грузоперевозок представлена на рисунке 3.3. Рисунок 3.3 3.3 Транспортная модель с промежуточными пунктами Транспортная модель с промежуточными пунктами соответствует реальной ситуации, когда между исходными и конечными пунктами имеются пункты для временного хранения грузов. Эта модель более общая, чем обычная, где перевозки осуществляются непосредственно между пунктами отправления и назначения. В стандартной транспортной модели предполагается, что прямой маршрут между пунктами производства и потребления является маршрутом минимальной стоимости. В транспортной задаче с разветвленной транспортной сетью задача нахождения кратчайшего маршрута не очевидна. Транспортная задача позволяет находить маршрут минимальной стоимости, если она ставится как задача с промежуточными пунктами, то есть с возможностью транзита груза. В этой постановке любая вершина может рассматриваться как транзитный пункт, то есть обладающая свойствами как исходного, так и конечного пункта. Поэтому в отличие от традиционной транспортной задачи в каждом транзитном пункте необходимо определить объем запасов и объем спроса. Если к реальным объемам запасов и спроса прибавить одну и ту же величину, то в замкнутой транспортной задаче это не приведет к изменениям транспортных потоков и не нарушит сбалансированность задачи. Вместе с тем появляется возможность организации потоков груза через транзитные пункты, не нарушая ограничения на ввоз-вывоз из данного пункта. Величина, прибавляемая к фактическим объемам запасов и спроса, должна обеспечивать возможность транзита суммарного объема имеющегося продукта. Эта величина называется буфером В и должна удовлетворять условию: (3.8). Пример 3.2 Решить транспортную задачу с транзитными пунктами, представленную схемой (рисунок 3.4): Рисунок 3.4 В данном случае задача является несбалансированной. Суммарные объемы производства превосходят объемы потребностей, поэтому вводится фиктивный пункт производства с запасами, равными 5 (рисунок 3.5). Рисунок 3.5 Так как задача с промежуточными пунктами, то любая вершина может рассматриваться как транзитный пункт, то есть обладающая свойствами как исходного, так и конечного пункта. Поэтому требуется введение буфера. Величина буфера В должна удовлетворять условию: Пусть В=30. Исходные данные заносятся в транспортную таблицу и методом «северо-западного угла» определяется первоначальное решение, которое далее проверяется на оптимальность и допустимость. Данное решение является неоптимальным, есть положительные оценки плана в клетках (1,3), (1,4),(4,3),(6,4). Целевая функция Z1=320. Выбирается клетка с наибольшим числом кij (1,3), именно с нее начинается цикл. Соответствующая переменная включается в базис (рисунок 3.6). Рисунок 3.6 – Итерация 1. В результате перемещений грузов по циклу получается новое решение, которое следует проверить на оптимальность и допустимость (рисунки 3.7-3.9). Рисунок 3.7 - Итерация 2. Целевая функция при данном распределении составляет Z2=230. Полученное значение целевой функции должно быть не больше предыдущего, так как задача решается на минимум. Рисунок 3.8 – Итерация 3. Целевая функция при данном распределении составляет Z3=180. Рисунок 3.9 – Итерация 4. На последней итерации получено оптимальное решение, о чем свидетельствуют неположительные оценки плана. Диагональные элементы таблицы получены в результате использования буфера и не дают информации об окончательном решении. Недиагональные элементы соответствуют реальным объемам перевозок. Схема оптимальных грузоперевозок представлена на рисунке 3.10. При этом значение целевой функции Zmin=165. Рисунок 3.10 – Схема перевозок к примеру 3.2 жүктеу/скачать 0.49 Mb. Достарыңызбен бөлісу:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||