Применение методов линейного программирования для оптимизации стоимости перевозок
Применение методов линейного программирования для оптимизации стоимости перевозок
(3. )
(3. )
(3. )
Тогда при условии
(3. )
мы имеем закрытую модель, а при условии
– открытую модель транспортной задачи.
Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики удовлетворены и при этом на некоторых базах остаются излишки груза
, либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены
.
Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный пункт”, например – склад.
План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок (Таблица 3. ):
Таблица 3. - План перевозок с указанием запасов и потребностей
Пункты
Отправления
Пункты назначения
Запасы
…
…
…
…
…
…
…
…
…
…
Потребности
…
или
Условие
или
означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Переменное
означает количество груза, перевозимого с базы
потребителю
: совокупность этих величин образует матрицу (матрицу перевозок).
Очевидно, переменные
должны удовлетворять условиям:
(3. )
Система (3. ) содержит
уравнений с
неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы (3. ) могут быть разделены на две группы: первая группа из т первых уравнений (“горизонтальные” уравнения) и вторая группа из п остальных уравнений (“вертикальные” уравнения). В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок). Таким образом, каждая неизвестная встречается в системе (3. ) дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях.
Такая структура системы (3. ) позволяет легко установить ее ранг. Действительно, покажем, что совокупность неизвестных, образующих первую строку и первый столбец матрицы перевозок, можно принять в качестве базиса. При таком выборе базиса, по крайней мере, один из двух их индексов равен единице, а, следовательно, свободные неизвестные определяются условием
,
.Перепишем систему (3. ) в виде
(3. )
где символы
и
означают суммирование по соответствующему индексу. Так, например,
При этом легко заметить, что под символами такого суммирования объединяются только свободные неизвестные (здесь
,
).
В рассматриваемой нами системе только два уравнения, а именно первое горизонтальное и первое вертикальное, содержат более одного неизвестного из числа выбранных нами для построения базиса. Исключив из первого горизонтального уравнения базисные неизвестные
с помощью вертикальных уравнений, мы получаем уравнение
или короче
(3. )
где символ
означает сумму всех свободных неизвестных. Аналогично, исключив из первого вертикального уравнения базисные неизвестные
с помощью горизонтальных уравнений, мы получаем уравнение
(3. )
Так как для закрытой модели транспортной задачи
, то полученные нами уравнения (3. ) и (3. ) одинаковы и, исключив из одного из них неизвестное
, мы получим уравнение-тождество 0=0, которое из системы вычеркивается.
Итак, преобразование системы (3. ) свелось к замене двух уравнений (первого горизонтального и первого вертикального) уравнением (3. ). Остальные уравнения остаются неизменными. Система приняла вид
(3. )
В системе (3. ) выделен указанный выше базис: базисные неизвестные из первых т уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного
[она входит в первое уравнение системы (3. )]. В системе (3. ) имеется
уравнений, выделенный базис содержит
неизвестных, а, следовательно, и ранг системы (3. ) .
Для решения транспортной задачи необходимо кроме запасов и потребностей знать также и тарифы
, т. е. стоимость перевозки единицы груза с базы
потребителю
.
Совокупность тарифов
также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу 3.:
Таблица 3. - Совокупность тарифов данные о запасах и потребностях
Пункты
Отправления
Пункты назначения
Запасы
…
…
…
…
…
…
…
…
…
…
Потребности
…
или
Сумма всех затрат, т. е. стоимость реализации данного плана перевозок, является линейной функцией переменных
:
(3. )
Требуется в области допустимых решений системы уравнений (3. ) и (3.) найти решение, минимизирующее линейную функцию (3. ).
Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен
то среди всех
неизвестных
выделяется
базисных неизвестных, а остальные
·
неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем
заполненных и
·
пустых клеток.
На предприятии ОАО «Электросигнал» имеется 4 транзитных склада Аi
, на которых хранятся сборочные узлы и 5 цехов Bj
, занимающихся сборкой готовой продукции. Ниже, в таблице 3., приведены данные по количеству сборочных узлов на каждом складе, запросы цехов и стоимость перевозки одного агрегата из Аi
в Bj
. Необходимо составить такой план перевозок, при котором запросы цехов будут удовлетворены при минимальной суммарной стоимости перевозок.
Таблица 3. – Исходные данные по количеству сборочных узлов и стоимость перевозки
Цеха
Склад
B1
(b1
=40)
B2
(b2
=50)
B3
(b3
=15)
B4
(b4
=75)
B5
(b5
=40)
А1
(а1
=50)
1,0
2,0
3,0
2,5
3,5
А2
(а2
=20)
0,4
3,0
1,0
2,0
3,0
А3
(а3
=75)
0,7
1,0
1,0
0,8
1,5
А4
(а4
=80)
1,2
2,0
2,0
1,5
2,5
В данном случае Σai
=225 >Σbj
=220 => имеем дело с открытой моделью транспортной задачи. Сведем ее к закрытой введением фиктивного цеха B6
с потребностью b5
=225-220=5 и стоимостью перевозок сi6
=0.Имеем таблицу 3. :
Таблица 3. -
Цеха
Склад
B1
(b1
=40)
B2
(b2
=50)
B3
(b3
=15)
B4
(b4
=75)
B5
(b5
=40)
B6
(b6
=5)
А1
(а1
=50)
1,0
2,0
3,0
2,5
3,5
0
А2
(а2
=20)
0,4
3,0
1,0
2,0
3,0
0
А3
(а3
=75)
0,7
1,0
1,0
0,8
1,5
0
А4
(а4
=80)
1,2
2,0
2,0
1,5
2,5
0
Математическая модель: обозначим xij
– количество товара, перевозимого из Аi
в Bj
. Тогда
В верхнем левом углу здесь и далее записываем значение ui
+vj
-cij
. Имеем: u1
+v1
--c11
=0,7>0, u1
+v6
-c16
=0,3>0, u3
+v3
-c33
=0,3>0, u3
+v5
-c35
=0,3>0,
u4
+v1
-c41
=0,2>0. => По критерию оптимальности, первый план не оптимален. Далее max(0,7;0,3;0,3;0,3;0,2)=0,7. => Поместим перевозку в клетку А1
В1
,сместив 20=min(20,50) по циклу, указанному в таблице штрихом. Получим новую таблицу. Найдем потенциалы: u1
+v1
=1,u1
+v2
=2,u2
+v1
=0,4,u3
+v2
=1, u3
+v4
=0,8, u4
+v3
=2, u4
+v4
=1,5, u4
+v5
=2,5 , u4
+v6
=0. Положим u1
=0,тогда v1
=1,u2
=-0,6,v2
=2,v4
=1,8, u3
=-1, u4
=-0,3,v3
=2,3,v5
=2,8,v6
=0,3. Составим таблицу 3. :