Знаходження розв'язку задачі дробово-лінійного програмування шляхом зведення її до задачі лінійного програмування

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

при наступних обмеженнях:

Крім того, передбачається, що в області невід'ємних розв'язків системи рівнянь (2) має місце нерівність .

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

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

Розв'язок системи лінійних рівнянь методом підстановки в середовищі програмування delphi

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

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

Головне вікно delphi-проекту практично не відрізняється від проектів, які реалізують інші чисельні методи рішення задач такого типу (Розв'язок однорідних систем в середовищі програмування delphi, Розв'язок СЛАР методом Крамера на delphi, Розв'язок СЛАР методом Жордана-Гаусса на delphi та інші), лише з однією відмінністю. Виходячи з того, що програма призначена для знаходження розв'язку двох лінійних рівнянь з двома невідомим, то розмірність матриці коефіцієнтів, а відповідно і стовпця вільних членів, задавати не потрібно.

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

Розв'язок системи двох лінійних рівнянь з двома невідомими методом підстановки

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

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

Для того щоб розв'язати дану систему методом підстановки будемо слідувати простому алгоритму:

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

Розв'язок задачі комівояжера методом Монте-Карло в середовищі програмування delphi

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

Отже, після запуску проекту, на екрані появиться форма наступного вигляду:

Головне вікно проекту "Розв'язок задачі комівояжера методом Монте-Карло"

Головне вікно проекту "Розв'язок задачі комівояжера методом Монте-Карло"

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

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

Рішення задачі комівояжера методом Монте-Карло

Методами Монте-Карло називать будь-яку статистичну процедуру, яка використовує статистичну вибірку. Сьогодні застосуємо дану процедуру, для знаходження розв'язку задачі комівояжера. Для цього припустимо, що у задачі комівояжер повинен проїхати міст, і побудувати свій маршрут таким чином, щоб побувати у кожному місті по одному разу і повернутися у початкове. Відмітимо, що, при цьому, витрати на переміщення між містами повинні бути мінімальними.

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

Зауваження: у середовищі програмування delphi, яке ми зазвичай використовуємо для програмної реалізації розглядуваних на даному сайті алгоритмів та методів, існує стандартна функція Random, яка дозволяє програмно формувати випадкові числа. Фактично ця та аналогічні функції в інших мовах програмування є датчиками випадкових чисел.

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