Знаходження оптимального числа листів фанери і вирізання потрібного числа заготовок при мінімальних відходах

Знаходження оптимального числа листів фанери і вирізання потрібного числа заготовок при мінімальних відходах

Вступ Завдання на виконання:

Зі стандартних листів фанери необхідно вирізати заготовки трьох типів у кількості, що відповідно дорівнює 24, 31 і 18 штук. Кожен лист фанери може бути розрізаний двома способами. Кількість заготовок і величина відходів матеріалу, які можна отримати при даному способі розкрою, наведені в табл. 1.

Таблиця 1:

1. Математична модель задачі

12Х1+ 16X2 -> min

2Х1+6Х2 >= 24

5Х1+ 4Х2 >= 31

2Х1+ 3Х2 >=18

Хі >= 0 (i=1,2)

Хі — ціле.

2. Обґрунтування вибору методу розв’язання задачі

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

Існує два методи рішення задач цілочисельного лінійного програмування:

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

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

Для вирішення цієї задачі в рамках курсового проекту використаємо алгоритм Гоморі.

3. Алгоритм розв’язання задачі (Алгоритм Гоморі)

1. Симплекс методом вирішуємо задачу:

— визначаємо індексний рядок:

— вибір розв’язального стовпчика:

При ц.ф. max, якщо всі, то рішення пункту знайдено;

При ц.ф. min, якщо всі, то рішення пункту знайдено;

— вибір розв’язального рядка і визначення розв’язального елемента:

Якщо всі, то задача не має рішення і є необмеженою;

У розв’язальному рядку записується:

У розв’язальному стовпчику записується:, для всіх r, крім r=i,

Для всіх інших елементів, крім r=i та k=j, використовується правило прямокутника:

l — номер ітерації;

— перераховуємо таблиці.

Якщо отриманий оптимальний результат є цілочисельним, тоді рішення задачі знайдено.

2. Нехай серед координат отриманого оптимального рішення є не цілі числа. Оберемо серед цих змінних ту, яка має найбільшу дробову частину: x_s=b_s. Цій змінній відповідає якийсь рядок. Для цього рядка справедлива рівність:

.

Рівняння:

буде додаватись в останню симплекс таблицю для продовження рішення. Змінна U_i буде (n+1) змінною і буде братися в якості базисної, для неї буде вводитись додатковий стовпчик.

3. Двоїстим симплекс методом вирішується отримана задача:

— від'ємне дробове число визначає вектор, який виводиться з базису. Вектор, який вводиться в базис обчислюється за формулою:

— відносно розв’язального елементу перераховується симплекс таблиця.

Якщо в результаті рішення отримаємо цілі значення, то рішення задачі знайдено. В противному випадку робимо 2 та 3 пункти.

Для розв’язання задачі використовуємо комп’ютерний математичний пакет: MathCAD та табличний процесор MS Exel.

4. Розв’язання задачі вручну

За умовою задачі ми склали математичну модель задачі. Приводимо задачу до канонічного виду:

12×1+ 16×2+ x3+ x4+ x5 -> min

2x₁ + 6x₂-1x₃ + 0x₄ + 0x₅ = 24

5x₁ + 4x₂ + 0x₃-1x₄ + 0x₅ = 31

2x₁ + 3x₂ + 0x₃ + 0x₄-1x₅ = 18

Хі >= 0 (i=1,3) Хі — ціле.

Зведемо завдання до знаходження максимуму. Для цього помножимо всі рядки на (-1) і шукатимемо опорний план.

— 2x₁-6x₂ + 1x₃ + 0x₄ + 0x₅ = -24

— 5x₁-4x₂ + 0x₃ + 1x₄ + 0x₅ = -31

— 2x₁-3x₂ + 0x₃ + 0x₄ + 1x₅ = -18

Опорний план:

X1 = (0,0,-24,-31,-18)

Визначаємо роз’вязальні рядок і стовпець.

На перетині роз’вязальних рядка і стовпця знаходиться роз’вязальний елемент, рівний (-4)

У базисному стовпці всі елементи додатні.

Переходимо до основного алгоритму симплекс-методу.

Поточний опорний план неоптимальний, оскільки в індексному рядку знаходяться від'ємні коефіцієнти.

Як роз’вязальний виберемо стовпець, відповідний змінній x1, оскільки це найбільший коефіцієнт по модулю.

Обчислимо значення Di по рядках як частку від ділення: b_i / a_i1

і з них выберемо найменше:

min (22¹/₂: 5¹/₂, 7³/₄: 1¹/₄, 5¹/₄: 1³/₄) = 3

Отже, 3-тій рядок є роз’вязальний .

Роз’вязальний елемент рівний (1³/₄) знаходиться на пересіченні роз’вязального стовпця і роз’вязального рядка.

Отримуємо нову симплекс-таблицю:

Кінець ітерацій: індексний рядок не містить від'ємних елементів — знайдений оптимальний план Остаточний варіант симплекс-таблиці:

Оптимальний план можна записати так:

x₃ = 6

x₂ = 4

x₁ = 3

F (X) = 0*6 + 16*4 + 12*3 = 100

5. Аналіз результатів роботи в програмі MathCAD

Для свого вирішення задачі використаємо функцію:

Minimize (f, var1, var2, …) повертає значення var1, var2, які задовольняють обмеження вирішують блок і, які змушують function f набути його найменшого значення.

Аргументи: var1, var2 … прості змінні

f — функція, визначена вище, вирішують блок. Наприклад, г аргументу міг послатися на function г (x, y) :=x/y.

Використання функціЇ:

1. Визначте функцію, щоб мінімізувати.

2. Визначте значення припущення для змінних, що вирішуються.

3. Надрукуйте слово Given, що означає умова завдання.

4. Внизу Given, type рівності і нерівності, які служать обмеженнями, використовуючи логічні оператори.

5. Введіть функцію Мінімізувати з відповідними аргументами.

Примітки:

· Ці функції повертають скаляр, коли лише одна змінна включена. Інакше вони повертають вектор.

· Якщо немає жодних обмежень слово Given не необхідне.

Вводимо вхідні дані та отримаємо наступний результат:

Вектор Р відображає значення шуканих мінних. Отже, х1=3, х2=4.

Знайдений результат відповідає результату, обчисленому вручну. Задача вирішена

Висновок

Mathcad — система комп’ютерної алгебри з класу систем автоматизованого проектування, орієнтована на підготовку інтерактивних документів з обчисленнями і візуальним супроводженням, відрізняється легкістю використання.

Mathcad має простий і інтуїтивний для використання інтерфейс користувача. Для введення формул і даних можна використовувати як клавіатуру, так і спеціальні панелі інструментів.

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

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

Список використаної літератури

mathcad математичний комп’ютерний

1. Методи оптимізації. Методичні вказівки до виконання лабораторних робіт / Уклад. Г. А. Гайна, Н. Л. Попович. — К.: КНУБА, 2011.

2. Методичні вказівки до виконання курсової роботи з дисципліни «Методи оптимізації» / Уклад. Г. А. Гайна. — К.: КНУБА, 2009.

3. Гайна Г. А. Методи оптимізації: алгоритми, приклади, задачі: Навчальний посібник. — К.: КНУБА, 2008. — 144с.