Читать контрольная по менеджменту: "Знаходження оптимального числа листів фанери і вирізання потрібного числа заготовок при мінімальних відходах" Страница 1

(Назад) (Cкачать работу)

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

Зі стандартних листів фанери необхідно вирізати заготовки трьох типів у кількості, що відповідно дорівнює 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)

Хі - ціле.

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

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

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

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

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

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

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

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

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

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

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

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

- номер ітерації;

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

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

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