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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Чисельне інтегрування довільної функції методом прямокутників

Розглянемо ще одну delphi-програму, яка знаходить наближений розв'язок визначеного інтеграла, використовуючи для цього метод прямокутників. Основна ідея даного методу полягає в тому, що сума площ прямокутників, якими можна замінити функцію на відрізку [a; b], наближається до площі під функцією. Чим менше довжина відрізків, на які ділиться відрізок функції, тим точніше значення шуканого інтеграла.

Інтерфейс користувача програми обчислення визначеного інтеграла методом прямокутників є доволі простим і зрозумілим. Він розроблений таким чином , що будь-який користувач ПК зумів самостійно і швидко розібратися з програмою. Більшу частину головного вікна займає область, відведена на графічні зображення.

Інтерфейс програми, яка реалізує метод прямокутників

Інтерфейс програми, яка реалізує метод прямокутників

Користувач вводить в програму підінтегральну функцію, кількість відрізків на які ділиться проміжок [a; b] і межі інтегрування, після чого натискає кнопку «Обчислити інтеграл». В результаті програма обчислює інтеграл методом прямокутників, а також будує відповідний графік, використовуючи компонента TImage.

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

Чисельне інтегрування довільної функції методом трапецій

Обчислення значення деякого інтеграла, як правило наближене, зводиться до обчислення прлощі криволінійної фігури обмеженлї віссю абсцис, графіком підінтегральної функції і відрізками прямих x=a і x=b (де a, b — межі інтегрування). Для знаходження шуканої площі скористаємось методом трапецій, а саме delphi-програмою, яка реалізує даний метод.

Програма розуміє круглі дужки, знаки арифметичних операцій * + — /, знак піднесення до степені ^ і наступні математичні функції: Abs(), Sqr(), Sqrt(), Exp(), Ln(), Sin(), Cos(), Tan(), ArcTan().

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

Інтерфейс програми, яка обчислює значення визначеного інтеграла методом трапецій

Інтерфейс програми, яка обчислює значення визначеного інтеграла методом трапецій

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

Програма апроксимації таблично заданої функції методом найменших квадратів

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

Інтерфейс програми "Апроксимація функції методом найменших квадратів"

Інтерфейс програми "Апроксимація функції методом найменших квадратів"

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

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

Рівномірне наближення функцій методом найменших квадратів

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

Будемо вважати, що емпірична формула являє собою многочлен степені m (де m<n):

Апроксимація функції методом найменших квадратів

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

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

Наступна сторінка »