close

Вход

Забыли?

вход по аккаунту

...бухгалтеру Відділу освіти Краснолиманської міської ради;pdf

код для вставкиСкачать
©Лекции подготовила доц. Мусина М.В.
Лекция 3.
Транспортная задача.
Транспортная задача (ТЗ) – специальный тип задач ЛП.
Постановка: имеется m поставщиков и n потребителей продукции. Заданы тарифы (стоимость) перевозки единицы продукции от поставщиков к потребителям, известны
запасы поставщиков и потребности каждого потребителя.
Требуется составить план поставок продукции от поставщиков к потребителям,
чтобы суммарная стоимость перевозок была min. Математическая постановка этой задачи
имеет вид:
m
n
 c x
ij ij
 min
i 1 j 1
m
x
ij
 b j ; j = 1,…,n
(1)
i 1
n
x
ij
 ai ; i = 1,…,m
j 1
xij ≥ 0
где xij – планы перевозок, cij – тарифы поставки продукции от i-того поставщика jтому потребителю, bj – потребность j-того потребителя, ai – запас у j-того поставщика.
Это задача ЛП со специальной матрицей. В задаче m*n неизвестных и m+n уравнений. Решение ТЗ – оптимальный план перевозок (поставок продукции). Поставленная задача (1) называется сбалансированной, если суммарный объем потребностей равен суммарному объему предложения продукции
n
m
 b j   ai
j 1
(2)
i 1
Если условие (2) не выполняется, то задача называется открытой.
Если условие сбалансированности не выполняется, то задача преобразуется в закрытую. Для этого в задачу вводят либо фиктивного поставщика недостающего объема
продукции (если потребности больше предложения), либо фиктивного потребителя лишней продукции (если предложение больше потребностей), тарифы которых полагают равными нулю.
Критерием эффективности в ТЗ является линейная функция, ограничения также
линейны, поэтому для их решения могут применяться методы линейной оптимизации, например, симплекс-метод. Однако специальная структура таких задач позволяет разработать более удобные методы.
Особенности ТЗ – все коэффициенты в уравнениях равны 1, что позволяет решать
задачу простыми способами. Уравнения не являются линейно независимыми в силу условия (2) (если задача сбалансирована). Число линейно-независимых уравнений – m+n-1,
переменных m*n, число базисных переменных – m+n-1.
k=m*n-(m+n-1)=(m-1)(n-1) – число свободных переменных.
Мы знаем, что в задачах ЛП оптимальные решения достигаются в одной из вершин
ОДР, где свободные переменные равны нулю, т.е. в нашем случае (m-1)(n-1) перевозок
должны быть равны нулю.
Любой план перевозок – допустимый, если он удовлетворят условию (1). План
опорный – если в допустимом плане отличны от нуля не более m+n-1 переменных. Если
число ненулевых xij в опорном плане равно (m+n+1), то план называется невырожденный,
иначе – вырожденный.
План – оптимальный, если он среди всех допустимых планов приводит к минимальной стоимости.
©Лекции подготовила доц. Мусина М.В.
В силу особой структуры ТЗ при ее решении не приходится решать СЛУ. Все операции по нахождению оптимального плана проводятся с таблицей. Т.е. составляют транспортную таблицу.
№
1
j
n
Предложение
1
c11
…
c1n
a1
…
i
…
cij
…
m
cm1
Спрос b1
…
…
cmn
bn
am
Решение задачи:
1. Построение начального (опорного) плана.
2. Улучшение плана до получения оптимального решения.
Составление опорного плана.
Возможно несколько методов построения: метод «северо-западного угла», минимального элемента, и прочие.
Рассмотрим, к примеру, метод СЗ угла.
Шаг 1. Составить транспортную таблицу.
Шаг 2. Транспортная таблица заполняется с левого верхнего (северо-западного) угла. При заполнении двигаются по строке вправо и по столбцу вниз. В клетку (1, 1) помещают максимально возможное число единиц продукции разрешенные ограничениями на
предложение и спрос: x11 = min(a1,b1).
Если a1<b1, то x11=a1 и предложение первого поставщика полностью исчерпано,
первую строку далее вычеркиваем, переходим ко второй, двигаясь по столбцу вниз. В
клетку (2, 1) помещают максимально возможное число единиц продукции, т.е. x21 =
min(a2,b1-a1). Если b1 – a1<a2, то x21=b1 - a1.
Спрос первого потребителя удовлетворяется. Вычеркиваем первый столбец и двигаемся по строке вправо, т.е. к клетке (2,2).
Процесс продолжается до тех пор, пока не исчерпано предложение и не исчерпан
спрос. Последней будет заполнена клетка (m,n).
Метод С-З угла наиболее простой метод, но и план перевозок, полученный таким
образом, достаточно далек от оптимального.
Метод минимального элемента.
Шаг 1. Составляем транспортную таблицу.
Шаг 2. Выбираем клетку таблицы, которой соответствует минимальное значение
тарифа.
Шаг 3. В выбранную клетку помещают максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос.
Если предложение производителя исчерпано, вычеркиваем соответствующую
строку, если спрос – столбец.
Если все клетки заполнены или вычеркнуты, то план построен, если нет, то переходим к шагу 2, без учета вычеркнутых клеток.
Заполнив таблицу, получим стоимость перевозок по методу минимального элемента.
Данная стоимость обычно бывает меньше стоимости, полученной по методу С-З
угла.
©Лекции подготовила доц. Мусина М.В.
Определение 1. Если при решении ТЗ число заполненных клеток совпадает с m+n1, то план перевозок невырожденный.
Определение 2. Если число заполненных клеток меньше m+n-1, то план перевозок
– вырожденный.
Вырожденный план получится, если на каком-то шаге одновременно удовлетворяется спрос потребителя и исчерпывается предложение поставщика, т.е. одновременно вычеркивается строка и столбец.
Проверка плана на оптимальность.
Для оценки плана на оптимальность вводится понятие косвенных затрат. КЗ – затраты, получаемы для маршрутов, по которым не осуществляется перевозки при данном
плане. Рассчитанные КЗ сравнивают с реальными затратами, которые имели бы место, если бы перевозки под данным маршрутам осуществятся. Если для всех невыбранных маршрутов КЗ не больше реальных, то данный план перевозок является оптимальным. Если
хотя бы для одного маршрута КЗ больше реальных, то план перевозок может быть улучшен путем введения в него данного маршрута.
Ввод нового маршрута соответствует вводу в список базисных переменных переменной транспортной задачи, соответствующей этому элементу. Эти рассуждения лежат в
основе методов для нахождения оптимального плана перевозок.
Например, метода потенциалов.
Получение оптимального плана транспортной задачи
с использованием метода потенциалов.
Шаг 1. Получение начального плана (метод С-З угла, мин. эл., и др.)
Шаг 2. Проверка плана на невырожденность. Общее число занятых клеток должно
быть m+n-1, если это не так, то рассмотрим дополнительные нули таким образом, чтобы
не образовался замкнутый цикл из занятых клеток (Вместо знака 0 ставим перечеркнутый
нуль, который считаем очень малой величиной). Выбираем такие клетки, где тариф минимальный.
Шаг 3. Проверка на оптимальность.
а. Определение потенциалов потребителей и производителей. Составляем систему
уравнений для заполненных клеток: ui+vj=cij, где ui – потенциал i-того поставщика, vj – потенциал j-того потребителя.
Т.к. Число уравнений m+n-1, а число неизвестных m+n полагают один производный
потенциал равным нулю. Обычно vj = 0.
б. Определение суммы потенциалов (косвенных затрат) для свободных клеток.
Dqp = uq + vp, где uq – потенциал q-того поставщика, vp – потенциал p-того потребителя.
в. Для каждой свободной клетки находим разность между cqp и Dqp (dqp=Dqp - cqp).
Если все dqp≤ 0 , то полученный план оптимальный, если хотя бы у одной клетки > 0, то
план может быть улучшен.
Шаг 4. Улучшение плана:
а. Выбор переменной, вводимой в список базисных - клетка с максимальным положительным значением разности (dqp).
Если несколько равных – выбираем любую.
Данная клетка ТТ заполняется.
б. Выбор переменной, выводимой из списка базисных.
Строят цикл с началом и концом в выбранной клетке, содержащий в качестве вершин заполненные клетки таблицы и состоящий из горизонтальных и вертикальных отрезков.
©Лекции подготовила доц. Мусина М.В.
В свободной клетке ставят +, а в остальных чередуясь – и +. Затем перераспределяем продукцию по циклу. Выбирают клетку со знаком «–» с наименьшим числом единиц
продукции. Это значение прибавлют к значениям, стоящим в клетках со знаком «+», и отнимают, там где «–».
Общий баланс не изменяется, при этом клетка с наименьшим количеством продукции становится свободной. Соответствующую переменную исключают из списка базисных. Далее повторяют все действия (с шага 2).
Дополнения и пояснения к транспортной задаче.
1. Уравнения для потенциалов записывают для всех клеток, где xij > 0.
2. Если опорноый план вырожденный, то в свободные клетки с минимальной cij
записывают перечеркнутый ноль (фиктивные поставки).
3. Понятие цикла: циклом в транспортной таблице называют несколько клеток,
соединенных замкнутой ломаной линией, каждый угол поворота которой кратен прямому углу.
4. Вырожденная задача: если в полученном допустимом решении какая-либо перевозка, например xrs одновременно и полностью выполняет ограничениям и по
пункту отправления Аr и по пункту назначения Вs, то либо запасы ar, либо заявки bs этих пунктов должны подвергнуты такой коррекции, чтобы появились недостающие базисные перевозки. Фиктивные поставки ставим либо в строку,
либо в столбец клетки xrs (выбирая мин. тариф)
При построении улучшенного плана эту нулевую поставку также перекидываем
по циклу, после чего 0 ставим в новую клетку, которая становится базисной, и
удаляем 0 из той клетки, где стоимость «-», т.е выводим ее из списка базисных.
По другому косвенные затраты называют псевдостоимостью.
1/--страниц
Пожаловаться на содержимое документа