19812

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

Доклад

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

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

Украинкский

2013-07-17

28 KB

1 чел.

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

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


 

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

23447. Битва за небеса 1.56 MB
  После нее победители немцев Британия Франция и США устанавливают Версальскую систему равновесия. Германия снова повержена и победители прежде всего наша Империя и США в 1944 году на Ялтинской конференции проектируют Ялтинскую модель мира. С балансом сил двух мировых держав СССР и США. Проклятая Североатлантическая сила ударит и по России едва только у нас сгниют от старости последние баллистические ракеты способные ударить по США.
23448. Геноцид русского народа 288.39 KB
  Ежегодно население России её коренных народов неуклонно сокращается и этот процесс вотвот станет необратимым. Каждый раз ставилась цель: довести долю машин и оборудования в экспорте России хотя бы до уровня 1985 года хотя бы до 40 . При этом промышленность России 2000х годов примерно в 13 раза энергопрожорливее индустрии СССР 1985 года. Ну где это всё Производительный малый бизнес в России раздавлен.
23449. Секретная служба в тылу немцев (1914 - 1918 гг.) 1.97 MB
  В 1913 году закончил колледж Гонвилла и Кейюса в Кембридже и собирался продолжить учебу чтобы стать горным инженером но с началом Первой мировой войны пошел добровольцем на фронт сначала служил в медицинской службе потом в полевой артиллерии где дослужился до капитана. Тем не менее они отмечали что в книгах содержится ряд неточностей и что автор порой слишком преувеличивал свои заслуги. Если мне не придётся больше быть в Голландии то я всё же буду помнить что дорога из Роттердама в Амстердам через Гаагу и Гарлем ровная а вокруг...
23450. История гитлерюгенда 404.5 KB
  История гитлерюгенда Введение ХХ век далеко не случайно считается эпохой тоталитаризма. У части западных историков сложилось восприятие гитлерюгенда как организации автономной от НСДАП и государственных органов Третьего Рейха. Поэтому несомненно что в большинстве своем члены гитлерюгенда свободны от вины за преступления совершенные нацистами. Но несмотря на всё это надо объективно рассматривать историческую роль гитлерюгенда так как он был организацией вполне интегрированной в политическую систему Третьего Рейха.
23451. Алфавитно-справочный перечень государей русских и замечательнейших особ их крови 4.98 MB
  АГАФИЯ великая княгиня Так некоторые известия именуют жену Всеволода II Ольговича великого князя киевского сообщая что она выдана за него в 1116 г. 189 и родила мужу сыновей Святослава князя киевского и Ярослава князя черниговского да еще дочь Звениславу за Болеславом IV герцогом польским. АГАФИЯ ВСЕВОЛОДОВНА великая княгиня жена по Татищеву вторая великого князя Юрия Георгия II Всеволодовича великого князя владимирского дочь Всеволода Святославича Чермного князя черниговского одно время великого князя киевского от...
23453. Древние майя. Загадки погибшей цивилизации 2.28 MB
  Древние майя. Кто создал эти колоссы Когда С какой целью Что вызвало к жизни блестящую цивилизацию майя в саном центре гиблых тропических джунглейАвтор книги на основе новейших данных о древнеамериканской истории рассматривает ряд таинственных событий далекого прошлого индейцев майя. Гуляева это древнейшие судьбы Мезоамерики важнейшего и глубоко своеобразного региона одного из первых очагов производящего хозяйства высокой и оригинальной цивилизации индейских народностей майя сапотеков нахуа. Гуляев назвал ее Древние...
23454. Георгий Константинович Жуков Воспоминания и размышления 10.56 MB
  Скоро мы узнали что в Питере 9 января 1905 года царские войска и полиция расстреляли мирную демонстрацию рабочих которая шла к царю с петицией просить лучших условий жизни. После Нижегородской ярмарки в том же году пришлось поехать на другую ярмарку в Урюпино в Область Войска Донского. Я всегда восхищался этим романтическим родом войск. От раненых мы многое узнали и в первую очередь то что наши войска очень плохо вооружены.
23455. Третий Рим 14.12 MB
  Ведь ему известно что русские были сторонниками христианской Византии и противниками мусульманской Турции. Следуя тезису о богоустановленном единстве всего христианского мира Филофей доказывал что первым мировым центром был Рим старый за ним Рим новый Константинополь а в последнее время на их месте стал третий Рим Москва. Не надо думать что это какаято гипербола или метафора. Филофей ясно подчеркивает что речь идет об объединении всех христианских царств под властью великого князя Василия.