Розв'язок задачі цілочисельного програмування графічним методом в середовищі Delphi
Графічний метод розв'язання задач цілочисельного програмування, як і для випадку задачі лінійного програмування, має обмежену область застосування, бо зазвичай використовується для задач з двома змінними. Тобто, кожна з нерівностей в системі обмежень задач такого типу, визначає на координатній площині 
деяку півплощину, а система нерівностей в цілому — перетин відповідних півплощин. Сукупність точок перетину даних півплощин називається областю допустимих рішень або багатокутником розв'язків. Даний багатокутник завжди являє собою опуклу фігуру, тобто має наступну властивість: якщо дві точки 
і 
належать цій фігурі, то і весь відрізок 
належить їй.
Розглянемо задачу цілочисельного програмування, та спробуємо розв'язати її використовуючи delphi-програму, яка реалізує даний метод. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару а також загальна кількість сировини наведені в наступній таблиці:
Перевірка приналежності точки багатокутнику
Припустимо, що нам необхідно, для деякої точки 
визначити, чи належить вона багатокутнику, чи лежить поза його межами (відмітимо, що точка належить багатокутнику, коли вона міститься на одній з його сторін або в його середині).
З'ясувати приалежність точки стороні багатокутника доволі просто, скориставшись алгоритмом приналежності точки відрізку: якщо точка належить відрізку з координатами 
та 
, то повинна виконуватись наступна рівність:
Для визначення приналежності точки середині багатокутника скористаємось одним із стандартних методів, а саме: проведемо з даної точки пряму, паралельну осі 
і підраховуємо, скільки сторін даного багатокутника вона перетинає. Якщо в результаті підрахунку було отримано непарну кількість сторін, то точка 
міститься в середині багатокутника, якщо парна кількість або нуль — то точка міститься за його межами.
Знаходження точки перетину двох прямих заданих двома точками
Нехай маємо дві прямі задані точками свого початку та кінця (перша пряма задана точками 
та
і друга — 
та 
відповідно), для яких необхідно визначити координати точки їх перетину. Очевидне рішення даної задачі полягає в тому, щоб вирішити систему з двох лінійних рівнянь, які описують задані прямі.
Отже, якщо задані дві точки і , то з курсу аналітичної геометрії відомо, що рівняння прямої, яке проходить через ці точки, можна записати у наступному вигляді:
Отриманий вираз слід перетворити до вигляду загального рівняння прямої: 
. Для цього, звільнимо рівняння (1) від дробів, розкриємо дужки та згрупуємо доданки при невідомих.
Загрузка ...