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


 

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

6591. Сознание и познание. Познание, истина, практика 34.34 KB
  Сознание и познание Сущность и возникновение сознания. Познание, истина, практика. Сознание существует как субъективная реальность, как идеальное, оно проявляет себя как отношение к действительности, но в то же время - оно есть реальное дело, к...
6592. Наука и ее роль в жизни общества. Функции, особенности и методы научного познания 29.91 KB
  Наука и ее роль в жизни общества Функции, особенности и методы научного познания. Стадии и уровни научного познания. НТР и моральные проблемы. Наука - это особая сфера человеческой деятельности, направленная на добывание, осмысление, системати...
6593. Человек и общество. Общество как процесс. Человек и история. 36.58 KB
  Человек и общество. Общество как система. Общество как процесс. Человек и история. Общество - система деятельности и жизни людей, объединенных территорией проживания, эпохой, историей, традициями и культурой. Основное предназначение обще...
6594. Духовная жизнь общества. Общественное сознание 30.87 KB
  Духовная жизнь общества. Общественное сознание. Основные формы духовной жизни общества. Общественное сознание и его формы. Основными формами духовной жизни общества принято считать мораль, право, религию, науку, искусство. Мораль - это...
6595. Человек и культура. Культура и цивилизация 33.62 KB
  Человек и культура. Культура и цивилизация. Структура культуры. Функции культуры. Культура и цивилизация. Культура делится на различные типы, виды, формы. Внутренняя структура культуры содержит два слоя: материальную и духовную культ...
6596. Человек и религия. Понятие, формы и функции религии. Мировые религии 39.4 KB
  Человек и религия Понятие, формы и функции религии. Мировые религии. Религия (religio - святость, благочестие) - совокупность представлений, мировоззрение и мироощущение определяемое верой в существование Бога, богов. Содержание ре...
6597. Словарь терминов по философии 48.88 KB
  Словарь терминов по философии Абсолют (от лат. absolutus - безусловный, неограниченный) - в философии и религии безусловное, совершенное начало бытия, свободное от каких либо условий (Бог, абсолютная личность). Абстракция (от лат. abstract...
6598. Авиационный двигатель и его производство 109.88 KB
  Авиационный двигатель и его производство Мировой опыт развития авиационного производства свидетельствует, что изготовление авиационных двигателей является наукоемким производством (НП). Авиадвигателестроение является одной из наиболее наукоемких отр...
6599. Характеристика наукоемкого производства. Характеристика наукоемкого производства авиационных двигателей 118.06 KB
  Характеристика наукоемкого производства Характеристика наукоемкого производства авиационных двигателей Изготовление наукоемкого объекта, имеющего высокие эксплуатационные параметры, очевидно, может быть осуществлено только в условиях наукоемкого про...