Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Важным частным случаем общей задачи линейного программирования является задача об оптимальном маршруте перевозок грузов, которая обычно называется транспортной задачей.
Описание ситуации. Некоторый однородный продукт (груз) сосредоточен в m пунктах отправления (производства) в количествах а1, а2, …, am единиц соответственно. Его нужно доставить в n пунктов назначения (потребления), подавших заявки на этот продукт в количествах b1, b2, …, bn единиц соответственно. Предполагается, что сумма всех заявок равна сумме всех запасов, т.е. выполнено следующее условие:
=. (1)
Это условие гарантирует, что все заявки будут выполнены полностью и из каждого пункта отправления будет вывезен весь груз.
Известны тарифы (стоимости) cij () перевозки единицы груза из i го пункта отправления в j-й пункт назначения. Требуется найти план перевозок, который удовлетворяет заявки всех пунктов назначения и минимизирует суммарные затраты на перевозку.
Математическая модель. Для построения модели описанной выше ситуации, определим переменные xij — количество груза, перевозимого из i-го пункта отправления в j-й пункт назначения (). Ясно, что они должны принимать неотрицательные значения. Множество всех переменных (план перевозок) задается в виде матрицы X = (xij), имеющей размеры mхn.
Сама математическая модель задачи нахождения плана перевозок с наименьшими суммарными затратами выглядит так:
, (2)
, (3)
, (4)
. (5)
Формула (2) задает правило подсчета общих транспортных затрат Z, необходимых для реализации плана перевозок X = (xij). Таким образом, Z является целевой функцией, и решается задача ее минимизации на множестве планов перевозок, задаваемом ограничениями модели (3) – (5).
Условие (3) показывает, что общее количество груза, вывезенное из любого пункта отправления должно равняться величине запаса этого пункта. Соответственно условие (4) показывает, что общее количество груза, доставленное в любой пункт назначения должно равняться потребности этого пункта.
Задача (2) – (5) называется транспортной задачей, а равенства (3) – (4) называются условиями сбалансированности плана перевозок X = (xij).
План перевозок X = (xij) (), удовлетворяющий соотношениям (3) – (5), называется допустимым планом задачи (2) – (5).
Допустимый план X* = () называется оптимальным планом, если на нем общая величина затрат на перевозки Z(X*) минимальна.
Транспортная задача называется закрытой (сбалансированной), если выполнено условие (1). Это условие обеспечивает существование оптимального решения задачи (2) – (5).
Если условие (1) не выполнено, то транспортная задача называется открытой. В этом случае ее можно свести к закрытой задаче путем введения фиктивного пункта отправления или назначения.
Допустимый план транспортной задачи называется опорным планом, если столбцы матрицы условий, соответствующие его положительным компонентам, линейно независимы. Известно, что максимальное число линейно независимых столбцов матрицы условий транспортной задачи равно m + n – 1. Поэтому опорный план не может иметь более m + n – 1 положительных компонент. Если опорный план имеет ровно m + n – 1 положительных компонент, то он называется невырожденным планом, а если меньше, то вырожденным.
Метод решения транспортной задачи включает следующие пункты.
1. Построение начального опорного плана перевозок.
2. Проверка полученного плана на оптимальность. Если он не является оптимальным, то строится новый улучшенный план перевозок, на котором транспортные затраты меньше, или, по крайней мере, равны затратам предыдущего плана. Этот пункт повторяется до тех пор, пока не будет получено оптимальное решение. Рассмотрим применение этого метода на следующем примере.
Задача. В трех пунктах производства производится некоторый продукт в количествах а1 = 50, а2 = 30, а3 = 50 единиц соответственно. Этот продукт необходимо доставить в четыре пункта потребления, заявки которых составляют b1 = 25, b2 = 30, b3 = 35, b4 = 40 единиц соответственно.
Тарифы перевозок задаются матрицей:
.
Требуется найти план перевозок продукции, при котором суммарные транспортные расходы будут минимальными.
Решение
Прежде чем приступить к построению опорного плана, определим тип задачи. Для этого вычислим и . Так как суммарные запасы поставщиков равны суммарным потребностям потребителей, то это закрытая задача. Следовательно, она имеет опорный план.
Определим переменные xij — количество груза, перевозимого из i-го пункта отправления в j-й пункт назначения ().
Математическая модель
Математическая модель транспортной задачи имеет вид:
Z = 4x11 +2x12 +5x13 +7x14 + x21 +3x22 +3x23 +2x24 +5x31 +4x32 +2x33 + 6x34 → min.
x11 + x12 + x13 + x14 = 50
x21 + x22 + x23 + x24 = 30
x31 + x32 + x33 + x34 = 50
x11 + x21 + x31 = 25
x12 + x22 + x32 = 30
x13 + x23 + x33 = 35
x14 + x24 + x34 = 40
хij 0, i = , j =.
1. Нахождение опорного плана методом северо-западного угла
Построим для нахождения начального опорного плана таблицу.
Таблица 1
|
25 |
30 |
35 |
40 |
|
|
50 |
4 |
2 |
5 |
7 |
|
30 |
1 |
3 |
3 |
2 |
|
50 |
5 |
4 |
2 |
6 |
Нахождение начального опорного плана может осуществляться различными способами. Наиболее простым способом является метод северо-западного угла.
Определим величину элемента x11 = min {, } = min {50, 25} = 25. Занесем эту величину в первую клетку таблицы (1). Она показывает, что первый поставщик поставляет первому потребителю 25 единиц груза.
Так как потребность первого потребителя полностью удовлетворена, закрываем первый столбец и переходим в следующую клетку (1, 2) первой строки. Оставшийся запас первого поставщика равен 25 = 50 – 25 единицам, а потребность второго потребителя равна 30 единицам. Следовательно, от первого поставщика он может получить 25 единиц, т.е. x12 = min {25, 30} = 25.
Так как запас первого поставщика исчерпан, закроем первую строку и перейдем на следующую строку в клетку (2, 2), соответствующую второму поставщику. Его запас равен 40, а оставшаяся потребность второго потребителя равна 5. Следовательно, x22 = min {40, 5} = 5.
Теперь потребность первого потребителя полностью удовлетворена. Поэтому закрываем второй столбец и переходим в следующую клетку второй строки. Оставшийся запас второго поставщика равен 25, а потребность третьего потребителя равна 35. Следовательно, полагаем x23 = min {25, 35} = 25. Закрываем вторую строку и переходим на следующую строку. Третьему потребителю требуется еще 10 единиц. Их ему может поставить третий поставщик, т.е. x33 = min {50, 10} = 10.
Оставшиеся 40 единиц получает четвертый потребитель: x34 = min {40, 40} = 40. Нахождение опорного плана перевозок завершено (см. таблицу 2). Полученный план содержит 6 ненулевых элементов. Ранг матрицы задачи также равен 6 = 3+ 4–1. Поэтому найденный опорный план является невырожденным.
Таблица 2
|
25 |
30 |
35 |
40 |
|
|
50 |
4 |
2 |
5 |
7 |
|
25 |
25 |
|||
|
30 |
1 |
3 |
3 |
2 |
|
5 |
25 |
|||
|
50 |
5 |
4 |
2 |
6 |
|
10 |
40 |
Из самого способа его построения вытекает сбалансированность плана перевозок по поставщикам и потребителям. Однако во избежание ошибок рекомендуется проверить балансы путем суммирования поставок по строкам и столбцам.
Определим затраты на перевозки на построенном опорном плане (значение целевой функции).
Z = 25·4 + 25·2 + 5·3 + 25·3 + 10·2 + 40·6 = 500.
Возможна ситуация, когда на каком-то шаге одновременно исчерпывается запас у текущего поставщика и полностью удовлетворяется потребность текущего потребителя. Тогда нужно закрыть либо текущую строку, либо текущий столбец, а в следующую незанятую клетку записать 0 (нулевую поставку). В этом случае после окончания работы метода будет получен вырожденный опорный план.
Пример 1. Предположим, что в нашей задаче запасы поставщиков таковы: а1 = 50, а2 = 40 и а3 = 40, т.е. запас первого поставщика остался без изменения, запас второго поставщика уменьшился на 10 единиц, а запас третьего поставщика увеличился на 10 единиц. Тогда ясно, что задача остается закрытой, но теперь метод северо-западного угла дает вырожденный опорный план.
Действительно, при подсчете перевозки x23 = min {35, 35} = 35 оказывается, что оставшийся запас второго поставщика равен потребности третьего потребителя, составляющей 35 единиц. Поэтому после закрытия второй строки в клетку (3, 3) нужно записать нулевую перевозку, а в клетку (3, 4) — перевозку, равную 40 единицам. Полученный опорный план содержит всего пять ненулевых элементов, т.е. является вырожденным (см. таблицу 3).
Таблица 3
|
25 |
30 |
35 |
40 |
|
|
50 |
4 |
2 |
5 |
7 |
|
25 |
25 |
|||
|
40 |
1 |
3 |
3 |
2 |
|
5 |
35 |
|||
|
40 |
5 |
4 |
2 |
6 |
|
0 |
40 |
2. Нахождение оптимального плана методом потенциалов
При проверке на оптимальность допустимого плана используется следующий критерий.
Теорема. Допустимый план перевозок X* = () в транспортной задаче будет оптимальным тогда и только тогда, когда найдутся числа u1,…, um и v1, …,vn такие, что выполнены следующие соотношения:
vj – ui ≤ сij для всех i, j (6)
vj – ui = сij, если > 0. (7)
Числа ui называются потенциалами пунктов отправления, а vj — потенциалами пунктов назначения. Условия (6) и (7) означают, что разность потенциалов между двумя любыми пунктами отправления и назначения в оптимальном плане не должна превосходить затрат на перевозку единицы груза. Если же между пунктами осуществляется перевозка, то разность потенциалов между ними в точности равна затратам на перевозку единицы груза. Потенциалы могут интерпретироваться как цены продукции в этих пунктах.
С помощью этого критерия можно не только проверить на оптимальность любой план перевозок, но и указать способ улучшения неоптимального плана. Для этого обычно используется метод потенциалов.
На каждом шаге этого метода выполняются следующие действия:
2.1. Расчет потенциалов
Рассматриваемая транспортная задача содержит три пункта отправления и четыре пункта назначения. Им соответствуют потенциалы u1, u2 и u3 для пунктов отправления и потенциалы v1, v2, v3 и v4 для пунктов назначения.
Выпишем систему уравнений для вычисления их значений.
|
Занятая клетка |
Уравнение |
|
(1, 1) (1, 2) (2, 2) (2, 3) (3, 3) (3, 4) |
v1 – u1 = 4 v2 – u1 = 2 v2 – u2 = 3 v3 – u2 = 3 v3 – u3 = 2 v4 – u3 = 6 |
Эта система содержит 6 уравнений и 7 неизвестных. Полагая u1 = 0, найдем последовательно все потенциалы: v1 = 4, v2 = 2, u2 = -1, v3 = 2, u3 = 0, v4 = 6 и занесем найденные значения в таблицу.
Таблица 4
|
25 |
30 |
35 |
40 |
||
|
50 |
4 |
2 |
5 |
7 |
u1 = 0 |
|
25 |
25 |
||||
|
30 |
1 |
3 |
3 |
2 |
u2 = -1 |
|
5 |
25 |
||||
|
50 |
5 |
4 |
2 |
6 |
u3 = 0 |
|
10 |
40 |
||||
|
v1 = 4 |
v2 = 2 |
v3 = 2 |
v4 = 6 |
Z = 500 |
Расчет потенциалов можно проводить, не решая систему уравнений, а непосредственно в таблице. Так, если известен потенциал пункта отправления ui, то для вычисления потенциала пункта назначения vj, соответствующего занятой клетке (i, j), следует использовать уравнение
vj = ui + сij.
Таким способом можно определить потенциалы всех пунктов назначения, которым соответствуют занятые клетки в i-й строке.
Например, если известно, что u1 = 0, то можно найти значения первого и второго пунктов назначения, которым соответствуют занятые клетки в первой строке: v1 = u1 + c11 = 0 + 4 = 4, v2 = u1 + c12 = 0 + 2 = 2.
В том случае, когда известен потенциал пункта назначения vj, для вычисления потенциала пункта отправления ui, соответствующего занятой клетке (i, j), следует использовать уравнение
ui = vj – сij.
Например, если известно, что v3 = 2, то можно найти значения второго и третьего пунктов потребления, которым соответствуют занятые клетки в третьем столбце: u2 = v3 – c23 = 2 – 3 = -1, u3 = v3 – c33 = 2 – 2 = 0.
2.2. Проверка оптимальности
После того как потенциалы всех пунктов найдены, следует для всех свободных клеток вычислить разности :
Δ21 = 4 – (-1 + 1) = 4, Δ31 = 4 – (0 + 5) = -1,
Δ33 = 2 – (0 + 4) = -2, Δ13 = 2 – (0 + 5) = -3,
Δ14 = 6 – (0 + 7) = -1, Δ24 = 6 – (-1 + 2) = 5.
Среди вычисленных разностей имеются положительные. Значит, опорный план, построенный выше, не является оптимальным.
Замечание. По своему экономическому смыслу величина характеризует изменение в общих затратах на перевозки, которое произойдет, если будет осуществлена перевозка единицы груза из пункта отправления i в пункт назначения j. Поэтому, если > 0, то это означает, что существует свободное направление перевозки груза, экономящее затраты, т.е. текущий план перевозок не оптимален. Если же все , то это означает, что нет свободных направлений перевозок, экономящих затраты, т.е. текущий план перевозок оптимален.
Следующим этапом является построение нового опорного плана с меньшим значением целевой функции.
2.3. Построение нового опорного плана
Для построения «лучшего» опорного плана нужно найти свободную клетку, которой соответствует наибольшая положительная разность . Если таких клеток несколько, то берется любая из них.
Затем строится новый план перевозок, в котором эта клетка будет занятой, т.е. будет осуществлена перевозка из пункта i в пункт j. Так как число занятых клеток меняться не должно, то одна из ранее занятых клеток освобождается. Освобождаемая клетка и новые объемы перевозок в занятых клетках определяются с помощью цикла.
Циклом называется набор клеток таблицы, которые можно соединить замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90° и удовлетворяет таким условиям:
Одной из вершин цикла должна быть выбранная свободная клетка, а его остальные вершины должны находиться в занятых клетках. При построении любого цикла нужно следовать следующему правилу: выйдя из клетки в горизонтальном (вертикальном) направлении нужно остановиться на такой клетке, из которой затем можно двигаться по вертикали (горизонтали). Для этого в соответствующем столбце (строке) должно быть более одной занятой клетки. В построенном цикле, начиная с выбранной клетки, помечаются вершины: нечетные — знаком "+", а четные — знаком "–".
Знаком "+" помечаются те клетки, в которых объемы перевозок должны увеличиться. Знаком "–" помечаются клетки, в которых объемы перевозок должны уменьшиться, чтобы сохранился баланс перевозок. Среди клеток, помеченных знаком "–", определяется клетка, которой соответствует наименьшая величина перевозки xij. Обозначим эту величину символом θ.
Значения перевозок в остальных помеченных клетках пересчитываются по такому правилу: к объемам перевозок, содержащихся в «плюсовых» клетках, добавляется величина перевозки θ, а из объемов перевозок, содержащихся в «минусовых» клетках, вычитается величина перевозки θ. Остальные занятые клетки не изменяются. Если в результате этой операции только одна из «минусовых» клеток содержит нулевое значение, то она освобождается. Если же таких клеток несколько, то освобождается та из них, которая имеет максимальный тариф перевозок, а остальные остаются занятыми и содержат нули. В этом случае новый опорный план будет вырожденным.
На этом процедура построения нового опорного плана завершается, и он проверяется на оптимальность, т.е. происходит возврат к первому этапу. Значение целевой функции на новом плане уменьшается по сравнению со старым значением на величину, равную θ·.
Построим новый опорный план, улучшающий начальный опорный план. Ранее мы нашли разности для всех свободных клеток. Максимальная разность, равная 5, находится в клетке (2, 4). Следовательно, эту клетку нужно загрузить.
Таблица 5
|
25 |
30 |
35 |
40 |
||
|
50 |
4 |
2 |
5 |
7 |
u1 = 0 |
|
25 |
25 |
||||
|
30 |
1 |
3 |
3 – |
2 + |
u2 = -1 |
|
5 |
25 |
||||
|
50 |
5 |
4 |
2 + |
6 – |
u3 = 0 |
|
10 |
40 |
||||
|
v1 = 4 |
v2 = 2 |
v3 = 2 |
v4 = 6 |
Z = 500 |
Строим цикл, который позволит определить освобождаемую клетку. В данном случае он находится легко: его вершины образуют клетки: (2, 3), (2, 4), (3, 3) и (3, 4). Пометим знаком "+" клетки (2, 4) и (3, 3): в них объемы перевозок должны увеличиться. Клетки (2, 3) и (3, 4) пометим знаком "–": в них объемы перевозок уменьшаются.
Определим величину перевозки θ в клетке (2,4), которая загружается. Она равна минимальному значению из содержащихся в «минусовых» клетках (2, 3) и (3, 4), т.е. θ = min {25, 40} = 25. Это значение содержится в клетке (2, 3); следовательно, она освобождается. Новые значения в клетках, являющихся вершинами цикла, таковы:
,
,
.
Затраты на перевозки в новом плане равны 375. Они уменьшились по сравнению с затратами на перевозки в старом плане на Δ24·θ =5·25 = 125.
Проверим, является ли найденный опорный план оптимальным. Для этого снова вычислим потенциалы. Снова положим u1 = 0. Затем с учетом сделанного замечания, найдем значения остальных потенциалов: v1 = 4, v2 = 2, u2 = -1, v4 = 1, u3 = -5, v3 = 2 и занесем найденные значения в таблицу. Для всех свободных клеток вычислим разности :
Δ21 = 4 – (-1 + 1) = 4, Δ31 = 4 – (-5 + 5) = 4,
Δ32 = 2 – (-5 + 4) = 3, Δ13 = -3 – (0 + 5) = -8,
Δ23 = -3 – (-1 + 3) = -5, Δ14 = 1 – (0 + 7) = -6.
Снова имеются положительные разности. Значит, построенный план не является оптимальным. Максимальную разность, равную 4, дают две клетки (2, 1) и (3, 1). Возьмем в качестве загружаемой клетку (3, 1).
Таблица 6
|
25 |
30 |
35 |
40 |
||
|
50 |
4 – |
2 + |
5 |
7 |
u1 = 0 |
|
25 |
25 |
||||
|
30 |
1 |
3 – |
3 |
2 + |
u2 = -1 |
|
5 |
25 |
||||
|
50 |
5 + |
4 |
2 |
6 – |
u3 = -5 |
|
35 |
15 |
||||
|
v1 = 4 |
v2 = 2 |
v3 = -3 |
v4 = 1 |
Z = 375 |
Построим цикл с вершиной в этой клетке. На этот раз ситуация существенно сложнее, чем в предыдущем случае. Следуя описанному выше правилу построения цикла, мы должны, выйдя из клетки (3, 1) переместиться в клетку (1, 1); далее — в клетки (1, 2), (2, 2), (2, 4), (3, 4) и вернуться в начальную клетку (см. табл. 6).
Итак, вершинами цикла будут клетки (3, 1), (1, 1), (1, 2), (2, 2), (2, 4) и (3, 4). В этом цикле «минусовыми» являются клетки (1, 1), (2, 2) и (3, 4). Найдем минимальное значение в этих клетках: θ = min{25, 5, 15} = 5. Оно содержится в клетке (2, 2). Следовательно, она освобождается. Новые значения в остальных клетках, являющихся вершинами цикла, таковы:
,
,
,
,
.
Новое значение целевой функции равно 355. Проверим построенный план на оптимальность.
Таблица 7
|
25 |
30 |
35 |
40 |
||
|
50 |
4 |
2 |
5 |
7 |
u1 = 0 |
|
20 |
30 |
||||
|
30 |
1 |
3 |
3 |
2 |
u2 = 3 |
|
30 |
|||||
|
50 |
5 |
4 |
2 |
6 |
u3 = -1 |
|
5 |
35 |
10 |
|||
|
v1 = 4 |
v2 = 2 |
v3 = 1 |
v4 =5 |
Z = 355 |
Для этого вычислим потенциалы. Положим u1 = 0. Затем найдем значения остальных потенциалов: v1 = 4, v2 = 2, u3 = -1, v3 = 1, v4 = 5, u2 = 3 и занесем найденные значения в таблицу. Для всех свободных клеток вычислим разности :
Δ21 = 4 – (3 + 1) = 0, Δ22 = 2 – (3 + 3) = -4,
Δ23 = 1 – (3 + 3) = -5, Δ32 = 2 – (1 + 4) = -3,
Δ13 = 1 – (0 + 5) = -4, Δ14 = 5 – (0 + 7) = -2.
Все разности неположительные. Значит, найденный план перевозок оптимален (см. табл. 7). Осуществляются такие перевозки:
Общие затраты на перевозки в оптимальном плане равны 355