КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Экономический анализ транспортных задачОпределение оптимального варианта перевозки грузов с учетом трансформации спроса и предложений Открытая транспортная задача Вырожденность в транспортных задачах Альтернативный оптимум в транспортных задачах
Признаком наличия альтернативного оптимума в транспортной задаче является равенство нулю хотя бы одной из оценок свободных переменных в оптимальном решении (X опт1 ). Сделав перераспределение грузов относительно клетки, имеющей Δ ij = 0, получим новое оптимальное решение (Х опт2), при этом значение целевой функции (транспортных расходов) не изменится. Если одна оценка свободных переменных равна нулю, то оптимальное решение находится в виде
где 0 ≤ t ≤ 1. Рассмотрим конкретную задачу, имеющую альтернативный оптимум. Пример 1. На трех складах имеется мука в количестве 60, 130 и 90 т, которая должна быть в течение месяца доставлена четырем хлебозаводам в количестве: 30, 80, 60, 110 т соответственно. Составить оптимальный план перевозок, имеющий минимальные транспортные расходы, если стоимость доставки 1 т муки на хлебозаводы задана матрицей
Решение. Составим распределительную таблицу в виде табл. 23.6.
По методу минимального тарифа найдем исходное решение. Определим потенциалы строк и столбцов. Найдем оценки свободных клеток:
Так как Δ12 = 4 > 0, то перераспределим грузы относительно клетки (1,2):
Занесем полученное перераспределение грузов в распределительную таблицу и вычислим потенциалы занятых и оценки свободных клеток (табл. 23.7).
Получим
Так как Δ33 = 0, то задача имеет альтернативный оптимум и одно из решений равно
Стоимость транспортных расходов составляет: L(X опт1 ) = 1550 усл. ед. Произведем перераспределение грузов относительно клетки (3,3):
Занесем в распределительную таблицу полученное перераспределение грузов, вычислим потенциалы занятых и оценки свободных клеток (табл. 23.8):
Так как Δ14 = 0, получили еще одно решение:
Стоимость транспортных расходов составит L(Х опт2 ) = 1550 усл. ед. Данная задача имеет два оптимальных решения Х опт1 и X опт2, общее решение находится по формуле
где 0 ≤ t ≤ 1. Найдем элементы матрицы общего решения:
Итак,
Стоимость транспортных расходов составляет 1550 усл. ед.
При решении транспортной задачи может оказаться, что число занятых клеток меньше, чем m + п - 1. В этом случае задача имеет вырожденное решение. Для возможного его исключения целесообразно поменять местами поставщиков и потребителей или ввести в свободную клетку с наименьшим тарифом нулевую поставку. Нуль помещают в такую клетку, чтобы в каждой строке и каждом столбце было не менее одной занятой клетки. Рассмотрим вырожденность в транспортной задаче на примере. Пример 2. Фирма осуществляет поставку бутылок на три завода, занимающиеся производством прохладительных напитков. Она имеет три склада, причем на складе 1 находится 6000 бутылок, на складе 2 — 3 000 бутылок и на складе 3 — 4 000 бутылок. Первому заводу требуется 4000 бутылок, второму заводу — 5 000 бутылок, третьему заводу — 1000 бутылок. Матрицей
задана стоимость перевозки одной бутылки от каждого склада к каждому заводу. Как следует организовать доставку бутылок на заводы, чтобы стоимость перевозки была минимальной? Решение. Запишем исходные данные в распределительную таблицу (табл. 23.9), найдем исходное опорное решение по методу минимального тарифа. Число заполненных клеток равно 5, т + п - 1 = 6, следовательно, задача является вырожденной. Для исключения вырожденности необходимо в какую-то клетку ввести нулевую поставку. Такая клетка становится условно занятой, ее целесообразно определить при вычислении потенциалов занятых клеток, она должна иметь наименьший тариф по сравнению с другими клетками, которые могут быть условно занятыми. Так, для нахождения потенциала и 3 поместим нулевую поставку в клетку (3,2), после чего представляется возможным вычислить остальные потенциалы.
Оценки свободных клеток следующие:
Все оценки отрицательные, получили оптимальное решение:
Таким образом, со склада 1 целесообразно поставить 3000 бутылок второму и четвертому заводам, со склада 2 — 2000 бутылок второму заводу и 1000 бутылок третьему, со склада 3 — 4000 бутылок первому заводу, при этом стоимость транспортных расходов будет минимальной и составит 28 000 усл. ед.
При открытой транспортной задаче сумма запасов не совпадает с суммой потребностей, т.е.
При этом: а) если
то объем запасов превышает объем потребления, все потребители будут удовлетворены полностью и часть запасов останется невывезенной. Для решения задачи вводят фиктивного (n + 1)-потребителя, потребности которого
Модель такой задачи будет иметь вид
при ограничениях:
б) если
то объем потребления превышает объем запасов, часть потребностей останется неудовлетворенной. Для решения задачи вводим фиктивного (m + 1)- поставщика :
Модель такой задачи имеет вид
при ограничениях:
При введении фиктивного поставщика или потребителя открытая транспортная задача становится закрытой и решается по ранее рассмотренному алгоритму для закрытых транспортных задач, причем тарифы, соответствующие фиктивному поставщику или потребителю, больше или равны наибольшему из всех транспортных тарифов, иногда их считают равными нулю. В целевой функции фиктивный поставщик или потребитель не учитывается.
Рассмотрим следующую задачу. Составить оптимальный план перевозки грузов от трех поставщиков с грузами 240, 40, 110 т к четырем потребителям с запросами 90, 190, 40 и 130 т. Стоимости перевозок единицы груза от каждого поставщика к каждому потребителю даны матрицей
Решение. Запасы грузов у поставщиков: = 390 т. Запросы потребителей: = 450 т; так как < то вводим фиктивного поставщика с грузом а 4ф = 450 - 390 = 60 т. Тариф фиктивного поставщика 4ф примем равным 20 усл. ед. Так как т + п – 1 = 7, а число занятых клеток равно 6, то для исключения вырожденности введем в клетку (2, 2) нулевую поставку. Оценки свободных клеток:
(табл. 23.10). Оценка свободной клетки (1,3) больше нуля, перераспределим грузы:
Запишем полученное перераспределение грузов в табл. 23.11. Имеем
Получили оптимальное решение:
Стоимость транспортных расходов — 3120 усл. ед.
Проведем экономический анализ задачи на конкретном примере. Пример 3. Три торговых склада могут поставлять некоторое изделие в количестве 9, 4 и 8 т. Величины спроса трех магазинов розничной торговли на это изделие равны 3, 5 и 6 т. Какова минимальная стоимость транспортировки от поставщиков к потребителям? Провести анализ решения при условии, что единичные издержки транспортировки в усл. ед. даны в матрице
Решение. Запасы складов: = 21 т, потребности магазинов: = 14 т, имеем открытую задачу. Введем фиктивный магазин со спросом b 4ф = 7 т и тарифом 20 усл. ед. (табл. 23.12). Оценки свободных клеток:
Оценки Δ32 = Δ34 = 0, задача имеет альтернативный оптимум, и одно из решений имеет вид
Минимальная стоимость транспортных расходов
Итоговое распределение перевозок, а также значения оценок свободных клеток, которые называют теневыми ценами, можно использовать при проведении экономического анализа. Теневая цена показывает, на сколько увеличится общая стоимость транспортных расходов, если в пустую клетку поместить одно изделие. Например, если придется осуществить перевозку одного изделия с торгового склада 2 в розничный магазин 3, то увеличение стоимости составит |Δ23| = | - 13| = 13 усл. ед., что больше, чем тариф груза клетки (2,3), равный 8 усл. ед. Дополнительное увеличение стоимости транспортных расходов появляется в связи с перераспределением перевозок. Составим цикл распределения перевозок с помещением груза в пустую клетку (2, 3):
В клетку (2, 3) помещаем груз 4 т, в (1, 3) вместо 1т — 5т, в (2, 2) вместо 4т — пустая клетка. Изменение расходов составит 4 ∙ 20 – 4 ∙ 10 + 8 ∙ 4 – 4 ∙ 5 = 72 усл. ед. или на одно изделие 72: 4 = 13 усл. ед. Если теневая цена клетки равна нулю (Δ32 = 0), то задача имеет альтернативный оптимум. Перераспределим грузы относительно клетки (3, 2):
Еще одно оптимальное решение задачи имеет вид
Минимальная стоимость транспортных расходов
Аналогичный анализ можно провести и по остальным свободным клеткам. Теневые цены свободных клеток можно использовать в качестве индикаторов изменений стоимости транспортировки одного изделия или тарифа. Например, теневая цена пустой клетки (3, 3) равна |Δ33| = | - 2| = 2, а фактическая цена транспортировки одного изделия — 7 усл. ед. Следовательно, для того чтобы использование данной клетки в распределении перевозок привело к снижению общих транспортных расходов, нужно, чтобы тариф этой клетки был не более 7 – 2 = 5 усл. ед. Проведем стоимостный анализ изменений в занятых клетках. При снижении тарифа увеличение числа изделий в данной клетке выгодно. Если же тарифы занятых клеток возрастают, то при достижении ими определенного значения использование этой клетки является нежелательным и необходимо произвести перераспределение грузов. В качестве примера определим допустимые изменения тарифа занятой клетки (1, 3). Тариф клетки равен 5 усл. ед. за одно изделие. Уменьшение этой величины не повлияет на объем перевозок, так как указанное количество изделий в клетке удовлетворяет всю потребность магазина 3. Если тариф клетки (3,1) становится больше 5 усл. ед., то при составлении циклов будет задействована пустая клетка (2, 3) с |Δ23| = 13 или (3, 3) с |Δ33| = 2. В обоих циклах клетка (1, 3) будет иметь знак "—" и любое увеличение тарифа повлечет снижение теневой цены пустой клетки (2, 3) или (3, 3). Изменение объема перевозок будет иметь место в случае, если тариф клетки (1,3) возрастет более чем на 2 усл. ед. и превысит 7 усл. ед. При этом теневая цена клетки (3,3) станет положительной и окажется невыгодным использование клетки (1.3). Таким образом, для получения оптимального распределения перевозок тариф клетки (1,3) должен изменяться в диапазоне от 0 до 7 усл. ед. Внутри указанного промежутка происходит лишь изменение общей стоимости транспортных расходов, а распределение перевозок не меняется.
Дата добавления: 2014-10-15; Просмотров: 1085; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |