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


 

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

48260. Феномен університетської освіти у історичному вимірі 945.5 KB
  В XI столітті XII столітті були засновані: Болонський університет 1088 Болонський університет найстаріший університет Європи в місті Болонья Північна Італія заснований в 1088 році як юридичний навчальний заклад. Заснований Університет Історія 9 століття Салерно Італія Медичний факультет; статус університету під сумнівом кінець 11 століття Болонья Італія Точна дата заснування не відома; офіційний рік заснування 1088; В кінці 11 століття існувала школа права; поступовий розвиток в університет 13 століття Заснований Університет...
48261. Літературознавство як наука 224 KB
  Автор будьякого художнього твору завжди репрезентує певний культурний прошарок своєї доби спостерігаючи яку беручи участь в її житті він водночас представляє певний ідеологічний або політичний напрям. Щоб розібратися в задумі письменника в політичній спрямованості його твору чи творчості треба знати основні факти біографії митця його зв'язки з іншими людьми участь у політичному і громадському житті. Вужчим за науковим обсягом вважаються так звані допоміжні галузі літературознавства бібліографія археологія текстологія методика...
48262. Уголовно-процессуальное право 108.76 KB
  Структурно уголовно-процессуальное право распадается на части; Общую и Особенную. Деление это носит двойственный характер. С одной стороны, оно отражает специфику структуры Уголовно-процессуального кодекса, что уже понятия уголовно-процессуального права. С другой стороны, такая дифференциация оправдана методологически.
48264. ПРЕДМЕТ І ЗАВДАННЯ ЕПІЗООТОЛОГІЇ 4.42 MB
  Епізоотологія наука яка вивчає об'єктивні закономірності процесів виникнення розвитку поширення і згасання інфекційних хвороб тварин та на основі пізнання загальних закономірностей а також сучасних даних суміжних наук розробляє раціональні заходи профілактики і ліквідації епізоотій. Назва науки Епізоотологія як вчення про заразні захворювання сільськогосподарських і диких тварин птахів риб бджіл складається з трьох грецьких слів: ері на zoon тварина і logos вчення. Тобто мова йде про значне ураження тварин...
48265. Редагування як вид професійної діяльності і складова редакційно-видавничого процесу 256 KB
  Редагування як вид професійної діяльності і складова редакційновидавничого процесу. План Предмет і завдання курсу Загальне редагування. Зміст поняття редагування.
48266. ЕКОНОМІЧНА ІНФОРМАЦІЯ І ЗАСОБИ ЇЇ ФОРМАЛІЗОВАНОГО ОПИСУ 186 KB
  ЕКОНОМІЧНА ІНФОРМАЦІЯ І ЗАСОБИ ЇЇ ФОРМАЛІЗОВАНОГО ОПИСУ Економiчна інформація ЕКІ це послiдовнiсть повiдомлень економiчного змiсту що можуть бути введенi вiдображенi збереженi обробленi переданi та загалом використанi для прийняття управлiнських рiшень на рiвнi окремих установ чи структурних одиниць так i економiки в цiлому. Економiчна інформація ЕКІ один з найбiльш масових рiзновидiв iнформацiї що вiдображає процеси виробництва розподiлу обмiну i споживання матерiальних благ та послуг. Види ЕКІ Вiдповiдно до виконуваних...
48267. Бюджетний механізм, його призначення та структура, роль в регулюванні соціально-економічних процесів у державі 45 KB
  Бюджетний механізм його призначення та структура роль в регулюванні соціальноекономічних процесів у державі. Бюджетний механізм може бути охарактеризований як комплекс спеціально розроблених і законодавчо закріплених у державі форм і методів створення і використання фінансових ресурсів для регулювання економічних і соціальних процесів. В економічній літературі відсутня єдина думка щодо визначення поняття фінансовий механізм . У працях провідних західних учених фінансовий механізм не вивчається як окремий об'єкт але всебічно досліджуються...
48268. Використання природи як засобу виховання в історії російської педагогіки 69.5 KB
  Мукачево 2011 Тема: Використання природи як засобу виховання в історії російської педагогіки. Концепція національного виховання “Освітаâ€. Теорія національного виховання.