Зміст
Введення
1. Постановка і аналіз завдання
2. Рішення задачі
3. Опис алгоритму
4. Опис програми
5. Контрольний приклад
Висновок
Текст програми
Література
1. Введення
Зазвичай при виробництві виробів матеріал надходить у вигляді рулонів, смуг, прямокутних листів, стержнів і т. д. Вступник матеріал розкроюється на частини заданих розмірів і певної конфігурації, що представляють собою в одних випадках заготовки, в інших - готові деталі. До завдань розкрою, відносяться і задачі щільного розміщення сукупності предметів на заданих ділянках.
Завдання раціонального розкрою описуються подібними математичними моделями. Істотна відмінність цих моделей визначається головним чином двома факторами:
1) конфігурацією одержуваних при розкрої заготовок;
2) обсягом продукції.
Завдання розкрою, обумовлені першим фактором, підрозділяють на два класи. До першого класу відносяться задачі фігурного розкрою, до другого - завдання нефігурного розкрою. При фігурному розкрої матеріал розкроюється на заготовки самих різних конфігурацій. До класу задач нефігурного розкрою відносяться завдання лінійного і прямокутного розкрою. У першому випадку матеріал розкроюють на заготовки різної довжини, для яких задається тільки один лінійний розмір. Під другому випадку отримують заготовки прямокутної форми, для яких задаються два розміру.
Завдання розкрою, обумовлені другим фактором, також поділяють на два класи: задачі розкрою в умовах масового (великосерійного) випуску виробів і задачі розкрою в умовах одиничного (дрібносерійного) виробництва. До обох класах можуть належати як завдання фігурного, так і завдання нефігурного розкрою. Завдання розкрою в умовах масового виробництва описуються безперервними моделями лінійного програмування, а в умовах одиничного виробництва - цілочисельними. У зв'язку з цим завдання розкрою в зазначених умовах часто називають відповідно безперервними і цілочисельними.
Завдання раціонального розкрою в умовах масового виробництва відносяться до класу задач лінійного програмуванні, з неявно заданими стовпцями (способами розкроу). При вирішенні таких завдань методами лінійного програмування виникає необхідність у генеруванні розкрою на кожному кроці процесу. Нижче розглянута задача генерування лінійних розкрою.
1. Постановка і аналіз завдання
Вирішити завдання гільйотинного розкрою матеріалу (довгомірного прокату) з максимальним прибутком: шматок матеріалу завдовжки L розкроюється на заготовки m найменувань, для кожної заготовки з номером i = відомі її довжина l i і оцінка з i . Потрібно знайти розкрій з максимальною оцінкою одержуваного набору заготовок.
Задача оптимального розкрою довгомірного прокату носить різний характер в залежності від типу виробництва. Наприклад, для великосерійного виробництва характерні наступні завдання: прагнення отримати значне число заготовок однакової довжини, мінімізувати залишок, отримати максимальний прибуток від розкрою і т.д. В даній курсовій роботі буде розглянуто рішення задачі оптимального розкрою матеріалу з максимальним прибутком методом динамічного програмування з використанням так званої "сітковим методом", при якому виникає необхідність генерування розкрою на кожному кроці процесу.
2. Рішення задачі
Припустимо, що шматок матеріалу довжиною L розкроюється на заготовки m найменувань. Для кожної заготовки з номером i = відомі її довжина l i і оцінка з i . Потрібно знайти розкрій з максимальною оцінкою одержуваного набору заготовок.
Розкрій може містити будь-яке число кожної з заготовок. Тоді набір заготовок характеризується m-вимірним вектором
X = (x 1 , x 2 , ..., x m ), (1)
Елементи якого являють собою цілі невід'ємні компоненти, що вказують на число заготовок кожного виду. При цьому потрібно максимізувати сумарну оцінку
(2)
набору заготовок (1) при єдиному лінійному обмеженні
. (3)
Генерування розкрою будемо розглядати як багатокроковий циклічний процес, що складається з послідовного вибору окремих заголовок.
Для вирішення поставленої завдання розглянемо функцію
(4)
xГЋX l
де через X i позначено безліч невід'ємних векторів х, що відповідають розкрою, в яких загальна довжина заготовок не перевершує довжини l. Нехай l 0 = min l i , де i = 1 ... m.
Тоді при всіх lГЋ [0, l 0 ] відповідні множини X l складаються з одного нульового елемента і, отже, f (l) = 0 для всіх таких l. Для lГЋ [0, L 0 ], справедливі наступні рекурентні співвідношення:
, (5)
iГЋI l
де через I l позначено безліч тих i, при яких l i ВЈ l.
Спираючись на рекурентні співвідношення (5), можна для вирішення завдання запропонувати простий чисельний метод, представляє собою перебір всіх допустимих розкрою. Реалізація всього процесу грунтується на двох етапах:
Перший етап
На першому етапі здійснюється так званий прямий хід: за формулами (5) для всіх l = послідовно обчислюються функції f (l) і при цьому фіксуються індекси i (l), при яких досягається максимум у виразі (5). Одержувана при цьому інформація l, f (l) і i (l) запам'ятовується і порядково записується в таблицю:
l
l 0
l 0 + 1
l 0 + 2
...
L
f (l)
f (l 0 )
f (l 0 + 1)
f (l 0 + 2)
...
f (L)
i (l)
i (l 0 )
i (l 0 + 1)
i (l 0 + 2)
...
i (L)
Другий етап
На другому етапі здійснюється так званий зворотний хід: для отримання шуканого вектора х (1), для якого виконується рівність m (x) = f (L), в розкрій в першу чергу включаються заготівля з номером i (l 1 ), де l 1 = L, і підраховується значення l 2 = l 1 -l i ( l 1) .
Якщо l 2 Ві l 0 , то в розкрій включається заготовка з номером i (l 2 ) і підраховується значення l 3 = l 2 -l i ( l 2) і т.д. Так як при кожному k Ві 1 очевидно, що l k +1 ВЈ l k -l 0 , то через кінцеве число описаних кроків виявиться, що l k +1 0. На цьому генерування шуканого розкрою закінчується і виводиться результат.
3. Опис алгоритму
1. Визначається поточне значення довжини розкрою l від мінімальної довжини деталі до довжини матеріалу.
2. Обчислюється максимальний індекс (номер) деталі, додавання якої можливо.
3. Якщо немає деталей, які можна додати в розкрій, то перевіряється не досягнуть чи максимум ціни розкрою для поточного значення довжини розкрою l.
Якщо максимум досягнутий, то він запам'ятовується. Остання додана деталь видаляється з розкрою та додається наступна (п. 4). Якщо немає деталей які можна додати в ...
