Xreferat.com » Рефераты по экономико-математическому моделированию » Методы линейного программирования для решения транспортной задачи

Методы линейного программирования для решения транспортной задачи

решения транспортной задачи" width="375" height="198" align="BOTTOM" border="0" />


Откажемся от этой клетки, исключим эту строку из рассмотрения. Тогда придем к таблице, у которой строк на единицу меньше, а число столбцов сохранилось. Число строк в сумме с числом столбцов будет меньше (k+l) на одну единицу, но и число отмеченных клеток уменьшится на одну. Для этого случая можно построить цикл по принятому допущению. Этот цикл возьмем и для нашей таблицы, так как в соответствии с оговоркой вершины цикла могут быть и не вo всex отмеченных клетках.

Второй случай. Нет таких ситуаций, когда клетка одна. В каждой строке (столбце) больше чем одна клетка (или нет ни одной) (табл.6).


Методы линейного программирования для решения транспортной задачи


Отметим одну клетку знаком плюс, пойдем от нее по строке, попадем в клетку, которая в другом столбце и неединственная в нем; по столбцу перейдем в другую строку, по этой строке в другой столбец и т.д. Это можно было бы продолжать до бесконечности, если бы не было конечным число отмеченных клеток. На каком-то этапе придем в строку (столбец), в которой уже были, чем будет замкнута цепь, т.е. получен цикл.

Выше было показано, что теорема справедлива для k=2, l=2, т.е. для k+l=4. По доказанному она справедлива для случаев: k+l=5, т.е. k+l>4; k+l=6, т.е. k+l>5; k+l>6 и т.д., т.е. для любого макета.

Допустимый план Х (xij) называется ациклическим (нециклическим), если набор клеток с отличными от нуля компонентами плана xij>0 не содержит ни одного цикла.

Пример ациклического плана приведен в табл.7,


Методы линейного программирования для решения транспортной задачи


где точки обозначают клетки, в которых xij >0 (xij<0 недопустимы по смыслу задачи). Как покажем ниже, среди ациклических планов есть оптимальный.

Если в ациклическом плане Х (xij) число положительных компонентов

N = k + l - 1 (остальные компоненты - нули), то элементы aij матрицы тарифов из набора клеток, в которых расположены xij >0, будем называть Х-отмеченными.

Если же число положительных компонент плана N < k + l - l, то к клеткам, занятым положительными xij добавляем недостающие до (k+l-1) из нулевых клеток, лишь бы присоединенные клетки вместе с уже взятыми не допускали циклов. Тарифы aij всех взятых клеток, равно как и сами клетки, включаются в число Х-отмеченных.

Больше (k + l - 1) число компонент ациклического плана не может быть: Методы линейного программирования для решения транспортной задачи, так как уже при N=k+l по доказанной выше теореме всегда из выбранных клеток можно построить цикл.

Теорема 2 (основная теорема). Если для некоторого плана Х= (xij) kl транспортной задачи можно подобрать систему из k+l чисел u1, u2,…, ui,…, uk; vl, v2,…, vj,…, vl, удовлетворяющую следующим условиям: vj - ui  aij для всех i = 1, 2,., k; j = 1, 2,., l, а для xij>0 (xij (-X)) vj - ui = aij, то план Х будет оптимальным.

Числа ui, vj называются потенциалами пунктов отправления и пунктов назначения; условия vj - ui  aij и vj - ui = aij называют условиями потенциальности плана Х.

К каждой клетке (i, j) относятся два потенциала: i-ro пункта отправления ui и j-ro пункта назначения vj. Условия потенциальности словесно можно сформулировать так: разность потенциалов для всех без исключения клеток должна быть меньше или равна тарифу, а для занятых (Х-отмеченных) клеток она должна быть точно равна тарифу. План, удовлетворяющий этим условиям, называется потенциальным.

С учетом такой терминологии основную теорему можно изложить короче: если некоторый план транспортной задачи потенциален, то он оптимален.

Доказательство. Допустим, что для некоторого плана Х (xij) условия потенциальности выполнены, т.е. существует такая система чисел ui и vj, которая удовлетворяет условиям vj - ui = aij и vj - ui  aij (табл.8).


Методы линейного программирования для решения транспортной задачи


Иными словами, пусть план Х потенциален. Докажем, что этот план будет оптимальным. План Х дает значение функционалу


Методы линейного программирования для решения транспортной задачи.


Так как мы еще не знаем, оптимален план Х или нет, то возьмем заведомо оптимальный план Х' (xij) и посмотрим, какое значение он доставляет функционалу:


Методы линейного программирования для решения транспортной задачи


(транспортные расходы минимальны). Выполняются ли условия потенциальности для плана Х' - неизвестно, но каждой клетке (i, j) макета 8, исходя из потенциальности плана Х, соответствует неравенство vj - ui  aij или, наоборот, aij ≥ vj - ui. Возьмем из каждой клетки макета соответствующий х'ij, умножим его на левую и правую части последнего неравенства и сложим. Получим неравенство


Методы линейного программирования для решения транспортной задачи.


Двойную сумму в правой части обозначим для краткости буквой S:


Методы линейного программирования для решения транспортной задачи,


ее можно переписать в виде разности двух двойных сумм:


Методы линейного программирования для решения транспортной задачи.


Преобразуем эти суммы следующим образом. Первая из них в развернутом виде дает


Методы линейного программирования для решения транспортной задачи


или


Методы линейного программирования для решения транспортной задачи.


Аналогично вторую двойную сумму можно записать так:


Методы линейного программирования для решения транспортной задачи.


Тогда равенство Методы линейного программирования для решения транспортной задачи запишется в иной форме:


Методы линейного программирования для решения транспортной задачи.


Но Методы линейного программирования для решения транспортной задачи есть сумма компонент плана по j-му столбцу, она

равна потребности j-ro пункта назначения


Методы линейного программирования для решения транспортной задачи.


Аналогично Методы линейного программирования для решения транспортной задачи есть сумма компонент плана, взятая по i-й строке, она равна запасам в i-м пункте отправления


Методы линейного программирования для решения транспортной задачи.


Эти равенства сумм компонент по строке и столбцу соответственно запасам и потребностям будут выполняться для любого допустимого плана, в том числе и для взятого в самом начале плана Х (xij):


Методы линейного программирования для решения транспортной задачи


Поэтому для любых допустимых планов будем иметь


Методы линейного программирования для решения транспортной задачи


и в написанном выше равенстве Методы линейного программирования для решения транспортной задачи суммы xij можно заменить соответствующими суммами xij:


Методы линейного программирования для решения транспортной задачи


Теперь вернемся к форме записи


Методы линейного программирования для решения транспортной задачи.


В плане Х (xij) по условию его потенциальности для каждой положительной компоненты xij> 0 выполняется равенство vj - ui = aij.

Остальные компоненты плана равны нулю, и соответствующие слагаемые в сумме обратятся в нули. Поэтому полученная сумма будет равна


Методы линейного программирования для решения транспортной задачи.


Подставляя Методы линейного программирования для решения транспортной задачи в


Методы линейного программирования для решения транспортной задачи,


приходим к неравенству


Методы линейного программирования для решения транспортной задачи


или zmin ≥ zX. Иными словами, транспортные расходы по плану Х меньше или равны минимальным расходам. Но меньше минимальных они быть не могут, остается только равенство zX = zmin.. План Х доставляет минимальные издержки, т.е. он оптимален, что и требовалось доказать.

Таким образом, если план потенциален, то он оптимален. Это и является тем критерием, по которому судят об оптимальности плана.

Справедливо и обратное положение: если план оптимален, то он о6язательно потенциален. Это условие (необходимость) принимается без доказательства. [5]

10. Особенности решения транспортных задач с неправильным балансом


Может случиться, что в рассматриваемых пунктах запасы не равны потребностям: или запасы превосходят потребности, или же запасы не обеспечивают потребностей.

Такая модель задачи называется открытой. Для нее тоже можно отыскать план с минимумом транспортных издержек, но не будут удовлетворены все потребности или не будет вывезен весь груз, так как нельзя подобрать такую систему чисел, которая при суммировании по строкам давала бы один результат, а при суммировании по столбцам - другой.

Для решения задачи поступаем следующим образом.

Первый случай. Методы линейного программирования для решения транспортной задачи.

В математическую модель транспортной задачи введем фиктивный (l+l) - й пункт назначения. Для этого в матрице задачи предусмотрим один столбец, для которого потребность будет равна излишку груза:


Методы линейного программирования для решения транспортной задачи,


Все тарифы на доставку груза в этот пункт будем считать равными нулю. Получим новую задачу, причем для старой и новой задачи функционал будет один и тот же, так как цены на дополнительные перевозки равны нулю:


Методы линейного программирования для решения транспортной задачи min


Фиктивный потребитель обеспечивает совместность ограничений, не внося искажений в решение.

Второй случай.

Если запасов не хватает для удовлетворения потребностей, т.е. Методы линейного программирования для решения транспортной задачи, то вводим фиктивный (k+1) - й пункт отправления, которому приписываем запас груза, равный


Методы линейного программирования для решения транспортной задачи,


тарифы на доставку грузов из этого фиктивного склада опять, полагаем нулевыми. В матрице добавится одна строка. На функционале это не отразится, а система ограничений задачи станет совместной, т.е. станет возможным отыскание оптимального плана на минимум стоимости перевозок. [5]

11. Алгоритм решения транспортной задачи методом потенциалов


Алгоритм метода потенциалов разделяется на предварительный шаг, выполняемый в начале решения, и общий шаг, повторяемый до тех пор, пока не будет получен оптимум.


11.1 Предварительный шаг


Этот шаг включает следующих три этапа.

1. Находим допустимый ациклический план.

2. Составляем систему чисел - потенциалов пунктов отправления и пунктов назначения.

3. Анализируем систему на потенциальность. Если она потенциальна (т.е. план потенциален), то найденный план оптимален. Если система не потенциальна, приступаем к общему шагу.

Первый этап: нахождение допустимого ациклического плана способом северо-западного угла.

Невзирая на тарифы, начинаем составление плана с заполнения левой верхней клетки (1,1) (с северо-западного угла).

Смотрим на запасы M1 и потребности N1. Если M1 < N1, то в клетку (1,1) вписываем Ml (т.е. отдаем пункту назначения весь запас груза из первого пункта отправления - случай в таблице). Если N1 < M1, то в клетку (1,1) записываем N1, т.е. покрываем всю потребность первого пункта назначения за счет первого пункта отправления.

Перепишем баланс после первой операции (изменятся и потребности, и запасы). В первой строке остальные клетки можно прочеркнуть, так как весь груз пошел в первый пункт.

Второй тур начинаем опять с северо-западного угла. Удовлетворяем оставшуюся потребность первого пункта назначения, доставив туда (N1-Ml) единиц груза из второго пункта отправления. Если потребность первого пункта удовлетворена полностью, остальные клетки в первом столбце прочеркиваем. Переписываем баланс после второй операции.

Снова начинаем с северо-западного угла, удовлетворяем потребность второго пункта назначения и т.д., пока справа и снизу не будут стоять нули, т.е. весь груз распределен и потребности удовлетворены. Полученный внутри таблицы план будет допустимым. Его и берем в качестве исходного.

Второй этап предварительного шага: определение системы потенциалов.

Потенциал приписывается каждому пункту отправления (обозначается ui) и каждому пункту назначения (vj). Всего потенциалов k+l чисел. Они вносятся в специально отведенные для этого строку и столбец макета.

Для Х-отмеченных тарифов aij, число которых всегда равно (k + l - 1), должны выполняться равенства vj - ui = aij. Эти равенства и будут служить теми уравнениями, из которых находятся потенциалы. Однако таких уравнений будет только (k + l - 1), а неизвестных в системе (k + l), т.е. на единицу больше. Такая система уравнений имеет бесчисленное множество решений, любое из которых годится для нашей цели. Чтобы найти какое-то одно решение, значение одного потенциала выбираем произвольно. Остальные потенциалы определяем из решения системы. Третий этап предварительного шага: испытание плана или системы потенциалов на потенциальность. Потенциальность заключается в том, чтобы неравенство vj - ui < aij выполнялось для всех без исключений клеток. При этом Х-отмеченные клетки проверять не надо, так как потенциалы подобраны из условия выполнения в них равенства.

Выделяем положительные разности ij:


ij = vj - ui - aij > 0.


На этом предварительный шаг закончен.

11.2 Общий повторяющийся шаг


Общий шаг выполняется в такой последовательности.

1. Из положительных разностей ij находим наибольшую разность i0j0:

iojo = mах (vj - ui - aij > 0).

Пусть этот максимум имеет место для клетки (i0, j0). Включаем эту клетку в набор Х-отмеченных (k + l - 1) клеток. Клеток становится (k+l), а для такого их количества всегда можно построить цикл. Этот цикл будет в данной ситуации единственным.

Действительно, набор Х-отмеченных клеток является ациклическим. Добавим к нему одну клетку и предположим, что для нее можно построить два цикла. В этом случае всегда можно выделить цикл с вершинами, принадлежащими исходному набору, что противоречит условию его ацикличности. Поэтому такой цикл существует только один и задача заключается в его выделении.

2. Означиваем цикл, т.е. расставляем знаки в его вершинах. В исходной клетке (включаемой в набор) ставим плюс. Двигаемся по ходу или против хода часовой стрелки и ставим знаки попеременно минус, плюс, - пока не придем к исходной вершине. Так как количество вершин в цикле четно, направление движения безразлично. В результате получим так называемый означенный цикл, клетки которого делятся поровну на клетки положительной полуцепи и клетки отрицательной полуцепи.

3. Выбираем наименьшее значение перевозки в клетках отрицательной полуцепи (xij) - . Пусть оно равно :


min (xij) - = .


Если таких значений несколько, берем одно из них, безразлично какое.

4. Из перевозок каждой клетки отрицательной полуцепи вычитаем , а к перевозкам каждой клетки положительной полуцепи прибавляем . Эта операция называется сдвигом по циклу на величину .

Процесс сдвига меняет план, но план остается допустимым.

Действительно, допустимый план обеспечивает баланс в строках и столбцах; всякий план, не нарушающий этот баланс, будет допустимым. Любой цикл, по которому производится сдвиг, содержит в каждом ряду (строке, столбце) по две вершины. В одну клетку добавляем , а из другой вычитаем , и баланс не нарушается. Следовательно, план, найденный в результате сдвига, останется допустимым.

После сдвига в клетке отрицательной полуцепи с минимальной перевозкой будет стоять нуль, а в клетке (i0, j0), включенной в набор, окажется число . Первую клетку из плана исключаем, а вторую включаем; план остается по-прежнему ациклическим, так как единственный имевшийся цикл нарушается исключением клетки.

Полученный после сдвига план можно записать следующим образом:


Методы линейного программирования для решения транспортной задачи


5. для полученного после сдвига плана составляем новую систему потенциалов. Эти новые потенциалы можно вычислить так же, как это делалось в предварительном шаге, а можно найти исправлением уже имеющейся системы.

Для занятых клеток должны выполняться равенства Методы линейного программирования для решения транспортной задачи.

Поэтому берем в таблице клетку, занятую в результате сдвига, и исправляем для нее потенциалы так, чтобы их разность равнялась тарифу. Лучше изменять один из них - тот, который стоит в строке или столбце с меньшим числом занятых клеток.

Затем испытываем другие занятые клетки и корректируем последовательно остальные потенциалы. Изменению подвергаются, как правило, не все числа, и такой порядок сокращает расчеты.

6. Производим исследование новой системы на потенциальность, т.е. исследование найденного плана на оптимальность. Для этого проверяем выполнение неравенств vj - ui ≤ aij для всех незанятых клеток. Если для них неравенства выполняются, то система потенциальна и план оптимален, т.е. решение закончено. Если для каких-то клеток неравенства не выполняются, вычисляем разности ij и делаем снова общий шаг и т.д., до тех пор, пока не будет получен оптимальный план. Вырождение в транспортной задаче проявляется в том, что среди (k+l-1) Х-отмеченных клеток оказывается клетка с нулевой перевозкой. Если эта клетка не попадает в цикл, на нее не обращаем внимания. Если она попадает в положительную полуцепь цикла, то на следующем шаге вместо нуля получим в этой клетке положительное число. Если же нулевая клетка оказывается в отрицательной полуцепи, то =0, т.е. сдвиг надо делать на число нуль. Такой нулевой сдвиг плана не меняет, но нуль переходит в другую клетку, меняется набор Х-отмеченных клеток и система потенциалов. Это дает возможность на очередном шаге осуществить уже не нулевой сдвиг и изменить план в сторону его улучшения. Контроль вычислений осуществляется таким образом. В процессе решения задачи на каждом шаге полученный план проверяется на допустимость. Для этого компоненты плана суммируются по строкам и столбцам; суммы должны равняться соответственно запасам и потребностям пунктов. Окончательный (оптимальный) план проверяется по формуле, вытекающей из доказательства основной теоремы:


Методы линейного программирования для решения транспортной задачи,


при этом контролируются и потенциалы. [5]

12. Транспортная задача с ограничениями на пропускную способность


Транспортная задача с ограниченными пропускными спосо6ностями коммуникаций решается с дополнительным ограничением: Методы линейного программирования для решения транспортной задачи, где dij - пропускная способность звена (i, j) в единицу времени. Математическая модель задачи такова:


Методы линейного программирования для решения транспортной задачи,


при ограничениях


Методы линейного программирования для решения транспортной задачи


Эта задача разрешима при выполнении условий


Методы линейного программирования для решения транспортной задачи.


Для транспортной задачи с ограниченными пропускными способностями справедливы следующие условия оптимальности полученного решения:


Методы линейного программирования для решения транспортной задачи

Методы линейного программирования для решения транспортной задачи

Методы линейного программирования для решения транспортной задачи [8]


13. Транспортная задача по критерию времени


Кроме транспортной задачи по критерию стоимости существует задача транспортного типа по критерию времени. Постановка такой задачи состоит в следующем.

Дана матрица времени (tij) kl, где tij - время на перевозку груза из i-того пункта отправления в j-тый пункт назначения. Матрица перевозок грузов (xij) kl, где xij - количество перевозимого груза из i-того пункта отправления в j-тый пункт назначения. Известно также наличие груза Mi и спрос на него Nj, Методы линейного программирования для решения транспортной задачи. Требуется определить такой план перевозок, при котором весь груз будет доставлен потребителям в кратчайший срок.

Постановка транспортной задачи по критерию времени отличается от транспортной задачи по критерию стоимости лишь целевой функцией.

Если в задаче по критерию стоимости определялись минимальные транспортные издержки, то при решении задачи по критерию времени следует определить наименьший промежуток времени, за который груз будет доставлен потребителю. Решение такой задачи очень важно в случае доставки скоропортящегося продукта.

Исходный опорный план можно получить по правилам "северо-западного угла", "минимального элемента", приближенным методом. Далее просматриваем все занятые клетки и в них выбираем максимальное время t, за которое осуществляется опорный план перевозок, т.е. Т=max (tij), где клетки (i; k) занятые. Каждому плану перевозок будет соответствовать вполне определенное значение Т, зависящее от плана, т.е. T=f (x). Следовательно, нужно найти такой план доставки груза потребителям, для которого Т будет минимальным.

Определив максимальное значение Т для исходного плана, просматриваем ту клетку, для которой t=Т=max (tij). Например, такой клеткой является (p, q). Для этой клетки строится цикл, который включает в себя занятые и свободные клетки. Таких циклов может быть несколько. Однако при построении его следует учесть условия. Занятая клетка (p, q), для которой tiq = Т будет нечетной, следующая клетка по часовой или против часовой стрелки - четная, следующая - нечетная и т.д. Цикл состоит из двух полуциклов - четного и нечетного. Для нечетных клеток цикла обязательно должна быть загрузка больше нуля, а для четных - время меньше Т. Свободные клетки, для которых время tij> Т, прочеркиваются и в расчет не принимаются.

Построив цикл для разгрузочной клетки (p, q), для которой t (p, q) = Т, определяем наименьшую загрузку в нечетных клетках цикла.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: