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

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

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

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

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

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

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

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

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

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

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

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

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

Знаходження власних значень та власних векторів матриці методом вичерпування в середовищі delphi

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

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

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

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

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

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

Відшукання всіх власних значень симетричної матриці методом обертань в середовищі delphi

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

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

Більш детальну інформацію про знаходження власних значень матриці методом обертань можна знайти за посиланням Розв'язок повної проблеми власних значень методом обертань.

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

Знаходження власних значень матриці використовуючи метод обертань

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

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

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