Характеристика Mathcad як системи комп'ютерної алгебри з класу систем автоматизованого проектування. Опис математичної моделі задачі. Обґрунтування вибору методу її розв’язання симплекс-методом, алгоритм Гоморі. Аналіз результатів роботи в MathCAD.
Краткое сожержание материала:

Размещено на

12

Размещено на

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

Вступ

Завдання на виконання:

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

Таблиця 1:

Тип заготовки	Кількість заготовок, шт.
	Перший спосіб розкрою	Другий спосіб розкрою
А	2	6
В	5	4
С	2	3
Величина відходів, см2	12	16

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. Розв'язання задачі вручну

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

12x1+ 16x2+ 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)

Базис	БР	x1	x2	x3	x4	x5
x3	-24	-2	-6	1	0	0
x4	-31	-5	-4	0	1	0
x5	-18	-2	-3	0	0	1
F(X0)	0	12	16	0	0	0

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

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

Базис	БР	x1	x2	x3	x4	x5
x3	-24	-2	-6	1	0	0
x4	-31	-5	-4	0	1	0
x5	-18	-2	-3	0	0	Другие файлы: Расширение понятия числа Число как основное понятие математики. Натуральные числа. Простые числа Мерсенна, совершенные числа. Рациональные числа. Дробные числа. Дроби в Древне... История математических констант - числа "пи" и "е" Письменная история числа "пи", происхождение его обозначения и "погоня" за десятичными знаками. Определение числа "пи" как отношения длины окружности... Простое доказательство великой теоремы Ферма Из уравнений / 18/ и /19/ следует, что необходимым условием для того чтобы числа В и С были целыми, является также одинаковая четность чисел A и X: об... Удосконалення технологічного процесу виготовлення фанери Технічні вимоги до фанери загального призначення. Аналіз використання деревинних та клейових напівфабрикатів. Параметри установки ступінчатого тиску.... Расчет числа теоретических тарелок простых и сложных ректификационных колонн Выбор оптимального варианта оформления процесса ректификации смеси. Построение диаграмм для бинарной системы. Расчёт числа теоретических тарелок полно...