19812

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

Доклад

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

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

Украинкский

2013-07-17

28 KB

1 чел.

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

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


 

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

67028. ТРАНСФОРМАЦИЯ КОРПОРАТИВНОЙ КУЛЬТУРЫ ДЛЯ ДОСТИЖЕНИЯ СТРАТЕГИЧЕСКИХ ЦЕЛЕЙ 645.5 KB
  Корпоративная культура может играть решающую роль в мобилизации всех ресурсов организации на достижение целей, но также может стать тормозом ее дальнейшего развития, поэтому особую актуальность в настоящее время приобрел вопрос возможности воздействия на процессы формирования, поддержания или изменения корпоративной культуры...
67029. Шкільний проект духовно – морального виховання 256.5 KB
  Вічним джерелом цієї проблеми є нестримне прагнення кожної людини визначитись з основами своєї діяльностіпоказати те чому завдячує людинароблячи той чи інший крок у своєму житті. Невід’ємною ланкою духовності людини є її культура. Поняття культура нерозривно пов’язане з усіма видами діяльності людини: політичнимекономічним правовим релігійним етичним художнім тощо.
67030. Путь к гармонии 100 KB
  Оборудование: мини-проекты толковый словарь правила Шаги к успеху и гармонии эмоциональный термометр индикаторы настроения ступенчатая шкала Этапы пути к гармонии. А чтобы достигнуть всего этого человек прежде всего должен находиться в гармонии с самим собой.
67031. Не руйнуй гармонії земної 107.5 KB
  Глобальною проблемою стали кислотні дощі, які гублять рослинність, знищують життя в прісних водах, це і негативні наслідки науково-технічної революції, неконтрольоване зростання населення Землі, кількість якого вже перевищила критичну межу, дедалі більше забруднення атмосфери, гідросфери.
67032. Що таке гендерна рівність? Всі ми – різні, але всі ми – однакові 4.19 MB
  Мета: ознайомити дітей з поняттями “гендер”, “гендерна рівність” та основами гендерно-правового законодавства України. Формувати в учнів інтерес до навчання з даної теми. Розвивати мислення, пам’ять, увагу та активізувати словниковий запас. Виховувати людяність, гуманність та толерантне ставлення один до одного, бажання приносити користь у суспільстві.
67033. Я люблю географію 100.5 KB
  Організаційний момент Сьогодні між командами змагання Нехай образ не буде серед вас Бо переможцем або переможеним Сьогодні може бути хтось із вас. За кожну правильну відповідь команда отримує 1 бал а за музичний конкурс 2 бали. 1 раунд Географічний лікбез командам прпонується однакове завдання: необхідно на слух правильно написати географічну...
67034. Географічна гра «Щасливий випадок» 69 KB
  Мета гри – дає можливість перевірити рівень засвоєних знань,виявити вміння застосовувати набуті знання, розвивати інтерес і пізнавальну діяльність учнів,сприяє розвитку навичок спілкування між підлітками. В грі приймають участь 2 команди по 5-6 учнів в кожній.
67035. Прямоугольный, остроугольный и тупоугольный треугольники 126 KB
  Цели урока: Обучающие: формировать понятие о прямоугольном, остроугольном, тупоугольном треугольниках; учить анализировать объекты; Развивающие: развивать речь, память, воображение, творческое мышление; Воспитывающие: учить выполнять работу аккуратно, уважать мнение других, жить в коллективе.
67036. Проект «Герб і прапор класу» 236.5 KB
  Мета: Сприяти формуванню особистісних якостей, виховувати особистість, якій притаманні демократична громадянська культура, готовність до компетентної участі у житті суспільства. Розвивати національну свідомість. Вивчення геральдики країни, області, міста, гімназії Виховувати патріотизм, повагу до української державної символіки.