Венетуліс Т.А. , к.т.н., професор кафедри обліку і аудиту
ДВНЗ «НГУ»
Зікрач Фаїна Олександрівна, магістр кафедри обліку і аудиту ДВНЗ «НГУ»
Оптимізація випуску
продукції на підприємстві ресторанного господарства
Підприємство ТОВ «МЛИН»
виготовляє обіди. Обіди пакуються в пакети по 20 обідів у кожному. Такий пакет вважається одиницею
виробів. Збут здійснюється партіями одиниць виробів. Фірма оцінює попит поквартально
відповідно в 100, 200, 180 і 300 одиниць виробів.
Протягом чотирьох кварталів фірма
може випустити 50, 180, 280 і 270 одиниць виробів. Виробництво і попит в різні
квартали не співпадають.
Попит в
поточному кварталі можна задовольнити наступними способами:
-
виробництвом заказів протягом поточного кварталу.
У першому випадку вартість одного пакета з 20 обідів в
середньому складає 1800,00 грн . Фірма планує розробити оптимальний план
виробництва на ці чотири квартали.
Викладену ситуацію можна змоделювати у вигляді
транспортної задачі, використовуючи наступні відповідності між елементами
задачі управління запасами і транспортної моделі.
Таблиця 1.1.
Відмінності між елементами задачі управління
Транспортна модель |
Модель управління запасами |
Пункт відправлення |
Період виробництва |
Пункт призначення |
Період споживання |
Пропозиція в пункті відправлення |
Об'єм виробництва за період |
Попит в пункті призначення |
Об'єм реалізації продукції за період |
Вартість перевезення з пункту в пункт |
Вартість одиниці продукції (виробництво+зберігання + штрафи) за період |
Формулювання завдання у вигляді транспортної моделі (табл. 1.2).
Таблиця 1.2.
Формування завдання
|
квартал 1 |
квартал 2 |
квартал 3 |
квартал 4 |
Об'єм виробництва |
квартал 1 |
1800 |
1850 |
1900 |
1950 |
50 |
квартал 2 |
2000 |
1800 |
1850 |
1900 |
180 |
квартал 3 |
2200 |
2000 |
1800 |
1850 |
280 |
квартал 4 |
2400 |
2200 |
2000 |
1800 |
270 |
Попит |
100 |
200 |
180 |
300 |
|
Транспортна
задача лінійного програмування формулюється так. Маємо m пунктів відправлення А1,
А2,... . Аm, у яких знаходяться запаси якогось однорідного вантажу в
кількості відповідно а1, а2,... .. аm одиниць.
Крім того, є n пунктів призначення В1, В2,... ... Вn, що
подали заявки відповідно на b1, b2,... . bn одиниць вантажу. Передбачається, що сума всіх
заявок дорівнює сумі всіх запасів, тобто
(1.1.)
Позначимо
сij вартість перевезення одиниці товару від кожного пункту відправлення Аi до кожного пункту призначення Вj. Матриця
вартостей С має вигляд
(1.2.)
Потрібно
скласти такий план перевезень, при якому всі заявки були б виконані й загальна
вартість усіх перевезень була мінімальною. Таким чином, у якості критерію
обрана вартість перевезення вантажу. Критеріями в транспортній задачі можуть
бути такі показники: відстань, час, потужність та ін.
Математична постановка транспортної задачі
Математичне формулювання
транспортної задачі може бути подано у такому вигляді: нехай xij¾ кількість вантажу, що
відправляється з i-го пункту відправлення Аi в j-й пункт
призначення Вj (),
xij ³ 0. Змінні xij повинні
задовольняти нерівностям (1)—(7).
(
1.3. )
Оптимальний план - це такий план, що серед усіх припустимих має
найменшу вартість перевезень. Вартість перевезень поміщують
у правому верхньому куті клітин таблиці. Клітини таблиці, у яких будемо
записувати відмінні від нуля перевезення , називаються базисними. Таких клітин не
більш ніж m+n-1. Порожні клітини
називаються вільними, їх не менше (m-1)(n-1).
Розв'язання транспортної задачі
методом потенціалів
Покращання плану перевезень у цьому методі виконується
за допомогою переміщення перевезень із клітини в клітину в транспортній таблиці
без порушення балансу заявок і запасів. Переміщення вантажів у таблиці
виконується за замкнутим циклом.
Циклом у транспортній таблиці
називаються декілька клітин, сполучених замкнутою ламаною лінією, що повертає
на 90° в окремих клітинах. Цикл
будують так, щоб одна його вершина була у вільній клітині, інші вершини в
базисних (заповнених) клітинах.
Існує теорема, відповідно до якої
для будь-якої вільної клітини транспортної таблиці завжди існує цикл ( притім
єдиний), одна з вершин якого лежить у цій зведеній клітині, а всі інші ( у
базисних клітинах).
У кожному циклі заміняють одну
вільну змінну на базисну, тобто заповнюють одну вільну клітину й натомість
звільняють одну з базисних клітин. Цикл має парне число вершин. Будемо
відзначати знаком «+» ті вершини, у яких у результаті переміщення вантажів
перевезення збільшуються, а знаком «-», вершини, у яких вони
зменшуються.
Перенести (перекинути) якусь
кількість одиниць вантажу за циклом - це значить збільшити
перевезення, що стоять у позитивних вершинах циклу, на цю кількість одиниць, а
перевезення, що стоять у негативних вершинах, зменшити на ту ж кількість.
При переносі будь-якої кількості
одиниць за циклом рівновага між запасами й заявками не змінюється. Кількість
одиниць вантажу, що можна перемістити, визначається мінімальним значенням
перевезень, що стоять у негативних вершинах циклу (якщо перемістити більше
число вантажу, виникають негативні перевезення).
Зміна вартості перевезень при
переміщенні однієї одиниці вантажу за циклом називають ціною циклу.
Визначається ціна циклу як алгебраїчна сума вартостей перевезень, що стоять у
вершинах циклу, причому, вартості, що стоять у позитивних вершинах, беруться зі
знаком «+», а в негативних ¾ із знаком
«-». Для поліпшення плану перевезень доцільно переміщати вантажі тільки за
тими циклами, ціна яких негативна.
Розрахунки
оптимального річного плану виробництва
продукції (табл. 1.3.) за алгоритмом методу потенціалів (табл. 1.4.).
Таблиця 1.3.
Опорний план транспортної
задачі
|
|
квартал 1 |
квартал 2 |
квартал 3 |
квартал 4 |
|
|
100 |
200 |
180 |
300 |
квартал 1 |
50 |
50 |
|
|
|
квартал 2 |
180 |
50 |
130 |
|
|
квартал 3 |
280 |
|
70 |
180 |
30 |
квартал 4 |
270 |
|
|
|
270 |
Таблиця 1.4.
Метод потенціалів
|
|
квартал 1 |
квартал 2 |
квартал 3 |
квартал 4 |
|
|
|
100 |
200 |
180 |
300 |
альфа |
квартал
1 |
50 |
|
250 |
500 |
500 |
0 |
квартал
2 |
180 |
|
|
250 |
250 |
-200 |
квартал
3 |
280 |
0 |
|
|
|
-400 |
квартал
4 |
270 |
250 |
250 |
250 |
|
-350 |
|
бета |
1800 |
1600 |
1400 |
1450 |
|
План перевезень оптимальний,
оскільки у вільних клітинах виконується умова альфа + Сij>=бета.
Мінімальна
сума витрат на виробництво одиниць виробів складає 1 429 500,00 грн.
Оптимальний
план виробництва одиниць виробів представлений в табл. 1.5.
Таблиця 1.5.
Оптимальний план
виробництва одиниць виробів
|
|
квартал 1 |
квартал 2 |
квартал 3 |
квартал4 |
|
|
100 |
200 |
180 |
300 |
квартал 1 |
50 |
50 |
|
|
|
квартал 2 |
180 |
50 |
130 |
|
|
квартал 3 |
280 |
|
70 |
180 |
30 |
квартал 4 |
270 |
|
|
|
270 |
Список використаних джерел:
Вагнер Г. Основи
досліджень операцій. Пер. з англ.. М. Мир., 1973, - 552 с.
Акулич М.Л. Математичне
програмування в прикладах і задачах. – М. Вищ. школа, 1986.- 319 с.