19812

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

Доклад

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

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

Украинкский

2013-07-17

28 KB

1 чел.

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

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


 

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

66348. Му Family 44 KB
  Мета: повторити раніше вивчені слова та структури, формувати уявлення про звукову систему англійської мови, ввести нові лексичні одиниці з теми "Му Family",вчити впізнавати їх та застосовувати у мовленні; формувати уміння в учнів самостійно працювати над завданнями...
66350. Іграшки. Урок англійської мови у 1 класі 36.5 KB
  Hello, everyone! I’m glad to see you! P: Hello! We are glad to see you too! T: How are you today? Come here and show us a picture with your mood. ( Учні виходять до дошки і обирають малюнок з смайликом, який показує настрій ).P1: I am fine, thank you. P2: I am so-so.
66351. З НОВИМ РОКОМ 38 KB
  Мета: повторити лексичний матеріал теми; ознайомити учнів з новими лексичними одиницями та тренувати їх вживання в усному мовленні; практикувати вживання в усному мовленні структури I see; повторити раніше вивчені літери; ознайомити учнів з літерами...
66352. Numbers. Цифры 127 KB
  Задача урока: Тренировка учащихся в употреблении лексики по теме Цифры в устных видах речевой деятельности; Совершенствование фонетических навыков навыков аудирования чтения и письма. Цели урока: Образовательные: Активизировать навыки чтения монологической и диалогической речи...
66353. Букви. Сім’я. Іграшки 2.03 MB
  Перевірити рівень засвоєння матеріалу «Букви. Сім'я. Іграшки», рівень умінь застосовувати вивчене в знайомих і змінених ситуаціях, розвиток монологічного мовлення, практикувати у вживанні граматичної структури have got.
66354. Travelling to Wonderland 37 KB
  Сегодня у нас с вами необычный урок, урок – путешествие в волшебную страну «Wonderland», в котором разговаривают на английском языке. А что бы наше путешествие состоялось, нам нужно вспомнить все, что мы знаем. Наши знания очень пригодятся.
66355. Узагальнення вивченого матеріалу по темам «Кольори» та «Алфавіт» 111.5 KB
  Мета уроку: Збагатити лексичний словник, стимулювати комунікативність, пізнавальну діяльність, інтерес до вивчення англійської мови. Практикувати вживання слів та фраз, повторити лексику попередніх уроків. Розвиток мовленнєвої компетенції, уваги, уяви, слуху зорового сприйняття.
66356. Спорт. Відкритий урок з англійської мови у 2 класі 215.5 KB
  Мета: Практична: вчити учнів вживати в мові лексику за темою «Спорт», формувати навички монологічного мовлення на рівнікількох речень. Вчити складати діалоги. Удосконалювати навички вживання do, go, play із назвами спорту. “With great pleasure” в усному мовленні.