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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

510

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

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

215

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

68

46

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

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

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

Розглянемо задачу лінійного програмування:

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

214

37

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

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

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

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

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

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

Програмна реалізація Симплекс методу на Delphi

Програма виконаний в середовищі Delphi 7 і призначена для розв'язання задачі лінійного програмування за симплекс методом. Отже, розглянемо конкретний приклад задачі такого типу, і спробуємо розв'язати її з допомогою даної програми.

Нехай потрібно знайти максимальне значення функції мети 112 при обмеженнях:

22

Запишемо систему обмежень у канонічній формі і побудуємо початкову симплекс таблицю:

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

Розв'язок задачі лінійного програмування методом штучного базису

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

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

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

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