Головна

Стандартний алгоритм симплекс-методу

  1. HSR: алгоритм сортування по глибині
  2. L1-L2, L2-L1 закони. ART1 алгоритм.
  3. А) Основні алгоритмічні конструкції. Базові алгоритми.
  4. адитивний алгоритм
  5. АЛГЕБРА многочленів. Найбільший спільний дільник двох многочленів (алгоритм Евкліда).
  6. алгоритм

1. Для поточного базисного плану наводиться критерій оптимальності: якщо в рядку оцінок немає позитивного коеф. , План і завдання виконане.

2. Якщо серед  , ...,  є> 0, план можна поліпшити за рахунок введення в числі базисних тієї вільної змінної, для якої оцінка макс.

3. Для визначення змінної, яку слід внести з числа базисно, потрібно переглянути стовпець матриці A, соотв. включеної в базис нової змінної. Якщо всі елементи цього стовпчика <= 0, то завдання рішення не має. Якщо є елементи> то вибирається той, для якого величина /  - Min. Тим самим визначається базис змін., Виведенн з матриці.

4. Стовпець з провідним елементом приводиться до вигляду, в якому ведучий елемент дорівнює 1, решта - неизм.

5. Кроки 1-4 повторюють до тих пір, поки не буде отримано оптимальне рішення.


Табличний метод вирішення транспортної задачі. Використання циклів перерахунків і методу потенціалів при пошуку оптимального плану перевезень. Достатня умова оптимальності

Табличний метод вирішення транспортної задачі

 є n постачальників і m споживачів однорідного продукту, наприклад, друкарської фарби. відомі вартості Cij перевезення одиниці продукту від i-го постачальника до j-му споживачеві. нехай Ai - Кількість продукту, що є у i-го постачальника, а Bj - Кількість продукту, необхідне j-му споживачеві. Завдання формулюється так: визначити, яка кількість Xij продукту потрібно перевезти від i-го постачальника до j-му споживачеві (i = 1,2, ..., n; j = 1,2, ..., m), Щоб загальна вартість перевезення L була мінімальною

і при цьому були виконані умови


Для знаходження початкового плану перевезень (будь-якого допустимого рішення) і подальшого поліпшення цього плану розроблений табличний метод, Який полягає в наступному.

Будується таблиця, що складається з m + 1-го рядка і n + 1-го стовпчика (по числу m споживачів і n постачальників). У правий крайній стовпець заносяться числа B1, B2, ..., Bm, А в нижній рядок числа A1, A2, ..., An.

Після цього починають заповнювати таблицю числами так, щоб їх сума в кожному рядку виявилася дорівнює відповідному значенню B, А сума по кожному колонку - відповідному значенню A. Кожна клітина таблиці відповідає однієї змінної Xij, Перший індекс якої відповідає номеру рядка, а другий - номеру стовпчика.

Деякі з клітин таблиці можуть залишатися порожніми - вони відповідають нульових значень змінних Xij. Будемо називати такі клітини і відповідні їм змінні небазисними, а заповнені клітини і відповідні їм змінні - базисними.

Існує простий спосіб побудови початкового плану перевезень. Він отримав назву методу північно-західного кута, Оскільки заповнення таблиці починається з лівого верхнього її кута. У цю клітку заноситься менше з чисел A1, B1. якщо B1 < A1, То це означає, що потреби першого споживача можна повністю задовольнити за рахунок запасів першого постачальника, в цьому випадку в перший рядок нічого вносити більше не треба і переходять до другої рядку. В іншому випадку в першу клітку заноситься число A1, Тобто першому споживачеві передаються всі запаси першого постачальника, але, оскільки їх потреба в продукті у споживача залишається, то заповнюється друга клітина в цьому рядку - використовуються запаси другого постачальника, потім третя і так до тих пір, поки потреби першого споживача не будуть задоволені повністю. Після цього починають заповнювати другий рядок, також рухаючись по ній зліва направо.

В результаті виконання зазначеної процедури в таблиці виявляються заповненими r = m+n-1 Клітина, і відповідні базисні змінні отримають деякі значення. При цьому автоматично будуть задоволені умови задачі: весь продукт, наявний у постачальників, буде розподілений між споживачами, при цьому кожен з них отримає рівно стільки, скільки йому потрібно.

Щоб поліпшити план, потрібно перейти до нового базисного рішення, аналогічно тому, як це робиться в симплекс-методі. Для цього потрібно змінити таблицю так, щоб одна з базисних клітин виявилася порожньою (тобто з нульовим значенням), а одна з порожніх (небазисних) отримала позитивне значення (стала базисною), При цьому, зрозуміло, суми по рядках і стовпцях таблиця повинні залишитися колишніми, оскільки ця умова допустимості будь-якого рішення.

Використання циклів перерахунків і методу потенціалів при пошуку оптимального плану перевезень

Перейти до нового базисного рішення можна за допомогою так званого циклу перерахунку.

циклом перерахунку називається ланцюжок клітин таблиці перевезень, які відповідають таким умовам:

· Одна з клітин в цьому ланцюжку вільна, інші - заповнені числами;

· Кожні дві сусідні клітини в ланцюжку знаходяться або в одному рядку, або в одному стовпці;

· Ніякі три сусідні клітини, що входять в ланцюжок, не можуть перебувати в одному рядку або в стовпці;

· Якщо кожні дві сусідні клітини ланцюжка з'єднати відрізком прямої, так, щоб вийшов замкнутий контур з ламаних ліній, то одна вершина цього контуру буде перебувати у вільному клітці таблиці, інші - в заповнених, тобто в базисних.

Таких ланцюжків можна побудувати стільки, скільки є в таблиці вільних (небазисних) клітин. Побудувавши такий ланцюжок, можна здійснити перехід до іншого набору базисних клітин за допомогою такої процедури:

1) послідовність клітин в ланцюжку позначається чергуються знаками + і -, при цьому вільна клітина позначається знаком плюс;

2) серед клітин, помічених знаком мінус, відшукується та, в якій записана найменша величина, ця величина потім додається до числам в клітинах, позначених знаком плюс і віднімається з чисел в клітинах, позначених знаком мінус.

В результаті такого циклічного переміщення буде отриманий інший набір базисних клітин і при цьому сума чисел в кожному рядку і в кожному стовпці залишаться колишніми.

Забезпечити цілеспрямований перебір можливих базисних рішень, який призводить до зменшення цільової функції при переході до нового базису, дозволяє метод потенціалів, Які ось у чому.

введемо n допоміжних змінних ai, i = 1,2, ..., n и m змінних bj, j = 1,2, ..., m і розглянемо систему рівнянь:

a i + b j = С i j,

де Сij - Ті елементи матриці вартостей, значення індексів i и j яких відповідають номерам рядків і стовпців матриці перевезень, на перетині яких знаходяться базисні клітини. Оскільки на кожному рядку і в кожному стовпці матриці перевезень є хоча б одна базисна клітина, в систему рівнянь увійдуть всі введені вище допоміжні змінні.

Число базисних клітин одно n + m -1. Таким чином, число рівнянь на одиницю менше числа невідомих. Якщо однією з невідомої довільно задати деяке значення, наприклад, покласти a1 = 0, то інші визначаються однозначно.

знайдені значення a1, a2, ..., a n и b1, b2, ...,b m називаються потенціалами. введемо матрицю C таку, що Cij =a i + b j, (i = 1,2, ..., n и j = 1,2, ..., m). Її називають матрицею фіктивних вартостей. Очевидно, що для тих значень індексів i и j, Які відповідають базисним змінним Xij, Елементи фіктивної та вихідної матриць вартостей збігаються, для інших значень індексів вони можуть відрізнятися.

Матриця фіктивних вартостей, побудована для деякого набору базисних клітин таблиці перевезень, дозволяє визначити, чи є поточний набір базисних змінних оптимальним і якщо ні, то яку з небазисних змінних слід включити в число базисних, щоб отримати кращий план, з меншим значенням цільової функції. Для цього складається матриця різниць між істинною і фіктивної матрицями вартостей:

DCij = Cij -Ci j = Cij - (a i + b j).

Якщо все DCij ? 0, то поточний план перевезень оптимальний. Якщо серед DCij є негативні, то план можна поліпшити. нехай DCpq - Найбільший по абсолютній величині негативний елемент, тоді вибравши змінну X pq в як кандидат на включення в число базисних і виконавши для неї цикл перерахунку, можна отримати новий план перевезень з меншим значенням цільової функції.




Розділ 5. Автоматизоване управління поліграфічним виробництвом | Інформаційне забезпечення систем управління. Фактографічні бази даних. Типи СУБД і їх характеристики

Методика розрахунку параметрів лазерних вивідних пристроїв, определ швидкість сканування | Структура, призначення та принцип роботи проявних машин. Основні системи автоматизації процесів обробки фотоматеріалів | Технічні засоби аналізу і введення зображення в систему додрукарської обробки | джерела світла | Структурна схема, призначення та принцип роботи формовиводного пристрої (рекордера) | Структурна схема формовиводного пристрою. | Основні етапи і характеристики електрофотографічних процесу кольоровий електрофотографії. Структурна схема, призначення пристроїв і принцип роботи апарату кольоровий електрографія | Принцип роботи, призначення і різновиди струменевих принтерів | Структурна схема, призначення пристроїв і принцип роботи лазерного фотоскладального автомата | Цифрові друкарські машини (ЦПМ). Основні типи ЦПМ і принцип роботи |

© um.co.ua - учбові матеріали та реферати