19817

Судження за допомогою оцінки клітини про її вигідність чи невигідність

Доклад

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

3.Судження за допомогою оцінки клітини про її вигідність чи невигідність. 1. Перевіряють виконання необхідного і достатнього умови розв'язності задачі. Якщо завдання має неправильний баланс то вводять фіктивного постачальника або споживача з відсутніми запасами або за

Украинкский

2013-07-17

27.5 KB

0 чел.

3.Судження за допомогою оцінки клітини про її вигідність чи невигідність.


1. Перевіряють виконання необхідного і достатнього умови розв'язності задачі. Якщо завдання має неправильний баланс, то вводять фіктивного постачальника або споживача з відсутніми запасами або запитами і нульовими вартостями перевезень.
2. Будують початкове опорне рішення (методом мінімальної вартості або яким-небудь іншим методом) і перевіряють правильність його побудови, для чого підраховують кількість зайнятих клітин (їх має бути m + n-1) і переконуються в лінійної незалежності векторів-умов (методом викреслювання).
3. Будують систему потенціалів, що відповідають опорному рішенням. Для цього вирішують систему рівнянь + = при> 0. Для того щоб знайти приватне рішення системи, одному з потенціалів (зазвичай тому, якому відповідає більше число зайнятих клітин) задають довільно деяке значення (частіше нуль). Решта потенціали однозначно визначаються за формулами = - при> 0, (24)
4еслі відомий потенціал, і
= - При> 0, (25)
якщо відомий потенціал.
4. Перевіряють, чи виконується умова оптимальності для вільних клітин таблиці. Для цього обчислюють оцінки для всіх вільних клітин за формулами = + - і ті оцінки, які більше нуля, записують в ліві нижні кути клітин. Якщо для всіх вільних клітин 0, то обчислюють значення цільової функції, і рішення задачі закінчується, так як отримане рішення є оптимальним. Якщо ж є хоча б одна клітина з позитивною оцінкою, то опорне рішення не є оптимальним.
5. Переходять до нового опорного рішення, на якому значення цільової функції буде менше. Для цього знаходять клітину таблиці завдання, якій відповідає найбільша позитивна оцінка max {} =. Будують цикл, що включає до свого складу дану клітку і частина клітин, зайнятих опорним рішенням. У клітинах циклу розставляють по черзі знаки "+" і "-", починаючи з "+" в клітці з найбільшою позитивною оцінкою. Здійснюють зрушення (перерозподіл вантажу) по циклу на величину =. Клітка зі знаком "-", в якій досягається, залишається порожньою. Якщо мінімум досягається в декількох клітинах, то одна з них залишається порожньою, а в інших проставляють базисні нулі, щоб число зайнятих клітин залишалося рівним m + n-1. Далі повертаємось до пункту 3 алгоритму.


 

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

5255. Выбор диодов СВЧ для конкретного применения 575.5 KB
  Выбор диодов СВЧ для конкретного применения Выполнить: Указать выбранные типы, обеспечивающие лучшее качество работы, и указать название, автора и страницы справочника. Указать функциональное назначение выбранных типов диодов. Прив...
5256. Проектирование двухступенчатого цилиндрического редуктора с косозубыми колесами 179.34 KB
  Техническое задание Определить исходные данные для проектирования двухступенчатого цилиндрического редуктора с косозубыми колесами в быстроходной (б) и прямозубыми колесами в тихоходной (Т) ступени рис. 1. Подобрать двигатель, определить перед...
5257. Параллельный метод для нахождения плана распределения каналов 102 KB
  Цель работы Изучить параллельный метод для нахождения плана распределения каналов (ПРК), который является приближенным. Такой метод зачастую используется при большом числе узлов. Задание Требования задаются числом каналов между различными парами узл...
5258. Зарубежное инвестирование 65.5 KB
  Вопрос №1. Дайте определение прямых инвестиций. Охарактеризуйте основные мотивы прямого зарубежного инвестирования, назовите его формы. Какие выгоды получает от вложения капитала за рубеж прямой инвестор? Прямые инвестиции – это вложение денежн...
5259. Міжнародний менеджмент. Конспект лекцій 1.16 MB
  Лекція. Введення у міжнародний менеджмент Міжнародний бізнес та міжнародний менеджмент Економічний, правовий та політичний аналіз в контексті задач міжнародного менеджменту Комплексний аналіз культурного середовища та врахування...
5260. Состав радиопередающего оборудования. Среднесуточная загрузка передатчиков и типы антен 145.24 KB
  Исходные данные Исходные данные о составе радиопередающего оборудования, заказчиках, классах излучения и среднесуточной загрузке передатчиков, о количестве и типах антенных сооружений, имеющихся на передающем радиоцентре, приведены в таблице 1...
5261. Международные финансовые и кредитные институты 109.5 KB
  Международные финансовые и кредитные институты Сущность, состав и роль международных финансовых и кредитных институтов Международный валютный фонд, его цели, задачи и основные функции Всемирный банк, его цели и задачи Состав ...
5262. Основы банковского маркетинга 96.5 KB
  Основы банковского маркетинга Банковский маркетинг: понятие, задачи, функции Концепция банковского маркетинга и маркетинговая деятельность Содержание маркетинговой деятельности банка Вопрос 1. Банковский маркетинг: понятие, задачи,...
5263. Основы банковского менеджмента 151 KB
  Основы банковского менеджмента Понятие и общая характеристика системы банковского менеджмента Оценка и качество банковского менеджмента Сущность, значение и принципы реализации банковской политики Финансовый менеджмент...