WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Транспортна задача (ТЗ). Постановка, методи розв’язування та аналізу - Реферат

Транспортна задача (ТЗ). Постановка, методи розв’язування та аналізу - Реферат


Реферат на тему:
Транспортна задача (ТЗ). Постановка, методи розв'язування та аналізу.
План.
1. Знаходження розв'язку деяких економічних задач. Що зводяться до транспортних задач.
2. Приклади розв'язування задач.
3. Література
Знаходження розв'язку деяких економічних задач, що зводяться до транспортної задачі .
Задача 1. На текстильному підприємстві знаходиться три типи ткацьких станків. На станках кожного із типів можуть вироблятися чотири типи тканин: міткаль, бязь, ситець і сатин. Виробництво кожного станка і собівартість тканин наведені в таблиці 1.
Таблиця 1.
Тип станка Виробництво станка (м/год) при виготовленні Собівартість (грн.) тканини при виготовленні 1( м/год)
міткалю бязі ситцю сатину міткалю бязі ситцю сатину
I 24 30 18 24 2 1 3 1
II 12 15 9 21 3 2 4 1
III 8 10 6 14 6 3 5 2
Враховуючи, що фонд робочого часу кожної із груп ткацьких станків відповідно дорівнює 90, 220, 180 станко-годин створюючи такий план із завантаження, при якому загальна собівартість випускаючих тканин в кількості 1200м. міткалю, 900м. бязі, 1800м. ситцю і 840м. сатину є мінімальною.
Розв'язання. Складемо математичну модель задачі. Врахуємо, що i-ий тип станків зайнятий виготовленням j-го виду тканин станко-годин. Тоді змінні повинні задовольняти слідуючі рівняння :
(1)
(2)
Змінні повинні задовольняти також умови невід'ємності:
(3)
Серед всіх можливих значень невідомих , задовольняючих рівнянь (1) і (2) і умови невід'ємності змінних (3), необхідно знайти таке, при якому лінійна функція
(4)
приймає найменше значення.
Змінимо математичну модель задачі таким чином, щоб звести її до моделі транспортної задачі. Для цього наведемо вихідні дані і невідомі величини вихідної задачі до одної одиниці, в якості якої візьмемо одну станко-годину роботи станків I-го типу. Тоді, оскільки виробництво станків II-го і III-го типів відповідно складають 12 і 13 виробництва станків I-го типу (табл. 1), фактичний фонд робочого часу у наведених станко-годинах складає 90+105+60=255.
Визначимо тепер скільки часу потрібно для виготовлення потрібної кількості кожної із видів тканини. Так як потрібно виготовити 1200м. міткалю і за одну наведену станко-годину можна виробити 24м., то для випуску необхідної кількості міткалю потрібно 1200/24=50 станко-годин. Аналогічно визначаємо потреби для виготовлення бязі, ситцю і сатину. Ці потреби відповідно складають 30, 100 і 20 станко-годин.
Позначимо тепер через xij кількість наведених станко-годин i-го типу станків, використовуючих при виготовленні j-го виду тканин. Тоді системи рівнянь (1) і (2) вихідної задачі можна переписати так
(5)
(6)
де
(7)
Цільова функція (4) вихідної задачі записується у вигляді:
. (8)
В результаті приходимо до наступної математичної задачі: вимагається серед всіх невідповідних розв'язків систем лінійних рівнянь (5) і (6) знайти таке, при якому функція (8) приймає мінімальне значення.
Таким чином, вихідна задача зводиться до задачі, математична модель якої нічим не відрізняється від транспортної задачі.
Оскільки 90+105+60=225 > 50+30+100+20=200, отримана задача має відкриту модель. Тому, щоб знайти її розв'язок, врахуємо, що є фіктивна необхідність в тканинах, на виготовлення яких необхідно затратити 255-200=55 станко-годин.
Отриману в результаті останнього припущення задачу розв'язуємо методом потенціалів (табл.2).
Таблиця 2.
Тип станків Тканина Виробнича потужність
міткаль бязь ситець сатин ін. тканина
I 2 1 3 1 0 90
90
II 6 4 8 2 0 105
50 30 10 15
III 18 9 15 6 0 60
5 55
Необхідність в тканинах 255
50 30 100 20 55
Як видно із таблиці 2, оптимальний план задачі (5)-(8) визначається матрицею:
Використовуючи відповідність (7), для визначення оптимального плану вихідної задачі (1)-(4) отримаємо матрицю:
Таким чином, згідно плану виготовлення тканин, передбачається використовувати 90 станко-годин станків I типу для виробництва ситцю, відповідно 100, 60, 20 і 30станко-годин станків II типу для виготовлення міткалю, бязі, ситцю і сатину, 15 станко-годин станків III типу для виробництва сатину. При цьому 155 станко-годин станків III типу залишаються вільними.
По відношенню з даним планом на станках I типу виготовляється 1620м. ситцю, на станках II типу 1200м. міткалю, 900м. бязі, 150м. ситцю і 630м. сатину, на станках III типу - 210м. сатину. При цьому 165 станко-годин станків III типу можуть бути використані для виготовлення надпланової продукції. При даному плані виготовлення тканин їх собівартість є мінімальною і складає:
.
Задача 2. На п'ятьох точильних станках різних типів можна виконувати п'ять операцій по обробці деталі. При цьому на кожному із станків може бути закріплена лишень одна операція і одна й та ж операція може виконуватися тільки одним станком. Знаючи час виконання кожної із операцій на кожному із станків, що задається матрицею:
скласти такий розподіл виконуючих операцій між станками, при якому загальні затрати часу на виготовлення деталі є мінімальними.
Розв'язання. Складемо математичну модель задачі. Позначимо через ( ) змінну, значення якої дорівнює одиниці, якщо на i-му станку j-та операція станку виконується, і дорівнює нулю у протилежній ситуації. Тоді закріплення за кожним станком тільки одної операції виражається рівняннями:
(9) а закріплення кожної із операцій тільки на одному станку - рівняннями:
(10)
Необхідно знайти такі значення невідомих ( ), задовольняючих системи лінійних рівнянь (9) і (10) і рівні 0 або 1, при яких функція:
(11) приймає мінімальне значення.
Оптимальний план сформульованої задачі може бути знайдений методами розв'язання транспортних задач. Знайдемо його методом потенціалів (табл. 3).
Таблиця 3.
Станки Операції За кожним станком закріплюється одна операція
1 2 3 4 5
I 2
0 4
6
8 3
1 1
II 1
1 3 2
0 7 6 1
III 7
2
1 4 5 8 1
IV 9
1
0 3
4
1 6 1
V 3
2 1
1 4
0 5 1
Кожна операція виконується тільки на одному станку 1 1 1 1 1 5
Як видно, оптимальним планом задачі є план, згідно якого на I станку виконується п'ята операція, на II - перша операція, на III - друга операція, на IV - четверта операція і на V станку - третя операція. У відповідності з цим планом час переробки деталі є мінімальним і складає: .
Література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.:КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка" (Інформаційно-видавничий центр"Інтелект+" Інститут післядипломної освіти) "Інтелект - Захід", 2004. - 448 с.
3. Акулич М.Л. Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.270-274.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: "Рута", 1998.-168 с.
Loading...

 
 

Цікаве