Задача про рюкзак. Математична модель задачі про рюкзак

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

Ілюстрація задачі про ранець

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

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

Побудов кривої Безьє в середовищі програмування delphi

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

Головне вікно проекту "Побудова кривої Безьє"

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

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

Криві Безьє. Основні поняття та властивості кривих Безьє

Векторні зображення складаються з контурів. Контури складаються із сегментів, обмежених вузлами. З декількох таких сегментів можна скласти, практично, будь-яку фігуру. Для опису контурів у програмах векторної графіки застосовують розроблені французьким математиком П'єром Безьє параметричні поліноміальні криві. Відмітимо, що криві та поверхні Безьє були використані у шістдесятих роках компанією «Рено» для комп'ютерного проектування форми кузовів автомобілів. На сьогодні вони широко використовуються в комп'ютерній графіці, автоматизованих системах управління виробництвом тощо. Квадратичні криві Безьє використовуються в шрифтах TrueType.

За заданим масивом вершин крива Безьє степеня визначається за формулою:

де  — базисні функції кривої Безьє, також відомі як поліноми Берштейна, .

На рисунку що міститься нижче, зображено графіки вагових коефіцієнтів  кривої Безьє при .

Вагові функції Безьє-Берштейна при m = 3

Зауваження: деякі з властивостей поліномів Берштейна суттєво впливають на поведінку кривих Безьє. Наведемо основні з них: многочлени Бернштейна набувають невід'ємних значень; в сумі многочлени Берштейна дають одиницю, тобто для них виконується умова (2); поліноми Берштейна не залежать від вершин масиву , а залежать лише від кількості точок у ньому.

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