Транспортные задачи(ТЗ)- частный случай задачи линейного программирования.
В ТЗ существуют поставщики и потребители грузов. У каждого поставщика имеется определенное количество груза - мощность поставщика, а каждому потребителю нужно определенное количество груза - спрос потребителя. Известны затраты на перевозку единицы груза. Нужно составить такой план перевозок, при котором: 1) Суммарные затраты на перевозку груза будут минимальными;2) По возможности будут задействованы все мощности поставщиков; 3)По возможности будет удален весь спрос потребителей.
Закрытая модель ТЗ(сбалансированная модель ТЗ)- модель, в которой суммарная мощность поставщиков равна суммарному спросу потребителей.
Открытая модель ТЗ(не сбалансированная модель ТЗ) – модель, в которой суммарная мощность поставщиков не равна суммарному спросу потребителей.
В процессе решения открытая модель всегда сводится к закрытой. Поэтому сначала рассмотрим закрытую модель.
Алгоритм решения закрытой модели/ТЗ:
1) Составляется специальная таблица поставщиков и потребителей с указанием их мощностей и спросов;
2) Находим первоначальный план поставок:
-метод северо-западного угла;
-метод минимальной стоимости;
-метод потенциалов;
3) Оптимизируем план распределительным методом;
Задача2.1
Требуется построить экономико-математическую модель следующей задачи. Имеется 3 поставщика и 4 потребителя. Мощности поставщиков и спрос потребителей, а также затраты на перевозку единицы груза для каждой пары поставщик- потребитель сведены в таблицу поставок:
Таблица 2.1
Поставщик | Мощность поставщика | Потребители и их спрос | |||
X11 | X12 | X13 | X14 | ||
X21 | X22 | X23 | X24 | ||
X31 | X32 | X33 | X34 |
i-номер строки;
j-номер столбца;
ij-клетка;
В клетке отмечены коэффициенты затрат-затраты от i-го поставщика к j-му потребителю.
Решение:
Построим экономико-математическую модель. Искомый объем i-го поставщика j-ому потребителю есть Xij. Назовем поставкой клетки(ij).
Запишем уравнения баланса для каждой строки таблицы поставок:
X11 + X12 + X13 + X14 =60;
X21 + X22 + X23 + X24 =120;
X31 + X32 + X33 + X34 =100;
Запишем уравнения баланса для каждого столбца таблицы поставок:
X11 + X21 + X31 =20;
X12 + X22 + X32 =110;
X13 + X23 + X33 =40;
X14 + X24 + X34 =110;
Суммарные затраты F на перевозку выражается через коэффициенты затрат (в углах ячеек):
F= X11 + 2X12 + 3X14 +X21 +6 X22 + 5X23 +2X24 + 6X31 +3X32+7X33 + 4X34 ;
Особенности экономико –математической модели:
Система ограничений – система уравнений в канонической форме. Коэффициенты при переменных равны 0 или 1. Каждая из переменных входит в систему ограничений два раза.
Обозначения:
Cij – коэффициенты затрат.
Mi – мощность поставщиков.
Nj –спрос потребителей.
i – 1,2,3…,m;
j – 1,2,3…,n;
m – число поставщиков.
n – число потребителей.
n
Тогда ∑ Xij= Mi i=1,2,…,m(2.1)
J=1
m
Тогда ∑ Xij= Nj j=1,2,…,n(2.2)
i=1
Целевая функция в общем виде;
n m
F= ∑ ∑ Cij xij –> min; (2.3)
J=1 i=1
n
∑ xij= Nj ;
J=1 - система ограничений.
n
∑ xij= Mi;
i=1
При данных ограничениях данная целевая функция должна стремиться к минимуму.
Математическая формулировка:
* * * *
На множестве решений системы ограничений (2.1, 2.2) найти такое решение, X(x11, x12,…,xmn) , при котором значение целевой функции F будет минимально. Являясь задачей линейного программирования ТЗ может быть решена симплексным методом. Однако специфичная форма системы ограничений, позволяет упростить этот метод. Существуют разные методы нахождения оптимального решения;
-метод северно-западного угла;
-метод минимальной стоимости;
-метод потенциалов;