Транспортная задача линейного программирования
Задание: Составить математическую модель транспортной задачи по исходным данным: ; ; Если полученная модель окажется открытой, то свести ее к замкнутой и найти оптимальное решение транспортной задачи методом потенциалов. Постановка задачи: Однородный продукт, сосредоточенный в трехпунктах производства (хранения) в количествах 35, 55 и 80 единиц, необходимо распределить между n -четырьмя пунктами потребления, которым необходимо соответственно 30, 55, 44, 42 единиц. Стоимость перевозки единицы продукта из i -го пункта отправления ( ) в j-ый пункт назначения ( ) равна с ij и известна для всех маршрутов. Она задана матрицей С:
Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными. Обозначим через хij количество груза, планируемого к перевозке от i-го поставщика ( ) j-му ( ) потребителю. При наличии баланса производства и потребления (1) Общий объем производства åа i = 80+50+35= 170 меньше , требуется всем потребителям åbi = 30+55+44+42=171. Таким образом, имеет место дисбаланс между запасами и запросами. В математическом плане это означает, что наша задача – это задача открытого типа. Для устранения дисбаланса (приведения задачи к закрытому типу), введем фиктивный пункт производства с объемом производства, равным указанному дисбалансу т.е. единице, причем тарифы на перевозку из этого пункта условимся считать равными нулю ( ). Четырьмя условиями того, что из каждого пункта хранения вывозится весь продукт, являются: Четырьмя условиями того, что каждому потребителю доставляется затребованное им количество продукта являются:
В качестве показателя эффективности выступает суммарная стоимость перевозок (L): ; В качестве критерия эффективности правомерно считать принцип минимизации результата т.к. на лицо стремление уменьшить стоимость перевозок. Приходим к следующей математической постановке задачи: найти план перевозок x , компоненты которого обеспечивают минимизацию линейной формы L , при следующих ограничениях на эти компоненты:
(1)
Решение: Сформулированная задача является задачей линейного программирования, которая обладает двумя особенностями, а именно 1) коэффициент при каждой из неизвестных в системе ограничений (1) равен 1; 2) одно из уравнений системы ограничений линейно зависит от других, в силу чего число базисных неизвестных в системе равно . Эти особенности позволяют решить задачу специально разработанными методами: методом северо-западного угла или методом наименьших затрат. Мы решим ее двумя способами.
Метод наименьших затрат
Обозначим через m ) вектор симплексных множителей или потенциалов. Тогда . Один из потенциалов можно выбрать произвольно, так как в системе (1) одно уравнение линейно зависит от остальных. Положим, что р1 = 0. Остальные потенциалы находим из условия, что для базисных клеток . В данном случае получаем: D 11 = 0, p 1 + q 1 - c 11 = 0, q 1 = 2 D 14 = 0, p 1 + q 4 - c 14 = 0, q 4 = 4 D 34 = 0, p3 + q4 – c34 = 0, p3 = -1 D 33 = 0, p3 + q3 – c33 = 0, q3= 4 D 21 = 0, p2 + q1 – c21 = 0, p2 = 2 D 22 = 0, p 2 + q 2 – c 22 = 0, q 2 = -1 D 44 = 0, p 4 + q 4 – c 44 = 0, p 4 =-4 Теперь по формуле вычисляем оценки всех свободных клеток: D 12 = p1 + q2 – c12 = 0-1-3=-4 D 13 = p1 + q3 – c13 = 0+4-6 =-2 D 23 = p2 + q3 – c23 = 2+4-5 = 1 - max D 24 = p2 + q4 – c24 = 2+4-7 = -1 D 31 = p3 + q1 - c31 = -1+2-5 = -4 D 32 = p3 + q2 – c32 = -1-1-2 = -4 D 41 = p4 + q1 – c41 = -4+2-0 = -2 D 42 = p4 + q2 – c42 = -4-1-0 = -5 D 43 = p 4 + q 3 – c 43 = -4-4-0 = -8 Находим наибольшую положительную оценку max ( ) = 1 = D 23 Для найденной свободной клетки 23 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 23-21-11-14-34-33-23:
min =0
D 14 = 0, p1 + q 4 - c1 4 = 0, q 4 = 4 D 34 = 0, p3 + q4 – c34 = 0, p3 = -1 D 33 = 0, p3 + q3 – c33 = 0, q3= 4 D 2 3 = 0, p2 + q 3 – c2 3 = 0, p2 = 1 D 22 = 0, p2 + q2 – c22 = 0, q2 = 0 D 44 = 0, p4 + q4 – c44 = 0, p4=-4
Теперь по формуле вычисляем оценки всех свободных клеток: D 12 = p1 + q2 – c12 = 0-3=-3 D 13 = p1 + q3 – c13 = 0+4-6 =-2 D 21 = p2 + q3 – c23 = 1+2-4 = -1 D 24 = p2 + q4 – c24 = 1+4-7=-2 D 31 = p3 + q1 - c31 = -1+2-5 = -4 D 32 = p3 + q2 – c32 = -1+0-2=-3 D 41 = p4 + q1 – c41 = -4+2=-2 D 42 = p4 + q2 – c42 = -4+0=-4 D 43 = p 4 + q 3 – c 43 = -4+4-0 = 0 Итак, , при Таким образом, пришли к оптимальному решению
Общая стоимость перевозок: денежных единиц. Для проверки полученного результата теперь решим задачу методом северо-западного угла. Метод Северо-западного угла
денежных единиц
Находим наибольшую положительную оценку max ( ) = 7 = D 31
Для найденной свободной клетки 31 строим цикл пересчета:
min =3
денежных единиц
Находим наибольшую положительную оценку max ( ) = 7 = D 11 Для найденной свободной клетки 11 строим цикл пересчета:
min =30
денежных единиц
Находим наибольшую положительную оценку max ( ) = 3= D 14 Для найденной свободной клетки 14 строим цикл пересчета:
min =5
Таким образом, пришли к оптимальному решению
денежных единиц.
Популярное: Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Почему стероиды повышают давление?: Основных причин три... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (173)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |