 |
|
Математические методы решения транспортной задачи
Транспортная задача является одной из важнейших частных задач ЛП. Если условия транспортной задачи и ее опорный план записаны в виде таблицы, то клетки, в которых находятся отличные от нуля перевозки, называются занятыми, остальные - незанятыми. Занятые клетки соответствуют базисным неизвестным, и для невырожденного опорного плана их количество равно m+n-1. Всякий план транспортной задачи, содержащий более m+n-1 занятых клеток, не является опорным, так как ему соответствует линейно зависимая система векторов. При таком плане в таблице всегда можно построить замкнутый цикл, с помощью которого уменьшают число занятых клеток.
Как и для других задач ЛП, итерационный процесс по отысканию оптимального плана транспортной задачи начинают с опорного. Первоначальный опорный план транспортной задачи решается несколькими методами: методом северо-западного угла, минимальной стоимости и двойного предпочтения и т.д. От того, как построен первый план, зависит количество шагов, необходимых для получения оптимального решения.
Рассмотрим транспортную задачу на примере.
На четыре магазина доставляется товары из трех пунктов хранения. В первом пункте имеется 400, во втором-700 и в третьем -1200 т товара. В магазины товары должны быть доставлено в следующих количествах: на первый -700, на второй -200, на третьий -600 и четвертый -800 т.
Расстояние между пунктами хранения и магазинами приведены в таблице 23.
Таблица 23.
| Пункты хранения | М а г а з и н ы 1 2 3 4 | |||
Требуется составить такой план транспортировки товара, который обеспечит наименьший объем грузоперевозок в т-км.
В рассматриваемой задаче суммарный запас товара в пунктах хранения равен суммарной потребности магазинов, т.е. задача называется закрытой.
Обозначим хij - количество товара, перевозимого из i -го пункта хранения на j-й магазин.
Исходные данные задачи можно представить в виде транспортной таблицы, строки которой соответствуют пунктам хранения, а столбцы - магазинам. В правых верхних углах клеток таблицы представлены расстояния от пунктов хранения до магазинов, в левых нижних углах- искомые размеры перевозок.
Таблица 24
| Пункт хранения | Запасы | ||||
| х11 | х12 | х13 | х14 | ||
| х21 | х22 | х23 | х24 | ||
| х31 | х32 | х33 | х34 | ||
| Потребность |
Рассмотрим решение задачи потенциальным методом.
Алгоритм потенциального метода состоит из следующих этапов:
1) Нахождение первого базисного (опорного) плана.
2) Проверка полученного плана на оптимальность.
3) Последовательное улучшение плана до получения оптимального.
Для построения первого опорного плана рассмотрим метод северо-западного угла (таблица 25).
Построение начинаем с северо-запада, то есть с клетки(1.1). Записываем в нее максимально возможную перевозку груза- 400т., то есть наименьшую из величин (400, 700). Таким образом, товар хранимый в первом пункте, полностью вывозится, а потребность первого магазина остается неудовлетворенным на величину 700-400=300.
Таблица 25
| Пункт хранения | Запасы | ||||
| Потребность |
Теперь сравниваем эту разность с запасом товара во втором пункте (700). Меньшую из этих величин записываем в клетку (2.1). Теперь полностью удовлетворена потребность первого магазина. Во втором пункте остается не вывезенными 400 т товара (700-300=400). Сравниваем эту величину с потребностью второго магазина (200) и наименьшую из них записываем в клетку (2.2). Теперь во втором пункте остаются не вывезенными 200 т товара. Сравниваем эту величину с потребностью третьего магазина (600) и наименьшую из них записываем в клетку (2.3). Далее в клетку (3.3) записываем 400 т и в клетку (3.4)-800 т товара. Полученный план является базисным, так как число загруженных клеток в нем равно m+n-1 =6. Сумма стоимости перевозимого товара на расстояния равна:
F= 18х400+17х300+10х200+11х200+10х400+9х800=27000 т-км.
Теперь необходимо определить является ли полученный план оптимальным. Для этого используем метод потенциалов.
Потенциалы -это числа, приписываемые каждой строке и каждому столбцу. Значит потенциалов m+n. Обозначим потенциалы строк U1, U2, U3, а столбцов V1, V2, V3, V4. Расстояния между пунктами хранения и магазинами- Сij .
Из теоремы следует, для того чтобы первоначальный план был оптимальным, необходимо выполнение следующих условий:
а) для каждой занятой клетки сумма потенциалов должна быть равна стоимости единицы перевозки, стоящей в этой клетке:
Ui +Vj = Cij , при хij >0
б) для каждой незанятой клетки сумма потенциалов должна быть меньше или равна стоимости единицы перевозки, стоящей в этой клетке: Ui +Vj <= Cij , при хij >0
Если хотя бы одна незанятая клетка не удовлетворяет условию б), то опорный план является не оптимальным и его нужно улучшить. Для проверки плана на оптимальность необходимо сначала построить систему потенциалов. Систему потенциалов можно построить только для невырожденного опорного плана.
Такой план содержит m+n-1 занятых клеток, поэтому для него можно составить систему из m+n-1 линейно независимых уравнений вида а) с n+m неизвестными.
Таблица 26
| Пункт Vj хранения Ui | V1 | V2 | V3 | V4 | Запасы |
| 1 U1 | 400 - | + | |||
| 2 U2 | 300 + | - 11 | |||
| U3 | + 10 | - 9 | |||
| Потребность |
Уравнений на одно меньше, чем неизвестных, поэтому система является неопределенной, и одному неизвестному придают нулевое значение. После этого остальные потенциалы определяются однозначно.
Рассчитаем потенциалов для занятых клеток. U1+V1=18; U2+V1=17; U2+V2=10; U2+V3=11; U3+V3=10; U3+V4=9 и полагаем U1=0, тогда V1=18, U2=17-18=-1, V2=10+1=11, V3=11+1=12; U3=10-12=-2; V4=9+2=11.
После определения потенциалов план исследуется на оптимальность.
Для не занятых клеток
U1+V2<=12, 0+11<=12, 11<=12 - верно;
U1+V3<=13, 0+12<=13, 12<=13 - верно;
U1+V4<=7, 0+11<=7, 11<=7 - неверно;
U2+V4<=13, -1+11<=13, 10<=13 - верно;
U3+V1<=15, -2+18<=15, 16<=15 - неверно;
U3+V2<=11, -2+11<=11, 9<=11 - неверно.
План не оптимален и его надо улучшать. Для улучшения среди неверных значений берут клетку с наибольшим по абсолютной величине значением и строят из нее замкнутый контур или цепочку. В данном случае берем клетку (1.4). Одна вершина контура должна лежать в этой свободной клетке, остальные- только в занятых клетках. Число вершин всегда должно быть четное. Контур, построенный из клетки (1.4), обозначен пунктиром. В вершине свободной клетки ставится знак (+), в остальных клетках знаки (+) и (-) чередуются.
В клетках с отрицательными вершинами выбирается наименьший объем перевозок, который вычитается из всех объемов перевозок по клеткам, имеющим отрицательные вершины контура, и прибавляется к объемам перевозок по клеткам с положительными вершинами контура. Отрицательные вершины контура расположены в клетках (1-1) с объемом перевозок, равным 400т, (2-3) -200т и (3-4) с объемом перевозок, равным 800т. Следовательно, меньший объем перевозок в клетках с отрицательными вершинами контура равен 200 т. Этот объем вычитаем из клеток (1-1) и (3-4), и прибавляем к клеткам (1-4), (2-1) и (3-3) и записываем в новую таблицу 27. Объем груза 200т как бы переместился по контуру в свободную клетку (1-4) с наибольшей по абсолютному значению величиной.
Таблица 27
| Пункт Vj хранения Ui | V1 | V2 | V3 | V4 | Запасы |
| U1 | 200 - | 200 + | |||
| U2 | |||||
| U3 | + | 600 - | |||
| Потребность |
В таблице 27 вновь проверяется объем ограничений по строкам и столбцам. Суммарные издержки на перевозку при таком плане равны
F= 200х18+200х7+500х17+200х10+600х10+600х9=26900 т-км.
Или на 100 т-км меньше, чем в первоначальном плане.
Составленный план опять принимается за исходный, и вся вычислительная процедура повторяется снова.
Для занятых клеток составим уравнения потенциалов.
U1+V1=18; U1+V4=7; U2+V1=17; U2+V2=10; U3+V3=10; U3+V4=9, полагаем U1=0, тогда V1=18, V4=7, U2 =-1, V2=11, U3 =2, V3=8.
Затем проверяем план на оптимальность путем проверки условия б)
U1+V2 <=12, 0+11<=12, 11<=12 - верно.
U1+V3 <=13, 0+8<= 13, 8<=13 - верно.
U2+V3 <=11, -1+8<=11, 7<=11 - верно.
U2+V4 <=13, -1+7<= 13, 6<= 13 - верно.
U3+V1<= 15, 2+18<=15, 20<=15 - неверно.
U3+V2 <=11, 2+11<=11, 13<=11 - неверно.
План не оптимален. Для улучшения среди неверных значений берут клетку с наибольшим по абсолютной величине значением и строят из нее замкнутый контур или цепочку. В данном моменте можно взять клетку (3-1). Одна вершина контура должна лежать в этой свободной клетке, остальные - только в занятых клетках. Отрицательные вершины контура расположены в клетках (1-1) с объемом перевозок, равным 200т и (3-4) - 600т. Следовательно, меньший объем перевозок в клетках с отрицательными вершинами контура равен 200 т. Этот объем вычитаем из клеток (1-1) и (3-4), прибавляем к клеткам (3-1) и (1-4) и записываем в новую таблицу 28.
Таблица 28
| Пункт Vj хранения Ui | V1 | V2 | V3 | V4 | Запасы |
| U1 | |||||
| U2 | 500 - | + | |||
| U3 | 200 + | 600 - | |||
| Потребность |
Суммарные издержки на перевозку при таком плане равны:
F= 400х7+500х17+200х10+200х15+600х10+400х9=25900 т-км
или на 1000 т-км меньше, чем в предыдущим плане.
Составленный план опять принимается за исходный, и вся вычислительная процедура повторяется снова.
Составим уравнения потенциалов для занятых клеток.
U1+V4=7; U2+V1=17; U2+V2=10; U3+V1=15; U3+V3=10; U3+V4=9;
Полагаем, что U1=0, тогда V4=7, U3 =2, V1 =13, U2=4, V2=6, V3=8.
Для незанятых клеток проверяем условия оптимальности.
U1+V1<=18, 0+13<=18, 13<=18 - верно
U1+V2<=12, 0+6<=12, 6<=12 - верно
U1+V3<=13, 0+8<=13, 8<=13 - верно
U2+V3<=11, 4+8<=11, 12<=11 - неверно
U2+V4<=13. 4+7<=13, 11<=13 - верно
U3+V2<=11 2+6<=11, 8<=11 - верно
Условие не выполняется в клетке (2-3). Построим контур. Отрицательные вершины контура расположены в клетках (2-1) и (3-3) с перевозками соответственно 500 и 600т. Таким образом, заполняем следующую таблицу 29.
Таблица 29
| Пункт Vj хранения Ui | V1 | V2 | V3 | V4 | Запасы |
| U1 | |||||
| U2 | |||||
| U3 | |||||
| Потребность |
Суммарные издержки на перевозку при таком плане равны
F= 400*7+200*10+500*11+700*15+100*10+400*9 =25400
или на 500 т-км меньше, чем в предыдущем плане.
Составленный план опять принимается за исходный, и вся вычислительная процедура повторяется снова. Затем проверяют план на оптимальность. Условие оптимальности выполняется и план оптимален.
По оптимальному плану с первого пункта хранения в четвертый магазин должны поступить 400т товара, со второго пункта во второй магазин -200т, а в третий - 500т, таким образом, все товары из пункта №2 будет вывезены. С третьего пункта хранения в первый магазин должен поступить -700т, в третий -100 т и в четвертый магазин - 400т товара.