Лінійне програмування. Постановка задачі лінійного програмування

Лінійне програмування має вигляд лінійної математичної моделі, яка складається з трьох частин:

  1. Функції мети для якої знаходимо оптимальне значення

    Задача лінійного програмування

    де Задача лінійного програмування — апибуток від реалізації однієї i-ї продукції, а Задача лінійного програмування — кількість даної продукції. Якщо в (1) змінити знаки коефіццієнтів Задача лінійного програмуванняна протилежні, то функція Задача лінійного програмування змінюється на Задача лінійного програмування і навпаки.

  2. Обмеження по запасу ресурсів:

    Задача лінійного програмування

    де Задача лінійного програмування — нориа витрат i-го ресурсу; Задача лінійного програмування — кількість продукції j-го виду, випуск одиниці якої потребує Задача лінійного програмування витрат, також слід зазначити, що виличина Задача лінійного програмування не повинна бути від'ємною; Задача лінійного програмування — запаси i-го ресурсу; i=1,...,m — порядковий номер ресурсу; j=1,...,n — порядковий номер продукції.

  3. Читати повністю

Метод Гоморі (метод відсікаючих площин)

Метод відсікаючих площин існує у двох варіантах: перший варіант призначений для розв'язку повністю цілочисельних задач (перший алгоритм Гоморі) і другий варіант —  призначений для розв'язку частково цілочисельних задач (другий алгоритм Гоморі). Основна відмінність між ними полягає у способі формування відсікання.

Алгоритм знаходження розв'язку методом Гоморі для цілком цілочисельних задач нпступний:

  1. Лінійна задача розв'язується класичним симплекс-методом, без врахування цілочисельності змінних Алгоритм Гоморі. В результаті отримують деякий оптимальний опорний план, який має наступний вигляд:

    Алгоритм Гоморі

  2. Якщо (1) містить рівняння для яких базисниі змінні Алгоритм Гоморі мають дробові значення, то серед них обирають таке рівняння, яке має найбільшу дробову частину. Дане рівняння перетворюють у додаткову нерівність:

    Алгоритм Гоморі

    де Алгоритм Гоморі.

Для обрання чисел Алгоритм Гоморі та Алгоритм Гоморі існують наступні правила:

Читати повністю

Задача цілочисельного програмування. Математична модель та методи розв'язку задачі цілочисельного програмування

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

Цілочисельне програмування

де Цілочисельне програмування — цілі числа. Виходячи з (1) бачимо, що зовнішній вигляд задачі лінійного цілочисельного програмування практично не відрізняється від задачі лінійного програмування, за вийнятком того, що на розв'язок задачі лінійного програмування накладається додаткове обмеження: визначення лише цілих значень змінних. Припустимо, що ми розв'язали деяку задачу лінійного програмування, не враховуючи вимогу цілочисельності, і отримали наступний многокутник розв'язків ABCDО.

Читати повністю

Приклад знаходження дерева мінімальної вартості для орієнтованого графа за алгоритмом Дейкстри

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

Алгоритм Дейкстри

Слідуючи алгоритму, початковій вершині (вершина під номером 1) присвоюємо постійну мітку Алгоритм Дейкстри після чого переходимо до першого етапу.

Етап 1: з вершини 1 існує орієнтоване ребро до вершин 2, 4 і 5. Обчислимо для даних вершин відповідні мітки. В результаті отримаємо наступну таблицю.

Алгоритм Дейкстри

Читати повністю

Знаходження найкоротшого шляху в орієнтованому графі за алгоритмом Дейкстри

Алгоритм Дейкстри, на відміну від алгоритму Флойда з допомогою якого можна відшукати найкоротший маршрут між будь-якими двома вершинами графа, призначений для пошуку маршруту найкоротшої довжини від заданої вершини графа до всіх інших. В процесі виконання даного алгоритму при переході від вершини i до вершини j використовується спеціальна процедура, яка кожній вершині графа присвоює відповіду мітка.

Позначемо через Алгоритм Дейкстри найкоротша відстань від початкової вершини 1 до вершини i, через Алгоритм Дейкстри — довжину ребра (i, j). Тоді для вершини j мітка Алгоритм Дейкстри визначається наступним чином:

Алгоритм Дейкстри

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

Читати повністю

Приклад знаходження дерева мінімальної вартості для орієнтованого графа за алгоритмом Флойда

Нехай дано деякий граф, для якого потрібно знайти дерево мінімальної вартості.

Алгоритм Флойда

Для рішення даної проблеми використаємо алгоритм Флойда, з допомогою якого, за n етапів (n — кількість вершин графа),  можна відшукати найкоротший маршрут між будь-якими двома вершинами графа.

Перш ніж приступити до розв'язку, запишемо початкову матрицю відстаней Алгоритм Флойда та початкову матрицю вершин Алгоритм Флойда.

Алгоритм Флойда

Переходимо до 1-го  етапу: в матриці Алгоритм Флойда виділимо синім кольором ведучий рядок і колонку під номеромАлгоритм Флойда. Також, червоним кольором виділимо ті елементи матриці Алгоритм Флойда, значення яких можна покращити з допомогою трикутного оператора.

Читати повністю

Визначення найкоротшого шляху за алгоритмом Флойда

Основна ідея алгоритму Флойда полягає в наступному: нехай є три вершини графа i, j і k, які поєднані між собою ребрами заданої довжини.

Алгоритм Флойда

Трикутний оператор Флойда

Якщо виконується нерівність Алгоритм Флойда, то доцільно замінити маршрут від вершини i до  вершини k (Алгоритм Флойда) маршрутом Алгоритм Флойда. Така заміна (іншими словами трикутний оператор) виконується в процесі виконання алгоритму Флойда.

Алгоритм Флойда складається з n етапів (де n кількість вершин графа).

Етап 0: на даному етапі визначаємо початкову матрицю відстаней Алгоритм Флойда і матрицю послідовності вершин Алгоритм Флойда. Діагональні елементи обох матриць в обчисленні не беруть участь, тому позначаємо їх символом «-». Також на даному етапі покладають Алгоритм Флойда.

Читати повністю

« Попередня сторінкаНаступна сторінка »