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


 

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

14269. Изменение эстетики кино с приходом звука 15.18 KB
  Изменение эстетики кино с приходом звука. Когда Эдисон в 1887 году построил свой кинескоп он имел в виду показать только смену кинокадров параллельно с чередованием звуков которые воспроизводились на изобретенном им ранее кинетофоне фонографе. Первые демонстрации нем
14270. Знайомство з Оперою 30 KB
  План конспект уроку з музики проведеного у 3А класі. Тема уроку: €œЗнайомство з Оперою€ Слухання: Семен ГулакАртемовський. Опера €œзапорожець за Дунаєм€ €œДует Одарки і Карася€ Спів нової пісні €œНа сонячній планеті€ Ме
14271. Подготовка к практике. Примеры развлечений с детьми 62 KB
  Подготовка к практике Примеры развлечений с детьми Развлечение с детьми младшего дошкольного возраста Тема:Птичьи голоса Программное содержание: развитие у детей музыкального восприятия творческого воображения; формирование музыкально-ритмических...
14272. Работа над художественным материалом в начальный период обучения 15.98 KB
  Работа над художественным материалом в начальный период обучения. В Педагогической практике работа над произведением принимает самые разнообразные формы в зависимости от личных качеств учащегося степени их одаренности и музыкального развития. Работа над произве...
14273. Рахманинов Сергей Васильевич (1873-1943) - композитор, пианист, дирижёр 251 KB
  Рахманинов Сергей Васильевич 18731943 композитор пианист дирижёр. Родился Рахманинов в дворянской семье в Старорусском уезде Новгородской губернии в имении Онег 20 марта 1873 г. История рода Рахманинова уходит корнями к внуку молдавского царя Стефана Вел
14274. Сказа́ние о неви́димом гра́де Ки́теже и деве Февро́нии 18.75 KB
  Сказа́ние о неви́димом гра́де Ки́теже и деве Февро́нии опера русского композитора Николая Андреевича РимскогоКорсакова. В опере четыре действия шесть картин. Основой сюжета стала легенда конца XVIII века о граде Китеже. РимскийКорсаков приступил к написанию музык
14275. Физика и музыка 371.5 KB
  Содержание Что называется высотой тона Что называется мажорной диатонической гаммой Что называется музыкальным интервалом Для чего служат черные клавиши на рояле и в органах Что называется равномерно темперированной гаммой Какова стандартная высота...
14276. Музыка в детских праздниках и представлениях 137.5 KB
  Реферат Музыка в детских праздниках и представлениях СОДЕРЖАНИЕ: ВВЕДЕНИЕ Роль праздников в развитии и воспитании детей. Значение и роль праздника. Построение праздника. Характеристика основных видов зрелищ для детей раннего возраста. М...
14277. Воздействие звука на человека 139.66 KB
  Воздействие звука на человека Что такое звук Звук представляет собой определенную вибрацию волну или энергию в пространстве. Вся Вселенная была создана Звуком. Согласно Библии: Вначале было Слово при помощи которого Бог творил нашу Вселенную. В индийской философи...