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

Графічний метод розв'язання задач цілочисельного програмування, як і для випадку задачі лінійного програмування, має обмежену область застосування, бо зазвичай використовується для задач з двома змінними. Тобто, кожна з нерівностей в системі обмежень задач такого типу, визначає на координатній площині graficnuj_metod_cp_delphi3 деяку півплощину, а система нерівностей в цілому — перетин відповідних півплощин. Сукупність точок перетину даних півплощин називається областю допустимих рішень або багатокутником розв'язків. Даний багатокутник завжди являє собою опуклу фігуру, тобто має наступну властивість: якщо дві точки graficnuj_metod_cp_delphi4 і graficnuj_metod_cp_delphi5 належать цій фігурі, то і весь відрізок graficnuj_metod_cp_delphi6 належить їй.

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

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

Перевірка приналежності точки багатокутнику

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

З'ясувати приалежність точки стороні багатокутника доволі просто, скориставшись алгоритмом приналежності точки відрізку: якщо точка Метод трасування променя належить відрізку з координатами metod_trasyvannja_promenja2 та metod_trasyvannja_promenja3, то повинна виконуватись наступна рівність:

metod_trasyvannja_promenja4

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

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

Знаходження точки перетину двох прямих заданих двома точками

Нехай маємо дві прямі задані точками свого початку та кінця (перша пряма задана точками Точка перетину двох прямих таline_intersection2 і друга — line_intersection3 та line_intersection4 відповідно), для яких необхідно визначити координати точки їх перетину. Очевидне рішення даної задачі полягає в тому, щоб вирішити систему з двох лінійних рівнянь, які описують задані прямі.

Отже, якщо задані дві точки Точка перетину двох прямих і line_intersection2, то з курсу аналітичної геометрії відомо, що рівняння прямої, яке проходить через ці точки, можна записати у наступному вигляді:

line_intersection6

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

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