![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Метод потенціалів розв ' язування транспортної задач
Задача, двоїста до транспортної. Один із способів розв’язування транспортної задачі ґрунтується на розгляді двоїстої задачі. Розглянемо транспортну задачу (1-4). Позначимо змінні двоїстої задачі, які відповідають рівнянням (2), через Для побудови двоїстої задачі поставимо у відповідність обмеженням початкової задачі змінні двоїстої: Згідно з загальними правилами побудови двоїстих задач маємо: за умов Змінні Сформулюємо другу теорему двоїстості для задач (1-4) та (3)-(4). Для того, щоб плани відповідних спряжених задач були оптимальними, необхідно і достатньо, щоб виконувалися умови доповнюючої нежорсткості: 1) 2) Зауважимо, що друга група умов для транспортної задачі виконується автоматично, оскільки всі обмеження задачі є рівняннями. Перша умова виконується у двох випадках: а) якщо б) якщо Необхідність і достатність виконання таких умов для оптимальності планів прямої та двоїстої задач було доведено раніше. Отже, як наслідок другої теореми двоїстості для транспортної задачі отримали необхідні та достатні умови оптимальності плану. Теорема (умова оптимальностіопорного плану транспортної задачі). Якщо для деякого опорного 1) 2) для всіх Використовуючи наведені умови існування розв'язку транспортної задачі, методи побудови опорних планів та умову оптимальності опорного плану транспортної задачі, сформулюємо алгоритм методу потенціалів, який по суті повторює кроки алгоритму симплексного методу.
Алгоритм методу потенціалів складається з таких етапів: 1. Визначення типу транспортної задачі (відкрита чи закрита). За необхідності слід звести задачу до закритого типу. 2. Побудова першого опорного плану транспортної задачі одним з відомих методів. 3. Перевірка опорного плану задачі на виродженість. За необхідності вводять нульові постачання. 4. Перевірка плану транспортної задачі на оптимальність. 4.1. Визначення потенціалів для кожного рядка і стовпчика таблиці транспортної задачі. Потенціали опорного плану визначають із системи рівнянь 4.2. Перевірка виконання умови оптимальності для пустих клітин. За допомогою розрахованих потенціалів перевіряють умову оптимальності 4.3. Вибір змінної для введення в базис на наступному кроці. Загальне правило переходу від одного опорного плану до іншого полягає в тому, що з попереднього базису виводять певну змінну (вектор), а на її місце вводять іншу змінну (вектор), яка має покращити значення цільової функції. Аналогічна операція здійснюється і в алгоритмі методу потенціалів. Перехід від одного опорного плану до іншого виконують заповненням клітинки, для якої порушено умову оптимальності. Якщо таких клітинок кілька, то для заповнення вибирають таку, що має найбільше порушення, тобто 4.4. Побудова циклу і перехід до наступного опорного плану. Вибрана порожня клітина разом з іншими заповненими становить
Внаслідок наведеного правила вибору Доведемо ациклічність нового плану. Вектор умов, який відповідає приєднаній клітині, є лінійною комбінацією векторів базису, які утворюють разом з ним цикл, бо ці вектори входять у згадану комбінацію з відмінними від нуля коефіцієнтами. Виключення з циклу одного з базисних векторів приводить до нової системи з Отже, клітинка, що була вільною, стає заповненою, а відповідна клітинка з мінімальною величиною 5. Перевірка умови оптимальності наступного опорного плану. Якщо умова оптимальності виконується — маємо оптимальний план задачі, інакше необхідно перейти до наступного опорного плану (тобто повернутися до пункту 3 даного алгоритму). Зауважимо, що аналогічно з розв'язуванням загальної задачі лінійного програмування симплексним методом, якщо за перевірки оптимального плану транспортної задачі для деяких клітин виконується рівність Приклад 2.
|
||||||
Последнее изменение этой страницы: 2020-12-09; просмотров: 98; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.218.167.41 (0.009 с.) |