19812

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

Доклад

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

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

Украинкский

2013-07-17

28 KB

1 чел.

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

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


 

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

40748. Субєкти кримінального процесу 68.21 KB
  Інші учасники кримінального провадження. Відводи субєктів кримінального провадження. Поняття і класифікація субєктів кримінального процесу Кримінальний процесуальний кодекс України прийнятий 13 квітня 2012 року чітко не визначає поняття і не подає класифікацію субєктів кримінального провадження тому їх називають порізному: 1 особи які беруть участь у процесуальній дії статті 104 107 КПК; 2 учасники кримінального провадження статті 27 113 237 КПК та ін.; 3 учасники судового провадження статті 34 107 317 347 КПК та ін.
40749. Сучасні види та способи друку 175.54 KB
  Класифікація видів та способів друку. Спеціальні види та способи друку. Класифікація видів та способів друку. Вид друку оприділяється конкретними особливостями роз положення друкарських елементів відносно пробільних на друкарських формах.
40750. АХОДИ ЗАБЕЗПЕЧЕННЯ КРИМІНАЛЬНОГО ПРОВАДЖЕННЯ 107.41 KB
  Затримання особи та обрання їй запобіжного заходу у вигляді взяття під варту : у чинному КПК України та у його проекті О. Поміщення особи у медичний заклад : пропозиції до нового КПК України В. 131 КПК заходами забезпечення кримінального провадження є: 1 виклик слідчим прокурором судовий виклик і привід ст. 133−143 КПК; 2 накладення грошового стягнення ст.
40751. Загальні положення досудового розслідування 41.62 KB
  Загальні положення досудового розслідування Поняття стадії досудового розслідування. Форми досудового розслідування: дізнання та досудове слідство. Поняття та характеристика загальних положень досудового розслідування.
40752. ПРОВАДЖЕННЯ СЛІДЧИХ (РОЗШУКОВИХ) ДІЙ 70.79 KB
  Забезпечення недоторканості житла чи іншого володіння особи в кримінальному процесі : Інститут слідчої дії ‑ це система правових приписів що визначають: сферу й обєкт слідчої дії його мету і завдання; підстави проведення; коло учасників та їх правовий статус; механізм реалізації ними своїх прав і обовязків; порядок здійснення і правила провадження пізнавальнозасвідчувальних дій; способи і форми їх фіксації; гарантії захисту прав і свобод людини заходи та межі примусу і відповідальності які застосовуються у разі...
40753. ПОВІДОМЛЕННЯ ПРО ПІДОЗРУ 44.63 KB
  Повідомлення про підозру займає особливе місце в структурі досудового розслідування. Воно підводить підсумок проведеної до того часу роботи, зібраним доказам, у більшості визначає подальше спрямування кримінального провадження і є початковим моментом притягнення до кримінальної відповідальності.
40754. Абразивні матеріали: класифікація, властивості та галузі використання 111.92 KB
  Абразивные материалы это материалы обладающие высокой твердостью и используемые для обработки поверхности различных материалов. Для изготовления абразивных инструментов используются частицы материалов различной зернистости обладающие высокой твердостью и способностью резания. Карбид кремния SiC обладает более высокой твердостью до3235 ГПа но имеет высокую хрупкость и малую прочность поэтому применяется для обработки хрупких материалов чугунов бронзы титановых и тугоплавких сплавов заточки твердосплавных инструментов.
40755. Регулювання конфліктів 69.82 KB
  Згладжування конфлікту. Співробітництво базується на впевненості сторін конфлікту в тому що розбіжності в поглядах є закономірними і сторони визнають право кожного на особисту думку та готові зрозуміти один одного що дає можливість аналізувати причини розбіжностей і знайти прийнятний для всіх вихід. Методика вирішення конфлікту
40756. ЗУПИНЕННЯ І ЗАКІНЧЕННЯ ДОСУДОВОГО РОЗСЛІДУВАННЯ 39.61 KB
  Підстави і процесуальний порядок зупинення та відновлення досудового розслідування. Форми закінчення досудового розслідування. Про затвердження Інструкції з організації взаємодії органів досудового слідства з оперативними підрозділами ОВС на стадіях документування злочинних дій реалізаціїоперативних матеріалів розслідування кримінальної справи та її розгляді в суді : наказ МВС України від 07 верес.