Знаходження оптимального числа листів фанери и Вирізання потрібного числа заготовок при мінімальніх відходах
Вступ
Завдання на виконан:
Зі стандартних листів фанери та патенти вірізаті заготовки трьох тіпів у кількості, что відповідно дорівнює 24, 31 и 18 штук. Коженая лист фанери может буті розрізаній двома способами. Кількість заготовок и величина відходів матеріалу, Які можна отріматі при даного способі розкрио, наведені в табл. 1.
Таблиця 1:
Тип заготовкіКількість заготовок, шт.Першій способ розкроюДругій способ розкроюА26В54С23Велічіна відходів, див лютого 1216
1. Математична модель задачі
12х1 + 16X2 - gt; min
2х1 + 6х2 gt;=24
5х1 + 4х2 gt;=31
2х1 + 3х2 gt;=18
Хі gt;=0 (i=1,2)
Хі - ціле.
2. Обґрунтування Вибори методу розв язання задачі
Оскількі в поставленій задачі цільова функція прямує до мінімуму (мінімізація величини відходів) i вона лінійно покладів від елементів решение та є обмеження, Які представляються собою лінійні нерівності, тоді поставлено завдання є задачею лінійного програмування. Та оскількі є Вимога, что змінні є цілімі числами (Кількість заготовок - ціле число), тоді відповідно задача являється задачею цілочісельного лінійного программирования. Математична модель поставленої задачі відповідає математічній моделі задачі цілочісельного лінійного программирования:
Існує два методи решение задач цілочісельного лінійного программирования:
1. Метод відсікання (алгоритм Гоморі): суть методу Полягає в тому, что при отріманні нецілочісельного решение необходимо побудуваті Рівняння, Пожалуйста відсіче отриманий оптимальний результат и залиша всі Інші значення ОДР. После цього завдання знову вірішується. Таким чином завдання вірішується до тихий пір, поки НЕ буде ОТРИМАНО цілочісельне решение задачі.
2. Метод гілок и границь: метод представляет собою комбінаторній метод, Який предполагает побудову розгалуження простору РІШЕНЬ и відкідання областей, Які НЕ вміщують Допустимі цілочісельні решение. У методі вірішується послідовність релаксованіх завдань и на Кожній ітерації віконується оцінка верхньої границі оптимального решение. Процес решение задачі є процесом породження гілок и побудова границь цільової Функції.
Для вирішенню цієї задачі в рамках курсового проекту вікорістаємо алгоритм Гоморі.
3. Алгоритм розв язання задачі (алгоритм Гоморі)
1. Симплекс методом вірішуємо задачу:
візначаємо індексній рядок:
вибір розв язального стовпчики:
При ц.ф. max:, если всі, то решение пункту | Полтава;
При ц.ф. min, если всі, то решение пункту | Полтава;
вибір розв язального рядка і визначення розв язального елемента:
, Если всі, то завдання не має решение и є НЕОБМЕЖЕНИЙ;
У розв язальному рядку запісується:
У розв язальному стовпчики запісується:, для всіх r, крім r=i,
Для всіх других елементів, крім r=i та k=j, вікорістовується правило прямокутник:
,
- номер ітерації;
перераховуємо табліці.
Если отриманий оптимальний результат є цілочісельнім, тоді решение задачі | Полтава.
. Нехай среди координат отриманий оптимального решение є НЕ цілі числа. Оберемо среди ціх змінніх ту, яка має найбільшу дробів часть: xs=bs. Цій змінній відповідає Якийсь рядок. Для цього рядка справедлива Рівність:
.
Рівняння:
,
буде додаватісь в Останню симплекс таблицю для продовження решение. Змінна U i буде (n + 1) змінною І буде брати в якості базісної, для неї буде вводітісь додатковий стовпчики.
. Двоїстім симплекс методом вірішується отримай завдання:
від ємне дробів число візначає вектор, Який виводу з базису. Вектор, Який вводитися в базис обчіслюється за формулою:
- відносно розв язального елєментів перераховується симплекс таблиця.
...
