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 алгоритму.


 

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

77399. Актуальность использования нетрадиционных и возобновляемых источников энергии 103 KB
  Актуальность использования нетрадиционных и возобновляемых источников энергии Понятие традиционной энергетики. Традиционная энергетика совокупность технических устройств использующих хорошо освоенные в технологическом отношении энергетические источники и способы преобразования получаемой от них энергии в первую очередь в электрическую. Их отличительные особенности: – значительная единичная мощность; – работа в общей электросети возможна работа и в тепловой сети; – единый...
77400. Определение токсичных выбросов в атмосферу от объектов традиционной энергетики 142 KB
  Определяется полное количество тепла полезно использованное в паровом котле кВт 1. Значения удельной энтальпии энергоносителя определяется при известных его параметрах по таблицам теплофизических свойств воды и водяного пара. Определяется расход топлива на каждый котел установленный в тепловом источнике г с 1. Определяется расход топлива на все котлы установленные в тепловом источнике г с 1.
77401. Признание брака недействительным 44 KB
  Понятие и основания признания брака недействительным. Под признанием брака недействительным понимается аннулирование брака и всех его правовых последствий с момента его заключения. Признание брака недействительным по правовой природе – санкция за нарушение требований установленных семейным законодательством.
77402. Правоотношения супругов 135.5 KB
  Личные неимущественные права и обязанности супругов. Каждый из супругов вправе выбирать место жительства место пребывания профессию и род занятий. СК не обязывает супругов проживать совместно но это более благоприятно устанавливая свободу в выборе место пребывания и места жительства – предоставляет выбор и свободу жить раздельно может быть даже и весь период супружеской жизни.
77404. Правоотношение родителей и детей 168 KB
  В данном случае – это происхождение ребёнка от конкретных лиц удостоверенное в установленном законом порядке. Установление происхождения ребёнка рождённого в браке. Происхождение ребёнка рождённого в браке установить довольно проще чем рождённого вне брака. Установление происхождения ребёнка рождённого в браке происходит в административном порядке.
77405. Алиментные обязательства членов семьи 75.5 KB
  Алиментное обязательство является имущественным правоотношением и средства предоставляющиеся в качестве алиментов представляют собой товар. В настоящее время алиментные обязательства могут возникать не только на основании закона но и на основании соглашения об уплате алиментов. Взаимность и возмездность в том что если родитель в своё время уклонялся от выполнения обязанности по содержанию ребёнка суд может освободить ребёнка от уплаты алиментов. Плательщик алиментов выплачивает алименты не предполагая получить какое-либо имущественное...
77406. Усыновление (удочерение) детей 102.5 KB
  Что касается усыновления – он в СК не раскрыт используется в различных аспектах: Правовой институт который представляет собой систему правовых норм посвящённых подбору усыновителей определению порядка передачи ребёнка на усыновление условия усыновления установление порядка и правовых последствий прекращения отношений по усыновлению. Усыновление как форма устройства определяет юридическую судьбу ребёнка. Усыновление обладает приоритетом именно для того чтобы обеспечить наилучшие интересы ребёнка существуют определённые правила...
77407. Семейное право в правовой системе РФ 40 KB
  Понятие и признаки семьи. Семья в Российском праве не является субъектом S является лишь члены семьи. Понятие семьи даётся социологическими науками понимается и как сожительство разнополых особей но и как различного степени родства людей или находящихся в свойстве родственниками по крови они не являются. В российском праве нет единого определения семьи которое бы имело значение для всех отраслей российского права.