|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Метод потенциаловПусть – некоторый допустимый план поставок. Назовем системой потенциалов плана такой набор чисел , ,…, и , ,…, , что выполнены соотношения Критерий оптимальности: план имеет наименьшую стоимость, если существует такая система потенциалов, что для всех индексов , для которых , выполнено соотношение Как определить систему потенциалов? План назовем невырожденным, если число занятых клеток (для которых ) равно . В этом случае полагаем и получаем систему из уравнения для определения неизвестного. Можно показать, что система имеет единственное решение. Если число занятых клеток окажется меньше , дополним план до невырожденного, назначив фиктивную, нулевую, поставку в необходимое количество пустых клеток (с наименьшей стоимостью). Пример. Пусть имеется три поставщика с ресурсами 1000, 1500, 1200 и два потребителя с потребностями 2300, 1400. Стоимость поставки единицы груза от -го поставщика к -му потребителю задана транспортной таблицей:
Поскольку 1000+1500+1200=2300+1400, задача закрытая. Определим первоначальное допустимое распределение груза методом северо-западного угла. Число занятых клеток равно 4=3+2-1, план невырожденный. Уравнения для потенциалов: Отсюда , , , , .
Выражения для незанятых клеток пишем в левом нижнем углу. Поскольку , план поставок неоптимальный.
Улучшение опорного плана. Если для первоначального плана не выполнен критерий оптимальности, план можно улучшить, перераспределив поставки по следующему правилу. Выберем свободную клетку с максимальным значением . Пусть это клетка с индексом . Соединим ее замкнутой ломаной с занятыми клетками, так чтобы вершины ломаной находились в занятых клетках, а стороны были параллельны сторонам таблицы. Можно показать, что для любого невырожденного плана поставок такая ломаная определена единственным образом. Припишем знаки + или - вершинам этой ломаной по следующему правилу: вершине с индексом знак +, а любым двум соседним вершинам разные знаки. Найдем минимальную поставку среди вершин со знаком -. Теперь именно это количество груза убавим у вершин со знаком - и прибавим к вершинам со знаком +. Перераспределение поставок закончено.
В результате получаем
План оптимальный.
Задача 8.1. В городе имеется три хлебозавода, которые выпускают одинаковую продукцию и развозят ее по 5 магазинам. Стоимость доставки пропорциональна расстоянию от завода до магазина (см. таблицу).
Мощности хлебозаводов составляют 40, 100 и 140 тонн продукции в сутки. Суточные потребности магазинов равны соответственно 20, 50, 60, 40, 110 тонн. Определите план поставок, минимизирующий суммарные транспортные расходы магазинов.
Решение. Запишем данные задачи в виде транспортной таблицы.
Определим первоначальное распределение поставок методом северо-западного угла.
Число занятых клеток равно 7, при этом , то есть план невырожденный. Рассчитаем систему потенциалов. Полагаем . В первой строке две занятые клетки, поэтому , , откуда , . В первом столбце других занятых клеток нет. Во втором столбце имеется поставка во второй строке, поэтому Û . Теперь мы знаем потенциал второй строки и можем найти потенциалы третьего и четвертого столбца. , . Получаем: , . В четвертом столбце занята поставкой клетка третьей строки, поэтому Û . Остается найти потенциал последнего, пятого, столбца. Û . Запишем полученные результаты в виде таблицы.
Найдем величины для всех незанятых поставками клеток.
Имеется единственная клетка, для которой величина положительна . Поэтому план не оптимален. Проведем перераспределение поставок. Построим прямоугольник перераспределения. Он проходит через четыре клетки. Расставив знаки вершин прямоугольника, найдем минимальную поставку среди отрицательных вершин. В данном случае она равна . После перераспределения новый план поставок имеет вид. План оказался вырожденным, поэтому одну из двух исчезнувших поставок в прямоугольнике перераспределения мы делаем фиктивной (то есть пишем в клетку 0 и считаем ее фиктивно занятой). После этого пересчитываем систему потенциалов , , и находим величины для незанятых клеток.
Теперь все величины отрицательны и план поставок оптимален. Мы можем определить его стоимость по формуле : .
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.) |