Мітки: симплекс метод

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

Метод гілок і меж – один з комбінаторних методів. На відміну від методу Гоморі застосовується як до повністю, так і частково цілочисельних задач. Його суть полягає в упорядкованому переборі варіантів і розгляді лише тих з них, які виявляються за певними ознаками корисними для знаходження оптимального рішення.

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

Читати далі

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

Розглянемо приклад знаходження розв’язку задачі цілочисельного програмування використовуючи метод Гоморі. Отже, для виготовлення товару A і В підприємство використовує два види сировини. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару A та B, а також загальна кількість сировини наведені в наступній таблиці:

Таблиця даних задачі лінійного програмування

Таблиця даних задачі цілочисельного програмування

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

Читати далі

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

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

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

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

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

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

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

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

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

Читати далі

Графічний метод. Приклад розв’язання задачі лінійного програмування графічним методом

Для виготовлення товару A і B підприємство використовує три види сировини I, II, III. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару A, B а також загальна кількість сировини наведені в наступній таблиці:

510

Потрібно організувати випуск даної продукції таким чином, щоб прибуток від її реалізації був максимальним.

Позначимо через 28 — кількість товару виду А; 33 — кількість товару виду В. Тоді математична модель даної задачі полягає у визначенні максимального значення функції мети:

215

при обмеженнях:

68

46

Читати далі

Графічний метод розв’язання задачі лінійного програмування

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

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

На відміну від графічного методу, симплекс-метод є більш універсальним, тобто дозволяє знайти розв’язок будь-якої задачі лінійного програмування. При рішенні задачі симплексним методом, обчислення ведуться в таблицях. Рішення задачі даним методом дає не тільки оптимальне рішення, але і рішення двоїстої задачі, залишки ресурсів і тому подібне.

Читати далі