19812

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

Доклад

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

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

Украинкский

2013-07-17

28 KB

1 чел.

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

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


 

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

25545. Единственный ребенок в семье 15.5 KB
  Ребенок маленький взрослый До поступления в детский сад а то и в школу единственный ребенок общается преимущественно со взрослыми. В семье ребенок хорошо усваивает модель отношений в которой один выше по иерархии родитель а другой ниже ребенок.Все это может привести к тому что в детском коллективе ребенок либо станет одиночкой либо будет всячески противопоставлять себя коллективу привлекая к себе персональное внимание учителя или воспитателя.
25546. Жизненный цикл семьи 12.27 KB
  Сорокин выделил 4 стадии: брачная пара в момент образования семья с маленькими зависимыми детьми семья с 1 взрослым ребенком стадия отделения всех детей. Эти события образуют 4 стадии семейного цикла: предродительство 11 года стадия репродуктивного родительства 25 года стадия социализированного родительства – ограничивается достижением совершеннолетия детьми либо моментом отделения последнего из взрослых детей стадия прародительства настает с наступлением первого внука 199 года Варианты стадий: продолженная...
25547. Функции семьи 12.52 KB
  Хозяйственнобытовая Поддержание физического здоровья членов семьи уход за детьми и престарелыми членами семьи. Получение хозяйственнобытовых услуг одними членами семьи от других. Экономическая Экономическая поддержка несовершеннолетних и нетрудоспособных членов общества Получение материальных средств одними членами семьи от других.
25548. Характеристика жилищных проблем молодых семей и перспективы их решения 16.22 KB
  Жилищная проблема молодых семей и ее особенности Как отмечалось ранее жилищная проблема – одна из острейших проблем стоящих перед молодежью. Сутью жилищной проблемы стало обеспечение доступности жилища для семей и одиноких граждан у которых доходы не соответствуют затратам на его воспроизводство то есть строительство реконструкцию модернизацию ремонт содержание 18. Так жилье бедных семей только на 58 обеспечено телефонами на 83 централизованным водоснабжением холодной водой и на 73 горячей водой на 87 центральным...
25549. Сущность, цель, принципы, направления в РФ 17.58 KB
  В конце прошлого века в российской социологической литературе достаточно четко обозначились 2 концептуальных подхода интерпретирующие семейные отношения и необходимость воздействия на них в рамках семейной политики. Отсюда следовала цель семейной политики: укрепление семьи как социального института. Разнообразие подходов к раскрытию сущности и целей семейной политики привели к ее пониманию как комплексной и межотраслевой. В России семейная политика получила государственное определение в 1996 году в указе президента РФ Об основных...
25551. Традиции семейного воспитания 17.48 KB
  Семья как и другие социальные институты существует воспроизводя традиции следуя определенным образцам деятельности без которых немыслимо само ее развитие. Передаваясь из поколения в поколение традиции адаптируясь к условиям современной жизни не остаются застывшими раз навсегда данными. Но эти функции обычаи и традиции осуществляют разными путями.
25552. Удовлетворенность браком и условия сохранения супружества 12.99 KB
  Субъективная удовлетворенность браком – отношение реальности выполнения партнером своих обязательств к ожидаемым. Причины неудовлетворенности браком: неудовлетворенность адекватных потребностей нереалистич чрезмерно завш ожидания в отношении брала и партнера В иследованиях установили что семейные люди особенно те кто участ в браке ощущающие более высокую степень удовлетворенности. Удовлетворенность браком может быть: полная частичная Эйдемиллер и Юстицкис различают неудовлетворительность осознанная сопровожд конфликтом...