19812

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

Доклад

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

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

Украинкский

2013-07-17

28 KB

1 чел.

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

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


 

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

54107. Криза грецької державності та піднесення Македонії 53.5 KB
  У середині ІУст.до н.е. становище грецьких міст-держав погіршилося внаслідок війни з персами, незалежність в якій вони зберегли, але понесли тяжких втрат, а також через внутрішні конфлікти та політичну роздробленість. Саме в цей час, зміцніла та почала процвітати Македонія, яка і скористалася ослабленням Греції.
54108. Базовые функции культуры 35 KB
  Человекотворческая функция. или гуманистическая функция. цицерон говорил о ней - cultura animi - возделывание, взращивание духа. бердяев считал, что судьбу нашего отечества должны решать люди с обновленным духом, иной волей к преображению жизни. все остальные функции так или иначе связаны с этой и даже вытекают из нее.
54109. День матері, Година спілкування 34 KB
  З часом воно поширилось і в інші країни світу. В Україні це свято відзначають вже 83 роки. Особливо готуються до цього свята діти. Вони дарують матусям власноруч виготовленні сувеніри та багато теплих, ласкавих та ніжних слів. Дякують за тепло, турботу та безмежну любов своїх матусь).
54111. Матусю моя дорогенька, це свято даруєм тобі 55.5 KB
  Вчитель: 8 березня – свято наших мам, бабусь, сестричок. Разом із приходом весни завітало до нас це перше весняне свято. Його ми присвячуємо найдорожчим, найріднішим людям.
54112. Свято Матері 63.5 KB
  Її любов до дитини безмежна й щира. Матусю мила найрідніша в світі Ти наше сонце щире і ясне Ти дбаєш щоб завжди ми були ситі Твоя любов дитину не мине. Найбільше щастя – мати для дитини Її любов і ласка щирий сміх.
54113. Вплив автотранспорту та сільгосптехніки на довкілля 260 KB
  Розвивати соціальні компетентно-комунікативні навички, приймати участь в дискусіях, співробітництві в групах, розвивати спостережливість, творчі, акторські здібності, розширювати кругозір студентів, викликати бажання до пошуку відповідей на запитання в книжках науково-пізнавального характеру, художній і народознавчій літературі, виховувати бережливе ставлення до природи.
54114. Мандрівка в місто культури 71.5 KB
  Раптом вибігає Поміха- Неуміха. Вона одягнена в чорне плаття, волосся розтріпане, на грудях плями, на обличчі - бруд. Вихоплює конверт, швидко продивляється лист і зловтішно викрикує:
54115. Зниклі цивілізації 52 KB
  Сьогодні ми зібралися у цій затишній кімнаті, щоб поговорити про відоме і невідоме, про знане і незнане, про фантастику і реальність. Свідомість людини швидко звикає до чогось нового, раніше незвіданого. Тунель під Ла-Маншем, пілотовані космічні польоти, всесвітня комп’ютерна мережа – усе це частина нашого сьогодення, реальності, яка ще років сто тому здалася б найсміливішою фантазією. Одначе для тих, хто народився після втілення в життя технічної новинки, воно вже не є чудом.