19812

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

Доклад

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

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

Украинкский

2013-07-17

28 KB

1 чел.

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

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


 

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

3438. Лекционный курс по начертательной геометрии 1.92 MB
  Лекционный курс по Начертательной Геометрии предназначен для освоения студентами Химико-биологических и Электротехнических специальностей техники геометрического и графического моделирования используемой при чтении и выполнении проектной документации...
3439. Источники аграрного права 89.23 KB
  Источники аграрного права 1. Понятие и особенности источников аграрного права Источники аграрного права служат формой выражения и закрепления аграрной политики государства как важного фактора, влияющего на формирование и развитие юридических институтов...
3440. Решение задач по уравнениям математической физики с применением математических пакетов 858.5 KB
  Данное пособие написано с целью представить небольшой вводный курс уравнений математической физики и показать, как применять для их решения математические пакеты. Основным таким пакетом является система компьютерной математики Maple
3441. Методы и технологии программирования 5.26 MB
  Введение в технологию разработки промышленного ПО. Основные понятия Трудозатраты, связанные с созданием программного обеспечения (ПО) прямо связаны с качеством и сложностью создаваемого ПО. Так трудозатраты на создание программного продукта в...
3442. Снижаем налоговые штрафы. Инструкция для налогоплательщика 517 KB
  Правовые основы снижения сумм налоговых санкций Нормы, регулирующие вопросы снижения штрафов, примененных налоговыми органами, находят свое закрепление в различных объективных формах, выражениях, которые объединяются общим понятием "источни...
3443. Методика аудита расчетов с персоналом по оплате труда 254 KB
  В России аудит является новым направлением внешнего контроля за хозяйственной деятельностью предприятий. С развитием рыночных отношений в действующие нормативные документы часто вносятся изменения и дополнения, которые в силу разных обстоят...
3444. Арбитражный процесс 3.79 MB
  В учебнике на основе современных процессуально-правовых концепций освещены все основные институты арбитражного процессуального права, в том числе вопросы международного гражданского (арбитражного) процесса и третейского разбирательства. Преимущество...
3445. Характеристики электропотребителей и системы электроснабжения микрорайона 899 KB
  Характеристики электропотребителей и системы электроснабжения микрорайона. Характеристика электроприемников городских электрических сетей. По характеру электропотребления и показателям электрической нагрузки все потребители города разбиваются на следующие группы.
3446. Эргономический анализ автомобиля Ford Fusion 1.4 MB
  Эргономика — это наука, изучающая проблемы, возникающие в системе «человек-техника-среда», с целью оптимизации трудовой деятельности оператора, создания для него комфортных и безопасных условий, повышения за счет этого его...