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


 

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

8165. Вступ. Загальне поняття про предмет Людина і світ 58 KB
  Вступ. Загальне поняття про предмет Людина і світ Мета уроку: Розкрити основні завдання вивчення курсу Людина і світ і сформувати уявлення про роль людинознавчого курсу в здійсненні світоглядного самовизначення людини розкрити зміст співвідношення ...
8166. Ціннісні виміри людського життя. Смерть і безсмертя 29.5 KB
  Тема уроку. Ціннісні виміри людського життя. Смерть і безсмертя. Мета:сформувати уявлення учнів про цінності та їх роль у житті людини ознайомити учнів з основними аспектами проблеми смерті та безсмертя як фінальних цінностей людини формуват...
8167. Почуття, інтелект, воля. Ідеали в житті людини 44 KB
  Почуття, інтелект, воля. Ідеали в житті людини. Мета: Розглянути поняття почуття, інтелект, воля, та проаналізувати ідеали в житті людини розвивати вміння критично аналізувати різні точки зору на певну проблему виховувати толерантне ставлення до п...
8168. Завершення І світової війни 33 KB
  Завершення І світової війни. Хоч головні битви розгорталися в 1918 р. на Західному фронті, історія розпорядилася так, що не вони завершили війну, а події на Східному фронті. Упродовж двох років у північній частині Греції англо-французькі війська без...
8169. Особа, суспільство, держава 31 KB
  Тема уроку. Особа, суспільство, держава. Мета: Навчити ліцеїстів розрізняти поняття людина, індивід, особистість, особа, громадянин. розвивати вміння висловлювати власне ставлення до проблеми виховувати почуття правової свідомості. Обладнання...
8170. Громадянство. Правова і соціальна держава 27 KB
  Тема уроку. Громадянство. Правова і соціальна держава. Мета уроку: визначити поняття громадянство, правова і соціальна держава розвивати вміння висловлювати власне ставлення до проблеми виховувати почуття правової свідомості. Обладнання: Дош...
8171. Культура Гетьманщини 15.54 KB
  Культура Гетьманщини 1648 pp. - період гетьманської держави, її очолюють високоосвічені, європейського рівня політичні й громадські діячі: П. Сагайдачний, Б. Хмельницький, І. Виговський, І. Мазепа. Вони докладають великих зусиль і кош...
8172. Феофан Прокопович - видатний діяч просвітництва і культури 15.29 KB
  Феофан Прокопович - видатний діяч просвітництва і культури Феофан Прокопович народився в Києві 1677 р. Рано втратив рідних, жив під опікою дядька, професора і ректора Києво-Могилянської академії. Дядько рано віддав хлопчика на навчання до Акаде...
8173. Козацькі Літописи 18.81 KB
  Козацькі Літописи Історії Запорозької Січі присвячено численні розвідки - від суто популяризаторських до капітальних праць. Різними дослідниками це явище висвітлюється по-різному: і як цілісний процес, і як окремі його складові чи персонали. Пр...