ЗАДАЧА 1
Підприємство спеціалізується на виробництві верхньогожіночого одягу. За підсумками року його фінансовий стан погіршився. Це буловикликано тим, що споживачі залишились не задоволені асортиментом та якістюпродукції, що пропонувалась підприємством. Тому керівництво розробило комплексзаходів, направлених на покращання стану підприємства. В тому числі буловирішено суттєво оновити асортимент продукції. Після вивчення попиту,проведення попередніх продажів був розроблений новий асортимент продукції. Втаблицях 3.1 та 3.2 представлений асортимент, що проектується для одного зпошивочних цехів підприємства.
Необхідно розподілити випуск продукції по місяцямкварталу таким чином, щоб максимізувати прибуток підприємства (побудуватиекономіко-математичну модель задачі оптимізації розподілу випуску продукції учасі у вигляді системи рівнянь і матрично-векторній формі).
Проектованийасортимент для одного з цехів швейної фабрикиВаріант 8 Потік Потік №1 Потік №2 Вид виробу Костюми Піджаки Модель виробу мод. 4808 мод. 4810 мод. 4816 мод. 1806 мод. 1823 Вид матеріалу Вовна Вовна Сукно Сукно Сукно Вовна Трудомісткість виготовлення 1 виробу, годин 3,83 3,81 3,85 2,30 2,35 2,37
Витрати матеріалу на 1 виріб, м2 3,10 3,18 3,15 1,82 1,90 1,92 Оптова ціна 1 виробу, грн. 203,35 200,43 204,08 140,80 142,35 142,42 Прибуток від реалізації 1 виробу, грн. 5,05 5,10 5,07 4,05 4,10 4,13 Місяць, в якому виготовляється І, ІІ ІІІ І, ІІІ ІІ, ІІІ І ІІ, ІІІ
ВиробничіобмеженняВаріант Попит на продукцію по місяцям, тис. шт. Виробнича потужність потоків, тис. шт. Костюми Сукні Піджаки Брюки І ІІ ІІІ І ІІ ІІІ І ІІ ІІІ І ІІ ІІІ Потік №1 Потік №2 8 14,6 13,5 14,8 – – – 10,6 11,4 11,7 – – – 47,5 31,4 Варі-ант Завдання по виручці від реалізації продукції по потокам та місяцям, тис. грн. Наявний фонд робочого часу потоків по місяцям, тис. годин
Запаси матеріалів кожного виду на складах підприємства по місяцям, тис. м2 Потік №1 Потік №2 Потік №1 Потік №2 Сукно Вовна І ІІ ІІІ І ІІ ІІІ І ІІ ІІІ І ІІ ІІІ І ІІ ІІІ І ІІ ІІІ 8 990 970 960 940 850 910 270 280 245 290 260 310 205 210 198 203 202 200
Розв’язок:
Характеристикарізновидів швейних виробівПоказники Асортимент виробів Потік μ Потік №1 μ=1 Потік №2 μ=2 Вид виробу s Костюми s=1 Піджаки s=2 Модель виробу j
мод.4808
j=1
мод.4810
j=2
мод.4816
j=3
мод.1806
j=1
мод.1823
j=2 Вид матеріалу α Вовнаα=1 Вовна α=1 Сукно α=2 Сукно α=2 Сукно α=2 Вовна α=1
Трудомісткість виготовлення 1 виробу, годин tμsjα 3,83 3,81 3,85 2,30 2,35 2,37
Витрати матеріалу на 1 виріб, м2 qμsjα 3,10 3,18 3,15 1,82 1,90 1,92
Оптова ціна 1 виробу, грн. Цμsjα 203,35 200,43 204,08 140,80 142,35 142,42
Прибуток від реалізації 1 виробу, грн. Пμsjα 5,05 5,10 5,07 4,05 4,10 4,13 Місяць, в якому виготовляється v І, ІІ ІІІ І, ІІІ ІІ, ІІІ І ІІ, ІІІ
хμsjαν
х11111
х11112
х11213
х11321
х11323
х22122
х22123
х22221
х22212
х22213
Виробничіобмеження
Попит на продукцію по місяцям, тис. шт. Rsν
Виробнича потужність потоків, тис. шт. Рμ Костюми Піджаки І ІІ ІІІ І ІІ ІІІ Потік №1 Потік №2 14,6 13,5 14,8 10,6 11,4 11,7 47,5 31,4
Завдання по виручці від реалізації продукції по потокам та місяцям, тис. грн.
Цμsjα
Наявний фонд робочого часу потоків по місяцям, тис. годин
Тμν
Запаси матеріалів кожного виду на складах підприємства по місяцям, тис. м2 Qαν Потік №1 Потік №2 Потік №1 Потік №2 Трикотаж Бавовна І ІІ ІІІ І ІІ ІІІ І ІІ ІІІ І ІІ ІІІ І ІІ ІІІ І ІІ ІІІ 990 970 960 940 850 910 270 280 245 290 260 310 205 210 198 203 202 200
Економіко-математичнамодель задачі оптимізації розподілу випуску продукції у часі в алгебраїчнійформі має вигляд:
1) Обсяг випуску готової продукціїповинен відповідати попиту:
/>
де хμsjαν– обсяг виробництва виробів виду s моделі j в μ-ому потоці, якийвідповідно до оптимального плану необхідно виготовляти у періоді ν ізматеріалу виду α;
Rsν – попит на вироби виду s в ν-ому періоді;
Dsν – можливий незадоволений попит навироби виду s в ν-ому періоді.
Рівнянняскладаються для кожного виду виробу по періодам.
s=1 v=1: х11111+х11321+D11 =14600 s=2 v=1: х22221 +D21= 10600
s=1 v=2: х11112+D12 = 13500 s=2 v=2: х22122 + х22212+D22= 11400
s=1 v=3: х11213+ х11323 +D13 = 14800 s=2 v=3: х22123 + х22213+D23= 11700
2) Сумарний випуск виробів виду s моделіj в μ-ому потоці, виготовлених із матеріалу виду α в періоді νне повинен перевищувати потужності потоку Рμ:
/>
де Нμ– можлива невикористана частка потужності потоку μ.
Рівнянняскладаються для кожного потоку.
μ=1: х11111+х11112+ х11213 + х11321 +х11323 + H1 = 47500
μ=2: х22122+х22123+ х22221 + х22212 + х22213+ H2 = 31400
3) Сумарний випуск виробів виду s моделіj в μ-ому потоці, виготовлених із матеріалу виду α в періоді ν воптових цінах повинен бути не менше встановленого завдання по виручці відреалізації продукції Вμν:
4)
/>
де Цμsjα – оптова ціна одиниціпродукції різновиду sjα, яка виготовляється в μ-ому потоці;
Wμν – можливе перевищеннявстановленого завдання по виручці від реалізації продукції в μ-ому потоців періоді ν.
Рівнянняскладаються для кожного потоку по періодам.
μ=1 v=1: 203,35х11111+ 204,08х11321 — W11 = 990000
μ=1 v=2: 203,35х11112- W12 = 970000
μ=1 v=3: 200,43х11213 + 204,08х11323 — W13 = 960000
μ=2 v=1: 142,35х22221 — W21 = 940000
μ=2 v=2:140,80х22122+ 142,42х22212 — W22 = 850000
μ=2 v=3:140,80х22123+ 142,42х22213 — W23 = 910000
5) Сумарні витрати часу на виготовленняусієї продукції в усіх пошивочних потоках не повинні перевищувати наявногофонду робочого часу цих потоків (Тμν) в періоді ν:
/>
де tμsjα – трудомісткість виготовлення виробу різновиду sjα вμ-ому потоці;
Y μv– можливий невикористаний час у пошивочному потоці μ в v-ому періоді.
Рівнянняскладаються для кожного потоку по періодам.
μ=1 v=1:3,83х11111+3,85х11321+ Y11= 270000
μ=1 v=2:3,83х11112+Y12= 280000
μ=1 v=3:3,813х11213 + 3,85х11323 + Y13= 245000
μ=2 v=1:2,35х22221 +Y21= 290000
μ=2 v=2:2,30х22122+ 2,37х22212 + Y22= 260000
μ=2 v=3:2,30х22123+ 2,37х22213 + Y23= 310000
6) Сумарні витрати матеріалу виду αна виготовлення всієї продукції не повинні перевищувати наявних ресурсів Qαν(кількості матеріалу на складі та запланованих обсягів поставок):
/>
де qμsjα – норма витрат матеріалу виду α на виріб різновидуsjα, виготовлений в μ-ому потоці;
Vαν– можливий залишок матеріалу виду α в періоді ν;
Vα(v-1)– залишки матеріалу виду α з попереднього періоду (v-1), які можуть бути використані длявиготовлення продукції в періоді v.
Рівнянняскладаються для кожного виду матеріалу по періодам.
α=1 v=1: 3,10х11111+V11=205000
α=1 v=2:3,10х11112+1,91х22212+V12 — V11=210000
α=1 v=3: 3,18х11213+1,91х22213+V13 — V12=198000
α=2 v=1:3,15х11321+1,90х22221+ V21=203000
α=2 v=2:1,81х22122+V22 – V21=202000
α=2 v=3: 3,15х11323+1,82х22123+V23 – V22=200000
7) Цільова функція – максимізаціясумарного прибутку
/>
де Пμsjα– прибуток, який отримує підприємство від реалізації одного виробу різновидуsjα, виготовленого в потоці μ.
L=5,05х11111+5,05х11112+5,10х11213+5,07х11321+5,07х11323+4,05х22122+4,05х22123++4,10х22221+4,13х22212+4,13х22213→max
8) Умова невід’ємності змінних:
хsjαν≥0, Dsν≥0, Нμ≥0,Wμν≥0, Yμv≥0,Vαv ≥0.
модель швейний асортименттканина
ЗАДАЧА 2
Підприємствоспеціалізується на виробництві верхнього жіночого одягу. Необхідно визначитиоптимальний набір тканин різної ширини в умовах, коли необхідна кількістьтканин оптимальної ширини для виготовлення проектованого асортименту дорівнює4, а на ринку пропонуються тканини 3 ширин. Вартість тканини j-ої ширини, яка витрачається на 1виріб і-ого виду наведена у таблиці 3.3. Виконати необхідні розрахунки тазробити відповідні висновки.Варіант і Модель Мі Значення ширини
Н1
Н2
Н3
Н4
Н5
Н6 Варіант 7 1
М1 8,6 8,5 7,3 7,5 7,5 8,9 2
М2 9,2 9,2 9,8 9,5 9,5 10,0 3
М3 9,0 8,9 9,5 9,4 10,0 9,8 4
М4 9,5 10,3 10,5 10,1 10,5 9,8 5
М5 8,0 8,3 8,0 7,9 8,5 8,5 6
М6 10,2 9,6 10,2 10,0 10,5 10,4
Розв’язок:Модель одягу Значення ширини тканини Модель одягу Значення ширини тканини
Н1
Н2
Н3
Н4
Н5
Н6
Н1
Н2
Н3
Н4
М1
М2
М3
М4
М5
М6
8,6
(9,2)
9,0
(9,5)
8,0
10,2
8,5
(9,2)
(8,9)
10,3
8,3
(9,6)
(7,3)
9,8
9,5
10,5
8,0
10,2
7,5
9,5
9,4
10,1
(7,9)
10,0
7,5
9,5
10,0
10,5
8,5
10,5
8,9
10,0
9,8
9,8
8,5
10,4
М1
М2
М3
М4
М5
М6
8,6
(9,2)
9,0
(9,5)
8,0
10,2
8,5
(9,2)
(8,9)
10,3
8,3
(9,6)
(7,3)
9,8
9,5
10,5
8,0
10,2
7,5
9,5
9,4
10,1
(7,9)
10,0
ΣАj 54,5 54,8 55,3 54,4 56,5 57,4
ΣАj 54,5 54,8 55,3 54,4
Нкл2
Нкл3
Нкл4
Нкл1
Нкл2
Нкл3
Нкл4
Нкл1
φ4,1=min(7,5;8,6)+ min(9,5;9,2)+ min(9,4;9,0)+ min(10,1;9,5)+
min(10,0;10,2) =
= 7,5 + 9,2 + 9,0+ 9,5 + 10,0 = 45,2 – min
φ4,2=min(7,5;8,5)+ min(9,5;9,2)+ min(9,4;8,9)+ min(10,1;10,3)+
min(10,0;9,6) =
= 7,5 + 9,2 + 8,9+ 10,1 + 9,6 = 45,3
φ4,3=min(7,5;7,3)+ min(9,5;9,8)+ min(9,4;9,5)+ min(10,1;10,5)+
min(10,0;10,2) =
= 7,3 + 9,5 + 9,4+ 10,1 + 10,0 = 46,3
φ4,1,2=min(7.5;8.6;8.5)+min(9,4;9,0;8,9)+min(10.0;10,2;9,6)=7,5+8,9+9,6=2
6–min
φ4,1,3=min(7.5;8.6;7,3)+min(9,4;9,0;9,5)+min(10.0;10,2;10,2)=7,3+9,0+10,0
=26,3
Відповідь:тканини шириною Н1, Н2, Н4.
ЗАДАЧА 3
Компаніяволодіє 4 фабриками, продукція з яких надходить до 4 складів. Використовуючидані про щомісячний обсяг випуску продукції та витрати на транспортування(таблиці 3.4 та 3.5), необхідно скласти 3 варіанти надходжень продукції насклад (методами північно-західного кута, найменших витрат, наближень Фогеля).Визначити загальні витрати на транспортування продукції по кожному з варіантів.
Задопомогою методу послідовних кроків, оптимізувати варіант надходжень продукції,розрахований методом північно-західного кута. Зробити відповідні висновки.
Варіант Фабрика Обсяг поставок, од. Склад Потреба, од. 6 АБВГ
12
17
15
20 КЛМН
18
22
10
14 Варіант Фабрика Витрати на транспортування одиниці продукції на склад, грн. К Л М Н 6
А
Б
В
Г
10
12
15
9
13
19
21
16
11
15
12
17
16
17
19
14
/>На склад
З фабрики К Л М Н Поставки з фабрики А 10 13 11 16 12 Б 12 19 15 17 17 В 15 21 12 19 15 Г 9 16 17 14 20 Потреба складів 18 22 10 14
/>64
64
Стадія2. Вихідний розподіл
1.Розподіл методом північно-західного кута
Розподілпочинається з верхнього лівого кута матриці. В клітинах першого рядкапоказується найбільша можлива кількість одиниць. Потім така ж процедураповторюється для другого, третього рядка і далі доти, доки всі потреби небудуть розподілені по рядкам і стовпцям.
Перевага:спрощується алгоритм розподілу.
Недолік:не враховуються витрати транспортування.
/>На склад
З фабрики К Л М Н Поставки з фабрики А 12 10 13 11 16 12 Б 6 12 11 19 15 17 17 В 15 11 21 4 12 19 15 Г 9 16 6 17 14 14 20 Потреба складів 18 22 10 14
/>64
64
Загальнівитрати =12·10 + 6·12 + 11·19 + 11·21 + 4·12 + 6·17 + 14·14= 978 грн.
2.Розподіл методом найменших витрат
В цьому випадкунайбільше значення проставляється в клітину з найменшими витратами. Зв’язкиможуть порушуватися довільно. Закінчується дана процедура після того, як усіпотреби будуть розподілені по рядкам і стовпцям.
/>На склад
З фабрики К Л М Н Поставки з фабрики А 10 2 13 10 11 16 12 Б 12 5 19 15 12 17 17 В 15 15 21 12 19 15 Г 18 9 16 17 2 14 20 Потреба складів 18 22 10 14
/>64
64
Загальнівитрати =2·13 + 10·11 + 5·19 + 12·17 + 15·21 + 18·9 + 2·14= 940 грн.
3.Розподіл методом наближень Фогеля
Етапипроцесу розподілу:
1. В кожному рядку та в кожномустовпці (з урахуванням фіктивних), визначити різницю між двома найменшими урядку або стовпцю значеннями витрат на транспортування.
2. Визначити рядок або стовпецьз найбільшою різницею.
3. Записати найбільше можливезначення одиниць в клітину з найменшими витратами, яка знаходиться в рядку абостовпці з найбільшою різницею, обраною на етапі 2.
4. Закінчити процедуру, якщозадоволені всі потреби рядків або стовпців, інакше перейти до етапу 5.
5. Перерахувати різницю міждвома клітинами з найменшими витратами в кожному рядку та кожному стовпцю, якізалишилися незаповненими. При розрахунку подальшої різниці не потрібновраховувати рядки та стовпці з показниками потреби або поставок, які дорівнюютьнулю. Повернутись до етапу 2. Цей метод у 80% випадків дозволяє отриматиоптимальне або близьке до нього рішення.
/>На склад
З фабрики К Л М Н Поставки з фабрики А 10 12 13 11 16 12 Б 12 19 10 15 7 17 17 В 15 8 21 12 7 19 15 Г 18 9 2 16 17 14 20 Потреба складів 18 22 10 14
/>64
64
1 2 3 4 5 6 7 11-10=1 1 – – – – – 15-12=3 3 3 5 – – – 15-12=3 3 3 3 3 3 3 14-9=5 2 2 2 2 2 – 1 10-9=1 16-13=3 12-11=1 16-14=2 2 – 3 1 2 3 – 3 1 2 4 – 3 – 2 5 – 3 – 2 6 – 3 – – 7 – 2 – –
Загальнівитрати = 12·13 + 10·15 + 7·17 + 8·21 + 7·19 + 18·9 + 2·16 = 920 грн.
Стадія3. Знаходження оптимального рішення
Пошукоптимального рішення полягає в оцінці кожної невикористаної клітини тавизначенні, чи не буде переміщення в неї вигіднішим з позиції зменшеннязагальних витрат. Якщо це так, то переміщення виконується і процес повторюєтьсядоти, поки не будуть оцінені всі клітини та виконані усі відповідніпереміщення.
Методпослідовних кроків
Етапипроцесу:
1. Оберіть будь-яку пустуклітину та укажіть замкнений шлях, що веде до неї. Цей шлях складається згоризонтальних та вертикальних ліній, які ведуть від пустої клітини через іншіназад до неї ж. В замкненому шляху може бути тільки одна пуста клітина – та, щорозглядається. Повороти шляху на 90є можуть виконуватися лише в найближчих допустої заповнених клітинах.
2. Перемістіть одну одиницю іззаповненої клітини у куті замкненого шляху в пусту клітину та приведіть іншізаповнені клітини, що залишилися в інших кутах у відповідність до заданихпотреб та поставок.
3. Визначить доцільністьздійсненого переміщення:
Σвитрат в клітинах, __ Σ витрат в клітинах, до яких була додана одиниця зяких була віднята одиниця
Якщовитрати в результаті переміщень скоротилися, то необхідно перемістити якомогабільше одиниць з оціненої заповненої клітини в пусту. Якщо витрати збільшилися,то ніяких переміщень не виконують, а пусту клітину помічають, щоб більше до неїне повертатися.
4. Повторювати етапи 1 – 3 доти,доки не будуть оцінені всі пусті клітини.
Максимальнакількість одиниць, яку можна додати до будь-якої клітини, не повиннаперевищувати кількість, що вказана в клітині з найменшим значенням, з якої будепроводитися віднімання. Це необхідно для врахування обмежень щодо потреб тапоставок.
Щобвпевнитися, що отриманий розподіл дійсно оптимальний, потрібно знову оцінитикожну пусту клітину та розглянути доцільність переміщення в неї. Якщо в кожнійз перевірених клітин витрати зростуть, то задача вирішена та розподіл єоптимальним.
Якщооцінка пустої клітини дає в результаті таке саме значення, що і розподіл, якийрозглядається, значить існує рівноцінне альтернативне оптимальне рішення.(Зазвичай пусту клітину, визначену як альтернативний оптимальний маршрут,помічають 0.)
Втранспортних задачах у випадках, 1) коли кількість заповнених клітин менше сумикількості рядків та стовпців мінус 1 (m+n-1) або2) коли перше значення в рядку або стовпці задовольняє обмеженням як по рядку,так і по стовпцю, може спостерігатися явище виродження.
Тодів будь-яку пусту клітину (або декілька) записується деяка кількість одиницьθ (зазвичай це 0) таким чином, щоб можна було скласти замкнений шлях дляоцінки інших пустих клітин. Це значення залишається в задачі доти, поки воно незникне при відніманні або до отримання остаточного рішення.
Оптимізаціярозподілу (метод північно-західного кута)
/>На склад
З фабрики К Л М Н Поставки з фабрики А 12 10 г 13 11 16 12 Б 6 12 11 19 б 15 17 17 В в 15 11 21 4 12 а 19 15 Г 9 16 6 17 14 14 20 Потреба складів
/>/>/>/>18 22 10 14
/>64
64
а) В-Н +1 (пустаклітина) + –
В-М -1 19 (В-Н) 12(В-М)
Г-М +1 17 (Г-М) 14(Г-Н)
Г-Н -1 36 > 26
Переміщеннянедоцільно
б) Б-М +1 (пустаклітина) + –
Б-Л -1 15 (Б-М) 19(Б-Л)
В-Л +1 21 (В-Л) 12(В-М)
В-М -1 36 > 31
Переміщеннянедоцільно
в) В-К +1 (пустаклітина) + –
Б-К -1 15 (В-К) 12(Б-К)
Б-Л +1 19 (Б-Л) 21(В-Л)
В-Л -1 34 > 33
Переміщеннянедоцільно
г) А-Л +1 (пустаклітина) + –
А-К -1 13 (А-Л) 10(А-К)
Б-К +1 12 (Б-К) 19(Б-Л)
Б-Л -1 25
Переміщеннядоцільно
/>На склад
З фабрики К Л М Н Поставки з фабрики А 1 10 11 13 д 11 16 12 Б 17 12 + 19 + 15 17 17 В + 15 11 21 4 12 + 19 15 Г 9 е 16 6 17 14 14 20 Потреба складів
/>/>18 22 10 14
/>64
64
д) А-М +1 (пустаклітина) + –
А-Л -1 11 (А-М) 13(А-Л)
В-Л +1 21 (В-Л) 12(В-М)
В-М -1 33 > 25
Переміщеннянедоцільно
е) Г-Л +1 (пустаклітина) + –
В-Л -1 16 (Г-Л) 21(В-Л)
В-М +1 12 (В-М) 17(Г-М)
Г-М -1 28
Переміщеннядоцільно
/>На склад
З фабрики К Л М Н Поставки з фабрики А 1 10 11 13 + 11 є 16 12 Б 17 12 + 19 + 15 17 17 В + 15 5 21 10 12 + 19 15 Г ж 9 6 16 + 17 14 14 20 Потреба складів
/>/>18 22 10
/>14
64
64
є) А-Н +1 (пустаклітина) + –
А-Л -1 16 (А-Н) 13(А-Л)
Г-Л +1 16 (Г-Л) 14(Г-Н)
Г-Н -1 32 > 27
Переміщеннянедоцільно
ж) Г-К +1 (пустаклітина) + –
А-К -1 9 (Г-К) 10(А-К)
А-Л +1 13 (А-Л) 16(Г-Л)
Г-Л -1 22
Переміщеннядоцільно
/>На склад
З фабрики К Л М Н Поставки з фабрики А + 10 12 13 + 11 + 16 12 Б 17 12 + 19 + 15 з 17 17 В + 15 5 21 10 12 + 19 15 Г 1 9 5 16 + 17 14 14 20 Потреба складів
/>18 22 10 14
/>64
64
з) Б-Н +1 (пустаклітина) + –
Б-К -1 17 (Б-Н) 12(Б-К)
Г-К +1 9 (Г-К) 14(Г-Н)
Г-Н -1 26 = 26
Переміщення можнане робити.
Загальнівитрати =12·13 + 17·12 + 5·21 + 10·12 + 1·9 + 5·16 + 14·14= 870 грн.
Отже,всі клітини перевірено і ми впевнились, що отриманий розподіл дійснооптимальний і становить 870 грн.