19812

Знаходження оптимального розподілу поставок методом оцінки клітин

Доклад

Информатика, кибернетика и программирование

2.Знаходження оптимального розподілу поставок методом оцінки клітин Один з найбільш простих методів вирішення транспортної задачі розподільний метод.Нехай для транспортної задачі знайдено початкове опорне рішення і обчислено значення цільової функції на цьому ріше

Украинкский

2013-07-17

28 KB

1 чел.

2.Знаходження оптимального розподілу поставок методом оцінки клітин

Один з найбільш простих методів вирішення транспортної задачі - розподільний метод.
Нехай для транспортної задачі знайдено початкове опорне рішення і обчислено значення цільової функції на цьому рішенні Z (). За теоремою для кожної вільної клітини таблиці завдання можна побудувати єдиний цикл, який містить цю клітку і частина клітин, зайнятих опорним рішенням. Означивши цей цикл і здійснивши зрушення (перерозподіл вантажу) по циклу на величину =, можна отримати нове опорне рішення Х2.
Визначимо, як зміниться цільова функція при переході до нового опорного рішення. При зсуві на одиницю вантажу по циклу, відповідному клітці (l, k), приріст цільової функції дорівнює різниці двох сум: =, де - сума вартостей перевезень одиниць вантажу в непарних клітинах циклу, позначених знаком "+", - сума вартостей перевезень одиниць вантажу в парних клітинах циклу, позначених знаком «-».
У клітинах, позначених знаком "+", величини вантажу додаються, що призводить до збільшення значення цільової функції Z (), а в клітинах, позначених знаком "-", величини вантажу зменшуються, що призводить до зменшення значення цільової функції.
Якщо різниця сум для вільної клітини (l, k) менше нуля, тобто <0, то перерозподіл величини за відповідним циклу призведе до зменшення значення Z () на величину, тобто опорне рішення можна поліпшити. Якщо ж величини, звані оцінками, для всіх вільних клітин таблиці транспортної задачі ненегативні, то значення цільової функції не можна зменшити і опорне рішення оптимально. Отже, ознакою оптимальності розподільного методу є умова = 0. (11)
Для вирішення транспортної задачі розподільним методом необхідно знайти початкове опорне рішення. Потім для чергової опорної клітини (l, k) побудувати цикл і обчислити оцінку. Якщо оцінка ненегативна, перехід до наступного вільної клітці. Якщо ж оцінка негативна, слід здійснити зсув по циклу на величину =. В результаті вийде нове опорне рішення.
Для кожного нового опорного рішення обчислення оцінок починається з першої вільної клітини таблиці. Очевидність перевіряються вільних клітин доцільно встановлювати в порядку зростання вартості перевезень, так як вирішується завдання на знаходження мінімуму.


 

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

77210. Разработка framework для JSR 290 TCK 450 KB
  Technology Compatibility Kit (TCK) – тестовая сюита, позволяющая протестировать реализацию какого-либо Java Specification Request (JSR) на соответствие спецификации. Это одна из трех составляющих ратифицированного JSR в Java Community Process, которыми являются: Спецификация JSR JSR Reference Implementation
77211. АКТОРНОЕ РАСШИРЕНИЕ ЯЗЫКА JAVA В СРЕДЕ MPS 243 KB
  В качестве средства создания расширения была выбрана среда мета-программирования MPS что позволило автоматически получить интегрированные средства разработки для применения расширения и кроме того достичь совместимости с другими языковыми расширениями созданными в среде MPS. Название средства Совместимость расширений Языковая инфраструктура LISP Есть Нет Внутренние языки в Ruby Groovy Есть Нет XText frmework Нет Есть...
77212. Исследование работы с географическими данными в Oracle 10g 482.5 KB
  Спроектировать базу данных с учетом специфики хранимой информации; Перенести собранную обо всех электростанциях информацию в БД; Разработка интерфейса администратора для мониторинга и управления информационной системой.
77213. СОЗДАНИЕ СРЕДЫ РАЗРАБОТКИ ДЛЯ ЯЗЫКА ПРОГРАММИРОВАНИЯ OCAML 96 KB
  OCaml в настоящее время является активно развивающимся языком программирования. Секрет его успеха, возможно, заключается в том, что этот язык интуитивно понятен и прост для изучения даже неопытным программистом.
77214. Cоздание дискретизирующего фильтра для обработки электроокулограмм. Обеспечение работы и настройки фильтра в режиме реального времени 512 KB
  Причиной этих бросков служит тот факт, что глазное яблоко представляет собой электрический диполь (сетчатка заряжена отрицательно относительно роговицы), поэтому при поворотах глазного яблока в районе глаз регистрируется изменение разности потенциалов.
77215. Язык для описания плагинов в среде программирования JetBrains MPS 347.5 KB
  С каждым годом приложения становятся более объемными и сложными. В связи с этим, требуются все более изощренные подходы к программированию для создания новых программ. Попробуем проследить, как развивались средства программирования, чтобы удовлетворять нуждам программистов по написанию сложных проектов.
77216. Применение нейронных сетей к ранжированию результатов информационного поиска 282 KB
  Существует ряд алгоритмов машинного обучения, которые позволяют определять ранг документов. Например, RankProp, PRank и RankBoost. Данные адаптивные алгоритмы тренируются на обучающей выборке документов, чтобы выявить зависимости положения документа от его признаков.
77217. Распознавание автомобильных номеров с помощью нейронных сетей 230 KB
  В современных условиях, когда прослеживается явная тенденция к автоматизации большинства процессов, которые раньше предполагали безоговорочное участие человека, идея автоматической идентификации автомобиля по номерной пластине с целью дальнейшего использования...
77218. Создание физически-корректного дождя и сопутствующих эффектов 5.78 MB
  Целью курсовой работы была разработка и реализация дешевых, с точки зрения вычислений, но мощных алгоритмов визуализации как непосредственно самого дождя, так и различных эффектов его сопровождающих.