|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Начальное распределение перевозок, полученное методом Вогеля
После третьего распределения продукта оставшееся его количество распределяется по клеткам транспортной таблицы однозначно. Оставшийся продукт помещается в клетки (Р, В), (Р, С) и (Р, фиктивный). U1+V2=20 Положим: 1) U1=0 V2=20 U1+V3=5 2) V3=5 U1+V4=0 3) V4=0 U2+V2=10 4) U2= -10 U3+V1=1 6) V1=1 U3+V4=0 5) U3=0 Проверка по пустым клеткам: S11=10-(U1+V1) =10-(0+1) =9 S21=2-(U2+V1) = 2-(-10+1) =2+9=11 S23=8-(U2+V3) =8-(-10+5) =8+5=13 S24=0-(U2+V4) =0-(-10+0) =10 S32=20-(U3+V2) =20-(0+20) =0 S33=7-(U3+V3) =7-(0+5) =2 Стоимость = (1∙ 20 + 6 ∙ 5 + 2 ∙ 0 + 4 ∙ 10 + 3 ∙ 1 + 5 ∙ 0) = 93 руб. Ответ: минимальная стоимость транспортировки составляет 93 рубля. Как и в предыдущем случае, мы еще не знаем, является ли данное решение оптимальным, однако, можно с уверенностью утверждать, что план перевозок, полученный методом Вогеля, более дешевый по сравнению с планом, стоимость которого составила 101 рубль, полученная методом минимальной стоимости. Проверка на оптимальность Чтобы осуществить проверку на оптимальность, необходимо определить является ли начальное распределение перевозок базисным, то есть, находится ли полученное решение в крайней точке допустимого множества. Если распределение перевозок является базисным, каждому ограничению должна соответствовать одна базисная переменная. Задача для m торговых складов и n розничных магазинов (включая фиктивный) содержит (m+n-1) независимых ограничений. Следовательно, базисное решение должно размещаться в (m+n-1) клетках транспортной таблицы. Если распространение перевозок включает (m+n-1) независимую переменную, то к нему непосредственно можно применять методы проверки оптимальности. Если же число переменных меньше указанного количества, то критерий проверки оптимальности необходимо модифицировать так, как это будет показано позже на примере. Однако если число переменных превышает (m+n-1), процедура распределения перевозок проведена некорректно. Обратимся к примеру 2 и проверим каждое из полученных распределений перевозок на базисность. В нашем примере три строки и четыре столбца, следовательно, базисное решение должно содержать (3+4-1)=6 заполненных клеток. Это говорит о том, что распределение перевозок проведено, верно. Следовательно, процедуру проверки можно применять, не прибегая к каким-либо модификациям.
Пример решения транспортной задачи [4] Задача 1. На двух складах А и В имеется соответственно 50 и 40 т груза. Требуется спланировать перевозки к трем потребителям C, D и E так, чтобы потребитель С получил 30 т, D — 20 т, E — 40 т, а затраты на перевозку были минимальными. Стоимость перевозки от складов к потребителям указаны в таблице. Решение. Составим математическую модель этой задачи. На множестве решений системы
Задача 2. На вокзалы А и В прибыло несколько комплектов мебели. Эту мебель нужно доставить в магазины C, D, E с учетом их потребностей. Спланировать перевозки этой мебели так, чтобы общая стоимость этих перевозок была наименьшей. Необходимые данные для решения задачи указаны в таблице.
Задача 3. В пунктах А и В находятся заводы по производству кирпича, в пунктах C и D — карьеры, снабжающие их песком. Заводу А необходимо 40 т песка, заводу В — 50 т. Карьер C готов перевезти 70 т песка, а карьер D — 30 т. Требуется спланировать перевозки так, чтобы затраты на перевозку были минимальными. Условия задачи представлены в табл.. Для упрощения решения в таблицу введен условный потребитель Е.
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.) |