28471

Метод найменшої вартості побудови початкового опорного плану

Доклад

Математика и математический анализ

Для даної задачі такою є клітинка А2В2 в яку записується найменше з чисел 220 230. У звуженому полі клітинок вибирається найменша вартість в клітинці А2В1 в яку записується min 10 150 =10. В цю клітинку записується min 280300=280 проставляється прочерк в А3В3 і біля запасів А1 записується залишок в 20 од. Далі заповнюється клітинка А1B4 з найменшою вартістю числом min 20 200=20 виставляються прочерки в клітинках А1В1 А1В2 і записується залишок потреб В4 в розмірі 180 од.

Украинкский

2013-08-20

17.79 KB

14 чел.

17.23.Метод найменшої вартості побудови початкового опорного плану передбачає на першому кроці вибір клітинки з найменшою вартістю перевезення одиниці вантажу (найменшого елемента матриці (cij)). Для даної задачі такою є клітинка А2В2, в яку записується найменше з чисел 220, 230. Олівцем виставляються прочерки в клітинках А1 В2, А3В2, виключаючи тим самим їх з наступного розгляду. Біля запасів А2, записуються залишки запасів в розмірі 10 од. У звуженому полі клітинок вибирається найменша вартість в клітинці А2В1 в яку записується min (10, 150) =10. В А2В3 та А2В4виставляються прочерки, бо запаси А2 вичерпані, а під потребами В1 записуються залишки потреб в розмірі 140 од. На наступному кроці серед клітинок, що залишилися незаповненими, вибирається А1 В3, в якій міститься найменша вартість. В цю клітинку записується min (280,300)=280, проставляється прочерк в А3В3 і біля запасів А1 записується залишок в 20 од. Далі заповнюється клітинка А1B4 з найменшою вартістю (числом min (20, 200)=20), виставляються прочерки в клітинках А1В1, А1В2, і записується залишок потреб В4 в розмірі 180 од. В підсумку залишаються тільки дві клітинки (А3В1, та А3В4), які не мають прочерка або чисел, що визначають величину перевезень. В першу з них (вартість менша) записуємо min (140, 320)=І40, а в другу – залишок запасів А3,. Остаточно отримаємо таблицю 3.Таблиця З

Зауважимо, що доцільно самостійно здійснювати кожен крок побудови опорного плану у власноруч намальованій транспортній сітці, а не користуючись вже готовою табл.З.Побудований опорний план методом найменшої вартості також невироджений. Знайдемо вартість перевезень згідно з ним:

Порівняння отриманих значень цільової функції на планах, побудованих різними методами, вказує на те, що опорний план, записаний в табл. З кращий (цільова функція мінімізується). Відмітимо, що можна навести багато прикладів ТЗ, в яких значення цільової функції на опорному плані, побудованому діагональним методом, е меншим, ніж на плані, побудованому методом найменшої вартості. Проте в середньому метод найменшої вартості дає краще наближення до оптимального плану в порівнянні із діагональним методом.


 

А также другие работы, которые могут Вас заинтересовать

18811. Взаимодействие организма и среды 121.5 KB
  Лекция 2. Взаимодействие организма и среды План лекции: Понятие о среде обитания и средах жизни Основные представления об адаптациях организмов. Факторы среды. Классификация факторов Общие закономерности воздействия факторов на живые организмы ...
18812. Популяционный уровень жизни. Биоценозы и экосистемы, основы их жизнедеятельности 90.5 KB
  Лекция 34. Популяционный уровень жизни. Биоценозы и экосистемы основы их жизнедеятельности План лекции Популяция ее характеристики и структура. Понятие о биоценозе и его структуре. Экосистема ее свойства и структура. Поток энергии и пищевые цепи. Э...
18813. Биосфера – глобальная экосистема 72.5 KB
  Лекция 5 Тема: Биосфера глобальная экосистема. План 1. Общие закономерности организации биосферы. Структура и границы. 2. Закон В.И. Вернадского о биогенной миграции атомов в биосфере. 3. Основные функции живого вещества. 4. Место человека в биосфере. Концепция и кри...
18814. Биогеохимические циклы. Круговорот веществ в природе 53 KB
  Тема: Биогеохимические циклы. План лекции Круговорот веществ в природе Биогеохимические циклы наиболее жизненно важных биогенных веществ Весь лик Земли: все ее ландшафты атмосфера химический состав вод все это обязано своим происхождением прежд
18815. Глобальные проблемы современности, Парниковый эффект, озоновые «дыры», кислотные дожди 90.5 KB
  Глобальные проблемы современности. Понятие загрязняющего вещества. Классификация загрязнений. Краткая характеристика загрязнения сред биосферы. Парниковый эффект озоновые дыры кислотные дожди Понятие загрязняющего вещества...
18816. ОБЩИЕ ВОПРОСЫ ОХРАНЫ ОКРУЖАЮЩЕЙ СРЕДЫ 93 KB
  Лекция 7. Тема: ОБЩИЕ ВОПРОСЫ ОХРАНЫ ОКРУЖАЮЩЕЙ СРЕДЫ План лекции 1. Общие положения охраны природной среды при хозяйственной деятельности. Концепция управления природными ресурсами по законам экологии. Инженерные природоохранные мероприятия 1. Общ
18817. Экологическая защита и охрана ОПС 77.5 KB
  Экологическая защита и охрана ОПС Примечание: Материал воспроизведен по Маковику. В этом источнике он хорошо систематизирован. Жирным курсивом выделена информация кот. будет использована во время третьего тестового контроля федеральные тестовые вопросы ...
18818. Основы экологического права. Ответственность за экологические нарушения 107.5 KB
  Лекция №9. Тема: Основы экологического права. План 1.Источники экологического права. 2.Государственные органы охраны окружающей среды. 3.Экологическая экспертиза. 4.Экологический мониторинг. 5. Экологический вред и экологический риск 6. Ответственность за ...
18819. Основы защиты водных объектов от загрязнения 89 KB
  Лекция №12 Тема: Основы защиты водных объектов от загрязнения. План Запасы природных вод. Основы классификации природных вод. Характеристика водопользования и водопотребления. Критерии качества воды. Промышленная классификация вод и систем водоснабжен...